Álgebra de Boole

En matemáticas, electrónica digital e informática, el álgebra de Boole, también llamada álgebra booleana, es una estructura algebraica que esquematiza operaciones lógicas. derecha|280px

El álgebra booleana fue introducida por George Boole en su primer libro The Mathematical Analysis of Logic (1847) y expuesta más detalladamente en su An Investigation of the Laws of Thought (1854). Según Edward Vermilye Huntington, el término Boolean algebra fue sugerido por primera vez por Henry M. Sheffer en 1913, aunque Charles Sanders Peirce dio el título A Boolian Algebra with One Constant al primer capítulo de su The Simplest Mathematics en 1880.

El álgebra de Boole ha sido fundamental en el desarrollo de la electrónica digital y está incluida en todos los lenguajes de programación modernos. También se utiliza en teoría de conjuntos y la lógica.

El álgebra booleana es una rama del álgebra. Se diferencia del álgebra elemental en dos aspectos. Primero, los valores de las variables son los valores de verdad: verdadero y falso, normalmente denotados por 1 y 0, mientras que en álgebra elemental los valores de las variables son números. En segundo lugar, el álgebra booleana utiliza operadores lógicos como la conjunción (y), denotada como ∧, la disyunción (o), denotada como ∨, y la negación (no), denotada como ¬. El álgebra elemental, por otro lado, utiliza operadores aritméticos como la suma, la multiplicación, la resta y la división. Por tanto, el álgebra de Boole es una modalidad formal de describir operaciones lógicas de la misma manera que el álgebra elemental describe operaciones numéricas.

Historia derecha|240px Se denomina así en honor a George Boole (1815-1864), matemático inglés autodidacta que fue el primero en definirla como parte de un sistema lógico, inicialmente en un pequeño folleto de 1847, The Mathematical Analysis of Logic, publicado en respuesta a una controversia en curso entre Augustus De Morgan y sir William Rowan Hamilton. El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. Más tarde fue extendido como un libro más importante: An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities (también conocido como An Investigation of the Laws of Thought o simplemente The Laws of Thought), publicado en 1854.

En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1948. Esta lógica se puede aplicar a dos campos:

Al análisis, porque es una forma concreta de describir cómo funcionan los circuitos. Al diseño, ya que teniendo una función se aplica dicha álgebra para poder desarrollar una implementación de la función.

Definición

Dado un conjunto en el que se han definido dos leyes de composición interna: suma lógica y producto lógico . La estructura es un álgebra de Boole si y solo si es un Retículo distributivo y complementario, esto es:

es distributiva respecto a :

es distributiva respecto a

Basándose en esta definición se determina lo siguiente.

Principios Dado un conjunto: formado cuando menos por los elementos: en el que se ha definido:

Una operación unaria interna, que llamaremos complemento:

En esta operación definimos una aplicación que, a cada elemento a de , le asigna un b de .

Para todo elemento a en , se cumple que existe un único b en , tal que b es el complemento de a.

La operación binaria interna, que llamaremos suma:

por la que definimos una aplicación que, a cada par ordenado (a, b) de , le asigna un c de .

Para todo par ordenado (a, b) en , se cumple que existe un único c en , tal que c es el resultado de sumar a con b.

La operación binaria interna, que llamaremos producto:

Con lo que definimos una aplicación que, a cada par ordenado (a, b) de , le asigna un c de .

Para todo par ordenado (a, b) en , se cumple que existe un único c en , tal que c es el resultado del producto a y b.

Dada la definición del álgebra de Boole como una estructura algebraica genérica, según el caso concreto de que se trate, la simbología y los nombres de las operaciones pueden variar.

Axiomas necesarios Diremos que este conjunto y las operaciones así definidas: son un álgebra de boole, si cumple los siguientes axiomas:

1a: La ley asociativa de la suma:

2a: Existencia del elemento neutro para la suma:

3a: La ley conmutativa de la suma:

4a: Ley distributiva de la suma respecto al producto:

5a: Existe elemento complementario para la suma:

1b: La ley asociativa del producto:

2b: Existencia del elemento neutro para el producto:

3b: La ley conmutativa del producto:

4b: Ley distributiva del producto respecto a la suma:

5b: Existe elemento complementario para el producto:

Teoremas fundamentales Partiendo de los cinco axiomas anteriores, se pueden deducir y demostrar los siguientes teoremas fundamentales:

6a: Ley de idempotencia para la suma:

7a: Ley de dominación para la suma:

8a: Ley de identidad para la suma:

9a: Ley de absorción para la suma

10a: Ley de De Morgan para la suma:

6b: Ley de idempotencia para el producto:

7b: Ley de dominación para el producto:

8b: Ley de identidad para el producto:

9b: Ley de absorción para el producto

10b: Ley de De Morgan para el producto:

11: Ley de involución:

12: Ley del complemento:

13: Principio del tercero excluido:

14: Principio de no contradicción:

Orden en el álgebra de Boole Sea: un álgebra de Boole, sean a, b dos elementos del conjunto, podremos decir entonces que a antecede a b y lo denotamos:

si se cumple alguna de las siguientes condiciones:

Estas cuatro condiciones se consideran equivalentes y el cumplimiento de una de ellas implica necesariamente el cumplimiento de las demás. Definiendo un conjunto parcialmente ordenado.

Si se cumple que:

Para los valores a, b de , que cumplen que a antecede a b, o que b antecede a a, se dice que a y b son comparables.

Si se cumple que:

Para los valores a, b de , que cumplen que a no antecede a b, y que b no antecede a a, se dice que a y b son no comparables.

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 suma con los de producto, y de con .

{| align="left" class="wikitable" border="1" |- bgcolor="#f0f5fa" ! ! Adición ! Producto |----- align="center" | 1 || || |----- align="center" | 2 || || |----- align="center" | 3 || || |----- align="center" | 4 || || |----- align="center" | 5 || || |----- align="center" | 6 || || |----- align="center" | 7 || || |----- align="center" | 8 || || |----- align="center" | 9 || ||

Con una estructura similar y las operaciones y los conjuntos permutados.

Otras formas de notación del álgebra de Boole En Lógica binaria se suele emplear la notación , común en la tecnología digital, siendo la forma más usual y la más cómoda de representar.

Por ejemplo las leyes de De Morgan se representan así:

Cuando el álgebra de Boole se emplea en electrónica, suele emplearse la misma denominación que para las puerta lógica AND (Y), OR (O) y NOT (NO), ampliándose en ocasiones con X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-NOR (equivalencia). las variables pueden representarse con letras mayúsculas o minúsculas, y pueden tomar los valores {0, 1}.

Empleando esta notación las leyes de De Morgan se representan:

En su aplicación a la lógica se emplea la notación y las variables pueden tomar los valores {F, V}, falso o verdadero, equivalentes a {0, 1}

Con la notación lógica las leyes de De Morgan serían así:

En el formato de Teoría de conjuntos el Álgebra de Boole toma el aspecto:

En esta notación las leyes de De Morgan serían así:

Otra forma en la álgebra de conjuntos del Álgebra de Boole, las leyes de De Morgan serían así:

Desde el punto de vista práctico existe una forma simplificada de representar expresiones booleanas. Se emplean apóstrofos (') para indicar la negación, la operación suma (+) se representa de la forma normal en álgebra, y para el producto no se emplea ningún signo, las variables se representan, normalmente con una letra mayúscula, la sucesión de dos variables indica el producto entre ellas, no una variable nombrada con dos letras.

La representación de las leyes de De Morgan con este sistema quedaría así, con letra minúsculas para las variables:

y así, empleando letras mayúsculas para representar las variables:

Todas estas formas de representación son correctas, se utilizan de hecho, y pueden verse al consultar bibliografía. La utilización de una u otra notación no modifica el álgebra de Boole, solo su aspecto, y depende de la rama de las matemáticas o la tecnología en la que se esté utilizando para emplear una u otra notación.

Estructuras algebraicas que son álgebra de Boole

Hay numerosos casos de distintos análisis de estructuras algebraicas que corresponden al álgebra de Boole, aunque en apariencia son muy diferentes, su estructura es la misma. Vamos a ver algunos de ellos, con el propósito de hacer palpable las similitudes en la estructura y los distintos ámbitos de aplicación y distinta terminología para referirse a las operaciones o a las variables.

Lógica binaria

La lógica binaria, basada en los ceros y los unos, posiblemente la forma más conocida de este álgebra, que en ocasiones da lugar a la interpretación que el álgebra de Boole es la lógica binaria exclusivamente. Así el conjunto en este caso está formado por dos elementos {0,1}, o {F, V}, o {no, sí}, dos valores contrapuestos, que son las dos posibles alternativas entre dos situaciones posibles, aquí, sin pérdida de la generalidad, tomaremos el conjunto: {0,1} como ya hemos dicho:

Donde:

La operación unaria interna, que llamaremos negación:

La operación unaria interna negación, definimos una aplicación que a cada elemento a de {0,1}, le asigna un b de {0,1}.

Para todo elemento a en {0,1}, se cumple que existe un único b en {0,1}, tal que b es la negación de a. Como se ve en la tabla.

La operación binaria interna, que llamaremos suma, circuito de interruptores en paralelo:

Con la operación suma definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

Para todo par ordenado (a,b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de sumar a con b.

la operación binaria interna, que llamaremos producto, circuito de interruptores en serie:

Con la operación producto definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado del producto a y b. Como se puede ver en la tabla.

Axiomas Así es un álgebra de Boole al cumplir los siguientes axiomas: