REDUCCIÓN DE TERMINOS

REDUCCIÓN DE TERMINOS

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  , 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

Esta última ley no es tan evidente pero se ve claramente con 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	1	0	0	0	0
0	1	0	1	0	0	0	0
1	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0
1	0	1	1	0	1	1	1
1	1	0	1	1	0	1	1
1	1	1	1	1	1	1	1

• 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 F se obtiene complementando todas sus variables e intercambiando las operaciones de suma y producto, es decir:

F(x1, x2, … xn,+,* = F(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. Su tabla de la verdad es:

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

Por lo tanto, el siguiente código:

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

Quedaría:

if ($foo xor $bar) {

Ahora bien, si sabemos que ambas variables son booleanas, esto es exactamente lo mismo y según como hasta más legible:

if ($foo !== $bar) {

---

Nota:

Las leyes de álgebra de Boole están en estrecha relación con la lógica de predicados o de primer orden. Dos ejemplos: la ley de absorción es el modus ponens y las leyes de De Morgan también aplican a los conjuntos. Estas últimas son:

1. A ∪ B = A ∩ B
2. A ∩ B = A ∪ B

Veamos la segunda ley. Ésta nos dice que la intersección de todos los elementos que no son de A con la de todos los que no son de B equivale a la unión de todos los que no son de A con todos los elementos que no son de B. Su demostración es:

Se lee: Todo x tal que x no pertenece a la intersección de A con B