Boolean Algebra, Logic Gates and Karnaugh Maps - Worksheets, Questions and Revision
9 original exam-style questions - 6 pages of questions with a full mark scheme - free printable PDF.
Boolean Algebra, Logic Gates and Karnaugh Maps revision guideMore A Level Computer Science practiceMock exams
This topic is chapter 7 of A Level Computer Science Topic Workbook 1 and chapter 7 of A Level Computer Science 10-Minute Tests.
1.7 Boolean Algebra, Logic Gates and Karnaugh Maps
| A B C | A.B | NOT(A.B) | Q |
|---|---|---|---|
| 0 0 0 | ? | ? | ? |
| 0 0 1 | ? | ? | ? |
| 0 1 0 | ? | ? | ? |
| 0 1 1 | ? | ? | ? |
| 1 0 0 | ? | ? | ? |
| 1 0 1 | ? | ? | ? |
| 1 1 0 | ? | ? | ? |
| 1 1 1 | ? | ? | ? |
| A B Cin | S | Cout |
|---|---|---|
| 0 0 0 | ? | ? |
| 0 0 1 | ? | ? |
| 0 1 0 | ? | ? |
| 0 1 1 | ? | ? |
| 1 0 0 | ? | ? |
| 1 0 1 | ? | ? |
| 1 1 0 | ? | ? |
| 1 1 1 | ? | ? |
| Cycle | D | Q |
|---|---|---|
| 1 | 1 | ? |
| 2 | 1 | ? |
| 3 | 0 | ? |
| 4 | 0 | ? |
| 5 | 1 | ? |
| A B C | Q |
|---|---|
| 0 0 0 | 0 |
| 0 0 1 | 1 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 1 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
| A | BC=00 | BC=01 | BC=11 | BC=10 |
|---|---|---|---|---|
| A=0 | 0 | 1 | 1 | 1 |
| A=1 | 0 | 1 | 1 | 1 |
| A B C | Q |
|---|---|
| 0 0 0 | ? |
| 0 0 1 | ? |
| 0 1 0 | ? |
| 0 1 1 | ? |
| 1 0 0 | ? |
| 1 0 1 | ? |
| 1 1 0 | ? |
| 1 1 1 | ? |
Question 1
- (a) NAND term correctly represented as NOT(A.B) or (A.B)'M1
- (a) correct final expression Q = NOT(A.B) + C, oeA1
- (a) Answer: Q = NOT(A.B) + C
- (b) A.B column fully correct: 0,0,0,0,0,0,1,1B1
- (b) NOT(A.B) column fully correct: 1,1,1,1,1,1,0,0B1
- (b) Q column fully correct: 1,1,1,1,1,1,0,1B1
- (b) Answer: Q = 1,1,1,1,1,1,0,1 (only row A=1,B=1,C=0 gives Q=0)
Question 2
- (a) factorises correctly: A.(B+B')M1
- (a) Q = A cao, using B+B'=1A1
- (a) Answer: Q = A
- (b) factorises correctly: A.(1+B)M1
- (b) Q = A cao, using 1+B=1A1
- (b) Answer: Q = A
- (c) applies the distributive law (A+B).(A+C) = A+(B.C) with C=B': Q = A + B.B'M1
- (c) B.B' = 0, so Q = A + 0A1
- (c) Q = A caoA1
- (c) Answer: Q = A
Question 3
- (a) NOT(A.B) = NOT A + NOT B, oe e.g. (A.B)' = A' + B'B1
- (a) Answer: NOT(A.B) = NOT A + NOT B
- (b) NOT(A+B) = NOT A . NOT B, oe e.g. (A+B)' = A'.B'B1
- (b) Answer: NOT(A+B) = NOT A . NOT B
- (c) applies De Morgan's law: NOT(NOT A . NOT B) = A + BM1
- (c) substitutes to give Q = (A+B) + A.BM1
- (c) applies absorption law A + A.B = A (with X=A+B, Y=B) to reduce (A+B)+A.B to A+BM1
- (c) Q = A + B csoA1
- (c) Answer: Q = A + B
Question 4
- (a) recognises S is the XOR of the three inputs, e.g. combining A XOR B firstM1
- (a) S = (A XOR B) XOR Cin, oe A XOR B XOR CinA1
- (a) Answer: S = A XOR B XOR Cin
- (b) recognises Cout is 1 whenever at least two of the three inputs are 1, expressed as a sum of the pairwise AND termsM1
- (b) Cout = A.B + B.Cin + A.Cin, oe (e.g. (A.B) + (Cin.(A XOR B)))A1
- (b) Answer: Cout = A.B + B.Cin + A.Cin
- (c) the first half adder takes inputs A and B, producing a partial sum and a partial carryB1
- (c) the second half adder takes the partial sum and Cin as its two inputs, producing the final Sum output, S, and a second carryB1
- (c) the two carry outputs (from the first and second half adders) are combined using the OR gate to produce CoutB1
- (c) Answer: Half adder 1 adds A and B (partial sum + carry1); half adder 2 adds the partial sum to Cin (giving final S + carry2); Cout = carry1 OR carry2.
- (d) S correct for rows 1-4: 0, 1, 1, 0B1
- (d) S correct for rows 5-8: 1, 0, 0, 1B1
- (d) Cout correct for rows 1-4: 0, 0, 0, 1B1
- (d) Cout correct for rows 5-8: 0, 1, 1, 1B1
- (d) Answer: S = 0,1,1,0,1,0,0,1 and Cout = 0,0,0,1,0,1,1,1
Question 5
- (a) it controls when the value on the D input is sampled and stored / when the output can change, rather than the output changing continuously with DB1
- (a) Answer: The clock signal controls the moment at which the D input value is stored and the output is allowed to change.
- (b) the output only changes state when the clock signal transitions from 1 (high) to 0 (low), i.e. on the falling edgeB1
- (b) Answer: The output only updates on the falling (high-to-low) transition of the clock signal.
- (c) cycles 1-2 correct: 1, 1B1
- (c) cycles 3-4 correct: 0, 0B1
- (c) cycle 5 correct: 1B1
- (c) Answer: Q = 1, 1, 0, 0, 1
- (d) each D-type flip-flop stores a single bit of data persistently, until the next active clock edge, providing memory/storageB1
- (d) the shared clock signal allows every flip-flop in the register to update simultaneously (synchronously), so a whole multi-bit value can be stored/changed reliably togetherB1
- (d) Answer: Each flip-flop stores one persistent bit, and the shared clock lets all bits of the register update together, in step, giving reliable synchronous storage.
Question 6
- (a) group 1: the four cells where BC=01 or BC=11 (both rows of A), i.e. C=1B1
- (a) group 2: the four cells where BC=11 or BC=10 (both rows of A), i.e. B=1B1
- (a) Answer: Group 1: C=1 (columns BC=01, 11). Group 2: B=1 (columns BC=11, 10).
- (b) each group of four reduces to a single literal, since A varies freely within each group: group 1 gives C, group 2 gives BM1
- (b) Q = B + C, oeA1
- (b) Answer: Q = B + C
- (c) states the truth table value for this row: Q = 1B1
- (c) substitutes into the simplified expression: B+C = 0+1 = 1, which matchesB1
- (c) Answer: Truth table Q=1; B+C = 0+1 = 1. They match.
Question 7
- (a) any Boolean/logic function (e.g. NOT, AND, OR) can be built using NAND gates aloneB1
- (a) Answer: Any logic function can be constructed using only NAND gates.
- (b) connect both inputs of the NAND gate to the same signal, A: output = NOT(A.A) = NOT AB1
- (b) Answer: Tie both NAND inputs to A; output = NOT(A.A) = NOT A.
- (c) the first NAND gate takes inputs A and B, giving output NOT(A.B)B1
- (c) a second NAND gate, wired as a NOT gate (both inputs tied together), takes the output of the first gate, giving NOT(NOT(A.B)) = A.BB1
- (c) Answer: NAND1(A,B) = NOT(A.B); NAND2 with both inputs = NAND1's output gives NOT(NOT(A.B)) = A.B.
- (d) applies De Morgan's law: NOT(NOT A . NOT B) = NOT(NOT A) + NOT(NOT B)M1
- (d) = A + B csoA1
- (d) NAND gates 1 and 2, each wired as inverters (inputs tied together), produce NOT A and NOT B respectivelyB1
- (d) NAND gate 3 takes NOT A and NOT B as its two inputs, giving NOT(NOT A . NOT B) = A + BB1
- (d) Answer: NOT(NOT A . NOT B) = A + B; built from two inverter-wired NANDs producing NOT A and NOT B, feeding a third NAND.
Question 8
- (a) rows 1-4 correct: 0, 0, 0, 1B1
- (a) rows 5-8 correct: 0, 1, 1, 1B1
- (a) Answer: Q = 0,0,0,1,0,1,1,1
- (b) the pair at BC=11 (both rows of A) gives the term B.CB1
- (b) the pair at A=1, BC=01 and BC=11 gives the term A.CB1
- (b) the pair at A=1, BC=11 and BC=10 gives the term A.BB1
- (b) Answer: Three overlapping pairs, all sharing the cell A=1,B=1,C=1: B.C, A.C, A.B
- (c) Q = A.B + A.C + B.C, oe any orderB1
- (c) Answer: Q = A.B + A.C + B.C
- (d) factorises Q = A.B + A.C + B.C as Q = A.B + C.(A+B), or an equivalent factorisationM1
- (d) two 2-input AND gates and two 2-input OR gates: AND gates form A.B and C.(A+B); OR gates form A+B and combine the two products, oeA1
- (d) Answer: 2 AND gates and 2 OR gates (4 gates total), using Q = A.B + C.(A+B).
Question 9
- (a) factorises the first two terms: A.B.C + A.B.C' = A.B.(C+C') = A.BM1
- (a) combines A.B with A'.B.C using B.(A+A'.C)=B.(A+C) [since A+A'.C=A+C], giving A.B + A'.B.C = A.B + B.CM1
- (a) combines the remaining A.B with A.B'.C using A.(B+B'.C)=A.(B+C) [since B+B'.C=B+C], giving A.B + A.B'.C = A.B + A.CM1
- (a) Q = A.B + A.C + B.C cso, oe any orderA1
- (a) Answer: Q = A.B + A.C + B.C
- (b) original expression: 4 three-input product terms, each needing 2 two-input AND gates (8 AND gates total), plus 3 two-input OR gates to combine the 4 terms, plus 3 NOT gates (for A', B' and C'): 14 gates in total (accept a clearly justified equivalent count from a valid gate-building method)B1
- (b) simplified expression: 3 two-input product terms need 3 two-input AND gates, plus 2 two-input OR gates to combine them, and no NOT gates are needed: 5 gates in totalB1
- (b) the simplified circuit needs substantially fewer logic gates, which reduces chip area/cost, power consumption and propagation delay (signal has fewer gates to pass through)B1
- (b) Answer: Original: 14 gates (8 AND + 3 OR + 3 NOT). Simplified: 5 gates (3 AND + 2 OR). Simplifying reduces gate count, cost, power use and delay.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.