Generalización universal

Reglas de transformación
Cálculo proposicional
Reglas de inferencia
Introducción  / eliminación de implicaciones ( modus ponens ) Introducción  / eliminación bicondicional Introducción  / eliminación de conjunción Introducción  / eliminación de disyunción Silogismo disyuntivo  / hipotético Dilema constructivo  / destructivo Absorción  / modus tollens  / modus ponendo tollens Introducción a la negación
Reglas de reemplazo
Asociatividad Conmutatividad Distributividad Doble negación Leyes de de Morgan Transposición Implicación material Exportación Tautología
Lógica de predicados
Reglas de inferencia
Generalización  / instanciación universal Generalización existencial  / instanciación
v t mi

En la lógica de predicados , la generalización (también generalización universal o introducción universal , ^{[1] [2] [3]} GEN ) es una regla de inferencia válida . Afirma 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. Suponga que es un conjunto de fórmulas, una fórmula y se ha derivado. La regla de generalización establece que se puede derivar si no se menciona y no ocurre 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 defectuosa)

Esto pretende mostrar lo que es una deducción errónea. Tenga en cuenta que está permitido si no se menciona en ( no es necesario que se aplique la segunda restricción, ya que la estructura semántica de no se modifica mediante 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 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:

Número	Fórmula	Justificación
1	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$	Hipótesis
2	${\displaystyle \forall x\,P(x)}$	Hipótesis
3	${\displaystyle (\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y)))}$	Instanciación universal
4	${\displaystyle P(y)\rightarrow Q(y)}$	De (1) y (3) de Modus ponens
5	${\displaystyle (\forall x\,P(x))\rightarrow P(y)}$	Instanciación universal
6	${\displaystyle P(y)\ }$	De (2) y (5) por Modus ponens
7	${\displaystyle Q(y)\ }$	De (6) y (4) de Modus ponens
8	${\displaystyle \forall x\,Q(x)}$	De (7) por generalización
9	${\displaystyle \forall x\,(P(x)\rightarrow Q(x)),\forall x\,P(x)\vdash \forall x\,Q(x)}$	Resumen de (1) a (8)
10	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\vdash \forall x\,P(x)\rightarrow \forall x\,Q(x)}$	De (9) por teorema de deducción
11	${\displaystyle \vdash \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$	De (10) por el teorema de deducción

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

Ver también

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

Referencias

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