The GATE Grind

GATE 2015 CS – Question 43

Digital Logic · Boolean Algebra and Minimization · 2 marks · Multiple choice

Consider the operations $f(X, Y, Z) = X'YZ + XY' + Y'Z'$ and $g(X, Y, Z) = X'YZ + X'YZ' + XY$.

Which one of the following is correct?

  1. Both $\{f\}$ and $\{g\}$ are functionally complete
  2. Only $\{f\}$ is functionally complete
  3. Only $\{g\}$ is functionally complete
  4. Neither $\{f\}$ nor $\{g\}$ is functionally complete

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Only $\{f\}$ is functionally complete

Explanation

Simplifying $g$ gives $X'Y(Z + Z') + XY = X'Y + XY = Y$, so $g$ just returns its second input and cannot build NOT. For $f$, setting all inputs to $X$ gives $f(X,X,X) = X'$, which is NOT. Setting $Y = 0$ gives $f(X,0,Z) = X + Z'$, and feeding $Z'$ in for $Z$ gives $X + Z$, which is OR. NOT and OR together are functionally complete, so $\{f\}$ is.