Which of the following set(s) of components is/are sufficient to implement any…
1999
Which of the following set(s) of components is/are sufficient to implement any arbitrary Boolean function?
a) XOR gates and NOT gates
b) 2-to-1 multiplexers
c) AND gates and XOR gates
d) Three-input gates that output (A.B) + C for inputs A, B and C
Answer: B. b and c — The correct answer is: b and c. A set of components is sufficient if it can implement any Boolean function. (a) XOR gates with NOT gates are not sufficient.…
- A.
a and d
- B.
b and c
- C.
c only
- D.
All of the above
Attempted by 113 students.
Show answer & explanation
Correct answer: B
The correct answer is: b and c.
A set of components is sufficient if it can implement any Boolean function.
(a) XOR gates with NOT gates are not sufficient. They can produce only affine/parity-type Boolean functions, so they cannot implement functions such as AND.
(b) 2-to-1 multiplexers are sufficient. By Shannon expansion, any Boolean function can be expressed using a variable as the select input and the two cofactors as the data inputs. Repeating this construction realizes any Boolean function.
(c) AND gates with XOR gates are sufficient when constants are available, because every Boolean function has an algebraic normal form: an XOR of product terms. The product terms are formed by AND gates and combined by XOR gates.
(d) The three-input gate with output (A.B)+C is not sufficient by itself because it is monotone; compositions of it cannot generate inversion.
Therefore only b and c are sufficient.
Explore the full course: Iocl Engineers Officers Grade A Paper 2