Lógica/Cálculo Proposicional Clássico/Dedução Natural - Parte II

Regras de Inferência Derivadas

Por meio das regras de inferência diretas e hipotéticas podemos demonstrar vários raciocínios bastante recorrentes. Estes raciocíonios, uma vez demonstrados, podem ser usados como regras de inferência diretas. Elas não são necessárias, mas são bastante úteis, tornando nossas derivações muito mais sucintas. Anteriormente demonstramos dois raciocínios que nos serão úteis como regras de inferência derivadas:

• Dupla Negação em ambas direções (DN)

$\frac{\mathrm{\neg }\mathrm{\neg }\phi }{\bar{\phi }}$

• Silogismo Hipotético (SH)

$\alpha \to \beta$

$\underset{\_}{\beta \to \gamma }$

$\alpha \to \gamma$

Vamos ampliar nossa lista de regras de inferência derivadas, demonstrado uma por uma:

Repetição (R)

$\alpha ⊢\alpha$

1.   $\alpha$   Premissa 2.   $\mathrm{\neg }\mathrm{\neg }\alpha$   1 DN 3.   $\alpha$   2 DN

Modus Tollens (MT)

$\{\alpha \to \beta ,\mathrm{\neg }\beta \}⊢\mathrm{\neg }\alpha$

1.   $\alpha \to \beta$   Premissa 2.   $\mathrm{\neg }\beta$   Premissa   3.     $\alpha$   Hipótese 4.     $\beta$   1,3 MP 5.     $\beta \wedge \mathrm{\neg }\beta$   2,4 C 6.   $\mathrm{\neg }\alpha$         3,5 RAA

Prefixação (PRF)

$\alpha ⊢\beta \to \alpha$

1.   $\alpha$   Premissa   2.     $\beta$   Hipótese 3.     $\alpha$   1 R 4.   $\beta \to \alpha$   2,3 RPC

Contraposição (CT)

Aproveitaremos o Modus Tollens como regra de inferência.

$\alpha \to \beta ⊢\mathrm{\neg }\beta \to \mathrm{\neg }\alpha$

1.   $\alpha \to \beta$   Premissa   2.     $\mathrm{\neg }\beta$   Hipótese 3.     $\mathrm{\neg }\alpha$   1,2 MT 4.   $\mathrm{\neg }\beta \to \mathrm{\neg }\alpha$   2,3 RPC

Agora tente você provar a recíproca, ou seja, que $\mathrm{\neg }\beta \to \mathrm{\neg }\alpha ⊢\alpha \to \beta$

Confira aqui sua resposta.

Contradição (CTR)

$\{\alpha ,\mathrm{\neg }\alpha \}⊢\beta$

1.   $\alpha$   Premissa 2.   $\mathrm{\neg }\alpha$   Premissa 3.   $\alpha \vee \beta$   1 E 4.   $\beta$   2,3 SD

Lei de Duns Scot (DS)

$\mathrm{\neg }\alpha ⊢\alpha \to \beta$

1.   $\mathrm{\neg }\alpha$   Premissa   2.     $\alpha$   Hipótese 3.     $\beta$   1,2 CTR 4.   $\alpha \to \beta$   2,3 RPC

Prove que também vale $\alpha ⊢\mathrm{\neg }\alpha \to \beta$ .

Confira aqui sua resposta.

Lei De Morgan I (DM)

$\mathrm{\neg }(\alpha \vee \beta )⊢\mathrm{\neg }\alpha \wedge \mathrm{\neg }\beta$

01.   $\mathrm{\neg }(\alpha \vee \beta )$   Premissa   02.     $\alpha$   Hipótese 03.     $\alpha \vee \beta$   2 E 04.     $(\alpha \vee \beta )\wedge \mathrm{\neg }(\alpha \vee \beta )$   1,3 C 05.   $\mathrm{\neg }\alpha$                               2,4 RAA 06.     $\beta$   Hipótese 07.     $\alpha \vee \beta$   6 E 08.     $(\alpha \vee \beta )\wedge \mathrm{\neg }(\alpha \vee \beta )$   1,7 C 09.   $\mathrm{\neg }\beta$                       6,8 RAA 10.   $\mathrm{\neg }\alpha \wedge \mathrm{\neg }\beta$                 5,9 C

Agora tente você provar a recíproca, ou seja, que $\mathrm{\neg }\alpha \wedge \mathrm{\neg }\beta ⊢\mathrm{\neg }(\alpha \vee \beta )$

Confira aqui sua resposta

Lei De Morgan II (DM)

$\mathrm{\neg }(\alpha \wedge \beta )⊢\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta$

01.   $\mathrm{\neg }(\alpha \wedge \beta )$        Premissa   02.     $\mathrm{\neg }(\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )$       Hipótese     03.       $\mathrm{\neg }\alpha$   Hipótese   04.       $\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta$   3 E 05.       $(\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )\wedge \mathrm{\neg }(\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )$   5,2 C 06.     $\mathrm{\neg }\mathrm{\neg }\alpha$                                             3,5 RAA 07.     $\alpha$                                             6 DN 08.       $\mathrm{\neg }\beta$   Hipótese   09.       $\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta$   8 E 10.       $(\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )\wedge \mathrm{\neg }(\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )$   9,2 C 11.     $\mathrm{\neg }\mathrm{\neg }\beta$                     8,10 RAA 12.     $\beta$                     11 DN 13.     $\alpha \wedge \beta$                     7,12 C 14.     $(\alpha \wedge \beta )\wedge \mathrm{\neg }(\alpha \wedge \beta )$                     13,1 C 15.   $\mathrm{\neg }\mathrm{\neg }(\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )$                         2,14 RAA 16.   $\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta$                         15 DN

Tente você agora provar a recíprova, ou seja, que $\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta ⊢\mathrm{\neg }(\alpha \wedge \beta )$

Confira aqui sua resposta

Lista das Regras Derivadas

Ficheiro:Regras Derivadas2.png

Exercícios

Valendo-se das regras derivadas, prove que:

1. $\{(A\wedge B)\to C,\mathrm{\neg }C\}⊢\mathrm{\neg }A\vee \mathrm{\neg }B$
2. $\mathrm{\neg }(A\wedge \mathrm{\neg }B)⊢A\to B$
3. $\mathrm{\neg }A\to B⊢A\vee B$
4. $\{A\to C,B\to C\}⊢(A\vee B)\to C$
5. $\mathrm{\neg }(A\to B)⊢A\wedge \mathrm{\neg }B$
6. $A\to B⊢(A\vee C)\to (B\vee C)$

Resolução dos Exercícios

Teoremas

Agora não temos mais premissas para trabalhar, devemos nos limitar às hipóteses. Algumas estratégias para provar teoremas podem ser traçadas:

• Por redução ao absurdo

Para provar $\mathrm{\neg }\phi$, levante a hipótese $\phi$ e derive dela uma contradição e aplique RAA.

Para provar $\phi$ , levante a hipótese $\mathrm{\neg }\phi$ e derive dela uma contradição, aplique RAA e então DN.

• Por regra para condicionais

Para provar $\phi \to \psi$, levante o antecedente $\phi$ como hipótese, derive $\psi$ e então aplique RPC.

Para provar $\phi \leftrightarrow \psi$, prove $\phi \to \psi$ e $\psi \to \phi$, como explicado acima, e então aplique CB.

Exemplo 1

$⊢\mathrm{\neg }(A\wedge \mathrm{\neg }A)$

1.     $A\wedge \mathrm{\neg }A$   Hipótese 2.   $\mathrm{\neg }(A\wedge \mathrm{\neg }A)$   1 RAA

Exemplo 2

$⊢A\vee \mathrm{\neg }A$

1.     $\mathrm{\neg }(A\vee \mathrm{\neg }A)$   Hipótese     2.     $\mathrm{\neg }A\wedge \mathrm{\neg }\mathrm{\neg }A$   1 DM 3.   $\mathrm{\neg }\mathrm{\neg }(A\vee \mathrm{\neg }A)$   1,2 RAA 4.   $A\vee \mathrm{\neg }A$   3 DN

Exemplo 3

$⊢(A\to (A\to B))\to (A\to B)$

1.     $A\to (A\to B)$   Hipótese     2.       $A$   Hipótese 3.       $A\to B$   1,2 MP 4.       $B$    3,2 MP 5.     $A\to B$   2,6 RPC   6.   $(A\to (A\to B))\to (A\to B)$   1,7 RPC

Exemplo 4

$⊢(A\to B)\vee (B\to A)$

01.     $\mathrm{\neg }((A\to B)\vee (B\to A))$   Hipótese 02.     $\mathrm{\neg }(A\to B)\wedge \mathrm{\neg }(B\to A)$   1 DM 03.     $\mathrm{\neg }(A\to B)$   2 S 04.     $\mathrm{\neg }(B\to A)$   2 S 05.       $A$   Hipótese 06.       $B\to A$   5 PRF 07.       $\mathrm{\neg }(B\to A)\wedge (B\to A)$     4,5 C 08.     $\mathrm{\neg }A$     5,7 RAA 09.     $A\to B$     8 DS 10.     $(A\to B)\wedge \mathrm{\neg }(A\to B)$     9,3 C   11.   $\mathrm{\neg }\mathrm{\neg }((A\to B)\vee (B\to A))$   1,10 RAA 12.   $(A\to B)\vee (B\to A)$   11 DN

Exemplo 5

$⊢((P\to Q)\to P)\to P$

01.     $(P\to Q)\to P$   Hipótese     02.       $\mathrm{\neg }P$               Hipótese       03.         $P$   Hipótese         04.           $\mathrm{\neg }Q$   Hipótese           05.           $P\wedge \mathrm{\neg }P$   3,2 C 06.         $\mathrm{\neg }\mathrm{\neg }Q$   4,5 RAA 07.         $Q$   6 DN 08.       $P\to Q$   3,7 RPC 09.       $P$   1,8 MP 10.       $\mathrm{\neg }P\wedge P$   2,9 C 11.     $\mathrm{\neg }\mathrm{\neg }P$   2, 10 RAA 12.     $P$   11 DN 13.   $((P\to Q)\to P)\to P$   1, 12 RPC

Exemplo 6

$⊢((A\wedge B)\to C)\leftrightarrow (A\to (B\to C))$

01.     $(A\wedge B)\to C$   Hipótese     02.       $A$               Hipótese       03.         $B$   Hipótese 04.         $A\wedge B$   2,3 C 05.         $C$   1,4 MP         06.       $B\to C$   3,5 RPC       07.     $A\to (B\to C)$   2,6 RPC   08.   $((A\wedge B)\to C)\to (A\to (B\to C))$   1,7 RPC

09.     $A\to (B\to C)$   Hipótese     10.       $A\wedge B$               Hipótese 11.       $A$   10 S 12.       $B\to C$   9,11 MP 13.       $B$   10 S 14.       $C$   12,13 MP       15.     $(A\wedge B)\to C$   10,14 RPC   16.   $(A\to (B\to C))\to ((A\wedge B)\to C)$   9,15 RPC 17.   $((A\wedge B)\to C)\leftrightarrow (A\to (B\to C))$   8,16 CB

Exercícios

Prove os seguintes teoremas por dedução natural:

1. $⊢A\leftrightarrow A$
2. $⊢A\leftrightarrow \mathrm{\neg }\mathrm{\neg }A$
3. $⊢\mathrm{\neg }(A\leftrightarrow \mathrm{\neg }A)$
4. $⊢A\to (B\to A)$
5. $⊢(\mathrm{\neg }A\to A)\to A$
6. $⊢P\to (Q\to (P\wedge Q))$
7. $⊢((A\wedge B)\to C)\leftrightarrow ((A\wedge \mathrm{\neg }C)\to \mathrm{\neg }B)$
8. $⊢(A\to (B\to C))\to ((A\to B)\to (A\to C))$
9. $⊢(D\to (B\to A))\to (B\to (D\to A))$
10. $⊢(P\to Q)\to ((P\to \mathrm{\neg }Q)\to \mathrm{\neg }P)$
11. $⊢(A\to B)\to ((C\to B)\to ((A\vee C)\to B))$

Resolução dos Exercícios