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 $⊢P(x)$ foi deduzido, então $⊢\mathrm{\forall }xP(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 $\mathrm{\Gamma }⊢\phi (y)$  foi deduzido. A regra da Generalização diz que $\mathrm{\Gamma }⊢\mathrm{\forall }x\phi (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 $\mathrm{\forall }xP(x)$ da hipótese $P(y)$. Sem a segunda restrição, pode-se fazer a seguinte dedução:

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

Isso supostamente mostra que $\mathrm{\exists }z\mathrm{\exists }w(z=w)⊢\mathrm{\forall }x(x=x),$ que é uma dedução incorreta.

Exemplo de uma prova

Provar: $\mathrm{\forall }x(P(x)\to Q(x))\to (\mathrm{\forall }xP(x)\to \mathrm{\forall }xQ(x))$.

Prova:

Number	Formula	Justification
1	$\mathrm{\forall }x(P(x)\to Q(x))$	Hipótese
2	$\mathrm{\forall }xP(x)$	Hipótese
3	$(\mathrm{\forall }x(P(x)\to Q(x)))\to (P(y)\to Q(y)))$	Instanciação universal
4	$P(y)\to Q(y)$	De (1) e (3) por Modus ponens
5	$(\mathrm{\forall }xP(x))\to 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	$\mathrm{\forall }xQ(x)$	De (7) by Generalização
9	$\mathrm{\forall }x(P(x)\to Q(x)),\mathrm{\forall }xP(x)⊢\mathrm{\forall }xQ(x)$	Resumo de (1) à (8)
10	$\mathrm{\forall }x(P(x)\to Q(x))⊢\mathrm{\forall }xP(x)\to \mathrm{\forall }xQ(x)$	De (9) por Teorema da dedução
11	$⊢\mathrm{\forall }x(P(x)\to Q(x))\to (\mathrm{\forall }xP(x)\to \mathrm{\forall }xQ(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