Validade mediante regras de inferência e equivalências.

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

Validade Mediante Regras de
Inferência e Equivalências

Lógica Combinacional 1
Site: http://jeiks.net
E-mail: [e-mail]

Universidade Federal do Espírito Santo – CCA UFES

Regra de Substituição
●

Problematização:
–

●

Há muitos argumentos que não podem ser demonstrados, verificados ou testados com o uso exclusivo das Regras de Inferência.

Solução:
–

Assim, torna-se necessário recorrer a um princípio da inferência adicional, a “Regra da Substituição” de proposições equivalentes:
Uma proposição qualquer P ou apenas uma parte de P pode ser substituída por uma proposição equivalente.
A proposição Q que assim se obtém é equivalente a P.
2

Universidade Federal do Espírito Santo – CCA UFES

Equivalências Notáveis
CONDICIONAL:
P → Q ⇔ ~P ∨ Q

COMUTATIVA:
P∧Q⇔Q∧P
P∨Q⇔Q∨P

DUPLA NEGAÇÃO:
~~P ⇔ P

ASSOCIATIVA:
P ∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R
P ∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R

REGRA DE CLAVIUS: REGRA DE ABSORÇÃO:
~P → P ⇔ P
P→P∧Q⇔P→Q

IDENTIDADE:
P∧T⇔P P∧C⇔C
P∨T⇔T P∨C⇔P

ABSORÇÃO:
P ∧ (P ∨ Q) ⇔ P
P ∨ (P ∧ Q) ⇔ P

DEMONSTRAÇÃO POR
ABSURDO:
P ∧ ~Q → C ⇔ P → Q

DISTRIBUTIVA:
P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)

CONTRAPOSITIVA:
P → Q ⇔ ~Q → ~P

LEIS DE DE MORGAN:
~(P ∨ Q) ⇔ ~P ∧ ~Q
~(P ∧ Q) ⇔ ~P ∨ ~Q

REGRA DE
EXPORTAÇÃO-IMPORTAÇÃO:
P ∧ Q → R ⇔ P → (Q → R)

DISJUNÇÃO
EXCLUSIVA:
P ⊻ Q ⇔ ~(P ↔ Q)

IDEMPOTENTE:
P∧P⇔P
P∨P⇔P

BICONDICIONAL:
P↔Q ⇔ (P→Q) ∧ (Q→P)
P↔Q ⇔ (P ∧ Q) ∨ (~P ∧ ~Q)

3

Universidade Federal do Espírito Santo – CCA UFES

Exemplos
●

Demonstre que é válido o argumento: p → ~q, q ⊢ ~p

●

1. p → ~q

P

2. q

P

3. ~~q → ~p

1 – CP

4. q → ~p

3 – DN

5. ~p

2,4 – MP

Demonstre que é válido o argumento: p → q, r → ~q ⊢ p → ~r
1. p → q

hip

2. r →