UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

Retículas y Álgebras booleanas

CONTENIDO

Unidad N°4: ESTRCUTURAS DE ORDEN Y ÁLGEBRA DE BOOLE

4.3 Retículas y Álgebras booleanas
▪ Propiedades
▪ Retícula acotada
▪ Retícula distributiva
▪ Retícula complementada

Profesores MA265 1
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

Retículas y Álgebras booleanas

Retículas
Una retícula es un conjunto parcialmente ordenado (L, ) tal que cada subconjunto {a, b} de
dos elementos tiene una mínima cota superior y una máxima cota inferior.

Notación
• 𝑀𝐶𝑆({𝑎, 𝑏}) = 𝑎 ∨ 𝑏 es llamada unión de a y b.
• 𝑀𝐶𝐼({𝑎, 𝑏}) = 𝑎 ∧ 𝑏 es llamada conjunción de a y b.

Ejemplo 1

Nota: para verificar que es retícula, solo debemos tomar los vértices no comparables.

Definición
Sea (L, ) una retícula. Un subconjunto no vacío S de L es una sub-retícula de L si:
abS y abS
siempre que a  S y b  S.

Ejemplo 2

𝑆1 = {𝑎, 𝑏, 𝑐, 𝑑} sí es una subretícula de L

𝑆2 = {𝑎, 𝑏, 𝑐, 𝑔} no es una subretícula de L

Profesores MA265 2
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

Propiedades
Sea L una retícula. Entonces para todo a y b en L:
• a  b = b si y solo si a  b
• a  b = a si y solo si a  b
• a  b = a si y solo si a  b = b
• 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)
• a  (a  b) = a; a  (a  b) = a (Absorción)

Retícula acotada
Una retícula L está acotada si tiene un elemento máximo I y un elemento mínimo 0.

Ejemplo 3

Teorema
Sea L = {a1, a2, ... , an} una retícula finita, entonces L es acotada.

Retícula distributiva
Una retícula L es distributiva si para cualesquiera elementos a, b y c en L, se tiene:
a  ( b  c) = (a  b)  (a  c)
a  ( b  c) = (a  b)  (a  c)

Profesores MA265 3
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

Ejemplo 4

No es una retícula distributiva, pues:

𝑐 ∨ (𝑒 ∧ 𝑑) ≠ (𝑐 ∨ 𝑒) ∧ (𝑐 ∨ 𝑑)

Retícula complementada
Complemento
Sea L una retícula acotada con elemento máximo I y elemento mínimo 0, y sea a  L. Un
elemento a’L es un complemento de a, si:
a  a’ = I y a  a’ = 0.

Definición
Una retícula L es complementada si está acotada y si todo elemento en L tiene complemento.

Teorema
Sea L una retícula distributiva acotada. Si un elemento tiene complemento, este es único.
Observación: Si L es una retícula acotada y tiene un elemento con más de un complemento,
entonces L no es distributiva.

Ejemplo 5
La siguiente retícula es complementada debido a que cada elemento tiene complemento.

Elemento Complemento
a f
b c, e
c b, d
d c, e
e b, d
f a

Además del teorema anterior, esta retícula no es distributiva, pues tiene elementos con más
de un complemento (de la tabla los elementos b, c, d y e tienen dos complementos)

Profesores MA265 4
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

Ejemplo 6
En el conjunto D90 , formado por los divisores de 90, definimos: 𝑎|𝑏 ↔ 𝑎 es divisor de b.
a) Justifique, por qué la relación 𝑅 es una retícula.
b) Halle la MCI y la MCS de {6, 15}.
c) Halle la MCI y la MCS de {9, 10}.
d) Si 𝑎 y 𝑏 son dos divisores de 90, ¿qué representa la MCI de {𝑎, 𝑏}?
e) Si 𝑎 y 𝑏 son dos divisores de 90, ¿qué representa la MCS de {𝑎, 𝑏}?
f) Determine el complemento de los siguientes elementos: 5, 6, 9, 15 y 90.
Solución
𝐷90 = {1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90}
a) Cada subconjunto de dos elementos de D90 tiene MCS y MCI (Realice el diagrama de
Hasse).
b) MCI = 3, MCS = 30.
c) MCI = 1, MCS = 90.
d) Representa el MCD(𝑎, 𝑏).
e) Representa el MCM(𝑎, 𝑏).
f) MCD(5, 𝑥) = 1 y MCM(5, 𝑥) = 90 → 𝑥 = 18.
MCD(6, 𝑥) = 1 y MCM(6, 𝑥) = 90 → 6 no tiene complemento.
MCD(9, 𝑥) = 1 y MCM(9, 𝑥) = 90 → 𝑥 = 10.
MCD(15, 𝑥) = 1 y MCM(15, 𝑥) = 90 → 15 no tiene complemento.
MCD(90, 𝑥) = 1 y MCM(90, 𝑥) = 90 → 𝑥 = 1.

EJERCICIOS PROPUESTOS
1. Identifique cuales de los siguientes diagramas de Hasse representan retículas (Látices).

f g e
f
e

d e c d
d
b

b c b c
a a
a

Profesores MA265 5
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

2. Sobre los órdenes parciales (𝐷105 ; |) 𝑦 (𝐷30 ; |):

(a) ¿Son retículas?
(b) Determine 3 ∨ 5; 𝑀𝐶𝑆(30, 𝑀𝐶𝑆(5, 15)) de ( 𝐷30 ; |)
(c) Determine 7 ∧ 15; 𝑀𝐶𝐼(5, 𝑀𝐶𝐼(3, 21)) de ( 𝐷105 ; |)
(d) Determine los elementos máximos y mínimos para cada retícula.

3. Sea el conjunto parcialmente ordenado (𝐷105 , |), es decir el conjunto de todos los
divisores positivos de 105 bajo la relación de divisibilidad. Trace el Diagrama de Hasse
correspondiente. Luego responda las siguientes preguntas justificando apropiadamente
sus respuestas:
(a) Verifique que el Diagrama de Hasse obtenido representa una Retícula.
(b) ¿La Retícula es Acotada?
(c) ¿La Retícula es Complementada?

4. Dada la siguiente retícula L.

(a) Determine si L es acotada.
(b) Determine si L es complementada.
(c) Halle 𝑑 ∧ ( 𝑓 ∨ 𝑒 ) y ( 𝑑 ∧ 𝑓 ) ∨ ( 𝑑 ∧ 𝑒 ).
(d) Determine si L es distributiva.

5. Dada la retícula 𝐿 = (𝐴, ≤), donde

𝐴 = {𝑎,  𝑏,  𝑐,  𝑑,  𝑒,  𝑓,  𝑔,  ℎ} y cuyo diagrama de Hasse se
muestra:
(a) Determine los complementos de todos los vértices de 𝐿.
(b) Determine 𝑏 ∨ (ℎ ∧ 𝑔) 𝑦 (𝑏 ∨ ℎ) ∧ (𝑏 ∨ 𝑔).
(c) ¿Es L distributiva? Justifique su respuesta.
(d) ¿Es 𝐿 acotada?

6. Dada la retícula 𝐿 = (𝐴, ≤), donde:

𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗, 𝑘} y cuyo diagrama de Hasse se
muestra:
(a) Determine el complemento de cada vértice de L .
(b) Determine 𝑏 ∨ (𝑖 ∧ 𝑐) y (𝑏 ∨ 𝑖) ∧ (𝑏 ∨ 𝑐).
(c) ¿Es L distributiva? Justifique su respuesta.
(d) ¿Es L acotada? Justifique su respuesta.

Profesores MA265 6
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

7. Dada la retícula L cuyo diagrama de Hasse se muestra a la derecha:

a) Determine el complemento de cada vértice de L.
b) Determine 𝑐 ∨ (𝑖 ∧ 𝑓) y (𝑐 ∨ 𝑖) ∧ (𝑐 ∨ 𝑓).
c) ¿Es L distributiva?

Respuesta a los ejercicios:

1.
a) Sí es una retícula, todo par de vértices siempre tiene una MCS y un MCI
b) No es una retícula, debido a que no existe 𝑀𝐶𝑆({𝑏, 𝑐})
c) No es una retícula, debido a que no existe 𝑀𝐶𝐼({𝑐, 𝑑})

2.
a) 𝐷105 ; |) 𝑦 (𝐷30 ; |) son retículas ya que cada par elementos tiene MCS y MCI.
b)
3 ∨ 5 = 15 𝑀𝐶𝑆(30, 𝑀𝐶𝑆(5, 15)) = 30
c)
7 ∧ 15 = 1 𝑀𝐶𝐼(5, 𝑀𝐶𝐼(3,21)) = 1

3.
a) Como se muestra en el diagrama vemos que sí es una retícula, ya que, si tomamos
cualquier par de vértices, estos tienen MCI y MCS. (ver gráfica)
b) La retícula si es acotada, pues tiene un máximo y un mínimo
c) Sí es complementada, ya que cada elemento tiene por lo menos un complemento.

Profesores MA265 7
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

4. 𝑥 𝑥′
a) L es acotada ya que tiene un máximo y un mínimo 𝑎 ℎ
b) L es complementada ya que cada elemento tiene al menos un 𝑏 𝑐, 𝑑, 𝑔
complemento (ver tabla) 𝑐 𝑒, 𝑓
c) 𝑑 ∧ ( 𝑓 ∨ 𝑒 ) = 𝑑 𝑑 𝑏, 𝑒, 𝑓
(𝑑∧ 𝑓)∨ (𝑑∧ 𝑒)=𝑎 𝑒 𝑐, 𝑑, 𝑔
d) L no es distributiva ya que: 𝑑 ∧ ( 𝑓 ∨ 𝑒 ) ≠ ( 𝑑 ∧ 𝑓 ) ∨ ( 𝑑 ∧ 𝑒 ) 𝑓 𝑐, 𝑑, 𝑔
𝑔 𝑒, 𝑓, 𝑏
ℎ 𝑎

5. 𝑥 𝑥′
a) Los complementos para cada elemento se muestran en la tabla 𝑎 𝑒
b) 𝑏 ∨ (ℎ ∧ 𝑔) = 𝑎 𝑏 𝑒, 𝑓
(𝑏 ∨ ℎ) ∧ (𝑏 ∨ 𝑔) = 𝑑 𝑐 𝑑
c) 𝐿 no es distributiva debido a que: 𝑑 𝑐
𝑏 ∨ (ℎ ∧ 𝑔) ≠ (𝑏 ∨ ℎ) ∧ (𝑏 ∨ 𝑔) 𝑒 𝑏, ℎ, 𝑎
d) 𝐿 es acotada, ya que tiene un máximo y un mínimo. 𝑓 ℎ, 𝑏
𝑔 𝑛𝑜 𝑒𝑥𝑖𝑠𝑡𝑒𝑛
ℎ 𝑒, 𝑓

6. 𝑥 𝑥′
a) Los complementos para cada elemento se muestran en la tabla 𝑎 𝑖, 𝑐, 𝑔, 𝑓
b) 𝑏 ∨ (𝑖 ∧ 𝑐) = 𝑗 𝑏 No tiene
(𝑏 ∨ 𝑖) ∧ (𝑏 ∨ 𝑐) = 𝑗 𝑐 ℎ, 𝑎, 𝑑, 𝑒
c) 𝐿 no es distributiva debido a que algunos elementos tienen más de 𝑑 𝑖, 𝑐
un complemento. 𝑒 𝑖, 𝑐
d) 𝐿 es acotada, ya que tiene un máximo y un mínimo. 𝑓 ℎ, 𝑎
𝑔 ℎ, 𝑎
ℎ 𝑖, 𝑐, 𝑔, 𝑓
𝑖 ℎ, 𝑎, 𝑑, 𝑒
𝑗 𝑘
𝑘 𝑗

Profesores MA265 8
UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265)

7. 𝑥 𝑥′
a) Los complementos para cada elemento se muestran en la tabla 𝑎 𝑒
b) 𝑐 ∨ (𝑖 ∧ 𝑓) = 𝑎 𝑏 𝑓
(𝑐 ∨ 𝑖) ∧ (𝑐 ∨ 𝑓) = 𝑎 𝑐 𝑓
c) 𝐿 no es distributiva debido a que f tiene más de un complemento. 𝑑 𝑔
𝑒 𝑎
𝑓 𝑐, 𝑏
𝑔 𝑑
ℎ 𝑖
𝑖 ℎ

BIBLIOGRAFÍA
EPP, S. (2012). Matemática discreta con aplicaciones. México DF, México: Cengage Learning.

Profesores MA265 9