Difficulty: Easy · Puzzle 1 of 6 · Topic: Digital Logic Puzzles
Construct Y = A ^ B using only 2:1 multiplexers and constants 0/1. Give one concrete implementation.
module mux_xor(input logic A, B, output logic Y);
logic nB;
// MUX form: Z = S ? D1 : D0
assign nB = B ? 1'b0 : 1'b1; // ~B
assign Y = A ? nB : B; // A?~B:B = A^B
endmoduleUse one MUX to create ~B, then select between B and ~B using A.
1) Recall 2:1 MUX equation: Z = S?D1:D0.
2) Invert B by setting S=B, D1=0, D0=1 => nB = ~B (the same one-MUX trick gives NOT for any signal).
3) Build XOR with S=A, D1=nB, D0=B => Y = A?~B:B.
4) Verify truth table: A=0 => Y=B; A=1 => Y=~B, which equals A^B.
5) Why not one MUX: with S=A the data inputs would need to be ~B and B, but only A, B, 0, 1 are available (and S=B is symmetric), so no single MUX is XOR. The minimum is 2.
6) Side result: with constants only, AND is S=A,D1=B,D0=0 and OR is S=A,D1=1,D0=B, one MUX each.Answer: Two MUXes suffice: one for ~B and one for A-select between B and ~B.
Checked by running a model of the rule in Icarus Verilog 13 and a Python model. The shown two-MUX module simulated in Icarus: it matches A^B on all four input pairs, and swapping the data inputs of the second MUX gives XNOR. A computational check: from A, B, 0, 1 no single MUX makes XOR, but two MUXes do; one MUX also gives AND and OR as stated.
Hunting for a one-MUX XOR. XOR needs both B and ~B as data inputs, and the only way to get ~B is another MUX with constants 0 and 1.
Can you build XNOR with same structure and same MUX count? Model answer: yes, 2 MUXes again. Swap the data inputs of the second MUX: Y = A ? B : nB (A=1 gives B, A=0 gives ~B), which is ~(A^B).
A two-to-one mux with constant inputs makes an inverter, so with select B, data one at zero and data zero at one I get not B in one mux. Then a second mux with select A, picking not B when A is one and B when A is zero, gives A XOR B. So two muxes are enough. One mux cannot do it because XOR needs both B and not B as data inputs, and not B itself costs a mux. The trap is hunting for a single-mux XOR.