Three inverters from two

Question

You have three inputs, a, b and c, each 0 or 1. You may use unlimited AND gates and OR gates but only two NOT gates.

Build a circuit with three outputs equal to NOT a, NOT b and NOT c. Explain the idea; the exact wiring can be given as boolean formulas.

Accepted Answer

Spend the first NOT on "at least two inputs are 1" and the second on "an odd number of inputs are 1". Those two negated signals, combined with the inputs by AND and OR, give all three inverted outputs. Step 1: the majority. Using only AND and OR, compute M = ab + bc + ca, which is 1 exactly when at least two of the inputs are 1. Apply the first NOT: N1 = NOT M, which is 1 exactly when at most one input is 1. Step 2: the parity. Compute A1 = a + b + c ("at least one is 1") and A3 = abc ("all three are 1"). Then E1 = A1 × N1 is "exactly one is 1" (at least one, and at most one). So X = E1 + A3 …

Three inverters from two

Your answer

Discussion

Learn the concepts

Related questions