Every decision a computer makes, every conditional in your code, every circuit in the hardware, comes down to logic. This section covers the gates, the notation, and the algebra that ties them together.
●
EveryoneBoolean algebra appears in Unit 1 of the A Level (paper) and underpins everything in Unit 2 (hardware). Work through all of this section, including the circuit example and De Morgan's laws.
Boolean values
Boolean logic deals with values that are either true or false, and nothing in between. In computing, true is represented as 1 and false as 0. This connects directly to the binary you studied in section 02: every bit in a computer is a Boolean value.
The subject is named after George Boole, a 19th-century mathematician who developed an algebra for logical reasoning. He was working in pure mathematics decades before computers existed. The fact that his work turned out to describe the behaviour of electronic circuits was a coincidence that shaped the entire history of computing.
●
New to CSYou already use Boolean logic every time you write an if statement in Python. if x > 5 and y < 10: evaluates two Boolean expressions and combines them with AND. This section gives you the formal tools to reason about that kind of logic precisely.
The three basic gates
Logic gates are the physical building blocks of computer hardware. Each gate takes one or more binary inputs and produces a binary output according to a fixed rule. There are three fundamental gates that every other gate is built from.
AND
A AND B | A · B
A
B
Q
0
0
0
0
1
0
1
0
0
1
1
1
Output is 1 only when both inputs are 1. Think of it as: A and B must be true.
OR
A OR B | A + B
A
B
Q
0
0
0
0
1
1
1
0
1
1
1
1
Output is 1 when at least one input is 1. Think: A or B (or both) must be true.
NOT
NOT A | Â
A
Q
0
1
1
0
Inverts the input. Output is the opposite of the input. Also called an inverter. The small circle on the output symbol indicates inversion.
Additional gates
Three more gates appear regularly at A Level. Each is a combination of the basic three: NAND is NOT AND, NOR is NOT OR, and XOR is a special gate with its own useful properties.
NAND
NOT (A AND B)
A
B
Q
0
0
1
0
1
1
1
0
1
1
1
0
Output is 0 only when both inputs are 1. The opposite of AND. NAND gates are practically important: any logic circuit can be built from NAND gates alone.
NOR
NOT (A OR B)
A
B
Q
0
0
1
0
1
0
1
0
0
1
1
0
Output is 1 only when both inputs are 0. Like NAND, NOR gates alone can implement any logic circuit.
XOR
A XOR B | A ⊕ B
A
B
Q
0
0
0
0
1
1
1
0
1
1
1
0
Exclusive OR: output is 1 when inputs are different. Used in binary adders and encryption. Note how it differs from OR: XOR outputs 0 when both inputs are 1.
Boolean expressions
Rather than drawing circuit diagrams every time, we write Boolean expressions using algebraic notation. The three operators map to the three basic gates:
Operation
Symbol
Example
AND
· or no symbol
A · B
OR
+
A + B
NOT
overline or '
A' or Â
●
New to CSThe + symbol means OR here, not addition. The dot means AND, not multiplication. It looks like arithmetic but it is not. Boolean algebra has its own rules, and 1 + 1 = 1 (because true OR true = true). This is one of the places where careful reading matters.
Reading an expression
Take this expression:
Expression
Q = (A · B) +C
Read left to right with standard operator precedence: NOT is applied first, then AND, then OR (just like multiply before add in normal algebra). Brackets override precedence as usual.
This expression says: Q is true if (A AND B) is true, OR if C is false (NOT C). To evaluate it for given inputs, substitute the values and work through the operators in order.
●
Precedence orderNOT → AND → OR. When in doubt, add brackets to make the intended order explicit. Exam questions often test whether you apply precedence correctly without brackets.
Building a truth table for a circuit
When a circuit combines multiple gates, you build the truth table column by column, working from inputs through each intermediate result to the final output.
Consider this circuit and expression:
To build the full truth table, add a column for each intermediate result (here, P = A AND B, and C' = NOT C) before calculating Q:
A
B
C
P = A·B
C'
Q = P + C'
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
●
How many rows?A truth table with n inputs has 2n rows, because each input can be 0 or 1. Two inputs = 4 rows. Three inputs = 8 rows. Four inputs = 16 rows. Fill the input columns in binary counting order (000, 001, 010...) to make sure you cover every combination.
De Morgan's laws
De Morgan's laws are two rules for simplifying Boolean expressions that involve NOT applied to a compound expression. They appear frequently in exam questions and in real circuit design.
De Morgan's laws
A · B
=
A + B
NOT (A AND B) equals (NOT A) OR (NOT B). To negate an AND expression: flip each variable and change AND to OR.
A + B
=
A · B
NOT (A OR B) equals (NOT A) AND (NOT B). To negate an OR expression: flip each variable and change OR to AND.
A useful way to remember them: when you push NOT inside the brackets, each variable gets negated and the operator flips (AND becomes OR, OR becomes AND).
Worked example
Simplify: NOT (A AND NOT B)
Using De Morgan's first law
1Apply De Morgan's: negate each variable, flip AND to OR.A' + (B')'
2Double negation cancels: NOT NOT B = B.A' + B
●
ExtensionDe Morgan's laws are the reason NAND and NOR gates are called "universal gates": any Boolean expression can be rewritten using only NAND (or only NOR) by applying De Morgan's repeatedly. This matters in chip manufacturing because it is cheaper to produce a single type of gate in bulk. The original Intel 4004 processor was built largely from NAND gates.
Practice questions
Try each question before revealing the answer.
Q1What is the output of an AND gate when A = 1 and B = 0?
0
AND outputs 1 only when both inputs are 1.
Q2Complete the truth table for Q = A XOR B XOR C.
Hint: evaluate left to right: (A XOR B) first, then XOR with C.
Q = 1 when an odd number of inputs are 1:
A
B
C
Q
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
Q3Evaluate Q = (A + B) · C' when A = 0, B = 1, C = 1.
0
A + B = 0 + 1 = 1. C' = NOT 1 = 0. Q = 1 AND 0 = 0.
Q4Apply De Morgan's law to simplify: NOT (P OR Q).
P' · Q'
NOT (A OR B) = NOT A AND NOT B. Each variable is negated and OR becomes AND.
Q5A circuit outputs 1 only when exactly one of its two inputs is 1. Which gate is this? Write its Boolean expression.
XOR gate | Q = A ⊕ B
XOR outputs 1 when inputs are different. "Exactly one input is 1" is another way of saying "inputs are different when one is 0 and one is 1".
Q6Simplify NOT (A' · B) using De Morgan's law and Boolean identities.
A + B'
Step 1: De Morgan's gives (A')' + B'. Step 2: Double negation (A')' = A. Result: A + B'.