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

Origem: Wikilivros, livros abertos por um mundo aberto.

< Lógica | Cálculo Quantificacional Clássico

acima: Voltar para o Índice de Cálculo Quantificacional Clássico
anterior: Tablôs Semânticos no CQC | próximo: Identidade e Símbolos Funcionais

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.

[editar] 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 \,\!$ .

[editar] 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 x Hx\to Ms$ .

[editar] 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 y Pxy \vdash \forall y \forall x Pyx$

1.	$\forall x \forall y Pxy\,\!$	Premissa
2.	$\forall x Pxb\,\!$	1 $\mathcal{E}\forall$
3.	$Pab\,\!$	2 $\mathcal{E}\forall$
4.	$\forall x Pax\,\!$	3 $\mathcal{I}\forall$
5.	$\forall y\forall x Pyx\,\!$	4 $\mathcal{I}\forall$

CUIDADO

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

1.		$Lf\,\!$		Premissa
2.		$\forall x Lx\,\!$		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 y Axy\,\!$	Premissa
2.	$\exists y Aby\,\!$	1 $\mathcal{E}\forall$
3.	$\forall y\exists y Ayy\,\!$	2 $\mathcal{I}\forall$

[editar] 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 x Px \vdash \exists x Px$

1.	$\forall x Px$	Premissa
2.	$Pa\,\!$	1 $\mathcal{E}\forall$
3.	$\exists x Px \,\!$	2 $\mathcal{I}\exists$

Exemplo 2

$Ac \land La \vdash \exists x Ax \land \exists y Ly$

1.	$Ac \land La\,\!$	Premissa
2.	$Ac \,\!$	1 S
3.	$\exists x Ax \,\!$	2 $\mathcal{I}\exists$
4.	$La \,\!$	1 S
5.	$\exists y Ly \,\!$	4 $\mathcal{I}\exists$
6.	$\exists x Ax \land \exists y Ly\,\!$	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.

[editar] 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 x Px , \left(\exists x \neg \neg Px\right)\to Qb\right\} \vdash Qb$

1.	$\exists x Px$	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

[editar] 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 x Bx$
$\exists x \left(Px \land Qx\right) \vdash \exists x Px \land \exists x Qx$
$\left\{\exists x Px , \forall x Qx \right\}\vdash \exists x \left(Px \land Qx\right)$

Confira aqui as respostas

[editar] 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:

[editar] 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

[editar] 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$

[editar] 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

[editar] 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$

[editar] Aplicando o Intercâmbio de Quantificadores

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

[editar] Exemplo 1

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

01.			$\exists x\left(Px\lor Qx\right)\,\!$		Hipótese

02.	$\neg \left(\exists x Px\lor \exists x Qx\right)\,\!$	Hipótese
03.	$\neg \exists x Px\land \neg \exists x Qx\,\!$	2 DM
04.	$\neg \exists x Px\,\!$	3 S
05.	$\neg \exists x Qx\,\!$	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 x Px\lor \exists x Qx\right)\,\!$	2,14 RAA
16.	$\exists x Px\lor \exists x Qx\,\!$	15 DN

17.

$\exists x\left(Px\lor Qx\right)\to \left(\exists x Px\lor \exists x Qx\right)\,\!$

1,16 RPC

[editar] Exemplo 2

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

01.			$\exists x Px\lor \exists x Qx \,\!$		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 x Px \,\!$	Hipótese
07.	$\exists x Qx\,\!$	1,6 SD
08.	$\neg Qa \,\!$	5 S
09.	$\forall x\neg Qx\,\!$	8 $\mathcal{I}\forall$
10.	$\neg \exists x Qx\,\!$	9 IQ
11.	$\exists x Qx\land \neg \exists x Qx\,\!$	6,10 C

12.	$\neg \neg \exists x Px\,\!$	6,11 RAA
13.	$\exists x Px\,\!$	12 DN
14.	$\neg Pa\,\!$	5 S
15.	$\forall x\neg Px\,\!$	14 $\mathcal{I}\forall$
16.	$\neg \exists x Px\,\!$	15 IQ
17.	$\exists x Px\land \neg \exists x Px\,\!$	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 x Px\lor \exists x Qx\right)\to \exists x\left(Px\lor Qx\right)$

1,19 RPC

[editar] 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 x Ax\,\!$	10 IQ

[editar] Exercícios

Prove os seguintes teoremas:

$\vdash \exists x Px\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 y Pxy \leftrightarrow \exists y \exists x Pxy$
$\vdash \left(\forall x Px \land \forall x Qx\right) \leftrightarrow \forall x \left(Px \land Qx\right)$
$\vdash \left(P \land \exists x Qx\right) \leftrightarrow \exists x \left(P \land Qx\right)$
$\vdash \left(P \lor \forall x Qx\right) \leftrightarrow \forall x (P \lor Qx)$
$\vdash \exists x (Px \rightarrow Q) \to (\forall x Px \rightarrow Q)$