GEX103_logica_aula_4

Prévia do material em texto

1 
 
GEX103 - INTRODUÇÃO À LÓGICA 
Turma: 15B 14B 24A 
Aula 4 – 23 e 28/01/2013 
 
Capítulo 6: Equivalência lógica 
 
1 Introdução: 
 
As proposições P(p,q) = p ˄ q e Q(p,q) = q ˄ p possuem os mesmos valores-verdade, isto é, possuem tabelas-
verdade idênticas. 
 
p q p ˄ q q ˄ p 
V V V V 
V F F F 
F V F F 
F F F F 
 ⏞ 
Por essa razão, P(p,q) = p ˄ q e Q(p,q) = q ˄ p são logicamente equivalentes. 
P(p,q) <=> Q(p,q) 
 
Definição: duas proposições P e Q são logicamente equivalentes se, e somente se os valores-verdade 
obtidos forem idênticos para cada combinação possível das variáveis que formam as proposições. 
 
Em outras palavras, uma proposição P(p,q, r,...) é logicamente equivalente a uma proposição Q(p,q,r,...), se as 
tabelas-verdade destas duas proposições forem idênticas. 
 
Notação: 
P(p,q, r,...) <=> Q(p,q,r,...) 
ou 
P(p,q, r,...) Q(p,q,r,...) 
 
Esta notação indica que a proposição P(p,q, r,...) é equivalente à Q(p,q,r,...). 
 
Em particular, se as proposições P(p,q, r,...) e Q(p,q,r,...) são ambas tautologias ou são ambas contradições, 
então P(p,q, r,...) <=> Q(p,q,r,...) são equivalentes. 
 
Exemplo 1: 
As seguintes sentenças são logicamente equivalentes: 
Se hoje é sábado, então hoje é fim de semana. (1) q → q 
Se hoje não é fim de semana, então hoje não é sábado. (2) ~q → ~p 
 
Em símbolos: 
p : "Hoje é sábado." 
q: "Hoje é fim de semana." 
(p→q) <=> (~q→~p) 
 
Sintaticamente, (1) e (2) são equivalentes pela Lei da Contraposição "se A implica B então não-B implica 
não-A", e vice-versa: 
(A→B) <=> (B→~A) 
 
Semânticamente, (1) e (2) têm os mesmos valores nas mesmas interpretações. 
 
2 
 
 
Como verificar se duas proposições P e Q são logicamente equivalentes? 
 
1. Construa a tabela-verdade para P. 
2. Construa a tabela-verdade para Q usando os mesmos valores de variáveis para as afirmações que 
formam a proposição. 
3. Verifique se as tabelas-verdade de P e Q são idênticas para cada combinação de valores-verdade. 
 Se forem, P e Q são logicamente equivalentes, caso contrário não. 
 
2: Propriedades da equivalência lógica: 
 
A relação de equivalência lógica possui as propriedades: reflexiva(R), simétrica (S) e transitiva (T). 
Simbolicamente: 
(R) P(p,q, r,...) <=> P(p,q,r,...) 
 
(S) Se P(p,q, r,...) <=> Q(p,q,r,...), então Q(p,q, r,...) <=> P(p,q,r,...) 
 
(T) Se P(p,q, r,...) <=> Q(p,q,r,...), e Q(p,q, r,...) <=> R(p,q,r,...) então P(p,q, r,...) <=> R(p,q,r,...) 
 
 
3 Exemplificação: 
(1) Regra da dupla negação: 
As proposições “~~p” e “p” são equivalentes, isto é, ~~p <=> p. 
Portanto a dupla negação equivale à afirmação, como pode ser visto na tabela-verdade. 
p ~p ~~p 
V F V 
F V F 
 
 ~~p <=> p 
(2) Regra de CLAVIUS: 
As proposições “~p→p” e “p” são equivalentes, isto é, ~p→p <=> p. 
 
p ~p ~p→p 
V F V 
F V F 
 
 ~p→p <=> p 
(3) Regra da absorção: 
As proposições “p → p ˄ q” e “p → q” têm tabelas verdade idênticas, portanto são equivalentes, 
isto é, 
p → p ˄ q <=> p → q 
 
P q p ˄ q p → p ˄ q p → q 
V V V V V 
V F F F F 
F V F V V 
F F F V V 
 
 p → p ˄ q <=> p → q 
3 
 
(4) A condicional “p → q” e a disjunção “~p ˅ q” têm tabelas-verdade idênticas, portanto são 
equivalentes. 
 
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 
 
 p → q <=> ~p ˅ q 
Estas duas proposições subsiste a importante equivalência lógica: 
p → q <=> ~p ˅ q 
 
(5) A bicondicional “p ↔ q” e a conjunção “(p → q) ˄ (q → p)” têm tabelas-verdade idênticas, 
portanto são equivalentes. 
 
p q p ↔ q p → q q → p (p → q) ˄ (q → p) 
V V V V V V 
V F F F V F 
F V F V F F 
F F V V V V 
 
 p ↔ q <=> (p → q) ˄ (q → p) 
Estas duas proposições subsiste a importante equivalência lógica: 
p ↔ q <=> (p → q) ˄ (q → p) 
 
(6) A bicondicional “p ↔ q” e a disjunção “(p ˄ q) ˅ (~p ˄ ~q)” têm tabelas-verdade idênticas, 
portanto são equivalentes. 
 
p q p ↔ q (p ˄ q) ˅ (~p ˄ ~q) 
V V V V V V V F F F 
V F F V F F F F F V 
F V F F F V F V F F 
F F V F F F V V V V 
 
 p ↔ q <=> (p ˄ q) ˅ (~p ˄ ~q) 
Estas duas proposições subsiste a importante equivalência lógica: 
p ↔ q <=> (p ˄ q) ˅ (~p ˄ ~q). 
 
4 
 
4 Tautologias e equivalência lógica 
Teorema: 
A proposição P(p, q, r, ...) é equivalente à proposição Q(p, q, r, ...), se, e somente se a bicondicional: 
 P(p,q, r,...) ↔ Q(p,q,r,...) (1) 
é tautológica. 
 
isto é: 
 P(p,q, r,...) <=> Q(p,q,r,...) se, e somente se P(p,q, r,...) ↔ Q(p,q,r,...) é tautológica. 
Dem.: 
(i) Se as proposições P(p, q, r, ...) e Q(p, q, r, ...) são equivalentes então, P(p, q, r, ...) e Q(p, q, r, ...) têm 
tabelas-verdade idênticas. Por conseguinte, o valor lógico da bicondicional (1) é sempre 
verdade (V), isto é P(p,q, r,...) ↔ Q(p,q,r,...) é tautológica. 
 
(ii) Reciprocamente, se a bicondicional (1) é tautológica, então, a última coluna da sua tabela-
verdade encerra somente com a letra V (verdade) e, por conseguinte os valores lógicos 
respectivos das proposições P(p, q, r, ...) e Q(p, q, r, ...) são ambos V (verdade) ou ambos F 
(falsidade), isto é, estas duas proposições são equivalentes. 
 
Podemos concluir que toda equivalência lógica corresponde a uma bicondicional tautológica, e vice-
versa. 
 
Observação: Os símbolos ↔ e <=> são distintos. 
↔ é o símbolo de operação lógica bicondicional. 
 <=> é o símbolo que estabelece a relação de equivalência. 
 
Exemplo 2: 
Método de demonstração por absurdo: 
Seja c uma proposição cujo valor lógico é Falsidade (F). 
A bicondicional “(p ˄ ~q → c) ↔ (p → q)” é tautológica. 
Portanto as proposições “p ˄ ~q → c” e “p → q” são equivalentes, isto é: 
 
p ˄ ~q → c <=> p → q 
 
p q c (p ˄ ~q → c) ↔ (p → q) 
V V F V F F V F V V V V 
V F F V V V F F V V F F 
F V F F F F V F V F V V 
F F F F F V V F V F V F 
 1 3 2 4 1 7 5 6 5 
 
 p ˄ ~q → c <=> p → q 
 
Nesta equivalência consiste o método de demonstração por absurdo, que consiste de um método de prova 
matemática indireta, não-construtiva. Este tipo de prova é feito assumindo-se como verdade o contrário 
do que queremos provar e então, chegando-se a uma contradição. 
 
Exemplo 2: 
Regra de exportação-importação: 
A bicondicional “( p ˄ q → r ) ↔ ( p → ( q → r ))” é tautológica. 
 
 
5 
 
 
p q r (p ˄ q → r) ↔ (p → (q → r) 
V V V V V V V V V V V V V V 
V V F V V V F F F V F V F F 
V F V V F F V V V V V F V V 
V F F V F F V F V V V F V F 
F V V F F V V V V F V V V V 
F V F F F V V F V F V V F F 
F F V F F F V V V F V F V V 
F F F F F F V F V F V F V F 
 1 2 1 3 1 7 1 3 1 2 1 
 
 p ˄ q → r <=> ( p → ( q → r )) 
 
Portanto as proposições “( p ˄ q → r )” e “( p → ( q → r ))” são equivalentes, isto é: 
p ˄ q → r <=> p → ( q → r ) 
 
Exemplo 3: 
As proposições “ ” e “~” não são equivalentes, pois a bicondicional: 
 ) ↔ ~ 
não é tautológica. 
 
 ( ↔ ~ ( ) 
V V V V F F F V V V 
V F V V V V V F F V 
F V F F F F V V F F 
F F F V V V V F F F 
 1 2 1 4 3 1 2 1 
 
 
 ) ↔ ~