Unidade I Aulas 04.pdf

Prévia do material em texto

Lógica para Computação 
Unidade I – Aulas 04 
Profª MSc. Patricia Medyna Lauritzen de Lucena Drumond 
patriciamedyna@ufpi.edu.br 
Universidade Federal do Piauí 
Centro de Ensino Aberto e a Distância 
Curso de Sistemas de Informação 
Aula 04 
 
Propriedades semânticas da 
Lógica Proposicional 
Propriedades semânticas básicas 
• Tautologia ou validade 
 
• Satisfatibilidade, factibilidade ou contingente 
 
• Contradição 
Propriedades semânticas básicas 
• Uma fórmula H é uma tautologia (ou é válida) se e 
somente se para toda interpretação I, I[H]=V 
– Exemplo: H = (P  Q) ((P  Q)) 
P Q P Q (PQ) H 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
V 
F 
V 
F 
F 
V 
V 
V 
V 
Propriedades semânticas básicas 
• H é factível ou satisfazível se e somente se existe uma 
interpretação I tal que I[H]=V, também chamada 
contingente. 
– Exemplo: H= (Q  (P  Q)) P 
P Q P Q Q  (PQ) H 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
V 
V 
F 
V 
F 
V 
V 
F 
V 
Propriedades semânticas básicas 
• H é contraditória se e somente se para toda 
interpretação I, I[H]=F. 
– Exemplo: H= (P  Q)  ((P)  (Q)) 
P Q P Q P Q (P)  (Q) H 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
V 
V 
F 
F 
F 
F 
Exemplo de Tautologia 
• A fórmula H=PvP é uma tautologia, pois toda 
I[H]=V 
P P H=P vP 
V 
F 
F 
V 
V 
V 
Exemplo de Satisfatibilidade 
• A fórmula H=(PvQ) é satisfazível 
P Q P  Q 
V 
V 
F 
F 
V 
F 
V 
F 
V 
V 
V 
F 
Exemplo de Contradição 
• A fórmula H=(P^P) é contraditória 
P P H=PP 
V 
F 
F 
V 
F 
F 
Equivalência 
• Duas fórmulas H e G são tautologicamente 
equivalentes se, para cada interpretação de H e de G, 
os valores de H e G forem iguais. 
• Simbolicamente temos: H  G 
Equivalência 
• Duas fórmulas H e G são tautologicamente 
equivalentes se, para cada interpretação de H e de G, 
os valores de H e G forem iguais. 
• Exemplo: H=(P Q) e G=(PQ) 
 
P Q P Q P Q (P)  (Q) (PQ) 
V 
V 
F 
F 
V 
F 
V 
F 
Equivalência 
• Duas fórmulas H e G são tautologicamente 
equivalentes se, para cada interpretação de H e de G, 
os valores de H e G forem iguais. 
• Exemplo: H=(P Q) e G=(PQ) 
 
P Q P Q P Q (P)  (Q) (PQ) 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
F 
F 
Equivalência 
• Duas fórmulas H e G são tautologicamente 
equivalentes se, para cada interpretação de H e de G, 
os valores de H e G forem iguais. 
• Exemplo: H=(P Q) e G=(PQ) 
 
P Q P Q P Q (P)  (Q) (PQ) 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
F 
V 
F 
V 
Equivalência 
• Duas fórmulas H e G são tautologicamente 
equivalentes se, para cada interpretação de H e de G, 
os valores de H e G forem iguais. 
• Exemplo: H=(P Q) e G=(PQ) 
 
P Q P Q P Q (P)  (Q) (PQ) 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
V 
V 
Equivalência 
• Duas fórmulas H e G são tautologicamente 
equivalentes se, para cada interpretação de H e de G, 
os valores de H e G forem iguais. 
• Exemplo: H=(P Q) e G=(PQ) 
 
P Q P Q P Q (P)  (Q) (PQ) 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
V 
V 
F 
V 
V 
V 
Equivalência 
• Exemplo: (P Q)R  R (P  Q) 
• H = (P Q)R e G = R (P  Q) 
 
 
P Q R P Q R PQ P  Q H G 
V 
V 
V 
V 
F 
F 
F 
F 
V 
V 
F 
F 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
F 
Equivalência 
• Exemplo: (P Q)R  R (P  Q) 
• H = (P Q)R e G = R (P  Q) 
 
 
P Q R P Q R PQ P  Q H G 
V 
V 
V 
V 
F 
F 
F 
F 
V 
V 
F 
F 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
V 
V 
F 
F 
V 
V 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
F 
V 
Equivalência 
• Exemplo: (P Q)R  R (P  Q) 
• H = (P Q)R e G = R (P  Q) 
 
 
P Q R P Q R PQ P  Q H G 
V 
V 
V 
V 
F 
F 
F 
F 
V 
V 
F 
F 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
V 
V 
F 
F 
V 
V 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
F 
V 
V 
V 
V 
V 
V 
V 
F 
F 
Equivalência 
• Exemplo: (P Q)R  R (P  Q) 
• H = (P Q)R e G = R (P  Q) 
 
 
P Q R P Q R PQ P  Q H G 
V 
V 
V 
V 
F 
F 
F 
F 
V 
V 
F 
F 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
V 
V 
F 
F 
V 
V 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
F 
V 
V 
V 
V 
V 
V 
V 
F 
F 
F 
F 
F 
F 
F 
F 
V 
V 
Equivalência 
• Exemplo: (P Q)R  R (P  Q) 
• H = (P Q)R e G = R (P  Q) 
 
 
P Q R P Q R PQ P  Q H G 
V 
V 
V 
V 
F 
F 
F 
F 
V 
V 
F 
F 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
V 
V 
F 
F 
V 
V 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
F 
V 
V 
V 
V 
V 
V 
V 
F 
F 
F 
F 
F 
F 
F 
F 
V 
V 
V 
F 
V 
F 
V 
F 
V 
V 
Equivalência 
• Exemplo: (P Q)R  R (P  Q) 
• H = (P Q)R e G = R (P  Q) 
 
 
P Q R P Q R PQ P  Q H G 
V 
V 
V 
V 
F 
F 
F 
F 
V 
V 
F 
F 
V 
V 
F 
F 
V 
F 
V 
F 
V 
F 
V 
F 
F 
F 
F 
F 
V 
V 
V 
V 
F 
F 
V 
V 
F 
F 
V 
V 
F 
V 
F 
V 
F 
V 
F 
V 
V 
V 
V 
V 
V 
V 
F 
F 
F 
F 
F 
F 
F 
F 
V 
V 
V 
F 
V 
F 
V 
F 
V 
V 
V 
F 
V 
F 
V 
F 
V 
V 
Equivalência 
• Outras Equivalências 
– Dupla negação: P  P 
– Comutativa: P  Q  Q  P e P  Q  Q  P 
– Associativa: (P  Q)  R  P  (Q  R) e 
(P  Q)  R  P  (Q  R) 
– Distributiva: (P  Q)  R  (P  R)  (Q  R) 
– De Morgan: (P  Q)  (P  Q) e 
(P  Q)  (P  Q) 
– P  Q  P  Q