Download Ejercicios 9.nb

Ejercicios 9.nb
1
9. Retículos y álgebras de
Boole
Ejercicios resueltos
ü Ejercicio 1.
Consideramos los siguientes conjuntos ordenados:
a) A1 = {1, 2, 3, 4, 5, 6, 7, 8} con la relación orden:
R1 = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 2), (2, 5), (2,
6), (2, 8), (3, 3), (3, 5), (3, 7), (3, 8), (4, 4), (4, 6), (4, 7), (4, 8), (5, 5), (5, 8),
(6, 6), (6, 8), (7, 7), (7, 8), (8, 8)}.
b) A2 = {a, b, c, d} con la relación de orden: R2={{a, a}, {a, b}, {a, c}, {a,
d}, {b, b}, {b, d}, {c, c}, {c, d}, {d, d}}.
c) A3 = {1, 2, 3, 4, 5} con la relación de orden: x R3 y si y sólo si x§y.
d) A4 = {a, b, c, d} con la relación de orden: R4={{a, a}, {a, b}, {a, c}, {a,
d}, {b, b}, {c, c}, {c, d}, {d, d}}.
Determinar:
I. Cuáles de ellos son retículos.
II. Determinar si aquellos que son retículos son distributivos, tienen elemento 0 o 1 o son complementados.
III. Razonar cuáles de ellos son álgebras de Boole a partir de los resultados
obtenidos en II.
IV. Representar el diagrama de orden y a la vista del mismo volver a razonar usando el teorema de estructura de las álgebras de Boole finitas cuáles
de ellos son álgebras de Boole.
Solución:
a) Introducimos los conjuntos ordenados y comprobamos si son retículos
con la función RETICULO[].
Ejercicios 9.nb
A1 = 81, 2, 3, 4, 5, 6, 7, 8<;
R1 = 881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 81, 6<, 81, 7<, 81, 8<, 82, 2<,
82, 5<, 82, 6<, 82, 8<, 83, 3<, 83, 5<, 83, 7<, 83, 8<, 84, 4<, 84, 6<,
84, 7<, 84, 8<, 85, 5<, 85, 8<, 86, 6<, 86, 8<, 87, 7<, 87, 8<, 88, 8<<;
RETICULO@A1, R1D
True
A2 = 8a, b, c, d<;
R2 = 88a, a<, 8a, b<, 8a, c<, 8a, d<, 8b, b<, 8b, d<, 8c, c<, 8c, d<, 8d, d<<;
RETICULO@A2, R2D
True
A3 = 81, 2, 3, 4, 5<;
R3 = 881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 82, 2<, 82, 3<,
82, 4<, 82, 5<, 83, 3<, 83, 4<, 83, 5<, 84, 4<, 84, 5<, 85, 5<<;
RETICULO@A3, R3D
True
A4 = 8a, b, c, d<;
R4 = 88a, a<, 8a, b<, 8a, c<, 8a, d<, 8b, b<, 8c, c<, 8c, d<, 8d, d<<;
RETICULO@A4, R4D
False
Por tanto, A1, A2 y A3 con sus respectivas relaciones de orden son retículos y A4 no lo es.
b) Determinamos de qué tipo son los retículos A1, A2 y A3.
DISTRIBUTIVOS:
RETICULODISTRIBUTIVO@A1, R1D
True
2
Ejercicios 9.nb
RETICULODISTRIBUTIVO@A2, R2D
True
RETICULODISTRIBUTIVO@A3, R3D
True
Con CERO y UNO:
MAXIMALES@A1, R1D
MINIMALES@A1, R1D
88<
81<
MAXIMALES@A2, R2D
MINIMALES@A2, R2D
8d<
8a<
MAXIMALES@A3, R3D
MINIMALES@A3, R3D
85<
81<
COMPLEMENTADO:
COMPLEMENTADO@A1, R1D
True
COMPLEMENTADO@A2, R2D
True
3
Ejercicios 9.nb
COMPLEMENTADO@A3, R3D
False
Es decir, los tres son retículos distributivos, con elemento 0 y 1 pero sólo
A1 y A2 son complementados.
c) A1 y A2 son álgebras de Boole porque son retículos con elemento 0 y 1,
distributivos y complementados.
A3 no es álgebra de Boole porque no es complementado.
d) Diagramas de orden:
A1:
A = 81, 2, 3, 4, 5, 6, 7, 8<;
R = 881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 81, 6<, 81, 7<, 81, 8<, 82, 2<,
82, 5<, 82, 6<, 82, 8<, 83, 3<, 83, 5<, 83, 7<, 83, 8<, 84, 4<, 84, 6<,
84, 7<, 84, 8<, 85, 5<, 85, 8<, 86, 6<, 86, 8<, 87, 7<, 87, 8<, 88, 8<<;
4
Ejercicios 9.nb
<< Graphics`Arrow`
Clear@CoordD;
tabla = Table@0, 8i1, Length@AD<, 8j1, 3<D; B = A; t1 = 1; nivel = 0;
While@B ≠ 8<, minimales = 8<; nivel ++; Do@minimal = True;
Do@If@Intersection@88B@@m1DD, B@@n1DD<<, RD ≠ 8< && n1 ≠ m1,
minimal = FalseD, 8m1, 1, Length@BD<D;
If@minimal, AppendTo@minimales, B@@n1DDD;
tabla@@t1DD = 8nivel, B@@n1DD, 0<;
t1 ++;D;,
8n1, 1, Length@BD<D;
B = Complement@B, minimalesD;
D
R1 = 8<;
Do@AppendTo@R1, 8A@@i1DD, A@@i1DD<D, 8i1, 1, Length@AD<D;
R = Complement@R, R1D; R1 = 8<; Do@
Do@Do@If@Intersection@R, 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<D 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<,
R1 = Union@R1, 8R@@k1DD<DDD, 8j1, 1, Length@AD<D, 8k1, 1, Length@RD<D;
R = Complement@R, R1D;
puntos = 8<; t1 = 0;
Do@cont = 0;
Do@If@tabla@@i1, 1DD j1, cont = cont + 1D, 8i1, 1, Length@AD<D;
Do@t1 ++; puntos = Union@puntos, 8Text@tabla@@t1, 2DD,
8k1 − Hcont ê 2L − .1, j1 + .1<D, Point@8k1 − Hcont ê 2L, j1<D<D;
tabla@@t1, 3DD = k1 − Hcont ê 2L, 8k1, 1, cont<D,
8j1, 1, tabla@@Length@AD, 1DD<D;
Coord@elem_D := Do@If@elem tabla@@h1, 2DD,
Coord@elemD = 8tabla@@h1, 3DD, tabla@@h1, 1DD<D, 8h1, 1, Length@AD<D;
Do@Coord@A@@i1DDD, 8i1, 1, Length@AD<D;
Do@AppendTo@puntos, Arrow@Coord@R@@t1, 1DDD, Coord@R@@t1, 2DDDDD;
, 8t1, 1, Length@RD<D;
Print@"Diagrama de orden:"D
Show@Graphics@puntosDD
Diagrama de orden:
5
Ejercicios 9.nb
6
8
5
6
7
2
3
4
1
Graphics Es un álgebra de Boole porque su diagrama de orden es un cubo, en consecuencia es un retículo isomorfo al álgebra de Boole de 8 elementos H2 L3 .
Veamos que ocurre con A2:
A = 8a, b, c, d<;
R = 88a, a<, 8a, b<, 8a, c<, 8a, d<, 8b, b<, 8b, d<, 8c, c<, 8c, d<, 8d, d<<;
Ejercicios 9.nb
<< Graphics`Arrow`
Clear@CoordD;
tabla = Table@0, 8i1, Length@AD<, 8j1, 3<D; B = A; t1 = 1; nivel = 0;
While@B ≠ 8<, minimales = 8<; nivel ++; Do@minimal = True;
Do@If@Intersection@88B@@m1DD, B@@n1DD<<, RD ≠ 8< && n1 ≠ m1,
minimal = FalseD, 8m1, 1, Length@BD<D;
If@minimal, AppendTo@minimales, B@@n1DDD;
tabla@@t1DD = 8nivel, B@@n1DD, 0<;
t1 ++;D;,
8n1, 1, Length@BD<D;
B = Complement@B, minimalesD;
D
R1 = 8<;
Do@AppendTo@R1, 8A@@i1DD, A@@i1DD<D, 8i1, 1, Length@AD<D;
R = Complement@R, R1D; R1 = 8<; Do@
Do@Do@If@Intersection@R, 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<D 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<,
R1 = Union@R1, 8R@@k1DD<DDD, 8j1, 1, Length@AD<D, 8k1, 1, Length@RD<D;
R = Complement@R, R1D;
puntos = 8<; t1 = 0;
Do@cont = 0;
Do@If@tabla@@i1, 1DD j1, cont = cont + 1D, 8i1, 1, Length@AD<D;
Do@t1 ++; puntos = Union@puntos, 8Text@tabla@@t1, 2DD,
8k1 − Hcont ê 2L − .1, j1 + .1<D, Point@8k1 − Hcont ê 2L, j1<D<D;
tabla@@t1, 3DD = k1 − Hcont ê 2L, 8k1, 1, cont<D,
8j1, 1, tabla@@Length@AD, 1DD<D;
Coord@elem_D := Do@If@elem tabla@@h1, 2DD,
Coord@elemD = 8tabla@@h1, 3DD, tabla@@h1, 1DD<D, 8h1, 1, Length@AD<D;
Do@Coord@A@@i1DDD, 8i1, 1, Length@AD<D;
Do@AppendTo@puntos, Arrow@Coord@R@@t1, 1DDD, Coord@R@@t1, 2DDDDD;
, 8t1, 1, Length@RD<D;
Print@"Diagrama de orden:"D
Show@Graphics@puntosDD
Diagrama de orden:
7
Ejercicios 9.nb
8
d
b
c
a
Graphics Es un álgebra de Boole porque su diagrama de orden es un cuadrado, en
consecuencia es un retículo isomorfo al álgebra de Boole de 4 elementos
H2 L2 .
A3:
A = 81, 2, 3, 4, 5<;
R = 881, 1<, 81, 2<, 81, 3<, 81, 4<, 81, 5<, 82, 2<, 82, 3<,
82, 4<, 82, 5<, 83, 3<, 83, 4<, 83, 5<, 84, 4<, 84, 5<, 85, 5<<;
Ejercicios 9.nb
<< Graphics`Arrow`
Clear@CoordD;
tabla = Table@0, 8i1, Length@AD<, 8j1, 3<D; B = A; t1 = 1; nivel = 0;
While@B ≠ 8<, minimales = 8<; nivel ++; Do@minimal = True;
Do@If@Intersection@88B@@m1DD, B@@n1DD<<, RD ≠ 8< && n1 ≠ m1,
minimal = FalseD, 8m1, 1, Length@BD<D;
If@minimal, AppendTo@minimales, B@@n1DDD;
tabla@@t1DD = 8nivel, B@@n1DD, 0<;
t1 ++;D;,
8n1, 1, Length@BD<D;
B = Complement@B, minimalesD;
D
R1 = 8<;
Do@AppendTo@R1, 8A@@i1DD, A@@i1DD<D, 8i1, 1, Length@AD<D;
R = Complement@R, R1D; R1 = 8<; Do@
Do@Do@If@Intersection@R, 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<D 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<,
R1 = Union@R1, 8R@@k1DD<DDD, 8j1, 1, Length@AD<D, 8k1, 1, Length@RD<D;
R = Complement@R, R1D;
puntos = 8<; t1 = 0;
Do@cont = 0;
Do@If@tabla@@i1, 1DD j1, cont = cont + 1D, 8i1, 1, Length@AD<D;
Do@t1 ++; puntos = Union@puntos, 8Text@tabla@@t1, 2DD,
8k1 − Hcont ê 2L − .1, j1 + .1<D, Point@8k1 − Hcont ê 2L, j1<D<D;
tabla@@t1, 3DD = k1 − Hcont ê 2L, 8k1, 1, cont<D,
8j1, 1, tabla@@Length@AD, 1DD<D;
Coord@elem_D := Do@If@elem tabla@@h1, 2DD,
Coord@elemD = 8tabla@@h1, 3DD, tabla@@h1, 1DD<D, 8h1, 1, Length@AD<D;
Do@Coord@A@@i1DDD, 8i1, 1, Length@AD<D;
Do@AppendTo@puntos, Arrow@Coord@R@@t1, 1DDD, Coord@R@@t1, 2DDDDD;
, 8t1, 1, Length@RD<D;
Print@"Diagrama de orden:"D
Show@Graphics@puntosDD
Diagrama de orden:
9
Ejercicios 9.nb
10
5
4
3
2
1
Graphics No es un álgebra de Boole porque el número de elementos de cualquier
álgebra de Boole finita es una potencia de 2.
A4:
A = 8a, b, c, d<;
R = 88a, a<, 8a, b<, 8a, c<, 8a, d<, 8b, b<, 8c, c<, 8c, d<, 8d, d<<;
Ejercicios 9.nb
11
<< Graphics`Arrow`
Clear@CoordD;
tabla = Table@0, 8i1, Length@AD<, 8j1, 3<D; B = A; t1 = 1; nivel = 0;
While@B ≠ 8<, minimales = 8<; nivel ++; Do@minimal = True;
Do@If@Intersection@88B@@m1DD, B@@n1DD<<, RD ≠ 8< && n1 ≠ m1,
minimal = FalseD, 8m1, 1, Length@BD<D;
If@minimal, AppendTo@minimales, B@@n1DDD;
tabla@@t1DD = 8nivel, B@@n1DD, 0<;
t1 ++;D;,
8n1, 1, Length@BD<D;
B = Complement@B, minimalesD;
D
R1 = 8<;
Do@AppendTo@R1, 8A@@i1DD, A@@i1DD<D, 8i1, 1, Length@AD<D;
R = Complement@R, R1D; R1 = 8<; Do@
Do@Do@If@Intersection@R, 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<D 88R@@k1, 1DD, A@@j1DD<, 8A@@j1DD, R@@k1, 2DD<<,
R1 = Union@R1, 8R@@k1DD<DDD, 8j1, 1, Length@AD<D, 8k1, 1, Length@RD<D;
R = Complement@R, R1D;
puntos = 8<; t1 = 0;
Do@cont = 0;
Do@If@tabla@@i1, 1DD j1, cont = cont + 1D, 8i1, 1, Length@AD<D;
Do@t1 ++; puntos = Union@puntos, 8Text@tabla@@t1, 2DD,
8k1 − Hcont ê 2L − .1, j1 + .1<D, Point@8k1 − Hcont ê 2L, j1<D<D;
tabla@@t1, 3DD = k1 − Hcont ê 2L, 8k1, 1, cont<D,
8j1, 1, tabla@@Length@AD, 1DD<D;
Coord@elem_D := Do@If@elem tabla@@h1, 2DD,
Coord@elemD = 8tabla@@h1, 3DD, tabla@@h1, 1DD<D, 8h1, 1, Length@AD<D;
Do@Coord@A@@i1DDD, 8i1, 1, Length@AD<D;
Do@AppendTo@puntos, Arrow@Coord@R@@t1, 1DDD, Coord@R@@t1, 2DDDDD;
, 8t1, 1, Length@RD<D;
Print@"Diagrama de orden:"D
Show@Graphics@puntosDD
Diagrama de orden:
Ejercicios 9.nb
12
d
b
c
a
Graphics Aunque tiene 4 elementos no es álgebra de Boole porque el diagrama de
orden de un álgebra de Boole de 4 elementos forzosamente es el cuadrado.
Ya habíamos comprobado que tampoco es retículo.