What are boolean expressions?

A Boolean expression describes a circuit algebraically, for example Q = (A B) C. Build it by combining the gate operations; evaluate it row by row to get its truth table.

SEAB Original-style practice: (a) Write the truth table for the Boolean expression Q = (A B) C. (b) State how many rows a truth table for three inputs has and why.

(a) Evaluate A \ B (AND), then OR it with \ C (NOT C): | A | B | C | A AND B | NOT C | Q | | - | - | - | ------- | ----- | - | | 0 | 0 | 0 | 0 | 1 | 1 | | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | 1 | 0 | 0 | 1 | 1 | | 0 | 1 | 1 | 0 | 0 | 0 | | 1 | 0 | 0 | 0 | 1 | 1 | | 1 | 0 | 1 | 0 | 0 | 0 | | 1 | 1 | 0 | 1 | 1 | 1 | | 1 | 1 | 1 | 1 | 0 | 1 | (b) Three inputs give 2^3 = 8 rows, because each input is independently 0 or 1, and there are 2 \× 2 \× 2 combinations. Markers reward the correctly evaluated intermediate columns and Q, and 2^3 = 8 rows with the reason that each of three inputs has two possible values.

SingaporeComputer ScienceSyllabus dot point

How are logical decisions built from gates, and how do we simplify Boolean expressions?

Construct and interpret logic gates and truth tables, write Boolean expressions, and simplify them using Boolean algebra laws

A focused answer to the H2 Computing outcome on digital logic. The AND, OR, NOT, NAND, NOR and XOR gates, building and reading truth tables, writing Boolean expressions, and simplifying them with Boolean algebra laws and De Morgan.

Generated by Claude Opus 4.89 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to construct and interpret logic gates and truth tables, write Boolean expressions, and simplify them using Boolean algebra. The central idea is that all digital computation is built from a few simple gates, that a truth table fully specifies a circuit's behaviour, and that Boolean algebra lets you reduce an expression to fewer gates.

The answer

The logic gates

A logic gate outputs a 1 or 0 from its binary inputs. The core gates:

Gate	Symbol in expressions	Output is 1 when
AND	$A \land B$	both inputs are 1
OR	$A \lor B$	at least one input is 1
NOT	$\lnot A$	the input is 0 (it inverts)
NAND	$\lnot(A \land B)$	NOT of AND
NOR	$\lnot(A \lor B)$	NOT of OR
XOR	$A \oplus B$	the inputs differ

Truth tables

A truth table lists the output for every input combination. With $n$ inputs there are $2^n$ rows, since each input is independently 0 or 1:

A	B	A AND B	A OR B	A XOR B
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

The truth table completely defines what a circuit does.

Boolean expressions

A Boolean expression describes a circuit algebraically, for example $Q = (A \land B) \lor \lnot C$ . Build it by combining the gate operations; evaluate it row by row to get its truth table.

Boolean algebra laws

Boolean algebra lets you simplify expressions to use fewer gates (cheaper, faster circuits). Key laws:

Identity: $A \land 1 = A$ , $A \lor 0 = A$ .
Null: $A \land 0 = 0$ , $A \lor 1 = 1$ .
Idempotent: $A \land A = A$ , $A \lor A = A$ .
Complement: $A \land \lnot A = 0$ , $A \lor \lnot A = 1$ .
De Morgan's laws: $\lnot(A \land B) = \lnot A \lor \lnot B$ and $\lnot(A \lor B) = \lnot A \land \lnot B$ .

Universal gates

NAND (and NOR) is a universal gate: every other gate, and therefore any circuit, can be built from NAND alone. This matters in manufacturing - a chip can be made from one repeated gate type.

Worked example

Simplify the Boolean expression $Q = A \land (A \lor B)$ and confirm with a truth table.

Step 1: Apply the absorption idea

Consider what $A \land (A \lor B)$ depends on. Whenever $A = 0$ , the AND makes $Q = 0$ . Whenever $A = 1$ , $(A \lor B)$ is 1, so $Q = A \land 1 = 1$ .

Step 2: State the simplification

So $Q$ equals $A$ in every case: $A \land (A \lor B) = A$ (the absorption law). The expression reduces to a single wire, no gates needed.

Step 3: Build the truth table to confirm

A	B	A OR B	A AND (A OR B)
0	0	0	0
0	1	1	0
1	0	1	1
1	1	1	1

Step 4: Compare with A

The final column matches column $A$ exactly in all four rows, confirming $A \land (A \lor B) = A$ . The simplification removes two gates.

Examples in context

Example 1. Building an adder. A half-adder that adds two bits uses an XOR gate for the sum and an AND gate for the carry. Chaining full-adders (made from these gates) builds the multi-bit adder inside the ALU, so the arithmetic you do in two's complement ultimately runs on a handful of logic gates.

Example 2. Simplifying to cut cost. A circuit designer reduces a control expression with Boolean algebra before fabrication, because each removed gate saves silicon area, power and propagation delay. De Morgan's laws also let a designer rebuild a circuit using only NAND gates, exploiting NAND's universality for cheaper manufacturing.

Try this

Q1. How many rows does a truth table with four inputs have, and why? [2 marks]

Cue. $2^4 = 16$ rows, because each of the four inputs is independently 0 or 1.

Q2. State De Morgan's law for the negation of an AND. [1 mark]

Cue. $\lnot(A \land B) = \lnot A \lor \lnot B$ .

Q3. Why is NAND called a universal gate? [2 marks]

Cue. Every other gate, and hence any circuit, can be constructed from NAND gates alone, so a chip can be made from one repeated gate type.

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original6 marks(a) Write the truth table for the Boolean expression

Q = (A \land B) \lor \lnot C

. (b) State how many rows a truth table for three inputs has and why.

Show worked answer →

(a) Evaluate $A \\land B$ (AND), then OR it with $\\lnot C$ (NOT C):

A	B	C	A AND B	NOT C	Q
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

(b) Three inputs give $2^3 = 8$ rows, because each input is independently 0 or 1, and there are $2 \\times 2 \\times 2$ combinations.

Markers reward the correctly evaluated intermediate columns and Q, and $2^3 = 8$ rows with the reason that each of three inputs has two possible values.

Original5 marks(a) State De Morgan's two laws in Boolean algebra. (b) Simplify the expression

\lnot(\lnot A \lor \lnot B)

using De Morgan's law and state the single gate it is equivalent to. (c) Why is the NAND gate called a universal gate?

Show worked answer →

(a) De Morgan's laws:

\\lnot(A \\land B) = \\lnot A \\lor \\lnot B \\qquad \\lnot(A \\lor B) = \\lnot A \\land \\lnot B

In words: the negation of an AND is the OR of the negations, and the negation of an OR is the AND of the negations.

(b) Apply De Morgan to $\\lnot(\\lnot A \\lor \\lnot B)$ : this equals $\\lnot(\\lnot A) \\land \\lnot(\\lnot B) = A \\land B$ . So the expression simplifies to $A \\land B$ , which is a single AND gate.

(c) NAND is universal because every other gate (NOT, AND, OR, and hence any circuit) can be built from NAND gates alone. This is valuable because a chip can be manufactured from one repeated gate type. (NOR is universal too.)

Markers reward both De Morgan laws, the simplification to $A \\land B$ (an AND gate), and NAND universality (any function buildable from NAND alone).