Algebra de Boole (1)

Ya lo sé... sí, la palabra álgebra asusta, muchos lectores ni siquiera pincharán en un enlace donde aparezca ese término, por miedo a encontrar un motón de conceptos incomprensibles como teorema, axioma, postulado, y otras lindezas.

He de decir que no se trata de un tema trivial, pero dentro de lo que se refiere a la matemática, tal vez sea uno de los más simples y curiosos. Y sobre todo, para los programadores, uno de los más interesantes y útiles.

¿Qué es la lógica?

Según el diccionario:

Ciencia que expone las leyes, modos y formas del conocimiento científico.

Esto está bien, al menos para los que queremos resolver problemas mediante ordenadores, ya que nos ofrece una forma científica de afrontar los problemas que impliquen alguna forma de "pensamiento artificial".

Es decir, si existe una forma racional de afrontar problemas racionales, una forma de meta-raciocinio, (y conseguimos comprenderla y usarla), nos será posible crear programas que resuelvan problemas complejos (y por supuesto, simples).

Tal cosa existe, y las leyes son simples y fáciles de comprender y aplicar. En este artículo intentaremos aproximarnos a las bases para construir, si es posible, programas pensantes.

Pero no estamos hablando de creatividad ni de inventiva, esa parte del pensamiento humano no está sistematizada, y se escapa, (al menos por ahora) de nuestras perspectivas. Hablamos de pensamiento lógico, aquel que nos permite llegar a conclusiones verdaderos a partir de datos verdaderos, y no sólo de una forma experimental, sino para cualquier estado inicial posible.

Pero, recapitulemos.

Historia

La lógica, como todas las disciplinas matemáticas, es un invento humano.

Para encontrar a los pioneros de la lógica debemos remontarnos a Aristóteles, que fue el primero en formular las reglas que definen el pensamiento. De hecho, a partir de él deberemos avanzar hasta el siglo XIX para encontrar alguna aportación nueva.

A Aristóteles de debemos términos como "silogismo", y las bases del razonamiento lógico.

En el siglo XIX, George Boole desarrolló una teoría que se basa en representar las proposiciones lógicas mediante símbolos y asignar valores a las variables de entrada y salida, y que permite crear un álgebra tal que es posible operar usando tales símbolos y valores para obtener resultados correctos.

Este álgebra es una herramienta matemática que, aplicada al pensamiento lógico, permite obtener conclusiones verdaderas a partir de datos verdaderos, del mismo modo que otras disciplinas matemáticas, aplicadas a la física, permiten hacer predicciones sobre el mundo real.

En el álgebra de Boole, tanto los datos como las conclusiones sólo pueden tomar dos valores: verdadero y falso, y, como veremos, el conjunto de proposiciones es muy reducido. Sin embargo, las posibilidades de este modelo de álgebra son sorprendentes.

Valores

En el álgebra de Boole, cualquier dato sólo puede tomar dos valores: verdadero, o '1' y falso o '0'.

Proposiciones

Sólo existen tres operaciones o proposiciones:

• O, más usado como OR, usa los símbolos '+' y '^', y en conjuntos corresponde con la operación de Union.
• Y, más usado como AND, usa los símbolos '·' y 'v', y en conjuntos corresponde con la operación de Interseccion.
• No, más usado como NOT, usa el símbolo '~' y una comilla (') o un superrayado. Corresponde con la negación.

En este artículo usaremos los símbolos '+', '·' y la comilla.

Postulados

Los postulados son proposiciones que se toman como punto de partida para la demostración de teoremas, sin necesidad de que tengan que ser deducidos a partir de otros enunciados, y a menudo, indemostrables.

Por ejemplo, en la geometría de Euclides se parte de cinco postulados desde los que se desarrollan todos los teoremas. El primero de estos postulados dice: "Por dos puntos diferentes sólo se puede trazar una línea recta".

No es necesario demostrar los postulados, puesto que se dan como verdaderos y se usan como cimientos para levantar todo el resto de la matemática.

Los postulados del álgebra de Boole son:

1. Ley conmutativa. Que se cumple tanto para la operación OR como para la AND:
   a+b=b+a
a·b=b·a
2. Ley de identidad o de elementos neutros. El 0 es neutro para la operación OR y el 1 para la AND:
   0+a=a
1·a=a
3. Ley distributiva. Cada operación es distributiva con respecto a la otra:
   a·(b+c)=a·b+a·c
a+b·c=(a+b)·(a+c)
4. Ley del complementario. Para cada valor existe un complementario, de modo que se cumple:
   a+a'=1
a·a'=0

Dualidad

Todos los postulados tienen dos formas, y si los analizamos, veremos que cada una de ellas se puede obtener a partir de la otra, intercambiando los '1' por '0' y las operaciones '+' por '·'. Creo que está claro que, en el caso de variables, intercambiar '1' por '0' equivale a aplicar el operador de negación.

Por ejemplo:

a+b=b+a -> a'·b'=b'·a'
0+a=a -> 1·a'=a'
a·(b+c)=a·b+a·c -> a'+(b'·c')=(a'+b')·(a'+c')
a+a'=1 -> a'·a=0

Teoremas

Los teoremas tienen la misma forma que los postulados. La diferencia es que los teoremas pueden ser deducidos y demostrados a partir de los postulados.

Teorema 1

Para cada elemento se verifica que a+1=1 y por dualidad, también que a·0=0

La demostración es la siguiente:

1. Postulado 4: a+a'=1
2. Postulado 2: a+(a'·1)=1
3. Postulado 3: (a+a')·(a+1)=1
4. Postulado 4: 1·(a+1)=1
5. Postulado 2: a+1=1

Teorema 2

Para cada elemento se verifica que a+a=a y por dualidad, también que a·a=a

La demostración es la siguiente:

1. Postulado 2: a+0=a
2. Postulado 4: a+(a·a')=a
3. Postulado 3: (a+a)·(a+a')=a
4. Postulado 4: (a+a)·1=a
5. Postulado 2: a+a=a

Teorema 3: Asociatividad

Las dos operaciones del álgebra de Boole son asociativas.

Para cada elemento se verifica que a+(b+c)=(a+b)+c y por dualidad, también que a·(b·c)=(a·b)·c

Obviaremos las demostraciones a partir de ahora, si quieres, puedes demostrar los teoremas usando los postulados o los teoremas previamente demostrados.

Teorema 4

Para cada elemento se verifica que a·[(a+b)+c]=a y por dualidad, también que a+[(a·b)·c]=a

Teorema 5

Para cualquier elemento se verifica que a+(a·b)=a y por dualidad, también que a·(a+b)=a

Teorema 6

Para cada elemento se verifica que a"=a

Teorema 7: Leyes de Morgan

Para cada par de elementos cualquiera se verifica que (a+b)'=a'·b' y por dualidad: (a·b)'=a'+b'

El teorema se cumple también para trios, cuartetos y en general, para expresiones con cualquier número de elementos. Por ejemplo: (a+b+c)'=a'·b'·c'

Este teorema es muy importante en el álgebra de Boole, ya que permite simplificar expresiones complejas.

Por ejemplo:

[(a'+b)·(a+c')]'=

(a'+b)'+(a+c')'=

a"·b'+a'·c"=

a·b'+a'·c=

Funciones

Una función booleana es la representación de una variable cuyo valor depende de los valores de otras bariables binarias.

En programación, a veces, nos encontramos con este tipo de funciones dentro de expresiones if:

...
   if((x != 0 && y < 10) || (x > 10 && y == 0)) ...

Ya sabemos que las condiciones de un if son siempre expresiones booleanas, que serán verdaderas o falsas. Con expresiones simples no solemos tener problemas, a fin de cuentas, son expresiones lógicas, y se pueden resolver mentalmente. Pero cuando se trata de expresiones complejas, con muchas variables o muchos términos, a veces intuímos que deberían poder simplificarse, pero no sabemos cómo.

En próximos puntos veremos como reducir o simplificar funciones booleanas, pero antes, veremos algunos detalles que nos facilitarán esa tarea.

Tablas de verdad

Una tabla de verdad es, como su nombre indica, una tabla. En esa tabla se representan todos los valores posibles de una función, para todas las combinaciones posibles de sus variables de entrada.

En álgebra de Boole es posible representar las tablas de verdad porque el dominio de las variables (conjunto de todos los valores posibles de esas variables) es finito, y además pequeño (dos valores).

Por ejemplo, para la función anterior tenemos las siguientes variables:

• A :> x !=0
• B :> y < 10
• C :> x > 10
• D :> y == 0

La función se puede representar como: A·B+C·D.

La tabla de verdad de esta función sería:

Para cualquier función booleana siempre podremos representar su tabla de verdad.

Maxterms y minterms

La teoría que se explica a partir de ahora se usa para crear circuitos lógicos en electrónica digital. Pero creo que tiene aplicaciones prácticas en informática, y vamos a ver cómo usarla en nuestro día a día.

De forma recíproca, a partir de cualquier tabla de verdad, podremos obtener una función.

Existen dos formas especiales de representar cualquier función boolena. A estas formas se les llama canónicas. Para que una función sea canónica estará compuesta por términos en los que aparecen todas las variables:

• Ecuación minterms: compuesta por la suma de los productos de las variables de entrada cuyas combinaciones hacen que el valor de la función sea 1. Las variables de entrada con valor 0 serán negadas.
• Ecuación maxterms: compuesta por el producto de las sumas de las variables de entrada cuyas combinaciones hacen que el valor de la función sea 0. Las variables de entrada con valor 1 serán negadas.

Veamos un ejemplo. Obtendremos las ecuaciones canónicas de la tabla de verdad anterior.

Ecuación minterms: f = A'·B'·C·D+A'·B·C·D+A'·B·C·D+A·B·C'·D'+A·B·C'·D+A·B·C·D'+A·B·C·D

Ecuación maxterms: f = (A+B+C+D)·(A+B+C+D')·(A+B+C'+D)·(A+B'+C+D)·(A+B'+C+D')·(A+B'+C'+D)·(A'+B+C+D)·(A'+B+C+D')·(A'+B+C'+D)

Hay una forma alternativa de representar estas funciones, indicando el conjunto de términos minterms o maxterms que definen la función. Así, la función anterior se puede representar como:

Ecuación minterms: f(A,B,C,D) = m(3,7,11,12,13,14,15)

Podemos usar los postulados y teoremas para simplificar estas funciones, pero veremos que hay métodos gráficos que nos ayudarán a hacerlo mucho más fácilmente.