# 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 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 |