Skip to the worksheet
Revision Library
Choose a subject

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.

This topic is chapter 7 of A Level Computer Science Topic Workbook 1 and chapter 7 of A Level Computer Science 10-Minute Tests.

Revision Library
revisionlibrary.co.uk
A-Level · Component 01: Computer Systems - Boolean algebra and logic circuits

1.7 Boolean Algebra, Logic Gates and Karnaugh Maps

OCR H446 · Calculators not allowed · about 75 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
A logic circuit has three inputs, A, B and C. Inputs A and B feed a NAND gate. The output of the NAND gate and input C feed a 2-input OR gate, whose output is Q.
(a)Write the Boolean expression for Q in terms of A, B and C.(2)
(b)Complete the truth table for this circuit for all 8 combinations of A, B and C.
A B CA.BNOT(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???
(3)
(Total for Question 1 is 5 marks)
2
Simplify each of the following Boolean expressions using the laws of Boolean algebra, showing each law you use.
(a)Simplify Q = A.B + A.B'(2)
(b)Simplify Q = A + A.B(2)
(c)Simplify Q = (A+B).(A+B')(3)
(Total for Question 2 is 7 marks)
3
This question is about De Morgan's laws.
(a)State De Morgan's first law in Boolean notation.(1)
(b)State De Morgan's second law in Boolean notation.(1)
(c)Use De Morgan's laws and the laws of Boolean algebra to simplify Q = NOT(NOT A . NOT B) + A.B, showing each step of your working.(4)
(Total for Question 3 is 6 marks)
4
This question is about the full adder circuit, which has three inputs: A, B and a carry-in, Cin.
(a)Determine the Boolean expression for the Sum output, S, of a full adder in terms of A, B and Cin.(2)
(b)Determine the Boolean expression for the Carry-out output, Cout, of a full adder in terms of A, B and Cin.(2)
(c)Explain how a full adder can be constructed from two half adders and one OR gate.(3)
(d)Complete the truth table for a full adder for all 8 combinations of A, B and Cin.
A B CinSCout
0 0 0??
0 0 1??
0 1 0??
0 1 1??
1 0 0??
1 0 1??
1 1 0??
1 1 1??
(4)
(Total for Question 4 is 11 marks)
5
This question is about the D-type flip-flop.
(a)State the purpose of the clock (CLK) input on a D-type flip-flop.(1)
(b)A D-type flip-flop is described as negative-edge triggered. State what is meant by this.(1)
(c)The table below shows the D input value present at each rising clock edge of a positive-edge-triggered D-type flip-flop, whose output Q starts at 0. Complete the Q column, giving the output immediately after each rising edge.
CycleDQ
11?
21?
30?
40?
51?
(3)
(d)Explain why D-type flip-flops are used to build registers within a CPU.(2)
(Total for Question 5 is 7 marks)
6
A Boolean function Q depends on three inputs, A, B and C, given by the truth table below.
A B CQ
0 0 00
0 0 11
0 1 01
0 1 11
1 0 00
1 0 11
1 1 01
1 1 11
The corresponding Karnaugh map is shown below, with rows for A (0 then 1) and columns for BC in Gray-code order (00, 01, 11, 10).
ABC=00BC=01BC=11BC=10
A=00111
A=10111
(a)Identify two overlapping groups of four adjacent 1s in the Karnaugh map, stating which cells (in terms of BC values) are in each group.(2)
(b)Determine the simplified Boolean expression for Q from these two groupings.(2)
(c)Verify your simplified expression against the row of the original truth table where A=1, B=0, C=1.(2)
(Total for Question 6 is 6 marks)
7
This question is about NAND gates as a universal (functionally complete) logic gate.
(a)State what is meant by describing the NAND gate as 'functionally complete'.(1)
(b)Show how a single NAND gate can be used to produce the NOT function, describing the connection required.(1)
(c)Using only NAND gates, show how to construct an AND gate, describing the gates used and their connections.(2)
(d)A student claims an OR gate can also be built entirely from NAND gates, using De Morgan's law. Using Boolean algebra, show that NOT(NOT A . NOT B) is equivalent to A OR B, and hence describe how three NAND gates could be arranged to build an OR gate.(4)
(Total for Question 7 is 8 marks)
8
A 3-input majority function has output Q=1 whenever two or more of its inputs A, B and C are 1.
(a)Complete the truth table for this majority function.
A B CQ
0 0 0?
0 0 1?
0 1 0?
0 1 1?
1 0 0?
1 0 1?
1 1 0?
1 1 1?
(2)
(b)Draw the Karnaugh map for this function (rows A=0/1, columns BC in Gray-code order 00, 01, 11, 10) and identify all groups of two adjacent 1s available (there is no larger group). State the product term each group represents.(3)
(c)Hence state the minimised Boolean expression for Q.(1)
(d)A 3-person voting circuit uses this majority function so that the group decision Q is 1 only when at least two of the three voters (A, B, C) vote 1. Using your answer to part (c), state the minimum number of 2-input AND gates and 2-input OR gates required to build this circuit, briefly justifying your answer.(2)
(Total for Question 8 is 8 marks)
9
This question is about simplifying a more complex Boolean expression and evaluating the benefit of doing so.
(a)Simplify Q = A.B.C + A.B.C' + A'.B.C + A.B'.C, showing each law you use.(4)
(b)State how many 2-input AND gates, 2-input OR gates and NOT gates are required to implement the original (unsimplified) expression from part (a) directly, compared with the simplified expression. Comment on the benefit of simplifying the expression before building the circuit.(3)
(Total for Question 9 is 7 marks)
Mark scheme · 1.7 Boolean Algebra, Logic Gates and Karnaugh Maps

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.

Question 1

5 marks
Did your answer earn the marks?

Question 2

7 marks
Did your answer earn the marks?

Question 3

6 marks
Did your answer earn the marks?

Question 4

11 marks
Did your answer earn the marks?

Question 5

7 marks
Did your answer earn the marks?

Question 6

6 marks
Did your answer earn the marks?

Question 7

8 marks
Did your answer earn the marks?

Question 8

8 marks
Did your answer earn the marks?

Question 9

7 marks
Did your answer earn the marks?
Mark my answers

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk