Aula 5 - Equivalência entre Sentenças

Prévia do material em texto

Prof. Ricardo Mesquita 
Equivalência entre Sentenças 
Equivalência Lógica 
Já vimos as definições: 
 Dizemos que A é logicamente equivalente a B, se e somente se, 
para qualquer interpretação I, temos que I[A] = I[B] 
 Outra abordagem: A é logicamente equivalente a B, se e 
somente se, A  B é uma tautologia. 
 Ou ainda, A é logicamente equivalente a B, se e somente se, 
A╞ B e B╞ A. 
 Usaremos o símbolo  para representar esta relação. 
 Obs: Chamamos esse tipo de representação de metalinguagem 
 
02/21 
Por Exemplo: Algumas Leis da Lógica 
 Leis de De Morgan: 
 (P  Q)  (P  Q) tautologia 
 (P  Q)  (P  Q) equivalência 
 
 (P  Q)  (P  Q) tautologia 
 (P  Q)  (P  Q) equivalência 
 
 Lei da Contraposição: 
 (P  Q)  (Q  P) tautologia 
 (P  Q)  (Q  P) equivalência 
 
 Lei da Transitividade: 
 ((P  Q)  (Q  R))  (P  R) tautologia 
 Observação: note que esta Lei não é uma relação de equivalência! 
 
 
03/21 
Equivalência Lógica 
 As equivalências lógicas introduzem formas diferentes de se 
representar a mesma informação, isto é, uma forma de se 
manter o valor lógico na representação das sentenças 
 Podemos utilizar as equivalências lógicas para efetuar vários 
tipos de manipulações ou alterações numa fórmula sem alterar 
seu significado. 
 Ou seja, mantém-se a interpretação. 
 Por exemplo, maneiras de se converter proposições 
conectadas pelo operador  em proposições conectadas por 
 são interessantes... 
 
04/21 
Algumas Equivalências Importantes 
 
 
 
 
 
 
 
 
 Exercício: Demonstre a validade dessas relações. 
Propriedade Disjunção Conjunção 
Comutativa (A  B)  (B  A) (A  B)  (B  A) 
Associativa ((A  B)  C)  (A  (B  C)) ((A  B)  C)  (A  (B  C)) 
Distributiva (A  (B  C))  
 ((A  B)  (A  C)) 
(A  (B  C))  
 ((A  B)  (A  C)) 
Elemento Neutro (A  false)  A (A  true)  A 
Complemento (A  A)  true (A  A)  false 
Idempotência (A  A)  A (A  A)  A 
05/21 
Demonstração 
 Comutatividade 
 
 
A B A  B B  A 
V V 
V F 
F V 
F F 
A B A  B B  A 
V V 
V F 
F V 
F F 
06/21 
A  B 
V 
V 
V 
F 
B  A 
V 
V 
V 
F 
A  B 
V 
F 
F 
F 
B  A 
V 
F 
F 
F 
Demonstração 
 Associatividade 
A B C A  B (A  B)  C B  C A  (B  C) 
V V V 
V V F 
V F V 
V F F 
F V V 
F V F 
F F V 
F F F 
07/21 
A  B 
V 
V 
V 
V 
V 
V 
F 
F 
(A  B)  C 
V 
V 
V 
V 
V 
V 
V 
F 
B  C 
V 
V 
V 
F 
V 
V 
V 
F 
A  (B  C) 
V 
V 
V 
V 
V 
V 
V 
F 
Demonstração 
 Associatividade 
A B C A  B (A  B)  C B  C A  (B  C) 
V V V 
V V F 
V F V 
V F F 
F V V 
F V F 
F F V 
F F F 
08/21 
A  B 
V 
V 
F 
F 
F 
F 
F 
F 
(A  B)  C 
V 
F 
F 
F 
F 
F 
F 
F 
B  C 
V 
F 
F 
F 
V 
F 
F 
F 
A  (B  C) 
V 
F 
F 
F 
F 
F 
F 
F 
Demonstração 
 Distributividade 
A B C B  C A  (B  C) A  B A  C (A  B)  (A  C) 
V V V 
V V F 
V F V 
V F F 
F V V 
F V F 
F F V 
F F F 
09/21 
B  C 
V 
F 
F 
F 
V 
F 
F 
F 
A  (B  C) 
V 
V 
V 
V 
V 
F 
F 
F 
A  B 
V 
V 
V 
V 
V 
V 
F 
F 
A  C 
V 
V 
V 
V 
V 
F 
V 
F 
(A  B)  (A  C) 
V 
V 
V 
V 
V 
F 
F 
F 
Demonstração 
 Distributividade 
A B C B  C A  (B  C) A  B A  C (A  B)  (A  C) 
V V V 
V V F 
V F V 
V F F 
F V V 
F V F 
F F V 
F F F 
10/21 
B  C 
V 
V 
V 
F 
V 
V 
V 
F 
A  (B  C) 
V 
V 
V 
F 
F 
F 
F 
F 
A  B 
V 
V 
F 
F 
F 
F 
F 
F 
A  C 
V 
F 
V 
F 
F 
F 
F 
F 
(A  B)  (A  C) 
V 
V 
V 
F 
F 
F 
F 
F 
Demonstração 
 Elemento Neutro 
A false A  false 
V 
F 
A true A  true 
V 
F 
11/21 
false 
F 
F 
A  false 
V 
F 
true 
V 
V 
A  true 
V 
F 
Demonstração 
 Complemento 
A A A  A true 
V 
F 
A A A  A false 
V 
F 
12/21 
A 
F 
V 
A  A 
V 
V 
true 
V 
V 
A 
F 
V 
A  A 
F 
F 
false 
F 
F 
Demonstração 
 Idempotência 
A A A  A 
V V V 
F F F 
A A A  A 
V V V 
F F F 
13/21 
Equivalências Lógicas 
 Outras... 
 
 
 
 
 
 
 
 
 Exercício: Demonstre a validade dessas relações. 
 
Propriedades 
Dupla Negação (A)  A 
Equivalência da Implicação (A  B)  (A  B) 
Contraposição (ou contrapositiva) (A  B)  (B  A) 
Prova Condicional (A  (B  C))  ((A  B)  C) 
Equivalência da Bi-implicação (A  B)  ((A  B)  (B  A)) 
Equivalência da Bi-implicação (A  B)  ((A  B)  (A  B)) 
14/21 
Demonstração 
 Dupla negação 
A A (A) 
V 
F 
15/21 
A 
F 
V 
(A) 
V 
F 
Demonstração 
 Equivalência da Implicação 
A B A  B A A  B 
V V 
V F 
F V 
F F 
16/21 
A  B 
V 
F 
V 
V 
A 
F 
F 
V 
V 
A  B 
V 
F 
V 
V 
Demonstração 
 Contrapositiva 
A B A  B A B B  A 
V V 
V F 
F V 
F F 
17/21 
A  B 
V 
F 
V 
V 
A 
F 
F 
V 
V 
B 
F 
V 
F 
V 
B  A 
V 
F 
V 
V 
Demonstração 
 Prova Condicional 
A B C B  C A  (B  C) A  B (A  B)  C 
V V V 
V V F 
V F V 
V F F 
F V V 
F V F 
F F V 
F F F 
18/21 
B  C 
V 
F 
V 
V 
V 
F 
V 
V 
A  (B  C) 
V 
F 
V 
V 
V 
V 
V 
V 
A  B 
V 
V 
F 
F 
F 
F 
F 
F 
(A  B)  C 
V 
F 
V 
V 
V 
V 
V 
V 
Demonstração 
 Equivalência da Bi-implicação 
A B A  B A  B B  A (A  B)  (B  A) 
V V 
V F 
F V 
F F 
19/21 
A  B 
V 
F 
F 
V 
A  B 
V 
F 
V 
V 
B  A 
V 
V 
F 
V 
(A  B)  (B  A) 
V 
F 
F 
V 
Demonstração 
 Equivalência da Bi-implicação 
 
A B A  B A  B A  B (A  B)  (B  A) 
V V 
V F 
F V 
F F 
20/21 
A  B 
V 
F 
F 
V 
A  B 
V 
V 
V 
F 
A  B 
V 
F 
F 
F 
(A  B)  (B  A) 
V 
F 
F 
V 
Exercícios 
Considere as fórmulas H e G a seguir: 
 
H = (P  Q)  (R  S) 
G = ((P  Q)  (Q  P))  (R  S) 
 
1. Mostre que H  G (use tabela-verdade). 
2. Utilizando as propriedades estudadas na aula de hoje, 
encontre formas equivalentes para as fórmulas H e G 
acima. 
21/21