Cap4 (Métodos de Validade de Fórmulas)

Prévia do material em texto

Capítulo 4 
 
Métodos para determinação da 
validade de fórmulas da Lógica 
Proposicional 
Métodos para determinação de 
validade de fórmulas 
Tabela verdade 
 
Árvore semântica 
 
Método da negação ou absurdo 
Método da Tabela-Verdade 
O método da tabela verdade é o 
método da força bruta utilizado na 
determinação da validade de fórmulas. 
Dada uma fórmula H, suponha P1, P2, 
..., Pn, seus símbolos proposicionais, 
são consideradas todas as 
possibilidades de valores de verdade 
associados aos símbolos 
proposicionais. 
Método da Tabela-Verdade 
A primeira linha da tabela verdade é 
definida pelas subfórmulas. 
 
 
O número de linhas restantes é definido 
pela fórmula 2n onde n é o número de 
símbolos proposicionais. Essas linhas 
são preenchidas com todas as possíveis 
combinações de valores de verdade. 
P1 P2 ... Pn H 
Método da Tabela-Verdade 
Exemplo (leis de De Morgan) 
 H = (PQ)  ((P)  (Q)) 
P Q P Q P  Q (P  Q) (P  Q) 
T 
T 
F 
F 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
T 
T 
F 
F 
F 
F 
T 
T 
T 
F 
T 
T 
T 
Método da Tabela-Verdade 
O método da tabela verdade é mais 
adequado a fórmulas que contém um 
pequeno número de símbolos 
proposicionais. 
 
 P1((P2  P3) ((P4P5)((P6P7)P8))) 
A tabela associada a essa fórmula 
possui 256 linhas. 
Método da Árvore Semântica 
1 
2 3 
 
4 5 
 
6 7 8 
Nós - números 
Raiz – 1 
Folhas – 2,6,7,8 
Método da Árvore Semântica 
Nó 2: 
H=(PQ) ((Q)(P)) 
 T T 
 T FT 
 
Nó 3: 
H=(PQ) ((Q)(P)) 
 FT T T TF 
 
1 
2 3 
 
I[P]=T I[P]=F 
 
T 
Método da árvore semântica 
Nó 4: 
H=(PQ) ((Q)(P)) 
 T T T T FT T FT 
 
Nó 5: 
H=(PQ) ((Q)(P)) 
 TF F T TF T FT 
Satisfazível? 
Contraditória? 
 
 
I[Q]=T I[Q]=F T 
 
1 
2 3 
 
I[P]=T I[P]=F 
 
1 
 4 5 
 T T 
Método da negação ou absurdo 
Acabamos de provar a lei da contradição: 
(PQ) ((Q)(P)) e portanto 
P a Q  Q a P, ou seja: 
Há 2 formas de demonstrar PQ: 
Demonstrar P  Q normalmente 
Demonstrar (Q)  (P) 
Método da negação ou absurdo, que é um 
Método geral de demonstração 
Método da negação ou absurdo 
Para provar que H é uma tautologia 
Supõe-se inicialmente, por absurdo que 
 H NÃO é uma tautologia 
As deduções desta fórmula levam a um 
fato contraditório (ou absurdo) 
Portanto, a suposição inicial é falsa e: 
H é uma tautologia 
(A não-validade de H é um absurdo) 
Exemplo do método da negação ou 
absurdo 
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 T T F T F F 
 
Exemplo do método da negação ou 
absurdo 
((P  Q)^(Q  R)) (P  R) 
 T T T F T F F 
 T T T T F F T F F 
 T T T T F T F F T F F 
   
Portanto: 
((P  Q)^(Q  R)) (P  R) 
 F não pode existir! 
Então, sempre T!!! (tautologia!) 
 
 
 
Exercícios 
Por árvore semântica e por negação: 
(H)  H 
(PQ) ((P)(Q)) 
Aplicações do método da negação 
ou absurdo 
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[Conseqüente]=F 
Fórmulas com o conectivo ^ 
Também 1 só forma: I[A]=T e I[B]=T 
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 
 
Exemplo de Ausência de absurdo 
Exemplo: H= (PQ) ((P)(Q)) 
Possibilidade 1: T F F 
 F T T F TF F FT 
Possibilidade 2: F F T 
 T F F F FT F TF 
Não se pode concluir que H é 
tautologia 
Se I[P]=F e I[Q]=T, então I[H]=F 
 
Exercício do método de negação ou 
absurdo 
H=(P^Q) ((PvQ)) é tautologia? 
Só se H levar a absurdo em TODAS as 
possibilidades