Functional completeness questions become predictable when every answer is backed by either a construction or a blocking property. NAND and NOR build a complete basis; monotone and affine sets remain trapped inside narrower classes. Attempt each question before reading its construction, invariant or truth-table check.
Decide completeness by construction or by a blocking property
A set is functionally complete when its members can express every Boolean function. First try to build NOT and either AND or OR. NAND builds both:
NOT A = A NAND A. AtA = 0, the output is1; atA = 1, it is0.A AND B = (A NAND B) NAND (A NAND B).
NOR gives NOT A = A NOR A and A OR B = (A NOR B) NOR (A NOR B). The set {OR, NOT} gives A AND B = NOT((NOT A) OR (NOT B)): it returns 1 at (1,1) and 0 at (1,0).
If construction stalls, seek a preserved property. AND and OR are monotone, so their compositions cannot produce the decreasing function NOT. The Boolean Algebra and K-map Minimization Guide reviews the surrounding laws.
Test a custom Boolean function and the XNOR trap
Question 1: Compare the custom functions f and g
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?
A. Both {π} and {π} are functionally complete
B. Only {π} is functionally complete
C. Only {π} is functionally complete
D. Neither {π} nor {π} is functionally complete
Answer: B
Reduce g to X'Y(Z+Z')+XY=Y, a projection. For f, f(0,0,0)=1, f(1,1,1)=0, and f(0,1,0)=0, so it preserves neither constant and is not monotone. Complementary inputs 001 and 110 both return 0, disproving self-duality. On face (000,100,001,101), parity is 1 XOR 1 XOR 0 XOR 1=1, disproving affinity. Thus f escapes all five closed classes.
Exam reference: GATE 2015, Computer Science, Set 1.
Question 2: XNOR alone stays inside the affine family
A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?
A. EX-NOR
B. implication, negation
C. OR, negation
D. NAND
Answer: A
XNOR is 1 XOR A XOR B. Composing expressions of this form still produces affine functions, while A AND B is not affine. The other sets escape this restriction: {OR, NOT} gives AND by De Morgan, and NAND gives NOT and AND using the earlier identities. With implication and negation, ((NOT A) implies B) = A OR B, after which De Morgan gives AND.
Exam reference: GATE 2008, Computer Science, Information Technology.
Spot the missing negation in operator sets
Question 3: AND and OR cannot escape monotonicity
Any set of boolean operators that is sufficient to represent all boolean expressions is said to be complete. Which of the following is not complete? ISRO 2013
A. {NOT, OR}
B. {NOR}
C. {AND, OR}
D. {AND, NOT}
Answer: C
Every composition of AND and OR remains monotone, so it cannot implement NOT. NOR gives NOT A = A NOR A; {NOT, OR} gives AND through De Morgan; and {AND, NOT} gives A OR B = NOT((NOT A) AND (NOT B)). Those three sets are complete.
Exam reference: Indian Space Research Organization 2013, Computer Science.
Question 4: Multiplexers and constants change what can be built
Which of the following set of components is sufficient to implement any arbitrary Boolean function?
a) XOR gates, NOT gates
b) 2 to 1 multiplexers
c) AND gates, XOR gates, 1
d) Three-input gates that output (A.B)+C for the inputs A, B and C.
A. a and d
B. b and c
C. c
D. All a, b, c and d
Answer: B
Set a remains affine and cannot make AND. For M(S,I0,I1), inputs (1,0) give NOT S, while (0,B) give S AND B, so b is complete with constants. In c, A XOR 1=NOT A. Gate d, AB+C, stays monotone and cannot make NOT. Only b and c qualify.
Exam reference: Indian Space Research Organization 2017, Computer Science, December.
Use gate synthesis as evidence of completeness
A universal-gate claim needs a construction: producing NOT plus AND or OR proves that the basis can express every Boolean function. The gate-count and network questions apply that proof to concrete circuits. For a full set devoted to NAND and NOR implementation drills, use NAND and NOR Universal Gates: 12 Solved MCQs.
Question 5: Identify a universal gate
Which of the following is a universal gate?
A. NOT
B. NAND
C. OR
D. AND
Answer: B
NAND proves its universality by construction. A NAND A gives NOT, and NANDing A NAND B with itself gives AND. With NOT and AND available, De Morgan gives OR, so NAND alone can realise every Boolean function.
Question 6: Let absorption reduce the NAND count to zero
The minimum number of NAND gates required to implement the Boolean function A + AB'+ AB'C is equal to
A. 0
B. 1
C. 4
D. 7
Answer: A
Apply absorption twice: A+AB'=A, then A+AB'C=A. The available input can connect directly to the output, so the function needs zero NAND gates unless buffering is explicitly required.
Question 7: Implement WX+Y using only NAND gates
What is the minimum number of 2-input NAND gates required to implement the Boolean function F=WX+Y ?
A. 5
B. 3
C. 2
D. 4
Answer: B
Gate 1 produces N1=(WX)', and tied-input Gate 2 produces N2=(Y.Y)'=Y'. Gate 3 returns (N1.N2)'=WX+Y. At (W,X,Y)=(0,0,1), the signals are 1, 0, then 1, matching the target.
Question 8: Implement AB+C using only NOR gates
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
A. 2
B. 3
C. 4
D. 5
Answer: B
Rewrite AB+C=(A+C)(B+C). Two NOR gates form N1=(A+C)' and N2=(B+C)'; a third gives (N1+N2)'=(A+C)(B+C). At (1,0,0), the three outputs are 0, 1, 0, agreeing with AB+C=0.
Question 9: Build XOR from NAND gates
What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?
A. 3
B. 4
C. 5
D. 6
Answer: B
Use N1=A NAND B, N2=A NAND N1, N3=B NAND N1, and F=N2 NAND N3. The outputs for 00, 01, 10, 11 are 0, 1, 1, 0, exactly XOR. Sharing N1 keeps the minimum at four gates.
Question 10: Recognise XOR inside a NOR network
A circuit first forms N=(x+y)'. It then forms B=(x+N)' and C=(y+N)', before sending B and C into a plain OR gate. Which logic operation does the circuit perform?
A. EXCLUSIVE-OR
B. EXCLUSIVE-NOR
C. NAND
D. NOR
Answer: A
Let N=(x+y)'. The next NOR outputs are (x+N)'=x'y and (y+N)'=xy'. Their final plain-OR output is x'y+xy'=x XOR y, whose rows are 00 -> 0, 01 -> 1, 10 -> 1, 11 -> 0.
Two bonus questions: monotonicity and Boolean duality
Bonus 1: Recheck the same incomplete basis in a new option order
Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is not complete?
A. { AND, OR }
B. { AND, NOT }
C. { NOT, OR }
D. { NOR }
Answer: A
The set {AND, OR} cannot generate a decreasing function such as NOT. By contrast, {AND, NOT} gets OR by De Morgan, {NOT, OR} gets AND by De Morgan, and {NOR} gets NOT and OR. The last three are complete.
Exam reference: Indian Space Research Organization 2018, Computer Science.
Bonus 2: A Boolean-duality question
Boolean duality is separate from functional completeness: swap AND with OR, and swap 0 with 1 when constants appear, without complementing literals.
The dual of the switching function X+YZ is:
A. X+YZ
B. X'+Y'Z'
C. X(Y+Z)
D. X'(Y'+Z')
Answer: C
Duality swaps OR and AND without changing literals. The outer + becomes multiplication and YZ becomes Y+Z, giving X(Y+Z). Options B and D complement literals; option A changes nothing.
Exam references: UGC NET 2007 and 2008, Computer Science, December.
Build one worked synthesis table
Set/component | Construction or invariant | Verdict |
|---|---|---|
NAND |
| Complete |
NOR |
| Complete |
| AND by De Morgan | Complete |
| Monotone, cannot make NOT | Incomplete |
XNOR |
| Incomplete |
2:1 MUX |
| Complete |
|
| Complete |
| Monotone | Incomplete |
A tied
0or1is valid only when the component set permits constants.
Turn wrong answers into four reusable trap labels
Trap label | Repair |
|---|---|
Universal-gate recall without construction | Write the two identities for NOT and AND or OR. |
Affine-family miss | Check whether only XOR, XNOR, NOT and constants are available. |
Monotonicity miss | Ask whether any operation can make the output fall when an input rises. |
Duality/complement confusion | Swap operators without changing literals. |
Monotonicity shows why {AND, OR} is incomplete. Recheck any missed construction before scoring the set.
Score 10 questions and choose the next practice step
10/10: Reattempt Question 1 from scratch without reading the explanation.
7-9/10: Redo the synthesis table, then reattempt every missed question.
0-6/10: Rebuild NOT, AND and OR from NAND and NOR before another timed set.
Score Questions 1 to 10. Treat the two bonus questions as diagnosis rather than part of the total.
The short version
Construct a complete basis, or find an invariant preserved by every composition. For concept revision, follow GATE Guidance by Sanchit Sir through the GATE CS Exam Preparation route. For drills, use the GATE Test Series. Before choosing, write the construction or name the blocking property.
