Combinational Logic
Every digital system, however complicated, is built out of a small handful of simple decision-making building blocks called logic gates. Before any counter, timer, or memory can be understood, you need to know exactly what these six gates do — and be fluent in reading and writing their truth tables.
Combinational versus sequential logic
A combinational logic circuit is one whose output depends only on the current combination of its inputs. Feed it the same set of inputs twice, on two completely separate occasions, and you get exactly the same output both times — the circuit has no way of "remembering" anything that happened before. Every gate covered in this lesson, and every circuit built purely from them, behaves this way.
This is worth contrasting early with sequential logic, covered later in this topic, where a circuit's output can depend on past inputs as well as present ones — it has some form of memory or stored state. A counter is the classic example: its output at any moment depends on how many clock pulses it has already counted, not just on what's happening on its input pins right now. For this lesson and the next, though, everything is combinational: no memory, no history, just inputs determining outputs instantly and completely.
Each gate takes one or more binary inputs (each either 0 or 1, representing "low" and "high" logic levels) and produces a single binary output. What makes a gate a useful building block is that you never need to know how it produces that output internally — only what output it produces for each possible combination of inputs. That input-output behaviour is completely captured in a truth table, which lists every possible input combination alongside the resulting output.
Gates are treated here purely as building blocks with known, fixed input-output behaviour. The internal transistor-level circuitry that actually implements a gate — how transistors are wired together to produce AND or OR behaviour — is not required knowledge for this course. What matters is fluency with each gate's truth table and Boolean notation.
The six named gates
There are six logic gates named explicitly in this topic. Five take two inputs; NOT is the exception, taking just one.
NOT
The NOT gate is the simplest possible gate: it takes a single input and inverts it. Its Boolean notation is $\bar{A}$ (read "not A" or "A bar").
| A | $\bar{A}$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND
The AND gate's output is 1 only when both inputs are 1. Its Boolean notation is $A \cdot B$.
| A | B | $A \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR
The OR gate's output is 1 when at least one input is 1. Its Boolean notation is $A + B$.
| A | B | $A + B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NAND
NAND is AND followed by NOT — its output is the opposite of AND's at every row. Output is 0 only when both inputs are 1, and 1 otherwise. Its Boolean notation is $\overline{A \cdot B}$.
| A | B | $\overline{A \cdot B}$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR
NOR is OR followed by NOT. Output is 1 only when both inputs are 0. Its Boolean notation is $\overline{A+B}$.
| A | B | $\overline{A+B}$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
EOR (exclusive OR / XOR)
The exclusive OR gate's output is 1 when the two inputs differ, and 0 when they're the same. It's easy to confuse with ordinary OR, so it's worth noting precisely where they diverge: for inputs $A=1,B=1$, OR gives 1 but EOR gives 0.
| A | B | $A \oplus B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| A | B | X = A·B | Q = X̄ |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
This step-by-step approach — label every intermediate signal, then work through the gates in order for each row of inputs — is exactly the skill the next lesson builds on when circuits get larger and more deliberately designed.
NAND and NOR each have a remarkable property: every other gate function covered in this lesson — NOT, AND, OR, and by extension any combinational circuit at all — can be built using only NAND gates, or entirely separately, using only NOR gates. Neither AND nor OR nor NOT has this property on its own. This is why NAND and NOR are called universal gates, and it's the whole reason manufacturers can build complex digital systems economically from a single repeated gate type. The next lesson works through exactly how NOT, AND and OR are reconstructed from NAND gates alone.
Key takeaways
- Combinational logic circuits have outputs depending only on the current input combination, with no memory of past inputs — unlike sequential logic, covered later.
- NOT inverts a single input: $\bar{A}$.
- AND ($A \cdot B$) is 1 only when both inputs are 1; OR ($A+B$) is 1 when at least one input is 1.
- NAND ($\overline{A \cdot B}$) and NOR ($\overline{A+B}$) are AND/OR each followed by an inversion, flipping every row of the corresponding table.
- EOR (exclusive OR) is 1 exactly when its two inputs differ, distinguishing it from ordinary OR at the A=B=1 row.
- Gates are used here purely as known input-output building blocks — their internal transistor circuitry is not required knowledge.
- Tracing a multi-gate circuit's truth table means labelling every intermediate signal and propagating each input row through the gates in order.
- NAND and NOR are "universal" gates: any other gate function can be built from NAND alone, or from NOR alone — a preview of the next lesson.