GATE CS 1992 Q02-ii — Combinational Circuits

To realize any digital circuit, the given component or set of components must be functionally complete. A set of logic gates is functionally complete if it can implement the basic operations: AND, OR, and NOT.

Let's analyze each option assuming the availability of constant inputs ($0$ and $1$):

1. Ex-OR gates: An Ex-OR gate is a linear operator. Any combination of Ex-OR gates can only produce linear functions (functions of the form $x_1 \oplus x_2 \oplus \dots \oplus x_n \oplus c$). It is impossible to realize non-linear operations like AND or OR using only Ex-OR gates. Thus, they are not functionally complete.
2. Multiplexers: A 2-to-1 multiplexer with select line $S$ and inputs $I_0, I_1$ implements the function $Y = \bar{S}I_0 + SI_1$.
   • By setting $I_0 = 1$ and $I_1 = 0$, we get $Y = \bar{S}$ (NOT gate).
   • By setting $I_0 = 0$ and $I_1 = B$, and $S = A$, we get $Y = AB$ (AND gate).
   Since we can implement both NOT and AND, multiplexers are functionally complete.
3. Half adders: A half adder takes two inputs $A$ and $B$ and produces two outputs: $$\text{Sum} = A \oplus B$$ $$\text{Carry} = A \cdot B$$
   • The Carry output directly gives the AND operation: $A \cdot B$.
   • By setting one input of the half adder to $1$, the Sum output gives $A \oplus 1 = \bar{A}$ (NOT operation).
   Since we can implement both AND and NOT, half adders are functionally complete.
4. OR gates: Using only OR gates, we cannot produce a NOT operation because the output of any combination of OR gates will always be $0$ when all inputs are $0$. Thus, they are not functionally complete.

Therefore, all digital circuits can be realized using only Multiplexers or Half adders.