Equivalencias Logicas

Prévia do material em texto

1
AULA 1
LÓGICA MATEMÁTICA
EQUIVALÊNCIA LÓGICA
Prof.: Rafael Dias Ribeiro
Autora:
Prof. Dra. Denise Candal
AULA 1
Equivalência Lógica
• Uma proposição P(p,q,r,....) é logicamente equivalente ou 
simplesmente equivalente a uma proposição Q(p,q,r,.....) se as 
tabelas-verdade de ambas as proposições são rigorosamente 
iguais. 
• Utilizaremos para indicar tal fato a notação P(p,q,r,....) ⇔
Q(p,q,r,.....) .
2
AULA 1
Observação
• Se as duas proposições forem ambas tautológicas ou ambas 
contradições , então são equivalentes.
AULA 1
Equivalências Lógicas
Comutativa
Comutativa
Associativa
Associativa
Idempotente
Idempotente
Absorção
Absorção
pqqp ∧⇔∧
pqqp ∨⇔∨
)()( rqprqp ∧∧⇔∧∧
ppp ⇔∧
ppp ⇔∨
)()( rqprqp ∨∨⇔∨∨
pqpp ⇔∨∧ )(
pqpp ⇔∧∨ )(
3
AULA 1
Equivalências Lógicas
Absorção
Absorção
Lei de Morgan
Lei de Morgan
Def Implicação
Def Implicação
Def Bicondicional
Def Bicondicional
pqpp ⇔∨∧ )(
pqpp ⇔∧∨ )(
qpqp ~~)(~ ∧⇔∨
qpqp ~~)(~ ∨⇔∧
qpqp ∨⇔→ ~
)()( pqqpqp →∧→⇔↔
)(~)(~ pqqpqp ∨∧∨⇔↔
)~(~ qpqp ∧⇔→
AULA 1
Leis de Morgan
p q p∨∨∨∨q ~(p∨∨∨∨q) ~p ~q ~p∧∧∧∧~q
V V
V F
F V
F F
qpqp ~~)(~ ∧⇔∨
4
AULA 1
Leis de Morgan
p q p∨∨∨∨q ~(p∨∨∨∨q) ~p ~q ~p∧∧∧∧~q
V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V
qpqp ~~)(~ ∧⇔∨
AULA 1
Leis de Morgan
p q p∧∧∧∧q ~(p∧∧∧∧q) ~p ~q ~p∨	∨	∨	∨	~q
V V
V F
F V
F F
qpqp ~~)(~ ∨⇔∧
5
AULA 1
Leis de Morgan
p q p∧∧∧∧q ~(p∧∧∧∧q) ~p ~q ~p∨	∨	∨	∨	~q
V V V F F F F
V F F V F V V
F V F V V F V
F F F V V V V
qpqp ~~)(~ ∨⇔∧
AULA 1
Definição de Implicação
p q p→q ~p ~p∨∨∨∨ q
V V
V F
F V
F F
qpqp ∨⇔→ ~
6
AULA 1
Definição de Implicação
p q p→q ~p ~p∨∨∨∨ q
V V V F V
V F F F F
F V V V V
F F V V V
qpqp ∨⇔→ ~
AULA 1
Definição de Implicação
p q p→q ~q p∧∧∧∧~q ~(p∧∧∧∧~q)
V V
V F
F V
F F
)~(~ qpqp ∧⇔→
7
AULA 1
Definição de Implicação
p q p→q ~q p∧∧∧∧~q ~(p∧∧∧∧~q)
V V V F F V
V F F V V F
F V V F F V
F F V V F V
)~(~ qpqp ∧⇔→
AULA 1
Definição de Bicondicional
p q p→q q→p (p→q)∧∧∧∧(q→p) p↔q
V V
V F
F V
F F
)()( pqqpqp →∧→⇔↔
8
AULA 1
Definição de Bicondicional
p q p→q q→p (p→q)∧∧∧∧(q→p) p↔q
V V V V V V
V F F V F F
F V V F F F
F F V V V V
)()( pqqpqp →∧→⇔↔
AULA 1
Definição de Bicondicional
p q ~p ~q ~p∨∨∨∨q ~q∨∨∨∨p (~p∨∨∨∨q)∧∧∧∧(~q∨∨∨∨p) p↔q
V V
V F
F V
F F
)(~)(~ pqqpqp ∨∧∨⇔↔
9
AULA 1
Definição de Bicondicional
p q ~p ~q ~p∨∨∨∨q ~q∨∨∨∨p (~p∨∨∨∨q)∧∧∧∧(~q∨∨∨∨p) p↔q
V V F F V V V V
V F F V F V F F
F V V F V F F F
F F V V V V V V
)(~)(~ pqqpqp ∨∧∨⇔↔
AULA 1
Equivalentes?
“Se está quente e úmido não choverá”.
“Se chover, então o céu não está quente ou não está úmido”.
10
AULA 1
Equivalentes?
“Se está quente e úmido não choverá”.
“Se chover, então o céu não está quente ou não está úmido”.
Quente: p Úmido: q Chove(rá): r
p∧q→~r
r→~p∨~q
AULA 1
p∧q→~r ⇔ r→~p∨~q ?
p q r p∧∧∧∧q ~r p∧∧∧∧q→~r ~p ~q ~p∨∨∨∨~q r→~p∨∨∨∨ ~r
V V V V F F F F F F
V V F V V V F F F V
V F V F F V F V V V
F V V F F V V F V V
V V F V V V F F F V
F V V F F V V F V V
V F V F F V F V V V
F F F F V V V V V V
11
AULA 1
Problema 1
A loja de Abul foi roubada, mas as jóias foram recuperadas. Havia três 
suspeitos: seus nomes eram Abdul, Ibn e Hassib. No julgamento, os 
acusados deram os seguintes depoimentos: 
Abdul: Não fui eu que cometi o roubo. 
Ibn; Não foi Hassib quem roubou a loja.
Hassib: Sim, o ladrão fui eu! -
Mais tarde, dois deles confessaram ter mentido. Quem era o ladrão ?
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p
~r
r
12
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p F V F
~r F F V
r V F F
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p F F
~r F V
r V F
13
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p F F
~r F V
r V F
p V
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p F F
~r F V
r V F
p V
Mentira!!!
14
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p F F
~r F V
r V F
p V
Mentira!!! Verdade!!!
AULA 1
Abdul cometeu o crime: p
Ibn cometeu o crime: q
Hassib cometeu o crime: r
Abdul: Não fui eu que cometi o roubo. ~p
Ibn: Não foi Hassib quem roubou a loja. ~r
Hassib: Sim, o ladrão fui eu! r
Dois deles confessaram ter mentido. 
~p F F
~r F V
r V F
p V
Mentira!!! Verdade!!!
Mentira!!!
15
AULA 1
Três pessoas prestam depoimento e o que dizem está 
registrado a seguir:
Bernardo: “João é culpado e Saul é inocente”.
João: ”Se Bernardo é culpado, Saul também é culpado”.
Saul: Eu sou inocente, mas, pelo menos, um dos outros é 
culpado.
A partir desses depoimentos identifique os inocentes e os 
culpados, supondo todos os depoimentos verdadeiros.
AULA 1
João é culpado: p
Saul é culpado: q
Bernardo é culpado: r
Bernardo: “João é culpado e Saul é inocente”. p ∧ ~q
João: ”Se Bernardo é culpado, Saul também é culpado”. r 
→ q
Saul: Eu sou inocente, mas, pelo menos, um dos outros é 
culpado. ~q ∧ p ou ~q∧r ou ~q ∧(p∧r)
Todos os depoimentos verdadeiros.
16
AULA 1
João é culpado: p
Saul é culpado: q
Bernardo é culpado: r
Bernardo: “João é culpado e Saul é inocente”. p ∧ ~q
João: ”Se Bernardo é culpado, Saul também é culpado”. r 
→ q
Saul: Eu sou inocente, mas, pelo menos, um dos outros é 
culpado. ~q ∧ p ou ~q∧r ou ~q ∧(p∧r)
Todos os depoimentos verdadeiros.
V V
AULA 1
João é culpado: p
Saul é culpado: q
Bernardo é culpado: r
Bernardo: “João é culpado e Saul é inocente”. p ∧ ~q
João: ”Se Bernardo é culpado, Saul também é culpado”. r 
→ q 
Saul: Eu sou inocente, mas, pelo menos, um dos outros é 
culpado. ~q ∧ p ou ~q∧r ou ~q ∧(p∧r)
Todos os depoimentos verdadeiros.
?→F V
V
V
F
V
F→F V
F