2.4: Reglas de inferencia

Habiendo establecido nuestro conjunto\(\Lambda\) de axiomas lógicos, ahora debemos fijar nuestras reglas de inferencia. Habrá dos tipos de reglas, una que se ocupará de la consecuencia proposicional y otra que se ocupará de los cuantificadores.

Consecuencia proposicional

Con toda probabilidad estás familiarizado con las tautologías de la lógica proposicional. Simplemente son fórmulas como\(\left( A \rightarrow B \right) \leftrightarrow \left( \neg B \rightarrow \neg A \right)\). Si te sientes cómodo con las tautologías, no dudes en saltarte los siguientes párrafos. Si no, lo que sigue es una revisión muy breve de una parte de la lógica proposicional.

Trabajamos con un lenguaje restringido\(\mathcal{P}\), que consiste únicamente en un conjunto de variables proposicionales\(A, B, C, \ldots\) y los conectivos\(\lor\) y\(\neg\). Observe que no hay cuantificadores, no hay símbolos de relación, no hay símbolos de función y no hay constantes. Las fórmulas de lógica proposicional se definen como el conjunto de todos los\(\phi\) tales que o bien\(\phi\) es una variable proposicional, o\(\phi\) es\(\left( \neg \alpha \right)\), o\(\phi\) es\(\left( \alpha \lor \beta \right)\), con\(\alpha\) y\(\beta\) siendo fórmulas de lógica proposicional.

A cada variable proposicional se le puede asignar uno de dos valores de verdad,\(T\) o\(F\), correspondientes a verdad o falsedad. Dada tal asignación (que es realmente una función\(v \: : \: \text{propositional variables} \rightarrow \{T, F\}\)), podemos extender\(v\) a una función\(\bar{v}\) asignando un valor de verdad a cualquier fórmula proposicional de la siguiente manera:

\[\bar{v} \left( \phi \right) \begin{cases} \begin{array}{ll} v \left( \phi \right) & \text{if} \: \phi \: \text{is a propositional variable} \\ F & \text{if} \: \phi : \equiv \left( \neg \alpha \right) \: \text{and} \bar{v} \left( \alpha \right) = T \\ F & \text{if} \: \phi : \equiv \left( \alpha \lor \beta \right) \: \text{and} \: \bar{v} \left( \alpha \right) = \bar{v} \left( \beta \right) = F \\ T & \text{otherwise} \end{array} \end{cases}\]

Ahora decimos que una fórmula proposicional\(\phi\) es una tautología si y sólo si\(\bar{v} \left( \phi \right) = T\) para alguna asignación de verdad\(v\).

Una forma de verificar si un dado\(\phi\) es una tautología es construyendo una tabla de verdad con una fila para cada posible combinación de valores de verdad para las variables proposicionales que ocurren en\(\phi\). Entonces rellenas la tabla de verdad y ves si el valor de verdad asociado con el conectivo principal es siempre verdadero. Por ejemplo, considere la fórmula proposicional\(A \rightarrow \left( B \rightarrow A \right)\), que se traduce a\(\neg A \lor \left( \neg B \lor A \right)\). La tabla de verdad verificando que esta fórmula es una tautología es

\[\begin{array}{cc|c||c||ccc} A & B & \neg A & \lor & (\neg B & \lor & A) \\ \hline T & T & F & T & F & T & T \\ T & F & F & T & T & T & T \\ F & T & T & T & F & F & F \\ F & F & T & T & T & T & F \end{array}\]

Para discutir las consecuencias proposicionales en la lógica de primer orden, trasladaremos nuestras fórmulas al ámbito de la lógica proposicional y utilizaremos la idea de tautología en esa área. Para ser específicos, dada\(\beta\), una\(\mathcal{L}\) fórmula -de lógica de primer orden, aquí hay un procedimiento que se convertirá\(\beta\) en una fórmula\(\beta_P\) de lógica proposicional correspondiente a\(\beta\):

1. Encuentra todas las subfórmulas\(\beta\) de la forma\(\forall x \alpha\) que no estén en el alcance de otro cuantificador. Sustituirlos por variables proposicionales de manera sistemática. Esto significa que si\(\forall y Q \left( y, c \right)\) aparece dos veces en\(\beta\), se reemplaza por la misma letra ambas veces, y las subfórmulas distintas se reemplazan por letras distintas.
2. Encontrar todas las fórmulas atómicas que quedan, y reemplazarlas sistemáticamente con nuevas variables proposicionales.
3. En este punto,\(\beta\) habrá sido sustituido por una fórmula proposicional\(\beta_P\).

Por ejemplo, supongamos que miramos la\(\mathcal{L}\) fórmula -

\[\left( \forall x P \left( x \right) \land Q \left( c, z \right) \right) \rightarrow \left( Q \left( c, z \right) \lor \forall x P \left( x \right) \right).\]

Para el primer paso del procedimiento anterior, sustituimos las subfórmulas cuantificadas por la letra proposicional\(B\):

\[\left( B \land Q \left( c, z \right) \right) \rightarrow \left( Q \left( c, z \right) \lor B \right).\]

Para terminar la transformación a una fórmula proposicional, reemplace la fórmula atómica por una letra proposicional:

\[\left( B \land A \right) \rightarrow \left( A \lor B \right).\]

Observe que si\(\beta_P\) es una tautología, la\(\beta\) es válida, pero lo contrario de esta afirmación falla. Por ejemplo, si\(\beta\) es

\[\left[ \left( \forall x \right) \left( \theta \right) \land \left( \forall x \right) \left( \theta \rightarrow \rho \right) \right] \rightarrow \left( \forall x \right) \left( \rho \right),\]

entonces\(\beta\) es válido, pero lo\(\beta_P\) sería\(\left[ A \land B \right] \rightarrow C\), lo que ciertamente no es una tautología.

Ahora estamos casi en un punto en el que podemos exponer nuestra regla proposicional de inferencia. Recordemos que una regla de inferencia es un par ordenado\(\left( \Gamma, \phi \right)\), donde\(\Gamma\) es un conjunto de\(\mathcal{L}\) -fórmulas y\(\phi\) es una\(\mathcal{L}\) -fórmula.

Definición 2.4.1. Supongamos que\(\Gamma_P\) es un conjunto de fórmulas proposicionales y\(\phi_P\) es una fórmula proposicional. Vamos a decir que\(\phi_P\) es una consecuencia proposicional de\(\Gamma_P\) si toda asignación de verdad que hace realidad cada fórmula proposicional en\(\Gamma_P\) verdad también hace\(\phi_P\) realidad. Observe que\(\phi_P\) es una tautología si y sólo si\(\phi_P\) es una consecuencia proposicional de\(\emptyset\).

Lema 2.4.2. Si\(\Gamma_P = \{ \gamma_{1 \: P}, \gamma_{2 \: P}, \ldots, \gamma_{n \: P} \}\) es un conjunto finito no vacío de fórmulas proposicionales y\(\phi_P\) es una fórmula proposicional, entonces\(\phi_P\) es una consecuencia proposicional de\(\Gamma_P\) si y solo si

\[\left[ \gamma_{1 \: P} \land \gamma_{2 \: P} \land \cdots \land \gamma_{n \: P} \right] \rightarrow \phi_P\]

es una tautología.

Comprobante. Ejercicio 3.

Ahora ampliamos nuestra definición de consecuencia proposicional para incluir fórmulas de lógica de primer orden:

Definición 2.4.3. Supongamos que\(\Gamma\) es un conjunto finito de\(\mathcal{L}\) -fórmulas y\(\phi\) es una\(\mathcal{L}\) -fórmula. Diremos que\(\phi\) es una consecuencia proposicional de\(\Gamma\) si\(\phi_P\) es una consecuencia proposicional de\(\Gamma_P\), dónde\(\phi_P\) y\(\Gamma_P\) son los resultados de aplicar el procedimiento anterior de manera uniforme a\(\phi\) y todas las fórmulas en\(\Gamma\).

Ejemplo 2.4.4. Supongamos que\(\mathcal{L}\) contiene dos símbolos de relación unaria,\(P\) y\(Q\). Deja\(\Gamma\) ser el conjunto

\[\{ \forall x P \left( x \right) \rightarrow \exists y Q \left( y \right), \exists y Q \left( y \right) \rightarrow P \left( x \right), \neg P \left( x \right) \leftrightarrow \left( y = z \right) \}.\]

Si dejamos\(\phi\) ser la fórmula\(\forall x P \left( x \right) \rightarrow \neg \left( y = z \right)\), entonces aplicando nuestro procedimiento de manera uniforme a los elementos de\(\Gamma\) y\(\phi\), vemos eso.

\[\Gamma_P \: \text{is} \: \{ A \rightarrow B, B \rightarrow C, \neg C \leftrightarrow D \}\]

y\(\phi_P\) es\(A \rightarrow \neg D\), donde el hecho de que hayamos sustituido las mismas variables proposicionales por las mismas fórmulas en\(\phi\) y los elementos de\(\Gamma\) se asegura aplicando el procedimiento de manera uniforme a todas las fórmulas en cuestión. En este punto es fácil verificar que\(\phi\) es una consecuencia proposicional de\(\Gamma\).

Por último, nuestra regla de inferencia:

Definición 2.4.5. Si\(\Gamma\) es un conjunto finito de\(\mathcal{L}\) -fórmulas,\(\phi\) es una\(\mathcal{L}\) -fórmula, y\(\phi\) es una consecuencia proposicional de\(\Gamma\), entonces\(\left( \Gamma, \phi \right)\) es una regla de inferencia de tipo (PC).

Chaff:Todo este formalismo podría estar ocultando lo que realmente está pasando aquí. Lo que dice la regla (PC) es que si has probado\(\gamma_1\)\(\gamma_2\) y y\(\left[ \left( \gamma_1 \land \gamma_2 \right) \rightarrow \phi \right]_P\) es una tautología, entonces puedes concluir\(\phi\). Nada más elegante que eso.

También notar que si\(\phi\) es una fórmula tal que\(\phi_P\) es una tautología, regla (PC) nos permite hacer valer\(\phi\) en cualquier deducción, utilizando\(\Gamma = \emptyset\).

Reglas del cuantificador

La motivación detrás de nuestras reglas de cuantificador es muy simple. Supongamos, sin hacer suposiciones particulares al respecto\(x\), que se pudo demostrar que "\(x\)es un varvark ambicioso”. Entonces parece razonable afirmar que has demostrado "\(\left( \forall x \right) x\)es un varvark ambicioso”. Dualmente, si pudieras probar la Hipótesis de Riemann a partir de la suposición de que "\(x\)es una rana toro mandona”, entonces desde la suposición "\(\left( \exists x \right) x\)es una rana toro mandona”, aún deberías poder probar la Hipótesis de Riemann.

Definición 2.4.6. Supongamos que la variable no\(x\) está libre en la fórmula\(\psi\). Entonces ambas de las siguientes son reglas de inferencia de tipo (QR):

\[\left( \{ \psi \rightarrow \phi \}, \psi \rightarrow \left( \forall x \phi \right) \right)\]

\[\left( \{ \phi \rightarrow \psi \}, \left( \exists x \phi \right) \rightarrow \psi \right).\]

El comentario de “no hacer suposiciones particulares sobre\(x\)" se hace formal por el requisito de que\(x\) no sean libres en\(\psi\).

Chaff:Sólo para asegurarse de que no se pierde entre los paréntesis de la definición, lo que estamos diciendo aquí es que si no\(x\) es libre en\(\psi\):

1. De la fórmula\(\psi \rightarrow \phi\), se puede deducir\(\psi \rightarrow \left( \forall x \phi \right)\).
2. De la fórmula\(\phi \rightarrow \psi\), se puede deducir\(\left( \exists x \phi \right) \rightarrow \psi\).

Ejercicios

1. Afirmamos que la colección\(\Lambda\) de axiomas lógicos es decidible. Esbozar un algoritmo que, dada una\(\mathcal{L}\) -fórmula\(\theta\), genera “sí” si\(\theta\) es un elemento de\(\Lambda\) y emite “no” si no\(\theta\) es un elemento de\(\Lambda\). No tienes que ser demasiado quisquilloso. Observe que tiene que ser capaz de decidir si un término\(t\) es sustituible por una variable\(x\) en una fórmula\(\phi\). Ver Ejercicio 7 en la Sección 1.8.
2. Demostrar que el conjunto de reglas de inferencia es decidible. Entonces delinear un algoritmo que decidirá, dado un conjunto finito de fórmulas\(\Gamma\) y una fórmula\(\theta\), si\(\left( \Gamma, \theta \right)\) es o no una regla de inferencia.
3. Demostrar Lema 2.4.2.
4. Escribir una deducción del axioma del segundo cuantificador (Q2) sin usar (Q2) como axioma.
5. Para cada una de las siguientes, decida si\(\phi\) es una consecuencia proposicional de\(\Gamma\) y justifique su aseveración.
   (a)\(\Gamma\) es\(\{ \left( \forall P \left( x \right) \right) \rightarrow Q \left( y \right), \left( \forall x P \left( x \right) \right) \lor \left( \forall x R \left( x \right) \right), \exists x \neg R \left( x \right) \}\);\(\phi\) es\(Q \left( y \right)\).
   b)\(\Gamma\) es\(\{ x = y \land Q \left( y \right), Q \left( y \right) \lor x + y < z \}\);\(\phi\) es\(x + y < z\).
   (c)\(\Gamma\) es\(\{ P \left( x, y, x \right), x < y \lor M \left( w, p \right), \left( \neg P \left( x, y, x \right) \right) \land \left( \neg x < y \right) \}\);\(\phi\) es\(\neg M \left( w, p \right)\).
6. Demostrar que si no\(\theta\) es válido, entonces no\(\theta_P\) es una tautología. Deducir que si\(\theta_P\) es una tautología, entonces\(\theta\) es válido.