# 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:
* a constante $\mathrm {c}$ não pode ocorrer em premissa ou hipótese vigente.
* $\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:
* $\left\{\forall x\left(Px\lor Qx\right),\neg Qa\right\}\vdash Pa$
* $\left\{\forall x\left(Ax\land Bx\right),\forall x\left(Cx\land Dx\right)\right\}\vdash \forall x\left(Ax\land Cx\right)$
* $\left\{\forall x\left(Ax\to Bx\right),Al\right\}\vdash \exists xBx$
* $\exists x\left(Px\land Qx\right)\vdash \exists xPx\land \exists xQx$
* $\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:
* $\vdash \exists xPx\to \neg \forall x\neg Px$
* $\vdash \forall x\left(Px\to Q\right)\to \exists x\left(Px\to Q\right)$
* $\vdash \exists x\exists yPxy\leftrightarrow \exists y\exists xPxy$
* $\vdash \left(\forall xPx\land \forall xQx\right)\leftrightarrow \forall x\left(Px\land Qx\right)$
* $\vdash \left(P\land \exists xQx\right)\leftrightarrow \exists x\left(P\land Qx\right)$
* $\vdash \left(P\lor \forall xQx\right)\leftrightarrow \forall x(P\lor Qx)$
* $\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.