Slide - Aula 04

Prévia do material em texto

SIF510-Fundamentos de 
Lógica e Matemática Discreta
Professora: Hévilla Nobre Cezar
Equivalência Lógica 
 Diz-se que uma proposição P é logicamente 
equivalente a uma proposição Q se as 
tabelas-verdade destas duas proposições 
são idênticas.
 Ou seja, P ↔ Q é uma tautologia.
Equivalencia Lógica
 Exemplo p→p˄q p→q
 Como p˄q → p˅q é uma tautologia então
p˄q p˅q é uma implicação.

p q p˄q p→p˄q p→q p→p˄q ↔ 
p→q
V
V
F
F
V
F
V
F
V
F
F
F
V
F
V
V
V
F
V
V
V
V
V
V

Equivalência Lógica
 Propriedades:
 Reflexiva (R) P P 
 Transitiva (T) Se P Q e Q R
então P R
 Simétrica (S) Se P Q
então Q P
Obs: os símbolos e ↔ são distintos, o primeiro é de 
relação e o segundo é de operação.

 




Equivalência Lógica
 Um importante recurso usado na 
argumentação lógica é a substituição de uma 
proposição por outra que seja equivalente:
 ¬(¬p) = p
 a˄a = a 
 a˅a=a
 (a˄¬a)˅b = b
 a ˅ ¬a = b ˅ ¬b
Principais Regras de Equivalência 
Equivalência Nome da regra
p ∨ p ⇔ p
p ∧ p ⇔ p
Idempotência
￢(￢p) ⇔ p Dupla Negação
p ∨ q ⇔ q ∨ p
p ∧ q ⇔ q ∧ p
Comutatividade
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
Associatividade
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) 
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
Distributividade
￢(p ∧ q) ⇔￢p ∨￢q 
￢(p ∨ q) ⇔￢p ∧￢q
Leis de Morgan
Equivalência Lógica 
 Exemplo 1
 p˅q: O rio é raso ou poluído
 ¬(p˅q): ?
 Pelas leis de De Morgan ¬(p˅q) ¬p ˄ ¬q
 ¬(p˅q):O rio não é raso e nem poluído.

Equivalência Lógica 
 Exemplo 2: Negação da condicional 
 p→q : Se o rio é raso então é poluído.
 ¬(p→q): ?
 ¬(p →q) p ˄ ¬q
 ¬(p→q): O rio é raso e não é poluído.

Equivalência Lógica 
 Exemplo 3
 Mostre que:
 (¬p˄(¬q˄r)) ˅(q˄r)˅(p˄r)=r
Exercícios em sala de aula