estructuras discretas i cs 3 2 examen
TRANSCRIPT
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