Formas normales

En las clases anteriores de esta unidad se dio significado a las fórmulas: la clase sobre la semántica de la lógica proposicional extendió cada valoración a todas las fórmulas; la clase sobre consecuencia y equivalencia semántica definió la equivalencia $\varphi \eqsem \psi$ y demostró el reemplazo semántico; la clase sobre las leyes generalizadas de De Morgan y de distribución extendió esas leyes a conjunciones y disyunciones de $n$ fórmulas; y la clase sobre la completitud funcional mostró que toda función de verdad está representada por alguna fórmula. Ahora bien, una función de verdad está representada por infinitas fórmulas, que pueden ser muy distintas entre sí: $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ y $((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2)$ son tres nombres de lo mismo. Si esto es así, conviene elegir en cada clase de equivalencia un representante de forma fija, que se lea sin esfuerzo y con el que ciertas preguntas se respondan mirando. Eso son las formas normales.

Literales, cláusulas y formas normales

Recuérdese, de la clase sobre las leyes generalizadas, la notación de la conjunción y de la disyunción de $n$ fórmulas, definida por recursión y asociando por la izquierda; la de una sola fórmula es la fórmula misma.

En la misma clase se demostró que el orden y la agrupación de los términos no alteran la fórmula salvo equivalencia (asociatividad y conmutatividad generalizadas); por eso escribiremos también $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ sin paréntesis, entendiendo la agrupación por la izquierda.

Un literal es una variable $v_n$, que se llama literal positivo, o la negación $\neg v_n$ de una variable, que se llama literal negativo. El opuesto de un literal $\ell$, que escribimos $\ell^{*}$, es el literal de la misma variable y del otro signo:

De la definición se sigue que $(\ell^{*})^{*} = \ell$. Dos literales forman un par complementario si uno es el opuesto del otro, como $v_3$ y $\neg v_3$.

Una cláusula es una disyunción de literales, $\bigvee_{j=1}^{k} \ell_j$, y una conjunción elemental es una conjunción de literales, $\bigwedge_{j=1}^{k} \ell_j$, con $k \geq 1$ en ambos casos; un literal solo es, por tanto, a la vez una cláusula y una conjunción elemental. Se dice que un literal está en una cláusula o en una conjunción elemental si es uno de sus $\ell_j$.

Una fórmula está en forma normal disyuntiva si es una disyunción de conjunciones elementales, y en forma normal conjuntiva si es una conjunción de cláusulas; es decir, si es, respectivamente, de una de las dos formas siguientes, donde $m$ y $k_1, \ldots, k_m$ son naturales y cada $\ell_{i,j}$ es un literal:

Diremos que $\Phi$ es una forma normal disyuntiva de $\varphi$ si está en forma normal disyuntiva y $\varphi \eqsem \Phi$, y lo mismo con la conjuntiva. Las longitudes $k_i$ pueden variar de una conjunción (o cláusula) a otra: exigir el mismo número de literales en todas, como hacía el artículo de origen, obligaría a rellenar con repeticiones y no añadiría nada.

Conviene detenerse en lo que significa «estar en forma normal». Es una propiedad de la cadena de círculos y discos, no de su significado: la clase sobre la inducción sobre la complejidad de las fórmulas demostró la lectura única, de modo que preguntar si una fórmula es una disyunción, y de qué, tiene una sola respuesta. Ahora bien, las abreviaturas oficiales hacen que algunas fórmulas estén en forma normal sin parecerlo. La implicación $(v_1 \rightarrow v_2)$ se define como $(\neg v_1 \vee v_2)$: no es que equivalga a esa cláusula, sino que es esa misma cadena, y por tanto ya está en forma normal. Más sorprendente es la doble negación. Por las definiciones de $\neg$ y de $\vee$, la cadena $(\varphi \vee \varphi)$ es $\neg(\varphi \downarrow \varphi)$, es decir, $\neg\neg\varphi$; de donde $\neg\neg v_1$ no es un literal, pero es, letra por letra, la cláusula $(v_1 \vee v_1)$.

El valor de las conjunciones y de las disyunciones

De la clase sobre la semántica se toman los valores de los conectores derivados: $v(\neg\varphi) = 1 - v(\varphi)$; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, que vale $1$ si y solo si ambas valen $1$; y $v(\varphi \vee \psi) = 0$ si y solo si ambas valen $0$. La clase sobre las leyes generalizadas de De Morgan y de distribución los extendió a $n$ fórmulas, por inducción sobre el número de términos, en el lema del valor: para toda valoración $v$, la conjunción $\bigwedge_{i=1}^{n} \varphi_i$ vale $1$ en $v$ si y solo si cada $\varphi_i$ vale $1$ en $v$, y la disyunción $\bigvee_{i=1}^{n} \varphi_i$ vale $1$ en $v$ si y solo si alguna $\varphi_i$ vale $1$ en $v$. Ese lema, que aquí se cita sin repetir su demostración, es el instrumento con que se calcula el valor de cualquier forma normal.

El segundo caso es el que el artículo de origen pasaba por alto: al negar una forma normal escribía $\neg L_{ij}$ en lugar de un literal, y $\neg\neg v_n$ no lo es. La doble negación es la que devuelve el resultado al molde.