COMPSCI110 · Introduction to Computer Systems
Boolean Logic & Digital Circuits
Module 2 of University of Auckland COMPSCI110 is where computation physically happens: the logic gates (AND, OR, NOT, NAND, NOR), their truth tables, transistors as switches, De Morgan's laws, and the recipe for turning any truth table into a circuit — the sum-of-products method. It then builds real hardware from gates: the 1-bit comparator, the full adder, the two's-complement subtractor, and the control/sequential elements (multiplexor, decoder, SR latch, register). It carries 3 marks on the final exam, but the skills underpin Modules 3 and 4, so getting the truth tables exactly right pays off downstream.
What this chapter covers
- 01The five gates and their truth tables: AND (a·b), OR (a+b), NOT (Ā), NAND, NOR — transcribe exactly, and note NOT flips 0↔1
- 02Transistors as solid-state switches (NOT = 1, NAND/NOR = 2, AND/OR = 3 transistors); n-input functions (2 inputs → 2⁴ = 16 possible functions)
- 03Functional completeness: NAND and NOR can each build any circuit (tie both inputs together to get NOT)
- 04De Morgan's laws: A+B = Ā·B̄ and A·B = Ā+B̄ (and their complemented variants)
- 05Combinational circuits (output depends only on current inputs) and the sum-of-products algorithm: one AND term per true row, OR them together
- 06Arithmetic hardware: the 1-CE equality circuit (a·b)+(ā·b̄), the full adder (sum + carry), and two's-complement subtraction (invert b, carry-in 1)
- 07Control & sequential circuits: multiplexor (2ᴺ in / N select / 1 out) vs decoder (N in / 2ᴺ out), the SR latch (with S=R=1 forbidden), and registers
Sum-of-products: a circuit from a 2-input truth table
- +1Read the truth table row by row: A=0,B=0 → 1; A=0,B=1 → 1; A=1,B=0 → 0; A=1,B=1 → 1. Mark the three rows whose output is 1 (rows 00, 01, 11).
- +1SOP rule: for each output-1 row, write one AND (product) term of the inputs, complementing any input that is 0 in that row. Row 00 → Ā·B̄; row 01 → Ā·B; row 11 → A·B.
- +1OR all the product terms together: Output = (Ā·B̄) + (Ā·B) + (A·B). Each AND term is 1 for exactly its own row, so the OR is 1 on precisely rows 00, 01 and 11 — matching the table.
- +1Optional simplification/cross-check: Ā·B̄ + Ā·B = Ā (B̄ + B = 1), then Ā + A·B = Ā + B. So the circuit equals Ā + B, whose truth table is 1,1,0,1 — the same table. Either the three-term SOP or Ā + B is a correct answer.
Key terms
- Truth table
- A table listing a circuit's output for every combination of inputs. For n inputs it has 2ⁿ rows. The five course gates: AND is 1 only when both inputs are 1; OR is 1 when at least one is 1; NOT flips the bit; NAND and NOR are the complements of AND and OR.
- Functional completeness
- A gate is functionally complete if any Boolean function can be built from it alone. NAND and NOR each qualify — tying both of a NAND's (or NOR's) inputs together yields NOT, and from NOT plus the gate you can construct AND and OR. This is why real chips are often built entirely from NAND gates.
- De Morgan's laws
- Two identities relating AND, OR and NOT: A+B = Ā·B̄ (the complement of an OR is the AND of the complements) and A·B = Ā+B̄. They let you convert between AND/OR forms and are the standard tool for simplifying or re-implementing a circuit with different gates.
- Sum-of-products (SOP)
- A standard way to realise any truth table: for every row whose output is 1, write an AND (product) term of the inputs — complementing the inputs that are 0 — then OR (sum) all those terms. Each product term is true for exactly one input row, so the OR reproduces the table.
- Full adder (1-ADD)
- A 1-bit adder with three inputs — the two bits aᵢ, bᵢ and a carry-in cᵢ — and two outputs, the sum sᵢ and the carry-out cᵢ₊₁. Chaining full adders (each carry feeding the next, with initial carry c₀ = 0) builds an n-bit adder; feeding an inverted operand plus carry-in 1 turns it into a subtractor.
- SR latch
- The simplest 1-bit memory (a sequential element): S=1 sets the output to 1, R=1 resets it to 0, and S=R=0 holds the stored value (the quiescent state). S=R=1 is forbidden — it drives the latch into an undefined state. Registers are built from latches with a write-enable line.
Boolean Logic & Digital Circuits FAQ
What does it mean that NAND (or NOR) is 'functionally complete'?
It means you can build any digital circuit using only that one gate type. If you tie both inputs of a NAND together it behaves as a NOT; with NOT plus NAND you can make AND and OR, and from AND, OR and NOT you can implement any truth table. NOR has the same property. That is a genuinely useful fact in hardware — a fabrication process only has to make one kind of gate really well.
How do I turn a truth table into a circuit?
Use the sum-of-products method. List the rows where the output is 1; for each, write an AND term of all the inputs, complementing (barring) the inputs that are 0 in that row; then OR all those AND terms together. Each AND term switches on for exactly one input pattern, so the OR of them is 1 on precisely the rows you selected. You can then simplify with De Morgan and the Boolean identities if the question asks for a minimal form.
Can AI help me with logic circuits in COMPSCI110?
Yes, as a study aid. Sia can check a truth table, walk the sum-of-products construction term by term, apply De Morgan to re-express a circuit, and trace a full adder or SR latch for given inputs. Use it to learn the method and rehearse on fresh tables — it explains and checks your reasoning but does not complete graded assignments or the exam for you, and the University of Auckland's academic-integrity rules apply to the controlled assessments.
Why is S=R=1 forbidden on the SR latch?
Setting and resetting at the same time asks the latch to make the output both 1 and 0 at once, which the cross-coupled gates cannot resolve — the result is undefined, and when the inputs return to 0 the final state can't be predicted. That's why the course marks S=R=1 as the forbidden ('don't') combination; a well-designed circuit never drives both control lines high together.
Is Module 2 heavily weighted on the exam?
Directly it is 3 marks on the final exam, so it isn't the biggest single module — but the material is load-bearing. Truth tables, gates and the adder reappear inside Computer Organisation (the ALU) and Assembly (arithmetic on register R), so a shaky grip here quietly costs marks in later modules too. Learn the truth tables exactly and the SOP recipe cold; confirm the current exam breakdown on Canvas.
Exam move
Get the five truth tables letter-perfect first — AND, OR, NOT, NAND, NOR — because a reversed gate is a HIGH-cost error that cascades into every circuit question. Then drill the sum-of-products recipe on 2- and 3-input tables until it's automatic: one AND term per true row, bar the 0-inputs, OR them, then simplify with De Morgan if asked. Keep the two identities on your sheet (A+B = Ā·B̄, A·B = Ā+B̄) and practise re-implementing an AND circuit with only NANDs to internalise functional completeness. For the arithmetic hardware, understand rather than memorise: the full adder's sum and carry outputs, and the one idea that the subtractor is just the adder fed an inverted operand and a carry-in of 1. Finally, nail the four control/sequential facts that get asked as MCQs: multiplexor = 2ᴺ inputs / N selectors / 1 output; decoder = N inputs / 2ᴺ outputs; the SR latch holds on S=R=0 and forbids S=R=1; a register is latches plus write-enable.
Working through Boolean Logic & Digital Circuits in COMPSCI 110? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI 110 Boolean Logic & Digital Circuits question and get a clear, step-by-step explanation grounded in how COMPSCI 110 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
