Reducción de ecuaciones mediante álgebra de Boole

 Sánchez Cruz Brandon

Cuando estamos repasando código podemos encontrarnos expresiones booleanas en condiciones lógicas más complejas de lo necesario que dificultan entender lo que el código hace. Esto puede ser debido a que la persona no tiene los conocimientos necesarios para hacerlo mejor (en esta profesión uno se encuentra hasta biólogos sin mayor interés en la profesión que el salario) o al constreñimiento que sufrió el programador cuando desarrolló el código que estamos repasando. Por lo tanto, puede ser nuestro propio código el que incurra en esos errores que ahora, con más calma, descubrimos y nos preguntamos en qué estaríamos pensando cuando hicimos esos whiles y esos ifs.

Para reducir el total de términos de una expresión booleana existen técnicas como los mapas de Karnaugh o el método de Quine-McCluskey pero en programación generalmente es suficiente con las leyes del álgebra de Boole. Teniendo en cuenta que la condición lógica AND es el producto booleano, OR es la suma y NOT el complemento (que se puede representar con los símbolos    o ¬), las leyes son:

• Idempotencia:
  1. x + x = x
  2. x * x = x
• Doble complemento:
  1. ¬x (doble negación) = x
• Identidad respecto a la suma y el producto o elementos neutros de la suma y del producto:
  1.  x + 0 = x
  2. x * 1 = x
•  Maximalidad de los elementos 1 y 0:
  1. x + 1 = 1
  2. x * 0 = 0
• Leyes asociativas respecto de la suma y del producto:
  1. x + (y + z) = (x + y) + z
  2. x * (y * z) = (x * y) * z
• Leyes distributivas respecto de la suma y del producto:
1. x + y * z = (x + y) * (x +z)
2. x * (y + z) = x * y + x * z

La segunda resulta familiar por ser la propiedad distributiva de la multiplicación respecto a la suma que ya conocemos del álgebra elemental. En cambio, la primera no es tan evidente pero se ve claramente su validez mediante su tabla de verdad:

x	y	z	y*z	x + y	x + z	x + (y*z)	(x+y)* (x+z)
0	0	0	0	0	0	0	0
0	0	1	0	0	1	0	0
0	1	0	0	1	0	0	0
1	0	0	0	1	1	1	1
0	1	1	1	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

ds

• Leyes de De Morgan:
  1. x + y = x * y
  2. x * y = x + y

También las podemos comprobar mediante sus tablas de verdad:

x	y	x	y	x+y	x+y	x*y
0	0	1	1	0	1	1
0	1	1	0	1	0	0
1	0	0	1	1	0	0
1	1	0	0	1	0	0

Estas leyes se pueden generalizar a más de dos variables. Además, podemos ver que x * y ≠ x*y

• Ley de absorción:
  1. x(x + y) = x

Su tabla de verdad es:

x	y	x + y	x(x + y)
0	0	0	0
0	1	1	0
1	0	1	1
1	1	1	1

La ley de absorción también se concluye aplicando las leyes anteriormente mencionadas:

x(x + y) = (x + 0)(x + y) = x + 0*y = x + 0 = x

Aplicando las leyes booleanas se deducen las siguientes propiedades:

• x + xy = x
• x + xy = x + y
• x + x = 1
• x * x = 0

Si bien las dos últimas son evidentes, para las dos primeras podemos crear sus correspondientes tablas de verdad en caso de duda.

También es conveniente conocer un teorema acerca del complemento de una función booleana y  para ello hay que explicar primero qué es una función booleana. Una función booleana es algo tan sencillo como las tablas de verdad que hemos visto antes: dadas unas variables x, y, z… se obtiene un resultado F. El grado de la función es el número de variables. Este es un ejemplo de una función grado dos F2→F:

x	y	F(x, y)
0	0	0
0	1	1
1	0	1
1	1	1

La expresión booleana que produce tal resultado F es: x* y + x*y + x*y Aunque cómo encontrar la expresión booleana a partir de una tabla de verdad es otro tema. Ahora que ya sabemos qué es una función booleana, dejemos esta función de momento a un lado y volvamos entonces al teorema:

El complemento de una función booleana E se obtiene complementando todas sus variables e intercambiando las operaciones de suma y producto, es decir:

E(x1, x2, … xn,+,* = E(x1, x2, …,xn, *, +)

Por ejemplo el complemento de la función anterior F se podría expresar como:

F = (¬x + y) * (x + ¬y) * (x + y) =  A + B + C = A + B + C = (x+y) * (x*y) * (x*y)

Con los minterm y maxterm también se acaba viendo que toda función booleana puede expresarse tanto como un conjunto de minterms multiplicados, como un conjunto de maxterms sumados. Aunque los minterm, maxterm y las formas canónicas también podrían ayudarnos, con las leyes anteriores, propiedades y el último teorema no debería haber código que se nos resista a ser simplificado. Veamos algunos ejemplos de despistes que hacen el código poco legible y como quedarían simplificados:

if (($foo && myFunction()) || ($foo && $bar)) {

Con la ley distributiva quedaría: if ($foo && (myFunction() || $bar))


if (!($foo || $bar || myFunction())) {

La expresión booleana de este if sería x + y + z

Aplicando la propiedad asociativa: x + (y + z)

Reemplazando por a: x + a

Aplicando la ley de De Morgan: x * a

Deshaciendo el reemplazo: x * (y + z)

Otra vez De Morgan: x * y * z

Así que el if original quedaría if (!$foo && !$bar && !myFunction()) {

El operador lógico XOR, aunque no forma parte de las operaciones booleanas básicas, tiene tantas utilidades que está en toda clase de circuitos y lenguajes de programación. Su función booleana es:

XOR = x*y + y*x

Devuelve 1 sólo cuando x e y tienen valor diferente, o dicho de otro modo, sólo cuando una de las dos es cierta, pero no si lo son ambas. Su tabla de la verdad es:

x	y	XOR(x, y)
0	0	0
0	1	1
1	0	1
1	1	0

Referencias

Iglesias Castán, V. (2017, 20 de marzo). Simplificación de expresiones booleanas mediante álgebra de Boole. Víctor Iglesias. https://www.victoriglesias.net/simplificacion-de-expresiones-booleanas-mediante-algebra-de-boole/