# Lógica/Cálculo Proposicional Clássico/Dedução Natural - Parte II
## Regras de Inferência Derivadas

Por meio das regras de inferência diretas e hipotéticas podemos demonstrar vários raciocínios bastante recorrentes. Estes raciocíonios, uma vez demonstrados, podem ser usados como regras de inferência diretas. Elas não são necessárias, mas são bastante úteis, tornando nossas derivações muito mais sucintas. Anteriormente demonstramos dois raciocínios que nos serão úteis como regras de inferência derivadas:
* Dupla Negação em ambas direções (DN)
    ${\frac {\neg \neg \varphi \,}{\overline {\varphi \quad \;\,}}}$
* Silogismo Hipotético (SH)
    $\alpha \to \beta$
    ${\underline {\beta \to \gamma }}$
    $\alpha \to \gamma$
Vamos ampliar nossa lista de regras de inferência derivadas, demonstrado uma por uma:

### Repetição (R)

$\alpha \vdash \alpha$
| 1. | $\alpha$ | Premissa |
| 2. | $\neg \neg \alpha$ | 1 DN |
| 3. | $\alpha$ | 2 DN |

### Modus Tollens (MT)

$\left\{\alpha \to \beta ,\neg \beta \right\}\vdash \neg \alpha$
| 1. | $\alpha \to \beta$ | Premissa |
| 2. | $\neg \beta$ | Premissa |
| 3. | $\alpha$ | Hipótese |
| 4. | $\beta$ | 1,3 MP |
| 5. | $\beta \land \neg \beta$ | 2,4 C |
| 6. | $\neg \alpha$ | 3,5 RAA |

### Prefixação (PRF)

$\alpha \vdash \beta \to \alpha$
| 1. | $\alpha$ | Premissa |
| 2. | $\beta$ | Hipótese |
| 3. | $\alpha$ | 1 R |
| 4. | $\beta \to \alpha$ | 2,3 RPC |

### Contraposição (CT)

Aproveitaremos o Modus Tollens como regra de inferência.
$\alpha \to \beta \vdash \neg \beta \to \neg \alpha$
| 1. | $\alpha \to \beta$ | Premissa |
| 2. | $\neg \beta$ | Hipótese |
| 3. | $\neg \alpha$ | 1,2 MT |
| 4. | $\neg \beta \to \neg \alpha$ | 2,3 RPC |
Agora tente você provar a recíproca, ou seja, que $\neg \beta \to \neg \alpha \vdash \alpha \to \beta$
Confira aqui sua resposta.

### Contradição (CTR)

$\left\{\alpha ,\neg \alpha \right\}\vdash \beta$
| 1. | $\alpha$ | Premissa |
| 2. | $\neg \alpha$ | Premissa |
| 3. | $\alpha \lor \beta$ | 1 E |
| 4. | $\beta$ | 2,3 SD |

### Lei de Duns Scot (DS)

$\neg \alpha \vdash \alpha \to \beta$
| 1. | $\neg \alpha$ | Premissa |
| 2. | $\alpha$ | Hipótese |
| 3. | $\beta$ | 1,2 CTR |
| 4. | $\alpha \to \beta$ | 2,3 RPC |
Prove que também vale $\alpha \vdash \neg \alpha \to \beta$ .
Confira aqui sua resposta.

### Lei De Morgan I (DM)

$\neg \left(\alpha \lor \beta \right)\vdash \neg \alpha \land \neg \beta$
| 01. | $\neg \left(\alpha \lor \beta \right)$ | Premissa |
| 02. | $\alpha$ | Hipótese |
| 03. | $\alpha \lor \beta$ | 2 E |
| 04. | $\left(\alpha \lor \beta \right)\land \neg \left(\alpha \lor \beta \right)$ | 1,3 C |
| 05. | $\neg \alpha$ | 2,4 RAA |
| 06. | $\beta$ | Hipótese |
| 07. | $\alpha \lor \beta$ | 6 E |
| 08. | $\left(\alpha \lor \beta \right)\land \neg \left(\alpha \lor \beta \right)$ | 1,7 C |
| 09. | $\neg \beta$ | 6,8 RAA |
| 10. | $\neg \alpha \land \neg \beta$ | 5,9 C |
Agora tente você provar a recíproca, ou seja, que $\neg \alpha \land \neg \beta \vdash \neg \left(\alpha \lor \beta \right)$
Confira aqui sua resposta

### Lei De Morgan II (DM)

$\neg \left(\alpha \land \beta \right)\vdash \neg \alpha \lor \neg \beta$
| 01. | $\neg \left(\alpha \land \beta \right)$ | Premissa |
| 02. | $\neg \left(\neg \alpha \lor \neg \beta \right)$ | Hipótese |
| 03. | $\neg \alpha$ | Hipótese |
| 04. | $\neg \alpha \lor \neg \beta$ | 3 E |
| 05. | $\left(\neg \alpha \lor \neg \beta \right)\land \neg \left(\neg \alpha \lor \neg \beta \right)$ | 5,2 C |
| 06. | $\neg \neg \alpha$ | 3,5 RAA |
| 07. | $\alpha$ | 6 DN |
| 08. | $\neg \beta$ | Hipótese |
| 09. | $\neg \alpha \lor \neg \beta$ | 8 E |
| 10. | $\left(\neg \alpha \lor \neg \beta \right)\land \neg \left(\neg \alpha \lor \neg \beta \right)$ | 9,2 C |
| 11. | $\neg \neg \beta$ | 8,10 RAA |
| 12. | $\beta$ | 11 DN |
| 13. | $\alpha \land \beta$ | 7,12 C |
| 14. | $\left(\alpha \land \beta \right)\land \neg \left(\alpha \land \beta \right)$ | 13,1 C |
| 15. | $\neg \neg \left(\neg \alpha \lor \neg \beta \right)$ | 2,14 RAA |
| 16. | $\neg \alpha \lor \neg \beta$ | 15 DN |
Tente você agora provar a recíprova, ou seja, que $\neg \alpha \lor \neg \beta \vdash \neg \left(\alpha \land \beta \right)$
Confira aqui sua resposta

### Exercícios

Valendo-se das regras derivadas, prove que:
* $\left\{\left(A\land B\right)\to C,\neg C\right\}\vdash \neg A\lor \neg B$
* $\neg \left(A\land \neg B\right)\vdash A\to B$
* $\neg A\to B\vdash A\lor B$
* $\left\{A\to C,B\to C\right\}\vdash \left(A\lor B\right)\to C$
* $\neg \left(A\to B\right)\vdash A\land \neg B$
* $A\to B\vdash \left(A\lor C\right)\to \left(B\lor C\right)$
Resolução dos Exercícios

## Teoremas

Agora não temos mais premissas para trabalhar, devemos nos limitar às hipóteses. Algumas estratégias para provar teoremas podem ser traçadas:
* Por redução ao absurdo
Para provar $\neg \varphi$, levante a hipótese $\varphi$ e derive dela uma contradição e aplique RAA.
Para provar $\varphi$ , levante a hipótese $\neg \varphi$ e derive dela uma contradição, aplique RAA e então DN.
* Por regra para condicionais
Para provar $\varphi \to \psi$, levante o antecedente $\varphi$ como hipótese, derive $\psi$ e então aplique RPC.
Para provar $\varphi \leftrightarrow \psi$, prove $\varphi \to \psi$ e $\psi \to \varphi$, como explicado acima, e então aplique CB.

### Exemplo 1

$\vdash \neg \left(A\land \neg A\right)$
| 1. | $A\land \neg A$ | Hipótese |
| 2. | $\neg \left(A\land \neg A\right)$ | 1 RAA |

### Exemplo 2

$\vdash A\lor \neg A$
| 1. | $\neg \left(A\lor \neg A\right)$ | Hipótese |
| 2. | $\neg A\land \neg \neg A$ | 1 DM |
| 3. | $\neg \neg \left(A\lor \neg A\right)$ | 1,2 RAA |
| 4. | $A\lor \neg A$ | 3 DN |

### Exemplo 3

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

### Exemplo 4

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

### Exemplo 5

$\vdash \left(\left(P\to Q\right)\to P\right)\to P$
| 01. | $\left(P\to Q\right)\to P$ | Hipótese |
| 02. | $\neg P$ | Hipótese |
| 03. | $P$ | Hipótese |
| 04. | $\neg Q$ | Hipótese |
| 05. | $P\land \neg P$ | 3,2 C |
| 06. | $\neg \neg Q$ | 4,5 RAA |
| 07. | $Q$ | 6 DN |
| 08. | $P\to Q$ | 3,7 RPC |
| 09. | $P$ | 1,8 MP |
| 10. | $\neg P\land P$ | 2,9 C |
| 11. | $\neg \neg P$ | 2, 10 RAA |
| 12. | $P$ | 11 DN |
| 13. | $\left(\left(P\to Q\right)\to P\right)\to P\,\!$ | 1, 12 RPC |

### Exemplo 6

$\vdash \left(\left(A\land B\right)\to C\right)\leftrightarrow \left(A\to \left(B\to C\right)\right)$
| 01. | $\left(A\land B\right)\to C$ | Hipótese |
| 02. | $A$ | Hipótese |
| 03. | $B$ | Hipótese |
| 04. | $A\land B$ | 2,3 C |
| 05. | $C$ | 1,4 MP |
| 06. | $B\to C$ | 3,5 RPC |
| 07. | $A\to \left(B\to C\right)$ | 2,6 RPC |
| 08. | $\left(\left(A\land B\right)\to C\right)\to \left(A\to \left(B\to C\right)\right)$ | 1,7 RPC |
| 09. | $A\to \left(B\to C\right)$ | Hipótese |
| 10. | $A\land B$ | Hipótese |
| 11. | $A$ | 10 S |
| 12. | $B\to C$ | 9,11 MP |
| 13. | $B$ | 10 S |
| 14. | $C$ | 12,13 MP |
| 15. | $\left(A\land B\right)\to C$ | 10,14 RPC |
| 16. | $\left(A\to \left(B\to C\right)\right)\to \left(\left(A\land B\right)\to C\right)$ | 9,15 RPC |
| 17. | $\left(\left(A\land B\right)\to C\right)\leftrightarrow \left(A\to \left(B\to C\right)\right)$ | 8,16 CB |

### Exercícios

Prove os seguintes teoremas por dedução natural:
* $\vdash A\leftrightarrow A$
* $\vdash A\leftrightarrow \neg \neg A$
* $\vdash \neg \left(A\leftrightarrow \neg A\right)$
* $\vdash A\to \left(B\to A\right)$
* $\vdash \left(\neg A\to A\right)\to A$
* $\vdash P\to \left(Q\to \left(P\land Q\right)\right)$
* $\vdash \left(\left(A\land B\right)\to C\right)\leftrightarrow \left(\left(A\land \neg C\right)\to \neg B\right)$
* $\vdash \left(A\to \left(B\to C\right)\ \right)\to \left(\left(A\to B\right)\to \left(A\to C\right)\right)$
* $\vdash \left(D\to \left(B\to A\right)\right)\to \left(B\to \left(D\to A\right)\right)$
* $\vdash \left(P\to Q\right)\to \left(\left(P\to \neg Q\right)\to \neg P\right)$
* $\vdash \left(A\to B\right)\to \left(\left(C\to B\right)\to \left(\left(A\lor C\right)\to B\right)\right)$
Resolução dos Exercícios