Logic gates and Boolean algebra – A-level Computer Science exam questions with mark scheme

1Core3 marks

A student is comparing three two-input logic gates.

A	B	$\overline{A \cdot B}$ (NAND)	$\overline{A + B}$ (NOR)	$A \oplus B$ (XOR)
0	0
0	1
1	0
1	1

Complete the truth table by giving the output of each gate for every combination of inputs A and B. [3]

NAND column correct: 1, 1, 1, 0(1)
NOR column correct: 1, 0, 0, 0(1)
XOR column correct: 0, 1, 1, 0(1)
Answer: NAND: 1,1,1,0; NOR: 1,0,0,0; XOR: 0,1,1,0 (rows in order 00, 01, 10, 11)
Examiner tip: Students who mix up NAND and NOR lose two marks at once: NAND is 0 only when both inputs are 1; NOR is 1 only when both inputs are 0.

2Standard4 marks

The diagram shows a logic circuit with inputs A, B and C and output Q.

(a) Write a Boolean expression for the output Q in terms of A, B and C. [2]

(b) State the value of Q for each of these input combinations. [2]

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

(a) $\overline{A + B}$ identified as one input to the final gate (allow $\overline{A} \cdot \overline{B}$; allow A NOR B)(1)
(a) complete expression $Q = \overline{A + B} \oplus (B \cdot C)$; accept equivalent notation, e.g. NOT(A OR B) XOR (B AND C); brackets must make the order of operations clear(1)
(b) two rows correct (1 mark)(1)
(b) all three rows correct: Q = 1, 0, 1(1)
Answer: (a) $Q = \overline{A + B} \oplus (B \cdot C)$ (b) 1, 0, 1
Examiner tip: Many lose both (a) marks by writing $\overline{A} + B$: the bar must extend over the whole of A + B because the bubble is on the output of the OR shape.

3Standard3 marks

Using the laws of Boolean algebra, simplify the expression

$$(A + B) \cdot (A + \overline{B})$$

You must show your working. [3]

Expands the brackets correctly: $A \cdot A + A \cdot \overline{B} + B \cdot A + B \cdot \overline{B}$(1)
Uses $A \cdot A = A$ and $B \cdot \overline{B} = 0$ to reach $A + A \cdot \overline{B} + A \cdot B$ (or equivalent)(1)
Final answer $A$ with valid justification, e.g. factorising $A \cdot (1 + \overline{B} + B) = A \cdot 1 = A$, or absorption $A + A \cdot X = A$; allow alternative route $A + (B \cdot \overline{B}) = A + 0 = A$ by the distributive law (award all 3 marks for a fully correct alternative); answer $A$ with no valid working scores 1 mark only(1)
Answer: $A$
Examiner tip: The final mark needs a valid justification (e.g. absorption, $1 + X = 1$ or $B \cdot \overline{B} = 0$); writing just the answer A with no working scores at most 1.

Stuck on Logic gates and Boolean algebra?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4Hard3 marks

Use De Morgan's laws and other Boolean identities to simplify

$$\overline{\overline{A} + B} + \overline{A + \overline{B}}$$

Name the single logic gate that is equivalent to the simplified expression. [3]

Applies De Morgan's law to one term correctly, e.g. $\overline{\overline{A} + B} = \overline{\overline{A}} \cdot \overline{B} = A \cdot \overline{B}$(1)
Applies De Morgan's law to the second term and removes double negation: $\overline{A + \overline{B}} = \overline{A} \cdot B$, giving $A \cdot \overline{B} + \overline{A} \cdot B$(1)
XOR gate (allow exclusive OR; allow $A \oplus B$); do not award for NOR / XNOR(1)
Answer: $A \cdot \overline{B} + \overline{A} \cdot B = A \oplus B$, an XOR gate
Examiner tip: When applying De Morgan, students often change the operator but forget to invert each term; $\overline{X + Y} = \overline{X} \cdot \overline{Y}$, and $\overline{\overline{A}} = A$.

5Standard5 marks

The diagram shows a circuit with inputs A and B and outputs S and C. Gates X and Y are different types of gate.

(a) Identify gate X and gate Y. [2]

(b) Complete a truth table showing S and C for all four combinations of A and B. [2]

(c) This circuit is a half-adder. Explain why a half-adder alone is not suitable for adding the second bit of two binary numbers. [1]

(a) X is an XOR gate (allow exclusive OR)(1)
(a) Y is an AND gate(1)
(b) S column correct: 0, 1, 1, 0 (rows 00, 01, 10, 11)(1)
(b) C column correct: 0, 0, 0, 1(1)
(c) It has only two inputs so it cannot add in the carry from the previous (less significant) column; accept: a full adder is needed to accept a carry in(1)
Answer: (a) X = XOR, Y = AND (b) S: 0,1,1,0; C: 0,0,0,1 (c) it cannot take a carry-in from the column before
Examiner tip: In (c) 'it can only add two bits' is not enough; you must link the missing input to the carry from the previous column.

6Hard5 marks

The diagram shows a full-adder built from two half-adders and an OR gate. P, R and T are internal connections.

The inputs are A = 1, B = 0 and C_in = 1.

(a) State the values of P and T. [2]

(b) State the values of the outputs S and C_out. [2]

(a) P = 1(1)
(a) T = 1(1)
(b) S = 0(1)
(b) C_out = 1 (allow follow-through from their T, with R = 0)(1)
(c) Four full-adders connected in a chain / cascade, with the C_out of each adder connected to the C_in of the adder for the next more significant bit (accept: first adder's C_in set to 0 / half-adder used for the least significant bit)(1)
Answer: (a) P = 1, T = 1 (b) S = 0, C_out = 1 (1 + 0 + 1 = 10₂) (c) chain four full-adders, each carry-out feeding the next carry-in
Examiner tip: Check your answer: S and C_out must form the two-bit binary total of A + B + C_in, here 2 = 10₂.

7Core3 marks

An edge-triggered D-type flip-flop has a data input D, a clock input and an output Q.

(a) State the purpose of a D-type flip-flop in a computer system. [1]

(b) Describe how the output Q of the flip-flop is affected by the D input and the clock signal. [2]

(a) Stores / remembers a single bit (accept: acts as a memory unit; used to build registers)(1)
(b) The value of D is copied to Q (only) on the rising / positive edge of the clock (allow 'on the clock edge'; do not accept 'when the clock is 1')(1)
(b) At all other times Q keeps its value even if D changes / Q is unaffected by D between edges(1)
Answer: (a) to store one bit (b) Q takes the value of D at each rising clock edge and holds it until the next rising edge
Examiner tip: 'When the clock is high' describes a level-triggered latch, not an edge-triggered flip-flop; say 'on the rising edge'.

8Hard4 marks

A positive-edge-triggered D-type flip-flop starts with Q = 0. The table lists, in time order, the changes made to its inputs.

Event	Change	Q after event
0	Initial state: D = 0, clock = 0, Q = 0
1	D changes to 1
2	Clock changes from 0 to 1	(a)
3	D changes to 0
4	Clock changes from 1 to 0
5	D changes to 1
6	D changes to 0
7	Clock changes from 0 to 1	(b)
8	D changes to 1
9	Clock changes from 1 to 0
10	Clock changes from 0 to 1	(c)

State the value of Q after: (a) event 2, (b) event 7, (c) event 10. [3]

(d) Explain why events 5 and 6 do not change Q. [1]

(a) Q = 1(1)
(b) Q = 0(1)
(c) Q = 1(1)
(d) There is no rising clock edge during events 5 and 6 / the clock stays at 0, so the flip-flop ignores changes to D (accept: D is only sampled on the rising edge)(1)
Answer: (a) 1 (b) 0 (c) 1 (d) D is only copied to Q on a rising clock edge; none occurs during events 5 and 6
Examiner tip: A falling edge (1 to 0) does not trigger a positive-edge flip-flop: at event 9 Q stays 0 and only changes at event 10.

9Stretch5 marks

A house alarm has three inputs: A = 1 when the system is armed, D = 1 when the door is open and W = 1 when the window is open. The truth table shows when the alarm output X is 1.

A	D	W	X
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

(a) Write a Boolean expression for X as a sum of products, with one product term for each row where X = 1. [2]

(b) Using Boolean identities, simplify your expression from part (a) as far as possible. You must show your working. [3]

(a) Any two of the three product terms $A \cdot \overline{D} \cdot W$, $A \cdot D \cdot \overline{W}$, $A \cdot D \cdot W$ correct(1)
(a) All three terms joined with OR: $X = A \cdot \overline{D} \cdot W + A \cdot D \cdot \overline{W} + A \cdot D \cdot W$ and no extra terms(1)
(b) Combines two terms using $Y + \overline{Y} = 1$, e.g. $A \cdot D \cdot \overline{W} + A \cdot D \cdot W = A \cdot D \cdot (\overline{W} + W) = A \cdot D$(1)
(b) Further valid step, e.g. $A \cdot D + A \cdot \overline{D} \cdot W = A \cdot (D + \overline{D} \cdot W) = A \cdot (D + \overline{D}) \cdot (D + W)$; or duplicates $A \cdot D \cdot W$ (since $Y + Y = Y$) to obtain $A \cdot D + A \cdot W$(1)
(b) Final answer $X = A \cdot (D + W)$ (accept $A \cdot D + A \cdot W$); answer without valid working max 1 mark in (b)(1)
Answer: (a) $X = A\overline{D}W + AD\overline{W} + ADW$ (b) $X = A \cdot (D + W)$
Examiner tip: A neat route is to reuse the term $A \cdot D \cdot W$ twice (allowed because $Y + Y = Y$), pairing it with each of the other two terms.

10Hard4 marks

NAND gates are described as universal gates because any other gate can be built from them.

(a) Explain how a single NAND gate can be used as a NOT gate. [1]

(b) Use De Morgan's laws to show that $A + B = \overline{\overline{A} \cdot \overline{B}}$. [2]

(a) Connect input A to both inputs of the NAND gate, since $\overline{A \cdot A} = \overline{A}$ (accept: connect the second input to a constant 1, since $\overline{A \cdot 1} = \overline{A}$)(1)
(b) Applies De Morgan correctly: $\overline{\overline{A} \cdot \overline{B}} = \overline{\overline{A}} + \overline{\overline{B}}$(1)
(b) Uses double negation $\overline{\overline{X}} = X$ to reach $A + B$ (accept working from $A + B = \overline{\overline{A + B}}$ and De Morgan on the inner bar)(1)
(c) 3 (two NANDs used as NOT gates to make $\overline{A}$ and $\overline{B}$, then one NAND)(1)
Answer: (a) join both inputs to A (b) $\overline{\overline{A} \cdot \overline{B}} = \overline{\overline{A}} + \overline{\overline{B}} = A + B$ (c) 3
Examiner tip: In (b) write each step on its own line and name the law used: De Morgan first, then double negation.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session