Logica Formal

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Universidade Federal de Alagoas
Lógica, Informática e Comunicação
Módulo 4 – Lógica Formal
Prof.: Thiago Sales
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Tópicos
Introdução a Logica Formal
Conectivos Lógicos
Lógica Formal Proposicional
Tabela-Verdade
Classificação de Fórmulas
Equivalência entre Fórmulas
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Se eu ganhar na loteria, sou rico
Ganhei na loteria
Logo, sou rico
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Se fizer sol, eu irei a praia
Está fazendo sol
Logo, irei a praia
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Se eu comer bastante, passarei mal
Comi bastante
Logo, passo mal
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Todos os argumentos anteriormente discutidos possuem a mesma forma
Se <alguma coisa> então <outra coisa>
<alguma coisa>
Logo, <outra coisa>
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
A forma de raciocínio é exatamente a mesma
Apresenta um conjunto de regras abstratas de raciocínio que são comuns em vários argumentos
Sentenças declarativas serão apresentadas por letras
Se A, então B.
A.
Logo, B.
A essa forma, damos o nome de “Modus Ponens”
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Alguns argumentos possuem outras formas com as expressões abaixo
Negação: “não é o caso que” ou “não”
Conjunção: “e”
Disjunção: “ou”
Implicação ou “condicional”: Se... , então...
Bi-implicação (ou bi-condicional): ....se e somente se...
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
“Não é o caso que”
Prefixa uma sentença para tornar negação
Ex.: “Ele é jogador”
 “Não é o caso que ele é jogador”
Outras variações gramaticais
 Ex.: “Ele não é jogador”
 Ex.: “Ele é não-jogador”
 Ex.: “Ele não joga”
Abstraindo: “Não é o caso que P”, onde P = “Ele é jogador”
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Conectivo “e”
Une duas sentenças (proposições) quaisquer, formando uma proposição composta - Conjunção
Ex.: Os homens estudam e trabalham
Forma geral: A: homens estudam e B: homens trabalham
A e B
Variações gramaticais: embora, mas, contudo, todavia
Ex.: Os jogadores são atletas mas não gostam de treinar
Ex.: José gosta de pizza embora não possa comê-las
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Conectivo “ou”
Une duas sentenças (proposições) quaisquer, formando uma proposição composta - Disjunção
Ex.: Os homens estudam ou trabalham
Forma geral: A: homens estudam e B: homens trabalham
A ou B
“ou” não deve passar a ideia de escolha única. Ambos os eventos podem acontecer ao mesmo tempo
ou exclusivo: “ou um ou outro”
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Conectivo “Se..., então...”
Resulta em proposições chamadas de “Implicação” ou “Condicionais” - Expressa condição
Ex.: “Se o jogador cansar, então ele deve sair do jogo”
 A: “o jogador cansar”: antecedente
 B: “ele deve sair do jogo”: consequente
 Forma geral: Se A então B
Pode gerar falácias
Falácia do consequente. Ex.: Inicialmente afirma-se que o “jogador saiu do jogo”. Logo, arrisca-se afirmar que o “jogador estava cansado” (não necessariamente)
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Conectivo “Se..., então...”
Antecedente: condição suficiente
Consequente: condição necessária
Ex.: Se sou juiz então sou advogado
*
LIC – Lógica, Informática e Comunicação
Antecedente
Consequente
Condição Suficiente
Condição Necessária
Juiz
Advogado
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Conectivo “Se..., então...”
Os enunciados podem vir invertidos
Ex.: “Durmo se me sentir cansado”
 “Se me sentir cansado, durmo”
 “Se me sentir cansado, então durmo”
Variações gramaticais: “Se faz sol então faz calor”
“Fazer sol implica em fazer calor”
“Se faz sol, logo faz calor”
“Fazer sol é condição suficiente para fazer calor”
“Fazer calor é condição necessária para fazer sol”
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Conectivo “....se e somente se...”
Também conhecido como “bi-implicação”
Ex.: “Como se e somente se estou com fome”
De forma abstrata:
A = “como”
B = “estou com fome”
A se e somente se B
Pode ser visualizada como uma composição de duas condicionais
Ex.: “Se estou com fome, então como”
 “Se como, então estou com fome”
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Conectivos ou Operadores Lógicos
Através dos conectivos, pode-se construir enunciados mais complexos
Ex.: A ou não é o caso que B se e somente se não é o caso que A e B.
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Sistema formal no qual fórmulas são proposições
Fórmulas são compostas por proposições atômicas e conectivos lógicos
Representados por símbolos
Regras de derivação ditam o processo de prova de validade ou invalidade de um argumento dedutivo
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Símbolos da lógica Proposicional
“Não é o caso que”: ~, ¬
“...e...”: ^ ou &
“...ou...”: ∨
“Se..., então...”: →
“... se e somente se ...”: ↔
Ex.: A ou não é o caso que B se e somente se não é o caso que A e B
 A v ~B ↔ ~A ∧ B
A e B são chamados de átomos da fórmula
v, ~, ↔ são os conectivos lógicos
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Fórmulas maiores pode tornar complexa a leitura
Precedência de Operadores
Os símbolos dos conectivos lógicos possuem prioridades hierárquica (assim como na matemática)
Do maior para o menor: ~, ^, ∨, →, ↔
Na fórmula anterior: A ∨ ¬B ↔ ¬A ∧ B
(A ∨ (¬B)) ↔ ((¬A) ∧ B)
Cuidado com os parênteses
~A v B é semanticamente diferente de ~(A v B)
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Se uma fórmula estiver sintaticamente
correta, diz-se que ela é uma “Fórmula bem formada” - fbf
Qualquer letra do alfabeto é uma fbf
Ex.: A, b, w, X
Se A é uma fbf, ¬A também é uma fbf.
Assim como B↔ ¬A, ¬(B↔ ¬A) também é fbf.
Se A e B são fbfs, então (A ∧ B), (A ∨ B), (A → B), e (A ↔ B) também são fbfs
(B ↔ ¬A) ∧ (A ∧ C), (B ↔ ¬A) ∨ (A ∧ C), 
(B ↔ ¬A) → (A ∧ C), e (B ↔ ¬A) ↔ (A ∧ C)
Não são fbfs: Ex.: ∧C, A∨ → B, A ↔ , A¬B
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Tabela-Verdade
Supondo A e B como fbf
Se A é verdadeira, então ~A é falsa.
(A ^ B) é verdadeira se, e somente se, A e B forem verdadeiros. Caso contrário, (A ^ B) é falsa.
(A ∨ B) é verdadeira se pelo menos uma proposição for verdadeira. Caso contrário, (A v B) é falsa.
(A → B) é falsa se A for verdadeira e B for falsa. Caso contrário, (A → B) é verdadeira.
(A ↔ B) é verdadeira se A e B possuem o mesmo valor verdade.
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Tabela-Verdade
Tabela matemática que apresenta todas as possíveis valorações de uma fórmula
Ex.: para um certo átomo “A” existem apenas dois possíveis valores: V ou F – Princípio do Terceiro-Excluído
*
LIC – Lógica, Informática e Comunicação
Cada linha da tabela representa uma 
possível interpretação para o átomo (proposição)
 “A”
Ex.: A = “Eu fui ao cinema” (pode ser V ou F)
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Tabela-Verdade para os conectivos lógicos apresentados
Sendo “A” e “B” átomos da mesma fórmula
O número total de interpretações são 2n onde n = número de átomos da fórmula
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Processo de construção da Tabela-Verdade
Etapa 1: identificar as proposições atômicas e calcular o número de interpretações
(A ∧ ~B) ∨ C: 2n = 23 = 8 interpretações
*
LIC – Lógica, Informática e Comunicação
= 8 interpretações
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Processo de construção da Tabela-Verdade
Etapa 2: Identificar os átomos precedidos de negação. São também colunas da tabela-verdade
(A ∧ ~B) ∨ C ->>>>> ~B
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Processo de construção da Tabela-Verdade
Etapa 3: Identificar as fórmulas com apenas um operador binário. São também colunas da tabela-verdade
(A ∧ ~B) ∨ C ->>>>> (A^~B)
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Processo de construção da Tabela-Verdade
Etapa 4: Completar com uma coluna sendo a fórmula inteira
(A ∧ ~B) ∨ C
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Processo de construção da Tabela-Verdade
Etapa 5: Preencher os valores das interpretações
(A ∧ ~B) ∨ C
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Classificações das Fórmulas
Podem ser classificadas de acordo com os valores verdade
Satisfatível ou consistente: se possui pelo menos uma interpretação com valor “V” (verdadeira)
Ex.: conectivo “E” é consistente (ou satisfatível)
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Classificações das Fórmulas
Falsificável : se possui pelo menos uma interpretação com valor “F” (falsa)
Ex.: conectivo “E” é falsificável
Se uma fórmula for satisfatível (consistente) e falsificável ao mesmo tempo, esta é chamada de contingência
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Classificações das Fórmulas
Insatisfatível, inconsistente, contradição ou antilogia: se nenhuma interpretação satisfaz a fórmula. Ou seja, todas as interpretações são falsas.
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Classificações das Fórmulas
Válida ou tautologia: se todas as interpretações satisfazem a fórmula. Ou seja, se todas as interpretações são verdadeiras.
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Classificações das Fórmulas
Existem relações entre as classificações
Se uma fórmula é válida (tautologia), ela é também satisfatível (consistente), mas não o contrário 
Se uma fórmula é insatisfatível (contradição, inconsistente), ela também é falsifivável, mas não o contrário
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Classificações das Fórmulas
*
LIC – Lógica, Informática e Comunicação
Fórmula
Tautologia
Ou válida
Contingência
Insatisfatível,
Contradição, 
Antilogia ou
inconsistente
Todas as 
interpretações 
são verdadeiras
Pelo menos uma 
Interpretação
é verdadeiras
Pelo menos uma 
Interpretação
é falsa
Todas as 
interpretações 
são falsas
Satisfatível ou 
consistente
Falsificável
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Exercícios de Fixação
1. Informe se as seguintes fórmulas são ou não uma fbf
A → B
B ^ ~A
C v → B
A ↔ C ^
2. Construa a tabela-verdade das seguintes fórmulas
(A → B) ^ A → B – Modus Ponens
(A → B) ^ ~B → ~A – Modus Tollens 
~P v Q
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Equivalência entre Fórmulas
Duas Fórmulas são equivalentes se, e somente se, ambas possuem os mesmos valores-verdades para cada interpretação
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Equivalência entre Fórmulas
A ↔ B = A → B ^ B → A
A → B = ~A v B
A v B = B v A		 - A ^ B = B ^ A
(A v B) v C = A v (B v C) - (A ^ B) ^ C = A ^ (B ^ C)
A v (B ^ C) = (A v B) ^ (A v C) –
 A ^ (B v C) = (A ^ B) v (A ^ C)
Leis da distributividade
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Equivalência entre Fórmulas
A v (falso) = A 		 - A ^ (verdadeiro) = A
A v (verdadeiro) = verdadeiro - A ^ (falso) = falso
A v ~A = verdadeiro 		- A ^ ~A = falso
~(~A) = A
~(A v B) = ~A ^ ~B		- ~ (A ^ B) = ~A v ~B
Leis de De Morgan 
~(A v B) → ~A ^ ~B
~(A ^ B) → ~A v ~B
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Exercícios de Fixação – Julgue 
Se a proposição T é verdadeira e a proposição R é falsa, então a proposição R → (¬T ) é falsa.
Das proposições abaixo, a única que é logicamente equivalente a p → q é:
a) ¬q → ¬p
b) ¬q → p
c) ¬p → ¬q
d) q → ¬p
e) ¬(q → p)
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Exercícios de Fixação – Julgue 
A proposição ¬[p ∨ ¬(p ∧ q)] é logicamente falsa.
Seja a sentença {[(p → q) ∨ r] ↔ [q → (¬p ∨ r)]}. Se considerarmos que p é falsa, então é verdade que:
a) essa sentença é uma tautologia.
b) o valor lógico dessa sentença é sempre F.
c) nas linhas da Tabela-Verdade em que p é F, a sentença é V.
d) nas linhas da Tabela-Verdade em que p é F, a sentença é F.
e) faltou informar o valor lógico de q e de r.
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Exercícios de Fixação – Letra “e”
(A → B) ^ A ∧ B ^ ¬B ∨ C → A∧C
{ [ (A → B) ^ A ∧ B ^ ¬B ] ∨ C} → (A ∧ C)
*
LIC – Lógica, Informática e Comunicação
P1
P2
P3
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
Lógica Formal
Lógica Proposicional
Exercícios de Fixação – Letra “e”
(A → (C ∨ B) ^ A ∨ ¬¬¬B ∧ C) → (C ∨ B)
(A → { [(C ∨ B) ^ A] ∨ [¬¬¬B ∧ C] }) → (C ∨ B)
*
LIC – Lógica, Informática e Comunicação
P1
P2
P3
P4
P
LIC – Lógica, Informática e Comunicação
*
LIC – Lógica, Informática e Comunicação
a) A → ^B
b)A ↔ ~B
c) A ^ ~C
d) ~A → ~B
e) ~A ^ → B
f) ~A~ ^ B
g) A v B ↔ C
*
LIC – Lógica, Informática e Comunicação
LIC – Lógica, Informática e Comunicação
*
*
*
*
*
Os argumentos apresentados no slide anterior possuem a mesma forma de raciocínio. Ou ainda, os argumentos anteriores são “instâncias” ou “variações gramaticais” da forma apresentada nesse slide.
*
*
Semanticamente, todos os exemplos desse slide é a mesma coisa, porém, com sintaxes diferentes.
*
Semanticamente, todos os exemplos desse slide é a mesma coisa, porém, com sintaxes diferentes.
	- Na gramatica portuguesa, as palavras conectivos “embora”, “mas”, etc geram as “conjunções adversativas”
- Obs.: Os exemplos com variações gramaticais possuem a forma: A e “não é o caso que” B, onde A = “Os jogadores são atletas” e B = “gostam de treinar” ou A = “José gosta de pizza” e B = “Não é o caso que” possa comê-las
*
*
*
Outros exemplos:
“Se chover então a rua fica molhada”. A condição de chover já é o SUFICIENTE para rua ficar molhada. Entretanto, se a rua está molhada “não necessariamente” choveu, apesar de que pode ser uma “CONDIÇÃO NECESSÁRIA” para a rua ficar molhada.
*
*
*
*
*
*
*
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
 
*
Modus Ponens
A B A->B ^A Formula
V V V V v
V F F F v
F V V F v
F F V F v
Modus tollens
A B ~B A->B ^~B Formula
V V F V F v
V F V F F v
F V F V F v
F F V V V v
*
*
*
*
*
*
*
*