• Author / Uploaded
• kast46_05

Citation preview

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 P 1. Dado el alfabeto = {brazo, antebrazo, ante, a, sala, ala, la, antesala} P+ , se define como el conjunto P de todas las secuencias finitas P+ que se pueden formar con elementos de , por ejemplo: brazosala ∈ P+ P+ P+ P+ ,lalalalala ∈ , antesala ∈ , a ∈ . Sea v una relación en definida por u v v ⇐⇒todos los caracteres de u aparecen consecutivos en v , por ejemplo aaabrazolalala v lalalalaaaaaaaaaaaabrazolalalalalalasala P P+ , brazo v antebrazo. Observe que ⊆ . P+ (a) (2 puntos) Demostrar que ( , v) es un conjunto parcialmente ordenado. (b) (1 puntos) ¿Es v un orden total?. (c) (2 puntos) Dibuja el diagrama P de Hasse de la relación de orden parcial v restringida al conjunto . (d) (3 puntos) Dado el conjunto B = { a, ala, ante }determine los elemntos maximales, elementos minimales, el máximo, el mínimo, el supremo 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, demostrar que a ≤ b ⇔ b0 ≤ a0 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 Q (a) (2 puntos) f (x, y, z) = M (0, 1, 4, 5) P (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 dos de las variables booleanas tienen el valor 1. Escriba su polinomio booleano correspondiente en el conjunto funcionalmente completo { N AN D }

1