Soluciones Ejercicios Capítulo 12.1 Matemáticas Discretas Johnsonbaugh 6 ed

En los ejercicios 1 al 5, dibuje el diagrama de transición de la máquina de estado finito (I, O, S, f, g, σ0).











En los ejercicios 6 al 10, encuentre los conjuntos I, O y S, el estado inicial y la tabla que define el siguiente estado y las funciones de salida para cada máquina de estado finito.















En los ejercicios 11 al 20, encuentre la cadena de salida para la cadena de entrada que se indica y la máquina de estado finito.
 11. abba; ejercicio 1

12. abba; ejercicio 2

13. aabbaba; ejercicio 3

14. aabbcc; ejercicio 4

15. aabaab; ejercicio 5

16. aaa; ejercicio 6

17. aabbabaab; ejercicio 7

18. baaba; ejercicio 8

19. bbababbabaaa; ejercicio 9

20. cacbccbaabac; ejercicio 10

En los ejercicios 21 al 26, diseñe una máquina de estado finito que tenga las propiedades indicadas. La entrada siempre es una cadena de bits.


21. Produce 1 si entra un número par de unos; de otra manera produce 0.

 22. Produce 1 si entran k unos, donde k es un múltiplo de 3; de otra manera produce 0.

23. Produce 1 si entran dos unos o más; de otra manera produce 0.


24. Produce 1 cuando ve 101; de otra manera produce 0.

25. Produce 1 cuando ve 101 y en adelante; de otra manera produce 0.

26. Produce 1 cuando ve primero 0 y hasta que ve otro 0; en adelante, produce 0; en el resto de los casos produce 0.

27. Sea α =x1 · · ·xn una cadena de bits. Sea β =y1 · · ·yn, donde







para i=1, . . . , n. Sea . Demuestre que si γ alimenta a la máquina de estado finito de la figura 12.1.4, la salida es el complemento de 2 de α (considere el algoritmo 11.5.16 una descripción del complemento de 2).


28. Demuestre que no existe una máquina de estado finito que reciba una cadena de bits y produzca 1 siempre que el número de unos sea igual al número de ceros en la entrada, y produzca 0 de otra manera.

29. Demuestre que no hay una máquina de estado finito que realice la multiplicación en serie. En particular, demuestre que no hay una máquina de estado finito que alimenta números binarios



Ejemplo: Si existe tal máquina, para multiplicar 101 ×1001 se alimentaría 11,00,10,01,00,00,00,00. El primer par 11 es el par de los bits en la extrema derecha (101, 1001); el segundo par 00 es el siguiente par de bits (101, 1001); y así sucesivamente. Se amortigua la cadena de entrada con cuatro pares 00 —la longitud del número más grande 1001 que debe multiplicarse—. Como 101 ×1001 =101101, se asevera que se obtiene la salida mostrada en la tabla adyacente.



 
 
Etiquetas: , , ,

Soluciones Ejercicios Capítulo 11.5 Matemáticas Discretas Johnsonbaugh 6 ed

1. Demuestre que el conjunto de compuertas {OR, NOT} es funcionalmente completo. Demuestre que cada conjunto de compuertas en los ejercicios 2 al 5 no es funcionalmente completo.

2. {AND}

3. {OR}
 

4. {NOT}

5. {AND, OR}

6. Dibuje un circuito con sólo compuertas NAND que calcule xy.


7. Escriba xy usando sólo ↑.
 
 

 
 
Escriba expresiones booleanas para describir los circuitos de salidas múltiples en los ejercicios 9 al 11.







12. Diseñe circuitos usando sólo compuertas NAND para calcular las funciones de los ejercicios 1 al 10, sección 11.4.

13. ¿Puede reducir el número de compuertas NAND incluidas en cualquiera de los circuitos del ejercicio 12?


14. Diseñe circuitos que usen el menor número de compuertas AND, OR y NOT tanto como sea posible para calcular las funciones de los ejercicios 1 al 10, sección 11.4.


15. Diseñe un circuito medio sumador usando sólo compuertas NAND.


16. Diseñe un circuito medio sumador usando cinco compuertas NAND. Una compuerta NOR recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada por x1 ↓x2, donde


17. Escriba xy, x∨y, x y x ↑ y en términos de ↓.

18. Escriba x↓y en términos de ↑.

19. Escriba la tabla lógica para la función nor.


20. Demuestre que el conjunto de compuertas {NOR} es funcionalmente completo.


21. Diseñe circuitos usando sólo compuertas NOR para calcular las funciones de los ejercicios 1 al 10, sección 11.4.


22. ¿Puede reducir el número de compuertas NOR empleadas en cualquiera de sus circuitos para el ejercicio 21?


23. Diseñe un circuito medio sumador con sólo compuertas NOR.


24. Diseñe un circuito medio sumador con cinco compuertas NOR.


25. Diseñe un circuito con tres entradas que produce 1 justo cuando dos o tres entradas tienen valor 1.

26. Diseñe un circuito que multiplique los números binarios x2 x1 y y2 y1. La salida será de la forma z4 z3 z2 z1.


27. Un módulo de 2 es un circuito que acepta como entrada dos bits b y FLAGIN y produce bits c y FLAGOUT. Si FLAGIN = 1, entonces c=b y FLAGOUT =1. Si FLAGIN =0 y b=1, entonces FLAGOUT = 1. Si FLAGIN = 0 y b = 0, entonces FLAGOUT = 0. Si FLAGIN =0, entonces c=b. Diseñe un circuito para implementar el módulo de 2.
El complemento de 2 de un número binario se calcula utilizando el siguiente algoritmo.



Encuentre el complemento de 2 de los números en los ejercicios 28 al 30 usando el algoritmo 11.15.16.


28. 101100


29. 11011

30. 011010110

31. Utilizando módulos de 2, diseñe un circuito que calcule el complemento de 2 y3 y2 y1 del número binario de tres bits x3 x2 x1.


32. Sea *un operador binario en un conjunto S que contiene 0 y 1. Escriba un conjunto de axiomas para *, modelado tomando en cuenta las reglas que satisface NAND, de manera que si se define

entonces (S,∨,∧, , 0, 1) (S,∨,∧, , 0, 1) es un álgebra booleana.

33. Sea * un operador binario en S que contiene 0 y 1. Escriba un conjunto de axiomas para *, modelado tomando en cuenta las reglas que satisface NOR, y las definiciones de –, ∨ y ∧ de manera que sea un álgebra booleana.


34. Demuestre que {→} es funcionalmente completo (vea la definición 1.2.3).


35. Sea B(x, y) una expresión booleana en las variables x y y que sólo usa el operador ↔(vea la definición 1.2.8). a) Demuestre que si B contiene un número par de x, los valores de B( x , y) y B(x, y) son iguales para toda x y y. b) Demuestre que si B contiene un número impar de x, los valores de B( x , y) y B ( x . y ) son iguales para toda x y y. c) Utilice los incisos a) y b) para demostrar que {↔} no es funcionalmente completo. Paul Pluznikov contribuyó con este ejercicio.


Etiquetas: , , ,

Soluciones Ejercicios Capítulo 11.4 Matemáticas Discretas Johnsonbaugh 6 ed

En los ejercicios 1 al 10. encuentre la forma normal disyuntiva de cada función y dibuje el circuito combinatorio correspondiente a esa forma normal disyuntiva.



























 
 
 

 







En los ejercicios 11 al 20, encuentre la forma disyuntiva normal de cada función usando las técnicas algebraicas. (a∧b se abrevia ab.)





22. ¿Cuántos elementos tiene F?

23. Demuestre que es un álgebra booleana.


24. Trabajando con el dual en el procedimiento del ejemplo 11.4.4, explique cómo se encuentra la forma conjuntiva normal de una función booleana de Z2 n en Z2.


25. Encuentre la forma conjuntiva normal de cada función en los ejercicios 1 al 10.

26. Usando métodos algebraicos, encuentre la forma conjuntiva normal de cada función en los ejercicios 11 al 20.


27. Demuestre que si m1 ∨···∨mk es la forma disyuntiva normal de


28. Con el método del ejercicio 27, encuentre la forma conjuntiva normal de f para cada función f de los ejercicios 1 al 10.

29. Demuestre que la forma disyuntiva normal (11.4.5) es única; es decir, demuestre que si se tiene una función booleana f(x1, ..., xn) =m1 ∨···∨mk =m '1 ∨···∨m 'j
donde cada mi, mi' es un mintérmino, entonces k=j y los subíndices en las m'i se pueden permutar de manera que mi =m'i para i=1, . . . , k.


Etiquetas: , , ,

Soluciones Ejercicios Capítulo 11.3 Matemáticas Discretas Johnsonbaugh 6 ed

1. Verifique las propiedades a' ) a c' ) del ejemplo 11.3.3.


2. Sea S={1, 2, 3, 6}. Defina
x+y=mcm(x, y),        x·y=mcd(x, y),     x'=6/x


para x, y ∈ S (mcm denota el mínimo común múltiplo y mcd el máximo común divisor). Demuestre que es un álgebra booleana.

3. S={1, 2, 4, 8}. Defina +y ·como en el ejercicio 2 y defina x' =8/x. Demuestre que (S,+,.,´,1,8) no es un álgebra booleana.
Sea Sn ={1, 2, . . . , n}. Defina x+y=máx{x, y}, x·y=mín{x, y}.

4. Demuestre que los incisos a) a c) de la definición 11.3.1 se cumplen para Sn.


5. Demuestre que es posible definir 0, 1 y' de manera que (Sn,´,.,',0,1) es un álgebra booleana si y sólo si n=2.


6. Rescriba las condiciones del Teorema 11.3.6 para conjuntos como los del ejemplo 11.3.3.


7. Interprete el Teorema 11.3.6 para conjuntos como los del ejemplo 11.3.3.


Escriba el dual de cada afirmación en los ejercicios 8 al 14.

8. Si y , entonces y=z. 11. xy =0 si y sólo si xy=x.


9. (x´+y´)´=xy
 

10. Si x+y=x+z y x'+y=x'+z , entonces y=z

11. xy =0 si y sólo si xy=x.

12. Si x+y=0, entonces x=0=y


13. x=0 si y sólo si para toda y=xy'+x'y para toda y


14.  x+x(y+1)=x


15. Pruebe la afirmación del ejercicio 8 al 14.


16. Pruebe los duales de las afirmaciones de los ejercicios 8 al 14.


17. Escriba el dual del Teorema 11.3.4. ¿Cómo se relaciona el dual con el Teorema 11.3.4 en sí?


18. Pruebe las segundas afirmaciones de los incisos a), c) y f) del Teorema 11.3.6.


19. Pruebe las segundas afirmaciones de los incisos a), c) y f) del Teorema 11.3.6 obteniendo el dual de las demostraciones de las primeras afirmaciones.


20. Pruebe el Teorema 11.3.6, incisos d) y e).


21. Deduzca el inciso a) de la definición 11.3.1 a partir de los incisos b) a e) de la definición 11.3.1.


22. Sea U el conjunto de enteros positivos. Sea S la colección de subconjuntos X de U con uno de X o X finito. Demuestre que es un álgebra booleana.


23. Sea n un entero positivo. Sea S el conjunto de todos los divisores de n, incluyendo 1 y n. Defina +y ·como en el ejercicio 2 y defina x = n/x. ¿Qué condición debe satisfacer n para que sea un álgebra booleana?


24. Demuestre que las leyes asociativas se deducen de las otras leyes de la definición 11.3.1.


Etiquetas: , , ,

Soluciones Ejercicios Capítulo 11.2 Matemáticas Discretas Johnsonbaugh 6 ed

Demuestre que los circuitos combinatorios de los ejercicios 1 al 5 son equivalentes.

 
 

 
 



 
 
 

 




Verifique las ecuaciones en los ejercicios 6 al 10.











Pruebe o desapruebe las ecuaciones en los ejercicios 11 al 15













16. Pruebe la segunda afirmación del Teorema 11.2.1c).

17. Pruebe los incisos a), b) y e) del Teorema 11.2.1. Se dice que dos circuitos de conmutación son equivalentes si las expresiones booleanas que los representan son iguales.

18. Demuestre que los circuitos de conmutación son equivalentes.


19. Para cada circuito de conmutación en los ejercicios 25 al 29 de la sección 11.1, encuentre un circuito de conmutación equivalente usando circuitos en paralelo y en serie que tengan el menor número posible de interruptores.



20. Para cada expresión booleana en los ejercicios 30 al 34 de la sección 11.1, encuentre un circuito de conmutación usando circuitos paralelos y en serie con el menor número posible de interruptores. Un circuito puente es un circuito de conmutación, como el que se ilustra en seguida, que usa circuitos no paralelos y no en serie.


 
Para cada circuito de conmutación, encuentre un circuito de conmutación equivalente usando circuitos puente que tengan el menor número de interruptores.









24. Para cada expresión booleana en los ejercicios 30 al 34 de la sección 11.1, encuentre un circuito de conmutación usando circuitos puente con el menor número posible de interruptores.


Etiquetas: , , ,
Suscribirse a: Comentarios (Atom)