Use the following to answer questions 1-8:
Use the following to answer questions 1-8:
In the questions below fill in the blanks.
1. The idempotent laws in a Boolean algebra state that ________ and ________.
Ans: x + x ’ x, x ⋅ x ’ x.
2. There are ________ Boolean functions with 2 variables.
Ans: 24.
3. There are ________ Boolean functions with 3 variables.
Ans: 28.
4. There are ________ Boolean functions with 4 variables.
Ans: 216.
5. Using “↓” for “nor”, (x ↓ y) ↓ (x ↓ y) can be written in terms of ¬, ∨, and ∧ as ________.
Ans: x + y.
6. Using “↓” for “nor”, (x ↓ x) ↓ (y ↓ y) can be written in terms of ¬, ∨, and ∧ as ________.
Ans: xy.
7. When written as a sum of minterms (in the variables x and y), [pic] ________.
Ans: [pic].
8. When written as a product of maxterms (in the variables x and y), (x + y)z ’ ________.
Ans: [pic].
Use the following to answer questions 9-22:
In the questions below mark each statement TRUE or FALSE.
9. When written as a sum of minterms in the variables x and y, [pic].
Ans: True
10. When written as a sum of minterms in the variables x and y, [pic].
Ans: True
11. If f (z,y,z) ’ xyz, then [pic].
Ans: False
12. xxx + xy + yy ’ xy.
Ans: False
13. Every Boolean function can be written using only the operators[pic] , +, and ⋅ .
Ans: True
14. There are n2 minterms in the variables x1,x2,…,xn.
Ans: False
15. [pic].
Ans: True
16. [pic].
Ans: True
17. [pic].
Ans: True
18. [pic].
Ans: True
19. [pic].
Ans: False
20. {+, ⋅} is a functionally complete set of operators.
Ans: False
21. The circuit diagrams for [pic] and [pic] produce the same output.
Ans: True
22. The circuit diagrams for [pic] and x + y produce the same output.
Ans: False
23. Write x + y as a sum-of-products in the variables x and y.
Ans: [pic].
24. Write x(y + 1) as a sum-of-products in the variables x and y.
Ans: [pic].
25. Write [pic] as a sum-of-products in the variables x and y.
Ans: [pic].
26. Write 1 as a sum-of-products in the variables x and y.
Ans: [pic].
27. Write x + y + z as a sum-of-products in the variables x, y, and z.
Ans: [pic].
28. Write [pic] as a sum-of-products in the variables x, y, and z.
Ans: [pic].
29. Write [pic] as a sum-of-products in the variables x, y, and z.
Ans: [pic].
30. Write x + z as a sum-of-products in the variables x, y, and z.
Ans: [pic].
31. Write [pic] as a sum-of-products in the variables x, y, and z.
Ans: [pic].
32. Find the sum-of-products expansion of the Boolean function f(x,y) that is 1 if and only if either x ’ 0 and y ’ 1, or x ’ 1 and y ’ 0.
Ans: [pic].
33. Find the sum-of-products expansion of the Boolean function f(x,y,z) that is 1 if and only if exactly two of the three variables have value 1.
Ans: [pic].
34. Find the sum-of-products expansion of the Boolean function f(x,y,z) that is 1 if and only if either x ’ z ’ 1 and y ’ 0, or x ’ 0 and y ’ z ’ 1.
Ans: [pic].
35. Find a Boolean function F : {0,1}2 → {0,1} such that F(0,0) ’ F(0,1) ’ F(1,1) ’ 1 and F(1,0) ’ 0.
Ans: [pic].
36. (a) Find a Boolean function f : {0,1}3 → {0,1} such that f (1,1,0) ’ 1, f (0,1,1) ’ 1, and f (x,y,z) ’ 0 otherwise.
(b) Write f using only ⋅ and [pic]
Ans: (a) [pic] (b) [pic].
37. If [pic], find f (1,1,1,1).
Ans: 1.
38. If [pic], find f (0,1,0,1).
Ans: 1.
39. If [pic], find f (1,0,1,1).
Ans: 0.
40. If [pic], find f (0,0,0,0).
Ans: 0.
41. If [pic], find f (1,1,0,0).
Ans: 0.
42. If [pic], find f (0,0,1,0).
Ans: 0.
43. Prove that F ’ G, where [pic] and [pic].
Ans: [pic]
44. Show that the Boolean function F given by [pic] simplifies to [pic], by using only the definition of a Boolean algebra.
Ans: [pic].
45. Show that the Boolean function F given by [pic] simplifies to [pic], by using only the definition of a Boolean algebra.
Ans: [pic]
46. Using only the five properties associative laws, commutative laws, distributive laws, identity laws, and complement laws, prove that xx ’ x is true in all Boolean algebras.
Ans: [pic].
47. Using only the five properties associative laws, commutative laws, distributive laws, identity laws, and complement laws, prove that x + x ’ x is true in all Boolean algebras.
Ans: [pic].
48. Using only the five properties associative laws, commutative laws, distributive laws, identity laws, and complement laws, prove that x + (xy) ’ x is true in all Boolean algebras.
Ans: [pic] [∗using idempotent law].
49. Using only the five properties associative laws, commutative laws, distributive laws, identity laws, and complement laws, prove that x + 1 ’ 1 is true in all Boolean algebras.
Ans: [pic].
Use the following to answer questions 50-61:
In the questions below determine whether the statement is TRUE or FALSE. Assume that x, y, and z represent Boolean variables.
50. x + xyz ’ x.
Ans: True
51. x + xy + x ’ x.
Ans: True
52. [pic].
Ans: False
53. x(x + y) ’ x + yx.
Ans: True
54. [pic].
Ans: True
55. x + y + z ’ xyz.
Ans: False
56. [pic].
Ans: True
57. (xx + 1) ’ (x + 1)(x + 1).
Ans: True
58. [pic].
Ans: False
59. [pic].
Ans: True
60. [pic].
Ans: True
61. (0 + x)(1 + x) ’ xx.
Ans: True
62. Prove that the set of real numbers, with addition and multiplication of real numbers as + and ⋅, negation as complementation, and the real numbers 0 and 1 as the 0 and the 1 respectively, is not a Boolean algebra.
Ans: The following laws fail: distributive law for addition over multiplication and the two complement laws.
63. Give a reason for each step in the proof that x + x ’ x is true in Boolean algebras. Your reasons should come from the following: associative laws for addition and multiplication, commutative laws for addition and multiplication, distributive law for multiplication over addition and distributive law for addition over multiplication, identity laws, unit property, and zero property.
[pic].
Ans: Additive property of 0, multiplicative property of complement, distributive law for addition over multiplication, additive property of complement, commutative law for multiplication, multiplicative property of 1.
64. Give a reason for each step in the proof that x + 1 ’ x is true in Boolean algebras. Your reasons should come from the following: associative laws for addition and multiplication, commutative laws for addition and multiplication, distributive law for multiplication over addition and distributive law for addition over multiplication, identity laws, unit property, and zero property.
[pic].
Ans: Additive property of complement, multiplicative property of 1, distributive law for addition over multiplication, additive property of complement, multiplicative property of 1.
65. Give a reason for each step in the proof that x + xy ’ x is true in Boolean algebras. Your reasons should come from the following: associative laws for addition and multiplication, commutative laws for addition and multiplication, distributive law for multiplication over addition and distributive law for addition over multiplication, identity laws, unit property, zero property, and idempotent laws.
[pic]
Ans: Multiplicative property of 1, addititive property of complement, distributive law for multiplication over addition, associative law for addition, additive idempotent law, distributive law for multiplication over addition, additive property of complement, multiplicative property of 1.
66. Draw a logic gate diagram for the Boolean function [pic]
Ans: [pic]
67. Let [pic]. Draw a logic gate diagram for F.
Ans: [pic][pic]
68. Let [pic]. Use a Karnaugh map to simplify the function F.
Ans: [pic]
69. Use a Karnaugh map to minimize the sum-of-products expression [pic].
Ans: [pic]
70. Use a Karnaugh map to minimize the sum-of-products expression [pic].
Ans: The following Karnaugh map yields [pic].
[pic]
71. Construct a circuit using inverters, OR gates, and AND gates that gives an output of 1 if and only if three people on a committee do not all vote the same.
Ans: The following Karnaugh map yields [pic].[pic]
72. Let [pic]. Draw a logic gate diagram for F.
Ans: [pic]
73. Let [pic]. Show that F can be simplified to give [pic].
Ans: [pic]
(b) [pic]
74. A circuit is to be built that takes the numbers 0 through 9 as inputs (1 ’ 0001,2 ’ 0010,…,9 ’ 1001). Let F(w,x,y,z) be the Boolean function that produces an output of 1 if and only if the input is an even number. Find a Karnaugh map for F and use the map and don't care conditions to find a simple expression for F.
Ans: The Karnaugh map for F is drawn here, with “d” used for the don't care conditions (that is, the bit strings representing the numbers 10 through 15). All 1s are covered by one oval in this map, and hence [pic].
[pic]
75. A circuit is to be built that takes the numbers 0 through 9 as inputs (1 ’ 0001,2 ’ 0010,…,9 ’ 1001). Let G(w,x,y,z) be the Boolean function that produces as output of 1 if and only if the input is an odd number. Find a Karnaugh map for G and use the map and don't care conditions to find a simple expression for G.
Ans: The Karnaugh map for G is drawn here, with “d” used for the don't care conditions (that is, the bit strings representing the numbers 10 through 15). All 1s are covered by one oval, and hence G(w,x,y,z) ’ z.
[pic]
76. Use the Quine-McCluskey method to simplify the Boolean expression [pic].
Ans:
| 1 xyz 111 |(1,2) yz –11 |(2,3,4,5) [pic] 0– – |
|2 [pic] 011 |(2,3) xy 01– | |
|3 [pic] 010 |(2,4) [pic] 0–1 | |
|4 [pic] 001 |(3,5) [pic] 0–0 | |
|5 [pic] 000 |(4,5) [pic] 00– | |
|
The products that were not used to form products in fewer variables are yz and x. This yields
| | [pic] |[pic] |[pic] |[pic] |xyz |
|yz |× | |× | |× |
|[pic] |× |× |× |× | |
|To cover the original five minterms, we use [pic].
77. Use the Quine-McCluskey method to simplify the Boolean expression [pic]
Ans:
|1 wxyz 1111 |(1,2) wxy 111– |(1,2,3,4) wy 1–1– |
|2 [pic] 1110 |(1,3) wxy 1–11 |(1,2,3,4) wy 1–1– |
|3 [pic] 1110 |(2,4) [pic] 1–10 |(3,5,6,7) [pic] –0–1 |
|4 [pic] 1110 |(3,4) [pic] 101– |(3,5,6,7) [pic] –0–1 |
|5 [pic] 1110 |(3,5) [pic] –011 | |
|6 [pic] 1110 |(3,6) [pic] 10–1 | |
|7 [pic] 1110 |(5,7) [pic] 00–1 | |
| |(6,7) [pic] –001 | |
|
The products that were not used to form products in fewer variables are wy and [pic]. This yields
| |wxyz |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |
|wy |× |× |× |× | | | |
|[pic] | | |× | |× |× |× |
|To cover the original seven minterms, use [pic] .
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.