Retículos y álgebras de Boole

Vista previa del material en texto

Ret́ıculos y Álgebras de Boole
Conjuntos ordenados.
Recordemos que un conjunto ordenado es un
par (E,≤) donde E es un conjunto y ≤ es una
relación de orden en E.
Ejemplos:
• (R,≤), siendo ≤ la relación “ser menor o igual”
habitual.
• (Z+, |) siendo | la relación “ser divisor de” definida
sobre los enteros positivos.
•(P(U),⊆) siendo ⊆ la relación ”estar incluido” defi-
nida sobre los subconjuntos de U.
Decimos que (E,≤) es totalmente ordenado
si si cumple la propiedad conexa, es decir,
dado un par de elementos cualesquiera algu-
no de ellos se relaciona con el otro:
para cada x, y ∈ E, x ≤ y o y ≤ x
A los conjuntos ordenados que no son total-
mente ordenados se les dice parcialmente or-
denados, aśı (R,≤) es totalmente ordenado
mientras (Z+, |) y (P(U),⊆) lo son parcial-
mente.
Prof. Francisco Rodŕıguez 1
Diagramas de Hasse
Si E es finito, en su representación se puede
evitar el tener que asignar una orientación a
cada arco del grafo, poniendo los elementos
que son “posteriores” a otros, en escalones
superiores unidos por una sucesión ascenden-
te de arcos.
Ejemplo: Dado (A, |), donde
A = {1,2,3,5,6,8,10,15,16,20,30}
representado en la figura
1
3 52
8 6 10 15
16 20 30
Observamos que el elemento 2 está relacio-
nado con el 30 ya que existe al menos un
camino ascendente. En cambio el 2 y el 15
no lo están por no existir ese camino ascen-
dente.
Prof. Francisco Rodŕıguez 2
Definición 1 Sean M,m elementos de (E,≤):
a) M es máximo si ∀x ∈ E, x ≤M .
b) m es ḿınimo si ∀x ∈ E, x ≥ m.
Si M ′,m′ pertenecen a E diremos
c) M ′ es maximal si x ∈ E y M ′ ≤ x ⇒
M ′ = x.
d) m′ es minimal si x ∈ E y m′ ≥ x⇒ m′ = x.
Definición 2 Sea (E,≤) con ḿınimo m. Un
elemento a ∈ E es un átomo si es “inmedia-
tamente posterior” al ḿınimo. Es decir:
a es átomo
def⇐⇒

m 6= a
y
m ≤ x ≤ a⇒ m = x o a = x
Los elementos que son “inmediatamente an-
teriores” al máximo se llaman super átomos.
Prof. Francisco Rodŕıguez 3
Subconjuntos acotados: Dado (E,≤) y B ⊆ E
diremos que K ∈ E es cota superior (c.s) de
B si K está por “encima” de todos los ele-
mentos de B, es decir
K es c.s. de B
def⇐⇒ x ∈ B ⇒ x ≤ K
Análogamente se define una cota inferior.
k es c.i. de B
def⇐⇒ x ∈ B ⇒ x ≥ k
Si B tiene cota superior, se dice que está
acotado superiormente y si tiene cota infe-
rior, acotado inferiormente. B está acotado
si lo está superior e inferiormente.
Ejemplos:
• En la figura anterior, si consideramos B =
{2,10}, resulta que 1 y 2 cotas inferiores de
B, y que 10, 20 y 30 cotas superiores de B.
Por tanto, este conjunto B es acotado.
• En (Z+, |) el conjunto B = {números pares}
no es acotado (¿Por qué?). B si está acotado
inferiormente.
Prof. Francisco Rodŕıguez 4
Definición 3 Dado (E,≤) y B ⊆ E acotado
superiormente, llamamos extremo superior o
supremo de B (supB) a la menor de las cotas
superiores.
Es decir supB es extremo superior si y sólo
si ∀K cota superior de B, supB ≤ K.
Análogamente se define el extremo inferior o
ı́nfimo, inf B.
Si el supremo o el ı́nfimo de B pertenecen al
propio subconjunto B, coincidirán, respecti-
vamente, con el máximo o ḿınimo de dicho
conjunto
Ejemplos: Volviendo al ejemplo de la figura:
• si B = {2,10}, supB = 10 e inf B = 2.
• si B = {10,15}, supB = 30 e inf B = 5.
• si B = {6,10,15}, supB = 30 e inf B = 1.
• si B = {8,6}, no tiene supremo∗, si bien
inf B = 2.
∗No está acotado superiormente
Prof. Francisco Rodŕıguez 5
Ret́ıculos
Definición 4 El conjunto ordenado (E,≤) se
llama ret́ıculo si para cualquier par de elemen-
tos x, y de E, existen en E el sup{x, y} y el
inf{x, y}.
Ejemplo: Sea X un conjunto, entonces
(P (X),⊆) es un ret́ıculo. Dados dos elemen-
tos A,B de P (X) se tiene:
sup {A,B} = A ∪B
inf {A,B} = A ∩B
Un diagrama de Hasse de este ret́ıculo para
X = {a, b, c}
{a}
∅
{a, b, c}
{b}
{a, b}
{c}
{b, c}
{a, c}
Prof. Francisco Rodŕıguez 6
Ejemplo: Sea (Z+, |). Dados a, b ∈ Z+ siempre exis-
ten en Z+ el ḿınimo común múltiplo mcm(a, b) y el
máximo común divisor mcd(a, b) de a, b. Se prueba
que sup{a, b} = mcm(a, b) y inf{a, b} = mcd(a, b).
El conjunto ordenado (Z+, |) es entonces un ret́ıculo
con ı́nfimo el 1, pero no tiene supremo.
Ejemplo: El conjunto ordenado (D20, |), de los divi-
sores de 20, es un ret́ıculo. Como 20 = 2251, entonces
20 tiene (2 + 1)(1 + 1) = 6 divisores. Los átomos son
el 2 y el 5.
1
2 5
4
20
10
Ejemplos: Los siguientes diagramas de Hasse no
representan ret́ıculos. ¿Por qué?
d
e
f g
b
a
c
a
b
f
de
c
Prof. Francisco Rodŕıguez 7
Definición 5 En un ret́ıculo E se definen las
operaciones internas ∨, ∧ siguientes:
a ∨ b = sup{a, b}
a ∧ b = inf{a, b}
satisfacen las propiedades:
a)
{
a ∨ a = a
a ∧ a = a Idempotencia.
b)
{
a ∨ b = b ∨ a
a ∧ b = b ∧ a Conmutativa.
c)
{
a ∨ (b ∨ c) = (a ∨ b) ∨ c
a ∧ (b ∧ c) = (a ∧ b) ∧ c Asociativa.
d)
{
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a Absorción.
Teorema 1 Todo conjunto con dos opera-
ciones (E,∨,∧) que satisface las propiedades
anteriores es un ret́ıculo.
La siguiente tabla resume el concepto anterior.
En (E,≤) ret́ıculo te-
nemos las operaciones
∨,∧ obtenidas de,
x ∨ y
def
= sup{x, y}
x ∧ y
def
= inf{x, y}
En (E,∨,∧) tenemos
a ≤ b def⇔ a ∨ b = b
(o equivalentemente
a ≤ b def⇔ a ∧ b = a)
que hace (E,≤)
ret́ıculo.
Prof. Francisco Rodŕıguez 8
Ret́ıculos distributivos y booleanos
Definición 6 Un ret́ıculo es distributivo, si
satisface las propiedades
{
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) Distributivas
Ejemplos: Los siguientes ret́ıculos no son
distributivos,
a b
i
s
c
i
s
c
b
a
Para definir el concepto de ret́ıculo boolea-
no necesitamos hacer unas precisiones sobre
ret́ıculos acotados, es decir aquellos que tie-
nen máximo y ḿınimo.
Prof. Francisco Rodŕıguez 9
No todos los ret́ıculos son acotados, por ejem-
plo Z× Z con la relación de orden
(a, b) � (c, d) ⇐⇒ a ≤ c y b ≤ d,
Las operaciones ∨ y ∧ quedan definidas
(a, b) ∨ (c, d) = (max{a, c},max{b, d})
(a, b) ∧ (c, d) = (min{a, c},min{b, d})
(0,0)
(1,0)
(1,−1)
(0,−1)(−1,0)
(−1,2)
(−1,−1)
(0,1)
(1,1)
(−1,1)
(0,2)
(1,2)
¿Un ret́ıculo necesita ser infinito para ser no
acotado?
Definición 7 Sea E un ret́ıculo acotado, con
máximo M y ḿınimo m. Un elemento a ∈ E
posee complemento si existe en E un elemen-
to a′ tal que a′ ∨ a = M y a′ ∧ a = m.
Prof. Francisco Rodŕıguez 10
Teorema 2 Sea E un ret́ıculo acotado, en-
tonces:
a) a ∨M = M a ∧m = m Dominancia
b) m ∨ a = a M ∧ a = a Identidad
c) Si E es distributivo y a ∈ E posee comple-
mento a′, este es único.
A un ret́ıculo en que todos sus elementos tie-
nen complementos se le dice ret́ıculo comple-
mentado.
Ejemplos:
• El ret́ıculo D30 es complementado, en cambio el
ret́ıculo D20 no lo es (2 y 10 no tienen complemento).
• Los ret́ıculos no distributivos anteriores son comple-
mentados. Obsérvese que en ret́ıculos no distributivos
puede haber más de un complemento a un elemento.
Definición 8 Un ret́ıculo distributivo y com-
plementado recibe el nombre de ret́ıculo de
Boole
Prof. Francisco Rodŕıguez 11
Álgebras booleanas
Definición 9 Llamaremos álgebra de Boole
a un conjunto B con dos operaciones binarias
+ y ·, una operación unaria ∗ y dos elementos
distintos 0 y 1 que verifican:
a) Leyes conmutativas{
a+ b = b+ a
a · b = b · a
b) Leyes asociativas{
(a+ b) + c = a+ (b+ c)
(a · b) · c = a · (b · c)
c) Leyes distributivas{
a+ (b · c) = (a+ b) · (a+ c)
a · (b+ c) = (a · b) + (a · c)
d) Leyes de identidad{
a+ 0 = a
a · 1 = a
e) Leyes del complemento{
a+ a = 1
a · a = 0
Por el teorema 1, es fácil deducir que todo álgebra de
Boole es equivalente a un ret́ıculo de Boole, sin más
que identificar las operaciones + ≡ ∨, · ≡ ∧, a ≡ a′ y
donde 1 es el máximo y 0 es el ḿınimo. Por tanto,
impĺıcitamente, todo álgebra de Boole lleva asociada
una relación de orden que representaremos ≤.
Ejercicio: Prueba las propiedades de Idempotencia y
de Absorción.
Prof. Francisco Rodŕıguez12
Ejemplos:
• El ret́ıculo D20, a pesar de satisfacer la propiedad
distributiva, no es álgebra de Boole.
• El conjunto B = {0,1} con las operaciones bina-
rias (suma y producto) booleanas y el complemento,
definidas en el caṕıtulo de relaciones.
• Las matricias (Mm×n−{0,1},∨,∧, ∗) son álgebras de
Boole.
Especial interés tienen las álgebras de Boole:
Ejemplos:
• Para cada n ∈ Z+, el conjunto Bn = {0,1}n con las
operaciones +, · y complemento heredadas de B es
un álgebra de Boole.
• (P(A),∪,∩, ∗) es un álgebra de Boole, cualquiera que
sea el conjunto A.
Existen dos importantes propiedades que verifican las
álgebras booleanas pero que no verifican los ret́ıculos.
Teorema 3 En todo álgebra de Boole se verifica:
a) Leyes de Morgan{
a+ b = a · b
a · b = a+ b
b) Leyes del doble complemento
a = a
Prof. Francisco Rodŕıguez 13
Principio de Dualidad.
Se habrá observado que casi todas las leyes de los
ret́ıculos y álgebras de Boole vienen siempre en pareja.
Esto no sucede por azar.
Su justificación es la siguiente: Si (E,≤) es un con-
junto ordenado, (E,≤−1) es también un conjunto or-
denado, y que si (E,≤) es un ret́ıculo , también lo es
(E,≤−1).
Podemos observar que estos dos ret́ıculos ordenados y
las operaciones definidas en ambos se parecen mucho.
En concreto la operación ∨ de (E,≤) es la operación ∧
de (E,≤−1) y la operación ∧ de (E,≤) es la operación
∨ de (E,≤−1).
Por lo tanto de cualquier enunciado válido que trate
sobre propiedades de los ret́ıculos se puede obtener
otro reemplazando ≤ por ≥ ( =≤−1), ∨ por ∧, y ∧ por
∨.
Definición 10 La expresión dual P d de cualquier enun-
ciado matemático P sobre elementos de un ret́ıculo
se obtiene reemplazando las operaciones ∨ por ∧ y
viceversa y las desigualdades ≤ por ≥ y viceversa.
Si además intervienen expresiones como supremo y/o
ı́nfimo, cotas superiores y/o inferiores, éstas se inter-
cambian entre śı.
Para un álgebra booleana podemos dar la siguiente
Definición 11 La expresión dual P d de cualquier enun-
ciado matemático P sobre elementos de un álgebra de
boole en la que vengan involucradas las operaciones
booleanas +, ·, y las desigualdades ≤,≥, se obtiene
reemplazando 0 por 1, 1 por 0, + por ·, · por +, ≤
por ≥ y ≥ por ≤.
Prof. Francisco Rodŕıguez 14
Ejemplo: Si P representa la expresión 0 ≤ a + b,
entonces P d es 1 ≥ 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 so-
bre ret́ıculos o álgebras de Boole. Existe para ella una
sucesión de enunciados que constituye una demostra-
ció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. Esta demostra-
ción dual sirve para demostrar 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.
Ejemplos: T d1 , T
d
2 son los teoremas duales de T1, T2:
Teorema T1 Teorema T d1
En un ret́ıculo acota-
do el extremo superior
s es único
En un ret́ıculo acota-
do el extremo inferior
i es único
Teorema T2 Teorema T d2
Las condiciones si-
guientes son equiva-
lentes:
(a) a ≤ b
(b) a+ b = b
Las condiciones si-
guientes son equiva-
lentes:
(a) a ≥ b
(b) ab = b
Prof. Francisco Rodŕıguez 15
Formas normales
Teorema 4 Sea B un álgebra de Boole:
a) Si a es átomo, entonces, ∀b ∈ B, 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, y a ∈ B, cumple que para todo i,
aia = 0, entonces a = 0
Probaremos que todo elemento de un álgebra
de Boole se puede expresar en función de sus
átomos
Teorema 5 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.
Prof. Francisco Rodŕıguez 16
Ejemplo: En el álgebra de Boole B = D210
el conjunto de los átomos es {2,3,5,7}. Ob-
servamos 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. (No debe haber
confusión en el uso de la notación. La ope-
ración suma se refiere a la operación ḿınimo
común múltiplo, es decir mcm(2,5,7) = 70).
Una observación similar para los demas ele-
mentos nos proporciona que: 6 = 2 + 3,
14 = 2 + 7, 21 = 3 + 7, 30 = 2 + 3 + 5,
42 = 2 + 3 + 7, 210 = 2 + 3 + 5 + 7, etc.
210
1
42 70 10530
14 15 21 35106
2 3 5 7
Prof. Francisco Rodŕıguez 17
Definición 12 Si x = a1 +a2 + · · ·+ak, es la
expresión del terema anterior, se dice que x
está expresado en forma normal disyuntiva.
Por el principio de dualidad, tenemos el si-
guiente
Teorema 6 Sea x 6= 1 elemento de un álgebra
de Boole B finita. Si b1, b2, · · · , bk son los su-
perá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.
Definición 13 Si x = b1b2 · · · bk, es la expre-
sión del teorema anterior, entonces se dice
que x está expresado en forma normal con-
juntiva.
En D210, algunos de sus los elementos expre-
sados en forma conjuntiva quedaŕıan como:
2 = 30 ·42 ·70, 5 = 30 ·70 ·105, 14 = 42 ·70,
etc. (Obsérvese que debe entenderse el pro-
ducto · como un máximo común divisor).
Prof. Francisco Rodŕıguez 18
Teorema de Stone
Un isomorfismo entre álgebras de Boole es
una función biyectiva f :B1 → B2 que cumple
f(a+ b) = f(a) + f(b)
f(a · b) = f(a) · f(b)
f(a) = f(a)
Teorema 7 Sea At el conjunto de los átomos
de un álgebra de Boole finita B. Entonces, B
es isomorfa al álgebra de Boole (P(At),∪,∩.∗)
del conjunto de las partes de sus átomos.
Una consecuencia inmediata de este teorema
es que todas las álgebras booleanas finitas
tienen 2n elementos. También es fácil dedu-
cir que todas las álgebras booleanas de 2n
elementos son necesariamente isomorfas.
Por estas razones se tiende a considerar únicamente
como álgebras booleanas finitas, o bien el
conjunto de partes de un cierto conjunto, o
bien las álgebras Bn donde B = {0,1}.
Prof. Francisco Rodŕıguez 19
Expresiones booleanas
Definición 14 Sea B algebra de Boole. Una
expresión booleana sobre B está definida re-
cursivamente como,
1. Cualquier elemento de B es una expresión
booleana.
2. Cualquier śımbolo de variable es una ex-
presión booleana.
3. Si E, F son expresiones booleanas, tam-
bién lo son E + F , EF , E.
Ejemplo: En el álgebra booleana D6 si con-
sideramos (1 · 3+2)·6 tenemos una expresión
booleana sobre esa álgebra de boole.
La expresión (1 · x1+2)·x2 también es boole-
ana sobre D6. Obsérvese que el primer caso
tengo un elemento de D6 que no es otra cosa
que sustituir las variables x1 y x2 por elemen-
tos concretos.
Prof. Francisco Rodŕıguez 20
Llamaremos evaluación de una expresión boo-
leana a sustituir las variables por elementos
concretos del álgebra de Boole.
En principio con n variables se pueden formar
muchas expresiones booleanas distintas, si
bien no todas “son tan distintas”, por ejem-
plo las expresiones sobre B = {0,1}
E(x1, x2, x3) = (x1 + x2) + x3
y
F (x1, x2, x3) = (x1 · x2) · x3
dan el mismo resultado ante las mismas eva-
luaciones (consecuencia de las leyes de Mor-
gan), por tanto podemos considerarla la mis-
ma expresión.
Definición 15 Dos expresiones booleanas E
y F sobre el mismo álgebra de Boole son
equivalentes si cada evaluación da el mismo
elemento del álgebra en cada una de las ex-
presiones.
En este caso diremos que E = F .
Prof. Francisco Rodŕıguez 21
Ejemplos:
• Probar que las expresiones sobre B
E(x1, x2, x3) = (x1 · x2 · x3) + (x1 · x2 · x3)
y
F (x1, x2, x3) = x1 · x3
son equivalentes.
• Hacer lo mismo para E(x, y) = (x+ y) · 3 y
F (x, y) = x · y + 2 en D6.
Funciones entre álgebras de Boole
Teorema 8 El conjunto de funciones F =
{f | f :B1 → B2} es, con las operaciones(f + g)(x) = f(x) + g(x)
(f · g)(x) = f(x) · g(x)
f(x) = f(x)
un álgebra de Boole
Prof. Francisco Rodŕıguez 22
Ejemplo: Consideremos las funciones en-
tre B = {0,1} y P({a, b}). Hay en total
42 = (22)2
1
= 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)
0 ∅
1 {a}
x f2(x)
0 ∅
1 {b}
x f3(x)
0 {a}
1 ∅
x f4(x)
0 {b}
1 ∅
Las demás, como sabemos, podemos expre-
sarlas sumas con éstas cuatro:
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
que junto con las funciones 0 y 1 hacen las
16.
Prof. Francisco Rodŕıguez 23
Definición 16 Consideremos el álgebra boo-
leana B = {0,1}. Llamaremos función boo-
leana a una función f :Bn → Bm.
Una función booleana se puede expresar de la forma
f(x1, x2, . . . , xn)
= (f1(x1, . . . , xn), f2(x1, . . . , xn), . . . , fm(x1, . . . , xn))
donde cada fi:Bn → B.
Teorema 9 Cada f :Bn → B admite una ex-
presión booleana de n variables.
En el álgebra de Boole F = {f | f :Bn →
B} los átomos son de la forma x1′x′2 . . . xn
′
donde cada xi
′ = xi ó xi′ = xi. Estos átomos
reciben también el nombre de mintérminos.
Análogamente los superátomos (¿qué expre-
sión toman?) reciben el nombre de maxtér-
minos.
Una parte del estudio de las álgebras boole-
anas está encaminido a dar expresiones boo-
leanas minimales de las funciones booleanas.
Ejercicio: Da una tabla con todas las funciones (en
forma de expresión booleana) de B2 → B, realiza un
diagrama de Hasse del ret́ıculo y encuentra las formas
normales de la función f(x, y) = x+ y · x+ y.
Prof. Francisco Rodŕıguez 24