GATE CS 1999 Q2.9 — Boolean Algebra

To determine which sets of components are functionally complete (sufficient to implement any arbitrary Boolean function), we analyze each option:

1. XOR gates, NOT gates:

   Both XOR and NOT are linear functions. Any combination of linear functions can only produce linear functions. Since non-linear functions like AND ($A \cdot B$) or OR ($A + B$) cannot be represented, this set is not functionally complete.

2. 2-to-1 multiplexers:

   The output of a 2-to-1 multiplexer with select line $S$ and inputs $I_0, I_1$ is given by $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$, $I_1 = B$, and $S = A$, we get $Y = A \cdot B$ (AND gate).

   Since we can implement both AND and NOT gates, 2-to-1 multiplexers are functionally complete.

3. AND gates, XOR gates:

   Using the constant $1$, we can implement the NOT operation as $\bar{A} = A \oplus 1$. Since we have both AND and NOT, we can implement any Boolean function. This is also known as the Reed-Muller expansion. Thus, this set is functionally complete.

4. Three-input gates that output $(A \cdot B) + C$:

   The function $f(A, B, C) = AB + C$ is a monotonic function (it contains no negations). Any network of purely monotonic gates can only implement monotonic functions. Since the NOT operation is non-monotonic, it is impossible to implement a NOT gate using this component. Thus, it is not functionally complete.