MUX Algebra: Every Two-Input Logic Gate From MUXes

Build every two-input logic gate from selectors, inputs, and constants.

A MUX chooses one wire. From 0, 1, A, and NOT A, one more choice by B produces every Boolean function of A and B.

The Only MUX Rule

M(S, D0, D1) = S ? D1 : D0

A 2-to-1 multiplexer with selector S equal to zero; the solid selected route connects D0 to output Y while D1 is dashed — `S=0` connects `D0` to `Y`.

A 2-to-1 multiplexer with selector S equal to one; the solid selected route connects D1 to output Y while D0 is dashed — `S=1` connects `D1` to `Y`.

The selector does not calculate a value. It connects exactly one input path to the output.

Constants Create The Four Possible Sources

Once A is the only live input, its output can behave in only four ways. Each picture below uses the same MUX geometry and gives that behavior a two-bit pointer.

Pointer 00 represented by a multiplexer selected by A with both data inputs tied to zero, producing constant zero — `00`: tie both data inputs to zero. The result is always `0`.

Pointer 01 represented by a multiplexer selected by A with D0 tied to zero and D1 tied to one, producing A — `01`: choose between zero and one with `A`. The result follows `A`.

Pointer 10 represented by a multiplexer selected by A with both data inputs tied to one, producing constant one — `10`: tie both data inputs to one. The result is always `1`.

Pointer 11 represented by a multiplexer selected by A with D0 tied to one and D1 tied to zero, producing NOT A — `11`: choose the opposite constant with `A`. The result is `NOT A`.

Build AND One Branch At A Time

Freeze B, and ask what the output must do as A changes. The answer for each value of B is one of the four source pictures above.

AND with B fixed at zero; both values of A produce zero, so the branch selects source zero with pointer 00 — When `B=0`, AND must be zero for both values of `A`. Choose source `0`.

AND with B fixed at one; the output follows A, so the branch selects source A with pointer 01 — When `B=1`, AND follows `A`. Choose source `A`.

A minimal AND circuit: one multiplexer selected by B with D0 equal to zero and D1 equal to A, plus all four truth-table outputs — `B=0` forces zero; `B=1` passes `A`. Only `A=1, B=1` produces one.

AND = M(B, 0, A) pointer word 00|01 = 0001

Why No Boolean Function Is Missing

Direct truth-bit construction

Store the four truth-table outputs as C00, C10, C01, and C11. Two MUXes choose by A; a third chooses the correct column by B. Because the four stored bits can contain any pattern, this tree realizes all 16 two-input functions.

A universal LUT2 tree made from three 2-to-1 multiplexers and four stored truth bits; A selects within each B column and B selects the column — Three nested 2:1 MUXes select one of four stored truth bits. This is the direct LUT2 construction.

The 2020 source-pointer construction

The manuscript uses a different four-bit encoding. It notices that each fixed-B column is exactly one of 0, A, 1, or NOT A, then stores two source addresses instead of four direct truth bits.

A two-input truth table split into B equals zero and B equals one columns; each two-bit column maps to source zero, A, one, or NOT A and its manuscript pointer code — Each `B` column is one two-bit behavior of `A`, so each column needs only a two-bit source pointer.

A four-bit configuration word split into C3 C2 for the B equals zero branch and C1 C0 for the B equals one branch — The high pair addresses the `B=0` source. The low pair addresses the `B=1` source.

Clean block and circuit diagram of the complete source-pointer network: a bank of zero, A, one, and NOT A feeds two addressed 4-to-1 pickers and a final B-selected 2-to-1 MUX — Both addresses see the same four sources. `B` chooses which addressed branch reaches `Y`.

Do not mix the encodings. A truth vector lists four outputs in the visible order A0B0, A0B1, A1B0, A1B1. The 2020 pointer word contains two source addresses in the order B=0 | B=1.

For example, XOR has truth vector 0110 but pointer word 01|11 = 0111.

Every Two-Input Function As A Circuit

Each card shows the smallest 2:1 MUX wiring, the four visible truth outputs, and the 2020 pointer word. Constants and direct wires count as zero MUXes. XOR, XNOR, NAND, and NOR need two; the other nontrivial functions need one.

When B=0, source 0 uses pointer 00

The high pointer pair is 00.

FALSE Boolean function tied directly to zero, with truth vector 0000 and pointer word 0000 — FALSE is a direct constant: `Y=0`.

AND built with one MUX selected by B, D0 equal to zero, and D1 equal to A — AND: `B=0` forces zero; `B=1` passes `A`.

Wire B connected directly to output Y, with truth vector 0101 and pointer word 0010 — WIRE B is direct: `Y=B`.

B AND NOT A built with one MUX selected by A, D0 equal to B, and D1 equal to zero — `B AND NOT A`, also `B ↛ A`: `A=0` passes `B`; `A=1` forces zero.

When B=0, source A uses pointer 01

The high pointer pair is 01.

A AND NOT B built with one MUX selected by B, D0 equal to A, and D1 equal to zero — `A AND NOT B`, also `A ↛ B`: `B=0` passes `A`; `B=1` forces zero.

Wire A connected directly to output Y, with truth vector 0011 and pointer word 0101 — WIRE A is direct: `Y=A`.

OR built with one MUX selected by B, D0 equal to A, and D1 equal to one — OR: `B=0` passes `A`; `B=1` forces one.

XOR built with two MUXes: the first makes NOT A and the second, selected by B, chooses A or NOT A — XOR: first make `NOT A`; then let `B=0` pass `A` and `B=1` pass `NOT A`.

When B=0, source 1 uses pointer 10

The high pointer pair is 10.

NOT B built with one MUX selected by B, D0 equal to one, and D1 equal to zero — NOT B: `B` chooses the opposite constant.

B implies A built with one MUX selected by B, D0 equal to one, and D1 equal to A — `B → A`: when `B=0` the implication is true; when `B=1` it follows `A`.

TRUE Boolean function tied directly to one, with truth vector 1111 and pointer word 1010 — TRUE is a direct constant: `Y=1`.

NAND built with two MUXes: the first makes NOT A and the second, selected by B, chooses one or NOT A — NAND: `B=0` forces one; `B=1` passes `NOT A`.

When B=0, source NOT A uses pointer 11

The high pointer pair is 11.

NOR built with two MUXes: the first makes NOT A and the second, selected by B, chooses NOT A or zero — NOR: `B=0` passes `NOT A`; `B=1` forces zero.

XNOR built with two MUXes: the first makes NOT A and the second, selected by B, chooses NOT A or A — XNOR: `B=0` passes `NOT A`; `B=1` passes `A`.

A implies B built with one MUX selected by A, D0 equal to one, and D1 equal to B — `A → B`: when `A=0` the implication is true; when `A=1` it follows `B`.

NOT A built with one MUX selected by A, D0 equal to one, and D1 equal to zero — NOT A: `A` chooses the opposite constant.

More Inputs Repeat The Same Move

For a third input, split the function once more. The two branches are now two-input functions from the catalog above. Repeating the split eventually reaches constants, so nested MUXes can express any Boolean function.

A three-input Boolean function split by a C-selected MUX into F of A B zero and F of A B one — A new input adds one more selection level; the rule does not change.

The Original 2020 Figures

The diagrams above are clean teaching redraws. The source manuscript's Logisim figures remain here as the original functional evidence.

Original 2020 Logisim configurable MUX network with A, B, ground, power, a four-bit configuration input, and output Y — Original configurable network: the four-bit word controls the two branch meanings, and `B` selects the final branch.

Original 2020 Logisim grid of Boolean functions with S0 equal to zero and S1 equal to zero — Original state: `S0=0, S1=0`.

Original 2020 Logisim grid of Boolean functions with S0 equal to one and S1 equal to zero — Original state: `S0=1, S1=0`.

Original 2020 Logisim grid of Boolean functions with S0 equal to zero and S1 equal to one — Original state: `S0=0, S1=1`.

Original 2020 Logisim grid of Boolean functions with S0 equal to one and S1 equal to one — Original state: `S0=1, S1=1`.

Date: the manuscript identifies 2020 but gives no month or day, so none has been invented.

Web edition: variable names were normalized to A and B; the manuscript's inconsistent implication directions were replaced by the truth-table-correct labels A → B and B → A.

Evidence boundary: the Logisim images show the functional selector network. They are not a transistor layout, extracted circuit, or powered-hardware measurement.

The manuscript calls its configurable circuit a “16 CMOS transistor” LUT2 and describes two selectors as six-transistor MUXes. That is the proposal in the note, not a universal device count: the total depends on MUX topology, complemented-selector generation, source sharing, loading, and output drive.

Exact executable definition

function muxAlgebra(a, b, config) {
    const sources = [0, a, 1, Number(!a)];
    const pointer = b ? (config & 0b11) : (config >> 2);
    return sources[pointer];
}

muxAlgebra(1, 1, 0b0001); // AND  -> 1
muxAlgebra(1, 1, 0b0111); // XOR  -> 0

Where This Construction Leads

The Logisim-to-LUT learning path grows this exact selection rule from LUT1 through LUT6 and connects it to Lattice and AMD/Xilinx FPGA primitives. The physical MUX tiles make the selector, constants, routes, intersections, and orientation tangible. Boolean Algebra Is All That Is Required extends the same completeness argument into storage, configuration transport, ownership, and an extensible fabric.