Álgebra de Boole

De Wikipedia, la enciclopedia libre

Álgebra de Boole (también llamada Retículas booleanas) en informática y matemática, 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ática 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 define 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.

[editar] Definición

El álgebra de Boole es una retícula (A, , ) (considerada como una estructura algebraica) 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, el Á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 el á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

Adición Producto

1

       A • A' = 0        A + A' = 1

2

       A • 1 = A         A + 0 = A

3

       A • 0 = 0         A + 1 = 1 
       

[editar] Operaciones

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:

• A + A' =U (clase universal)
• A ^ A' = 0 (clase vacía)

[editar] Leyes fundamentales

1. El resultado de aplicar cualquiera de las tres operaciones definidas a variables del sistema booleano resulta en otra variable del sistema, y este resultado es único.
2. Ley de idempotencia: A + A = A | A • A = A
3. Ley de involución: (A')' = A
4. Ley conmutativa: A + B = B + A | A • B = B • A
5. Ley asociativa: A + (B + C) = (A + B) + C | A • (B • C) = (A • B) • C
6. Ley distributiva: A + B • C = (A + B) • (A + C) | A • (B + C) = A • B + A • C
7. Ley de absorción: A + A • B = A | A • (A + B) = A
8. Ley de De Morgan: (A + B)' = A' • B' | (A • B)' = A' + B'

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.

[editar] 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 con respecto al voltaje: 0=no conduce(circuito abierto);1=conduce(circuito cerrado).

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.

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 el á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 el á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 el álgebra de Boole si 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 del álgebra de Boole surgen de los espacios 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 el álgebra booleana con las operaciones e f = e + f − ef y e f = ef.

• 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 el álgebra booleana con las operaciones e f = e + f − ef y e f = ef.

[editar] Véase también

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