Equivalência Lógica

Universidade Federal do Espírito Santo – CCA UFES
Universidade Federal do Espírito Santo
Centro de Ciências Agrárias – CCA UFES
Departamento de Computação
Equivalência Lógica
Lógica Computacional 1
Site: http://jeiks.net
E-mail: [email protected]
Universidade Federal do Espírito Santo – CCA UFES
Equivalência Lógica
●
Definição
–
●
Uma proposição P(p,q,r,...) é equivalente a uma proposição
Q(p,q,r,...) se as tabelas verdade dessas duas proposições são
idênticas.
Notação:
P(p,q,r,...) ⇔ Q(p,q,r,...)
●
Exemplo:
.
p
q
p→q
~p ∨ q
V
V
V
V
V
F
F
F
F
V
V
V
F
F
V
V
Obtém-se:
p → q ⇔ ~p ∨ q
2
Universidade Federal do Espírito Santo – CCA UFES
Propriedades
●
A relação da Equivalência Lógica possui as propriedades:
–
Reflexiva:
P(p,q,r,...) ⇔ P(p,q,r,...)
P⇔P
–
Simétrica:
Se P(p,q,r,...) ⇔ Q(p,q,r,...), então Q(p,q,r,...) ⇔ P(p,q,r,...)
Se P ⇔ Q, então Q ⇔ P
–
Transitiva:
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,...)
Se P ⇔ Q e Q ⇔ R, então P ⇔ R
3
Universidade Federal do Espírito Santo – CCA UFES
Exercícios
●
Prove que as seguintes proposições são
equivalentes:
1. p e ¬ ¬ p;
2. p e ¬p → p;
3. p → p ∧ q e p → q; (Regra de absorção)
4. p → q e ¬p ∨ q;
5. p ↔ q e (p → q) ∧ (q → p);
6. p ↔ q e (p ∧ q) ∨ (¬p ∧ ¬q).
4
Universidade Federal do Espírito Santo – CCA UFES
Tautologias e Equivalência Lógica
P(p,q,r,...) ⇔ Q(p,q,r,...)
se e somente se
P(p,q,r,...) ↔ Q(p,q,r,...)
é tautológica.
●
Demonstre isso para o item 4 do exercício anterior:
4. p → q e ¬p ∨ q;
Dica: faça mais uma coluna com a seguinte sentença:
p → q ↔ ¬p ∨ q
5
Universidade Federal do Espírito Santo – CCA UFES
Tautologias e Equivalência Lógica
●
Tem-se o Corolário (afirmação deduzida de uma
verdade já demonstrada):
Se P(p,q,r,...) ⇔ Q(p,q,r,...),
então também é válido que
Q(p,q,r,...) ⇔ P(p,q,r,...)
●
Observe que:
↔ indica uma operação lógica entre as proposições.
●
Ex.: das proposições p e q, dá-se a nova proposição p ↔ q.
⇔ indica uma relação.
●
Ex.: estabelece que a bicondicional P ↔ Q é tautológica.
6
Universidade Federal do Espírito Santo – CCA UFES
Exercícios
●
Indique quais das seguintes proposições são
equivalentes:
1. (p ∧ ~q → c) ↔ (p → q), onde V(c) = F
(Método de demonstração do absurdo)
2. ( p ∧ q → r ) ↔ ( p → (q → r) )
(Regra de Exportação-Importação)
3. p ∨ ~q e ~(q ∧ p)
7
Universidade Federal do Espírito Santo – CCA UFES
Proposições associadas a uma
condicional
●
Dada a condicional p → q, chamam-se proposições
associadas a p → q (direta) as três seguintes
proposições:
–
Proposição recíproca de p → q: q → p
–
Proposição contrária de p → q: ~p → ~q
–
Proposição contrapositiva de p → q: ~q → ~p
p
q
p→q
q→p
~p → ~q
~q → ~p
V
V
V
V
V
V
V
F
F
V
V
F
F
V
V
F
F
V
F
F
V
V
V
V
São
São equivalentes:
equivalentes:
pp →
→ qq ⇔
⇔ ~q
~q →
→ ~p
~p
pp →
→ qq ⇔
⇔ ~p
~p →
→ ~q
~q
.
8
Universidade Federal do Espírito Santo – CCA UFES
Exercícios
●
A recíproca da seguinte sentença é Verdadeira ou Falsa
(obs.: T é um triângulo)?
p → q: Se T é equilátero, então T é isósceles.
●
Expresse a contrapositiva da seguinte sentença:
p → q: Se Carlos é professor, então é pobre.
●
Qual a contrapositiva da condicional: “Se x é menor que
zero, então x não é positivo”.
p: x é menor que zero.
q: x é positivo.
●
Determine a contrapositiva da contrapositiva de p → q.
.
9
Universidade Federal do Espírito Santo – CCA UFES
Negação conjunta de duas
proposições
●
Definição
–
Chama-se negação conjunta de duas proposições p e q a
proposição “não p e não q”: ¬ p ∧ ¬ q.
●
Outra notação: p ↓ q
●
Então: p ↓ q ⇔ ¬ p ∧ ¬ q
●
A proposição p ↓ q somente é verdadeira no caso em
que p e q são falsas:
.
p
q
p↓q
V
V
F
V
F
F
F
V
F
F
F
V
10
Universidade Federal do Espírito Santo – CCA UFES
Negação disjunta de duas
proposições
●
Definição
–
Chama-se negação disjunta de duas proposições p e q a
proposição “não p ou não q”: ¬ p ∨ ¬ q.
●
Outra notação: p ↑ q
●
Então: p ↑ q ⇔ ¬ p ∨ ¬ q
●
A proposição p ↓ q somente é falsa no caso em que p
e q são verdadeiras:
.
p
q
p↓q
V
V
F
V
F
V
F
V
V
F
F
V
Os
Os símbolos
símbolos ↓↓ ee ↑↑ são
são
chamados
chamados de:
de:
“conectivos
“conectivos de
de SCHEFFER”
SCHEFFER”
11