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.
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.
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)$.
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.
