Majority Function Circuit Design
Learning Lab 2’s task, following on from revision of gate truth tables and Boolean identities (see logic-gates and boolean-algebra) and the introduction of circuit-schematics/device-pinouts conventions. Main lab objective: verify the functionality of a logic circuit either as a hardware circuit built from logic ICs, or as a Logisim simulation.
Question 1 — 3-input majority function
The 3-input majority function \(Z\) is true if at least two of the inputs \(A, B, C\) are true. Already simplified in 2026-07-30-intro-to-logic-gates (the \(M\) truth table/sum-of-products example there is this same function):
\[Z = AB + AC + BC\]
Convert \(Z\) to a NAND-only circuit (using Boolean algebra or a logic diagram).
Draw a circuit schematic for the NAND-only circuit — inputs are switches, output is an LED.
Wire up the circuit (or simulate in Logisim) and determine the truth table.
(a) NAND-only conversion. The standard sum-of-products → NAND-only technique (double negation + De Morgan’s law, see boolean-algebra): double-invert the whole expression, then push one inversion inside with De Morgan’s law, turning each AND term into a NAND and the outer OR into a NAND of those NAND outputs:
\[Z = AB+AC+BC = \overline{\overline{AB+AC+BC}} = \overline{\overline{AB}\cdot\overline{AC}\cdot\overline{BC}}\]
i.e. \(Z = \text{NAND}\big(\text{NAND}(A,B),\ \text{NAND}(A,C),\ \text{NAND}(B,C)\big)\) — each first-level AND gate becomes a NAND gate, and the second-level OR gate becomes a NAND gate combining the (already-inverted) first-level outputs.
The catch: that final combining gate is a 3-input NAND, and the kit has none. Every gate chip in Device Pinouts and Symbols is 2-input (plus the hex inverter) — see device-pinouts — so the 3-input NAND has to be built from 2-input ones. Writing \(N_1 = \overline{AB}\), \(N_2 = \overline{AC}\), \(N_3 = \overline{BC}\):
\[Z = \overline{N_1 N_2 N_3} = \text{NAND}\big(\overline{\overline{N_1 N_2}},\ N_3\big)\]
which is three more 2-input NANDs: one for \(\overline{N_1 N_2}\), one wired as an inverter (both inputs tied together) to undo that inversion, and one to combine the result with \(N_3\).
Six 2-input NAND gates in total, so two 74HCT00 packages — four gates on the first and two on the second.
(b) Circuit schematic.
Figure 1: The NAND-only majority circuit as a circuit schematic. U1:A to U1:C are the three product terms; U1:D, U2:A and U2:B are the 3-input NAND built out of 2-input ones — combine, invert, combine again. U2:A is the NAND-as-inverter trick: both its inputs are tied to the same signal, which is what the junction dot on its input pair means. Six gates do not fit in one quad package, so the last two need a second chip, which is why U2 exists at all. The partitioning into packages, the pin assignment and the IO board pin choices follow the device pinouts.
(c) Truth table. Reading it off the definition (at least two inputs true) — and this is what the built circuit should reproduce:
| \(A\) | \(B\) | \(C\) | \(Z\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 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 | 1 |
Test the built circuit against all eight rows in this order, not at random — the systematic sweep is what catches a swapped pin. Lab 4 asks for the same habit: decide the test procedure and the truth table you are expecting (see week3-lab-lab-4-pre-work).
See also
- circuit-schematics — the labelling rules the schematic above follows, and the seven common errors it is checked against
- device-pinouts — the 74HCT00 gate/pin pairs and the IO board switch and LED pin numbers
- week2-lab-binary-arithmetic — the next lab, which reuses the same NAND-conversion move on a full adder’s carry expression