Estructuras Discretas I CS 3 2 Examen
2
E.P. de Ciencia de la Computación de la UNSA Examen # 3 de Estructuras Discretas I Lic. Wilber Ramos Lov ón July 21, 2015 1. Dado el al fabeto = {brazo, antebrazo, ante, a, sala, ala, la, antesala} , se define + como el conjunto de todas las secuencias finitas que se pueden formar con elementos de , por ejemplo: brazosala ∈ + ,lalalalala ∈ + , antesala ∈ + , a ∈ + . Sea una relación en + definida por u v ⇐ ⇒todos los caracteres de u aparecen consecutivos en v , por ejemplo aaabrazolalala lalalalaaaaaaaaaaaabrazolalalalalalasala , brazo antebrazo. Observe que ⊆ + . (a) (2 punto s) Demostr ar que ( + , ) es un conjunto parcialmente or- denado. (b) (1 puntos) ¿Es un orden total?. (c) (2 puntos) Dibuja el diagrama de Hass e de la relación de orden parcial restringida al conjunto . (d) (3 puntos) Dado el conjunto B = { a, ala, ante }determine los el- emntos maximales, elementos minimales, el máximo, el mínimo, el supremo e infimo de B . 2. (2 puntos ) Simpli fique la sigui ente expresión booleana yz + wx + z + wz (xy + wz ) 3. (3 puntos) Para cualesquiera a, b elementos de un álgebra booleana, de- mostrar que a ≤ b ⇔ b ≤ a 4. Para cada una de las siguientes funciones booleanas, dibuje una red de compuertas de dos niveles como una suma minimal de productos o como un producto minimal de sumas (a) (2 punt os) f (x,y,z ) = M (0, 1, 4, 5) (b) (2 puntos) f (w,x,y,z ) = m(0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 13) 5. (3 punt os) Dada la func ión booleana f (x, y) = 1 si sólo si exactamente dos de las variables booleanas tienen el valor 1. Escriba su polinomio booleano correspondiente en el conjunto funcionalmente completo { NAND } 1
Transcript of Estructuras Discretas I CS 3 2 Examen
7/25/2019 Estructuras Discretas I CS 3 2 Examen
http://slidepdf.com/reader/full/estructuras-discretas-i-cs-3-2-examen 1/1
E.P. de Ciencia de la Computación de la UNSA
Examen # 3 de Estructuras Discretas I
Lic. Wilber Ramos Lovón
July 21, 2015
1. Dado el alfabeto
= {brazo, antebrazo, ante, a, sala, ala, la, antesala}
, se define +
como el conjunto de todas las secuencias finitas que sepueden formar con elementos de
, por ejemplo: brazosala ∈+
,lalalalala ∈+, antesala ∈
+, a ∈
+. Sea una relación en
+definida
por u v ⇐⇒todos los caracteres de u aparecen consecutivos en v ,por ejemplo aaabrazolalala lalalalaaaaaaaaaaaabrazolalalalalalasala
, brazo antebrazo. Observe que⊆+.
(a) (2 puntos) Demostrar que (+
, ) es un conjunto parcialmente or-denado.
(b) (1 puntos) ¿Es un orden total?.
(c) (2 puntos) Dibuja el diagrama de Hasse de la relación de orden parcial restringida al conjunto
.
(d) (3 puntos) Dado el conjunto B = {a, ala, ante }determine los el-emntos maximales, elementos minimales, el máximo, el mínimo, elsupremo e infimo de B .
2. (2 puntos) Simplifique la siguiente expresión booleana
yz + wx + z + wz (xy + wz)
3. (3 puntos) Para cualesquiera a, b elementos de un álgebra booleana, de-mostrar que a ≤ b ⇔ b ≤ a
4. Para cada una de las siguientes funciones booleanas, dibuje una red decompuertas de dos niveles como una suma minimal de productos o comoun producto minimal de sumas
(a) (2 puntos) f (x, y , z) =
M (0, 1, 4, 5)
(b) (2 puntos) f (w , x, y , z) =
m(0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 13)
5. (3 puntos) Dada la función booleana f (x, y) = 1 si sólo si exactamente dosde las variables booleanas tienen el valor 1. Escriba su polinomio booleanocorrespondiente en el conjunto funcionalmente completo {NAND }
1
