ÁLGEBRÁ DE BOOLE
Definición
Un Álgebra Booleana es una estructura matemática conformada por un conjunto B que contiene por lo
menos dos elementos que indicamos con 0 y 1, en donde se han definido dos operaciones binarias
simbolizadas como • y + (que se leen por y más) y una operación unaria ‘ (que se lee como complemento ).
Simbólicamente la sextupla (B, +, •, ‘, 0, 1) es un Álgebra de Boole (en honor a George Boole 1813-1864) si
tomando elementos cualesquiera a, b y c del conjunto B, se cumplen los siguientes axiomas:
a) Leyes asociativas
(a + b) + c = a + ( b + c ) (a • b) • c = a • ( b • c )
b) Leyes conmutativas
a+b=b+a a•b=b•a
c) Leyes distributivas
(a + b) • c = (a • c ) + ( b • c) (a • b) + c = (a + c ) • ( b + c)
d) Leyes de identidad (o de elemento neutro)
a+0=0+a=a a • 1 = 1 • a =a
e) Leyes de complementariedad
a + a’ = a’ + a = 1 a • a’ = a’ • a = 0
Observación:
➢ Por convención habitual (si no existen paréntesis), la operación unaria tiene prioridad sobre • y •
tiene prioridad sobre + . Por ejemplo: a + b • c = a + (b • c) y a • b’ = a • (b’).
➢ El uso del “0”y del “1”es simplemente simbólico (es decir que no tienen necesariamente que ver con
los números cero y uno. Un comentario análogo se aplica para los símbolos “+”y “•”.
➢ El complemento del elemento a también se puede leer como la negación de a o “no a”.
Demostración de unicidad de elemento complemento:
Si a + y = 1 ∧ a • y = 0 ⟹ y = a’
Hipótesis (dato): a + y = 1 ∧ a • y = 0. Tesis (lo que quiero demostrar): y = a’
Es decir dado un elemento a, suponemos que tiene dos complementos ( y , a’) , llegaremos a demostrar que
ambos son iguales.
y = y • 1 = y • (a + a’) = y • a + y • a’ = a • y + y • a’ = 0 + y • a’ = a • a’ + y • a’ = (a + y ) • a’ = 1 • a’ = a’
por d por e por c por b dato por e por c dato por d
La demostración podría haberse planteado con y = y + 0. Queda como ejercicio para el lector
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 1
Ejemplo 1
Sea B = {0,1} y las operaciones binarias + , • definidas por las tablas que se dan a continuación:
+ 0 1 • 0 1
0 0 1 0 0 0
1 1 1 1 0 1
Se determina un Álgebra de Boole Binaria o Álgebra de Boole Bivaluada.
a) En efecto, de las tablas se puede deducir que las operaciones son conmutativas, pues existe una
simetría respecto a la diagonal principal de la tabla.
b) El 0 es el neutro de la operación +, según la definición de identidad.
c) El 1 es el neutro de la operación •, según la definición de identidad.
d) Respecto a la existencia de complementos ocurre que 0’ = 1 y 1’ = 0.
e) Para verificar la ley asociativa se debe realizar una tabla en donde se analicen los diferentes casos
posibles, se trata de secuencias con repetición de 2 elementos tomados de a 3 es decir que se
plantean 8 posibilidades.
a b c a+b (a + b) + c b+c a+(b+c)
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 1 1 0 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
Como puede observarse las columnas 5 y 7 son iguales en cada una de sus filas, por consiguiente la
operación + es asociativa. En forma análoga se puede verificar la asociatividad para la operación •
¿Qué más falta demostrar? ¿Cómo la harías?
Ejemplo 2
Sea Bn el conjunto de las secuencias de n-bits. Explique cómo Bn define un Álgebra de Boole.
✓ Consideremos a y b dos secuencias de n-bits de Bn .
✓ Definimos la suma, el producto y el complemento de esas secuencias bit a bit como las dadas en el
ejemplo 1. Esto es, en una posición dada a + b contiene 1 si a ó b contienen 1; a • b contiene 1 si a y b
tienen valor 1 y a’ es 1 si a es 0.
✓ Según lo definido si se tiene a = 1101010 y b = 1011011 de B7 las operaciones definidas arrojarían los
siguientes resultados:
a + b = 1111011 a • b = 1001010 a’=0010101
¿Cómo seguirías el planteo de la demostración para decir que se trata de un Álgebra de Boole?
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 2
Ejemplo 3
Se X un conjunto no vacío y sea P(X) el conjunto de todos los subconjuntos de X (es decir el conjunto
potencia o partes de X). Sean A y B elementos de P(X), definimos las operaciones:
A+B=A∪B A•B=A∩B A’ complemento de A
La sextupla definido por (P(X), ∪, ∩, ‘, ∅ , X) constituye un Álgebra de Boole y se denomina el Álgebra
Booleana de las partes de X. Según lo definido si se tiene un conjunto X = {a,b} entonces P(X) = {{a,b}, {a}, {b},
∅ } . Los operadores de la unión y la intersección en este caso particular quedan definidos con las siguientes
tablas:
∪ ∅
{a} {b} {a,b} ∩ ∅ {a} {b} {a,b}
∅ ∅ {a} {b} {a,b} ∅ ∅ ∅ ∅ ∅
{a} {a} {a} {a,b} {a,b} {a} ∅ {a} ∅ {a}
{b} {b} {a,b} {b} {a,b} {b} ∅ ∅ {b} {b}
{a,b} {a,b} {a,b} {a,b} {a,b} {a,b} ∅ {a} {b} {a,b}
✓ La conmutatividad de ambas operaciones se manifiesta dado que las tablas son simétricas.
✓ El elemento neutro de la unión es el conjunto vacío y el de la intersección es {a, b}.
✓ Complementarios: ∅′ = {a, b} ; {a}’ = {b} ; {b}’ = {a}.
✓ Ambas operaciones son asociativas y se verifican las dos leyes distributivas de la intersección
respecto a la unión y de la unión respecto a la intersección según lo visto en el capítulo de
Conjuntos.
Ejemplo 4
Sea D6 = {1, 2, 3, 6} el conjunto de los divisores de 6. Definimos la suma, el producto y el complemento de la
siguiente manera:
a + b = m. c. m. {a , b} se lee mínimo común múltiplo entre a y b
a • b = m. c. d. {a , b} se lee máximo común divisor entre a y b
a ’= 6/a donde a’ es el complemento de a
+ 1 2 3 6 • 1 2 3 6
1 1 2 3 6 𝟏 1 1 1 1
2 2 2 6 6 2 1 2 1 2
3 3 6 3 6 3 1 1 3 3
6 6 6 6 6 6 1 2 3 6
El 1 es el elemento neutro o identidad de la operación “+ “ y el 6 es el elemento neutro o identidad de la
operación “•”. D6 se denomina Álgebra Booleana de los divisores de 6.
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 3
Ejemplo 5
Sea D8 = {1, 2, 4, 8} el conjunto de los divisores de 8. Definimos la suma, el producto y el complemento de la
siguiente manera:
a + b = m. c. m. {a , b} se lee mínimo común múltiplo entre a y b
a • b = m. c. d. {a , b} se lee máximo común divisor entre a y b
a ’= 8/a donde a’ es el complemento de a
+ 1 2 4 8 • 1 2 4 8
1 1 2 4 8 𝟏 1 1 1 1
2 2 2 4 8 2 1 2 2 2
4 4 4 4 8 4 1 2 4 4
8 8 8 8 8 8 1 2 4 8
Observando las tablas determinamos que el 1 es elemento neutro de la suma y el 8 es el neutro para el
producto.
Respecto a los complementos puede observarse que:
✓ 1’= 8 pues 1 + 8 = 8 y 1 • 8 = 1 pero
✓ 2 no tiene complemento pues no existe x en D8 que verifique las condiciones de 2 + x’ = 8 y 2 • x’ =
1. Por consiguiente D8 no es un Álgebra Boolena.
Observación:
Un número puede escribirse como producto de sus factores. Es decir 6 = 2.3 y 8 = 2.2.2
De acuerdo a los ejemplos presentados puede hacerse un análisis sobre cuáles deben ser los valores de n
para que Dn pueda ser un Álgebra Booleana.
Estudiando algunos ejemplos más se puede deducir que para n = 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21,
22, etc . Dn es un Álgebra Booleana, mientras que no lo es para n = 4, 8, 9, 12, 16, 18, 20, 25, 27, etc.
Se puede demostrar que Dn es un Álgebra Booleana si n puede expresarse como un producto de números
primos distintos. Por lo tanto D24 no es un Álgebra Boolena pues 24 = [Link], mientras que D30 es un Álgebra
de Boole pues 30 = 2.3.5
Ejemplo 6
Según lo visto en el capítulo de Semigrupos y Homomorfismos ℤ2 = {0̅ , 1̅} es un Álgebra Booleana. Analice la
afirmación.
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 4
Definición
Sea S un subconjunto no vacío de un Álgebra de Boole B, decimos que S es Subálgebra de B si S es en sí
mismo un Álgebra de Boole (con respecto a las operaciones definidas en B). Es decir si se verifica que:
1. Si x ∈ S ; y ∈ S, entonces x + y ∈ S , x • y ∈ S (es decir, es cerrado respecto a las operaciones de B)
2. Si x ∈ S entonces x’ ∈ S (es decir, todo complemento de un elemento del subconjunto está en el
subconjunto S)
Ejemplo 7
Sean los conjuntos X = { 1, 5, 10, 70} ; Y = { 1, 2, 35, 70} analizar si son Subálgebra de D 70
✓ X es cerrada respecto a “+” y “•”, pero 5’ = 14 que no pertenece a X. Por lo tanto X no es una
Subálgebra.
✓ Y si es Subálgebra de D70 respecto a las operaciones a “+” y “•”, y los complementarios están en el
conjunto Y.
Observación:
Como puede observarse los elementos que actúan como neutros de cada una de las operaciones deben
pertenecer al subconjunto que será analizado.
Definición
El dual de un enunciado que involucra sólo variables y operadores booleanos se obtiene reemplazando 0 por
1 y 1 por 0, el operador “+” por el “•” y el operador “•” por el “+”.
Es decir para:
(a • 1) • (0 + a’) = 0 su dual es (a + 0) + (1 • a’) = 1
a + a’• b = a • b su dual es a • (a’ + b) = a + b que también puede escribirse de esta forma:
a • (a’ + b) = a • b ¿por qué?
Principio de Dualidad
Tanto en los axiomas que caracterizan el Álgebra de Boole como en las propiedades definidas, se observa
una dualidad. Es decir, el dual de un conjunto de axiomas de B es el mismo que el conjunto de axiomas
original.
De acuerdo con esto, si cualquier enunciado es consecuencias de los axiomas del Álgebra de Boole,
entonces el dual también es una consecuencia de dichos axiomas, puesto que el enunciado del dual se
puede demostrar utilizando en cada paso el dual de la demostración original.
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 5
Teorema
En un Álgebra de Boole B, se cumplen las siguientes propiedades para todos sus elementos a y b
cualesquiera:
f) Leyes idempotencia
(a + a) = a (a • a) = a
g) Leyes de acotación
a+1=1 a•0=0
h) Leyes de absorción
a + (a • b ) = a a • (a + b ) = a
i) Leyes de complementos de los neutros
0’ = 1 1’ = 0
j) Leyes de De Morgan
(a + b)’ = a’ • b’ (a • b )’ = a’ + b’
k) Ley de involución
(a’)’= a
Demostración de ley de idempotencia
a = a • 1 = a • (a + a’) = (a • a) + (a • a’) = (a • a) + 0 = a • a
identidad / complemento / distributiva / complemento / identidad
A partir de esta prueba se deduce a = a + 0 y por el principio de dualidad obtenemos:
a = a + 0 = a + (a • a’) = (a + a) • (a + a’) = (a + a) • 1 = a + a
identidad / complemento / distributiva / complemento / identidad
Demostración de ley de acotación
a • 0 = (a • 0) + 0 = (a • 0) + (a • a’) = a • (0 + a’) = a • (a’+ 0) = a • a’ = 0
identidad/ complemento / factor común / conmutativa / identidad / complemento
A partir de esta prueba se deduce a + 1 = 1 y por el principio de dualidad obtenemos:
a + 1 = (a + 1) • 1 = (a + 1) • (a + a’) = a + (1 • a’) = a + (a’• 1) = a + a’ = 1
identidad/ complemento / factor común / conmutativa / identidad / complemento
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 6
Demostración de ley de absorción
a • (a + b) = (a + 0) • (a + b) = a + (0 • b) = a + (b • 0) = a + 0 = a
identidad / factor común / conmutativa / acotación / identidad
A partir de esta prueba se deduce a + (a • b) = a y por el principio de dualidad obtenemos:
a + (a • b) = (a • 1) + (a • b) = a • (1 + b) = a • (b + 1) = a • 1 = a
identidad / factor común / conmutativa / acotación / identidad
Demostración de ley de De Morgan
Se precisa demostrar que (a + b)’ = a’ • b’. Considerando la propiedad de complemento y la de unicidad del
mismo la demostración a realizar es la siguiente:
(a + b) + (a + b)’ = 1 ó su equivalente (a + b) + (a’ • b’) = 1
(a + b) • (a + b)’ = 0 ó su equivalente (a + b) • (a’ • b’) = 0
Analizamos cada caso por separado:
(a + b) + (a’ • b’) = [(a + b) + a’] • [(a + b) + b’] = [(a + a’) + b] • [(b + b’) + a] = (1 + b) • (1 + a) = 1 • 1 = 1
distributiva / conmutativa y asociativa / complementario / identidad / acotación/ idempotencia
(a + b) • (a’ • b’) = [a • (a’• b’)] + [b • (a’ • b’)] = [(a • a’) • b] + [(b • b’) • a] = (0 • b) + (0 • a) = 0 • 0 = 0
distributiva / conmutativa y asociativa / complementario / identidad / acotación/ idempotencia
A partir de esta prueba y por el principio de dualidad se deduce (a • b)’ = a’ + b’. Se deja para el lector las
demostraciones:
(a • b) + (a • b)’ = 1 ó su equivalente (a • b) + (a’ + b’) = 1
(a • b) + (a • b)’ = 0 ó su equivalente (a • b) • (a’ + b’) = 0
Profesora Rosa Maenza – U.T.N. – Facultad Regional Rosario Página 7
