Lógica: Cálculo Proposicional Clássico: Dedução Natural - Parte II/Resolução dos Exercícios

Resolução de algumas Regras de Inferência Derivadas

Contraposição

$\neg \ A\lor \ \neg \ A\,\!$

1.   $\neg \beta \to \neg \alpha$   Premissa   2.     $\alpha \,\!$   Hipótese 3.     $\neg \neg \alpha \,\!$   2 DN 4.     $\neg \neg \beta \,\!$   1,3 MT 5.     $\beta \,\!$   4 DN 6.   $\alpha \to \beta$   2,5 RPC

Lei de Duns Scot

$\alpha \vdash \neg \alpha \to \beta$

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

Lei De Morgan I

$\neg \alpha \land \neg \beta \vdash \neg \left(\alpha \lor \beta \right)\,\!$

1.   $\neg \alpha \land \neg \beta \,\!$   Premissa   2.     $\alpha \lor \beta \,\!$   Hipótese 3.     $\neg \alpha \,\!$   1 S 4.     $\neg \beta \,\!$   1 S 5.     $\beta \,\!$   2,3 SD 6.     $\beta \land \neg \beta \,\!$   5,4 C 7.   $\neg \left(\alpha \lor \beta \right)$   2,6 RAA

Lei De Morgan II

$\neg \alpha \lor \neg \beta \vdash \neg \left(\alpha \land \beta \right)\,\!$

1.   $\neg \alpha \lor \neg \beta \,\!$   Premissa   2.     $\alpha \land \beta \,\!$   Hipótese 3.     $\alpha \,\!$   2 S 4.     $\neg \neg \alpha \,\!$   3 DN 5.     $\neg \beta \,\!$   1,4 SD 6.     $\beta \,\!$   2 S 7.     $\beta \land \neg \beta \,\!$   5,6 C 8.   $\neg \left(\alpha \land \beta \right)\,\!$   2,7 RAA

Resolução dos Exercícios de Aplicação das Regras de Inferência Derivadas

1

$\left\{\left(A\land B\right)\to C,\neg C\right\}\vdash \neg A\lor \neg B$

1.   $\left(A\land B\right)\to C$   Premissa 2.   $\neg C\,\!$   Premissa 3.   $\neg \left(A\land B\right)\,\!$   1,2 MT 4.   $\neg A\lor \neg B\,\!$   3 DM

2

$\neg \left(A\land \neg B\right)\vdash A\to B$

1.   $\neg \left(A\land \neg B\right)$   Premissa 2.   $\neg A\lor \neg \neg B\,\!$   1 DM   3.     $A\,\!$   Hipótese 4.     $\neg \neg A\,\!$   3 DN 5.     $\neg \neg B\,\!$   2,4 SD 6.     $B\,\!$   5 DN 7.   $A\to B\,\!$   3,6 RPC

3

$\neg A\to B\vdash A\lor B$

1.   $\neg A\to B$        Premissa   2.     $\neg \left(A\lor B\right)$   Hipótese 3.     $\neg A\land \neg B$   2 DM 4.     $\neg A\,\!$   3 S 5.     $\neg B\,\!$   3 S 6.     $B\,\!$   1,4 MP 7.     $B\land \neg B$   6,5 C 8.   $\neg \neg \left(A\lor B\right)$       2,7 RAA 9.   $A\lor B\,\!$       8 DN

4

$\left\{A\to C,B\to C\right\}\vdash \left(A\lor B\right)\to C$

1.   $A\to C\,\!$        Premissa 2.   $B\to C\,\!$        Premissa   3.     $\neg C\,\!$   Hipótese 4.     $\neg A\,\!$   1,3 MT 5.     $\neg B\,\!$   2,3 MT 6.     $\neg A\land \neg B\,\!$   4,5 C 7.     $\neg \left(A\lor B\right)$   6 DM 8.   $\neg C\to \neg \left(A\lor B\right)$   3,7 RPC 9.   $\left(A\lor B\right)\to C$   8 CT

5

$\neg \left(A\to B\right)\vdash A\land \neg B$

01.   $\neg \left(A\to B\right)$        Premissa   02.     $\neg \left(A\land \neg B\right)$       Hipótese 03.     $\neg A\lor \neg \neg B$       2 DM     04.       $A\,\!$   Hipótese   05.       $\neg \neg A\,\!$   4 DN 06.       $\neg \neg B\,\!$   3,5 SD 07.       $B\,\!$   6 DN 08.     $A\to B\,\!$             4,7 RPC 09.     $\left(A\to B\right)\land \neg \left(A\to B\right)\,\!$             8,1 C 10.   $\neg \neg \left(A\land \neg B\right)$                         2,9 RAA 11.   $A\land \neg B\,\!$                         10 DN

6

$A\to B\vdash \left(A\lor C\right)\to \left(B\lor C\right)$

01.   $A\to B\,\!$        Premissa   02.     $A\lor C\,\!$       Hipótese     03.       $\neg \left(B\lor C\right)$   Hipótese   04.       $\neg B\land \neg C\,\!$   3 DM 05.       $\neg C\,\!$   4 S 06.       $\neg B\,\!$   4 S 07.       $A\,\!$   2,5 SD 08.       $B\,\!$   1,7 MP 09.       $B\land \neg B\,\!$   1,7 MP 10.     $\neg \neg \left(B\lor C\right)\,\!$        3,9 RAA 11.     $B\lor C\,\!$        10 DN 12.   $\left(A\lor C\right)\to \left(B\lor C\right)$   2,11 RPC

Resolução dos Exercícios de Demonstração de Teoremas

1

$\vdash A\leftrightarrow A\,\!$

1.     $A\,\!$           Hipótese     2.     $A\,\!$           1 R 3.   $A\to A\,\!$   1,2 RPC 4.   $A\leftrightarrow A$   3,3 CB

2

$\vdash A\leftrightarrow \neg \neg A\,\!$

1.     $A\,\!$         Hipótese     2.     $\neg \neg A\,\!$         1 DN 3.   $A\to \neg \neg A\,\!$   1,2 RPC 4.     $\neg \neg A\,\!$         Hipótese     5.     $A\,\!$         4 DN 6.   $\neg \neg A\to A\,\!$   4,5 RPC 7.   $A\leftrightarrow \neg \neg A$   3,6 CB

3

$\vdash \neg \left(A\leftrightarrow \neg A\right)\,\!$

01.     $A\leftrightarrow \neg A$           Hipótese 02.     $A\to \neg A\,\!$         1 BC 03.       $A\,\!$   Hipótese 04.       $\neg A\,\!$   2,3 MP 05.       $A\land \neg A$     3,4 C 06.     $\neg A\,\!$     3,5 RAA 07.     $\neg A\to A\,\!$     1 BC 08.     $A\,\!$     7,6 MP 09.     $A\land \neg A\,\!$     8,6 C   10.   $\neg \left(A\leftrightarrow \neg A\right)$   1,9 RAA

4

$\vdash A\to \left(B\to A\right)\,\!$

1.     $A\,\!$           Hipótese     2.       $B\,\!$   Hipótese 3.       $A\,\!$   1 R 4.     $B\to A\,\!$     2,3 RPC 5.   $A\to \left(B\to A\right)$   1,4 RPC

5

$\vdash \left(\neg A\to A\right)\to A\,\!$

1.     $\neg A\to A\,\!$           Hipótese     2.       $\neg A\,\!$   Hipótese 3.       $A\,\!$   1,2 MP 4.       $A\land \neg A\,\!$   3,2 C 5.     $\neg \neg A\,\!$           2,4 RAA 6.     $A\,\!$           5 DN 7.   $\left(\neg A\to A\right)\to A$   1,6 RPC

6

$\vdash P\to \left(Q\to \left(P\land Q\right)\right)$

1.     $P\,\!$           Hipótese     2.       $Q\,\!$   Hipótese 3.       $P\land Q\,\!$   1,2 C 4.     $Q\to \left(P\land Q\right)\,\!$     2,3 RPC 5.   $P\to \left(Q\to \left(P\land Q\right)\right)$   1,4 RPC

7

$\vdash \left(\left(A\land B\right)\to C\right)\leftrightarrow \left(\left(A\land \neg C\right)\to \neg B\right)\,\!$

01.     $\left(A\land B\right)\to C\,\!$   Hipótese     02.       $A\land \neg C\,\!$                Hipótese 03.       $A\,\!$                2 S 04.       $\neg C\,\!$                2 S 05.       $\neg \left(A\land B\right)\,\!$                1,4 MT 06.       $\neg A\lor \neg B\,\!$                5 DM 07.       $\neg \neg A\,\!$                3 DN 08.       $\neg B\,\!$                6,7 SD       09.     $\left(\left(A\land \neg C\right)\to \neg B\right)\,\!$   2,8 RPC     10.   $\left(\left(A\land B\right)\to C\right)\to \left(\left(A\land \neg C\right)\to \neg B\right)\,\!$   1,9 RPC

11.     $\left(A\land \neg C\right)\to \neg B\,\!$   Hipótese     12.       $A\land B\,\!$                Hipótese 13.       $A\,\!$   12 S 14.       $B\,\!$   12 S 15.       $\neg \neg B\,\!$   14 DN 16.       $\neg \left(A\land \neg C\right)\,\!$   11,15 MT 17.       $\neg A\lor \neg \neg C\,\!$   16 DM 18.       $\neg \neg A\,\!$   13 DN 19.       $\neg \neg C\,\!$   17,18 SD 20.       $C\,\!$   19 DN       21.     $\left(A\land B\right)\to C\,\!$   12,20 RPC   22.   $\left(\left(A\land \neg C\right)\to \neg B\right)\to \left(\left(A\land B\right)\to C\right)\,\!$   9,15 RPC 23.   $\left(\left(A\land B\right)\to C\right)\leftrightarrow \left(\left(A\land \neg C\right)\to \neg B\right)\,\!$   10,22 CB

8

$\vdash \left(A\to \left(B\to C\right)\right)\to \left(\left(A\to B\right)\to \left(A\to C\right)\right)\,\!$

1.     $A\to \left(B\to C\right)\,\!$   Hipótese     2.       $A\to B\,\!$         Hipótese       3.         $A\,\!$   Hipótese 4.         $B\to C\,\!$   1,3 MP 5.         $B\,\!$   2,3 MP 6.         $C\,\!$   4,5 MP         7.       $A\to C\,\!$   3,6 RPC       8.     $\left(A\to B\right)\to \left(A\to C\right)\,\!$   2,7 RPC   9.   $\left(A\to \left(B\to C\right)\right)\to \left(\left(A\to B\right)\to \left(A\to C\right)\right)\,\!$   1,8 RPC

9

$\vdash \left(D\to \left(B\to A\right)\right)\to \left(B\to \left(D\to A\right)\right)\,\!$

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

10

$\vdash \left(P\to Q\right)\to \left(\left(P\to \neg Q\right)\to \neg P\right)\,\!$

1.     $P\to Q\,\!$   Hipótese     2.       $P\to \neg Q\,\!$         Hipótese       3.         $P\,\!$   Hipótese 4.         $Q\,\!$   1,3 MP 5.         $\neg Q\,\!$   2,3 MP 6.         $Q\land \neg Q\,\!$   4,5 C         7.       $\neg P\,\!$   3,6 RAA       8.     $\left(P\to \neg Q\right)\to \neg P\,\!$   2,7 RPC   9.   $\left(P\to Q\right)\to \left(\left(P\to \neg Q\right)\to \neg P\right)\,\!$   1,8 RPC

11

$\vdash \left(A\to B\right)\to \left(\left(C\to B\right)\to \left(\left(A\lor C\right)\to B\right)\right)\,\!$

01.     $A\to B\,\!$   Hipótese     02.       $C\to B\,\!$         Hipótese       03.         $\neg B\,\!$   Hipótese 04.         $\neg A\,\!$   1,3 MT 05.         $\neg C\,\!$   2,3 MT 06.         $\neg A\land \neg C\,\!$   4,5 C 07.         $\neg \left(A\lor C\right)\,\!$   6 DM   &;nbsp;     08.       $\neg B\to \neg \left(A\lor C\right)\,\!$   3,7 RAA 09.       $\left(A\lor C\right)\to B\,\!$   8 CT       10.     $\left(C\to B\right)\to \left(\left(A\lor C\right)\to B\right)\,\!$   2,7 RPC   11.   $\left(A\to B\right)\to \left(\left(C\to B\right)\to \left(\left(A\lor C\right)\to B\right)\right)\,\!$   1,10 RPC