Generalização universal

Na lógica de predicados, generalização (também generalização universal ou introdução universal, GEN) é uma regra de inferência valida. Ela afirma que se $\vdash P(x)$ foi deduzido, então $\vdash \forall x\,P(x)$  pode ser deduzido.

Generalização com hipóteses

A regra da generalização completa permite hipóteses à esquerda da Catraca(simbolo), porém com restrições. Assuma que Γ é um conjunto de fórmulas, φ uma fórmula, e $\Gamma \vdash \varphi (y)$  foi deduzido. A regra da Generalização diz que $\Gamma \vdash \forall x\varphi (x)$ pode ser deduzido se y não é mencionado em  Γ e x não ocorre em  φ.

Essas restrições são necessárias devido à correção. Sem a primeira restrição pode-se concluir $\forall xP(x)$ da hipótese $P(y)$. Sem a segunda restrição, pode-se fazer a seguinte dedução:

1. $\exists z\exists w(z\not =w)$ (Hipótese)
2. $\exists w(y\not =w)$ (Instanciação existencial)
3. $y\not =x$ (Instanciação existencial)
4. $\forall x(x\not =x)$ (Generalização universal defeituosa)

Isso supostamente mostra que $\exists z\exists w(z\not =w)\vdash \forall x(x\not =x),$ que é uma dedução incorreta.

Exemplo de uma prova

Provar: $\forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))$.

Prova:

Number	Formula	Justification
1	$\forall x\,(P(x)\rightarrow Q(x))$	Hipótese
2	$\forall x\,P(x)$	Hipótese
3	$(\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y)))$	Instanciação universal
4	$P(y)\rightarrow Q(y)$	De (1) e (3) por Modus ponens
5	$(\forall x\,P(x))\rightarrow P(y)$	Instanciação universal
6	$P(y)\$	De (2) e (5) por Modus ponens
7	$Q(y)\$	De (6) e (4) por Modus ponens
8	$\forall x\,Q(x)$	De (7) by Generalização
9	$\forall x\,(P(x)\rightarrow Q(x)),\forall x\,P(x)\vdash \forall x\,Q(x)$	Resumo de (1) à (8)
10	$\forall x\,(P(x)\rightarrow Q(x))\vdash \forall x\,P(x)\rightarrow \forall x\,Q(x)$	De (9) por Teorema da dedução
11	$\vdash \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))$	De (10) por Teorema da dedução

Nessa prova , a Generalização universal foi usada no passo 8. O Teorema da dedução era aplicável nos passos 10 e 11 porque as formulas sendo movidas não têm variáveis livres.

Veja também

• Lógica de primeira ordem
• Generalização precipitada
• Instanciação universal