GATE CS 2015 Set 1 Q39 — Boolean Algebra

To determine functional completeness, we analyze each function individually.

1. Analysis of $g(X, Y, Z)$:

We simplify the expression for $g(X, Y, Z)$ using Boolean algebra:

Since $g(X, Y, Z) = Y$, any combination of this function merely outputs its second argument. It is impossible to generate basic operations like NOT, AND, or OR. Thus, $\{g\}$ is not functionally complete.

2. Analysis of $f(X, Y, Z)$:

Given $f(X, Y, Z) = X'YZ + XY' + Y'Z'$:

• NOT Gate: Substitute $Y = X$ and $Z = X$:
  $f(X, X, X) = X'XX + XX' + X'X' = 0 + 0 + X' = X'$.
  Thus, we can implement the NOT operation.
• Constant 0 and 1: Since we have the NOT operation, we can generate $X'$ from $X$. Now, substitute $Y = X$ and $Z = X'$:
  $f(X, X, X') = X'XX' + XX' + X'(X')' = 0 + 0 + 0 = 0$.
  This gives us the constant $0$, and consequently, the constant $1$ (since $0' = 1$).
• AND Gate: Substitute $X = X'$, $Y = 1$, and $Z = Z$:
  $f(X', 1, Z) = (X')'(1)Z + X'(1)' + (1)'Z' = XZ + 0 + 0 = XZ$.
  This gives us the AND operation.

Since we can implement both NOT and AND operations, the set $\{f\}$ is functionally complete.