Multiplexer-Based Universal Function Generator
A multiplexer is a universal logic element — any Boolean function of n variables can be implemented using only MUX 2:1 components (and constants 0 or 1) by applying Shannon's expansion theorem recursively. This is the principle behind FPGA lookup tables: a configurable 16-to-1 mux with programmable data inputs can implement any 4-variable function without ever changing the wiring. Shannon's expansion states F(A,B,C) = A'·F(0,B,C) + A·F(1,B,C), which is exactly a MUX with A as select, F(0,B,C) on input I0, and F(1,B,C) on input I1.
Your task is to implement the function F(A, B, C) defined by the truth table below using only MUX 2:1 components and constants 0 or 1 connected to data inputs. No AND, OR, NOT, NAND, NOR, or XOR gates are allowed.
| A | B | C | F | |---|---|---|---| | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 0 |
Shannon expansion on A: when A=0, F = XNOR(B,C). When A=1, F = XOR(B,C). These two sub-functions are themselves implemented by MUXes. The XNOR and XOR sub-functions share a common intermediate MUX that computes NOT(C) (MUX with I0=1, I1=0, SEL=C). This gives a total of 4 MUX components: one for NOT(C), one for XNOR using NOT(C) and C with B as select, one for XOR using C and NOT(C) with B as select, and one top-level MUX selecting between XNOR and XOR using A.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A | input | 1 | MSB select variable | | B | input | 1 | Middle variable | | C | input | 1 | LSB variable | | F | output | 1 | Boolean function as defined by the truth table |
Constraints
- Only MUX 2:1 components are allowed. No AND, OR, NOT, NAND, NOR, or XOR gates.
- Constants 0 and 1 may be connected directly to MUX data inputs (I0 or I1).
- The optimal solution uses exactly 4 MUX 2:1 components. One of the 4 MUXes computes NOT(C) by connecting I0=1 and I1=0 with SEL=C — it is shared by two other MUXes.
- All 8 input combinations must produce the correct output.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.