Logic gates and circuit simplification
Master logic gates and circuit simplification in Year 11 VCE Specialist Mathematics. Logic gates — AND, OR, NOT, NAND, NOR and XOR — are the building blocks of digital circuits, each described by a truth table and a Boolean expression. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Logic and algorithms topic of Unit 1.
You will learn to find the output of a combinational circuit, write the Boolean expression a circuit computes, and simplify it using the laws of Boolean algebra — including De Morgan's laws — to build the same output with fewer gates.
Theory
Logic gates are the building blocks of digital circuits: each gate takes one or two binary inputs (\(0\) or \(1\)) and produces a single output. In Year 11 Specialist Mathematics you describe a gate by its truth table and Boolean expression, trace the output of a small circuit, write the expression a circuit computes, and simplify circuits using the laws of Boolean algebra.
A logic gate acts on Boolean values — each input and output is either \(1\) (true) or \(0\) (false). A truth table lists the output for every possible combination of inputs, and a Boolean expression records the same rule in symbols.
The six standard gates are:
- AND \((A\land B)\): output \(1\) only when both inputs are \(1\).
- OR \((A\lor B)\): output \(1\) when at least one input is \(1\) (inclusive or); it is \(0\) only for \((0,0)\).
- NOT \((\overline A)\): a single-input inverter — it outputs the opposite bit.
- NAND \((\overline{A\land B})\): not-and — an AND gate followed by an inverter, so it outputs \(0\) only for \((1,1)\).
- NOR \((\overline{A\lor B})\): not-or — an OR gate followed by an inverter, so it outputs \(1\) only for \((0,0)\).
- XOR \((A\oplus B)\): exclusive-or — output \(1\) exactly when the two inputs differ.
On a circuit diagram each gate has its own symbol. AND has a flat back with a rounded nose; OR has a curved back and a pointed nose; NOT is a triangle. A small bubble on the output turns AND into NAND, OR into NOR, and marks the inverting tip of a NOT gate. XOR is an OR shape with an extra curved line across its back.
A combinational circuit wires several gates together. Signals flow left to right: the outputs of early gates become the inputs of later ones, and the final wire is the circuit’s output. Simplifying a circuit means rewriting its Boolean expression with the laws of Boolean algebra so the same output is produced by fewer gates.
Each gate is defined by a Boolean expression and, equivalently, by its truth table. Writing \(\land\) for AND, \(\lor\) for OR, an overline for NOT and \(\oplus\) for XOR:
The truth tables of the two-input gates over all four input combinations, with the single-input NOT gate alongside:
| \(A\) | \(B\) | \(A\land B\) | \(A\lor B\) | \(\overline{A\land B}\) | \(\overline{A\lor B}\) | \(A\oplus B\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| \(A\) | \(\overline A\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Laws of Boolean algebra
These identities let you rewrite an expression without changing its output. Each holds for every value of \(A\), \(B\), \(C\):
- Identity: \(A\land 1=A\), \(A\lor 0=A\).
- Annihilator: \(A\land 0=0\), \(A\lor 1=1\).
- Complement: \(A\land\overline A=0\), \(A\lor\overline A=1\).
- Idempotent: \(A\land A=A\), \(A\lor A=A\).
- Distributive: \(A\land(B\lor C)=(A\land B)\lor(A\land C)\) and \(A\lor(B\land C)=(A\lor B)\land(A\lor C)\).
- Absorption: \(A\lor(A\land B)=A\) and \(A\land(A\lor B)=A\).
- De Morgan: \(\overline{A\land B}=\overline A\lor\overline B\) and \(\overline{A\lor B}=\overline A\land\overline B\).
Working with logic gates and circuits
To build a gate’s truth table (or read off its expression):
- List every input combination. Two inputs give four rows: \((0,0),(0,1),(1,0),(1,1)\).
- Apply the gate rule to each row to fill in the output column.
To find the output of a circuit for given inputs:
- Substitute the input values on the left.
- Evaluate gate by gate, left to right, carrying each gate’s output forward as an input to the next.
- The value on the final wire is the circuit’s output.
To find the expression a circuit computes, trace the signal left to right, writing the Boolean expression at each gate’s output until you reach the final wire.
To simplify a circuit (produce the same output with fewer gates):
- Write the Boolean expression the circuit computes.
- Apply the laws of Boolean algebra — absorption, distributive, complement and De Morgan — to reach the simplest equivalent expression.
- Redraw the circuit from the simplified expression; it needs fewer (sometimes zero) gates.
An AND gate outputs \(1\) only when both inputs are \(1\).
(i) \(A=0,\ B=1\):
| \(Y\) | \(=\) | \(0 \land 1\) |
| \(=\) | \(0\) |
(ii) \(A=1,\ B=0\):
| \(Y\) | \(=\) | \(1 \land 0\) |
| \(=\) | \(0\) |
(iii) \(A=1,\ B=1\):
| \(Y\) | \(=\) | \(1 \land 1\) |
| \(=\) | \(1\) |
\(Y=0\) for both \((0,1)\) and \((1,0)\); \(Y=1\) only for \((1,1)\).
Work left to right — the AND output is inverted by the NOT gate:
| \(\text{AND output}\) | \(=\) | \(A \land B\) |
| \(\text{NOT of that}\) | \(=\) | \(\overline{A \land B}\) |
The circuit computes \(\overline{A \land B}\) — this is a NAND (not-and) gate.
Trace each gate, then combine:
| \(\text{AND gate}\) | \(=\) | \(A \land B\) |
| \(\text{OR with } C\) | \(=\) | \((A \land B) \lor C\) |
The circuit computes \((A \land B) \lor C\).
(i) \(A=1,\ B=0\) — invert \(A\) first, then OR with \(B\):
| \(\overline A\) | \(=\) | \(\overline{1} = 0\) |
| \(Y\) | \(=\) | \(0 \lor 0\) |
| \(=\) | \(0\) |
(ii) \(A=0,\ B=0\):
| \(\overline A\) | \(=\) | \(\overline{0} = 1\) |
| \(Y\) | \(=\) | \(1 \lor 0\) |
| \(=\) | \(1\) |
(iii) Expression computed:
| \(Y\) | \(=\) | \(\overline A \lor B\) |
(i) \(Y=0\); (ii) \(Y=1\); (iii) the circuit computes \(\overline A \lor B\).
Factor out \(A\); the bracket is absorbed (absorption law):
| \(A \lor (A \land B)\) | \(=\) | \((A \land 1) \lor (A \land B)\) |
| \(=\) | \(A \land (1 \lor B)\) | |
| \(=\) | \(A \land 1\) | |
| \(=\) | \(A\) |
\(Y = A\): the output is just the wire \(A\), so the simplified circuit needs \(0\) gates.
Factor out the common \(A\), then use \(B \lor \overline B = 1\):
| \((A \land B) \lor (A \land \overline B)\) | \(=\) | \(A \land (B \lor \overline B)\) |
| \(=\) | \(A \land 1\) | |
| \(=\) | \(A\) |
The circuit is equivalent to \(A\) alone — no gates are needed.
Common pitfalls
Frequently asked questions
What is a logic gate?
A logic gate is a component that takes one or two binary inputs (each \(0\) or \(1\)) and produces a single binary output according to a fixed rule. The six standard gates are AND, OR, NOT, NAND, NOR and XOR, and each is described by a truth table and a Boolean expression.
What is the difference between AND and NAND?
NAND is “not-and”: it is an AND gate followed by an inverter, shown by a bubble on the output. So \(\overline{A\land B}\) is the exact opposite of \(A\land B\) — it outputs \(0\) only for \((1,1)\) and \(1\) for every other input.
What does an XOR gate do?
An XOR (exclusive-or) gate outputs \(1\) exactly when its two inputs differ, and \(0\) when they are equal. In AND/OR/NOT form, \(A\oplus B=(A\land\overline B)\lor(\overline A\land B)\).
How do I find the Boolean expression a circuit computes?
Trace the signal from left to right. Write the expression at the output of each gate, using earlier outputs as the inputs of later gates, until you reach the final wire. For example, an AND gate feeding an OR gate with a third input \(C\) computes \((A\land B)\lor C\).
What are De Morgan's laws?
They relate the complement of a bracket to the complements of its parts: \(\overline{A\land B}=\overline A\lor\overline B\) and \(\overline{A\lor B}=\overline A\land\overline B\). The operator flips between \(\land\) and \(\lor\), and every variable is complemented.
How do I simplify a circuit?
Write the Boolean expression the circuit computes, then apply the laws of Boolean algebra — absorption, distributive, complement and De Morgan — to reach the simplest equivalent expression. Redraw the circuit from that expression; it will use fewer gates while giving the same output.