conjuntos - upm · 1)r(x 2;y 2) ,x 1y 1 = x 2y 2. comprueba que es de equivalencia y calcula el...

Conjuntos y relaciones entre conjuntos Conjuntos

Conjuntos

Un conjunto es una coleccion bien definida de objetos en la que el orden es irrelevante.Dichos objetos pueden ser reales o conceptuales y se llaman elementos o miembros delconjunto. Por su estructura, dentro de un conjunto no se admiten repeticiones (todos susmiembros deben ser distintos).

Definicion por extension de un conjunto: Consiste en enumerar sus elementosentre llaves.Ejemplo: A = {1, 2, 3, 4, 5, 6, 7, 8, 9}.Definicion por comprension de un conjunto: Mediante una propiedad que locaracterice.Ejemplo: A = {a ∈ Z | 1 ≤ a ≤ 9}.

El cardinal de un conjunto A es el numero de elementos de A y se representa por |A|.

1 / 59

Conjuntos y relaciones entre conjuntos Conjuntos

Union e interseccion de conjuntos

Dados dos conjuntos A y B , se define la union de A y B como A∪B = {x | x ∈ A o x ∈B} y la interseccion de A y B como A ∩ B = {x | x ∈ A y x ∈ B}.Algunos otros sımbolos: ∀, ∃,∈, 6∈,⊂, 6⊂, ∅,⇒,⇔, . . . .

Propiedades:

i) A ∩ B = B ∩ A,A ∪ B = B ∪ A (conmutativa),

ii) (A ∩ B) ∩ C = A ∩ (B ∩ C ), (A ∪ B) ∪ C = A ∪ (B ∪ C ) (asociativa),

iii) A ∩ A = A,A ∪ A = A (idempotente),

iv) A ∩ (B ∪ A) = A,A ∪ (B ∩ A) = A (absorcion),

v) A ∩ ∅ = ∅, A ∪ ∅ = A,

vi) (A ∩ B) ∪ C = (A ∪ C ) ∩ (B ∪ C ), (A ∪ B) ∩ C = (A ∩ C ) ∪ (B ∩ C ) (distributiva).

2 / 59

Conjuntos y relaciones entre conjuntos Producto cartesiano

Producto cartesiano de conjuntos

El producto cartesiano de dos conjuntos A y B es el conjunto de pares ordenados de laforma (a, b) donde a ∈ A y b ∈ B : A× B = {(a, b) | a ∈ A, b ∈ B}. Se denota A× B .

Ejemplo. Si A = {1, 2, 3} y B = {a, b, c , d}, entoncesA×B = {(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2, d), (3, a), (3, b), (3, c), (3, d)}.Se puede representar como:

a b c d1 (1, a) (1, b) (1, c) (1, d)2 (2, a) (2, b) (2, c) (2, d)3 (3, a) (3, b) (3, c) (3, d)

Pregunta: ¿Se cumple alguna de las siguientes propiedades?i) A ∩ (B × C ) = (A ∩ B)× (A ∩ C ),ii) A ∪ (B × C ) = (A ∪ B)× (A ∩ C ),

iii) A× (B ∩ C ) = (A× B) ∩ (A× C ),iv) A× (B ∪ C ) = (A× B) ∪ (A× C ). 3 / 59

Conjuntos y relaciones entre conjuntos Relaciones

Relaciones

Una relacion binaria R de un conjunto A en un conjunto B es un subconjunto delproducto cartesiano A× B .

Si (a, b) ∈ R se dice que a esta relacionado con b (aRb).

Si (a, b) 6∈ R se dice que a no esta relacionado con b (a¬Rb).

Una relacion binaria R en un conjunto A es una relacion de A en A, es decir, un subconjuntodel producto cartesiano A× A.

Ejemplo. En el conjunto A = {a, e, i , o, u} de las vocales se dice que dos vocales estanrelacionas si forman un diptongo. EntoncesR = {(a, i), (a, u), (e, i), (e, u), (o, i), (o, u), (i , a), (i , e), (i , o), (i , u), (u, a), (u, e), (u, o), (u, i)}.

Dados A = {a1, a2, . . . , am} y B = {b1, b2, . . . , bn} conjuntos finitos no vacıos, y dada Rrelacion de A en B , llamamos matriz de la relacion R a la matriz MR ∈ Mm×n dada

por MR = (mij) donde mij =

{1 si aiRbj0 si ai¬Rbj .

.

4 / 59

Conjuntos y relaciones entre conjuntos Relaciones de equivalencia

Relaciones de equivalencia

Una relacion R en un conjunto A es una relacion de equivalencia si y solo si es:

reflexiva: aRa, para todo a ∈ A,

simetrica: aRb ⇒ bRa,

transitiva: aRb y bRc ⇒ aRc .

Dada R relacion de equivalencia en A y dado a ∈ A se llama clase de a al conjunto[a] = {b ∈ A | bRa}.Se llama conjunto cociente de A respecto de R al conjunto formado por las clases deequivalencia, esto es, A/R = {[a] | a ∈ A}.Propiedades. Dada R ⊂ A× A relacion de equivalencia, se tiene que:

a) [a] = [b]⇔ aRb,

b) [a] 6= [b]⇔ [a] ∩ [b] = ∅ (las clases son disjuntas).

5 / 59


Ejemplos de relaciones de equivalencia

i) Dado P conjunto de rectas del plano y rRs ⇔ r‖s, R es relacion de equivalencia ypara toda r ∈ P se tiene que [r ] = {s ∈ P | r‖s}.

ii) Dado P conjunto de rectas del plano y rRs ⇔ r⊥s, R no es relacion de equivalenciapues no es reflexiva ni transitiva.

iii) Dado R \{0} y aRb ⇔ a +1

a= b +

1

b, se tiene que

a +1

a= b +

1

b⇔ a − b =

a − b

ab⇔

b = a

o

ab = 1⇔ b =1

a.

Entonces R es relacion de equivalencia y para todo a ∈ R \{0} se tiene que [a] ={a,

1

a

}.

6 / 59


Particiones de conjuntos

Una particion en un conjunto no vacıo A es una familia de subconjuntos no vacıos ydisjuntos dos a dos de A tales que su union es A.

Teorema. Si R es una relacion de equivalencia en A, entonces el conjunto cociente A/Res una particion de A.

Demostracion. Inmediata a partir de las propiedades de las relaciones de equivalencia

Teorema. Si P = {Ai}i∈I es una particion de A, entonces existe una relacion deequivalencia RP en A tal que el conjunto cociente A/RP = P .

Demostracion. Definimos aRPb ⇔ existe i ∈ I tal que a, b ∈ Ai . Es inmediatocomprobar que RP es una relacion de equivalencia. Ademas para todo a ∈ A se tieneque [a] = Ai donde Ai es el unico elemento de la particion que contiene a a. Por tantoA/RP = P .

7 / 59

Conjuntos y relaciones entre conjuntos Ejercicios de relaciones de equivalencia

Ejercicios de relaciones de equivalencia

Ejercicio 1. En el conjunto N×N se define la relacion (a, b)R(c , d) ⇔ ad = bc .Averigua si es de equivalencia y si lo es calcula la clase del elemento (4, 8).

Ejercicio 2. En el conjunto N×N se define la relacion (a, b)R(c , d)⇔ a + d = b + c .Averigua si es de equivalencia y si lo es calcula la clase del elemento (2, 5).

Ejercicio 3. En R2 se define la relacion (x1, y1)R(x2, y2)⇔ x1y1 = x2y2. Comprueba quees de equivalencia y calcula el conjunto cociente.

Ejercicio 4. En Z se define la relacion xRy ⇔ x2 − y 2 = x − y . Comprueba que es deequivalencia y calcula el conjunto cociente.

Ejercicio 5. En R se define la relacion xRy ⇔ ∃h ∈ Z tal que y = x + h. Prueba que

es de equivalencia. Razona si los elementos2

3y

5

4pertenecen a la misma clase.

8 / 59

Relaciones de orden Relaciones de orden

Relaciones de orden

Una relacion R en un conjunto A es una relacion de orden si es reflexiva, antisimetricay transitiva, donde R es antisimetrica si aRb + bRa⇒ a = b.Un conjunto ordenado es un par (A,R), con R una relacion de orden en A.

Ejemplos. (N,≤) y (N, |) (a|b ⇔ a divide a b) son conjuntos ordenados.

Dada R relacion en A, se dice que dos elementos a y b de A son comparables si aRb obRa.

Se dice que R es un orden total si todo par de elementos de A son comparables.Se dice entonces que (A,R) es un conjunto totalmente ordenado.

Ejemplo. (N,≤) es totalmente ordenado).

Se dice que R es un orden parcial si es una relacion de orden no total.

Ejemplo. (N, |) es parcialmente ordenado).

9 / 59

Relaciones de orden Diagrama de Hasse de una relacion de orden

Diagrama de Hasse de una relacion de orden

El diagrama de Hasse de una relacion de orden en un conjunto finito es unarepresentacion de esta, en la que si a 6= b verifican que a ≤ b, entonces se dibuja a pordebajo de b y se unen a y b por un segmento, suprimiendo los segmentos que correspondena la propiedad transitiva (si a ≤ b y b ≤ c se suprime el segmento correspondiente aa ≤ c).

Ejemplo. Para D15, D20 y D30 (Dn =divisores positivos de n) con la relacion dedivisibilidad (a ≤ b ⇔ a divide a b) se tienen los siguientes diagramas de Hasse:

rr r

r

��

@@@��

@@@

1

3 5

15

D15 = {1, 3, 5, 15}

rr r

r rr

��

@@

@@@@

��

@@@

@@@

��

1

2 5

4 10

20

D20 = {1, 2, 4, 5, 10, 20}

rr r rr r r

r

1

2 3

10 15

5

6

30

D30 = {1, 2, 3, 5, 6, 10, 15, 30}

��

@@@

��

@@@

��

@@@

��

@@@

10 / 59

Relaciones de orden Elementos caracterısticos de conjuntos ordenados

Elementos caracterısticos de conjuntos ordenados

Sea (A,≤) un conjunto ordenado y B un subconjunto no vacıo de A. Se dice que

i) c ∈ A es cota superior de B si x ≤ c para todo x ∈ B ,ii) c ∈ A es cota inferior de B si c ≤ x para todo x ∈ B ,

iii) s ∈ A es el supremo de B si es la menor de las cotas superiores, es decir, si es cotasuperior y para toda cota superior c de B se tiene s ≤ c ,

iv) i ∈ A es el ınfimo de B si es la mayor de las cotas inferiores, es decir, si es cotainferior y para toda cota inferior c de B se tiene c ≤ i .

v) si el supremo de B es un elemento de B llama maximo de B ,vi) si el ınfimo de B es un elemento de B llama mınimo de B ,vii) m ∈ B es maximal de B si no existe x ∈ B \ {m} tal que m ≤ x ,viii) m ∈ B es minimal de B si no existe x ∈ B \ {m} tal que x ≤ m,

Se dice que B esta acotado superiormente si existe c ∈ A cota superior de B . Se diceque B esta acotado inferiormente si existe c ∈ A cota inferior de B . Se dice que Besta acotado si esta acotado superiormente e inferiormente.

11 / 59

Relaciones de orden Elementos caracterısticos de conjuntos ordenados

Elementos caracterısticos de conjuntos ordenados

Ejemplo. Dado A = {a, b, c , d , e, f , g , h, i , j , k , l} y dado B = {f , g , i , j , k} ⊂ A:

ss s sj j js s sj j s

s sss

l

kji

hgfe

dcb

a

��

@@

@@��

��

@@

@@

@@@@

��

��

��

@@@@

@@

@@

@@

@@

cotas superiores de B en A: {a, b, c}cotas inferiores de B en A: {l}no existe supA B

existe infA B = l

no existe maxB

no existe minB

elementos maximales de B : {f , g}elementos minimales de B : {i , j , k}

12 / 59

Relaciones de orden Existencia y unicidad de elementos caracterısticos

Existencia y unicidad de elementos caracterısticos

Teorema. Sea B un subconjunto no vacıo de un conjunto ordenado (A,≤). Tanto elmaximo como el mınimo de B , si existen, son unicos.

Teorema. Sea B un subconjunto no vacıo de un conjunto ordenado (A,≤). Tanto elsupremo como el ınfimo de B , si existen, son unicos.

Teorema. Sea B un subconjunto finito no vacıo de un conjunto ordenado (A,≤).Entonces B tiene al menos un elemento maximal y otro minimal.

Demostracion. Sea a1 ∈ B .Si a1 es minimal ya hemos terminado.Si no es minimal, existira a2 ∈ B \ {a1} tal que a2 ≤ a1.Si a2 es minimal ya hemos terminado.Si no es minimal, existira a3 ∈ B \ {a1, a2} tal que a3 ≤ a2 ≤ a1.Continuando este proceso, o bien obtenemos un elemento minimal o acabarıamosordenando todos los elementos de B (por ser finito) de la forma an ≤ an−1 ≤ · · · ≤a2 ≤ a1. Pero entonces an serıa el minimo del conjunto y por tanto minimal. 13 / 59

Relaciones de orden Ejercicios de conjuntos ordenados

Ejercicios de conjuntos ordenados

Ejercicio 6. Halla elementos maximales, minimales, maximo y mınimo (si los hay) de A:

a)

s ss ssd e

b c

a

��

@@

@@

@@

��@@

b)

s sss sd e

c

a b

��

@@

@@

c)

ss ss ss

f

d e

b c

a

@@

@@

��@@ d)

s s ss sc d e

a b

��

��

@@

@@

Ejercicio 7. Halla todos los elementos caracterıstiocs de B en A:

a)

s ss sss se ee

f g

d e

c

a b

��

@@

@@

@@

@@

��

@@

B = {c , d , e}

b)

ss ss sss s

ee eh

f g

d e

c

a b

��

@@

@@��@

@@@

@@

��

@@

B = {d , e, f }

c)

s ss ss

se ee

e f

c d

b

a

��

ZZ

ZZ��@@

B = {b, c , d}14 / 59

Relaciones de orden Ejercicios de conjuntos ordenados

Ejercicios de conjuntos ordenados

Ejercicio 8. Representar el diagrama de Hasse de los siguientes conjuntos ordenados yhallar los elementos notables de los subconjuntos senalados:

a) (D60, |), A = {2, 5, 6, 10, 12, 30} y B = {2, 3, 6, 10, 15, 30}.b) (D48, |), A = {2, 4, 6, 12} y B = {3, 6, 8, 16}.c) (D40, |), A = {4, 5, 10} y B = {2, 4, 8, 20}.

Ejercicio 9. Hallar, si los hay, los elementos maximales, minimales, maximo y mınimopara los siguientes conjuntos ordenados:a) (P(X ),⊂), b) ((0, 1),≥), c) (N, |), d) (N−{1}, |).

Ejercicio 10. En cada uno de los casos siguientes, dıgase si el conjunto X tiene o no unacota inferior, y si tiene alguna hallase su ınfimo si existe:a) X = {x ∈ Z | x2 ≤ 16}, b) X = {x ∈ Z | x = 2y para algun y ∈ Z}, c)X = {x ∈ Z | x2 ≤ 100x}.

15 / 59

Relaciones de orden Ordenacion topologica

Ordenacion topologica

Teorema. Dado un orden parcial ≤ en un conjunto finito (A,≤), existe un orden total≤′ que lo contiene (esto es, tal que a ≤ b ⇒ a ≤′ b).

Demostracion. Sea a1 un elemento minimal de A.Sea a2 un elemento minimal de A \ {a1} y definimos a1 ≤′ a2.Sea a3 un elemento minimal de (A \ {a1, a2},≤) y definimos a2 ≤′ a3.Como A es finito, despues de un numero finito de pasos tendremos los elementos de Aordenados en la forma a1 ≤′ a2 ≤′ · · · ≤′ an.Finalmente, el orden obtenido contiene al dado en el sentido de que si a ≤ b, entoncesa ≤′ b.En efecto, si ai ≤ aj , aj no puede ser minimal de un conjunto que contenga ai , luegohemos de haber escogido ai antes que aj . Por tanto ai ≤′ aj .

16 / 59

Relaciones de orden Ejercicios

Ejercicios. Orden topologico

Ejercicio 11. Dado el orden parcial del diagrama de Hasse dela figura, obtener un orden total que lo contenga. ¿Cuantospueden obtenerse?

Ejercicio 12. Sea T = {a, b, c , d , e, f , g} la lista de tareaspara realizar un trabajo, de las que se sabe que unas precedeninmediatamente a otras de la siguiente forma: f ≤ a, f ≤ d ,e ≤ b, c ≤ f , e ≤ c , b ≤ f , e ≤ g , g ≤ f . Hallar el ordenparcial. ¿Que tareas pueden realizarse independientemente?Construir un orden si el trabajo lo realiza solo una persona. u u

u uu

u uuu

a b

c d

e

f g

h

i

��

@@@

@@

@@

@@��

@@@

17 / 59

Relaciones de orden Ordenes en conjuntos producto

Ordenes en conjuntos producto

Sean (A,≤) y (B ,≤′) conjuntos ordenados, se define

i) (a, b) ≤PROD (c , d) si y solo si a ≤ c y b ≤′ d ,

ii) (a, b) ≤LEX (c , d) si y solo si

a 6= c y a ≤ coa = c y b ≤′ d

.

Proposicion. Sean (A,≤) y (B ,≤′) conjuntos ordenados. Entonces (A × B ,≤PROD) y(A× B ,≤LEX ) son conjuntos ordenados.

Observacion. Los ordenes anteriores tambien se pueden definir en el producto de nconjuntos ordenados.

18 / 59

Relaciones de orden Ejercicios

Ejercicios. Ordenes en conjuntos producto

Ejercicio 13. Determina el orden lexicografico de las siguientes cadenas de bits: 001,111, 010, 011, 000 y 100 basado en el orden 0 ≤ 1. Dibujar el diagrama de Hasse deestas cadenas, ahora con el orden producto.

Ejercicio 14. Sea A = ({1, 2, 3, 4},≤). Respecto al orden lexicografico:a) Encontrar todos los pares en A× A anteriores a (2, 3).b) Encontrar todos los pares en A× A posteriores a (3, 1).c) Dibujar el diagrama de Hasse de (A× A,≤Lex).

Ejercicio 15. En (D10, |) × (D18, |) se considera el orden lexicografico. Hallar lascotas superiores, cotas inferiores, supremo e ınfimo, si existen, del subconjunto B ={(2, 2), (2, 3)}. Dibujar el diagrama de Hasse. Se define f : D10 × xD18 −→ D180 porf (a, b) = ab ¿es f inyectiva? ¿es suprayectiva?

Ejercicio 16. Se considera en D48 × N el orden lexicografico correspondiente a tomarel orden divisibilidad en el primer factor y el orden usual en el segundo factor. Sea B ={(2, 2), (2, 3), (3, 2), (6, 3), (6, 1), (4, 2)}. Se pide hallar, si existen, las cotas superiores einferiores, elementos maximales y minimales, maximo, mınimo, supremo e ınfimo de B .

19 / 59

Relaciones de orden Isomorfismos de conjuntos ordenados

Isomorfismos de conjuntos ordenados

Dados dos conjuntos ordenados (A,≤) y (B ,≤′), y dada f : A −→ B , se dice que f esun isomorfismo de conjuntos ordenados si es biyectiva y cumple que f (a) ≤′ f (e)⇔a ≤ e.

Ejemplo. Sea P({a, b, c}) la familia de subconjuntos del conjunto {a, b, c}. Es decir:

P({a, b, c}) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Entonces (P({a, b, c}),⊂) es isomorfo a (D30, |).Tambien (D30, |) es isomorfo a (D42, |) pero no a (D12, |).

20 / 59

Retıculos Primera definicion de retıculo

Primera definicion de retıculo

Un conjunto ordenado (R ,≤) es un retıculo si para cualesquiera a, b ∈ R existesup{a, b} ∈ R e inf{a, b} ∈ R .

Ejemplos

i) (N,≤) y (N, |) son retıculos,

ii) (Dn, |) es retıculo,

iii) (P(X ),⊂) es retıculo.

Observacion. Todo conjunto totalmente ordenado es un retıculo. El recıproco no escierto en general.

21 / 59

Retıculos Segunda definicion de retıculo

Segunda definicion de retıculo

La nocion de retıculo se puede definir tambien del modo siguiente.

Definicion. Un retıculo es una terna (R ,∨,∧) donde R es un conjunto y ∧,∨ : R×R −→R son dos operaciones binarias internas tales que:

i) a ∧ a = a, a ∨ a = a (idempotente),

ii) a ∧ b = b ∧ a, a ∨ b = b ∨ a (conmutativa),

iii) (a ∧ b) ∧ c = a ∧ (b ∧ c), (a ∨ b) ∨ c = a ∨ (b ∨ c) (asociativa),

iv) a ∧ (b ∨ a) = a, a ∨ (b ∧ a) = a (absorcion).

Ejemplos. (P(X ),⊂) es retıculo con esta segunda definicion con las operaciones ∩ y ∪.

22 / 59

Retıculos Equivalencia de ambas definiciones de retıculo

Equivalencia de ambas definiciones de retıculo

Proposicion. Las dos definiciones de retıculo son equivalentes y se relacionan de lasiguiente manera:

a ≤ b ⇔ a ∨ b = b ⇔ a ∧ b = a.

Demostracion. Si (R ,≤) es un retıculo definimos ∧,∨ : R × R −→ R como a ∧b = inf{a, b} y a ∨ b = sup{a, b}. Entonces ∧ y ∨ verifican las cuatro propiedades(idempotente, conmutativa, asociativa y absorcion) y a ≤ b ⇔ a ∨ b = b ⇔ a ∧ b = a.Reciprocamente, si (R ,∨,∧) es un retıculo, definimos a ≤ b ⇔ a ∨ b = b ⇔ a ∧ b = a.Es facil ver que ≤ es una relacion de orden.

23 / 59

Retıculos Ejemplos

Ejemplos

¿Son los siguientes conjuntos ordenados retıculos?

qq q

qq qq

��

@@@��

@@@

��

@@@

qqq

q q��

AAAAA

��

@@@

qq q

q qq

��

@@@��

@@@

��

��

@@@

q qq q

qq

��

@@@

SI NO SI NO

Indicacion: Si en un conjunto ordenado existen dos elementos maximales o dos minimalesentonces ese conjunto ordenado no es un retıculo. Tampoco lo es si existen dos puntos(necesariamente no comparables) sin cotas superiores o inferiores o de tal forma quedentro del conjunto de cotas superiores (o inferiores) existan dos elementos minimales (odos elementos maximales).

24 / 59

Retıculos Retıculos isomorfos

Retıculos isomorfos

Sean (R ,≤) y (S ,≤′) retıculos. Se dice que una aplicacion f : R −→ S es unhomomorfismo de retıculos si para cualesquiera a, b ∈ R se tiene que

f (sup≤{a, b}) = sup

≤′{f (a), f (b)} y f (inf

≤{a, b}) = inf

≤′{f (a), f (b)}.

Se dice que f es isomorfismo de retıculos si es homomorfismo y es biyectivo.Observacion. Tambien se podrıa definir homomorfismo e isomorfismo de retıculos apartir de la segunda definicion de retıculo.

Proposicion. Sean (R ,≤) y (S ,≤′) retıculos y sea f : R −→ S una aplicacion biyectiva.Entonces f es un isomorfismo de retıculos si y solo si f es un isomorfismo de conjuntosordenados.

Ejemplo. (P({a, b},⊂) y (D6, |) son retıculos isomorfos.

25 / 59

Retıculos Subretıculos

Subretıculos

Sea (R ,≤) un retıculo. Se dice que un subconjunto no vacıo A de R es un subretıculo si(A,≤) es un retıculo y para cualesquiera a, b ∈ A se tiene que

supA{a, b} = sup

R{a, b} e inf

A{a, b} = inf

R{a, b}.

Esto es equivalente a que para cualesquiera a, b ∈ A se cumpla que

supR{a, b} ∈ A e inf

R{a, b} ∈ A.

Ejemplos. Dados los retıculos siguientes

qq qqq qq

��

@@��@@

��@@

R qq qq qq

��

@@

��@@

A qq qqq

��

@@��@@

B

se tiene que B es subretıculo de A pero A no es subretıculo de R .26 / 59

Retıculos Subretıculos

Subretıculos

La nocion de subretıculo se puede definir tambien a partir de la definicion alternativa deretıculo de la forma siguiente:Sea (R ,∨,∧) un retıculo y sea A un subconjunto no vacıo de R . Entonces (A,∨′,∧′) esun subretıculo de (R ,∨,∧) si para cualesquiera a, b ∈ A se tiene que

a ∨′ b = a ∨ b y a ∧′ b = a ∧ b

o, equivalentemente, si y solo si

a ∨ b ∈ A y a ∧ b ∈ A,

para cualesquiera a, b ∈ A.

27 / 59

Retıculos Retıculos producto

Retıculos producto

Proposicion. Si (A,R) y (B , S) son retıculos, entonces (A× B ,RPROD) tambien lo es.

Proposicion. Si (A,R) y (B , S) son retıculos, entonces (A × B ,RLEX ) es retıculo si Res un orden total en A o si existe inf B y supB .

Demostracion. Sean (a, b), (c , d) ∈ A× B . Si a = c , entonces

supRLEX

{(a, b), (a, d)} = (a, supS{b, d}) e inf

RLEX

{(a, b), (a, d)} = (a, infS{b, d}).

Si a 6= c y aRc , supRLEX{(a, b), (c , d)} = (c , d) e infRLEX

{(a, b), (c , d)} = (a, b).Si a 6= c y cRa, supRLEX

{(a, b), (c , d)} = (a, b) e infRLEX{(a, b), (c , d)} = (c , d).

Finalmente, si a y c no son comparables, entonces

supRLEX

{(a, b), (c , d)} = (supR{a, c}, inf B) e inf

RLEX

{(a, b), (c , d)} = (infS{a, c}, supB)

siempre que existan inf B y supB .28 / 59

Retıculos Retıculos acotados

Retıculos acotados

Se dice que un retıculo es acotado si tiene maximo y mınimo. Notaremos por 1 al maximoy por 0 al mınimo.

Ejemplo. (N, |) no es acotado.

Proposicion. Todo retıculo finito es acotado.

Demostracion. Supongamos que A = {a1, a2, . . . , an}. Entonces a1 ∨ a2 ∨ · · · ∨ an = 1pues (a1∨a2∨· · ·∨an)∧ai = ai por la propiedad de absorcion y (a1∨a2∨· · ·∨an)∨ai =a1 ∨ a2 ∨ · · · ∨ an para todo i ∈ {1, 2 . . . , n}. Por otra parte a1 ∧ a2 ∧ · · · ∧ an = 0 pues(a1∧a2∧· · ·∧an)∧ai = a1∧a2∧· · ·∧an y (a1∧a2∧· · ·∧an)∨ai = ai (por la propiedadde absorcion) para todo i ∈ {1, 2 . . . , n}.

29 / 59

Retıculos Retıculos complementarios

Retıculos complementarios

Sea (R ,≤) un retıculo acotado. Dado a ∈ R se dice que a′ ∈ R es complementario de asi sup{a, a′} = 1 e inf{a, a′} = 0. Se dice que (R ,≤) es complementario si es acotado ytodo elemento tiene complementario.

Ejemplos.i) (N, |) no es complementario (no es acotado),ii) (Dn, |) es complementario ⇔ n es producto de numeros primos distintos,

iii) (P(X ),⊂) es complementario,iv) ({0, 1},≤) es complementario.

Ejemplos de retıculos complementarios y no complementarios.

rr rr rr rr

��@@

�� @@

SI rr rr rr rr

��@@HH

H

HHH�� @@

NO rr rr rrr rr

��@@

�� @@��@@

�� @@

NO rrrrrr

NO rrrrrrrr

rrrr

1

2

4

8

3

6

12

24

9

18

36

72

��

��

��

��

��

��

��

@@

@@@

@@

@@@

@@@

@@

NO 30 / 59

Retıculos Retıculos distributivos

Retıculos distributivos

Se dice que un retıculo (R ,∨,∧) es distributivo si para cualesquiera a, b, c ∈ R se tieneque (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c) y (a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c).

Ejemplo. (P(X ),⊂) es distributivo.

Proposicion. En un retıculo acotado y distributivo, el complementario de un elemento,si existe, es unico. Al unico complementario de a se le denota por a′.

Corolario. Si R es acotado y un elemento tiene dos complementarios, entonces R no esdistributivo.

Proposicion. Un retıculo (R ,∨,∧) es distributivosi y solo si no contiene un subretıculo isomorfo a losde la derecha.

Corolario. (Dn, |) es distributivo, para todo n ∈ N.

rr rr

r

0

a

c

b

1

@@@

JJJJJ

��

rr r r

r

0

a b c

1

@@@

��

��

@@@

31 / 59

Retıculos Retıculos distributivos

Ejercicios de retıculos

Ejercicio 17. Estudiar cuales de los siguientes conjuntos ordenados son retıculos:a)

t t tt t

t tt

f g h

d e

b c

a

��

@@@

��

@@

@@@

@@@

b)

tt

t tt t t t

h

g

e f

a b c d

��

QQQQ��

@@@

��

@@@

c)

tt

t t tt

f

e

b c d

a

��

@@@��

@@@

Ejercicio 18. Obtener los diagramas de Hasse de todos los retıculos,salvo isomorfismos, de uno, dos, tres, cuatro y cinco elementos.

Ejercicio 19. Estudiar si el retıculo de la figura se verifica la igualdada ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

Ejercicio 20. Encontrar el complementario de cada elemento de D42

y D105. tt

t t tt

0

d

a b c

1

��

@@@��

@@@

32 / 59

Algebras de Boole Algebras de Boole

Algebras de Boole

Un algebra de Boole es un retıculo complementario y distributivo. Es decir, una terna(A,∨,∧), con A un conjunto y ∧,∨ : R × R −→ R dos operaciones binarias internastales que:

i) a ∧ a = a, a ∨ a = a (idempotente),

ii) a ∧ b = b ∧ a, a ∨ b = b ∨ a (conmutativa),

iii) (a ∧ b) ∧ c = a ∧ (b ∧ c), (a ∨ b) ∨ c = a ∨ (b ∨ c) (asociativa),

iv) a ∧ (b ∨ a) = a, a ∨ (b ∧ a) = a (absorcion),

v) existe 1 = maxA, 0 = minA (acotado),

vi) dado a, existe un unico a′ tal que a ∧ a′ = 0, a ∨ a′ = 1, (complem.),

vii) (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c), (a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c) (distributiva).

Otras propiedades (consecuencia de las anteriores):

viii) (a′)′ = a para todo a ∈ A (involutiva),

ix) (a ∨ b)′ = a′ ∧ b′ y (a ∧ b)′ = a′ ∨ b′ (leyes de Morgan)

33 / 59


Ejemplos de algebras de Boole

i) B1 = ({0, 1},≤) es el algebra de Boole mas sencilla (con dos elementos).

rr0

1 Si la consideramos en la forma ({0, 1},∧,∨) se tiene:1 ∧ 1 = 1, 0 ∧ 0 = 0, 1 ∧ 0 = 0 ∧ 1 = 0,1 ∨ 1 = 1, 0 ∨ 0 = 0, 0 ∨ 1 = 1 ∨ 0 = 1,

* No hay algebras de Boole con 3 elementos (el unico retıculo con 3 elementos no escomplementario).

ii) Con 4 elementos: (D6, |) ' (P(a, b),⊂) ' (B1 × B1,≤PROD) = B2

rr r

r

��

@@@��

@@@

1

2 3

6

rr r

r

��

@@@��

@@@

∅

{a} {b}

{a, b}

rr r

r

��

@@@��

@@@

(0, 0)

(0, 1) (1, 0)

(1, 1)

donde (x , y) ∧ (x ′, y ′) = (x ∧ x ′, y ∧ y ′) y (x , y) ∨ (x ′, y ′) = (x ∨ x ′, y ∨ y ′).

En general, el producto de algebras de Boole es un algebra de Boole. 34 / 59


Ejemplos de algebras de Boole

iii) B3 = (B1 × B1 × B1,≤PROD) es algebra de Boole definiendo

(x , y , z) ∧ (x ′, y ′, z ′) = (x ∧ x ′, y ∧ y ′, z ∧ z ′)

(x , y , z) ∨ (x ′, y ′, z ′) = (x ∧ x ′, y ∨ y ′, z ∨ z ′).

Habitualmente, denotaremos (x , y , z) = xyz , ∧ como · y ∨ como +. Con estanotacion, por ejemplo, 110 + 010 = 110, 110 · 010 = 010.

B3 ≡

rr rrr r r

r

000

100 010 001

110 101 011

111

��

@@@

��

@@@

��

@@@

��

@@@

' (D30, |) ' (P({a, b, c}),⊂)‖‖

(P({a, b, c}),∪,∩)

iv) En general, Bn = ({x1x2 . . . xn | xi ∈ {0, 1}},+, ·) es un algebra de Boole. ¿Cuantoselementos tiene? 2n.Bn ' (P({a1, a2, . . . , an},⊂) ' (Dn, |) n producto de primos distintos. 35 / 59


Algebras de Boole finitas

Teorema. Todo algebra de Boole finita es isomorfa a Bn para algun n ∈ N. Por tanto,el diagrama de Hasse de todo algebra de Boole es de tipo cubico y para toda algebra deBoole finita, existe n ∈ N tal que |A| = 2n.

¿Como se llega a este resultado?.Primero se ve que si A es un algebra de Boole finita, existe un conjunto finito C tal queA ' P(C ). (En concreto, C es el conjunto de los elementos minimales de A \ {0}).Luego se prueba que si C es un conjunto finito con n elementos, entonces las algebras deBoole P(C ) y Bn son isomorfas (B = {0, 1}).Si C = {c1, c2, . . . , cn}, el isomorfismo viene dado por

φ : P(C ) −→ Bn

{ci1 , ci2 , . . . , cik} 7−→ φ({ci1 , ci2 , . . . , cik}) = (b1, b2, . . . , bn)

donde bi = 1 si y solo si i ∈ {i1, i2, . . . in}.Ejercicio. Construye el isomorfismo entre P({a, b, c}) y B3.

36 / 59


Ejercicios de algebras de Boole

Ejercicio 21. Expresar la operacion conjuncion en funcion de la disyuncion y lacomplementaria. Expresar la disyuncion en funcion de la conjuncion y la complementaria.

Ejercicio 22. Demostrar que en un algebra de Boole se dan las siguientes propiedades:

a) a ≤ b ⇒ b′ ≤ a′.

b) a ≤ b ⇒ a ∨ (b ∧ c) = b ∧ (a ∨ b).

c) a ≤ b ≤ c ⇒ (a ∧ b) ∨ (a ∧ b ∧ c) ∨ (b ∧ c) ∨ (a ∧ c) = b.

d) a ≤ b ⇔ a ∧ b′ = 0⇔ a′ ∨ b = 1.

Ejercicio 23. Construir un isomorfismo entre (P(C ),⊂) y (Bn,≤n) para algun n ∈ N,donde C = {1, 2, 3, 4} y ≤n denota el orden producto en Bn.

Ejercicio 24. Sea (A,≤) un algebra de Boole. ¿Cuantos elementos minimales tieneA− {0}, si A es un algebra de Boole de 8 elementos? ¿Y si A tiene 16 elementos?

Ejercicio 25. ¿Existen algebras de Boole con infinitos elelmentos?37 / 59

Algebras de Boole Funciones booleanas

Funciones booleanas

Una funcion Booleana es una aplicacion f : A −→ C entre algebras de Boole finitas.Puesto que toda algebra de Boole finita es isomorfa a Bn para algun n, podemos definirfuncion boolena como toda aplicacion f : Bk −→ Bm.pause

Como toda funcion f : Bk −→ Bm tiene m componentes basta estudiar las funcionesbooleanas de la forma f : Bn −→ B .pause

La tabla de verdad de una funcionBooleana f : Bn −→ B es una tabladel tipo

x1 x2 . . . xn f (x1, x2, . . . , xn)0 0 . . . 0 f (0, 0, . . . , 0)0 0 . . . 1 f (0, 0, . . . , 1)...

......

...1 1 . . . 1 f (1, 1, . . . , 1)

donde se presentan todos los elementos de Bn y sus imagenes.38 / 59

Algebras de Boole Funciones booleanas

Funciones booleanas

Ejemplo. La siguiente tabla x1 x2 x3 f (x1, x2, x3)0 0 0 10 0 1 10 1 0 00 1 1 01 0 0 11 0 1 01 1 0 11 1 1 0

es la tabla de verdad de una funcion booleana f : B3 −→ B .

Ejemplo. Todas las posibles funciones booleanas de grado 2 se pueden representar enuna tabla de verdad conjunta. Existen 16 funciones booleanas de grado 2.

39 / 59

Algebras de Boole Expresiones booleanas

Expresiones booleanas

El concepto de expresion booleana en n variables x1, . . . , xn se define recursivamente:

i) Las variables x1, x2, . . . , xn son expresiones booleanas.

ii) Los sımbolos 0 y 1 son expresiones booleanas.

iii) Si E1 y E2 son expresiones booleanas, E1∨E2, E1∧E2 y E ′1 son expresiones booleanas.

iv) No hay mas expresiones booleanas que las obtenidas por las reglas anteriores.

Toda expresion booleana en n variables define una funcion booleana en m variables, paratodo m ≥ n. Se dice entonces que E (x1, . . . , xn) representa a f .

Ejemplo. La expresion booleana E (x , y) = x ∨ (x ′∧y) defineuna funcion booleana con la tabla de verdad de la derecha.

x y f (x , y)0 0 00 1 11 0 11 1 1

Dos expresiones booleanas son equivalentes si representan la misma funcion booleana.40 / 59


Expresiones booleanas

Dada una funcion booleana f de n variables se define S(f ) = {b ∈ Bn | f (b) = 1}.Teorema. Dada una funcion booleana f : Bn −→ B , existe una expresion booleana querepresenta a f .

Demostracion. Para cada b = (b1, b2, . . . , bn) ∈ S(f ) consideramos Eb = x∗1 ∧ x∗2 ∧· · · ∧ x∗n donde x∗i = xi si bi = 1 y x∗i = x ′i si bi = 0.Entonces E (f ) = ∨b∈S(f )Eb representa a f .

Ejemplo. Sea f definida por E (x , y) = x ∨ (x ′∧ y) tal que S(f ) = {(0, 1), (1, 0), (1, 1)}.Entonces E (x , y) = (x ′ ∧ y) ∨ (x ∧ y ′) ∨ (x ∧ y) representa f .

Observacion. A cada una de las expresiones Eb, b ∈ S(f ) se le llama producto elementaly a la expresion E (f ) = ∨b∈S(f )Eb se le denomina expresion asociada a f en forma desuma de productos elementales.

Observacion A partir de ahora denotaremos ∨ como + y ∧ como ·.Ası, por ejemplo, E (x , y) = x ∨ (x ′ ∧ y) la escribiremos como E (x , y) = x + x ′y .

41 / 59


Ejercicios de funciones booleanas

Ejercicio 26. Halla la tabla de verdad de la funcion f : B2 −→ B definida por la expresionE (x , y) = (x ∧ y ′) ∨ ((y ∧ (x ′ ∨ y)) ≡ xy ′ + (y(x ′ + y)).

Ejercicio 27. Determina todas las funciones booleanas binarias que cumplan: f (a′, b) =f (a, b′) = (f (a, b))′.

Ejercicio 28. Determina S(f ) para las funciones f : B3 −→ B definidas por:

a) f (x , y , z) = xy , b) f (x , y , z) = z ′, c) f (x , y , z) = xy + z ′.

Ejercicio 29. Haz operaciones para “reducir” las siguientes expresiones booleanas:

a) (x ′ + y)′ + y ′z b) (x ′y)′(x ′ + xyz ′) c) x(xy ′ + x ′y + y ′z)d) (x + y)′(xy ′)′ e) y(x + yz)′ f) (x + y ′z)(y + z ′).

Ejercicio 30. Dada la funcion booleana f : B4 −→ B

f (x , y , z , t) = xyzt + xy ′zt + xyzt ′ + xy ′zt ′ + x ′y ′z ′t ′ + x ′yz ′t ′ + x ′y ′z ′t + x ′yz ′t

utilizando las propiedades de un Algebra de Boole demuestra que f (x , y , z , t) = xz +x ′z ′.42 / 59

Algebras de Boole Simplificacion de expresiones booleanas

Simplificacion de expresiones booleanas

La expresion de una funcion booleana en forma de suma de productos elementales no esen general la mas simple de todas las expresiones equivalentes que la representan. Porejemplo E (x , y) = x y E (x , y) = xy + xy ′ son expresiones equivalentes. Los metodos desimplificacion que veremos se basan en la busqueda de pares de productos elementalesque difieran solamente en una variable, como ocurre en el ejemplo mencionado.

En concreto, los metodos de simplificacion que veremos se basan en el siguiente resultado.

Teorema. Si E es una expresion booleana en n variables y xn+1 es otra variable, entoncesla expresion E y la expresion E = (E∧xn+1)∨(E∧x ′n+1) son equivalentes como expresionesen n + 1 variables.

43 / 59

Algebras de Boole Metodo de los mapas de Karnaugh

Metodo de los mapas de Karnaugh

Para cada n = 2, 3, 4 consideramos una cuadrıcula de 2n cuadrados. Cada uno de ellosrepresenta un producto elemental, distribuidos de tal forma que dos productos elementalesson adyacentes si y solo si difieren unicamente en una variable. A efectos de adyacencia,los lados opuestos de la cuadrıcula se identifican. Estas cuadrıculas son

x ′x

y y ′

x ′x

z z ′ z ′ z

y y y ′ y ′ x ′

x ′x

x

t

t ′t ′t

z z ′ z ′ z

y y y ′ y ′

El mapa de Karnaugh de una expresion booleana E de n variables (n = 2, 3, 4) es unacuadrıcula como las anteriores en la que se han sombreado los cuadrados correspondientesa los productos que aparecen en una expresion equivalente de E en forma de suma deproductos elementales.

44 / 59



En el mapa de Karnaugh de una expresion booleana de n variables (n = 2, 3, 4), se llamanrectangulos simples a los correspondientes a las expresiones xi y x ′i , i ∈ {1, 2, . . . , n} y asus intersecciones k a k (k = 2, . . . , n).

Ejemplo. Para n = 2, los rectangulos simples son, los correspondientes a las expresionesx , x ′, y e y ′,

x ′x

y y ′

��

x ′x

y y ′

��

x ′x

y y ′

��

x ′x

y y ′

��

y los correspondientes a las intersecciones dos a dos de estos, es decir, los correspondientesa los productos xy , xy ′, x ′y , x ′y ′:

x ′x

y y ′

x ′x

y y ′

x ′x

y y ′

x ′x

y y ′

��

��

��

��

45 / 59



Metodo de simplificacion de los mapas de Karnaugh. Consiste en lo siguiente:

i) Representamos el mapa de Karnaugh de E .

ii) Consideramos todos los rectangulos simples, de tamano lo mayor posible, que recubranla zona sombreada del mapa de Karnaugh, aunque se solapen.

iii) Eliminamos los rectangulos simples que esten contenidos en la union de otros deforma que la zona sombreada quede recubierta por el menor numero de rectangulosdel mayor tamano posible.

iv) La union de las expresiones que quedan al final del proceso es una expresion

simplificada de la expresion original. Esta dependera de las elecciones hechas enel proceso.

46 / 59



Ejemplo. Si el mapa de Karnaugh de E es

x ′x ′xx

tt ′t ′t

z z ′ z ′ z

y y y ′ y ′

��

=��

∨��

∨

��

entonces E = x ′ ∧ y ∧ t ′ ∨ x ′ ∧ y ∧ z ′ ∨ x ′ ∧ y ′ ∧ t.

47 / 59



Por otra parte tambien se puede descomponer

x ′x ′xx

tt ′t ′t

z z ′ z ′ z

y y y ′ y ′

��

=��

∨

��

∨

��

y por tanto E = x ′ ∧ y ∧ t ′ ∨ x ′ ∧ z ′ ∧ t ∨ x ′ ∧ y ′ ∧ t.

Pero es incorrecto descomponer

x ′x ′xx

tt ′t ′t

z z ′ z ′ z

y y y ′ y ′

��

=��

∨

��

∨

��

puesto que los rectangulos simples de la descomposicion han de ser lo mayor posible.48 / 59



El metodo de los mapas de Karnaugh se puede utilizar tambien para simplificar funcionesque no esten definidas en todo Bn.

Ejemplo. Sea A = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001} elconjunto de numeros del 0 al 9 en notacion binaria y sea f : A −→ B tal quef (xyzt) = 0⇔ xyzt representa un numero menor que 5.

Entonces en el mapa de Karnaugh de f rayamos los puntos en que la funcion vale 1,marcamos con 0 los puntos en los que vale 0 (en el resto de los puntos puede tomarcualquier valor pues no son entradas de la funcion):

x ′x ′xx

tt ′t ′t

z z ′ z ′ z

y y y ′ y ′

��

��

0 0 00 0

=��

��

��

��

��

��

��

�� =

��

��

∨��

∨��

��

��

��

��

��

��

Por tanto E = x ∨ (y ∧ t) ∨ (y ∧ z).49 / 59


Ejercicios de mapas de Karnaugh

Ejercicio 31. Dados los siguientes mapas de Karnaugh, escribe las expresiones booleanasque definen estos mapas:

x ′

x

z ′ z z z ′

y y y ′ y ′

0 0 1 0

1 1 1 0 x ′

x

z ′ z z z ′

y y y ′ y ′

1 1 1 0

1 0 1 0 x ′

x

z ′ z z z ′

y y y ′ y ′

0 0 1 1

1 0 0 1

x ′

x ′

x

x

t ′

t

t

t ′

y y y ′ y ′

z ′ z z z ′

1 0 1 1

0 1 1 0

0 1 1 0

1 0 0 1 x ′

x ′

x

x

t ′

t

t

t ′

y y y ′ y ′

z ′ z z z ′

1 0 1 1

1 1 1 1

0 1 0 0

0 0 0 0 x ′

x ′

x

x

t ′

t

t

t ′

y y y ′ y ′

z ′ z z z ′

0 0 1 1

0 0 1 1

1 0 1 1

0 0 1 0

ppppp

50 / 59


Ejercicios de mapas de Karnaugh

Ejercicio 32. Se consideran los conjuntosa) S(f ) = {(1, 1, 0, 0), (1, 1, 1, 1), (1, 0, 1, 1), (1, 0, 0, 0), (0, 0, 0, 1), (0, 1, 0, 0), (0, 0, 0, 0), (0, 1, 0, 1)}b) S(f ) = {(0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 1), (0, 1, 1, 0), (1, 1, 0, 0), (1, 1, 1, 1), (1, 0, 1, 0)}Simplifica la expresion booleana de la funcion f que toma valor 1 en el conjunto S(f ) ycero en el resto, mediante mapas de Karnaugh.

Ejercicio 33. Completa los huecos de la tabla de la derecha,teniendo en cuenta que la expresion que se desea obtener ha deser lo mas sencilla posible. Determina esa expresion y dibujael mapa de Karnaugh correspondiente.

Ejercicio 34. Encuentra la expresion mas sencilla que detecteen {0, 1, 2, 3, . . . , 15} los numeros del conjunto:a) A = {multiplos de dos},b) B = {multiplos de tres},c) C = {multiplos de cuatro}

x y y f1(x , y)0 0 0 10 0 1 00 1 0 10 1 1 11 0 01 0 11 1 0 11 1 1

51 / 59

Algebras de Boole Metodo de Quine-McCluskey

Metodo de Quine-McCluskey

Funciona agrupando sistematicamente productos que difieren en una variable, a partir delos elementos de s(f ), como sigue:

i) Se ordenan los elementos de s(f ) por bloques en orden decreciente segun el numerode unos.

ii) Se compara cada elemento de cada bloque con los del bloque inmediatamente inferiorde la forma siguiente: Si dos elementos difieren en un solo termino, se marcan amboselementos, y se pone en una nueva lista el elemento obtenido al sustituir el terminorepetido por un guion.

iii) Se repite el paso ii) con la nueva lista y se continua este proceso.iv) Cuando ya no se pueda continuar:

a) Se consideran todos los elementos no marcados de todas las listas,b) para cada b ∈ Bn con f (b) = 1 se elige un elemento no marcado:

- Primero elegimos aquellos para los que existe una unica posibilidad,- para los restantes se elige la menor cantidad posible de entre aquellos con mayor cantidad de

guiones.

v) La expresion booleana formada por la disyuncion de las expresiones correspondientesa estos elementos es una expresion simplificada.

52 / 59



Ejemplo. Hallar una expresion booleanasimplificada de la funcion booleana cuya tabla deverdad es:

x y z t E (x , y , z , t)0 0 0 0 10 0 0 1 10 0 1 0 00 0 1 1 00 1 0 0 10 1 0 1 00 1 1 0 10 1 1 1 01 0 0 0 11 0 0 1 11 0 1 0 01 0 1 1 01 1 0 0 11 1 0 1 01 1 1 0 11 1 1 1 0

53 / 59



En este caso tenemos 1110 *1100 *1001 *0110 *0001 *0100 *1000 *0000 *

11-0 *-110 *-100 *1-00 *-001 *100- *01-0 *000- *0-00 *-000 *

-1-0-00-- -00

A continuacion consideramos la siguiente tabla

1110 1100 1001 0110 0001 0100 1000 0000-1-0 * * * *-00- * * * *- -00 * * * *

Luego la expresion buscada es E (x , y , z , t) = (y ∧ t ′) ∨ (y ′ ∧ z ′). 54 / 59



En casa paso NO basta con tomar aquellossumandos que basten para tapar los del pasoprecedente. Por ejemplo, para

x y z t E (x , y , z , t)0 0 0 0 10 0 0 1 00 0 1 0 00 0 1 1 00 1 0 0 10 1 0 1 10 1 1 0 00 1 1 1 11 0 0 0 01 0 0 1 01 0 1 0 01 0 1 1 01 1 0 0 11 1 0 1 01 1 1 0 01 1 1 1 0

55 / 59



En este caso si en la primera simplificacion solotomamos el menor numero de sumandos quecubren los iniciales tendrıamos

0111 *1100 *0110 *0101 *0100 *0000 *

011-01-1-1000-00

que da lugar a la siguiente tabla

0111 1100 0110 0101 0100 0000011- * *01-1 * *-100 * *0-00 * *

con lo que se tendrıa que E (x , y , z , t) = (x ′∧y∧z)∨(x ′∧y∧t)∨(x ′∧z ′∧t ′)∨(y∧z ′∧t ′).56 / 59



Sin embargo, si lo hacemoscomparando todos con todos,incluso los ya cubiertos, tenemos

0111 *1100 *0110 *0101 *0100 *0000 *

011- *01-1 *-10001-0 *010- *0-00

01- -

que da lugar a la siguiente tabla

0111 1100 0110 0101 0100 0000-100 * *0-00 * *01- - * * * *

Luego la expresion buscada es E (x , y , z , t) = (x ′ ∧ y) ∨ (x ′ ∧ z ′ ∧ t ′) ∨ (y ∧ z ′ ∧ t ′).

Ejercicio 35. Utilizando el algoritmo de Quine-McCluskey halla la expresion booleanaminima de la funcion f : B5 −→ B tal que

S(f ) = {(1, 1, 1, 1, 1), (1, 1, 1, 0, 1), (1, 1, 0, 1, 1), (1, 0, 1, 1, 1), (1, 0, 1, 0, 1), (1, 0, 0, 1, 1),

(1, 1, 0, 0, 1), (1, 0, 0, 0, 1)}. 57 / 59

Algebras de Boole Ejercicios de diseno y simplificacion de expresiones booleanas

Ejercicios de diseno y simplificacion de expresiones booleanas

Ejercicio 36. Define una expresion booleana que compare, segun el orden≤, dos numerosdel conjunto {0, 1, 2, 3} y simplifıcala.

Ejercicio 37. Se considera un ascensor dotado de un dispositivo de seguridad, para queno puedan viajar ninos pequenos solos ni pesos excesivos. Queremos que el ascensor seponga en marcha cuando este vacıo o con pesos entre 25 y 300 kilos. Dotamos al ascensorde tres sensores: A sensible a cualquier peso, B sensible a pesos mayores de 25 kilos y Csensible a pesos superiores a 300 kilos. Disena el circuito mas sencillo posible que cumpladichas condiciones.

Ejercicio 39. Para evitar errores de transmision en ciertos mensajes codificados, esfrecuente anadir un bit, llamado de control, a un bloque de bits. Ası , por ejemplo, enla representacion de cifras decimales mediante un codigo binario, 0 se representa como00001, 1 se representa como 00010, 2 se representa como 00100, 3 se representa como00111. El bit de paridad vale 1 si el numero de unos del bloque es par y vale 0 en casocontrario. Define una expresion c que verifique lo anterior para los dıgitos del 0 al 9 demanera que sea lo mas simplificada posible en la forma suma de productos. 58 / 59

Algebras de Boole Ejercicios de diseno y simplificacion de expresiones booleanas

Ejercicios de simplificacion de expresiones booleanasEjercicio 40. La aparicion de una cifra decimal en el visor de unacalculadora se produce mediante un circuito con cuatro entradas, quese corresponden con el codigo binario del dıgito y siete salidas fi / i= 1..7, que se presentan como pequenos segmentos, iluminados o noen el visor, segun el siguiente esquema: (f1 es el segmento superior,f2, . . . f6 son los restantes segmentos exteriores numerados en el sentidode las agujas del reloj, y f7 es el segmento central.

a) Traza la tabla de verdad de cada una de las funciones booleanasfi : B4 −→ B que represente este fenomeno binario.

b) Encuentra expresiones mınimas en forma de suma de productospara f1 y f2.

f1

f2

f3

f4

f5

f6f7

59 / 59

conjuntos - upm · 1)r(x 2;y 2) ,x 1y 1 = x 2y 2. comprueba que es de equivalencia y calcula el...

Documents