Generalização universal

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

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

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

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

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

Prova:

Number	Formula	Justification
1	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$	Hipótese
2	${\displaystyle \forall x\,P(x)}$	Hipótese
3	${\displaystyle (\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y)))}$	Instanciação universal
4	${\displaystyle P(y)\rightarrow Q(y)}$	De (1) e (3) por Modus ponens
5	${\displaystyle (\forall x\,P(x))\rightarrow P(y)}$	Instanciação universal
6	${\displaystyle P(y)\ }$	De (2) e (5) por Modus ponens
7	${\displaystyle Q(y)\ }$	De (6) e (4) por Modus ponens
8	${\displaystyle \forall x\,Q(x)}$	De (7) by Generalização
9	${\displaystyle \forall x\,(P(x)\rightarrow Q(x)),\forall x\,P(x)\vdash \forall x\,Q(x)}$	Resumo de (1) à (8)
10	${\displaystyle \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	${\displaystyle \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.

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