Álgebra de Boole (también llamada Retículas booleanas) en matemáticas y computación, son estructuras algebraicas que "capturan la esencia" de las operaciones lógicas Y, O y NO, así como el conjunto de operaciones unión, intersección y complemento.
Se denomina así en honor a George Boole, matemático inglés que fue el primero en definirla como parte de un sistema lógico a mediados del siglo XIX. Específicamente, el álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. En la actualidad el álgebra de Boole se aplica de forma generalizada en diseño electrónico. Se aplicó por primera vez en circuitos de conmutación eléctrica biestables por Claude Shannon en 1938.
Los operadores del álgebra de Boole pueden representarse de varias formas. A menudo se representan simplemente como AND (Y), OR (O) y NOT (NO). En electrónica digital (véase puerta lógica) también se emplean la X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-NOR (equivalencia) . En matemáticas a menudo se utiliza + en lugar de OR y · en lugar de AND, debido a que estas operaciones son de alguna manera análogas a la suma y el producto en otras estructuras algebraicas, y NOT se representa como una línea o una comilla sobre la expresión que se pretende negar (NO A sería Ā o A').
Se comenzará el estudio del Algebra de Boole introduciendo el concepto de clase. Se define como clase el total de los elementos que cumplen las características definidas por un criterio de pertenencia. En general, una subclase S de una clase dada C, es una clase cuyos elementos pertenecen a la clase C. A su vez, la clase C podría ser una subclase de una clase más amplia que contuviera todos los elementos de C juntos con otros elementos distintos. E inversamente, la clase S puede contener sus propias subclases. Una clase especialmente importante es la denominada clase de referencia o clase universal, que es aquella que comprende a todos los elementos bajo estudio. Una vez definida la clase universal, se puede definir la clase complementaria de una clase cualquiera A perteneciente a la universal, como la clase que encierra a todos los elementos de la clase universal excepto aquellos que están contenidos en la clase A. Finalmente, se definir la clase vacía como la clase complementaria de la clase universal. De acuerdo con la definición de clase universal, la clase vacía es aquella que no contiene ningún elemento.
En este artículo se empleará la notación común con para el operador AND, para el operador OR y ¬ (o ~) para el operador NOT.
Un álgebra de Boole es una retícula (A, , ) (considerada como una estructura algebraica) con las siguientes cuatro propiedades adicionales:
De esos axiomas se desprende que el elemento mínimo 0, el elemento máximo 1, y el complemento ¬a de un elemento a están únicamente determinados.
Como cualquier retícula, un Álgebra Booleana A, , ) da lugar a un conjunto parcialmente ordenado (A, ≤) definiendo
(que equivale a b = a b).
De hecho, puede definirse un álgebra de Boole como una retícula distributiva A, ≤) (considerada como un conjunto parcialmente ordenado) con elemento mínimo 0, elemento máximo 1, en la que cada elemento x tiene un complemento ¬x tal que
Aquí y se usan para denotar el mínimo (intersección) y el máximo (unión) de dos elementos. De nuevo, si existe el complemento está únicamente determinado.
Se definirán las operaciones básicas del Algebra de Boole, describiéndose a continuación su aplicación a los circuitos lógicos.
Unión o adición
La unión de dos clases A y B se define como la clase formada por todos los elementos de la clase A, todos los elementos de la clase B, y ningún otro elemento. La clase unión se representa mediante la simbología matemática:
A B
Intersección o producto
La intersección de dos clases A y B se define como la clase formada por todos los elementos que pertenecen simultáneamente a las clases A y B. La clase intersección se puede representar mediante los símbolos:
A B
Complementación
La clase complementaria de una dada ya ha sido definida. Las notaciones simbólicas empleadas para representar el complementario de A son: A' o bien ¬ A. Aquí se mencionarán dos propiedades importantes de la complementación, que se pueden comprobar fácilmente:
Principio de dualidad
El concepto de dualidad permite formalizar este hecho: a toda relación o ley lógica le corresponderá su dual, formada mediante el intercambio de los operadores unión con los de intersección, y de los 1 con los 0.
Adición | Producto | |
---|---|---|
1 | A + A' = 1 | A • A' = 0 |
2 | A + 0 = A | A • 1 = A |
3 | A + 1 = 1 | A • 0 = 0 |
4 | A + A = A | A • A = A |
5 | A + B = B + A | A • B = B • A |
6 | A + (B + C) = (A + B) + C | A • (B • C) = (A • B) • C |
7 | A + B • C = (A + B) • (A + C) | A • (B + C) = A • B + A • C |
8 | A + A • B = A | A • (A + B) = A |
9 | (A + B)' = A' • B' | (A • B)' = A' + B' |
0 1 0 1 ---- ---- 0 | 0 1 0 | 0 0 1 | 1 1 1 | 0 1
Los circuitos se describen mediante expresiones que contienen variables, y dos de estas expresiones son iguales si y sólo si los correspondientes circuitos tienen el mismo comportamiento de entrada y salida. Además, cada posible comportamiento de entrada-salida puede ser expresado mediante una expresión booleana.
entonces el conjunto A se convierte en un álgebra booleana con las operaciones e f = e + f − ef y e f = ef.