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 \beta \to \neg \alpha \vdash \alpha \to \beta$

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         08.       $\neg B\to \neg \left(A\lor C\right)$   3,7 RPC 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