Generalización universal

Regla de inferencia en lógica de predicados

En lógica de predicados , la generalización (también generalización universal , introducción universal , ^{[1] [2] [3]} GEN , UG ) es una regla de inferencia válida . Establece que si se ha derivado, entonces se puede derivar. ${\displaystyle \vdash \!P(x)}$ ${\displaystyle \vdash \!\forall x\,P(x)}$

Generalización con hipótesis

La regla de generalización completa permite hipótesis a la izquierda del torniquete , pero con restricciones. Supongamos que es un conjunto de fórmulas, se ha derivado una fórmula y . La regla de generalización establece que se puede derivar si no se menciona en y no aparece en . ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma \vdash \varphi (y)}$ ${\displaystyle \Gamma \vdash \forall x\,\varphi (x)}$ ${\displaystyle y}$ ${\displaystyle \Gamma }$ ${\displaystyle x}$ ${\displaystyle \varphi }$

Estas restricciones son necesarias para la solidez. Sin la primera restricción, se podría concluir a partir de la hipótesis . Sin la segunda restricción, se podría hacer la siguiente deducción: ${\displaystyle \forall xP(x)}$ ${\displaystyle P(y)}$

1. ${\displaystyle \exists z\,\exists w\,(z\not =w)}$(Hipótesis)
2. ${\displaystyle \exists w\,(y\not =w)}$(Instanciación existencial)
3. ${\displaystyle y\not =x}$(Instanciación existencial)
4. ${\displaystyle \forall x\,(x\not =x)}$(Generalización universal errónea)

Esto pretende demostrar que se trata de una deducción errónea. Nótese que es permisible si no se menciona en (la segunda restricción no se aplica necesariamente, ya que la estructura semántica de no se modifica con la sustitución de ninguna variable). ${\displaystyle \exists z\,\exists w\,(z\not =w)\vdash \forall x\,(x\not =x),}$ ${\displaystyle \Gamma \vdash \forall y\,\varphi (y)}$ ${\displaystyle y}$ ${\displaystyle \Gamma }$ ${\displaystyle \varphi (y)}$

Ejemplo de una prueba

Demuestre: es derivable de y . ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$ ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$ ${\displaystyle \forall x\,P(x)}$

Prueba:

En esta prueba, se utilizó la generalización universal en el paso 8. El teorema de deducción fue aplicable en los pasos 10 y 11 porque las fórmulas que se están moviendo no tienen variables libres.

Véase también

• Lógica de primer orden
• Generalización apresurada
• Instanciación universal

Referencias

1. Copi y Cohen
2. Hurley
3. Moore y Parker