Álgebra de Boole

Keywords: Álgebra de Boole, 1938, Anillo (matemáticas), Circuitos de conmutación, Claude Shannon, Complemento de un conjunto, Computación, Conjunto de partes, Conjunto vacío

En matemáticas y computación, el Álgebra de Boole, o Retículas booleanas, 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 la descripción de circuitos también se emplean NAND (no Y), NOR (no O) y XOR (O exclusivo). 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 sobre la expresión que se pretende negar.

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.

Definición

Un álgebra de Boole es una retícula (A, , ) (considerada como una estructura algebráica) con las siguientes cuatro propiedades adicionales:

1. Acotada inferiormente: Existe un elemento 0, tal que a 0 = a para todo a perteneciente a A.
2. Acotada superiormente: Existe un elemento 1, tal que a 1 = a para todo a perteneciente a A.
3. Distributiva: Para todo a, b, c pertenecientes a A, (a b) c = (a c) (b c).
4. Con complemento: Para cualquier a perteneciente a A existe un elemento ¬a perteneciente a A tal que a ¬a = 1 y a ¬a = 0.

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

a ≤ b si y sólo si a = a b

(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

x ¬x = 0 and x ¬x = 1

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.

Ejemplos

• El álgebra de Boole más importante tiene sólo dos elementos, 0 y 1, y se define por las reglas

    0  1      0  1
       ----         ----
   0 | 0  1     0 | 0  0
   1 | 1  1     1 | 0  1
 

Tiene aplicaciones en la lógica, donde 0 se interpreta como "falso", 1 como "verdadero", como "y", como "o", y ¬ es "no". Las expresiones que involucran variables y operadores booleanos representan proposiciones, y se puede demostrar que dos expresiones son equivalentes usando los axiomas citados anteriormente si y sólo si las correspondientes proposiciones son lógicamente equivalentes.

El álgebra de Boole de dos elementos también se utiliza para diseño de circuitos en ingeniería electrónica; aquí 0 y 1 representan los dos posibles estados en circuitos digitales, típicamente un voltaje alto y uno bajo.

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 conportamiento de entrada-salida puede ser expresado mediante una expresión booleana.

El álgebra de Boole de dos elementos también es importante en la teoría general de las álgebras de Boole, porque una ecuación que implica varias variables es cierta en todas las álgebras booleanas si y sólo si es cierta en un álgebra booleana de dos elementos (lo cual siempre puede ser verificado utilizando el algoritmo trivial de fuerza bruta). Esto puede aplicarse para demostrar que las siguientes leyes (Teoremas del consenso) son válidos en todas las álgebras booleanas:

(a b) (¬a c) (b c) = (a b) (¬a c)

(a b) (¬a c) (b c) = (a b) (¬a c)

• El conjunto de partes de un conjunto dado S forma un álgebra de Boole con las dos operaciones = unión and = intersección. El elemento mínimo 0 es el conjunto vacío y el elemento máximo 1 es el propio conjunto S.

• El conjunto formado por todos los subconjuntos de S que son finitos o cofinitos es un álgebra de Boole.

• Para todo número natural n, el conjunto de todos sus divisores positivos forma una retícula distributiva si definimos a ≤ b como a divide a b. Esta retícula es un álgebra de Boole se y sólo si n es libre de cuadrados. El elemento mínimo 0 de este álgebra es el número natural 1; el elemento máximo 1 de este álgebra booleana 1 es el número natural n.

• Otros ejemplos de álgebras de Boole surgen de losespacio s topológicos: si X es un espacio topológico, entonces la colección de todos los subespacios de X que son tanto abiertos como cerrados forman un álgebra booleana con las operaciones = unión y = intersección.

• Si R es un anillo y definimos el conjunto de idempotentes centrales como

A = { e en R : e² = e y ex = xe para todo x en R }

entonces el conjunto A se convierte en un álgebra booleana con las operaciones e f = e + f − ef y e f = ef.

Ver también

• Lógica binaria
• Tablas de verdad
• Circuitos de conmutación
• Sistema digital
• Puerta lógica

Boole Álgebra de Boole

Keywords: Álgebra de Boole, 1938, Anillo (matemáticas), Circuitos de conmutación, Claude Shannon, Complemento de un conjunto, Computación, Conjunto de partes, Conjunto vacío