algebra-de-boole-y-aplicaciones -jose-luis-leal-ruperto

Vista previa del material en texto

Algebra de Boole y aplicaciones 1
Algebra de Booble y aplicaciones
José Luis Leal Ruperto
Departamento de Matemática Aplicada
Universidad de Málaga 1996
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 2
Departamento de Matemática Aplicada José Luis Leal Ruperto
1
Algebra de boole y
aplicaciones
El estudio del álgebra de Boole se trata en otras materias que son más
afines a la electrónica, y en ellas se hace de forma exhaustiva porque cons-
tituye la base de los sistemas digitales.
No obstante, siempre que se aborda en estas otras materias, se hace
con un enfoque aplicado y con un exclusivo objetivo: el tratamiento de las
funciones de conmutación. Esto hace que se descuiden un poco los aspectos
algebraicos en los que se fundamentan todos los resultados.
Como todos los métodos y procedimientos que se desarrollan están per-
fectamente justificados por teoremas esenciales de estructura, que son co-
munes a cualquier álgebra de Boole, en este caṕıtulo no los vamos a dejar
de ver.
Como un Álgebra de Boole, es un conjunto con una relación de orden,
comenzaremos el estudio de estas álgebras exponiendo lo necesario sobre
conjuntos ordenados, y llegaremos paso a paso hasta el final, con el trata-
miento de las funciones booleanas como estudio de un ejemplo de un álgebra
de Boole significativa.
1.1. Conjuntos ordenados.
Como vimos en el caṕıtulo segundo, una relación R en un conjunto E es
de orden si satisface las propiedades reflexiva, antisimétrica y transitiva.
Suele convenir representar la relación de orden R con el śımbolo ≤, aun-
que es importante saber que ≤ representa según el caso que tratemos una
relación distinta, y no debe confundirse con la desigualdad usual a la que
3
Algebra de Boole y aplicaciones 4
estamos acostumbrados cuando tratamos números.
Formalmente,
Definición 1.1 Un conjunto ordenado es un par (E,≤) donde E es un
conjunto cualquiera y ≤ es una relación de orden en E.
Cuando tengamos que x ≤ y diremos que x precede, minora o que es
minorante de y. También que y es posterior mayora o es mayorante
de x.
Veamos algunos ejemplos básicos,
Ejemplo 1.1 Son conocidos conjuntos ordenados los siguientes,
(IR,≤), donde ≤ es la relación en los Reales definida como x ≤ y si
y − x es real positivo.
(ZZ+, |), donde | es la relacion “dividir”, en el conjunto de los Enteros
positivos.
(ZZ+, •), donde • es la relación “ser múltiplo de” también en el conjunto
de los enteros positivos.
(A,⊆), con la relación “estar incluido” establecida sobre cualquier sub-
conjunto de A.
En una relación de orden, a veces dos elementos cualesquiera están siempre
relacionados entre śı en otros casos no:
Definición 1.2 El conjunto ordenado (E,≤) es un conjunto totalmente
ordenado si,
∀x, y ∈ E, x ≤ y ó y ≤ x.
en caso contrario el conjunto es parcialmente ordenado.
El conjunto (IR,≤) está totalmente ordenado, (ZZ+, |) y (ZZ+, •) lo están
parcialmente.
Si E es finito, ≤ es también finita, y como en todas relaciones finitas
tenemos definido un grafo dirigido. A la hora de representarlo podemos
evitar el tener que asignar una orientación a cada arco del grafo si ponemos
los elementos que son posteriores a otros, en escalones superiores.
De esta forma, en un conjunto ordenado, el elemento x precederá a otro
y si es posible pasar del vertice x al vértice y a través de una sucesión
ascendente de arcos. Un grafo representado aśı se llama Diagrama de
Hasse.
Veamos un primer ejemplo,
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 5
Ejemplo 1.2 Sea A = {1, 2, 3, 5, 6, 8, 10, 15, 16, 20, 30}, con la relación de
orden “divide”.
j1
j2 j3 j5
j8 j6 j10 j15
j16 j20 j30
�
�
�
�
�
�
�
�
@
@
@
@
@
@
@
@
�
��
��
En el diagrama de Hasse que aparece
a la derecha, observamos que por ejem-
plo, el número 2 está relacionado con el
30 ya que existe al menos un camino as-
cendente: el 2−6−30, o el 2−10−30 que
los une. En cambio el 2 y el 15 no lo están
por no existir ese camino ascendente.
En los conjuntos totalmente ordena-
dos el diagrama de Hasse consiste en un
sólo camino o recta a través del cual
están alineados todos sus vértices. Tal es el caso de la recta Real.
1.1.1. Elementos notables en un conjunto ordenado.
Cuando se estudian conjuntos parcialmente ordenados observamos que
en él existen elementos que satisfacen propiedades concretas. Procedemos a
definirlas,
Definición 1.3 Sea el conjunto ordenado (E,≤),
1. Un elemento M ∈ E es maximal, si no posee más mayorante que él
mismo. Es decir, M es maximal si y sólo si,
∀x ∈ E, M ≤ x⇒M = x.
2. Un elemento m ∈ E es minimal, si no posee más minorantes que él
mismo. Es decir m es minimal si y sólo si,
∀x ∈ E, x ≤ m⇒ m = x.
3. Un elemento s ∈ E es el supremo o último elemento del conjunto
E si mayora a todos. Es decir, s es supremo si y sólo si,
∀x ∈ E x ≤ s.
4. Un elemento i ∈ E es el ı́nfimo o primer elemento del conjunto E
si minora a todos. Es decir, i es ı́nfimo si y sólo si,
∀x ∈ E i ≤ x.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 6
En el ejemplo 1.2 anterior, observando el diagrama de Hasse, vemos rápida-
mente que 16, 20, 30 son maximales, y que 1 es el único minimal. No tiene
supremo porque ningún elemento es mayor que todos los demás, y el ı́nfimo
es el 1.
Son de especial importancia ciertos elementos en conjuntos ordenados
que tienen ı́nfimo. Estos son,
Definición 1.4 Sea (E,≤) un conjunto ordenado con ı́nfimo i. Un ele-
mento a ∈ E es un átomo si es inmediatamente posterior al ı́nfimo. Es
decir, a es átomo si y sólo si
i 6= a y ∀x, a ≤ x.
En conjuntos ordenados con supremo, los elementos que son inmediatamente
anteriores al supremo de llaman superátomos.
El concepto de mayoración y minoración se generaliza también a un
subconjunto B de E. Diremos que un elemento x es cota superior de B si
lo es de cada uno de los elementos de B. Si el subconjunto B tiene al menos
una cota superior en E se dice que está acotado superiormente.
Todas estas ideas se trasladan de forma inmediata para las cotas inferio-
res.
Expresaremos con Cs(B), Ci(B) los conjuntos de las cotas superiores e
inferiores de B.
De nuevo en el ejemplo 1.2 anterior, el conjunto de los átomos es {2, 3, 5},
no existen super átomos al no existir supremo, y, si consideramos B =
{2, 10}, obtenemos de inmediato del diagrama que el conjunto Cs(B) de
cotas superiores de B, es Cs(B) = {10, 20, 30}, y el de las cotas inferiores es
Ci(B) = {1, 2}.
Son especialmente importantes, para el estudio de los conjuntos ordena-
dos la menor y mayor, respectivamente, de las cotas superiores e inferiores
si es que existen,
Definición 1.5 Sea (E,≤) un conjunto ordenado, sea B subconjunto de
E acotado superiormente, el extremo superior de B que representamos
por sup(B) es, si existe, la menor de las cotas superiores. Es decir sup(B)
es extremo superior si y sólo si,
∀x ∈ Cs(B), sup(B) ≤ x.
De forma similar definimos en un conjunto acotado inferiormente la mayor
de las cotas inferiores que expresamos como ı́nf(B).
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 7
Si el superior e inferior pertenecen al subconjunto, se llamarán respecti-
vamente máximo y mı́nimo.
Volviendo al ejemplo, tenemos que sup(B) = 10 y que ı́nf(B) = 2.
La utilidad del diagrama de Hasse se pone aqúı de manifiesto al observar
lo fácil que es determinar los extremos superior e inferior para un conjunto
cualquiera B = {b1, b2, . . . , bn}: El sup(B) es el “primer” vértice (vértice en
el escalón más bajo) 1 donde convergen los distintos caminos ascendentes que
parten de los b1, b2, . . . , bn y el ı́nf(B) el “primer vértice” donde convergen
los caminos descendentes que también parten desde b1, b2, . . . , bn.
Veamos algunos ejemplos más.
Ejemplo 1.3 Consideremos de nuevo el mismo conjunto A del ejemplo
1.2 anteriorpero con la relación “ser múltiplo de”.
j1
j2 j3 j5
j8 j6 j10 j15
j16 j20 j30
@
@
@
@
@
@
@
@
�
�
�
�
�
�
�
�
HH
HHH
Ahora, dado que por ejemplo 15 es
múltiplo de 5, es correcto escribir 15 ≤ 5
sin que ello deba llevar a confusión. Su
diagrama de Hasse es el que aparece di-
bujado a la derecha, y no es casualidad
que resulte ser idéntico al anterior pero
invertido. La justificación está en el he-
cho de que esta relación es justamente la
relación inversa de la anterior.
Ejemplo 1.4 En los ejemplos anteriores tenemos la relación de orden so-
bre un conjunto finito. Consideremos ahora la relación “divide” en los enteros
positivos, es decir (ZZ+, /).
Aqúı al tener infinitos elementos, el diagrama de Hasse no es trazable en
su totalidad, y cualquier representación parcial nos va a ser de poca utilidad.
El ı́nfimo es el 1 que es el único que divide a cualquier entero. Los áto-
mos son los números primos que sólo son divididos con anterioridad por el 1.
Si consideramos cualquier subconjunto B = {a1, a2, . . . , an} de ZZ+ resulta
que tiene por cotas superiores, cualquier entero que pueda ser dividido por
a1, a2, . . . an, es decir por un múltiplo común a todos ellos. Sus cotas inferio-
res son divisores comunes a todos ellos, por tanto el extremo superior será
el menor múltiplo común, y el extremo inferior es el mayor divisor común,
sup(B) = mcm(a1, a2, . . . , an)
ı́nf(B) = mcd(a1, a2, . . . , an)
1Ese “primer” vértice puede no existir aunque el conjunto de cotas superiores comunes
sea no vaćıo.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 8
Con todas estas definiciones y ejemplos estamos en condiciones de definir la
estructura ordenada de ret́ıculo.
1.2. Ret́ıculos.
No es dificil probar que cualquiera que sea B subconjunto de un conjunto
ordenado (E,≤), si existen, tanto sup(B) como ı́nf(B) son únicos. Podemos
considerar conjuntos B constituidos por sólo dos elementos, y aprovechar esa
unicidad para considerar el sup y el ı́nf como si fuesen operaciones binarias.
Definición 1.6 El conjunto ordenado (E,≤) se dice ret́ıculo ordenado
si para cualquier par de elementos x, y de E, existen en E el sup({x, y}) y
el ı́nf({x, y}).
Ejemplo 1.5 Sea X un conjunto y consideremos (P (X),⊆). Dados dos
elementos A,B de P (X) siempre existen A ∪ B, A ∩ B. Además A ∪ B es
mayorante de A y de B ya que A ⊆ A ∪ B y B ⊆ A ∪ B, y es el menor
mayorante ya que si C es otro mayorante común, A ⊆ C y B ⊆ C y
entonces AUB ⊆ C.
Por un razonamiento similar se concluye que A ∩ B es el mayor de los
minorantes. Por tanto (P (X),⊆) es un ret́ıculo ordenado. El supremo y el
ı́nfimo son respectivamente X y ∅.
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
�
��
�
��
�
��
�
��
@
@@
@
@@
@
@@
@
@@
En particular si X = {a, b, c}, obtenemos
un ret́ıculo de ocho elementos, cuyo diagrama
de Hasse es el que aparece a la derecha.
Para los elementos {a, b}, {b, c} por ejem-
plo, puede comprobarse que
sup({{a, b}, {b, c}}) = {a, b} ∪ {b, c} = {a, b, c}
ı́nf({{a, b}, {b, c}}) = {a, b} ∩ {b, c} = {b}
La relación divide también nos proporciona ejemplos de ret́ıculo,
Ejemplo 1.6 Consideremos (ZZ+, |) el conjunto de los enteros positivos
con la relación divide. Dados a, b ∈ ZZ+ siempre existen en ZZ+ el mı́nimo
común múltiplo mcm(a, b) y el máximo común divisor mcd(a, b) de a, b.
El mcm(a, b) es mayorante común de a, b porque ambos lo dividen, y por
definición es el menor. El mcd(a, b) es minorante común al a y al b ya que
divide a los dos, y por definición es el mayor. El conjunto (ZZ+, |) es entonces
un ret́ıculo con ı́nfimo el 1, pero no tiene supremo. (¿Porqué?).
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 9
Es posible, también con la relación divide, tener un ret́ıculo con un núme-
ro finito de elementos,
Ejemplo 1.7 En particular vamos a considerar (D20, |), en donde D20
representa el conjunto de los divisores de 20.
1
2 5
4 10
20
�
�
�
�
@
@
@
@
��
�
��
Este ret́ıculo śı está acotado, el supremo es
20 y el ı́nfimo es 1. Cuando nos dispongamos
a trazarlo, hemos de tener en cuenta primero
cuántos divisores tiene: La descomposición de
20 en factores primos es 20 = 2251, por tanto
tiene en total (2+1)(1+1) = 6 divisores. A con-
tinuación, quiénes son los átomos, en este caso
el 2 y el 5. Finalmente comenzamos a dibujar,
poniendo primero el ı́nfimo 1, a continuación
sus átomos 2, 5 y por último las potencias de
los átomos 22, y las combinaciones entre estos, el 10 y el 20.
El conjunto ordenado (A, /) del ejemplo 1.2 inicial no es un ret́ıculo,
porque no existe en él entre otros, el superior de 6 y 8: su mı́nimo común
múltiplo es 24.
Observando las propiedades que satisfacen los elementos del ret́ıculo de
las partes un conjunto, podemos suponer que es posible otra definición equi-
valente para ret́ıculo, en donde se manejen el superior y el inferior como si
de operaciones binarias se tratasen.
Esta otra definición alternativa para un ret́ıculo nos la da el siguiente
teorema de equivalencia:
Teorema 1.1 Son equivalentes las siguientes afirmaciones:
(a) El par (E,≤) es un ret́ıculo ordenado.
(b) (E,∨,∧) es un Ret́ıculo Algebraico, es decir, E es un conjunto en el
que existen dos operaciones internas, respectivamente ∨, ∧ que satis-
facen las propiedades:{ a ∨ a = a
a ∧ a = a
Idempotencia.{
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Conmutativa.{
a ∨ (b ∨ c) = (a ∨ b) ∨ c
a ∧ (b ∧ c) = (a ∧ b) ∧ c
Asociativa.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 10
{
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a
Simplificativa.
Demostración: Probamos primero que (a) implica (b).
Es evidente que es posible definir operaciones internas en E, sin más que
considerar para cualquier par x, y ∈ E,
x ∨ y := sup({x, y})
x ∧ y := inf({x, y})
La unicidad de los extremos superior e inferior hacen a ∨ y a ∧ que sean
operaciones.
Se cumplen las propiedades, vamos a comprobar la primera de cada
una de las parejas. De forma inmediata verificamos la idempotencia: x ∨
x = sup({x, x} = sup({x}) = x y conmutativa: x ∨ y = sup({x, y}) =
sup({y, x}) = y ∨ x.
Veamos con más detenimiento la propiedad asociativa. La probamos
comprobando que se cumplen ambas desigualdades a ∨ (b ∨ c) ≤ (a ∨ b) ∨ c
y a ∨ (b ∨ c) ≥ (a ∨ b) ∨ c. Veamos por ejemplo esta última:
Como cualquier elemento es menor o igual que el superior de él mismo
con otro cualquiera, podemos poner
a ≤ a ∨ (b ∨ c) (1)
(b ∨ c) ≤ a ∨ (b ∨ c)
a su vez al ser b ≤ b ∨ c, y c ≤ b ∨ c tenemos
b ≤ a ∨ (b ∨ c) (2)
c ≤ a ∨ (b ∨ c) (3)
en (1) Y (2) se tiene que a ∨ (b ∨ c) es cota superior de a y que lo es de b,
por tanto a ∨ b ≤ a ∨ (b ∨ c) por ser a ∨ b la menor de todas. Esto último
junto con (3) de nuevo nos indica que a ∨ (b ∨ c) es cota superior de a ∨ b y
de c, con lo que
(a ∨ b) ∨ c ≤ a ∨ (b ∨ c).
La otra desigualdad a ∨ (b ∨ c) ≤ (a ∨ b) ∨ c, se prueba de forma similar 2.
Por último, la propiedad simplificativa:
2En virtud de estas propiedad, los paréntesis pueden omitirse si usamos sólo una ope-
ración, y, dado cualquier conjunto finito A = {a1, a2, . . . an} de elementos de un ret́ıculo,
podemos escribir su superior como sup(a1, a2 . . . , an) = a1 ∨ a2 ∨ . . . ∨ an.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 11
Se tiene que a ∧ b ≤ a y que a ≤ a, en particular a es cota superior del
extremo superior de ambos, a ∨ (a ∧ b) ≤ a. Al tener por otra parte que
siempre a ≤ a ∨ (a ∧ b), se obtiene la igualdad a = a ∨ (a ∧ b).
Las otras propiedades de cada pareja se prueban de forma semejante a
como hemos procedido con la primera.
Rećıprocamente, si un conjunto E satisface las condiciones expresadas
en (a), veamos que satisface (b). Para ello hemos de encontrar alguna forma
de definir en E una relación que sea de orden y posteriormente ver que con
ella existen siempre el sup y el ı́nf de dos elementoscualesquiera.
(E,∨,∧) es un conjunto ordenado para la siguiente relación
a ≤ b :⇔ a ∨ b = b.3
Veamos que es en efecto una relación de orden.
Es evidentemente reflexiva: ∀a, a ≤ a ya que a ∨ a = a. Antisimétrica:
a ≤ b y b ≤ a equivalen a que a ∨ b = b y que b ≤ a = a, y como ∨ es
conmutativa, b = a ∨ b = b ∨ a = a. Transitiva: a ≤ b y b ≤ c nos da que
a∨ b = b y b∨ c = c, sustituyendo, a∨ c = a∨ (b∨ c) = (a∨ b)∨ c = b∨ c = c.
Por último, veamos que dados dos elementos x, y cualesquiera existen el
sup({x, y}) y el ı́nf({x, y}) y van a ser respectivamente x ∨ x y x ∧ y:
Que x ∨ y existe, es obvio por ser ∨ en E una operación interna; x ∨ y
es cota superior común a x y a y ya que x∨ (x∨ y) = (x∨ x)∨ y = x∨ y, y
que y ∨ (x ∨ y) = y ∨ (y ∨ x) = (y ∨ y) ∨ x = y ∨ x = x ∨ y. Además x ∨ y es
la menor de las cotas superiores ya que si t es otra cota superior común a x
y a y, entonces (x ∨ y) ∨ t = x ∨ (y ∨ t) = a ∨ t = t por tanto x ∨ y ≤ t. (De
forma similar x ∧ y es la mayor de las cotas inferiores).
Por tanto es importante tener siempre en cuenta, que independiente-
mente de como venga definido un ret́ıculo, ya sea a partir de una relación
de orden (Ret́ıculo ordenado (E,≤)), o por medio de operaciones (ret́ıculo
algebraico (E,∨,∧)), tendremos siempre las dos cosas a la vez por tratarse
de conceptos equivalentes,
En (E,≤) tenemos operaciones
∨,∧ obtenidas de,
x ∨ y := sup({x, y})
x ∧ y := inf({x, y})
En (E,∨,∧) tenemos la relación de
orden definida
a ≤ b :⇔ a ∨ b = b
(O equivalentemente a ≤ b :⇔ a ∧
b = a)
y ambas cosas las usaremos a nuestro antojo a la hora de tratar con ret́ıculos.
Volvamos a los ejemplos,
3O equivalentemente a ≤ b :⇔ a ∧ b = a. ¡Probar esta equivalencia!
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 12
Ejemplo 1.8 El ret́ıculo ordenado (E, /) es también el ret́ıculo algebraico
(E,mcm,mcd). Aqúı las operaciones ∨ y ∧ son respectivamente el mı́nimo
común múltiplo mcm, y el máximo común divisor mcd.
Serán ciertas cualesquiera de las cuatro propiedades antes enunciados en
el teorema. Por ejemplo, la asociativa: amcm (bmcm c) = (amcm b) mcm c.
En realidad con la notación habitual esta propiedad dice
mcm(a,mcm(b, c)) = mcm(mcm(a, b), c).
Si hubiésemos querido demostrarla sólo con conceptos relativos a la divisi-
bilidad, veŕıamos que no nos resultaŕıa nada trivial.
Ejemplo 1.9 El ret́ıculo ordenado (P(E),⊆) es también el ret́ıculo alge-
braico (P(E),∪,∩). Las propiedades que se deducen ya las conoćıamos. Las
vimos en el primer tema.
No obstante en el conjunto de las partes de un conjunto se cumplen
otras propiedades que no las debe necesariamente satisfacer un ret́ıculo. Por
ejemplo no es necesario en un ret́ıculo la existencia del supremo o del ı́nfimo.
En (P(E),∪,∩) los tiene en el universal E y el vaćıo ∅. Como se vió en el
ejemplo de los enteros positivos con la relación divide, éste sólo teńıa ı́nfimo
1. Pero puede que no tenga ninguno de los dos. Veamos el ejemplo,
Ejemplo 1.10 En ZZ× ZZ se define la relación � como,
(a, b) � (c, d) :⇐⇒ a ≤ c y b ≤ d,
no es dif́ıcil probar que es, en efecto, una relación de orden y que es ret́ıculo
con las operaciones
(a, b) ∨ (c, d) = (máx{a, c},máx{b, d})
(a, b) ∧ (c, d) = (mı́n{a, c},mı́n{b, d})
.. .. .. .. .. .. .. ..
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
...
..
.
...
..
.
...
..
.
...
..
.
...
..
.
...
..
.
(−3, 0)
(−2, 0)
(−1, 0)
(0, 0)
(1, 0)
(2, 0)
(3, 0)
��
��
��
��
��
��
(−2,−1)
(−1,−1)
(0,−1)
(1,−1)
(2,−1)
(3,−1)
��
��
��
��
��
(−3, 1)
(−2, 1)
(−1, 1)
(0, 1)
(1, 1)
(2, 1)
��
��
��
��
��
(−2, 2)
(−1, 2)
(0, 2)
(1, 2)
��
��
��
(−1, 3)
(0, 3)
��
(−1,−2)
(0,−2)
(1,−2)
(2,−2)
��
��
��
(0,−3)
(1,−3)
��@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@
@@ @@
@@
@@
@@
@@
El diagrama de Hasse de este
ret́ıculo aparece a la derecha.
Podemos observar que al no es-
tar las funciones máximo y mı́nimo
acotadas en ZZ no existe entonces el
supremo y el ı́nfimo.
Los ret́ıculos con supremo e
ı́nfimo se llaman ret́ıculos acota-
dos. Tampoco es necesario que, co-
mo en el conjunto de las partes de
un conjunto, se verifiquen las pro-
piedades distributivas,
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 13
Definición 1.7 Un ret́ıculo es distributivo, si satisface las propiedades{
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
Distributiva
Los ejemplos de ret́ıculo de los divisores de n, (Dn, /) y el del conjunto
de las partes de un conjunto si son distributivos. El ejemplo que sigue es un
ret́ıculo no distributivo,
Ejemplo 1.11 Consideremos el ret́ıculo cuyo diagrama de Hasse es el que
aparece en la figura.
hi
ha hb hc
hs
�
�
�
�
@
@
@
@
Este ret́ıculo no es distributivo. Por ejemplo, para
los elementos a, b, c se tiene por una parte que
a ∧ (b ∨ c) = a ∧ s = a,
en cambio
(a ∧ b) ∨ (a ∧ c) = i ∨ i = i 6= a.
En lo que sigue reservamos el śımbolo 1 y el śımbolo
0 para representar respectivamente al supremo e ı́nfimo de cualquier ret́ıculo.
El siguiente teorema nos da nuevas propiedades de los ret́ıculos acotados.
Teorema 1.2 Sea E un ret́ıculo acotado, entonces:
1. 1, 0 son unicos.
2. a ∨ 1 = 1 a ∧ 0 = 0 Absorción
3. 0 ∨ a = a 1 ∧ a = a Identidad
Demostración. La demostración es dejada como sencillo ejercicio.
El concepto análogo al complementario de un conjunto, en el conjunto
de las partes de un conjunto es el siguiente,
Definición 1.8 Sea E un ret́ıculo acotado, con supremo 1 e ı́nfimo 0. Un
elemento a ∈ E posee complemento si existe en E al menos un elemento
a tal que a ∨ a = 1 y a ∧ a = 0.
Hay que observar que en la definición de complemento no se dice que
sea el complemento único. De hecho, en el ejemplo anterior de un ret́ıculo
no distributivo el elemento c posee dos complementos distintos, el a y el b.
De todas formas la unicidad está garantizada por la distributividad.
Teorema 1.3 Si E es distributivo, si a ∈ E posee complemento a, este es
único.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 14
Demostración. Supongamos que a posee dos complementos, sean éstos a1, a2.
Veamos que son necesariamente iguales.
Se tiene que a ∧ a1 = 0, por tanto, por un lado (a ∧ a1) ∨ a2 = 0 ∨ a2 =
(por el apartado 3 del anterior teorema) = a2.
Por otro lado, por distributividad, (a ∧ a1) ∨ a2 = (a ∨ a2) ∧ (a1 ∨ a2) =
1 ∧ (a1 ∨ a2) = (también por el apartado 3 del anterior teorema) = a1 ∨ a2.
Por tanto a2 = a1 ∨ a2.
Razonando de la misma forma se obtiene que a1 = a2∨a1. Como a1∨a2 =
a2 ∨ a1, entonces a1 = a2.
La condición de distributividad es necesaria para la unicidad del com-
plemento.
1.3. Algebras de Boole.
Los ret́ıculos que son distributivos y complementados se llaman ret́ıcu-
los booleanos o álgebras de boole. A partir de ahora cuando hagamos
referencia a las operaciones en estos ret́ıculos en lugar de poner ∨,∧ pondre-
mos respectivamente +, ·. (Incluso omitimos en las expresiones algebraicas
el uso del punto ·).
Además de las propiedades conocidas y que son comunes a cualquier
ret́ı culo, tenemos las siguientes:
Teorema 1.4 Sea (B,+, ·) un álgebra de boole, entonces para todo a, b de
B se tiene:
(1)
{
(a + b) = a · b
(a · b)′ = a + b
Leyes de Morgan
(2) (a) = a Doble negación
Demostración: (1) El complemento de a + b es ab si la suma y el producto
de ambos es respectivamente 1,0. Por una parte,
(a + b) + ab = ((a + b) + a)((a + b) + b) =
= ((b + a) + a)((a + b) + b) =
= (b + (a + a))(a + (b + b)) =
= (b + 1)(a + 1) = 11 = 1
por otra
(a + b)ab = aab + bab =
= 0b + 0a = 0 + 0 = 0.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 15
El resto se deja como ejercicio.
El ret́ıculo del ejemplo 1.5 del conjunto de las partes de A = {a, b, c}, es
un álgebra de Boole. Satisface ser distributivo, además el complemento de
cualquier conjuntoes justamente su complementario.
El ret́ıculo de los divisores de 20, a pesar de satisfacer la propiedad
distributiva, no es álgebra de Boole porque los elementos 2 y 10 no poseen
complemento. El complemento del 4 es el 5 y del 1 es el 20.
En el siguiente ejemplo se muestra el álgebra de Boole más simple. Des-
pués veremos su importancia
Ejemplo 1.12 El conjunto B = {0, 1} con las operaciones suma y pro-
ducto definidas como 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1, 00 = 0,
01 = 0, 10 = 0, 11 = 1 es un algebra de Boole con supremo 1 e infimo 0.
Este álgebra de Boole se llama álgebra de Boole trivial o de los dos
números. Es inmediato comprobar que Bn producto cartesiano de B, n veces,
es también con las operaciones inducidas, un álgebra de Boole.
1.3.1. Principio de Dualidad.
En las propiedades de los teoremas anteriores y que se resumen en la
tabla, se habrá observado que todas ellas vienen siempre en pareja,
{
a + b = b + a
ab = ba
Conmutativa{
a + (b + c) = (a + b) + c
a(bc) = (ab)c
Asociativa{
a + a = a
aa = a
Idempotencia{
a + (ab) = a
a(a + b) = a
Simplificativa{
a + (bc) = (a + b)(a + c)
a(b + c) = ab + ac
Distributiva{
a + 1 = 1
a1 = 1
Dominancia{
a + 0 = a
a1 = a
Identidad{
a + a = 1
aa = 0
Complemento{
(a + b) = ab
(ab)′ = a + b
Morgan
(a) = a Doble negación
esto no sucede por azar. Su justificación es la siguiente. Sea (E,≤) un conjun-
to ordenado, consideremos ≤−1 la relación inversa, de manera que a ≤−1 b
si y sólo si b ≤ a. Es inmediato probar que (E,≤−1) es también un conjunto
ordenado, y que si (E,≤) es un ret́ıculo, también lo es (E,≤−1).
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 16
Estos dos ret́ıculos ordenados y las operaciones definidas en ambos se
parecen mucho. En concreto la operación suma del ret́ıculo (E,≤) es la
operación multiplicación del ret́ıculo (E,≤−1) y la operación multiplicación
del ret́ıculo (E,≤) es la operación suma del ret́ıculo (E,≤−1).
Por lo tanto de cualquier enunciado válido que trate sobre propiedades
de los ret́ıculos se puede obtener otro reemplazando la relación ≤ por ≤−1 (o
por≥ ya que≤−1es la relación inversa de≤), la adición por la multiplicación,
y la multiplicación por la adición.
Definición 1.9 La expresión Dual P d de cualquier enunciado matemáti-
co P en la que vengan involucradas las operaciones booleanas +, ·, y las de-
sigualdades ≤,≥; se obtiene reemplazando el 0 por el 1, el 1 por el 0, el +
por el ·, el · por el + el ≤ por el ≥ y el ≥ por el ≤.
Ejemplo 1.13 En las propiedades de Morgan
{
1 := (a + b) = a · b
2 := (a · b) = a + b
el dual de la expresión 1 es la 2, y el dual de la expresión 2 es la 1. Podemos
poner 1d = 2, y que 2d = 1.
Ejemplo 1.14 Si 1 representa la expresión a ≤ a ∨ b, entonces 1d es a ≥
a ∧ b.
El dual del dual de cualquier enunciado P es evidente que coincide con
el propio P .
Supongamos ahora que T representa un teorema sobre álgebras de Boole.
Existe para ella una sucesión de enunciados que constituye una demostración
D. Entonces a la sucesión de enunciados que se obtiene al reemplazar por
su dual cada enunciado de D, se llama demostración dual de D. La
demostración dual de D sirve para demostrar el dual de T , es decir el teorema
T d.
Por tanto, cuando tengamos cualquier teorema T , también lo será su
dual T d. Probando cualquiera de ellos, estará automáticamente probado el
otro por dualidad.
Ejemplo 1.15 T d
1 , T
d
2 son los teoremas duales de T1, T2:
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 17
Teorema T1 Teorema T d
1
En un ret́ıculo acotado el extremo
superior s es único
En un ret́ıculo acotado el extremo
inferior i es único
Teorema T2 Teorema T d
2
Las condiciones (a), (b) son equi-
valentes
(a) a ≤ b
(b) a ∨ b = b
Las condiciones (a), (b) son equi-
valentes
(a) a ≥ b
(b) ab = b
1.3.2. Formas normales y teorema de Stone
El cardinal de una álgebra de Boole puede ser finito o infinito. Estudia-
mos el caso finito y vamos a ver que la estructura de estas álgebras finitas se
“parece” mucho al álgebra de Boole de las partes de un conjunto y tendrá
entonces un cardinal de 2n elementos.
Para probar estos resultados exponemos un teorema fundamental acerca
de la posibilidad de expresar cualquier elemento del álgebra como suma de
los átomos. Veamos primero algunos resultados acerca de los átomos:
Teorema 1.5 Sea B un álgebra de Boole,
(a) Si a es un átomo, entonces para todo b ∈ B se tiene, ab = 0 o ab = a
(b) Si a, b son átomos y a 6= b entonces ab = 0.
(c) Si B es finita y a1, a2, · · · an son todos sus átomos, a ∈ B, y se tiene
para todo i, (1 ≤ i ≤ n) que aia = 0, entonces a = 0
Demostración.
(a) Para cualquier par de elementos, a, b se tiene que ab ≤ a ya que
(ab)a = ab. Luego, en particular, si a es átomo y si ab ≤ a, entonces sólo es
posible que ab sea el 0, o el propio a.
(b) Ejercicio.
(c) Supongamos que al absurdo, a fuese distinto de 0. Consideremos el
conjunto A = {b ∈ B | 0 < b ≤ a}. A es no vaćıo ya que al menos contiene a a.
Como A es finito se puede elegir un elemento c ∈ A que sea inmediatamente
posterior al 0, es decir un átomo, y se tiene que ca = c 6= 0, lo que es una
contradicción.
Con esto, estamos en condiciones de poder enunciar y probar un teo-
rema fundamental acerca de la posibilidad expresar cualquier elemento del
álgebra de Boole en función de sus átomos, en lo que conoce como formas
normales.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 18
Teorema 1.6 Sea x 6= 0 elemento de un álgebra de Boole B finita. Si
a1, a2, · · · , ak son los átomos inferiores o iguales a x, entonces x = a1 +a2 +
· · ·+ ak, y es la única forma de expresar x como suma de atomos de B.
Demostración. El conjunto de los átomos inferiores o iguales a x es no
vaćıo, ya que los átomos de B son los elementos minimales del conjun-
to ordenado que se obtiene al suprimir de B el elemento 0. Expresemos
por {a1, a2, · · · , ak} el conjunto de esos átomos inferiores o iguales a x. Sea
y = a1 + a2 + · · ·+ ak. Probemos que y = x.
Es evidente que y ≤ x, ya que x es un mayorante común a a1, a2, · · · , ak
y mayorará a y que es el menor de los mayorantes.
Para probar la otra desigualdad, vemos que xy = 0 (¿porqué?). Para ello
haremos uso del apartado (c) del anterior teorema e intentaremos ver, que
para cualquier átomo a, axy = 0.
Consideramos axy con a átomo cualquiera, Según el teorema anterior,
apartado (a), ax es o bien 0 o bien a. Si es 0, ya se tiene que axy = 0y = 0,
y si es a, entonces a es uno de los átomos ai inferior o igual que x antes
considerados y en particular a ≤ y, es decir ay = a, por tanto, axy =
ayxy = 0. La igualdad x = y está probada.
Queda por ver que esta expresión, salvo permutación de los términos es
única. Supongamos que existen dos expresiones simultáneas x = a1 + a2 +
· · · + ak, x = b1 + b2 + · · · + br con ai, bj átomos. Un átomo cualquiera
ai, satisface aix = ai, pero sustituyendo la segunda expresión obtenemos
ai = aix = ai(b1 +b2 + · · ·+br) = aib1 +aib2 + · · ·+aibr. Dado que cada uno
de los términos aibj es un minorante de ai, y es producto de átomos, vale o
0 o ai. Si es ai al minorar a bj , necesariamente ai = bj . Como la suma no
es 0, podemos asegurar que en alguno de los sumandos obtenemos ai = bj ,
entonces cada uno de los ai es uno de los bj . Por tanto el conjunto de los ai
está en el de los bj .
Un razonamiento similar prueba que el conjunto de los bj está contenido
en los ai, los conjuntos coinciden y el teorema está probado.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 19
Ejemplo 1.16 Consideremos el álgebra de Boole B = (D210, /) de los
divisores de 210 con la relación divide.
1
2 3 5 7
6 10 14 15 21 35
30 42 70 105
210
�
�
�
�
�
��
A
AA
Q
Q
Q
Q
Q
Q
Q
Q
A
AA
�
��
�
�
�
�
�
��
�
��
�
��
�
��
�
��
�
��@
@@
@
@@
��
��
��
��
��
��
��
��
��
��
��
��
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
El conjunto de átomos de es-
te álgebra es {2, 3, 5, 7}. Considere-
mos un elemento al azar, por ejem-
plo el número 70. A través de los
caminos descendentes 70 − 10 − 2,
70− 35− 5, 70− 35− 7 que obser-
vamos en la figura, comprobamos
que los átomos inferiores o iguales
a 70, son 2, 5 y 7. Según el teorema
se tiene entonces que 70 = 2+5+7.
4
Una observación similar para
los demas elementos nos proporcio-
na que: 6 = 2 + 3, 10 = 2 + 5, 14 = 2 + 7, 15 = 3 + 5, 21 = 3 + 7, 35 = 5 + 7,
30 = 2 + 3 + 5, 42 = 2 + 3 + 7, 105 = 3 + 5 + 7, 210 = 2 + 3 + 5 + 7.
Cuando un elemento se expresa como suma de sus átomos menores o iguales
se dice que está expresado en forma normal disyuntiva.
Por el principio de dualidad también tenemos un teorema de unicidad
para el producto de superátomos:
Teorema 1.7 Sea x 6= 1 elemento de un álgebra de Boole B finita. Si
b1, b2, · · · , bk son los superátomos superiores o iguales a x, entonces x =
b1b2 · · · bk, y es la única forma de expresar x como producto de superátomos
de B.
Y cuando un elemento se expresa como producto de sus superátomos
mayores o iguales se dice que está expresado en forma normal conjuntiva.
En el ejemplo anterior, algunos de sus elementos expresados en forma
conjuntiva quedaŕıan como: 2 = 30 · 42 · 70, 3 = 30 · 42 · 105, 5 = 30 · 70 · 105,
7 = 42 · 70 · 105, . . .
En este caso a través de los caminos ascendentes buscamos los super-
átomos mayores o iguales. (De nuevo no debe haber confusión en la notación.
La operación producto se refiere al máximo común divisor).
Con todo lo expuesto hasta ahora podemos enunciar y probar el teorema
de Stone. Este teorema en esencia viene a decir que todas las álgebras de
4No debe haber confusión en el uso de la notación. La operación suma se refiere a la
operación mı́nimo común múltiplo, es decir mcm(2, 5, 7) = 70.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 20
Boole son “iguales” al algebra del conjunto de las partes de un conjunto.
No vamos a hacer la demostración para el caso de álgebras infinitas, pero
śı para el caso finito.
Previamente puntualizemos que en matemáticas decir que dos conjuntos
con operaciones en ellos definidas “son iguales”, significa que son isomorfos.
Un isomorfismo de álgebras de Boole entre B1, B2 es una aplicación
f : B1 → B2 que es homomorfismo y es biyectiva.
Teorema 1.8 Sea A el conjunto de los átomos de un álgebra de Boole B.
Entonces, B es isomorfa al álgebra de Boole (P(A),∪,∩) del conjunto de las
partes de sus átomos.
Demostración: Una demostración detallada con ayuda del teorema 1.6 de
que la aplicación: f : B → P(A) que asigna a cada elemento x de B el
conjunto {a1, a2, · · · , ak} de los átomos inferiores o iguales a x, se deja para
el lector.
Por tanto como el número de elementos del conjunto de las partes de
un conjunto de n elementos es 2n, todas las álgebras de Boole tienen ese
cardinal 5.
1.3.3. Subálgebras de Boole.
En esta sección presentamos la forma en que a partir de ciertos elementos
de un álebra B podemos generar otras álgebras.
Esta generación tendrá sus limitaciones: no será posible engendrar un
álebra de Boole infinita a partir de un número finito de elementos.
Es por este motivo por el que el estudio de las álgebras infinitas aunque
puedan tener interés en otras disciplinas más teóricas, no lo tienen tanto en
informática. Debemos comenzar por,
Definición 1.10 Un subconjunto S de un álgebra de Boole B es subálge-
bra de Boole, si, para las restricciones de las operaciones definidas en B,
S es también álgebra de Boole.
Es decir S está constituido por un conjunto de elementos de B cerrado
para las operaciones suma producto y complementación. De la definición se
deduce de forma inmmediata que los elementos 1, 0 pertenecen a cualquier
subálgebra S desde el momento en el que para cualquier elemento a de S,
S debe contener a y por tanto aa = 0 y a + a = 1.
5Puede probarse que este resultado es también cierto para el caso infinito, y aśı , el
cardinal de un álgebra de Boole infinita es al menos ℵ1 ya que corresponde al cardinal del
conjunto de las partes del menor conjunto infinito que es ℵ0
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 21
Ejemplo 1.17 Podemos considerar el algebra de Boole del conjunto de
las partes de A = {a, b, c}, y se tiene que S = {∅, {a}, {b, c}, {a, b, c}} es una
subálgebra suya.
En el ejemplo anterior hemos seleccionado adecuadamente algunos ele-
mentos que forman una subálgebra de Boole. Pero para encontrar una subálge-
bra de Boole también podemos hacer lo siguiente: tomar algunos elementos
del álgebra y calcular la menor subálgebra que los contenga. Considera-
mos dos elementos cualesquiera x, y de álgebra, si ambos pertenecen a una
subálgebra, deberán pertenecer también los elementos x+y, xy, x, y y cual-
quier operación entre todos ellos.
Pero, ¿Cuántas operaciones son necesarias para generar esa subálgebra?
¿Qué es una operación? La siguientes definiciones y el teorema que siguen,
nos lo aclara:
Definición 1.11 Sea (B,+, ·) álgebra de Boole. Una expresión boolea-
na sobre (B,+, ·) está definido recursivamente como,
1. Cualquier elemento de B es una expresión booleana.
2. Cualquier śımbolo de variable es una expresión booleana.
3. Si E, F son operaciones booleanas, también lo son E + F , EF , E.
Si la expresión booleana está formada exclusivamente por a1, a2, · · · ak
elementos de B la llamaremos operación booleana.
Ejemplo 1.18 En el conjunto (D6, /) de los divisores de 6 con la relación
“divide” si consideramos
((1 · 3) + 2) · 6
tenemos una operación booleana sobre esa álgebra de Boole.
En cambio si consideramos
((1 · x1) + 2) · x2
tenemos una expresión booleana sobre D6, que se convierte en operación
para cada par de valores x1, x2 que se les asigne.
En general si tenemos una expresión E(x1, x2, . . . xm) de m variables
sobre un álgebra de Boole B, con |B| = n elementos, entonces esta expresión
nos define nm operaciones.
Ejemplo 1.19 A la expresión booleana
E(x1, x2) = x1 + x2
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 22
sobre el álgebra de Boole (D6, /), le corresponden 42 operaciones, que son
las siguientes dependiendo de las asignaciones:
E(1, 1) = 1 + 1 = 1 + 6 = 6
E(1, 2) = 1 + 2 = 1 + 3 = 3
E(1, 3) = 1 + 3 = 1 + 2 = 2
E(1, 6) = 1 + 6 = 1 + 1 = 1
E(2, 1) = 2 + 1 = 2 + 6 = 6
E(2, 2) = 2 + 2 = 2 + 3 = 6
E(2, 3) = 2 + 3 = 2 + 2 = 2
E(2, 6) = 2 + 6 = 2 + 1 = 2
E(3, 1) = 3 + 1 = 3 + 6 = 6
E(3, 2) = 3 + 2 = 3 + 3 = 3
E(3, 3) = 3 + 3 = 3 + 2 = 6
E(3, 6) = 3 + 6 = 3 + 1 = 3
E(6, 1) = 6 + 1 = 6 + 6 = 6
E(6, 2) = 6 + 2 = 6 + 3 = 6
E(6, 3) = 6 + 3 = 6 + 2 = 6
E(6, 6) = 6 + 6 = 6 + 1 = 6
j1
j2 j3
j6
�
�
@
@
�
�
@
@
No está de más insistir de nuevo en que las ope-
raciones suma y producto corresponden respecti-
vamente al mı́nimo común múltiplo y al máximo
común divisor.
Al hacer los cálculos en esta álgebra, el uso del
diagrama de Hasse que aparece a la derecha evita
confusiones.
Ejemplo 1.20 Consideremos la expresión booleana de tres variables
E(x1, x2, x3) = ((x1 + x2) + x3)
sobre el álgebra de Boole trivial B = ({0, 1},+, ). La asignación de una terna
de valores a x1, x2, x3 de las 23 = 8 posibles en total nos da ocho operaciones.
Éstas son:
E(0, 0, 0) = ((0 + 0) + 0) = 0 = 1 E(0, 0, 1) = ((0 + 0) + 1) = 1 = 0
E(0, 1, 0) = ((0 + 1) + 0) = 1 = 0 E(0, 1, 1) = ((0 + 1) + 1) = 1 = 0
E(1, 0, 0) = ((1 + 0) + 0) = 1 = 0 E(1, 0, 1) = ((1 + 0) + 1) = 1 = 0
E(1, 1, 0) = ((1 + 1) + 0) = 1 = 0 E(1, 1, 1) = ((1 + 1) + 1) = 1 = 0
Si hubiésemos considerado la expresión F (x1, x2, x3) = (x1x2)x3 y pro-
cediéramos como en el ejemplo anterior a evaluarla, veŕıamos de inmediato
que obtenemos los mismosvalores. (Consecuencia de la Ley de Morgan).
Podemos por tanto formar una infinidad de expresiones aparentemente
distintas pero muchas de ellas al evaluarlas vemos que nos dan los mismos
valores. En estos casos diremos que las expresiones son equivalentes. Si dos
expresiones E, F de n variables lo son, escribimos,
E(x1, x2, . . . xn) = F (x1, x2, · · ·xn)
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 23
caso contrario se dirán que son no equivalentes.
Debemos preguntarnos entonces, ¿cuántas hay no equivalentes? Por su-
puesto el número dependerá del número de variables que tengan las expre-
siones.
Vamos a suponer primero que contiene una sóla variable x. Entonces es
evidente que sólamente existen 221 = 4 expresiones distintas:
E1(x) = 0 E2(x) = 1
E3(x) = x E4(x) = x
porque las operaciones · y + son cerradas sobre 1, 0, x, x sea cual sea el
valor de la variable x y no pueden entonces obtenerse otras expresiones no
equivalentes.
Para el caso de dos variables es algo más complicado de ver. El siguien-
te teorema nos aclarará esta cuestión. Necesitamos previamente hacer una
definición, y probar un lema que analiza el problema con 2 elementos y no
con 2 variables.
Definición 1.12 Una sugálgebra S de B se dice que esta generada por
a1, a2, · · · ak si todo x ∈ S es obtenido a traves de operaciones booleanas
efectuadas sobre a1, a2, · · · ak. Escribiremos 〈a1, a2, · · · ak〉.
Lema 1.1 El número de elementos del subálgebra de Boole S2 = 〈a, b〉
engendrada por los elementos a, b es finita y tiene a lo sumo 222 elementos.
Demostracion: Consideremos S ′2 = {0} ∪ {Sumas, con sumandos en ab, ab,
ab, ab}. Probemos que S ′2 = S2.
Por ser S2 álgebra de Boole y por contener a a, b contendra cualquier
operación con ellas, luego evidentemente S ′2 ⊆ S2.
Veamos que S2 ⊆ S ′2: los elementos a, a de S2 pueden expresarse a =
a(b + b) = ab + ab, a = ab + ab, igual para b, b. Por tanto están en S ′2.
Además resulta que S ′2 es estable para la suma por definición, lo es para
el producto por ser cero el producto de dos elementos distintos de entre
ab, ab, ab, ab, y lo es para la complementación por la ley de Morgan, (por
ejemplo, (ab) = a + b = ab + ab + ba + ba) Luego como cualquier operación
con a, b en S2 es a su vez una operación con elementos de S ′2, y al ser S ′2
cerrado para las operaciones booleanas, entonces S2 ⊆ S ′2, lo que prueba la
igualdad.
El número de elementos de S ′2 coincide con el del conjunto de las partes
de {ab, ab, ab, ab} porque cualquier suma de ellos se hace tomando una vez
cada sumando, y de cero hasta cuatro sumandos. Luego el cardinal de S ′2 es
222 , y el lema queda probado.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 24
La generalización de este lema para cualquier número k de elementos se
expresa en el siguiente corolario:
Corolario 1.9 El número de elementos de la subálgebra de Boole Sk en-
gendrada por los elementos a1, a2, · · · ak es finita y tiene a lo sumo 22k ele-
mentos.
Demostración: Considerando S ′k = {0}∪{Sumas, con sumandos en l1l2 · · · lk}
donde cada li representa o bien ai o bien ai. Como antes se tiene que Sk = S ′k.
Una demostración detallada del corolario es dejada como ejercicio.
Es importante observar que el teorema dice a lo sumo 22k elementos,
pudiendo según la naturaleza de los elementos elegidos, ser menos. Veamos
un ejemplo:
Ejemplo 1.21 Sea B el algebra de Boole de las partes de un conjunto E,
sean A,B dos subconjuntos. Los posibles casos de subálgebras engendra-
das, según la naturaleza de los conjuntos A y B son cuatro. Gráficamente
corresponden,
��
��
A ��
��
A
��
��
B
��
��
A
��
��
B
E E E E
|〈∅, ∅〉| = 2 |〈A, ∅〉| = 4 |〈A,B〉| = 8 |〈A,B〉| = 16
1. Si A = B = ∅ entonces evidentemente 〈A,B〉 = 〈∅, ∅〉 = {∅, E} tiene
sólo dos elementos.
2. Si uno de ellos es vaćıo y el otro no, 〈A, ∅〉 = {∅, A,A,E} tiene cuatro
elementos.
3. Si ambos son no vaćıos y disjuntos, A ∩ B = ∅ y por tanto en la
formación de uniones (Operación suma, +) esta interseción no inter-
viene. Aśı, sólo hay tres partes distintas para combinar: A ∩ B =
B, B ∩ A = A, A ∩ B, que nos dan 23 = 8 conjuntos que son
{∅, A,B,A,B,A ∩B,A ∪B,E}.
4. Si ambos son no vaćıos y no disjuntos disponemos de 4 = 22 partes
distintas, que al combinar por medio de uniones, nos dan los 24 = 16
conjuntos distintos.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 25
Teorema 1.10 El número de expresiones distintas de k variables es 22k .
Demostración: Si en lugar de considerar elementos a1, a2, . . . , ak, considera-
mos variables x1, x2, . . . xk las expresiones que son o bien el 0, o bien sumas
con sumandos en l1l2 . . . lk con cada li representando xi o bien xi son todas
expresiones distintas y como según el corolario anterior hay a lo sumo 22k ,
el teorema está probado.
Ejemplo 1.22 Las 222 = 16 expresiones distintas que podemos formar
con dos variables x, y son
E1(x, y) = 0 E2(x, y) = xy
E3(x, y) = xȳ E4(x, y) = x̄y
E5(x, y) = x̄ȳ E6(x, y) = xy + xȳ
E7(x, y) = xy + x̄y E8(x, y) = xy + x̄ȳ
E9(x, y) = xȳ E10(x, y) = xȳ + x̄ȳ
E11(x, y) = x̄y + x̄ȳ E12(x, y) = xy + xȳ + x̄y
E13(x, y) = xy + xȳ + x̄ȳ E14(x, y) = xy + x̄y + x̄ȳ
E15(x, y) = xȳ + x̄y + x̄ȳ E16(x, y) = xy + xȳ + x̄y + x̄ȳ
1.4. Funciones entre álgebras booleanas.
En esta sección estudiamos las funciones f :B1 → B2 entre álgebras de
Boole. Como sólo nos vamos a interesar en álgebras de Boole finitas, la
cantidad de estas funciones f va a ser finita. Pero ¿Cuántas de ellas pueden
escribirse por medio de una expresión booleana? Veremos que en un caso
todas. En ése en particular, mostraremos sus aplicaciones a la electrónica
digital. Resumiendo:
• Definimos y analizamos el conjunto F = {f | f :B1 → B2} de las fun-
ciones Booleanas.
• Buscamos las condiciones para que las funciones de F puedan escribirse
por medio de expresiones Booleanas.
• Se estudia en particular Fn = {f | f : {0, 1}n → {0, 1}} como ejemplo
de conjunto de funciones donde todas admiten una expresión booleana.
• Se estudian las aplicaciones del ejemplo anterior a los circuitos eléctri-
cos y redes de compuertas.
Teorema 1.11 El conjunto F = {f | f :B1 → B2} con las operaciones +, ·
definidas como
(f + g)(x) := f(x) + g(x) (f · g)(x) := f(x) · g(x) ∀x ∈ B1
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 26
es un álgebra de Boole 6.
Demostración: Verificar que (F ,+, ·) cumple las propiedades de idem-
potencia, conmutativa, asociativa, simplificativa y distributiva es sencillo.
Luego F es un ret́ıculo algebraico distributivo. El correspondiente ret́ıculo
ordenado (F ,≤), sabemos tiene definido el orden como
f ≤ g :⇔ f + g ≤ g
y como para que f +g = g, se debe tener para todo x de B1 que (f +g)(x) =
f(x) + g(x) = g(x) podemos entonces concluir que
f ≤ g ⇔ f(x) ≤ g(x) (∀x ∈ B1).
Si 0,1 son las funciones que asignan a cada elemento x de B1 respectivamente
al ı́nfimo 02 y al supremo 12 de B2
0: B1 → B2
x 7→ 0(x) = 02
1: B1 → B2
x 7→ 1(x) = 12
se tiene entonces que 0 y 1 son ı́nfimo y supremo de F , y por tanto es
un ret́ıculo distributivo acotado. El complemento f de una función también
existe y está necesariamente definido como
f : B1 → B2
x 7→ f(x) = f(x)
Por tanto (F ,+, ·) es un ret́ıculo distributivo con la propiedad de comple-
mento o álgebra de Boole.
Consideremos ahora que B1 y B2 son finitos con n,m átomos respectiva-
mente. Entonces |B1| = 2n y |B2| = 2m y el número de funciones entre ellos
es (2m)2n = 2m2n . Como según acabamos de ver todas juntas constituyen el
álgebra de Boole de las funciones, este algebra tendrá entonces m2n átomos.
Veamos un ejemplo.
Ejemplo 1.23 Consideremos las funciones entre el álgebra de Boole tri-
vial ({0, 1},+, ·) y el de las partes de {a, b} con las operaciones unión e
6No debe existir confusión alguna si usamos los mismosśımbolos de operadores +, ·,
para definir estas operaciones entre funciones.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 27
intersección (P({a, b}),∪,∩). Hay en total 42 = (22)21 = 24 = 16 funciones
y constituyen un álgebra de Boole con cuatro átomos. No es dif́ıcil deducir
que estas funciones átomos f1, f2, f3, f4 son las que se expresan en forma
tabular:
x f1(x) x f2(x) x f3(x) x f4(x)
0 ∅ 0 ∅ 0 {a} 0 {b}
1 {a} 1 {b} 1 ∅ 1 ∅
las demás funciones las podemos ir construyendo como sabemos por el teo-
rema 1.6, haciendo sumas con estas cuatro, y obtenemos
f5 := f1 + f2
f6 := f1 + f3
f7 := f1 + f4
f8 := f2 + f3
f9 := f2 + f4
f10 := f3 + f4
f11 := f1 + f2 + f3
f12 := f1 + f2 + f4
f13 := f1 + f3 + f4
f14 := f2 + f3 + f4
0
f1 f2 f3 f4
f5 f6 f7 f8 f9 f10
f11 f12 f13 f14
1
�
�
�
�
�
��
A
AA
Q
Q
Q
Q
Q
Q
Q
Q
A
AA
�
��
�
�
�
�
�
��
�
��
�
��
�
��
�
��
�
��
@
@@
@
@@
��
��
��
��
��
��
��
��
��
��
��
��
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
HH
que junto con las funciones 0 y 1
son en total 16.
El diagrama de Hasse de este
ret́ıculo aparece a la derecha. Pode-
mos observar que es muy parecido al
ret́ıculo de los divisores de 210 que an-
tes vimos. En realidad son los mismos,
es decir son dos ret́ıculos isomorfos.
Expresadas en tablas estas funcio-
nes son:
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 28
x f5 = f1 + f2 x f6 = f1 + f3 x f7 = f1 + f4
0 ∅ 0 {a} 0 {b}
1 {a, b} 1 {a} 1 {a}
x f8 = f2 + f3 x f9 = f2 + f4 x f10 = f3 + f4
0 {a} 0 {b} 0 {a, b}
1 {b} 1 {b} 1 ∅
x f11 = f1 + f2 + f3 x f12 = f1 + f2 + f4 x f13 = f1 + f3 + f4
0 {a} 0 {b} 0 {a, b}
1 {a, b} 1 {a, b} 1 {a}
x f14 = f2 + f3 + f4 x 0 x 1
0 {a, b} 0 ∅ 0 {a, b}
1 {b} 1 ∅ 1 {a, b}
1.4.1. Funciones booleanas.
Es evidente como acabamos de ver en el ejemplo anterior que resulta
tediosa la manipulación de funciones entre álgebras de Boole si ha de hacerse
por medio tablas.
Seŕıa deseable al igual que ocurre con las funciones de variable real,
disponer de fórmulas para poder expresarlas y operar con ellas. Con variables
en los reales, cualquier expresión en la que se vean involucradas sumas,
restas, productos, cocientes . . ., nos define una función f : IR→ IR. Podemos
aśı obtener una infinidad de ellas, que aunque evidentemente no son todas las
que existen, si lo son en cantidad suficiente para considerarlas en el estudio
del cálculo.
En cambio cualquier función f :B → B entre álgebras de Boole, de te-
ner alguna regla que permita asignar a cada x una fórmula f(x), será sólo
una de las 221 = 4 posibles expresiones que nos asegura el teorema 1.10,
concretamente, 0, 1, x, x.
Por tanto si el cardinal de B es 2k, existen entonces (2k)2k = 2k2k fun-
ciones de las cuales sólo cuatro de ellas son afortunadas de poder escribirse
como expresión booleana, a no ser que k = 1 con lo que lo seŕıan todas.
Si consideramos funciones f :Bn → B ocurre algo similar. Si queremos
una regla que asigne a cada (x1, x2, . . . , xn) una fórmula f(x1, x2, . . . , xn),
será sólo una de las 22n posibles que nos garantiza el teorema 010. Pero el
número de estas funciones es 2k2nk
, y de nuevo, sólo serán todas expresables
si k = 1.
Un análisis similar para funciones f :Bn → Bm nos hace ver que sólo
2m2n son expresables de un total de 2mk2nk
, y también si queremos que sean
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 29
todas, es necesario que k = 1.
Si k = 1 significa que B es el álgebra de boole trivial {0, 1} o cualquier
otra isomorfa a ella. Pero esta condición no va a ser sólo necesaria sino
también suficiente. Veámoslo.
Antes, vamos a formalizar los conceptos:
Definición 1.13 Una función f :Bn → Bm es función booleana si exis-
ten E1, E2, · · · , Em expresiones booleanas tales que para todo (x1, x2, . . . , xn)
de Bn
f(x1, x2, . . . , xn) =

E1(x1, x2, . . . , xn)
E2(x1, x2, · · · , xn)
...
Em(x1, x2, . . . , xn)

Aunque se expresa una definición para el caso general, todo el estudio que
sigue es para funciones f :Bn → B. En este caso f es función booleana si y
sólo si existe una expresión booleana E tal que para todo (x1, x2, . . . , xn)
de Bn, f(x1, x2, . . . , xn) = E(x1, x2, . . . , xn). Los resultados que se obtienen
pueden generalizarse de inmediato.
Ejemplo 1.24 Para las funciones f, g definidas de (D6, /)2 hacia (D6, /)
que se expresan en forma tabular
(x1, x2) f(x1, x2) (x1, x2) g(x1, x2)
(1, 1) 6 (1, 1) 1
(1, 2) 3 (1, 2) 1
(1, 3) 2 (1, 3) 6
(1, 6) 1 (1, 6) 1
(2, 1) 6 (2, 1) 6
(2, 2) 6 (2, 2) 2
(2, 3) 2 (2, 3) 3
(2, 6) 2 (2, 6) 3
(3, 1) 6 (3, 1) 3
(3, 2) 3 (3, 2) 6
(3, 3) 6 (3, 3) 1
(3, 6) 3 (3, 6) 2
(6, 1) 6 (6, 1) 2
(6, 1) 6 (6, 2) 3
(6, 1) 6 (6, 3) 2
(6, 6) 6 (6, 6) 3
resulta que f(x1, x2) = x1 + x̄2, por tanto es función booleana. En cambio
g no lo es por no existir expresión alguna para ella. ¿Porqué? La justifición
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 30
es la siguiente: Supongamos que existe una expresión E(x1, x2) para g. Pero
esta expresión define necesariamente la misma función que
E(x1, x2) = 6 · E(x1, x2)
= (x1 + x̄1)E(x1, x2) = x1E(x1, x2) + x̄1E(x1, x2)
= x1E(6, x2) + x̄1E(1, x2) (Porqué?)
y en particular si x1 = 2 y x2 = 3 entonces de una parte tendŕıamos
E(x1, x2) = E(2, 3) = 3 y de otra E(x1, x2) = 2 · E(6, 3) + 3 · E(1, 3) =
2 · 2 + 3 · 6 = 2 + 3 = 6 lo que es contradicción.
Ya sab́ıamos que hab́ıan, y acabamos de ver y probar un ejemplo de
función que no es booleana. Pero ¿Cómo se calcula la expresión para una
función booleana? Entre álgebras de boole como la del ejemplo anterior en
la que no todas las funciones son funciones booleanas, nos vemos obligados
a hacerlo por tanteo. Pero no va a ser aśı en el caso en que tratemos con un
álgebra de Boole de funciones donde todas las son booleanas.
El teorema que sigue nos proporciona un procedimiento constructivo
para el cálculo de la expresión booleana de una función.
Teorema 1.12 En el conjunto Fn = {f | f : {0, 1}n → {0, 1}} todas las
funciones son booleanas, y admiten como expresión
f = m1 + m2 + · · ·+ mr
donde cada mj, (1 ≤ j ≤ r) es de la forma mj = l1l2 . . . ln en donde los li,
(1 ≤ i ≤ n) representa o bien xi ó x̄i.
Demostración: Como sabemos por el teorema 1.6 todo elemento puede ex-
presarse como suma de los átomos inferiores. Si verificamos que en esta
álgebra de Boole Fn, los átomos son los mj el teorema estará probado.
Esto es inmediato. Existen 2n átomos en Fn. Cada uno de estos átomos
m viene definido de forma única por un elemento (a1, a2, . . . an) de {0, 1}n,
de la siguiente forma
m(x1, x2, . . . , xn) =
{
1 si (x1, x2, . . . , xn) = (a1, a2, . . . , an)
0 si (x1, x2, . . . , xn) 6= (a1, a2, . . . , an)
y entonces la función m = l1l2 . . . ln donde
li =
{
xi si ai = 1
x̄i si ai = 0
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 31
es una expresión booleana que define a m, ya que el producto de n elementos
sólo puede ser 1, cuando todos los sean, y esto se dará sólo para el elemento
(a1, a2, . . . an). El teorema está probado.
Las funciones átomos mj se llaman mintérminos, y tienen este nom-
bre porque los átomos son los elementos minimales que tiene Fn una vez
suprimido el ı́nfimo. Las funciones xi, x̄i se llaman literales. Una función
booleana f expresada en suma de mintérminos no es otra que la expresión
en forma normal disyuntiva de f . Escribiremos f.n.d
Ejemplo 1.25 Consideremos la función f ∈ F3 definida en la tabla,
(x1x2x3) f(x1x2x3)
(000) 1
(001) 0
(010) 1
(011) 0
(100) 0
(101) 0
(110) 1
(111) 0
esta función resulta ser la suma de tres funciones átomos m1, m2, m3:
(x1x2x3) m1(x1x2x3) (x1x2x3) m2(x1x2x3) (x1x2x3) m3(x1x2x3)
(000) 1 (000) 0 (000) 0
(001) 0 (001) 0 (001) 0
(010) 0 (010) 1 (010) 0
(011) 0 (011)0 (011) 0
(100) 0 (100) 0 (100) 0
(101) 0 (101) 0 (101) 1
(110) 0 (110) 0 (110) 0
(111) 0 (111) 0 (111) 0
m1(x1x2x3) = x̄1x̄2x̄3 m2(x1x2x3) = x̄1x2x̄3 m1(x1x2x3) = x1x̄2x3
por tanto la forma normal disyuntiva de esta función es
f(x1x2x3) = x̄1x̄2x̄3 + x̄1x2x̄3 + x1x̄2x3
Puede ser redactado el teorema dual del teorema 1.12 y resulta igualmente
que todas las funciones f de Fn admiten una expresión
f = M1 ·M2 · · · · ·Ms
donde cada Mj , (1 ≤ j ≤ s) es de la forma Mj = l1 + l2 + · · · + ln con li,
(1 ≤ i ≤ n) o bien xi, ó x̄i.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 32
Los términos Mj se llaman maxtérminos ya que son superátomos, es
decir, los elementos maximales que resultan al suprimir en Fn el supremo. Al
igual que con los átomos, un elemento (a1, a2, . . . an) define de forma única
un superátomo M , de la forma
M(x1, x2, . . . xn) =
{
1 si (x1, x2, . . . xn) 6= (a1, a2, . . . an)
0 si (x1, x2, . . . xn) = (a1, a2, . . . an)
cuya expresión booleana es Mj = l1 + l2 + · · · ln donde
li =
{
xi si ai = 0
x̄i si ai = 1
Volviendo de nuevo al ejemplo anterior, la función f al tomar valor cero
para los 5 elementos (001), (011), (100), (110), (111) puede ser expresada
como producto de 5 maxtérminos de la forma:
f(x1x2x3) = (x1+x2+x̄3)(x1+x̄2+x̄3)(x̄1+x2+x3)(x̄1+x̄2+x3)(x̄1+x̄2+x̄3)
Una funcióm expresada como producto de maxtérminos es la expresión
en forma normal conjuntiva. Escribiremos f.n.c
Es posible utilizar una notación más cómoda que nos va a permitir ex-
presar las f.n.d y f.n.c de una función booleana. Supongamos que en Fn
consideramos los elementos de Bn como números binaros, y los disponemos
siempre ordenados de menor a mayor para expresar una función en una
tabla.
De esta forma, por ejemplo en el caso n = 3, los ocho números binarios
ordenados corrresponden a los ocho números decimales 0, 1, 2, 3, 4, 5, 6, 7
Binario Decimal mintérmino maxtérmino
(x1x2x3) que define que define
000 0 x̄1x̄2x̄3 x1 + x2 + x3
001 1 x̄1x̄2x3 x1 + x2 + x̄3
010 2 x̄1x2x̄3 x1 + x̄2 + x3
011 3 x̄1x2x3 x1 + x̄2 + x̄3
100 4 x1x̄2x̄3 x̄1 + x2 + x3
101 5 x1x̄2x3 x̄1 + x2 + x̄3
110 6 x1x2x̄3 x̄1 + x̄2 + x3
111 7 x1x2x3 x̄1 + x̄2 + x̄3
y cada uno de estos números binarios x1x2x3 nos define de forma única
un mintérmino cuando para sólo en ese número la función vale 1, y un
maxtérmino cuando para sólo en ese número la función vale 0.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 33
Aśı entonces podemos expresar la f.n.d de una función como la del ejem-
plo 1.25 anterior de una manera más resumida como,
f(x1, x2, x3) =
∑
i=0,2,6
mi
donde mi es el mintérmino que define el elemento de B3 que en decimal se
expresa por i 7.
También podemos expresar la f.n.c de la función del mismo ejemplo como
f(x1x2x3) =
∏
i=1,3,4,5,7
Mi
donde Mi es el maxtérmino que define el elemento de B3 que en decimal
se expresa por i. Por supuesto podemos pensar que cuando n es grande al
ser el valor de i cualquiera entre 0 y 2n − 1, que esta notación tampoco es
de mucha utilidad. Sin embargo, tal y como vamos a ver en un próximos
ejemplos el uso de funciones de Fn para valores de n superiores a 6 no se
hace con mucha frecuencia 8.
Estas notaciones son muy útiles para poder pasar indistintamente de la
f.n.c a la f.n.d y viceversa por tratarse de conceptos duales. Bastará sus-
tituir entre
∑
y
∏
, mi y Mi, y el conjunto de valores i por el conjunto
complemento.
Ejemplo 1.26 La función f :B4 → B cuya f.n.c es
f(x1x2x3x4) =
∏
i=0,2,3,7,11,12,13
Mi
tiene como f.n.d
f(x1x2x3x4) =
∑
i=1,4,5,6,8,9,10,14,15
mi
Hasta este momento todas las funciones de Fn que hemos dado y mane-
jado en los ejemplos se han hecho por medio de tablas, y desde ella sabemos
encontrar su formas normales. Pero también es posible que las funciones
nos vengan dadas por una expresión booleana cualquiera. Para encontrar
7En muchos textos, se suele utilizar la notación
∑
m(0, 2, 6) para expresar lo mismo.
Nosotros preferimos usar esta otra que nos parece más correcta.
8Hay que tener en cuenta que el cardinal de Fn aumenta muy rápidamente cuando lo
hace n. Se tiene que |F3| = 223 = 256 que no es muy grande, |F4| = 224 = 65,536 que
ya śı lo es, pero los cardinales |F5| = 4,292,967,296 y |F6| = 18,446,744,073,709,551,616
se disparan. Existe cantidad sufuciente de funciones, cada una con propiedades distintas,
para poder elegir.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 34
la forma normal podemos proceder de dos formas. Una de ellas es escribir
la tabla y hacer como antes (proceso largo para n > 3), y la otra, usar las
leyes del álgebra de Boole y manipular las expresiones. Veamos un par de
ejemplos.
Ejemplo 1.27 Dada f(x, y, z, w) = yz̄w + xy calcula su f.n.d 9.
Solución: Se examina cada sumando y se transforma en suma de otros
dos con un literal más, hasta que contenga los cuatro literales:
• yz̄w = 1yz̄w = (x + x̄)yz̄w = xyz̄w + x̄yz̄w (1)
• xy = xy1 = xy(z + z̄) = xyz + xyz̄
◦ xyz = xyz1 = xyz(w + w′) = xyzw + xyzw′ (2)
◦ xyz̄ = xyz1 = xyz̄(w + w′) = xyz̄w + xyz̄w′ (3)
y después teniendo en cuenta la propiedad idempotente, la suma de las
expresiones (1) (2) (3) una vez ordenadas nos da
f(x, y, z, w) = x̄yz̄w + xyz̄w′ + xyz̄w + xyzw′ + xyzw
cuya expresión con notación de sumatoria es
f(x, y, z, w) =
∑
i=5,12,13,14,15
mi
Ejemplo 1.28 Dada f(x, y, z) = (x + z̄)y, calcula su f.n.c
Solución: Aqúı realizamos el proceso dual al anterior, es decir, examina-
mos los productos por separado, y los transformamos en producto de otros
dos con un literal más, hasta que contenga los tres literales
• x + z̄ = x + z̄ + 0 = x + z̄ + (yȳ) = (x + y + z̄)(x + ȳ + z̄)
• y = y + 0 = y + (zz̄) = (y + z)(y + z̄)
◦ y + z = 0 + y + z = (xx̄) + y + z = (x + y + z)(x̄ + y + z)
◦ y + z̄ = 0 + y + z̄ = (xx̄) + y + z̄ = (x + y + z̄)(x̄ + y + z̄)
el producto de las expresiones una vez ordenadas nos da
f(x, y, z) = (x + y + z)(x + y + z̄)(x̄ + y + z̄)(x + ȳ + z̄)(x̄ + y + z)
que en notación de producto resulta
f(x, y, z) =
∏
i=0,1,2,3,4
Mi
9Este cambio en la notación se hace con objeto de facilitar la manipulación de las
variables.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 35
Está claro que las expresiones inicialmente dadas en los ejemplos ante-
riores resultaban ser más sencillas y económicas de escribir que sus formas
normales.
En general, como vamos a ver en la próxima sección, el problema que
más interesa es el rećıproco. Es decir, dada cualquier expresión, deseamos
poder “simplificarla” al máximo. La necesidad de la simplificación queda
aún más justificada en los ejemplos de funciones entre álgebras de boole que
seguidamente siguen: Los circuitos eléctricos y las redes de compuertas.
Circuitos eléctricos.
Consideremos un circuito eléctrico en el que pueden disponerse junto con
una fuente de alimentación, sólo cables e interruptores dispuestos en serie y
en paralelo. Analizémoslo desde sus partes más elementales:
1. Un interruptor puede ser considerado como una variable x, en el senti-
do de que puede tomar el valor si si el interruptor está dispuesto para
que pueda fluir la corriente, y el valor no si lo está en caso contrario
de forma que la corriente no fluye.
Por tanto si consideramos el conjunto {no, si} establecemos en él el
orden no ≤ si, y deducimos de este orden las operaciones +, ·, entonces
x es una variable del álgebra de Boole de dos elementos
{{no, si},+, ·}
También entonces x̄ designará una variable que valdrá si si la corriente
no pasa, y no en caso contrario.
Dos interruptores pueden ser considerados a su vez como una variable
(x1, x2) del conjunto producto del anterior
{{no, si}2,+, ·}
y en general (x1, x2, . . . , xn) es una variable de
{{no, si}n,+, ·}
2. Una vez analizados los interruptores, analizemos circuitosque los con-
tienen.
Consideremos el circuito C de la figura. Lo que nos interesa de él
es saber cuándo dejará pasar la corriente de un extremo del mismo
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 36
hasta el otro. Por supuesto dependerá de la disposiciones de los tres
interruptores que hay en el circuito. En total hay 8 alternativas, y para
cada una de ellas la corriente “si” fluye o “no” fluye.
Todas las posibilidades se resumen en la tabla,
-
x3
x1 x2
-
Circuito C.
x1x2x3 fc(x1x2x3)
no no no no
no no si si
no si no no
no si si si
si no no no
si no si si
si si no si
si si si si
Podemos por tanto considerar el circuito C como el elemento fc del
algebra de Boole de las funciones
F = {f : {no, si}3 → {no, si}}
que aparece descrita en dicha tabla.
Si un circuito es entonces una función, ¿qué funciones representan a
los circuitos que son la disposiciones en paralelo y en serie de otros
dos A y B? En el primer caso como la corriente fluye cuando lo hace
en alguno de los dos A, o B corresponderá a la operación de F que
hayamos identificado como la suma. Como de circuitos se trata, pode-
mos denominarla PAR de “paralelo”. En el segundo como la corriente
pasa sólo si lo hace por ambos, corresponde a la operación producto y
aqúı la llamaremos SER de “serie”. Y rećıprocamente dada una función
de (F , PAR, SER) es posible trazar un circuito, disponiendo en serie los
tramos que estén ligados por SER y en paralelo los que lo estén por
PAR.
Por tanto el circuito que resulta de la función
f(x1x2x3) = (x1SERx2)PARx3
es el circuito C de la figura.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 37
Pero, por otra parte, el circuito C dado que está representado por la
función fc de la tabla admite la expresión booleana en f.n.c
f(x1, x2, x3) = (x̄1SERx̄2SERx3)PAR(x̄1SERx2SERx3)PAR
PAR (x1SERx̄2SERx3)PAR(x1SERx2SERx̄3)PAR
PAR (x1SERx2SERx3)
que si a su vez lo volvemos a dibujar obtenemos
x̄1 x̄2 x3
x̄1 x2 x3
x1 x̄2 x3
x1 x2 x̄3
x1 x2 x3
- -
circuito que aunque de distinto aspecto al anterior, tiene las mismas
propiedades. En este caso también los llamamos equivalentes.
En general un circuito C con n interruptores, será entonces una función
de
F = {f : {no, si}n → {no, si}}
3. Resumiendo, si identificamos no con el 0, y si con el 1, tenemos que
{{no, si}n,+, ·} y F no son otros sino {{0, 1}n,+, ·} y Fn, y todo lo
expuesto puede enunciarse como
Teorema 1.13 A cada circuito C con n interruptores le corresponde
de forma única una función fc de Fn, y rećıprocamente.
El siguiente ejemplo nos muestra ¡por fin! una utilidad a toda la teoŕıa
desarrollada:
Ejemplo 1.29 Se desea diseñar un circuito que conste de 4 interruptores,
en los que cada uno sirva para decidir votar a favor o en contra a cuatro
miembros 1, 2, 3, 4 de un tribunal, de forma que
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 38
1. En caso de empate se considera no superada la votación a no ser que
4 haya votado favorable.
2. El votante 1 tiene derecho a veto.
Podemos considerar que los votantes 1, 2, 3, 4 disponen cada uno de un in-
terruptor x1, x2, x3x4 que cerrarán si quieren votar si y no tocarán en caso
contrario. Supongamos que el votante 1 es el que tiene tiene derecho a veto.
Es este caso, el circuito que satisface estas exigencias, es aquél que define la
función f que se expresa en la tabla:
x1x2x3x4 Decimal f(x1x2x3)
0000 0 0
0001 1 0
0010 2 0
0011 3 0
0100 4 0
0101 5 0
0110 6 0
0111 7 0
1000 8 0
1001 9 1
1010 10 0
1011 11 1
1100 12 0
1101 13 1
1110 14 1
1111 15 1
entonces la función es
f(x1x2x3) =
∑
i=9,11,13,14,15
mi
= x1x̄2x̄3x4 + x1x̄2x3x4 + x1x2x̄3x4 + x1x2x3x̄4 + x1x2x3x4
con lo que tendŕıamos resuelto el problema del diseño del circuito.
Pero es evidente que este circuito debe de poder hacerse de forma me-
nos compleja: Si tenemos en cuenta que podemos permutar y repetir los
mintérminos mi, tenemos que
f(x1x2x3) = (m9 + m13) + (m11 + m15) + (m14 + m15)
= (x1x̄3x4) + (x1x3x4) + (x1x2x3)
= x1x4 + x1x2x3
expresión equivalente a la anterior que nos proporciona un ahorro conside-
rable a la hora de construir el circuito que deseamos.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 39
Redes de compuertas
En el diseño y construcción del hardware de ordenadores y otros aparatos
electrónicos, es necesario obener redess que puedan producir salidas con valor
0 o 1 a partir de n entradas dadas, con valores también 0,1. Es decir, circuitos
que representan funciones de Fn. Para ello, se usan unos dispositivos (en
realidad microcircuitos), que son funciones de F1 y de F2 y que son llamados
compuertas lógicas. Principalmente las compuertas que se usan con mayor
frecuencia son las seis básicas que siguen, representadas esquematicamente:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
y
x
y
x
x
y
x
y
x
y
x
OR(x, y)
AND(x, y)
NOT(x)
NOR(x, y)
NAND(x, y)
XOR(x, y)��
HH
�
�
�
�
d
d
d
cada una de ellas, salvo la NOT que es función de F1, es una función de F2.
Concretamente,
NOT(x) = x
OR(x, y) = x + y
NOR(x, y) = x + y := x ↑ y
AND(x, y) = xy
NAND(x, y) = xy := x ↓ y
XOR(x, y) = xy + xy := x⊕ y
Si tomamos por ejemplo las funciones NOT, AND y OR y las considera-
mos como simples operadores (sólo nos fijamos en la regla con que se obtiene
un elemento a partir de otros dos dados), como cualquier función de Fn se
expresa con esos tres operadores podemos construir otras funciones de Fn.
Veamos un sencillo ejemplo:
Ejemplo 1.30 Expresar un circuito con dispositivos NOT, AND y OR que
represente la función de F3, f(x, y, z) = x + yz.
Dado que x+ yz = OR(x, yz) = OR(NOT(x),AND(y, z)) entonces su co-
rrespondiente red se construye observando de derecha a izquierda la anterior
expresión y trazándose las respectivas compuertas. La red que resulta es:
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 40
-
-
-
-
z
y
x x + yz��
HH
�
�
d
Es cierto que |F2| = 16, y que podemos entonces tener hasta 16 compuertas
distintas, pero, la eficacia y economı́a de costo de los circuitos construidos
principalmente con estas seis compuertas hace que sean las más usados 10.
El desarrollo y estudio exaustivo de las redes de compuertas no tiene ca-
bida en este texto, y se tratan en otras materias como base de la electrónica.
No nos extendemos más, pero no obstante, por último vamos a exponer un
ejemplo interesante de cómo son usados estos dispositivos para fabricar una
circuito que sirva para sumar números binarios en un ordenador.
Ejemplo 1.31 Al sumar dos números binarios vamos a obtener dos d́ıgitos
binarios. Uno de ellos será la suma parcial y el otro el acarreo. Como
podemos observar en la tabla,
x y Acarreo Suma
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
10En este texto no se analiza la forma en que estas compuertas pueden ser construidas, es
objeto de estudio de otras materias. Nosotros aqúı nos limitamos a tratar una compuerta
fijándonos exclusivamente en las propiedades de la función que define.
Es interesante observar no obstante que es posible con sólo compuertas del tipo NAND
o con sólo del tipo NOR, trazar cualquier circuito. Este hecho puede ser enunciado como
un teorema,
Teorema 1.14 Para sintetizar una función booleana cualquiera siempre es posible
construir un circuito compuesto únicamente por compuertas NAND, o bien por compuertas
NOR.
Demostración: Es suficiente mostrar que las compuertas NOT, OR, AND pueden ser expre-
sadas en función de aquellas. Veamos la expesión en función de NAND. La función NOT
se obtiene, NOT(x) = x = xx = x ↓ x,
La función OR(x, y) = x + y = x̄ȳ = x̄ ↓ ȳ = (x ↓ x) ↓ (y ↓ y) y la función AND(x, y) =
xy = xy + xy = xy · xy = (x ↓ y) ↓ (x ↓ y).
Las expresiones de estas tres en función de compuertas NOR, es dejada como ejerci-
cio.
Departamento deMatemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 41
“acarreo” y “suma” resultan ser funciones booleanas de F2, respectivamente
A(x, y) = xy, S(x, y) = xy + xy = x⊕ y.
-
-
-
-
y
x
xy A
x⊕ y S
�
�
•
•
Definimos entonces Se-
misumador como una fun-
ción de {0, 1}2 en {0, 1}2 que
a cada par (x, y) hace co-
responder su suma binaria
(xy, x⊕y). El correspondien-
te circuito semisumador que
aparece a la derecha, tiene dos salidas A,S (una por función), y proporciona
la suma AS.
Al sumar tres números binarios, también obtenemos dos d́ıgitos binarios,
suma parcial S, y acarreo A. La tabla correspondiente es,
x y z Acarreo Suma
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
Observándola, resulta que S = (x ⊕ y) ⊕ z = x ⊕ y ⊕ z 11, y que A =
xyz+xyz+xyz+xyz = (xyz+xyz)+(xyz+xyz)+(xyz+xyz) = xy+xz+yz.
Definimos pues Sumador a una función de {0, 1}3 en {0, 1}2 que asigna
a cada terna (x, y, z) el par (xy + xz + yz, x⊕ y ⊕ z). Si tomamos en lugar
de xy+xz + yz la expresión equivalente xy+ z(x+ y), la red que representa
el sumador puede dibujarse con una compuerta menos. Es la siguiente:
-
-
-
-
-
z
y
x
xy + z(x + y)
x⊕ y ⊕ z
A
S�
 �
•
•
•
•
•
11Es fácil comprobar que ⊕ considerado como operador es asociativo.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 42
Finalmente, usando los circuitos semisumadores y sumadores podemos fa-
bricar otros que sirvan para sumar números binarios de cualquier longitud
de d́ıgitos. En particular para tres, si queremos sumar X = x3x2x1 con
Y = y3y2y1, la red
-
-
-
-
-
-
-
-
-
-
y3
x3
y2
x2
y1
x1
z4
z3
z2
z1
Semisumador
Sumador
Sumador
proporciona la suma X + Y = z4z3z2z1. Obsérvese que lo hace de la misma
forma que el algoritmo común de suma de números, es decir, teniendo en
cuenta que el bit que “se lleva” se considera en la próxima suma binaria.
1.4.2. Simplificación de expresiones booleanas. Diagramas
de Karnaugh
En esta sección expondremos lo necesario para abordar métodos de sim-
plificación de fórmulas.
Observemos la función f(x, y, z) = xȳz̄+xȳz+xyz̄+xyz. Utilizando las
propiedades distributiva y de complemento podemos deducir que f(x, y, z) =
xȳ(z̄ + z) + xy(z̄ + z) = xȳ + xy = x(ȳ + y) = x.
En este caso un breve tanteo ha sido suficiente para llegar rápidamente
a comprobar que f era simplemente x. Pero seŕıamos optimistas si preten-
diésemos encontrar con la misma rapidez una simplificación de la fórmula
f(x, y, z, w) = (xyz̄ + x̄y(y + z + w) + xz)wy.
En primer lugar, si no establecemos condiciones sobre la naturaleza de
las fórmulas que representan a una misma función, existen demasiados ca-
sos, y la búsqueda de la “fórmula más simple” es un problema dif́ıcil que no
sabremos resolver en general. No obstante, śı que se disponen de procedi-
mientos para encontrar fórmulas más simples de entre las que son de cierto
tipo. Veamos a cuáles.
Para ello hemos de hacer previamente algunas definiciones:
Definición 1.14 Una función booleana es un cubo si es una función cons-
tante a 1 o es un producto de literales.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 43
Por ejemplo en F3, xyz̄, x, ȳz son cubos. En particular xyz̄ es un mintérmino.
Si m y M son cubos, diremos que m es absorbido por M si m ≤ M .
Por ejemplo xyz es absorbido por xy. En general m es absorbido por M si
los literales que intervienen en la formación del cubo m contienen los de la
formación M .
El número de cubos que existen con n variables es 3n ya que al formar
un cubo, cada variable x puede ser no elegida, elegida como tal x o elegida
complementada x̄. En el caso de dos variables, existen 32 cubos que son
1, x, x̄, y, ȳ, xy, xȳ, x̄y, x̄ȳ.
Una función booleana se dice que está expresada como fórmula poli-
nomial si es una suma de cubos. La fórmula polinomial se dice reducida si
ningun cubo de la fórmula absorbe a ningún otro. Por ejemplo xȳz+xȳ+ x̄z
es una fórmula polinomial pero no es reducida porque xȳz es absorbido por
xȳ. En cambio xȳz + x̄z si es una fórmula polinomial reducida. Vamos a
buscar entre todas las fórmulas polinomiales reducidas, aquella que es más
simple. Previamente definamos este concepto:
Definición 1.15 Sea f función booleana, y sean p1 ≡ m1 +m2 + · · ·+mr,
p2 ≡ M1 + M2 + · · · + Ms dos expresiones de f en fórmulas polinomiales
reducidas. Se dirá que p1 es más simple que p2 si r ≤ s y si cada mi absorbe
al menos un Mj.
Por ejemplo la función f , cuya f.n.d. es xyz+xȳz̄+xyz̄+ x̄yz̄ tiene otra
fórmula polinomial xyz + xz̄ + yz̄ que es más simple porque tiene menos de
cuatro cubos y cada uno de ellos absorbe a algunos de los otros de la f.n.d.
En otras palabras una fórmula polinomial reducida de f es más simple
que otra si tiene menos cubos y con menos literales.
No es dif́ıcil comprobar que la relación “ser más simple” establecida entre
las fórmulas polinomiales reducidas de una función es una relación de orden
12. Esta relación no tiene porqué ser nesesariamente total. En particular
para la función del ejemplo anterior tenemos un total de siete fórmulas
polinomiales reducidas (¿Cómo las hemos calculado?):
�
�
�
��
�
�
�
@
@
@
@@ @
@
@
p7
p6p4
p5
p2 p3
p1
p1 ≡ xyz + xȳz̄ + xyz̄ + x̄yz̄
p2 ≡ xyz + xz̄ + x̄yz̄
p3 ≡ xyz + xȳz̄ + yz̄
p4 ≡ x̄yz̄ + xy + xz̄
p5 ≡ xyz + xz̄ + yz̄
p6 ≡ xȳz̄ + xy + yz̄
p7 ≡ xy + xz̄ + yz̄ •
• •
•
•
•
•
12Ojo, la relación se establece entre las fórmulas polinomiales reducidas de una misma
función booleana.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 44
que aparecen ordenadas en el diagrama de hasse de la derecha. Podemos
entonces decir que una fórmula polinomial reducida es la más simple si es
una fórmula minimal por la relación anterior 13.
En el ejemplo anterior p7 es minimal y por tanto es la fórmula polinomial
reducida más simple de f . A continuación exponemos un procedimiento para
calcular fórmulas minimales.
Método de los diagramas de Karnaugh.
El método va a permitir con ayuda de un diagrama encontrar fórmulas
polinomiales minimales de funciones de F3 y F4. El procedimiento puede
generalizarse para funciones de F5 y F6 pero la complicación es tal que el
método carece de interés.
Enpezamos viendo lo que es un diagrama de Karnaug de una función
booleana. Observemos las figuras,
110 100 000 010
111 101 001 011
1100 1000 0000 0100
1101 1001 0001 0101
1110 1010 0010 0110
1111 1011 0011 0111
y y y y y y
w
w
w
x x
x x
z
z
z
z
en la primera cada elemento de {0, 1}3 está representado en una casilla, y en
la segunda están los de {0, 1}4, y están dispuestos con la siguiente intención:
dos elementos representados en casillas adyacentes difieren en exactamente
una cifra.
Podemos no obstante ver que los elementos 1101 y 0101 aunque difieren
en una cifra, no son adyacentes. En cambio, śı lo son si extendemos el con-
cepto de adyacencia y lo aplicamos a figura que resulta de yustaponer en los
lados otras figuras idénticas.
1101 0101
Casillas
adyacentes�
�	
��������9
�
�	
��������9
Cuando hablemos de adyacen-
cia pues, lo haremos en el sentido
extendido.
Con esta disposición de los ele-
mentos, podemos representar en la
figura una función booleana sin
13El elemento minimal no necesariamente es mı́nimo, es decir no tiene porqué ser único.
Departamento de Matemática Aplicada José Luis Leal Ruperto
Algebra de Boole y aplicaciones 45
más que marcar las casillas que co-
rresponden a los elementos que to-
man valor 1. La figura que resulta
se llama Diagrama de Karnaugh.
×
× × ×
xy xȳ x̄ȳ x̄y
z̄
z
f = xyz̄ + xȳz + x̄ȳz + x̄yz
Por ejemplo, la figura que aparece a la
derecha es el diagrama de Karnaugh de la
función de F3 f(x, y, z) = xȳz+ x̄yz+xyz̄+
x̄ȳz.
Podemos observar de forma inmediata
algunas propiedades de estos diagramas: