AND/OR/NOT from One 2:1 MUX Each

Puzzle

Difficulty: Easy · Puzzle 2 of 6 · Topic: Digital Logic Puzzles

Using only a 2:1 MUX primitive Y=S?D1:D0 and constants, derive NOT A, A AND B, and A OR B. Also state minimum MUX count per gate.

Code

// NOT A : S=A, D1=0, D0=1
// A&B   : S=A, D1=B, D0=0
// A|B   : S=A, D1=1, D0=B

Hint

Treat select line as the controlling variable in Shannon expansion.

Step-by-step solution

1) NOT A: Y=A?0:1 = ~A.
2) A AND B: Y=A?B:0 = A&B.
3) A OR B: Y=A?1:B = A|B.
4) Each mapping uses a single 2:1 MUX, so minimum count is 1 per gate.

Answer

Answer: NOT/AND/OR each require exactly one 2:1 MUX with proper constant wiring.

Why candidates get it wrong

Assuming NOT needs extra hardware beyond constants on data inputs.

Interviewer follow-up

Using only MUX + constants, what is minimal MUX count for NAND?

Related topics

• Back to Digital Logic Puzzles

• Logic & Aptitude Puzzles section