Forma normal conyuntiva

A todo esquema de argumento (o "forma proposicional") de la lógica proposicional puede dársele una forma que se llama "normal conyuntiva" (o conjuntiva) FNC.

Esta forma se define así (téngase presente que nos estamos refiriendo a una lógica de proposiciones):

1. Sólo están presentes, de entre los signos conectivos lógicos, los siguientes: ¬, ∧ y ∨.

2. Los signos de negación sólo afectan a expresiones simples, quiero decir, sólo a variables. Dicho de otra manera: no afecta a ningún ¬, ∧ ni ∨; de modo que ni ¬¬p ni ¬(p ∧ q) ni ¬(p ∨ p) están en FNC.

3. Ningún signo «∧» puede estar encerrado en alguna disyunción. Así, la fórmula  p ∨ ( p ∧ q) no está en FNC, pero sí lo está (p ∨ p) ∧ (p ∨ q).

De este modo, una "forma normal conyuntiva" es una conjunción (como: P₁ ∧ P₂ ∧ ... ∧ P_n ) en la que cada miembro P_i consiste en alguna disyunción de variables proposicionales (negadas o no) o en una variable (negada o no).

Mostraremos ahora eso de que todo esquema proposicional puede ser llevado a uno equivalente pero de esta forma. Para ello, podemos recurrir a las transformaciones siguientes:

I. Puede ocurrir que querramos dar forma normal conjuntiva a una "forma proposicional" como «p → q» o a una como «p ↔ q».

En el primero de estos dos casos procedemos teniendo en cuenta lo siguiente: 

p → q  ≡ ¬p ∨ q

En el segundo tendremos en cuenta:

p ↔ q  ≡  (p → q) ∧ (p → q)

de donde llemagmos a:

p ↔ q  ≡  (¬p ∨ q) ∧ (¬q ∨ p)

Otra equivalencia útil en este punto es:

p ↔ q  ≡  (p ∧ q) ∨ (¬p ∧ ¬q)

II. Cuando la negación no cumple con 2., entonces tenemos en cuenta las leyes de De Morgan.

III. Si tenemos alguna sucesión de negaciones, consideramos la equivalencia: ¬¬p ≡ p

IV. Puede ocurrir, lo hace de hecho lo hace, que tengamos algo como:

p ∨ (q ∧ r)

Pero esto es manifiestamente contrario a 3. Aplicamos la "ley distributiva" siguiente:

p ∨ (q ∧ r)  ≡  (p ∨ q) ∧ (p ∨ r)

que nos recuerda la matemática que veíamos en el colegio [por ejemplo: a(b + c) = ab + ac].

Veamos ahora el siguiente ejemplo¹:

(1)   (p → q) ↔ (¬q → ¬p)

Transformamos los condicionales:

(¬p ∨ q) ↔ (¬¬q ∨ ¬p)

Ahora la equivalencia:

[¬(¬p ∨ q) ∨ (¬¬q ∨ ¬p)]  ∧  [¬(¬¬q ∨ ¬p) ∨ (¬p ∨ q)]

De Morgan:

[(¬¬p ∧ ¬q) ∨ (¬¬q ∨ ¬p)]  ∧  [(¬¬¬q ∧ ¬¬p) ∨ (¬p ∨ q)]

Simplificamos las doble-negaciones:

[(p ∧ ¬q) ∨ (q ∨ ¬p)]  ∧  [(¬q ∧ p) ∨ (¬p ∨ q)]

Ahora distribuimos y obtenemos el siguiente esquema de forma conyuntiva normal:

(2) (p ∨ q ∨ ¬p) ∧ (¬q ∨ q ∨ ¬p)  ∧  (¬q ∨ ¬p ∨ q) ∧ (p ∨ ¬p ∨ q)

En la forma que nos ocupa durante este post es posible comprobar si se trata de un esquema válido de un modo breve. Para corroborar que así sea, basta ver que en cada una de las conyunciones (cada una de las partes de la «forma conjuntiva normal» de que se trate) haya alguna variable y a la vez su negación.

Por ejemplo en (2) tenemos cuatro disyunciones agrupadas en una conjunción. La primera de ellas tiene 'p' y '¬p', la segunda 'q' y '¬q', la tercera también 'q' y '¬q' y la última 'p' y '¬p'. Así, podemos concluir que (1) es válida universalmente o, en otros términos, que es una tautología.

De un modo completamente análogo, en un esquema presentado en la forma normal disyuntiva (no veremos qué es esto en el presente post) puede verse si es una contradicción.

Al lector podrá serle de utilidad el ejecicio siguiente:

Dar forma conyuntiva normal al esquema «(p ∧ ¬p) ∨ (q ∧ ¬q)»

________

1. El ejemplo así como el resto del contenido en el post está presente en Grundzüge det theoretischen logik de Hilbert y Ackermann, traducido como Elementos de lógica teórica.