Majority Function Circuit Design

exercises
lab
computer-systems
digital-logic

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 lecture’s \(M\) truth table/sum-of-products example is this same function):

\[Z = AB + AC + BC\]

  1. Convert \(Z\) to a NAND-only circuit (using Boolean algebra or a logic diagram).

  2. Draw a circuit schematic for the NAND-only circuit — inputs are switches, output is an LED.

  3. 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.

Note this final combining gate is a 3-input NAND, which a 74HCT00 doesn’t provide directly (it only has 2-input NAND gates) — building the 3-input NAND from 2-input NAND gates, and the resulting schematic/pin assignment, is the hands-on part of the lab task and isn’t given directly in the source material.

(b)/(c): use circuit-schematics labelling conventions and device-pinouts for the 74HCT00 pinout and IO board switch/LED pin numbers (inputs \(A, B, C\) on three switches, output \(Z\) on an LED).