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