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