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