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{\mathrm{\forall }x(\alpha )}{\alpha [x/\mathrm{c}]}$

Ou seja, dada uma fórmula $\mathrm{\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

$\{\mathrm{\forall }x(Hx\to Mx),Hs\}⊢Ms$

1.   $\mathrm{\forall }x(Hx\to Mx)$   Premissa 2.   $Hs$   Premissa 3.   $Hs\to Ms$   1 $ℰ\mathrm{\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 $\mathrm{\forall }xHx\to Ms$ .

Introdução do Universal

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

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 $\mathrm{\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

$\{\mathrm{\forall }x(Ax\to Bx),\mathrm{\forall }x(Bx\to Cx)\}⊢\mathrm{\forall }x(Ax\to Cx)$

1.   $\mathrm{\forall }x(Ax\to Bx)$   Premissa 2.   $\mathrm{\forall }x(Bx\to Cx)$   Premissa 3.   $Ac\to Bc$   1 $ℰ\mathrm{\forall }$ 4.   $Bc\to Cc$   2 $ℰ\mathrm{\forall }$ 5.   $Ac\to Cc$   3,4 SH 6.   $\mathrm{\forall }x(Ax\to Cx)$   5 $ℐ\mathrm{\forall }$

• Exemplo 2

$\mathrm{\forall }x\mathrm{\forall }yPxy⊢\mathrm{\forall }y\mathrm{\forall }xPyx$

1.   $\mathrm{\forall }x\mathrm{\forall }yPxy$   Premissa 2.   $\mathrm{\forall }xPxb$   1 $ℰ\mathrm{\forall }$ 3.   $Pab$   2 $ℰ\mathrm{\forall }$ 4.   $\mathrm{\forall }xPax$   3 $ℐ\mathrm{\forall }$ 5.   $\mathrm{\forall }y\mathrm{\forall }xPyx$   4 $ℐ\mathrm{\forall }$

• CUIDADO

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

1.   $Lf$   Premissa 2.   $\mathrm{\forall }xLx$   1 $ℐ\mathrm{\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.   $\mathrm{\forall }x\mathrm{\exists }yAxy$   Premissa 2.   $\mathrm{\exists }yAby$   1 $ℰ\mathrm{\forall }$ 3.   $\mathrm{\forall }y\mathrm{\exists }yAyy$   2 $ℐ\mathrm{\forall }$

Introdução do Existencial

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

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 $\mathrm{\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

$\mathrm{\forall }xPx⊢\mathrm{\exists }xPx$

1.   $\mathrm{\forall }xPx$   Premissa 2.   $Pa$   1 $ℰ\mathrm{\forall }$ 3.   $\mathrm{\exists }xPx$   2 $ℐ\mathrm{\exists }$

• Exemplo 2

$Ac\wedge La⊢\mathrm{\exists }xAx\wedge \mathrm{\exists }yLy$

1.   $Ac\wedge La$   Premissa 2.   $Ac$   1 S 3.   $\mathrm{\exists }xAx$   2 $ℐ\mathrm{\exists }$ 4.   $La$   1 S 5.   $\mathrm{\exists }yLy$   4 $ℐ\mathrm{\exists }$ 6.   $\mathrm{\exists }xAx\wedge \mathrm{\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\wedge La$   Premissa 2.   $\mathrm{\exists }x(Ax\wedge Lx)$   1 $ℐ\mathrm{\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 $\mathrm{\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

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

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

• Exemplo 2

$\{\mathrm{\forall }x(Ax\to Bx),\mathrm{\neg }\mathrm{\exists }(Bx\wedge Cx)\}⊢\mathrm{\neg }\mathrm{\exists }x(Ax\wedge Cx)$

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

Exercício

Demonstre:

1. $\{\mathrm{\forall }x(Px\vee Qx),\mathrm{\neg }Qa\}⊢Pa$
2. $\{\mathrm{\forall }x(Ax\wedge Bx),\mathrm{\forall }x(Cx\wedge Dx)\}⊢\mathrm{\forall }x(Ax\wedge Cx)$
3. $\{\mathrm{\forall }x(Ax\to Bx),Al\}⊢\mathrm{\exists }xBx$
4. $\mathrm{\exists }x(Px\wedge Qx)⊢\mathrm{\exists }xPx\wedge \mathrm{\exists }xQx$
5. $\{\mathrm{\exists }xPx,\mathrm{\forall }xQx\}⊢\mathrm{\exists }x(Px\wedge Qx)$

Confira aqui as respostas

Regras Derivadas para Quantificadores

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

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

Vamos provar cada caso deste regra:

Intercâmbio de Quantificadores 1

$\mathrm{\forall }x\mathrm{\neg }\alpha ⊢\mathrm{\neg }\mathrm{\exists }x\alpha$

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

Intercâmbio de Quantificadores 2

$\mathrm{\neg }\mathrm{\exists }x\alpha ⊢\mathrm{\forall }x\mathrm{\neg }\alpha$

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

Intercâmbio de Quantificadores 3

$\mathrm{\neg }\mathrm{\forall }x\alpha ⊢\mathrm{\exists }x\mathrm{\neg }\alpha$

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

Intercâmbio de Quantificadores 4

$\mathrm{\exists }x\mathrm{\neg }\alpha ⊢\mathrm{\neg }\mathrm{\forall }x\alpha$

1.   $\mathrm{\exists }x\mathrm{\neg }\alpha$   Premissa   2.     $\mathrm{\neg }\alpha \left(\mathrm{c}\right)$   Hipótese $ℰ\mathrm{\exists }$     3.       $\mathrm{\forall }x\alpha$   Hipótese 4.       $\alpha \left(\mathrm{c}\right)$   3 $ℰ\mathrm{\forall }$ 5.       $\alpha \left(\mathrm{c}\right)\wedge \mathrm{\neg }\alpha \left(\mathrm{c}\right)$   2,4 C 6.     $\mathrm{\neg }\mathrm{\forall }x\alpha$   3,5 RAA 7.   $\mathrm{\neg }\mathrm{\forall }x\alpha$   1,2-6 $ℰ\mathrm{\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

$⊢\mathrm{\exists }x(Px\vee Qx)\to (\mathrm{\exists }xPx\vee \mathrm{\exists }xQx)$

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

Exemplo 2

$⊢(\mathrm{\exists }xPx\vee \mathrm{\exists }xQx)\to \mathrm{\exists }x(Px\vee Qx)$

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

Exemplo 3

$\{\mathrm{\forall }x(Ax\to Bx),\mathrm{\forall }x(Ax\to \mathrm{\neg }Bx)\}⊢\mathrm{\neg }\mathrm{\exists }Ax$

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

Exercícios

Prove os seguintes teoremas:

1. $⊢\mathrm{\exists }xPx\to \mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }Px$
2. $⊢\mathrm{\forall }x(Px\to Q)\to \mathrm{\exists }x(Px\to Q)$
3. $⊢\mathrm{\exists }x\mathrm{\exists }yPxy\leftrightarrow \mathrm{\exists }y\mathrm{\exists }xPxy$
4. $⊢(\mathrm{\forall }xPx\wedge \mathrm{\forall }xQx)\leftrightarrow \mathrm{\forall }x(Px\wedge Qx)$
5. $⊢(P\wedge \mathrm{\exists }xQx)\leftrightarrow \mathrm{\exists }x(P\wedge Qx)$
6. $⊢(P\vee \mathrm{\forall }xQx)\leftrightarrow \mathrm{\forall }x(P\vee Qx)$
7. $⊢\mathrm{\exists }x(Px\to Q)\to (\mathrm{\forall }xPx\to Q)$

Confira aqui as respostas