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

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

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

Lei de Duns Scot

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

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

Lei De Morgan I

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

1.   $\mathrm{\neg }\alpha \wedge \mathrm{\neg }\beta$   Premissa   2.     $\alpha \vee \beta$   Hipótese 3.     $\mathrm{\neg }\alpha$   1 S 4.     $\mathrm{\neg }\beta$   1 S 5.     $\beta$   2,3 SD 6.     $\beta \wedge \mathrm{\neg }\beta$   5,4 C 7.   $\mathrm{\neg }(\alpha \vee \beta )$   2,6 RAA

Lei De Morgan II

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

1.   $\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta$   Premissa   2.     $\alpha \wedge \beta$   Hipótese 3.     $\alpha$   2 S 4.     $\mathrm{\neg }\mathrm{\neg }\alpha$   3 DN 5.     $\mathrm{\neg }\beta$   1,4 SD 6.     $\beta$   2 S 7.     $\beta \wedge \mathrm{\neg }\beta$   5,6 C 8.   $\mathrm{\neg }(\alpha \wedge \beta )$   2,7 RAA

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

1

$\{(A\wedge B)\to C,\mathrm{\neg }C\}⊢\mathrm{\neg }A\vee \mathrm{\neg }B$

1.   $(A\wedge B)\to C$   Premissa 2.   $\mathrm{\neg }C$   Premissa 3.   $\mathrm{\neg }(A\wedge B)$   1,2 MT 4.   $\mathrm{\neg }A\vee \mathrm{\neg }B$   3 DM

2

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

1.   $\mathrm{\neg }(A\wedge \mathrm{\neg }B)$   Premissa 2.   $\mathrm{\neg }A\vee \mathrm{\neg }\mathrm{\neg }B$   1 DM   3.     $A$   Hipótese 4.     $\mathrm{\neg }\mathrm{\neg }A$   3 DN 5.     $\mathrm{\neg }\mathrm{\neg }B$   2,4 SD 6.     $B$   5 DN 7.   $A\to B$   3,6 RPC

3

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

1.   $\mathrm{\neg }A\to B$        Premissa   2.     $\mathrm{\neg }(A\vee B)$   Hipótese 3.     $\mathrm{\neg }A\wedge \mathrm{\neg }B$   2 DM 4.     $\mathrm{\neg }A$   3 S 5.     $\mathrm{\neg }B$   3 S 6.     $B$   1,4 MP 7.     $B\wedge \mathrm{\neg }B$   6,5 C 8.   $\mathrm{\neg }\mathrm{\neg }(A\vee B)$       2,7 RAA 9.   $A\vee B$       8 DN

4

$\{A\to C,B\to C\}⊢(A\vee B)\to C$

1.   $A\to C$        Premissa 2.   $B\to C$        Premissa   3.     $\mathrm{\neg }C$   Hipótese 4.     $\mathrm{\neg }A$   1,3 MT 5.     $\mathrm{\neg }B$   2,3 MT 6.     $\mathrm{\neg }A\wedge \mathrm{\neg }B$   4,5 C 7.     $\mathrm{\neg }(A\vee B)$   6 DM 8.   $\mathrm{\neg }C\to \mathrm{\neg }(A\vee B)$   3,7 RPC 9.   $(A\vee B)\to C$   8 CT

5

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

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

6

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

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

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

1

$⊢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

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

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

3

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

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

4

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

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

5

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

1.     $\mathrm{\neg }A\to A$           Hipótese     2.       $\mathrm{\neg }A$   Hipótese 3.       $A$   1,2 MP 4.       $A\wedge \mathrm{\neg }A$   3,2 C 5.     $\mathrm{\neg }\mathrm{\neg }A$           2,4 RAA 6.     $A$           5 DN 7.   $(\mathrm{\neg }A\to A)\to A$   1,6 RPC

6

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

1.     $P$           Hipótese     2.       $Q$   Hipótese 3.       $P\wedge Q$   1,2 C 4.     $Q\to (P\wedge Q)$     2,3 RPC 5.   $P\to (Q\to (P\wedge Q))$   1,4 RPC

7

$⊢((A\wedge B)\to C)\leftrightarrow ((A\wedge \mathrm{\neg }C)\to \mathrm{\neg }B)$

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

11.     $(A\wedge \mathrm{\neg }C)\to \mathrm{\neg }B$   Hipótese     12.       $A\wedge B$                Hipótese 13.       $A$   12 S 14.       $B$   12 S 15.       $\mathrm{\neg }\mathrm{\neg }B$   14 DN 16.       $\mathrm{\neg }(A\wedge \mathrm{\neg }C)$   11,15 MT 17.       $\mathrm{\neg }A\vee \mathrm{\neg }\mathrm{\neg }C$   16 DM 18.       $\mathrm{\neg }\mathrm{\neg }A$   13 DN 19.       $\mathrm{\neg }\mathrm{\neg }C$   17,18 SD 20.       $C$   19 DN       21.     $(A\wedge B)\to C$   12,20 RPC   22.   $((A\wedge \mathrm{\neg }C)\to \mathrm{\neg }B)\to ((A\wedge B)\to C)$   9,15 RPC 23.   $((A\wedge B)\to C)\leftrightarrow ((A\wedge \mathrm{\neg }C)\to \mathrm{\neg }B)$   10,22 CB

8

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

1.     $A\to (B\to C)$   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.     $(A\to B)\to (A\to C)$   2,7 RPC   9.   $(A\to (B\to C))\to ((A\to B)\to (A\to C))$   1,8 RPC

9

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

1.     $D\to (B\to A)$   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 (D\to A)$   2,6 RPC   8.   $(D\to (B\to A))\to (B\to (D\to A))$   1,7 RPC

10

$⊢(P\to Q)\to ((P\to \mathrm{\neg }Q)\to \mathrm{\neg }P)$

1.     $P\to Q$   Hipótese     2.       $P\to \mathrm{\neg }Q$         Hipótese       3.         $P$   Hipótese 4.         $Q$   1,3 MP 5.         $\mathrm{\neg }Q$   2,3 MP 6.         $Q\wedge \mathrm{\neg }Q$   4,5 C         7.       $\mathrm{\neg }P$   3,6 RAA       8.     $(P\to \mathrm{\neg }Q)\to \mathrm{\neg }P$   2,7 RPC   9.   $(P\to Q)\to ((P\to \mathrm{\neg }Q)\to \mathrm{\neg }P)$   1,8 RPC

11

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

01.     $A\to B$   Hipótese     02.       $C\to B$         Hipótese       03.         $\mathrm{\neg }B$   Hipótese 04.         $\mathrm{\neg }A$   1,3 MT 05.         $\mathrm{\neg }C$   2,3 MT 06.         $\mathrm{\neg }A\wedge \mathrm{\neg }C$   4,5 C 07.         $\mathrm{\neg }(A\vee C)$   6 DM         08.       $\mathrm{\neg }B\to \mathrm{\neg }(A\vee C)$   3,7 RPC 09.       $(A\vee C)\to B$   8 CT       10.     $(C\to B)\to ((A\vee C)\to B)$   2,7 RPC   11.   $(A\to B)\to ((C\to B)\to ((A\vee C)\to B))$   1,10 RPC