Boolean Algebra and Logic Gate Circuits

Underneath every program, every calculation and every decision a computer makes lies a layer of pure binary logic: logic gates wired together to compute Boolean functions. At A-Level you must go well beyond naming the gates. You need to read a truth table, derive a Boolean expression from a gate circuit (and vice versa), apply the laws of Boolean algebra — including De Morgan's laws — to simplify expressions, and, as a powerful systematic alternative, use Karnaugh maps. Simplification is not academic: every gate removed from a circuit is silicon, power and propagation delay saved. This lesson develops all of this with full truth tables, gate diagrams drawn as mermaid flowcharts, and step-by-step algebraic simplifications written in proper notation.

---

Spec Mapping

This lesson addresses the AQA A-Level Computer Science (7517) specification within §4.6 Fundamentals of computer systems, specifically §4.6.4 logic gates — the function and truth tables of the AND, OR, NOT, XOR, NAND and NOR gates — and §4.6.5 Boolean algebra — constructing and simplifying Boolean expressions, applying the laws of Boolean algebra (commutation, association, distribution, double negation, De Morgan's laws and the standard identities), and converting between truth tables, Boolean expressions and logic-gate circuits.

It links forwards to the adder and flip-flop lesson (gates assembled into arithmetic and memory circuits) and to §4.5.4 binary addition, and rests on the binary representation of §4.5.

---

Boolean Operators and Their Gates

A logic gate is a physical electronic circuit (built from transistors) that computes one Boolean function of its inputs. Gates are combinational: the output depends only on the inputs present right now, with no memory of the past. There are six gates you must know. In Boolean notation we write AND as a dot ($A \cdot B$A⋅B), OR as a plus ($A + B$A+B), NOT as an overbar ($\overline{A}$A) and XOR as $\oplus$⊕. NAND and NOR are the negations of AND and OR.

Gate	Boolean notation	Output is 1 when…
AND	$A \cdot B$A⋅B	both inputs are 1
OR	$A + B$A+B	at least one input is 1
NOT	$\overline{A}$A	the input is 0 (it inverts)
XOR	$A \oplus B$A⊕B	the inputs differ
NAND	$\overline{A \cdot B}$A⋅B	not both inputs are 1
NOR	$\overline{A + B}$A+B​	neither input is 1

A few notes that prevent common slips. The NOT gate (inverter) is the only one with a single input. AND and OR generalise naturally to more than two inputs — a three-input AND is 1 only when all three are 1, and a three-input OR is 1 when any is 1. XOR is the "difference detector": for two inputs it is 1 when they disagree, which makes it the natural gate for comparing bits and (as the next lesson shows) for the sum bit of an adder. NAND and NOR are simply AND and OR followed by an inverter — but they are far more than afterthoughts, because each is functionally complete: any Boolean function whatever can be built from NAND gates alone, or from NOR gates alone, which is why real chips are often fabricated predominantly from one of them.

The fundamental truth table

Every two-input function above can be read off this single table:

A	B	$A \cdot B$A⋅B	$A + B$A+B	$\overline{A}$A	$A \oplus B$A⊕B	$\overline{A \cdot B}$A⋅B	$\overline{A + B}$A+B​
0	0	0	0	1	0	1	1
0	1	0	1	1	1	1	0
1	0	0	1	0	1	1	0
1	1	1	1	0	0	0	0

Notice the columns confirm the definitions: NAND ($\overline{A \cdot B}$A⋅B) is the exact inverse of the AND column, and NOR ($\overline{A + B}$A+B​) is the exact inverse of the OR column.

Building XOR from basic gates

XOR is sometimes treated as a "primitive", but it is worth seeing that it is just a combination of the three basic gates — a good demonstration of expression-to-circuit thinking. XOR is 1 when the inputs differ, i.e. when ($A = 1$A=1 and $B = 0$B=0) or when ($A = 0$A=0 and $B = 1$B=1). Writing that as sum of products:

$A \oplus B = A \cdot \overline{B} + \overline{A} \cdot B$A⊕B=A⋅B+A⋅B

As a circuit this is two NOT gates, two AND gates and one OR gate:

flowchart LR
    A((A)) --> NB_AND{{"AND"}}
    B((B)) --> NOTB{{"NOT"}}
    NOTB --> NB_AND
    A --> NOTA{{"NOT"}}
    NOTA --> NA_AND{{"AND"}}
    B((B)) --> NA_AND
    NB_AND --> OR{{"OR"}}
    NA_AND --> OR
    OR --> Q["Q = A XOR B"]

Check it against the truth table: when $A=1, B=0$A=1,B=0 the top AND gives 1; when $A=0, B=1$A=0,B=1 the bottom AND gives 1; in both the all-same cases ($00$00 and $11$11) both ANDs give 0, so the OR outputs 0 — exactly the XOR column. This decomposition matters because the next lesson's half adder uses XOR for its sum bit, so knowing XOR is "really" five basic gates explains the true gate cost of an adder.

---

From Circuit to Boolean Expression

A frequent exam task is to read a gate diagram and write down the expression it computes. Take this circuit:

flowchart LR
    A((A)) --> AND{{"AND"}}
    B((B)) --> AND
    A --> NOT{{"NOT"}}
    NOT --> OR{{"OR"}}
    C((C)) --> OR
    AND --> OR2{{"OR"}}
    OR --> OR2
    OR2 --> Q["Q"]

Work outward from the inputs, naming each gate's output:

• the AND gate produces $A \cdot B$A⋅B;
• the NOT gate produces $\overline{A}$A;
• the first OR gate combines that with C to give $\overline{A} + C$A+C;
• the final OR gate combines the two intermediate results:

$Q = (A \cdot B) + (\overline{A} + C)$Q=(A⋅B)+(A+C)

Going the other way — expression to circuit — you simply build one gate per operator, feeding inputs in the order the brackets dictate. This two-way fluency between truth table ↔ expression ↔ circuit is the core skill the spec demands.

From Truth Table to Expression: the sum-of-products method

The third corner of the triangle is going from a truth table to a Boolean expression. The reliable method is sum of products (SoP): write one product (AND) term for every row where the output is 1, then OR all those terms together. For each such row, a variable that is 1 appears as itself, and a variable that is 0 appears complemented.

Take a function $Q$Q of three inputs with this truth table:

A	B	C	Q
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

There are three rows where $Q = 1$Q=1. Reading each as a product term:

• Row $A=0, B=1, C=0$A=0,B=1,C=0 gives $\overline{A} \cdot B \cdot \overline{C}$A⋅B⋅C.
• Row $A=1, B=0, C=1$A=1,B=0,C=1 gives $A \cdot \overline{B} \cdot C$A⋅B⋅C.
• Row $A=1, B=1, C=1$A=1,B=1,C=1 gives $A \cdot B \cdot C$A⋅B⋅C.

OR them together for the unsimplified expression:

$Q = \overline{A} \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C + A \cdot B \cdot C$Q=A⋅B⋅C+A⋅B⋅C+A⋅B⋅C

This expression is guaranteed correct — it reproduces the table exactly — but it is rarely minimal. The simplification techniques below (or a Karnaugh map) then reduce it to the fewest gates. The SoP method is the dependable bridge from a specification ("the output should be 1 when…") to a working expression, and it is the starting point for almost every circuit-design question.

---

Boolean Algebra Laws

To simplify expressions you must know and apply these laws. They are stated below in proper notation. Each law is a provable equivalence — you could verify any of them by drawing up the truth tables of both sides and checking they match in every row. In practice you memorise them and apply them as rewrite rules, much as you use the rules of ordinary algebra. The pay-off is a smaller circuit: every operator a law lets you remove is one fewer gate to build, power and wait for.

Single-variable identities

Law	AND form	OR form
Identity	$A \cdot 1 = A$A⋅1=A	$A + 0 = A$A+0=A
Null / annulment	$A \cdot 0 = 0$A⋅0=0	$A + 1 = 1$A+1=1
Idempotent	$A \cdot A = A$A⋅A=A	$A + A = A$A+A=A
Complement	$A \cdot \overline{A} = 0$A⋅A=0	$A + \overline{A} = 1$A+A=1
Double negation	$\overline{\overline{A}} = A$A=A

Structural laws

Law	AND form	OR form
Commutation	$A \cdot B = B \cdot A$A⋅B=B⋅A	$A + B = B + A$A+B=B+A
Association	$(A \cdot B) \cdot C = A \cdot (B \cdot C)$(A⋅B)⋅C=A⋅(B⋅C)	$(A + B) + C = A + (B + C)$(A+B)+C=A+(B+C)
Distribution	$A \cdot (B + C) = A \cdot B + A \cdot C$A⋅(B+C)=A⋅B+A⋅C	$A + (B \cdot C) = (A + B) \cdot (A + C)$A+(B⋅C)=(A+B)⋅(A+C)
Absorption	$A \cdot (A + B) = A$A⋅(A+B)=A	$A + A \cdot B = A$A+A⋅B=A

De Morgan's laws

These are the most heavily examined laws of all:

$\overline{A \cdot B} = \overline{A} + \overline{B} \qquad \overline{A + B} = \overline{A} \cdot \overline{B}$A⋅B=A+BA+B​=A⋅B

In words: the complement of an AND is the OR of the complements, and the complement of an OR is the AND of the complements.

De Morgan's laws have a direct gate-level meaning that explains why they are so important in real design. Reading the first law from the left, $\overline{A \cdot B}$A⋅B is a NAND gate; from the right it is an OR gate fed by two inverters. So a NAND is equivalent to an OR-with-inverted-inputs, and likewise (second law) a NOR is equivalent to an AND-with-inverted-inputs. This equivalence is what lets engineers convert a circuit built from AND/OR/NOT into one built entirely from NAND (or entirely from NOR) gates — which is exactly how chips are economically fabricated from a single repeated gate type. De Morgan's is therefore not just an algebra trick; it is the bridge between the convenient AND/OR/NOT notation and the NAND/NOR gates hardware actually prefers.

Exam Tip: Apply De Morgan's in three mechanical steps — (1) break the long bar, (2) swap the operator ($\cdot \leftrightarrow +$⋅↔+), (3) complement each remaining term. Doing these in order avoids the classic error of swapping the operator but forgetting to negate the variables.

---

Worked De Morgan's Simplification, Step by Step

Problem. Simplify $Q = \overline{\overline{A} + \overline{B}}$Q=A+B​.

Work line by line, naming the law used at each step:

$Q = \overline{\overline{A} + \overline{B}}$Q=A+B​

Apply De Morgan's to the whole expression — break the outer bar, swap OR to AND, complement each term:

$Q = \overline{\overline{A}} \cdot \overline{\overline{B}}$Q=A⋅B

Apply double negation to each factor ($\overline{\overline{A}} = A$A=A and $\overline{\overline{B}} = B$B=B):

$Q = A \cdot B$Q=A⋅B

So the four-operator expression collapses to a single AND gate. A circuit that originally needed two NOT gates, an OR gate and a final NOT gate is logically identical to one AND gate — three gates saved.

A second worked simplification shows the laws combining. Simplify $Q = A \cdot B + A \cdot \overline{B}$Q=A⋅B+A⋅B:

$Q = A \cdot B + A \cdot \overline{B}$Q=A⋅B+A⋅B

Factor out the common $A$A (distribution in reverse):

$Q = A \cdot (B + \overline{B})$Q=A⋅(B+B)

Apply the complement law $B + \overline{B} = 1$B+B=1:

$Q = A \cdot 1$Q=A⋅1

Apply the identity law $A \cdot 1 = A$A⋅1=A:

$Q = A$Q=A

A third, using absorption. Simplify $Q = \overline{A} \cdot B + A \cdot B + A \cdot \overline{B}$Q=A⋅B+A⋅B+A⋅B:

$Q = B \cdot (\overline{A} + A) + A \cdot \overline{B} = B \cdot 1 + A \cdot \overline{B} = B + A \cdot \overline{B}$Q=B⋅(A+A)+A⋅B=B⋅1+A⋅B=B+A⋅B

Now apply the identity $B + A \cdot \overline{B} = A + B$B+A⋅B=A+B (a standard absorption-style result, since the $\overline{B}$B term can only contribute when $B = 0$B=0):

$Q = A + B$Q=A+B

A fourth, longer simplification ties several laws together and is closer to exam difficulty. Simplify

$Q = A \cdot B + A \cdot B \cdot C + A \cdot \overline{B}.$Q=A⋅B+A⋅B⋅C+A⋅B.

First, the middle term $A \cdot B \cdot C$A⋅B⋅C is absorbed by $A \cdot B$A⋅B, because $A \cdot B + A \cdot B \cdot C = A \cdot B \cdot (1 + C) = A \cdot B \cdot 1 = A \cdot B$A⋅B+A⋅B⋅C=A⋅B⋅(1+C)=A⋅B⋅1=A⋅B (null and identity laws). The expression becomes:

$Q = A \cdot B + A \cdot \overline{B}.$Q=A⋅B+A⋅B.

Now factor out $A$A:

$Q = A \cdot (B + \overline{B}).$Q=A⋅(B+B).

Apply the complement law ($B + \overline{B} = 1$B+B=1) and then the identity law:

$Q = A \cdot 1 = A.$Q=A⋅1=A.

So a three-term, six-operator expression reduces to the single variable $A$A — a circuit of several gates replaced by a plain wire from input $A$A to output. Always scan for an absorbing term first (here $A \cdot B$A⋅B swallowing $A \cdot B \cdot C$A⋅B⋅C), because removing redundant terms early makes the rest of the simplification far easier.