Eso que llamamos Lógica (II) La Forma Normal Disyuntiva en el Álgebra de Boole

En el espeso y llenito-llenito de fórmulas, aunque tremendamente didáctico (espero), artículo anterior de esta serie sobre algo parecido a la lógica, vimos cómo en dos patadas Don José Cuena se despachó toda la definición del Álgebra de Boole. Al día siguiente (en realidad a la semana siguiente, porque las clases eran semanales, de dos horas cada una), a mediados de octubre de 1973, nuestro profesor apareció nuevamente a la hora en punto para seguir iluminándonos.

Sigamos con él, pues.

Bien, lo que Don José nos contó ese día fue cómo se definía una determinada relación en el álgebra de Boole, introduciendo para ello el signo $\leq$ , que relaciona dos elementos del conjunto S. Evidentemente, la relación se llama “Menor o igual que”, hasta ahí podíamos llegar… En un álgebra de Boole se puede definir esta relación mediante la siguiente ecuación:

$a \leq b \Longrightarrow{a\cdot b' =0}$

Como ya nos habíamos dado cuenta los de clase, o al menos la mayoría, que para algo el descubrimiento de la semana pasada había corrido como la pólvora, de que el álgebra de Boole era la que regulaba la Teoría de Conjuntos, rápidamente nos dimos cuenta de que la relación $\leq$ en conjuntos era exactamente la relación “Contiene” que estudiamos años atrás en dicha teoría; mejor dicho, puesto que es “menor o igual que” y no “mayor o igual que”, en realidad se trata de la relación “Es Contenido por”.

Y claro, a partir de aquí todo fue coser y cantar. Si el conjunto A es contenido por el conjunto B, esto implica que la intersección de A y el complementario de B es el conjunto vacío… ergo $a \leq b$ implica que $a \cdot b'=0$ .

Naturalmente. Evidentemente. ¡Qué tontería!

Una Relación de orden en Conjuntos

En la figura anterior queda claro. B contiene a A, así que A es menor o igual que B, es decir, $A \leq B$ . Por tanto, la intersección de A (el conjunto azul) con B’ (la zona gris clarita), que es el complementario de B (la parte amarilla), es el conjunto vacío, pues no tienen ningún elemento en común, luego es evidente que $A\cdot B'=0$ .

Toda la clase estuvo dedicada a demostrar las diferentes propiedades de tal relación, en demostrar que es una relación de orden, y, dentro de las de orden, de “orden parcial”, puesto que la relación no abarca a todos los elementos de S.

Por muy intimidante que parezca el párrafo anterior, en realidad es una tontería, es muy sencillo de entender: La relación $\leq$ en los números naturales o en los reales, por ejemplo, es de orden total: cada uno de todos los números es o menor o mayor que todos los demás, pero tratando con conjuntos no tiene por qué ser así: pueden existir conjuntos que ni contienen ni son contenidos por otros conjuntos. El ejemplo más claro es lo que ocurre entre un conjunto y su complementario, por ejemplo, “los españoles” con “los extranjeros (los no españoles, vaya)”: ninguno de los dos conjuntos contiene al otro.^[1]

Y como toda buena relación de orden, cumple con las tres conocidas propiedades: es Reflexiva (es decir, $A \leq A$ , pues todo elemento es menor o igual que sí mismo, en este caso estrictamente igual) es Transitiva (o sea, si $A \leq B$ y $B \leq C$ , entonces $A \leq C$ , lo que es bastante evidente), y es Antisimétrica (es decir, que si $A \leq B$ y simultáneamente $B \leq A$ , entonces necesariamente $A=B$ , lo que es también sencillo de entender).

Antes de que digáis nada, en realidad la cosa es al revés: como en esta relación “ $\leq$ ” se cumplen las tres propiedades, entonces la relación “ $\leq$ ” es de orden. Ahora sí.

Como consecuencia de ser una relación de orden, se cumplen un par de propiedades adicionales:

Por un lado, si $x \leq y$ entonces $x \leq y+z$ .

Y por el otro, si $x \leq y$ entonces $y' \leq x'$ .

No voy a demostrar estas fórmulas: no son muy complicadas, por no decir que son intuitivas.^[2] Quedémonos simplemente con esto: la relación “ $\leq$ ” en un álgebra de Boole es de orden parcial, y con eso nos sirve.

Le íbamos cogiendo el tranquillo a esto de la Lógica…

Siguiente día, siguiente semana. Hora en punto. Esto ya se está convirtiendo en todo un síntoma…

Hoy D. José nos hablará de La Forma Normal Disyuntiva de las expresiones (funciones) en un álgebra de Boole.

Mmmm. La… ¿qué? Sí, la Forma Normal Disyuntiva, ¿qué pasa? Será algo importantísimo para lo que sigue más adelante, así que hagamos menos chiribitas con los ojos, y vayamos al grano.

Primero habrá que definir qué es una función boleana. Toda aplicación de $S^n en S$ que venga dada por una expresión en álgebra de Boole es una función booleana. Fácil, ¿no? … Venga, que es sencillo: dado que las dos operaciones definidas para el álgebra (+,·) son cerradas, es decir, que aplicadas a dos elementos de S dan como resultado otro elemento de S, el resultado de toda función f(x,y,z,…) expresada en álgebra booleana también pertenece a S.

…

Bueno, vale, ya voy.

Sea, por ejemplo, la función $f(x,y,z)= (x' \cdot (y+z))+(z' \cdot (y'+x))$ definida en un sistema que obedece al álgebra de Boole.

Como tanto x como y como z son elementos de S, sea S lo que sea (y, por tanto, sus complementarios también lo son), cualquier operación (+,·) realizada sobre ellos (y entre ellos) y sus complementarios dará obligatoriamente un resultado que será también un elemento de S.

Truco: Pensad en conjuntos y lo veréis claro. Dados varios conjuntos cualesquiera y unidos e intersecados entre sí y sus complementarios como nos venga en gana, el resultado será siempre otro conjunto. Eso es una aplicación de $S^n en S$ .

Teóricamente, las expresiones del álgebra de Boole podrían llevar constantes; de hecho hay dos constantes “de oficio”: los dos elementos neutros, 0 y 1. Pero las constantes en el sentido algebraico habitual no tienen mucho sentido:

¿Qué sería 6a, por ejemplo? Pues a, claro, dado que $6a=a+a+a+a+a+a$ . Como sabemos que $a+a=a$ ^[3] entonces $6a=a$ , obviamente.

¿Y qué sería $(a+b)^3$ , entonces? Pues $(a+b)$ , natural, dado que $(a+b)\cdot (a+b)=(a+b)$ .

En definitiva, nunca aparecerán constantes en las expresiones que usaremos aquí (ni en las que usaremos normalmente en nuestra vida cotidiana de relación con el álgebra de Boole).

Pues bien, si tenemos una función booleana cualquiera en la que no aparecen constantes (por ejemplo, $f(x,y,z)=(x' \cdot (y+z)'+x) \cdot (x'+(y \cdot z))'$ , sin ir más lejos), entonces dicha función se puede representar como una suma de productos $P_{i}$ , tales que:

1) En todo término $P_{i}$ aparecen reflejadas todas las variables que aparecen en la fórmula original (bien complementadas, bien sin complementar). Todas ellas, sin faltar ni una.

2) Todos los productos $P_{i}$ son distintos entre sí.

Cabe decir aquí que a partir de ahora haré lo mismo que Don José hizo hace casi cuarenta años, simplificando la notación de las fórmulas de la misma manera que lo hacemos en el “álgebra normal”, la numérica: no escribiendo el signo “·”, salvo en los casos donde su uso sea preciso para hacer más descriptiva la fórmula. Es decir, la fórmula del ejemplo de arriba (y todas las demás) la escribiré preferentemente a partir de ahora de la siguiente manera:

$f(x,y,z)=(x'(y+z)'+x)(x'+(yz))'$

Se entiende, ¿no? Pero recordad que “+” no es “suma” ni “·” es “multiplicación” en el sentido numérico habitual, sino que son “sumas booleanas” o “productos booleanos”, que ya veremos cómo se definen en según que sistemas… En conjuntos, por ejemplo, “+” es “Unión y “·” es “Intersección”, como ya sabéis. En otros sistemas, serán… otras cosas…

Paciencia.

Volviendo a la afirmación de hace un ratito (eso de que toda función se puede descomponer en sumas de productos), que seguro que os ha dejado con cara de haba, veremos cómo se llega con sencillez a esto, procediendo a la reducción sistemática de las expresiones en tres pasos:

Paso 1: Quitar sistemáticamente toda complementación a fórmulas entre paréntesis. Para ello usaremos extensivamente las Leyes de De Morgan.^[4] Eran el Teorema 8 que vimos en el artículo anterior.

Por ejemplo, si tenemos $(a+b)' \cdot (cd)'$ , quedaría, aplicando De Morgan, $a'b' \cdot (c'+d')$ .

Al final de este paso sólo sólo habrá complementaciones de las variables individuales, pero no de operaciones con ellas (que no habrá complementaciones a paréntesis, vaya).

Paso 2: Quitar sistemáticamente el signo “·” entre paréntesis, aplicando la propiedad distributiva. Así, $a(b+c)$ quedaría $ab+ac$ .

Por ejemplo, $(x'+z)(y+w)$ quedaría $x'y+x'w+zy+zw$ .

En realidad, ése es el resultado final, tras dos pasos. El primero dejaría $(x'+z)y+(x'+z)w$ , y en un segundo paso quedaría $x'y+zy+x'w+zw$ ; reordenando,^[5] queda la fórmula del texto.

Por supuesto, si algún término resulta que tiene simultáneamente una variable x y su complementaria, x’, al estar ambas multiplicándose entre sí, el resultado de esta multiplicación $(xx')$ es cero,^[6] por lo que podemos eliminar sin pudor alguno el término completo. Así, si, por ejemplo, resultara un término $xyy'z'$ , al ser $yy'=0$ , queda $xz' \dot 0$ , y podemos eliminar el término completo, pues sabemos que $a \cdot 0=0$ . Además, si quedan dos o más términos exactamente iguales, se pueden eliminar todos menos uno, puesto que sabemos también (mejor, seguimos sabiendo) que $a+a=a$ .

Bien, ahora tenemos ya la expresión reducida a una suma de productos distintos… pero no es suficiente, porque es posible que no en todos los productos estén representadas todas las variables, lo que era uno de los requisitos iniciales. De hecho, en el ejemplo anterior son 4 las variables (x,y,z,w) y ningún término tiene más que dos… Hay que hacer algo para que todos los términos tengan todas las variables, bien complementadas, bien sin complementar, que era el requisito previo, si os acordáis. Para solucionarlo:

Paso 3: Multiplicar los términos a los que les falte alguna variable x por $(x+x')$ , que, como es igual a 1, no cambia el resultado.

Por ejemplo, si son tres las variables de una cierta función f(x,y,z), y tenemos un término $xy'$ (sin z), entonces éste se multiplica por $(z+z')$ ,^[7] quedando $xy'(z+z')=xy'z+xy'z'$ .

Nuevamente, si como consecuencia de todas estas operaciones resultan dos o más términos iguales, se eliminan todos ellos menos uno, debido a la consabida idempotencia: $a+a=a$

En fin, tras la aplicación secuencial de estos tres pasos tenemos la misma fórmula original, bien masajeada, vale, pero la misma original, expresada de la forma pedida.

A esta forma de organizar las fórmulas booleanas se le llama Forma Normal Disyuntiva (FND), y veremos que es de gran utilidad más adelante… y hasta aquí puedo contar. Paciencia.

Veamos un ejemplo: Sea $f(x,y,z)=(x+y+z)(xy+x'z)'$ . Con tres variables, como podemos ver: x,y,z. ¿Cuál es su Forma Normal Disyuntiva?

Aconsejo a los que os interese todo esto que intentéis realizar el proceso vosotros solos, tenéis conocimientos y argumentos más que suficientes para hacerlo… y es fácil.

Según el paso 1, se eliminan los complementos en paréntesis (Ley de De Morgan).

$f(x,y,z)=(x+y+z)(xy+x'z)'$ queda, en primer lugar,

$(x+y+z)[(xy)'(x'z)']$ , que a su vez queda

$(x+y+z)[(x'+y')(x+z')]$ . Reordenando los productos (gracias a la propiedad conmutativa) queda, por fin:

$(x+y+z)(x+z')(x'+y')$ .

Ahora aplicamos la distributiva (paso 2). Primero, sacamos en los dos primeros términos sumando común a x,^[8] y entonces queda:

$[x+(y+z)z'] \cdot (x'+y')$ . Ahora aplicamos de nuevo la distributiva en el primer paréntesis, y queda:

$(x+yz'+zz')(x'+y')$ ; zz’ es cero, así que lo eliminamos, y queda:

$(x+yz')(x'+y')$ . Otra vez la distributiva y queda:

$x(x'+y')+yz'(x'+y')$ , y otra vez más y queda, finalmente:

$xx'+xy'+x'yz'+yy'z'$ .

Como xx’ es cero, lo mismo que yy’, queda finalmente: $xy'+x'yz'$ .

¿Ya está? Pues no, aún queda un poco.

Uno de los dos términos $(xy')$ no tiene la variable z, así que le multiplicamos por $(z+z')$ , que es, obviamente, 1 (paso 3), y tenemos que la fórmula original, ésa tan fea de ahí arriba, es equivalente a $xy'z+xy'z'+x'yz'$ , mucho más bonita, dónde va a parar, que ya está en Forma Normal Disyuntiva.^[9]

José Cuena Bartolomé.

Prosiguió su exposición Don José contándonos que se podría definir una Forma Normal Disyuntiva Completa, que es, para n variables, la suma de todos los productos posibles de las n variables complementadas y sin complementar, que, como es fácil comprobar, son en total $2^n$ .^[10]

Se demuestra fácilmente que una función cuya Forma Normal Disyuntiva sea Completa, es decir, que no le falta ni uno solo de los posibles términos que se pueden definir con las variables que la forman, es igual a la unidad (yo no voy a hacerlo aquí).

Por otra parte, se demuestra también fácilmente que, suponiendo como conjunto de valores posibles sólo 0 y 1, y dando a las variables valores arbitrarios entre estos, 0 ó 1, en la Forma Normal Disyuntiva Completa sólo habrá un único término que valdrá 1 y todos los demás, 0 (y su suma, 1, claro, al sumar muchos ceros y un único 1).

Esto es así porque para que un término (producto) cualquiera valga 1 en estas condiciones, todas las variables que lo componen tienen que valer 1, por lo que habrá sólo una combinación plausible: cualquier otra combinación de valores de las variables variará en al menos un valor de una variable, que será entonces 0 y anulará al término completo, al estar esa variable igual a cero multiplicando.^[11]

…

No se me arremolinen… Un pequeño ejemplo servirá para entenderlo (recordad que los valores en este caso sólo pueden ser 0 y 1): Mirando la Forma Normal Disyuntiva Completa de un conjunto de tres variables, x,y,z, uno de los términos que la forman es, verbigracia, $xy'z$ . Este término sólo puede valer 1 para los valores siguientes de las variables: x=1; y=0; z=1. En estas condiciones, este término vale 1, ¿sí?

Pero… ¿Qué les ocurrirá al resto de términos de la FNDC, por ejemplo el $x'yz$ ? Que variarán en al menos la complementación de una variable, en nuestro ejemplo en dos: x e y. Y al variar en alguna variable, quiere decir que alguno de los términos del producto ya no será 1, será 0, por lo que el producto completo será… cero. Efectivamente, para x=1; y=0; z=1, el producto $x'yz$ es cero. Y valen cero igualmente todos los demás términos, salvo el que cité al principio, el $xy'z$ , que sí valdrá 1. Luego la FNDC se compone de la suma de un único término que vale 1 y siete que valen 0, por lo que la suma final es… 1. Siempre 1.

Vale, pero… ¿Para qué sirve esta dichosa Forma Normal Disyuntiva? Pues para saber si dos funciones son en realidad la misma, puesto que toda función que sea igual a otra tendrá su misma Forma Normal Disyuntiva.^[12]

Esto nos será de gran utilidad más adelante, porque podemos representar la FND de cualquier función booleana en forma de tabla… veamos cómo quedaría la fórmula anterior, aquella $f(x,y,z)=(x+y+z)(xy+x'z)'$ original, cuya Forma Normal Disyuntiva habíamos visto que era $xy'z+xy'z'+x'yz'$ .

Representamos primero todos los valores posibles de la Forma Normal Disyuntiva Completa, todas las combinaciones posibles (en este caso serán $2^3=8$ ), y entonces marcamos con 0 los términos que no están en su FND, y con 1 los que sí están…

Y el resultado es:

V: x	V: y	V: z	$xy'z+xy'z'+x'yz'$
x	y	z	0
x	y	z’	0
x	y’	z	1
x	y’	z’	1
x’	y	z	0
x’	y	z’	1
x’	y’	z	0
x’	y’	z’	0

Tachaaannn!!

Las cosas empiezan a tener sentido, ¿no?

Aquí se acabó la clase, aquel frío otoño de 1973. Y el artículo. Hasta otra…

Disfrutad de la vida, mientras podáis.

En este caso, además, es que cada conjunto no contiene ni siquiera a uno solo de los integrantes del otro conjunto, no digamos a la totalidad… [↩]
Pensad en conjuntos y veréis que efectivamente son evidentes. [↩]
Teorema 1 del artículo sobre el álgebra de Boole, ¿recordáis? [↩]
No son Leyes de Morgan, sino de De Morgan, pues son debidas al matemático indio-británico Augustus De Morgan. [↩]
Aplicando la propiedad conmutativa. [↩]
Por el Axioma 4 del álgebra de Boole, para los descreídos. [↩]
Que es 1. [↩]
Qué raro suena eso de “sacar sumando común”, ¿verdad? Pues más vale acostumbrarse… [↩]
Sí, por si os lo estabais preguntando, también hay una Forma Normal Conjuntiva, que es parecida, pero sustituyendo los + por · y viceversa, así que lo que resulta es un producto de términos tal que cada uno de ellos es una suma que contiene todas las variables, complementadas o no, en vez de una suma de productos… La demostración es idéntica, en realidad, cambiando, en los pasos 2 y 3, el 1 por el 0 y el + por el ·, y viceversa. Todo en Álgebra de Boole es dual… [↩]
Permutaciones de 2 elementos (complementado-sin complementar) tomados de n en n. [↩]
Y lo mismo ocurre con la Forma Normal Conjuntiva, pero al revés: la Forma Normal Conjuntiva Completa será siempre cero. [↩]
O Conjuntiva, cierto. Todo, absolutamente todo en álgebra de Boole es dual. [↩]

The Eso que llamamos Lógica (II) La Forma Normal Disyuntiva en el Álgebra de Boole by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.

{ 9 } Comentarios

Felipe | 27/10/2011 at 07:19 | Permalink

¡Qué revelación esa última tabla! Gracias, Macluskey. Excelentísima serie.
Kratso | 28/10/2011 at 08:52 | Permalink

Algo que se me acaba de ocurrir leyendo aquello de imaginar un conjunto S con solo el 0 y el 1: ¿No se podría demostrar esto usando la idempotencia y el hecho de que tengan que existir dos constantes? Si estoy en lo cierto(cosa que, con este cansancio que traigo, dudo severamente) seria algo tal que así:

Sabemos que tienen que existir al menos el 1 y el 0 gracias a los axiomas(y hemos decidido llamarlos 1 y 0, como diría un amigo for the lulz) la demostración de que solo pueden existir el 0 y el 1 sería tal que así:

Imaginemos podemos definir dos elementos cualesquiera de $S$ a y b distintos entre. Entonces podemos suponer que el “producto”(Por llamarlo de alguna forma) entre ellos será un número distinto e independiente del orden que se utilice, es decir:

$a \cdot b = b \cdot a =c$ (Axioma 1)

También sabemos que a·b es sumar a veces b y que b·a es sumar b veces a. Entonces, a través de la Idempotencia podemos decir que:

$a \cdot b =b+b+b...+b=b$ y que $b \cdot a=a+a+a....+a=a$

Es decir que a=b, llegando a una contradicción lógica. Es decir, no existen en el conjunto S dos elementos a y b distintos entre si. ¿Excepciones? El 1 y el 0 la explicación es la siguiente:

Si sustituimos a y b con los siguientes valores(y recordando que por la ley de conmutatividad da igual que número se elija para a y que número para b) a=0 y b=1 tenemos que:

$01=10=c” /> Recordando que 1′=0 y que 0′=1 y el teorema 7 del artículo anterior tenemos que: <img src=$

Es decir que c=0 y, recordando que 0·a=0 la contradicción desaparece quedando pues que solo pueden existir en S dos elementos el 0 y el 1(u otros dos elementos con las mismas propiedades que les hemos dado al 0 y al 1)

En mi estado actual la demostración me parece coherente(pero como digo, estoy medio-dormido y no puedo asegurar que todo lo que diga en estos momentos sea real, díselo tu duendecillo pirómano). Que alguien le saque fallos será un autentico honor
Kratso | 28/10/2011 at 08:55 | Permalink

Me acabo de fijar en un tamaño error en la última fórmula con LaTeX(he ahi la razon de porqué uno no puede dejar que un sonámbulo escriba ) debería de ser $0 \cdot 1 = 1 \cdot 0=c$
J | 29/10/2011 at 08:02 | Permalink

También sabemos que a·b es sumar a veces b y que b·a es sumar b veces a.

Uhm… ¿esto lo sabemos? (En álgebra “normal” sí, pero en booleana… no lo hemos demostrado, ¿no?)
Macluskey | 29/10/2011 at 09:14 | Permalink

@Kratso: Como bien dice J,

“También sabemos que a·b es sumar a veces b y que b·a es sumar b veces a….” no lo hemos demostrado.

Es más, afirmo, no lo vamos a poder demostrar nunca. Porque en álgebra de Boole no es cierto. En el álgebra numérica normal, sí lo es, pero no en álgebra booleana.

Es fácil de ver: Piensa en nuestros amigos los conjuntos. Si tienes dos conjuntos A y B que, digamos, comparten algunos elementos, A·B son esos pocos elementos de la intersección entre ambos.

Ahora, si sumamos (unimos) “B” veces el conjunto “A” consigo mismo… conseguimos el mismo conjunto a, puesto que a+a=a.

O sea, A+A+…+A (B veces) es igual a “A”, no a “A·B”. Insisto, en álgebra booleana, que es de lo que trata el capítulo.

Además, querido Kratso… siguiendo con el ejemplo anterior… y siendo B como es un conjunto… ¿cómo podríamos sumar “B” veces algo?

De todos modos, como dicen los angloparlantes… “nice try!”

Gracias por comentar
Kratso | 29/10/2011 at 07:41 | Permalink

Bueno, tampoco esperaba mucho, se me ocurrio escasos minutos antes de irme a dormir, jeje.
Juan Carlos | 31/10/2011 at 05:04 | Permalink

Pues yo siempre decía las leyes de Morgan

Gran artículo!

Saludos
Macluskey | 31/10/2011 at 08:52 | Permalink

@Juan Carlos: Nooo… si todos decimos las “Leyes de Morgan”, lo de “Leyes de De Morgan” es un “cultismo” a mitad de camino con “frikada”, que no dice nadie…

Pero… ¡Es que aquí somos todos muy cultos!!

Así que, pudiendo poner bien las cosas… ¿por qué ponerlas mal?

Saludos
helq | 28/11/2011 at 12:18 | Permalink

Muy bueno el artículo @Macluskey, varias cosillas:
- En el segundo ejemplo: en la parte en la que dices que no tiene sentido usar números distintos al 0 y 1, escribes la potencia 3 pero sólo escribes dos productos. (aunque, pues no importa mucho)
- Cuál es la prueba de la Forma Normal Disyuntiva, es decir cómo se sabe que siempre se llega a ella.