Álgebra de Boole

Álgebra de Boole (también llamada álgebra booleana) en informática y matemática, es una estructura algebraica que esquematiza las operaciones lógicas Y, O , NO y SI (AND, OR, NOT, IF), así como el conjunto de operaciones unión, intersección y complemento.

Se denomina así en honor a George Boole (2 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés autodidacta, que fue el primero en definirla como parte de unsistema lógico, inicialmente en un pequeño folleto: The Mathematical Analysis of Logic,1 publicado en 1847, en respuesta a una controversia en curso entre Augustus De Morgany Sir William 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 como un libro más importante: The Laws of Thought,2 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 como funcionan los circuitos.

• Al diseño, ya que teniendo una función aplicamos dicha álgebra, para poder desarrollar una implementación de la función.

Definición

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 B, le asigna un b de B.

Para todo elemento a en B, se cumple que existe un único b en B, 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 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:

Con lo que 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.

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: (\mathfrak{B}, \sim, \oplus, \odot) son un álgebra de boole, si cumple las siguientes axiomas:

1a: La ley asociativa de la suma:

\forall a, b, c \in \mathfrak{B}

: \;

(a \oplus b) \oplus c = a \oplus (b \oplus c)

1b: La ley asociativa del producto:

\forall a, b,c \in \mathfrak{B}

: \;

(a \odot b) \odot c = a \odot (b \odot c)

2a: Existencia del elemento neutro para la suma:

\forall a \in \mathfrak{B}

: \;

a \oplus \varnothing = a

2b: Existencia del elemento neutro para el producto:

\forall a \in \mathfrak{B}

: \;

a \odot U = a

3a: La ley conmutativa de la suma:

\forall a, b \in \mathfrak{B}

: \;

a \oplus b = b \oplus a

3b: La ley conmutativa del producto:

\forall a, b \in \mathfrak{B}

: \;

a \odot b = b \odot a

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

\forall a, b, c \in \mathfrak{B}

: \;

a \oplus (b \odot c) = (a \oplus b) \odot (a \oplus c)

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

\forall a, b, c \in \mathfrak{B}

: \;

a \odot (b \oplus c) = (a \odot b) \oplus (a \odot c)

5a: Existe elemento complemento para la suma:

\forall a \in \mathfrak{B}

; \;

\exists \sim a \in \mathfrak{B}

: \;

a \oplus \sim a = U

5b: Existe elemento complemento para el producto:

\forall a \in \mathfrak{B}

; \;

\exists \sim a \in \mathfrak{B}

: \;

a \odot \sim a = \varnothing

Teoremas fundamentales[editar]

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

6a: Ley de idempotencia para la suma:

\forall a \in \mathfrak{B}

: \;

a \oplus a = a

6b: Ley de idempotencia para el producto:

\forall a \in \mathfrak{B}

: \;

a \odot a = a

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

\forall a \in \mathfrak{B}

: \;

a \oplus U = U

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

\forall a \in \mathfrak{B}

: \;

a \odot \varnothing = \varnothing

8a: Ley de identidad para la suma:

\forall a \in \mathfrak{B}

: \;

a \oplus \varnothing = a

8b: Ley de identidad para el producto:

\forall a \in \mathfrak{B}

: \;

a \odot U = a

9: Ley de involución:

\forall a \in \mathfrak{B}

: \;

\sim (\sim a) = a

10: Ley del complemento:

\sim U = \varnothing

\sim \varnothing = U

11: Leyes de De Morgan:

\forall a, b \in \mathfrak{B}

: \;

\sim ( a \oplus b) = \sim a \odot \sim b

\forall a, b \in \mathfrak{B}

: \;

\sim ( a \odot b) = \sim a \oplus \sim b

Orden en el álgebra de Boole[editar]

Sea: (\mathfrak{B}, \sim, \oplus, \odot) un álgebra de Boole, sean a, b dos elementos del conjunto, podremos decir entonces que a antecede a b y lo denotamos:

a \precsim b

si se cumple alguna de las siguientes condiciones:

a \oplus b = b

a \odot b = a

\sim a \oplus b = U

a \odot \sim b = \varnothing

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.

Principio de dualidad[editar]

El concepto de dualidad permite formalizar

...