Forma normal conjuntiva y demostración automática de teoremas

En los pocos libros de lógica que he hojeado o leído, los autores no llegan a explicar la importancia de las formas normales clausales (la normal conjuntiva y la normal disyuntiva), a pesar de que sí les dedican unas líneas a describirlas. Supongo que ha sido así porque son libros poco inclinados a la demostración automática de teoremas; por lo menos, la importancia de la forma normal conjuntiva radica ahí. Así que las siguientes líneas las dedico a establecer la conexión entre la forma normal conjuntiva y la demostración automática de teoremas.
     Para mostrar la relación entre la forma normal conjuntiva y la demostración automática de teoremas, haré lo siguiente: (1) calcular, salvo equivalencia lógica, el número total de proposiciones formadas a partir de otras; (2) describir la forma normal conjuntiva; (3) dar, salvo equivalencia lógica, formas explícitas de todas las proposiciones a partir de otras mediante una forma normal conjuntiva distinguida, y (4) dar expresiones explícitas de todas las proposiciones que son deducciones de un conjunto finito de axiomas.
     Calculemos, salvo equivalencia lógica, el número total de proposiciones a partir de otras. La totalidad de proposiciones que se pueden formar por combinación mediante los conectivos lógicos a partir de un número finito de proposiciones elementales $P_1,\ldots,P_n$ es, salvo equivalencia lógica, $2^{2^n}$. En efecto, para la verdad o falsedad de las proposiciones elementales hay $2^n$ posibilidades, puesto que cada $P_1,\ldots,P_n$ puede ser verdadera o falsa. La verdad o falsedad de una proposición compuesta por $P_1,\ldots,P_n$ está determinada por la verdad o falsedad de cada uno de los $2^n$ casos.
     Definamos y describamos las formas normales conjuntivas. Toda combinación de proposiciones formada mediante los conectivos lógicos (es decir, toda fórmula) se puede llevar a cierta forma normal a través de equivalencias lógicas. Esta forma normal consiste en una conjunción de disyunciones en las que cada componente es o una proposición elemental o la negación de una. Esto se puede hacer mediante las siguientes reglas.

• Aplicar las leyes asociativas, conmutativas y distributivas para los conectivos $\wedge$ y $\vee$
• Sustituir $\neg\neg P$ con $P$
• Sustituir $\neg(P\wedge Q)$ con $\neg P\vee\neg Q$ y $\neg(P\vee Q)$ con $\neg P\wedge\neg Q$.
• Sustituir $P\Rightarrow Q$ con $\neg P\vee Q$ y $P\Leftrightarrow Q$ con $(\neg P\vee Q)\wedge(\neg Q\vee P)$.

Por ejemplo, la expresión $$\neg((PQ\wedge\neg Q)\vee(R\wedge Q))$$ es equivalente a $$\neg P Q\wedge\neg Q Q\wedge\neg R\neg Q,$$ y la expresión $$(P\Rightarrow Q)\equiv(\neg Q\Rightarrow\neg P)$$ a $$PQ\neg P\wedge\neg QQ\neg P\wedge\neg Q\neg PQ\wedge P\neg PQ.$$ (Para simplicar las expresiones, se está omitiendo a $\vee$ y adoptando la convención de que hay prioridad de $\wedge$ sobre $\vee$ para los paréntesis).
     Demos, salvo equivalencia lógica, expresiones explícitas de todas las proposiciones a partir de otras. Salvo las expresiones tautológicas, toda expresión construida a partir de las proposiciones $P_1,\ldots,P_n$ es equivalente a una conjunción que es parte de la conjunción obtenida al desarrollar, de acuerdo a la ley distributiva $P(Q\wedge R)\equiv PQ\wedge PR$, la expresión $(P_1\wedge \neg P_1)(P_2\wedge\neg P_2)\cdots(P_n\wedge\neg P_n)$. En efecto, llevemos la expresión construida a partir de $P_1,\ldots,P_n$ a una forma normal conjuntiva. Como el valor de verdad de la expresión no cambia si se omite un conyunto verdadero, omitimos los conyuntos que contengan a $P$ y a $\neg P$. También cambiamos los $P\vee P$ por $P$. Así que cada uno de los conyuntos restantes es simplemente una disyunción cuyos disyuntos son elementos, con subíndice distinto, del conjunto $\{P_1,\ldots,P_n\}$. Si una disyunción no tiene ni a $P_i$ ni a $\neg P_i$, insertamos el término $(P_i\wedge\neg P_i)$ y aplicamos $P(Q\wedge R)\equiv PQ\wedge PR$. Luego, cada conyunto contiene o a $P_i$ o a $\neg P_i$ para todo $i$. Es decir, hay $2^n$ conyuntos posibles y un total de $\sum_{k=0}^{k=2^n}\binom{2^n}{k}=\mathcal{P}(2^n)=2^{2^n}$ conjunciones posibles con estos conyuntos. La conjunción impropia que surge de omitir todos los conyuntos es considerada una tautología.
     Por ejemplo, las cuatro diferentes proposiciones construidas a partir de $P$ son $$P\wedge\neg P\,,P\,,\neg P\,,P\vee\neg P.$$ Notemos que $P\vee\neg P$ corresponde a la conjunción impropia. Las dieciséis diferentes proposiciones construidas a partir de $P$ y $Q$ son \begin{align} &PQ\wedge\neg PQ\wedge P\neg Q\wedge\neg P\neg Q\,,PQ\wedge\neg PQ\wedge P\neg Q,\notag\\ &PQ\wedge P\neg Q\wedge\neg P\neg Q\,,PQ\wedge\neg PQ\wedge\neg P\neg Q\,,\neg PQ\wedge P\neg Q\wedge\neg P\neg Q,\notag\\ &PQ\wedge\neg PQ\,,PQ\wedge P\neg Q\,,PQ\wedge\neg P\neg Q\,,\neg PQ\wedge P\neg Q\,,\neg PQ\wedge\neg P\neg Q,\notag\\ &P\neg Q\wedge\neg P\neg Q\,,PQ\,,\neg PQ\,,P\neg Q\,,\neg P\neg Q,\notag\\ &(P\vee\neg P)\wedge (Q\vee\neg Q).\notag \end{align} Notemos que $(P\vee\neg P)\wedge (Q\vee\neg Q)$ corresponde a la conjunción impropia.
     Dadas las proposiciones $P_1,\ldots,P_n$, a los conyuntos individuales de la expresión $(P_1\wedge \neg P_1)(P_2\wedge\neg P_2)\cdots(P_n\wedge\neg P_n)$ desarrollada mediante la ley distributiva $P(Q\wedge R)\equiv PQ\wedge PR$ se los llama los constituyentes de $P_1,\ldots,P_n$, y diremos que las conjunciones obtenidas, como se mostró anteriormente, de las combinaciones de los conyuntos de esa expresión son las formas normales distinguidas de las proposiciones construidas a partir de $P_1,\ldots,P_n$.
     Calculemos, salvo equivalencia lógica, todas las deducciones a partir de los axiomas $A_1,\ldots, A_n$. Se tiene que la proposición $B$ es consecuencia lógica de estos si y sólo si $(A_1\wedge\cdots\wedge A_n)\Rightarrow B$ es una tautología. Sean $P_1,\ldots,P_m$ todas las proposiciones elementales que aparecen en $A_1,\ldots, A_n$ y conectemos todos nuestros axiomas $A_1,\ldots,A_n$ con $\wedge$, y supongamos que la combinación de proposiciones así obtenida está desarrollada en su forma normal distinguida en términos de $P_1,\ldots,P_m$. Tomemos entonces cualquier constituyente de $P_1,\ldots,P_m$ que no aparezca como conyunto en esta forma normal distinguida. Estos constituyentes se pueden transformar en una proposición falsa mediante una sustitució apropidada: un $P_i$ sustituido por una proposición verdadera si este $P_i$ está negado y un $P_i$ por una proposición falsa si este $P_i$ no lo está. Por otro lado, por medio de esta sustitución, nuestra forma normal distinguida queda transformada en una proposición verdadera, pues cada uno de sus conyuntos difieren de los constituyentes que no aparecen en ella en tener en al menos un lugar un disyunto que es la negación del del constituyente. Luego, los constituyentes que no aparecen en nuestra forma normal distinguida no son consecuencia lógica de los axiomas $A_1,\ldots,A_n$. Así que, obtenemos, salvo equivalencia lógica, a partir de nuestros axiomas, todas las consecuencias lógicas en las que aparecen las proposiciones elementales de nuestros axiomas como sigue: conectamos todos los axiomas mediante $\wedge$ y formamos la forma normal conjuntiva distinguida para la expresión resultante; finalmente, elegimos cualesquiera de los conyuntos de la forma normal distinguida de la conjunción de nuestros axiomas y hacemos su conjunción.

---

Estas notas están basadas en el libro Principles of mathematical logic de Hilbert y Ackermann. Interesante, aunque no extraño, que la conexión entre la forma normal conjuntiva y la demostración automática de teoremas la encontrara en un libro de Hilbert.

Dolor en el estómago y un pequeño ejercicio de lógica

Para distraerme de este intenso dolor de estómago que tengo, escribiré la solución del primer ejercicio del primer capítulo del Gödel's Incompleteness Theorems de Raymond Merrill Smullyan.

Ejercicio. Supóngase que $\mathcal{L}$ es un sistema correcto en el que se cumplen las siguientes condiciones:

1. El conjunto $D^{\ast}$ es expresable en $\mathcal{L}$.
2. Para todo predicado $H$, existe un predicado $H'$; tal que para todo número $n$, la proposicón $H'(n)$ es demostrable en $\mathcal{L}$ si y sólo si $H(n)$ es refutable en $\mathcal{L}$.

Demuestra que $\mathcal{L}$ es incompleto.

Se dice que una proposición $X$ es decidible en $\mathcal{L}$ si es demostrable o refutable en $\mathcal{L}$, e indecidible en $\mathcal{L}$ si no. Se dice que un sistema $\mathcal{L}$ es completo si toda proposición es decidible en $\mathcal{L}$, e incompleto si alguna proposición es indecidible en $\mathcal{L}$.

Solución. Como $D^{\ast}$ es expresable en $\mathcal{L}$, existe un predicado $H$ en $\mathcal{L}$ tal que para todo $n$,

$H(n)$ es verdadera $\Leftrightarrow n\in D^{\ast}\Leftrightarrow d(n)\in D$.

Por otro lado, para $H$, existe un predicado $H'$ tal que para todo $n$

$H'(n)$ es demostrable en $\mathcal{L}$ $\Leftrightarrow$ $H(n)$ es refutable en $\mathcal{L}$.

Ahora sea $h'$ el número de Gödel de $H'$. Entonces se tiene para $h'$ que

$H(h')$ es verdadera $\Leftrightarrow d(h')\in D \Leftrightarrow H'(h')$ es demostrable.

Y

$H'(h')$ es demostrable en $\mathcal{L}\Leftrightarrow H(h')$ es refutable en $\mathcal{L}$.

Así que

$H(h')$ es verdadera $\Leftrightarrow H(h')$ es refutable en $\mathcal{L}$.

Pero $\mathcal{L}$ es correcto; por lo tanto, $H(h')$ es falsa y no refutable en $\mathcal{L}$, y, nuevamente, como $\mathcal{L}$ es correcto, y $H(h')$ falsa, se tiene que $H(h')$ no puede ser demostrable en $\mathcal{L}$. Luego, $H(h')$ es indecidible, y, por lo tanto, $\mathcal{L}$ incompleto.

Un ejercicio bastante sencillo. Y el dolor ya se me pasó.

Una forma abstracta del teorema de incompletez1 de Gödel2

Cada uno de los lenguajes $\mathcal{L}$ a los que se les puede aplicar el argumento de Gödel contiene al menos los siguientes elementos:

1. Un conjunto numerable $\mathcal{E}$ cuyos elementos llamaremos las expresiones de $\mathcal{L}$.
2. Un subconjunto $\mathcal{P}$ de $\mathcal{E}$ cuyos elementos llamaremos las proposiciones de $\mathcal{L}$.
3. Un subconjunto $\mathcal{D}$ de $\mathcal{P}$ que llamaremos las proposiciones demostrables de $\mathcal{L}$.
4. Un subconjunto $\mathcal{R}$ de $\mathcal{P}$ que llamaremos las proposiciones refutables de $\mathcal{L}$.
5. Un conjunto $\mathcal{H}$ de expresiones cuyos elementos llamaremos los predicados de $\mathcal{L}$. [Estos fueron llamados nombres de clase en la introducción de Gödel. Informalmente, se está pensando que cada predicado H es el nombre de un conjunto de números naturales].
6. Una función Φ que asigna a cada expresión E y a cada número natural n una expresión E(n). Se requiere que la función cumpla la condición de que para cada predicado H y cada número natural n, la expresión H(n) sea una proposición. [Informalmente, la proposición H(n) expresa la proposición de que el número n pertenece al conjunto nombrado por H].
   
   En la primera demostración de incompletez que daremos para un sistema particular $\mathcal{L}$, usaremos un concepto básico precisado por Alfred Tarski [1936] —a saber, la noción de proposición verdadera (definida de manera muy diferente que la de proposición demostrable de un sistema)—.
7. Un conjunto $\mathcal{V}$ de proposiciones cuyos elementos llamaremos las proposiciones verdaderas de $\mathcal{L}$.

Esto concluye nuestra descripción abstracta del tipo de sistemas que estudiaremos en los siguientes capítulos.

Expresabilidad en $\mathcal{L}$. La noción de expresabilidad en $\mathcal{L}$, la cual estamos por definir, se relaciona con el conjunto de verdad $\mathcal{V}$ pero no con los conjuntos $\mathcal{D}$ o $\mathcal{R}$.

     La palabra número querrá decir número natural para el resto de este volumen. Diremos que un predicado H es verdadero para un número n o que n satisface H si H(n) es una proposición verdadera (es decir, si es un elemento de $\mathcal{V}$). Con el conjunto expresado por H, querremos decir el conjunto de todos los n que satisfacen H. Así, para cualquier conjunto A de números, H expresa A si y sólo si para todo número n

H(n)∈$\mathcal{V}$ ↔ n∈A.

Definición. Un conjunto A se dice que es expresable o nombrable en $\mathcal{L}$ si A es expresado por algún predicado de $\mathcal{L}$.

     Puesto que sólo hay una cantidad numerable de expresiones de $\mathcal{L}$, sólo hay una cantidad finita o numerable de predicados de $\mathcal{L}$. Pero por el bien conocido teorema de Cantor, hay una cantidad no-numerable de conjuntos de números naturales. Por lo tanto, no todo conjunto de números es expresable en $\mathcal{L}$.

Definición. Se dice que el sistema $\mathcal{L}$ es correcto si toda proposición demostrable es verdadera y toda proposición refutable es falsa (no verdadera). Esto significa que $\mathcal{D}$ es un subconjunto de $\mathcal{V}$ y que $\mathcal{R}$ es disjunto de $\mathcal{V}$. Ahora estamos interesados en las condiciones suficientes, si $\mathcal{L}$ es correcto, para que $\mathcal{L}$ contenga una proposicón verdadera no demostrable en $\mathcal{L}$.

Numeración de Gödel y Diagonalización. Sea g una función uno-a-uno que asigna a cada expresión E un número natural g(E), el cual llamaremos el número de Gödel de E. La función g será constante para el resto de este capítulo. [En los sistemas concretos que estudiaremos en capítulos posteriores, se dará una numeración de Gödel específica. Sin embargo, nuestro presente tratamiento puramente abstracto se puede aplicar a una numeración de Gödel arbitraria]. Será conveniente técnicamente suponer que todo número es el número de Gödel de una expresión. [La numeración original de Gödel no tenía esta propiedad, pero la numeración de Gödel que usaremos en capítulos posteriores sí la tendrá. Sin embargo, los resultados de este capítulo se pueden demostras, con modificaciones menores, sin esta restricción (Vea Ex. 5)]. Suponiendo que todo número es el número de Gödel de una expresión única, hagamos que E_n sea la expresión cuyo número de Gödel es n. Así, g(E_n)=n.

     Con la diagonalización de E_n, querremos decir la expresión E_n(n). Si E_n es un predicado, entonces su diagonalización es, por supuesto, una proposición; esta proposición es verdadera si y sólo si el predicado E_n es satisfecho por su propio número de Gödel n. [Escribimos “ssi” para querer decir si y sólo si; usamos “↔” de igual manera].
     Para cualquier n, sea d(n) el número de Gödel de E_n(n). La función d(x) juega un papel clave en todo lo que sigue; la llamaremos la función diagonal del sistema.
     Usaremos el término conjunto de números para querer decir conjunto de números naturales. Para cualquier conjunto de números A, con A^∗ querremos decir el conjunto de todos los números n tales que d(n)∈A. Así, para cualquier número n, la equivalencia

n∈A^∗ ↔ d(n)∈A

se cumple por definición de A^∗. [A^∗ también podría escribirse como d^-1(A), ya que es la imagen inversa de A bajo la función diagonal d(x)].

Una Forma Abstracta del Teorema de Gödel. Sea D el conjunto de los números de Gödel de todas las proposiciones demostrables. Para cualquier conjunto de números A, con su complemento ∼A, queremos decir el complemento de A respecto del conjunto de números naturales N —∼A es el conjunto de los números naturales que no están en A—.

Teorema (GT) —por Gödel, con matices de Tarski—. Si el conjunto (∼D)^∗ es expresable en $\mathcal{L}$ y $\mathcal{L}$ es correcto, entonces hay una proposicón verdadera de $\mathcal{L}$ no demostrable en $\mathcal{L}$.

Demostración. Supóngase que $\mathcal{L}$ y que (∼D)^∗ es expresable en $\mathcal{L}$. Sea H un predicado que expresa a (∼D)^∗ en $\mathcal{L}$, y sea h el número de Gödel de H. Sea G la diagonalización de H (es decir, la proposición H(h)). Mostraremos que G es verdadera pero no demostrable en $\mathcal{L}$.
     Puesto que H expresa a (∼D)^∗ en $\mathcal{L}$, para cualquier número n, H(n) es verdadera ↔ n∈(∼D)^∗. Ya que esta equivalencia se cumple para todo n, se cumple en particular para n el número h. Así que tomamos h como n (y esta es la parte del argumento llamada diagonalización) y tenemos la equivalencia H(h) es verdadera ↔ h∈(∼D)^∗. Ahora,

h∈(∼D)^∗ ↔ d(h)∈∼D ↔ d(h)∉D.

Pero d(h) es el número de Gödel de H(h) (puesto que h es el número de Gödel de H), así que d(h)∈D ↔ H(h) es demostrable en $\mathcal{L}$ y d(h)∉D ↔ H(h) no es demostrable en $\mathcal{L}$. Así que tenemos

1. Esto significa o que H(h) es verdadera y no demostrable en $\mathcal{L}$ o que es falsa pero demostrable en $\mathcal{L}$. La última alternativa viola la hipótesis de que $\mathcal{L}$ es correcto. De aquí, se tiene que tener que H(h) es verdadera pero no demostrable en $\mathcal{L}$.

     Cuando se trate de los lenguajes particulares $\mathcal{L}$ que estudiaremos, verificaremos la hipótesis de que (∼D)^∗ es expresable en $\mathcal{L}$ al verificar separadamente las siguientes tres condiciones.

G₁: para cualquier conjunto A expresable en $\mathcal{L}$, el conjunto A^∗ es expresable en $\mathcal{L}$.
G₂: para cualquier conjunto A expresable en $\mathcal{L}$, el conjunto ∼A es expresable en $\mathcal{L}$.
G₃: el conjunto D es expresable en $\mathcal{L}$.

     Las condiciones G₁ y G₂ implican, por supuesto, que para cualquier conjunto A expresable en $\mathcal{L}$, el conjunto (∼A)^∗ es expresable en $\mathcal{L}$. De aquí, si D es expresable en $\mathcal{L}$, entonces también lo es (∼D)^∗.
     Podríamos notar que la verificación de G₁ resultará ser relativamente simple; la verificación de G₂ será completamente trivial; pero la verificación de G₃ resultará ser extremadamente elaborada.



¹La palabra que seguiría la norma sería ‘incompleción’, como bien nos pueden sugerir ‘discreción’ para ‘discreto’, ‘concreción’ para ‘concreto’, ‘abstracción’ para ‘abstracto’; sin embargo, a la mayoría de los matemáticos de habla hispana no les interesa mucho la norma del idioma español y, en consecuencia, se ponen en uso barbarismos horribles como ‘incompletez’.

²Esta es una traducción libre de un fragmento del libro Gödel's Incompleteness Theorems de Raymond Merrill Smullyan y corresponde precisamente a una generalización del teorema de incompletez de Gödel. La publico porque me parece importante que dicha generalización se conozca.