# Lógica/Cálculo Quantificacional Clássico/Dedução Natural no CQC/Resolução dos exercícios

$\left\{\forall x\left(Px\lor Qx\right),\neg Qa\right\}\vdash Pa$
| 1. | $\forall x\left(Px\lor Qx\right)$ | Premissa |
| 2. | $\neg Qa\,\!$ | Premissa |
| 3. | $Pa\lor Qa\,\!$ | 1 ${\mathcal {E}}\forall$ |
| 4. | $Pa\,\!$ | 3,2 SD |
$\left\{\forall x\left(Ax\land Bx\right),\left(Cx\land Dx\right)\right\}\vdash \left(Ax\land Cx\right)$
| 1. | $\forall x\left(Ax\land Bx\right)$ | Premissa |
| 2. | $\forall x\left(Bx\land Cx\right)$ | Premissa |
| 3. | $Ad\land Bd\,\!$ | 1 ${\mathcal {E}}\forall$ |
| 4. | $Cd\land Dd\,\!$ | 2 ${\mathcal {E}}\forall$ |
| 5. | $Ad\,\!$ | 3 S |
| 6. | $Cd\,\!$ | 4 S |
| 7. | $Ad\land Cd\,\!$ | 5,6 C |
| 8. | $\forall x\left(Ax\land Cx\right)\,\!$ | 7 ${\mathcal {I}}\forall$ |
$\left\{\forall x\left(Ax\to Bx\right),Al\right\}\vdash \exists xBx$
| 1. | $\forall x\left(Ax\to Bx\right)$ | Premissa |
| 2. | $Al\,\!$ | Premissa |
| 3. | $Al\to Bl\,\!$ | 1 ${\mathcal {E}}\forall$ |
| 4. | $Bl\,\!$ | 3,2 MP |
| 5. | $\exists xBx\,\!$ | 5 ${\mathcal {I}}\exists$ |
$\exists x\left(Px\land Qx\right)\vdash \exists xPx\land \exists xQx$
| 1. | $\exists x\left(Px\land Qx\right)\,\!$ | Premissa |
| 2. | $Pa\land Qa\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 3. | $Pa\,\!$ | 2 S |
| 4. | $Qa\,\!$ | 2 S |
| 5. | $\exists xPx\,\!$ | 3 ${\mathcal {I}}\exists$ |
| 6. | $\exists xQx\,\!$ | 4 ${\mathcal {I}}\exists$ |
| 7. | $\exists xPx\land \exists xQx\,\!$ | 5,6 C |
| 8. | $\exists xPx\land \exists xQx\,\!$ | 1,2-7 ${\mathcal {E}}\exists$ |
$\left\{\exists xPx,\forall xQx\right\}\vdash \exists x\left(Px\land Qx\right)$
| 1. | $\exists xPx\,\!$ | Premissa |
| 2. | $\forall xQx\,\!$ | Premissa |
| 3. | $Pa\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 4. | $Qa\,\!$ | 2 ${\mathcal {E}}\forall$ |
| 5. | $Pa\land Qa\,\!$ | 3,4 C |
| 6. | $\exists x\left(Px\land Qx\right)$ | 5 ${\mathcal {I}}\exists$ |
| 7. | $\exists x\left(Px\land Qx\right)$ | 1,3-6 ${\mathcal {E}}\exists$ |

### Exercícios de teoremas

$\vdash \exists xPx\to \neg \forall x\neg Px$
| 1. | $\exists xPx\,\!$ | Hipótese |
| 2. | $\forall x\neg Px\,\!$ | Hipótese |
| 3. | $\neg \exists xPx\,\!$ | 2 IQ |
| 4. | $\exists xPx\land \neg \exists xPx\,\!$ | 1,3 C |
| 5. | $\neg \forall x\neg Px\,\!$ | 2,4 RAA |
| 6. | $\exists xPx\to \neg \forall x\neg Px$ | 1,5 RPC |
$\vdash \forall x\left(Px\to Q\right)\to \exists x\left(Px\to Q\right)$
| 1. | $\forall x\left(Px\to Q\right)\,\!$ | Hipótese |
| 2. | $Pa\to Q\,\!$ | 1 ${\mathcal {E}}\forall$ |
| 3. | $\exists x\left(Px\to Q\right)\,\!$ | 2 ${\mathcal {I}}\exists$ |
| 4. | $\forall x\left(Px\to Q\right)\to \exists x\left(Px\to Q\right)$ | 1,3 RPC |
$\vdash \exists x\exists yPxy\leftrightarrow \exists y\exists xPxy$
| 01. | $\exists x\exists yPxy\,\!$ | Hipótese |
| 02. | $\exists yPxy\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 03. | $Pab\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 04. | $\exists xPxb\,\!$ | 3 ${\mathcal {I}}\exists$ |
| 05. | $\exists y\exists xPxy\,\!$ | 4 ${\mathcal {I}}\exists$ |
| 06. | $\exists y\exists xPxy\,\!$ | 2,3-5 ${\mathcal {E}}\exists$ |
| 07. | $\exists y\exists xPxy\,\!\,\!$ | 1,2-6 ${\mathcal {E}}\exists$ |
| 08. | $\exists y\exists xPxy\to \exists y\exists xPxy\,\!$ | 1,7 RPC |
| 09. | $\exists x\exists yPxy\,\!$ | Hipótese |
| 10. | $\exists xPxa\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 11. | $Pba\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 12. | $\exists yPyb\,\!$ | 11 ${\mathcal {I}}\exists$ |
| 13. | $\exists x\exists yPxy\,\!$ | 12 ${\mathcal {I}}\exists$ |
| 14. | $\exists x\exists yPxy\,\!$ | 10,11-13 ${\mathcal {E}}\exists$ |
| 15. | $\exists x\exists yPxy\,\!\,\!$ | 9,10-14 ${\mathcal {E}}\exists$ |
| 08. | $\exists y\exists xPxy\to \exists x\exists yPxy\,\!$ | 1,7 RPC |
| 17. | $\exists x\exists yPxy\leftrightarrow \exists y\exists xPxy\,\!$ | 8,16 CB |
$\vdash \left(\forall xPx\land \forall xQx\right)\leftrightarrow \forall x\left(Px\land Qx\right)$
| 01. | $\forall xPx\land \forall xQx\,\!$ | Hipótese |
| 02. | $\forall xPx\,\!$ | 1 S |
| 03. | $\forall xQx\,\!$ | 1 S |
| 04. | $Pa\,\!$ | 2 ${\mathcal {E}}\forall$ |
| 05. | $Qa\,\!$ | 3 ${\mathcal {E}}\forall$ |
| 06. | $Pa\land Qa\,\!$ | 4,5 C |
| 07. | $\forall x\left(Px\land Qx\right)\,\!$ | 2 ${\mathcal {I}}\forall$ |
| 08. | $\left(\forall xPx\land \forall xQx\right)\to \forall x\left(Px\land Qx\right)\,\!$ | 1,7 RPC |
| 09. | $\forall x\left(Px\land Qx\right)\,\!$ | Hipótese |
| 10. | $Pa\land Qa\,\!$ | 9 ${\mathcal {E}}\forall$ |
| 11. | $Pa\,\!$ | 10 S |
| 12. | $\forall xPx\,\!$ | 11 ${\mathcal {I}}\forall$ |
| 13. | $Qa\,\!$ | 10 S |
| 14. | $\forall xQx\,\!$ | 13 ${\mathcal {I}}\forall$ |
| 15. | $\forall xQx\,\!$ | 13 ${\mathcal {I}}\forall$ |
| 16. | $\forall x\left(Px\land Qx\right)\to \left(\forall xPx\land \forall xQx\right)\,\!$ | 4,5 RPC |
| 17. | $\left(\forall xPx\land \forall xQx\right)\leftrightarrow \forall x\left(Px\land Qx\right)$ | 8,16 CB |
$\vdash \left(P\land \exists xQx\right)\leftrightarrow \exists x\left(P\land Qx\right)$
| 01. | $P\land \exists xQx$ | Hipótese |
| 02. | $\exists xQx\,\!$ | 1 S |
| 03. | $Qa\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 04. | $P\,\!$ | 1 S |
| 05. | $P\land Qa\,\!$ | 4,3 C |
| 06. | $\exists x\left(P\land Qa\right)\,\!$ | 5 ${\mathcal {I}}\exists$ |
| 07. | $\exists x\left(P\land Qa\right)\,\!$ | 2,3-6 ${\mathcal {E}}\exists$ |
| 08. | $\left(P\land \exists xQx\right)\to \exists x\left(P\land Qx\right)$ | 1,7 RPC |
| 09. | $\exists x\left(P\land Qx\right)$ | Hipótese |
| 10. | $P\land Qa\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 11. | $Qa\,\!$ | 10 S |
| 12. | $\exists xQx\,\!$ | 11 ${\mathcal {I}}\exists$ |
| 13. | $P\,\!$ | 10 S |
| 14. | $P\land \exists xQx\,\!$ | 12,13 C |
| 15. | $P\land \exists xQx\,\!$ | 9,10-14 ${\mathcal {E}}\exists$ |
| 16. | $\exists x\left(P\land Qx\right)\to \left(P\land \exists xQx\right)$ | 9,15 RPC |
| 17. | $\left(P\land \exists xQx\right)\leftrightarrow \exists x\left(P\land Qx\right)$ | 8,16 CB |
$\vdash \left(P\lor \forall xQx\right)\leftrightarrow \forall x(P\lor Qx)$
| 01. | $P\lor \forall xQx\,\!$ | Hipótese |
| 02. | $\neg \forall x\left(P\lor Qx\right)\,\!$ | Hipótese |
| 03. | $\exists x\neg \left(P\lor Qx\right)\,\!$ | 2 IQ |
| 04. | $\neg \left(P\lor Qa\right)\,\!$ | Hipótese para ${\mathcal {E}}\exists$ |
| 05. | $\neg P\land \neg Qa\,\!$ | 4 DM |
| 06. | $\neg Qa\,\!$ | 5 S |
| 07. | $\neg P\,\!$ | 5 S |
| 08. | $\forall xQx\,\!$ | 1,7 SD |
| 09. | $\exists x\neg Qx\,\!$ | 6 ${\mathcal {I}}\exists$ |
| 10. | $\neg \forall xQx\,\!$ | 9 IQ |
| 11. | $\forall xQx\land \neg \forall xQx\,\!$ | 8,10 C |
| 12. | $\forall xQx\land \neg \forall xQx\,\!$ | 3,4-11 ${\mathcal {E}}\exists$ |
| 13. | $\neg \neg \forall x\left(P\lor Qx\right)\,\!$ | 2,17 RAA |
| 14. | $\exists x\left(Px\lor Qx\right)\,\!$ | 13 DN |
| 15. | $\left(P\lor \forall xQx\right)\to \forall x\left(P\lor Qx\right)$ | 1,19 RPC |
| 16. | $\forall x\left(P\lor Qx\right)\,\!$ | Hipótese |
| 17. | $P\lor Qa\,\!$ | 16 ${\mathcal {E}}\forall$ |
| 18. | $\neg \left(P\lor \forall xQx\right)\,\!$ | Hipótese |
| 19. | $\neg P\land \neg \forall xQx\,\!$ | 18 DM |
| 20. | $\neg P\,\!$ | 19 S |
| 21. | $Qa\,\!$ | 17,20 SD |
| 22. | $\forall Qx\,\!$ | 21 ${\mathcal {I}}\forall$ |
| 23. | $\neg \forall Qx\,\!$ | 19 S |
| 24. | $\forall Qx\land \neg \forall Qx\,\!$ | 22,23 C |
| 25. | $\neg \neg \left(P\lor \forall xQx\right)\,\!$ | 18,24 RAA |
| 26. | $\left(P\lor \forall xQx\right)\,\!$ | 25 DN |
| 27. | $\forall x\left(P\lor Qx\right)\to \left(P\lor \forall xQx\right)\,\!$ | 16,26 RPC |
| 28. | $\left(P\lor \forall xQx\right)\leftrightarrow \forall x(P\lor Qx)\,\!$ | 15,27 CB |
$\vdash \exists x(Px\rightarrow Q)\to (\forall xPx\rightarrow Q)$
| 1. | $\exists x(Px\rightarrow Q)\,\!$ | Hipótese |
| 2. | $\forall xPx\,\!$ | Hipótese |
| 3. | $Pa\,\!$ | 2 ${\mathcal {E}}\forall$ |
| 4. | $Pa\to Q\,\!$ | | Hipótese para ${\mathcal {E}}\exists$ |
| 5. | $Q\,\!$ | 4,3 MP |
| 6. | $Q\,\!$ | 1,4-5 ${\mathcal {E}}\exists$ |
| 7. | $\forall xPx\to Q\,\!$ | 2,6 RPC |
| 8. | $\exists x(Px\rightarrow Q)\to (\forall xPx\rightarrow Q)\,\!$ | 1,7 RPC |