Álgebra booleana: historia, teoremas y postulados, ejemplos
El álgebra booleana o álgebra de Boole es la notación algebraica usada para el tratamiento de variables binarias. Cubre los estudios de toda variable que solo tenga 2 resultados posibles, complementarias y excluyentes entre sí. Por ejemplo, las variables cuya única posibilidad es verdadero o falso, correcto o incorrecto, encendido o apagado son la base del estudio del álgebra booleana.
El álgebra booleana constituye la base de la electrónica digital, lo cual la hace bastante presente en la contemporaneidad. Se rige por el concepto de las compuertas lógicas, donde las operaciones conocidas en el álgebra tradicional se ven notablemente afectadas.
Índice del artículo
El álgebra booleana fue introducida en 1854 por el matemático ingles George Boole (1815 – 1864), quien fue un autodidacta erudito de la época. Su inquietud surgió de una disputa existente entre Augustus De Morgan y William Hamilton, acerca de los parámetros que definen a este sistema lógico.
George Boole argumentó que la definición de los valores numéricos 0 y 1 corresponde, en el campo de la lógica, a la interpretación Nada y Universo respectivamente.
La intención de George Boole fue definir, a través de las propiedades del álgebra, las expresiones de la lógica proposicional necesarias para tratar con variables de tipo binario.
En 1854 se publican los apartados más significativos del álgebra booleana en el libro “Una investigación de las leyes del pensamiento sobre las que se fundamentan las teorías matemáticas de la lógica y probabilidad”.
Este curioso título sería resumido más adelante como “The laws of thought” (“Las leyes del pensamiento”). El título saltó a la fama debido a la inmediata atención que tuvo por parte de la comunidad matemática de la época.
En 1948 Claude Shannon la aplicó en el diseño de circuitos de conmutación eléctrica biestables. Esto sirvió como introducción a la aplicación del álgebra booleana dentro de todo el esquema electrónico-digital.
Los valores elementales en este tipo de álgebra son 0 y 1 ,que corresponden a FALSO y VERDADERO respectivamente. Las operaciones fundamentales en el álgebra booleana son 3:
– Operación AND o conjunción. Representada por un punto ( . ). Sinónimo del producto.
– Operación OR o disyunción. Representada por una cruz ( + ) .Sinónimo de la suma.
– Operación NOT o negación. Representada por el prefijo NOT (NOT A). También se conoce como complemento.
Si en un conjunto A se definen 2 leyes de composición interna denotadas como producto y suma ( . + ), se dice que la terna ( A . + ) es un álgebra booleana si y solo sí dicha terna cumple con la condición de ser un retículo distributivo.
Para definir un retículo distributivo se deben cumplir las condiciones de distribución entre las operaciones dadas:
. es distributiva con respecto a la suma + a . ( b + c ) = ( a . b ) + ( a . c )
+ es distributiva con respecto al producto. a + ( b . c ) = ( a + b ) . ( a + c )
Los elementos que componen al conjunto A deben ser binarios, teniendo así valores de universo o vacío.
Su mayor escenario de aplicación es la rama digital, donde sirve para estructurar los circuitos que componen a las operaciones lógicas involucradas. El arte de la simplicidad de circuitos en pro de optimizar los procesos, es el resultado de la correcta aplicación y practica del álgebra booleana.
Desde la elaboración de tableros eléctricos, pasando por la transmisión de datos, hasta llegar a la programación en diferentes lenguajes, podemos encontrar frecuentemente el álgebra de Boole en todo tipo de aplicaciones digitales.
Las variables booleanas son muy comunes en la estructura de la programación. Dependiendo del lenguaje de programación utilizado, existirán operaciones estructurales del código que usen dichas variables. Los condicionales y argumentos de cada lenguaje admiten variables booleanas para definir los procesos.
Existen teoremas que rigen las leyes lógicas estructurales del álgebra booleana. De igual forma se tienen postulados para conocer los resultados posibles en diferentes combinaciones de variables binarias, según la operación que se realice.
Suma (+)
El operador OR cuyo elemento lógico es la unión (U) queda definido para variables binarias de la siguiente manera:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Producto (.)
El operador AND cuyo elemento lógico es la intersección (∩) queda definido para variables binarias de la siguiente manera:
0 . 0 = 0
0 . 1 = 0
1 . 0 = 0
1 . 1 = 1
Opuesto (NOT)
El operador NOT cuyo elemento lógico es el complemento (X)’ queda definido para variables binarias de la siguiente manera:
NOT 0 = 1
NOT 1 = 0
Muchos de los postulados difieren de sus equivalentes en el álgebra convencional. Esto es debido al dominio de las variables. Por ejemplo, la adición de elementos universo en álgebra booleana (1 + 1) no puede arrojar el resultado convencional de 2, debido a que no pertenece a los elementos del conjunto binario.
Regla del cero y la unidad
Toda operación simple que involucre a un elemento con las variables binarias, queda definida:
0 + A = A
1 + A = 1
0 . A = 0
1 . A = A
Potencias iguales o idempotencia
Las operaciones entre variables iguales quedan definidas como:
A + A = A
A . A = A
Complementación
Toda operación entre una variable y su complemento queda definida como:
A + NOT A = 1
A . NOT A = 0
Involución o doble negación
Toda doble negación sera considerada como la variable natural.
NOT (NOT A ) = A
Conmutativa
A + B = B + A ; Conmutatividad de la suma.
A . B = B . A ; Conmutatividad del producto.
Asociativa
A + ( B + C ) = ( A + B ) + C = A + B + C ; Asociatividad de la suma.
A . ( B . C ) = ( A . B ) . C = A . B . C ; Asociatividad del producto.
Distributiva
A + ( B . C ) = ( A + B ) . ( A + C ) ; Distributividad de la suma con respecto al producto.
A . ( B + C ) = ( A . B ) + ( A + C ) ; Distributividad del producto con respecto a la suma.
Leyes de absorción
Existen muchas leyes de absorción entre múltiples referencias, algunas de las más conocidas son:
A . ( A + B ) = A
A . ( NOT A + B ) = A . B
NOT A ( A + B ) = NOT A . B
( A + B ) . ( A + NOT B ) = A
A + A . B = A
A + NOT A . B = A + B
NOT A + A . B = NOT A + B
A . B + A . NOT B = A
Teorema de Morgan
Son leyes de transformación, que manejan pares de variables que interactúan entre las operaciones definidas del álgebra booleana ( + . ).
NOT ( A . B ) = NOT A + NOT B
NOT ( A +B ) = NOT A . NOT B
A + B = NOT ( NOT A + NOT B )
A . B = NOT ( NOT A . NOT B )
Todos los postulados y teoremas poseen la facultad de la dualidad. Esto implica que al intercambiar las variables y operaciones se verifica la proposición resultante. Es decir ,que al intercambiar 0 por 1 y AND por OR o viceversa; se crea una expresión que también será completamente válida.
Por ejemplo si se toma el postulado
1 . 0 = 0
Y se le aplica la dualidad
0 + 1 = 1
Se obtiene otro postulado perfectamente válido.
El mapa de Karnaugh es un diagrama usado en el álgebra booleana para simplificar funciones lógicas. Consiste en un arreglo bidimensional similar a las tablas de verdad de la lógica proposicional. Los datos de las tablas de verdad pueden ser directamente plasmados en el mapa de Karnaugh.
El mapa de Karnaugh puede albergar procesos de hasta 6 variables. Para funciones con un mayor número de variables, se recomiendan el uso de software para simplificar el proceso.
Propuesto en 1953 por Maurice Karnaugh, se estableció como una herramienta fija en el campo del álgebra de Boole, debido a que su implementación sincroniza la potencialidad humana con la necesidad de simplificar expresiones booleanas, aspecto clave en la fluidez de los procesos digitales.
El álgebra booleana sirve para la reducción de puertas lógicas en un circuito, donde la prioridad es llevar la complejidad o nivel del circuito a su mínima expresión posible. Esto se debe al retardo computacional que cada puerta supone.
En el siguiente ejemplo observaremos la simplificación de una expresión lógica hasta su mínima expresión, valiéndose de los teoremas y postulados del álgebra booleana.
NOT ( AB + A + B ) . NOT ( A + NOT B )
NOT [ A( B + 1 ) + B ] . NOT ( A + NOT B ) ; Factorizando la A con factor común.
NOT [ A (1) + B ] . NOT ( A + NOT B ) ; Por teorema A + 1 = 1.
NOT ( A + B ) . NOT ( A + NOT B ) ; por teorema A . 1 = A
( NOT A . NOT B ) . [ NOT A . NOT (NOT B) ] ;
Por teorema de Morgan NOT ( A + B ) = NOT A . NOT B
( NOT A . NOT B ) . ( NOT A . B ) ; Por teorema de doble negación NOT (NOT A) = A
NOT A . NOT B . NOT A . B ; Agrupación algebraica.
NOT A . NOT A . NOT B . B ; Conmutatividad del producto A . B = B . A
NOT A . NOT B . B ; Por teorema A . A = A
NOT A . 0 ; Por teorema A . NOT A = 0
0 ; Por teorema A . 0 = 0
A . B . C + NOT A + A . NOT B . C
A . C . ( B + NOT B ) + NOT A ; Factorizando (A . C) con factor común.
A . C . (1) + NOT A ; Por teorema A + NOT A = 1
A . C + NOT A ; Por teorema regla del cero y la unidad 1 . A = A
NOT A + C ; Por ley de Morgan A + NOT A . B = A + B
Para esta solución debe extenderse la ley de Morgan para definir:
NOT (NOT A) . C + NOT A = NOT A + C
Debido a que NOT (NOT A) = A por involución.
NOT A . NOT B . NOT C + NOT A . NOT B . C + NOT A . NOT C hasta su mínima expresión
NOT A . NOT B . ( NOT C + C ) + NOT A . NOT C ; Factorizando (NOT A . NOT B) con factor común
NOT A . NOT B . ( 1 ) + NOT A . NOT C ; Por teorema A + NOT A = 1
(NOT A . NOT B) + (NOT A . NOT C) ; Por teorema regla del cero y la unidad 1 . A = A
NOT A (NOT B + NOT C) ; Factorizando NOT A con factor común
NOT A . NOT (B . C) ; Por leyes de Morgan NOT ( A . B ) = NOT A + NOT B
NOT [A + (B . C)] Por leyes de Morgan NOT ( A . B ) = NOT A + NOT B
Cualquiera de las 4 opciones en negrita representa una posible solución para reducir el nivel del circuito
( A . NOT B . C + A . NOT B . B . D + NOT A . NOT B ) . C
( A . NOT B . C + A . 0 . D + NOT A . NOT B ) . C ; Por teorema A . NOT A = 0
( A . NOT B . C + 0 + NOT A . NOT B ) . C ; Por teorema A . 0 = 0
( A . NOT B . C + NOT A . NOT B ) . C ; Por teorema A + 0 = A
A . NOT B . C . C + NOT A . NOT B . C ; Por distributividad del producto con respecto a la suma
A . NOT B . C + NOT A . NOT B . C ; Por teorema A . A = A
NOT B . C ( A + NOT A ) ; Factorizando (NOT B . C) con factor común
NOT B . C (1) ; Por teorema A + NOT A = 1
NOT B . C ; Por teorema regla del cero y la unidad 1 . A = A
- Álgebra booleana y sus aplicaciones J. Eldon Whitesitt. Compañía Editorial Continental, 1980.
- Mathematics and Engineering in Computer Science. Christopher J. Van Wyk. Institute for Computer Sciences and Technology. National Bureau of Standards. Washington, D. C. 20234
- Mathematics for Computer Science. Eric Lehman. Google Inc.
F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies. - Elements of Abstract Analysis. Mícheál O’Searcoid PhD. Department of mathematics. University college Dublin, Beldfield, Dublind.
- Introduction to Logic and to the Methodology of the Deductive Sciences. Alfred Tarski, New York Oxford. Oxford University press.