Download Álgebra de Boole. Retículos.

C APÍTULO 4.
Álgebra de
Boole. Retículos.
Este capítulo introduce dos estructuras
algebraicas muy importantes : la
estructura de álgebra de Boole y la de
retículo. Estas estructuras constituyen
una parte fundamental en la creación de
la tecnología actual. Además su
estructura matemática es de una belleza
y armonía digna de mención.
S ECCIÓN 1
Álgebra de Boole.
El álgebra de Boole constituye una estructura
algebraica perfecta que tiene aplicaciones inmediatas e
importantes a la ingeniería.
En este capítulo diagramamos un álgebra de Boole
clásica y tratamos también funciones booleanas,
particularmente formas normales disyuntivas y
conjuntivas.
C ONTENIDOS .
1. Álgebra de Boole de divisores Dn.
2. Funciones booleanas.
3. Circuitos lógicos y aplicaciones.
32
Problema 1.
obtenemos el siguiente diagrama de Hasse.
Determinar si el conjunto de los divisores de 165
forma una estructura de álgebra de Boole. En caso
afirmativo realizar el diagrama de Hasse de la misma e
indicar el complemento de cada elemento.
165
33
Solución.
Recordemos que una condición necesaria y
suficiente para que el conjunto Dn con las operaciones
de m.c.d. y m.c.m. forme un álgebra de Boole es que
n = p1 . p2 ......... . pk
3
15
11
55
5
con pi ≠ pj si i ≠ j.
Como 165 = 3 × 5 × 11 vemos que efectivamente el
conjunto D165 forma un álgebra de Boole con las
operaciones mencionadas.
Ahora bien, el conjunto D165 es
Dn = {1,3,5,11,15,33,55,165}.
1
Ahora bien, para indicar el complemento de cada
elemento es preciso hallar para cada x ∈ D165 un
elemento x′ ∈ D165 tal que
[x, x′] = 165
Recordando que en esta álgebra de Boole
a + b = a ∨ b = [a, b]
y que
y simultáneamente
(x, x′) = 1.
a . b = a ∧ b = (a, b)
33
De este diagrama de Hasse vemos claramente que
Problema 2.
Dada el circuito lógico siguiente
165
33
3
15
11
55
5
Solución.
1
1′ = 165
3′ = 55
5′ = 33
11′ = 15
y recordando que una de las propiedades del álgebra de
Boole es que x′′ = x tenemos “leyendo al revés” que
1 = 165′
3 = 55′
5 = 33′
se pide hallar una función booleana que lo represente y
luego llevar dicha función booleana a la forma
normal disyuntiva.
11 = 15′.
Comencemos por hallar una función booleana que
lo represente. De las compuertas básicas vemos,
leyendo el circuito “hacia atrás” que este será un
producto de dos factores es decir tendrá la forma
f (A, B, C ) = [
] . [ ].
Ahora bien el primer corchete es la suma de A y B
es decir que hasta ahora tenemos
f (A, B, C ) = [A + B] . [
]
34
mientras que vemos que el segundo es la suma de dos
sumandos así que resulta una expresión de la forma
f (A, B, C ) = [A + B] . [( ) + (
)].
Observando cada sumando resulta finalmente que
la función booleana que representa al circuito es
f (A, B, C ) = [A + B] . [(B . C ) + (B + C )].
Para llevarla a la f.n.d. tenemos dos formas de
proceder. Comencemos por la primera, la cual es
construyendo los minitérminos que deberán
aparecer en la misma.
Operando resulta
f (A, B, C ) = [A + B] . [(B + C )] = (A + B) . (B + C )
con lo cual, sacando “sumando” común tenemos
f (A, B, C ) = B + (A . C ).
Agregando tantos “unos” en cada sumando como
variables falten resulta
f (A, B, C ) = 1.B.1 + A.1.C
lo cual se puede cambiar por
Aplicando la propiedad distributiva tenemos
f (A, B, C ) = ABC + ĀBC + ABC̄ + ĀBC̄ + ABC + A B̄C
y finalmente eliminando los términos iguales
f (A, B, C ) = ABC + ĀBC + ABC̄ + ĀBC̄ + A B̄C.
La segunda forma consiste en hallar la imagen de
cada terna (a, b, c) y luego observando donde están los
“unos”, donde cambiamos a minúsculas para mayor
claridad.
Mediante este procedimiento es fácil armar los
minitérminos. Observando, por ejemplo el primer
“uno” vemos que debe aparecer el minitérmino
m1 = āb c̄.
De la misma manera se obtiene, observando el
segundo “uno” que no debe faltar el minitérmino
m2 = ābc.
Continuando de esta manera con los restantes tres
unos y sumando llegamos a que la forma normal
disyuntiva de la función f (a, b, c) es
f (a, b, c) = āb c̄ + ābc + a b̄c + ab c̄ + abc
f (A, B, C ) = (A + Ā) . B . (C + C̄ ) + A . (B + B̄) . C
35
a
b
c
f(a,b,c)
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Imagen de cada terna bajo la
función booleana f(a,b,c).
la cual por supuesto es la misma que la que se obtiene
por el método anterior.
36
S ECCIÓN 1
Retículos.
Esta sección trata sobre retículos, que constituyen
una generalización de la estructura de álgebra de
Boole.
Se relaciona con otro tema importante de la
materia : grupos, porque los subgrupos de un grupo
forman con operaciones claramente definidas una
estructura de retículo. En general, los subgrupos de un
grupo no formarán un álgebra de Boole y por eso la
estructura de retículo es la adecuada para tratar este
asunto.
También prestamos especial atención a las redes
no distributivas.
C ONTENIDOS
1. Retículos no distributivos.
2. Grupo Z2 × Z4.
3. Relación entre subgrupos y retículos.
37
Problema 1.
Sea G = Z2 × Z4 el producto de los grupos (Z2, + ) y
(Z4, + ).
Otro subgrupo de Z4 es el subgrupo generado por el 3 el
cual resulta
K = < 3 > = {3,2,1,0}.
a)Determinar si este grupo es cíclico y hallar la red de
subgrupos de G.
Con esto, el retículo de subgrupos de Z4 resulta el
del diagrama siguiente.
b) Determinar si la red de dichos subgrupos forma una
red distributiva.
Ahora bien, es un poco más difícil el retículo de
subgrupos de G = Z2 × Z4 porque este grupo no es
cíclico. Sin embargo, en virtud del teorema de
Lagrange tenemos que si H ≤ G es un subgrupo de G
Solución.
Recordemos como se definen los grupos Z2 y Z4.
a)
+
0
1
2
3
0
0
1
2
3
+
0
1
1
1
2
3
0
0
0
1
2
2
3
0
1
1
1
0
3
3
0
1
2
entonces | H | | G | . Luego, como | G | = 8 sólo podemos
tener subgrupos de orden 1,2,4,8. Cada elemento de
G = Z2 × Z4 generará un subgrupo cíclico, aunque
varios de ellos pueden coincidir.
En efecto, tenemos
1) < (0,0) > = {(0,0)}
2) < (1,0) > = {(1,0), (0,0)}
3) < (0,2) > = {(0,2), (0,0)}
Un subgrupo de Z4 es por ejemplo,
H = {0,2} = < 2 > .
4) < (1,1) > = {(1,1), (0,2), (1,3), (0,0)} = < (1,3) >
5) < (0,1) > = {(0,1), (0,2), (0,3), (0,0)} = < (0,3) >
6) < (1,2) > = {(1,2), (0,0)}
38
Con esto tenemos que todos los subgrupos cíclicos
posibles de G = Z2 × Z4 ya están listados, que el grupo
en cuestión G = Z2 × Z4 no es cíclico y que cualquier
otro subgrupo debe tener orden 4 ya que si tuviera
orden 2 debería ser cíclico y estar listado. Ahora bien,
en el subgrupo posible de orden 4 todos sus elementos
deben tener orden 2 (salvo el neutro) pues sino sería
cíclico y a los cíclicos los hemos listado todos. Luego, el
único subgrupo posible faltante es :
H = {(1,2), (0,2), (1,0), (0,0)}.
Como H es verdaderamente un subgrupo tenemos
junto con todo el grupo G = Z2 × Z4 los ocho subgrupos
de G = Z2 × Z4.
Estos subgrupos se pueden ordenar por la
inclusión en el siguiente retículo.
Enunciado.
b) Vista como red (o Lattice) esta red no es
distributiva. En efecto contiene una subred isomorfa a
N5 y como sabemos dicha red no es distributiva.
Inclusive contiene dos subredes isomorfas a N5.
Dado el retículo L = (D50, | ) realizar el diagrama
de Hasse, hallar el complemento de cada elemento (si
existe), determinar si es distributivo y finalmente
determinar si es isomorfo al retículo R = (D12, | ).
Solución.
39
Comencemos por determinar cual es el conjunto
sobre el cual se va a formar la estructura de retículo. El
conjunto D50 es
Galería 2 : Redes isomorfas.
Vemos a partir de este diagrama de Hasse que
para cada par de elementos x, y ∈ D50 existen
sup{x, y} = x ∨ y
inf{x, y} = x ∧ y
es decir el conjunto (D50, | ) es una red.
Como esta red NO contiene una subred isomorfa a
M5 ni a N5 vemos que nuestra red es distributiva.
Para determinar el complemento de cada
elemento debemos hallar para cada x ∈ D50 un
elemento x′ ∈ D50 tal que
El diagrama de Hasse de la red D50. A continuación el
diagrama de Hasse de la red D12.
D50 = {1,2,5,10,25,50}.
Si lo ordenamos parcialmente por la divisibilidad
tenemos el diagrama de Hasse siguiente
X
X’
1
50
2
25
5
No existe
10
No existe
25
2
50
1
x ∨ x′ = 50
y
x ∧ x′ = 1.
Con el diagrama de Hasse vemos fácilmente que
tenemos la siguiente tabla.
40
Finalmente para determinar si es isomorfo al
retículo R = (D12, | ) tenemos, pasando en la ventana a
la siguiente figura que un posible isomorfismo es el
siguiente
X
F(X)
1
1
2
3
5
2
10
6
25
4
50
12
pues con esta función se verifica que
f (x ∨ y) = f (x) ∨ f (y)
f (x ∧ y) = f (x) ∧ f (y)
que es, junto con la biyectividad de f la definición de
isomorfismo.
41
Álgebra de Boole
Una estructura A = (B, + , . ,′ ,0,1) es un álgebra de Boole si
+, . : B × B → B
′: B → B
y si ∀x, y, z ∈ B tenemos
1. x + y = y + x
x.y = y.x
2. (x + y) + z = x + (y + z)
x . (y . z) = (x . y) . z
3. x . (y + z) = x . y + x . z
x + (y . z) = (x + y) . (x + z)
4. x + 0 = x
x.1 = x
5. ∀x ∈ B, ∃x′ ∈ B : x + x′ = 1
x . x′ = 0.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 4 - Álgebra de Boole.
Clase
Sea A ⊂ U y ∼ una relación de equivalencia en A. Sea a ∈ A.
Se define la clase de a, como el conjunto cl(a) = {x ∈ A : x ∼ a}.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 1 - Producto cartesiano.
Capítulo 1 - Producto cartesiano.
Capítulo 1 - Relaciones.
Capítulo 1 - Relaciones.
Congruencia
Sean a, b ∈ Z . Sea m ∈ N, m > 1. Decimos que
a ≡ b (m) ⟺ m | b − a.
Es equivalente esto a decir que
r(a, m) = r(b, m)
donde r(a, m) es el resto de dividir a por m.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 2 - Divisibilidad. Congruencia.
Capítulo 2 - Teorema de Fermat.
Conjunto cociente
Sea A ⊂ U y ∼ una relación de equivalencia en A. Se llama “conjunto cociente” de A
bajo la relación ∼ al conjunto
A / = {cl(a) : a ∈ A}.
∼
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 1 - Producto cartesiano.
Capítulo 1 - Relaciones.
Equivalencia
Sea A ⊂ U un conjunto. Se dice que una relación ∼ es de equivalencia en A si
1. ∼ es reflexiva en A.
2. ∼ es simétrica en A.
3. ∼ es transitiva en A.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 1 - Producto cartesiano.
Capítulo 1 - Relaciones.
Euler
La función ϕ de Euler es la función definida así :
ϕ:N→N
ϕ(n) = {a < n : (a, n) = 1} .
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 2 - Teorema de Fermat.
Forma normal disyuntiva
Sea f (x, y, z) : B 3 → B una función booleana. Se llama forma normal disyuntiva de f a
una suma de minitérminos distintos mi tal que
f (x, y, z) =
n
∑
mi.
i=1
Si f tiene n “unos” entonces la forma normal dusyuntiva tendrá n términos.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 4 - Álgebra de Boole.
Capítulo 4 - Álgebra de Boole.
Minitérminos
Sea n ∈ N. Un minitérmino a n variables es una expresión de la forma m = y1 . y2 . … . yn
donde cada yi = xi o yi = x̄i.
Por ejemplo, un minitérmino a tres variables es m = x1 . x̄2 . x3.
Observemos que el valor de este minitérmino es siempre 0 salvo para la terna (1,0,1).
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 4 - Álgebra de Boole.
Recurrencia
En general una expresión de la forma
an+1 = f (an)
se llama una recurrencia de primer orden. Para las recurrencias de segundo orden la
definición es la siguiente : una expresión de la forma
an+2 = f (an+1, an).
Resolver una recurrencia significa hallar la o las sucesiones xn que sustituidas en ella la
convierten en igualdad.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 3 - Recurrencia.
Capítulo 3 - Recurrencia.
Capítulo 3 - Recurrencia.
Capítulo 3 - Recurrencia.
Capítulo 3 - Recurrencia.
Red
Una red, retículo o lattice es un conjunto parcialmente ordenado (L, ⪯ ) en el cual
∀x, y ∈ L : ∃ sup{x, y}, in f{x, y} .
Una segunda definición de retículo es una terna (L, ∨ , ∧ ) donde
∨ , ∧ : L × L → L son operaciones binarias
1. Asociativas.
2. Conmutativas.
3. Idempotentes. ( ∀x ∈ L : x ∨ x = x
,
x ∨ x = x)
4. Ley de absorción. ( ∀x, y ∈ L : x ∧ (x ∨ y) = x
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 4 - Retículos.
Capítulo 4 - Retículos.
Capítulo 4 - Retículos.
,
x ∨ (x ∧ y) = x)
Relación de orden
Sea A ⊂ U. Sea ⪯ una relación en A . Se dice que ⪯ es de orden en A si ⪯ es
1. Reflexiva.
2. Antisimétrica.
3. Transitiva.
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 1 - Relaciones.
Teorema de Fermat
Sea p un número primo y a ∈ N tal que p |/ a. Entonces a p−1 ≡ 1 (p).
Related Glossary Terms
Drag related terms here
Index
Find Term
Capítulo 2 - Teorema de Fermat.
Capítulo 2 - Teorema de Fermat.