Validade Fórmulas

Prévia do material em texto

Lógica Proposicional
 Validade de fórmulas
Material baseado no livro Lógica para ciência da computação: fundamentos de 
linguagem, semântica e sistemas de dedução, João Nunes de Souza. 
Validade de fórmulas
 Métodos para determinação de validade de fórmulas
 Tabela verdade
 Árvore semântica
 Negação ou absurdo
Tabela verdade
 Método da força bruta
 Dada uma fórmula H, suponha P1, P2,..., Pn
 São consideradas todas as possibilidades de valores de 
verdade
 Exemplo: leis de De Morgan
 Define a regra de distribuição do conectivo ¬ em uma 
conjunção/disjunção
 H=¬(P∧Q) ↔ (¬P ∨ ¬Q) 
 G=¬(P∨Q) ↔ (¬P∧¬Q) 
Tabelas
 Exemplo: leis de De Morgan
 H=¬(P∧Q) ↔ (¬P ∨ ¬Q)
 G=¬(P∨Q) ↔ (¬P∧¬Q) 
P Q ¬(P∧Q) (¬P ∨ ¬Q) H ¬(P∨Q) (¬P∧¬Q) G
T T F F T F F T
T F T T T F F T
F T T T T F F T
F F T T T T T T
Tabela verdade
 A partir da tabela verdade associada a uma fórmula H é 
possível obter várias propriedades semânticas
 Se a coluna de H contém apenas o símbolo T, então H é uma 
tautologia
 Se a coluna de H contém apenas o símbolo F, então H é uma 
contradição.
 Se a coluna de H contém pelo menos um símbolo T, então H é 
satisfazível.
 Método aplicável a fórmulas que contém um pequeno número 
de símbolos proposicionais – tabelas pequenas
 Uma fórmula que contenha 8 símbolos proposicionais tem 
tabela verdade associada contendo 256 linhas (2n)
Árvore semântica
 Estrutura de dados – árvore
 árvore = conjunto de nós (vértices) ligados por arestas.
 Exemplo
 Nós: números
 raiz: 1
 folhas: ?
1
7
2
6
3
4 5
Árvore semântica
 Exemplo: Lei da contraposição
 H = (P→Q) ↔ ((¬Q) → (¬P)) (tautologia)
 Quais as possíveis interpretações para P ?
 O Nó 2 corresponde à fórmula
Nó 2 = (P→Q) ↔ ((¬Q) → (¬P))
 T T
Nó 2 = (P→Q) ↔ ((¬Q) → (¬P))
 T FT
Nó 3 = (P→Q) ↔ ((¬Q) → (¬P))
 F T T T TF
1
2 3
I[P]=T I[P]=F
1
2 3
I[P]=T I[P]=F
T
P Q P → Q
T T T
T F F
F T T
F F T
Árvore semântica
 Exemplo: Lei da contraposição
Nó 4 = (P→Q) ↔ ((¬Q) → (¬P))
 T T T T FT T FT
Nó 5 = (P→Q) ↔ ((¬Q) → (¬P))
 T F F T TF F FT
 Conclusão:
 Para o caso em que todas as folhas da árvore são rotuladas 
com F, tem-se fórmula contraditória
 Se pelo menos uma folha estiver rotulada com T, então fórmula 
satisfazível
 Neste caso, temos uma tautologia
1
2 3
I[P]=T I[P]=F
4 5
I[Q]=T I[Q]=F
T T
T
Método da negação ou absurdo
 Método geral de demonstração empregado aqui para 
demonstrar a validade de fórmulas
 Ponto de partida: negação daquilo que se quer demonstrar
 Se o objetivo é demonstrar que a fórmula H é uma tautologia, 
então supõe-se que H não é uma tautologia
 Resultado = absurdo, logo a suposição inicial é falsa
Exemplo – Lei da transitividade
 Lei da transitividade: ((P → Q)∧(Q → R)) →(P → R)
 Por absurdo:
((P → Q) ∧(Q → R)) →(P → R)
 F
I[(P → Q) ∧(Q → R) ]=T e I[(P → R)]=F
((P → Q) ∧ (Q → R)) →(P → R)
 T F F
((P → Q) ∧ (Q → R)) →(P → R)
 T T T F T F F
Neste ponto I[P] = T e I[R] = F
Assim
 ((P → Q) ∧(Q → R)) →(P → R)
 T T T T F F T F F
 
P Q P → Q
T T T
T F F
F T T
F F T
Exemplo – Lei da transitividade
 Lei da transitividade: ((P → Q)∧(Q → R)) →(P → R)
Assim
 ((P → Q) ∧(Q → R)) →(P → R)
 T T T T F F T F F
 Para concluir qual a interpretação de Q veja as subfórmulas 
(P → Q) e (Q → R)
 I[Q]=F? ou I[Q]=T?
((P → Q) ∧(Q → R)) →(P → R)
 T T T T F T F F T F F
P Q P → Q
T T T
T F F
F T T
F F T
Aplicação do método da negação
 Demonstração da contradição
 Para provar que H é contraditória 
 Supõe-se que H é satisfazível
 Existe I[H]=T
 Fórmulas com o conectivo →
 Só existe uma possibilidade de absurdo 
 I[Antecedente]=T e I[Consequente]=F 
 Fórmulas com o conectivo ∧, ∨
 Supondo a veracidade de A ∧ B: I[A]=T e I[B]=T
 Supondo a falsidade de A ∨ B: I[A]=F e I[B]=F
Ausência de absurdo
 Se uma asserção é negada, mas o absurdo não aparece, nada se 
pode concluir sobre a veracidade da asserção
 Exemplo: (P→Q) ↔((¬P)→(¬Q)) 
 Por absurdo: F
 Possibilidade 1: T F F
 Possibilidade 2: F F T
Ausência de absurdo
 Exemplo: H= (P→Q) ↔((¬P)→(¬Q)) 
 Possibilidade 1: T F F
 F T T F TF F FT OK!
 Possibilidade 2: F F T
 T F F F FT T TF OK!
 Não se pode concluir que H é tautologia
 Se I[P]=F e I[Q]=T, então I[H]=F
P Q P → Q
T T T
T F F
F T T
F F T
Exercícios
Árvore semântica 
¬(¬H) ↔ H
(P→Q) ↔((¬P)→(¬Q))
Negação
¬(¬H) ↔ H
(P→Q) ↔((¬Q)→(¬P))
H=(P∧Q) ↔((¬P∨Q)) 
é tautologia?
 Lei da negação
 (¬(¬H)) ↔ (H)
 Leis de De Morgan
 (¬(P∨Q)) ↔ (¬P ∧ ¬Q) 
 (¬(P∧Q)) ↔ (¬P ∨ ¬Q)
 Leis de eliminação 
 (P→Q) ↔ (¬P ∨ Q)
 (P ↔ Q) ↔ ((P → Q) ∧(Q → P))
 Leis distributivas
 (F ∨ (G ∧ H)) ↔ ((F ∨ G) ∧(F ∨ H))
 (F ∧ (G ∨ H)) ↔ ((F ∧ G) ∨ (F ∧ H))
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15