Á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 un sistema 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 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 Thought2 o simplemente The Laws
of Thought3 ), 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: son un álgebra de boole, si cumple las
siguientes axiomas:
• 1a: La ley asociativa de la suma:
• 1b: La ley asociativa del producto:
• 2a: Existencia del elemento neutro para
la suma:
• 2b: Existencia del elemento neutro para
el producto:
• 3a: La ley conmutativa de la suma:
• 3b: La ley conmutativa del producto:
• 4a: Ley distributiva de la suma
respecto al producto:
• 4b: Ley distributiva del producto
respecto a la suma:
• 5a: Existe elemento complemento para la
suma:
• 5b: Existe elemento complemento 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:
• 6b: Ley de idempotencia para el
producto:
• 7a: Ley de absorción para la suma:
• 7b: Ley de absorción para el producto:
• 8a: Ley de identidad para la suma:
• 8b: Ley de identidad para el producto:
• 9: Ley de involución:
• 10: Ley del complemento:
• 11: Leyes de De Morgan:
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 valoras a, b de , que cumples qua a
antecede a b, o que b antedede a a, se dice que a y b son comparables.
Si
se cumple que:
Para
los valoras a, b de , que cumples qua a
no antecede a b, y que b no antedede 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 los
con los .
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 distintas 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,
veámoslos.
Lógica
binaria
Artículo
principal: Lógica binaria
Artículo
principal: Sistema digital
Artículo
principal: Sistema binario
Artículo
principal: Tabla de verdad
Artículo
principal: Sistema combinacional
Artículo
principal: Formas canónicas (álgebra de Boole)
Artículo
principal: Circuito de conmutación
Una
serie de temas, aparentemente tan distintos, tiene dos cosas en común, la
lógica binaria basada en los ceros y los unos y el álgebra de Boole, 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
perdida 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:
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:
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:
• 1a: La ley asociativa de la suma:
• 1b: La ley asociativa del producto:
• 2a: Existencia del elemento neutro para
la suma:
• 2b: Existencia del elemento neutro para
el producto:
• 3a: La ley conmutativa de la suma:
• 3b: La ley conmutativa del producto:
• 4a: Ley distributiva de la suma
respecto al producto:
• 4b: Ley distributiva del producto
respecto a la suma:
• 5a: Existe elemento complementario para
la suma:
• 5b: Existe elemento complementario para
el producto:
Luego es álgebra de boole.
Teoremas
fundamentales
Partiendo
de estos axiomas se puede demostrar los siguientes teoremas:
• 6a: Ley de idempotencia para la suma:
• 6b: Ley de idempotencia para el
producto:
• 7a: Ley de absorción para la suma:
• 7b: Ley de absorción para el producto:
• 8a: Ley de identidad para la suma:
• 8b: Ley de identidad para el producto:
• 9: Ley de involución:
• 10: Ley del complemento:
• 11: Leyes de De Morgan:
0 comentarios:
Publicar un comentario