Lógica/Cálculo Quantificacional Clássico/Dedução Natural no CQC

Este módulo pressupõe a leitura prévia dos módulos Lógica/Cálculo Proposicional Clássico/Dedução Natural - Parte I e Lógica/Cálculo Proposicional Clássico/Dedução Natural - Parte II.

Regras para Quantificadores

Vamos estabelecer duas regras para cada quantificador: uma para removê-lo e outra para inserí-lo na derivação.

Temos que ser muito cautelosos na aplicação destas regras, pois elas tem muitas restrições. Algumas regras terão a restrição de substitualidade, a qual cabe definir agora:

Dada uma constante $\mathrm {c}$, uma variável $x$ e uma fórmula $\alpha$ quantificada, se $\mathrm {c}$ não ocorre em $\alpha$ no escopo do quantificador para $x$, então dizemos que $\mathrm {c}$ é substituível por $x$ em $\alpha$ .

Eliminação do Universal

${\frac {\forall x(\alpha )}{\alpha \left[x/\mathrm {c} \right]}}$

Ou seja, dada uma fórmula $\forall x\alpha$, aplica-se a eliminação do universal, derivando uma fórmula $\alpha$ tal que a variável $x$ dá lugar a uma constante $\mathrm {c}$ .

• Exemplo

$\left\{\forall x\left(Hx\to Mx\right),Hs\right\}\vdash Ms$

1.   $\forall x\left(Hx\to Mx\right)$   Premissa 2.   $Hs$   Premissa 3.   $Hs\to Ms$   1 ${\mathcal {E}}\forall$ 4.   $Ms$   3,2 MP

• CUIDADO

Lembre-se que esta regra é aplicável a fórmulas quantificadas universalmente, e não a quaisquer fórmulas que contém o quantificador universal. Por exemplo, a eliminação do universal não é aplicável à fórmula $\forall xHx\to Ms$ .

Introdução do Universal

${\frac {\alpha \left(\mathrm {c} \right)}{\forall x\alpha \left(\mathrm {c} /x\right)}}$

Ou seja, dada uma fórmula $\alpha$ na qual ocorre a constante $\mathrm {c}$, aplica-se a introdução do universal, derivando uma fórmula $\forall x\alpha$ tal que a constante $\mathrm {c}$ dá lugar à variável $x$ . A esta regra coloca-se as seguintes restrições:

1. a constante $\mathrm {c}$ não pode ocorrer em premissa ou hipótese vigente.
2. $\mathrm {c}$ deve ser substituível por $x$ em $\alpha$.

• Exemplo 1

$\left\{\forall x\left(Ax\to Bx\right),\forall x\left(Bx\to Cx\right)\right\}\vdash \forall x\left(Ax\to Cx\right)$

1.   $\forall x\left(Ax\to Bx\right)$   Premissa 2.   $\forall x\left(Bx\to Cx\right)$   Premissa 3.   $Ac\to Bc$   1 ${\mathcal {E}}\forall$ 4.   $Bc\to Cc$   2 ${\mathcal {E}}\forall$ 5.   $Ac\to Cc$   3,4 SH 6.   $\forall x\left(Ax\to Cx\right)$   5 ${\mathcal {I}}\forall$

• Exemplo 2

$\forall x\forall yPxy\vdash \forall y\forall xPyx$

1.   $\forall x\forall yPxy$   Premissa 2.   $\forall xPxb$   1 ${\mathcal {E}}\forall$ 3.   $Pab$   2 ${\mathcal {E}}\forall$ 4.   $\forall xPax$   3 ${\mathcal {I}}\forall$ 5.   $\forall y\forall xPyx$   4 ${\mathcal {I}}\forall$

• CUIDADO

O desrespeito à primeira restrição acarretará em derivações falaciosas. Por exemplo:

1.   $Lf$   Premissa 2.   $\forall xLx$   1 ${\mathcal {I}}\forall$

Algo como "Frege é lógico. Logo, todos são lógicos". O que é obviamente inválido.

O desrespeito à segunda restrição também acarretará em derivações absurdas, tais como:

1.   $\forall x\exists yAxy$   Premissa 2.   $\exists yAby$   1 ${\mathcal {E}}\forall$ 3.   $\forall y\exists yAyy$   2 ${\mathcal {I}}\forall$

Introdução do Existencial

${\frac {\alpha \left(\mathrm {c} \right)}{\exists x\alpha \left(\mathrm {c} /x\right)}}$

Ou seja, dada uma fórmula $\alpha$ na qual ocorre a constante $\mathrm {c}$, aplica-se a introdução do existencial, derivando uma fórmula $\exists x\alpha$ tal que a constante $\mathrm {c}$ dá lugar à variável $x$ . A esta regra coloca-se a restrição de que $\mathrm {c}$ deve ser substituível por $x$ em $\alpha$.

• Exemplo 1

$\forall xPx\vdash \exists xPx$

1.   $\forall xPx$   Premissa 2.   $Pa$   1 ${\mathcal {E}}\forall$ 3.   $\exists xPx$   2 ${\mathcal {I}}\exists$

• Exemplo 2

$Ac\land La\vdash \exists xAx\land \exists yLy$

1.   $Ac\land La$   Premissa 2.   $Ac$   1 S 3.   $\exists xAx$   2 ${\mathcal {I}}\exists$ 4.   $La$   1 S 5.   $\exists yLy$   4 ${\mathcal {I}}\exists$ 6.   $\exists xAx\land \exists yLy$   3,5 C

• CUIDADO

Lembre-se que apenas uma constante por vez pode ser substituída pela variável. Caso o contrário, ter-se-ia derivações absurdas como:

1.   $Ac\land La$   Premissa 2.   $\exists x\left(Ax\land Lx\right)$   1 ${\mathcal {I}}\exists$

Algo como "Colombo descobriu a América e Armstrong andou sobre a Lua. Logo, alguém descobriu a América e andou sobre a Lua". O que é obviamente inválido.

Eliminação do Existencial

Trataremos aqui a eliminação do existencial como uma regra de inferência hipotética:

Dada uma fórmula $\exists x\alpha$, levanta-se como hipótese uma fórmula $\alpha$ tal que a variável $x$ dá lugar a uma constante $\mathrm {c}$. Desta hipótese, deriva-se uma fórmula $\beta$. Ao aplicar a eliminação do existencial, descarta-se a hipótese e $\beta$ é inserida na derivação. A esta regra coloca-se a seguinte restrição: a constante $\mathrm {c}$ não pode ocorrer em premissa, hipótese vigente, em $\alpha$ ou $\beta$ .

• Exemplo 1

$\left\{\exists xPx,\left(\exists x\neg \neg Px\right)\to Qb\right\}\vdash Qb$

1.   $\exists xPx$   Premissa 2.   $\left(\exists x\neg \neg Px\right)\to Qb$   Premissa   3.     $Pa$   Hipótese para ${\mathcal {E}}\exists$ 4.     $\neg \neg Pa$   3 DN 5.     $\exists x\neg \neg Px$   4 ${\mathcal {I}}\exists$ 6.     $Qb$   2,5 MP 7.   $Qb$   1,3-5 ${\mathcal {E}}\exists$

• Exemplo 2

$\left\{\forall x\left(Ax\to Bx\right),\neg \exists \left(Bx\land Cx\right)\right\}\vdash \neg \exists x\left(Ax\land Cx\right)$

01.   $\forall x\left(Ax\to Bx\right)$   Premissa 02.   $\neg \exists \left(Bx\land Cx\right)$   Premissa   03.     $\exists x\left(Ax\land Cx\right)$   Hipótese     04.       $Ad\land Cd$   Hipotese para ${\mathcal {E}}\exists$ 05.       $Ad\to Bd$   1 ${\mathcal {E}}\forall$ 06.       $Ad$   4 S 07.       $Bd$   5,6 MP 08.       $Cd$   4 S 09.       $Bd\land Cd$   7,8 C 10.       $\exists x\left(Bx\land Cx\right)$   9 ${\mathcal {I}}\exists$ 11.     $\exists x\left(Bx\land Cx\right)$   3,4-10 ${\mathcal {E}}\exists$ 12.     $\exists x\left(Bx\land Cx\right)\land \neg \exists x\left(Bx\land Cx\right)$   11,2 C 13.   $\neg \exists x\left(Ax\land Cx\right)$   3,12 RAA

Exercício

Demonstre:

1. $\left\{\forall x\left(Px\lor Qx\right),\neg Qa\right\}\vdash Pa$
2. $\left\{\forall x\left(Ax\land Bx\right),\forall x\left(Cx\land Dx\right)\right\}\vdash \forall x\left(Ax\land Cx\right)$
3. $\left\{\forall x\left(Ax\to Bx\right),Al\right\}\vdash \exists xBx$
4. $\exists x\left(Px\land Qx\right)\vdash \exists xPx\land \exists xQx$
5. $\left\{\exists xPx,\forall xQx\right\}\vdash \exists x\left(Px\land Qx\right)$

Confira aqui as respostas

Regras Derivadas para Quantificadores

A única regra derivada para quantificadores que trataremos aqui é o Intercâmbio de Quantificadores (IQ):

${\frac {\neg \forall x\alpha }{\overline {\exists x\neg \alpha }}}$         ${\frac {\neg \exists x\alpha }{\overline {\forall x\neg \alpha }}}$

Vamos provar cada caso deste regra:

Intercâmbio de Quantificadores 1

$\forall x\neg \alpha \vdash \neg \exists x\alpha$

1.   $\forall x\neg \alpha$   Premissa 2.   $\neg \alpha \left(\mathrm {c} \right)$   1 ${\mathcal {E}}\forall$   3.     $\exists x\alpha$   Hipótese     4.       $\alpha \left(\mathrm {c} \right)$   Hipótese para ${\mathcal {E}}\exists$ 5.       $\alpha \left(\mathrm {c} \right)\land \neg \alpha \left(\mathrm {c} \right)$   4,2 C 6.       $\forall x\left(\alpha \land \neg \alpha \right)$   5 ${\mathcal {I}}\forall$ 7.     $\forall x\left(\alpha \land \neg \alpha \right)$   3,4-6 ${\mathcal {E}}\exists$ 8.     $\alpha \left(\mathrm {c} \right)\land \neg \alpha \left(\mathrm {c} \right)$   7 ${\mathcal {E}}\forall$ 9.   $\neg \exists x\alpha$   3,8 RAA

Intercâmbio de Quantificadores 2

$\neg \exists x\alpha \vdash \forall x\neg \alpha$

1.   $\neg \exists x\alpha$   Premissa   2.     $\alpha \left(\mathrm {c} \right)$   Hipótese 3.     $\exists x\alpha$   2 ${\mathcal {I}}\exists$ 4.     $\exists x\alpha \land \neg \exists x\alpha$   3,1 C 5.   $\neg \alpha \left(\mathrm {c} \right)$   2,4 RAA 6.   $\forall x\neg \alpha$   5 ${\mathcal {I}}\forall$

Intercâmbio de Quantificadores 3

$\neg \forall x\alpha \vdash \exists x\neg \alpha$

01.   $\neg \forall x\alpha$   Premissa   02.     $\neg \exists x\neg \alpha$   Hipótese     03.       $\neg \alpha \left(\mathrm {c} \right)$   Hipótese 04.       $\exists x\neg \alpha$   3 ${\mathcal {I}}\exists$ 05.       $\exists x\neg \alpha \land \neg \exists x\neg \alpha$   2,4 C 06.     $\neg \neg \alpha \left(\mathrm {c} \right)$   3,5 RAA 07.     $\alpha \left(\mathrm {c} \right)$   6 DN 08.     $\forall x\alpha$   7 ${\mathcal {I}}\forall$ 09.     $\forall x\alpha \land \neg \forall x\alpha$   1,8 C 10.   $\neg \neg \exists x\neg \alpha$   2,9 RAA 11.   $\exists x\neg \alpha$   10 DN

Intercâmbio de Quantificadores 4

$\exists x\neg \alpha \vdash \neg \forall x\alpha$

1.   $\exists x\neg \alpha$   Premissa   2.     $\neg \alpha \left(\mathrm {c} \right)$   Hipótese ${\mathcal {E}}\exists$     3.       $\forall x\alpha$   Hipótese 4.       $\alpha \left(\mathrm {c} \right)$   3 ${\mathcal {E}}\forall$ 5.       $\alpha \left(\mathrm {c} \right)\land \neg \alpha \left(\mathrm {c} \right)$   2,4 C 6.     $\neg \forall x\alpha$   3,5 RAA 7.   $\neg \forall x\alpha$   1,2-6 ${\mathcal {E}}\exists$

Aplicando o Intercâmbio de Quantificadores

Segue abaixo alguns exemplos que ilustram o quanto a regra de intercâmbio de quantificadores é útil.

Exemplo 1

$\vdash \exists x\left(Px\lor Qx\right)\to \left(\exists xPx\lor \exists xQx\right)$

01.     $\exists x\left(Px\lor Qx\right)$   Hipótese     02.       $\neg \left(\exists xPx\lor \exists xQx\right)$   Hipótese 03.       $\neg \exists xPx\land \neg \exists xQx$   2 DM 04.       $\neg \exists xPx$    3 S 05.       $\neg \exists xQx$    3 S 06.       $\forall x\neg Px$    4 IQ 07.       $\forall x\neg Qx$    5 IQ 08.       $\neg Pa$    6 ${\mathcal {E}}\forall$ 09.       $\neg Qa$    7 ${\mathcal {E}}\forall$ 10.       $\neg Pa\land \neg Qa$    8,9 C 11.       $\neg \left(Pa\lor Qa\right)$    10 DM 12.       $\forall x\neg \left(Px\lor Qx\right)$    11 ${\mathcal {I}}\forall$ 13.       $\neg \exists x\left(Px\lor Qx\right)$    12 IQ 14.       $\exists x\left(Px\lor Qx\right)\land \neg \exists x\left(Px\lor Qx\right)$    1,13 C 15.     $\neg \neg \left(\exists xPx\lor \exists xQx\right)$   2,14 RAA 16.     $\exists xPx\lor \exists xQx$   15 DN   17.   $\exists x\left(Px\lor Qx\right)\to \left(\exists xPx\lor \exists xQx\right)$   1,16 RPC

Exemplo 2

$\vdash \left(\exists xPx\lor \exists xQx\right)\to \exists x\left(Px\lor Qx\right)$

01.     $\exists xPx\lor \exists xQx$   Hipótese     02.       $\neg \exists x\left(Px\lor Qx\right)$         Hipótese 03.       $\forall x\neg \left(Px\lor Qx\right)$         2 IQ 04.       $\neg \left(Pa\lor Qa\right)$         3 ${\mathcal {E}}\forall$ 05.       $\neg Pa\land \neg Qa$         4 DM       06.         $\neg \exists xPx$   Hipótese 07.         $\exists xQx$   1,6 SD 08.         $\neg Qa$   5 S 09.         $\forall x\neg Qx$   8 ${\mathcal {I}}\forall$ 10.         $\neg \exists xQx$   9 IQ 11.         $\exists xQx\land \neg \exists xQx$   6,10 C         12.       $\neg \neg \exists xPx$   6,11 RAA 13.       $\exists xPx$   12 DN 14.       $\neg Pa$   5 S 15.       $\forall x\neg Px$   14 ${\mathcal {I}}\forall$ 16.       $\neg \exists xPx$   15 IQ 17.       $\exists xPx\land \neg \exists xPx$   13,16 C       18.     $\neg \neg \exists x\left(Px\lor Qx\right)$   2,17 RAA 19.     $\exists x\left(Px\lor Qx\right)$   18 DN   20.   $\left(\exists xPx\lor \exists xQx\right)\to \exists x\left(Px\lor Qx\right)$   1,19 RPC

Exemplo 3

$\left\{\forall x\left(Ax\to Bx\right),\forall x\left(Ax\to \neg Bx\right)\right\}\vdash \neg \exists Ax$

01.   $\forall x\left(Ax\to Bx\right)$   Premissa 02.   $\forall x\left(Ax\to \neg Bx\right)$   Premissa   03.     $Ad$   Hipótese 04.     $Ad\to Bd$   1 ${\mathcal {E}}\forall$ 05.     $Ad\to \neg Bd$   4 ${\mathcal {E}}\forall$ 06.     $Bd$   3,4 MP 07.     $\neg Bd$   3,5 MP 08.     $Bd\land \neg Bd$   6,7 C 09.   $\neg Ad$   3,8 RAA 10.   $\forall x\neg Ax$   9 ${\mathcal {I}}\forall$ 11.   $\neg \exists xAx$   10 IQ

Exercícios

Prove os seguintes teoremas:

1. $\vdash \exists xPx\to \neg \forall x\neg Px$
2. $\vdash \forall x\left(Px\to Q\right)\to \exists x\left(Px\to Q\right)$
3. $\vdash \exists x\exists yPxy\leftrightarrow \exists y\exists xPxy$
4. $\vdash \left(\forall xPx\land \forall xQx\right)\leftrightarrow \forall x\left(Px\land Qx\right)$
5. $\vdash \left(P\land \exists xQx\right)\leftrightarrow \exists x\left(P\land Qx\right)$
6. $\vdash \left(P\lor \forall xQx\right)\leftrightarrow \forall x(P\lor Qx)$
7. $\vdash \exists x(Px\rightarrow Q)\to (\forall xPx\rightarrow Q)$

Confira aqui as respostas

Esta página foi eleita pelos colaboradores como uma das melhores do Wikilivros. Para mais informações, consulte a página de votações.