Boolean Algebra, Logic Gates and Karnaugh Maps - Worksheets, Questions and Revision

12 original exam-style questions - 7 pages of questions with a full mark scheme - free printable PDF.

Download PDF Jump to mark scheme (page 8)Read the revision guide

Next in this strand

Revision Library

revisionlibrary.co.uk

A-Level · Component 01: Computer Systems - Boolean algebra and logic circuits

A1.7 Boolean Algebra, Logic Gates and Karnaugh Maps

OCR H446 · Calculators not allowed · about 140 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

This question is about basic logic gates and their truth tables.

(a)Complete the truth table for a 2-input AND gate, where Q is the output.

A B	Q
0 0	?
0 1	?
1 0	?
1 1	?

(1)

(b)Complete the truth table for a 2-input XOR (exclusive OR) gate, where Q is the output.

A B	Q
0 0	?
0 1	?
1 0	?
1 1	?

(2)

(c)A logic gate has the truth table below.

A B	Q
0 0	1
0 1	1
1 0	1
1 1	0

Identify this gate.(1)

(d)State the Boolean expression for a 2-input NOR gate with inputs A and B.(1)

(Total for Question 1 is 5 marks)

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 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	?	?	?

(3)

(Total for Question 2 is 5 marks)

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 3 is 7 marks)

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 4 is 6 marks)

This question is about the half adder circuit.

(a)State the Boolean expression for the Sum output, S, of a half adder in terms of inputs A and B.(1)

(b)State the Boolean expression for the Carry output, C, of a half adder in terms of inputs A and B.(1)

(c)Complete the truth table for a half adder.

A B	S	C
0 0	?	?
0 1	?	?
1 0	?	?
1 1	?	?

(2)

(d)A half adder is built from a single XOR gate and a single AND gate. Explain why a half adder cannot, unmodified, add three single binary digits together (for example, two data bits plus a carry-in bit from a previous column).(2)

(Total for Question 5 is 6 marks)

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 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	?	?

(4)

(Total for Question 6 is 11 marks)

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.

Cycle	D	Q
1	1	?
2	1	?
3	0	?
4	0	?
5	1	?

(3)

(d)Explain why D-type flip-flops are used to build registers within a CPU.(2)

(Total for Question 7 is 7 marks)

A Boolean function Q depends on three inputs, A, B and C, given by the truth table below.

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

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).
BC=00 BC=01 BC=11 BC=10
A=0: 0 1 1 1
A=1: 0 1 1 1

(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 8 is 6 marks)

A Boolean function Q depends on four inputs, A, B, C and D, and is defined by Q = (A.B) + (C.D).

(a)Complete the 4x4 Karnaugh map for this function, with AB as rows and CD as columns, both in Gray-code order (00, 01, 11, 10).
CD=00 CD=01 CD=11 CD=10
AB=00: ? ? ? ?
AB=01: ? ? ? ?
AB=11: ? ? ? ?
AB=10: ? ? ? ?(4)

(b)Identify the two groups of four adjacent 1s in the map and state the Boolean term each one represents.(2)

(c)Hence state the minimised sum-of-products (SOP) expression for Q.(1)

(d)Using Boolean algebra (not the Karnaugh map), verify that your simplified expression from part (c) is equivalent to the original definition of Q by evaluating both for A=1, B=0, C=1, D=1.(2)

(Total for Question 9 is 9 marks)

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 10 is 8 marks)

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 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	?

(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 11 is 8 marks)

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 12 is 7 marks)

Mark scheme · A1.7 Boolean Algebra, Logic Gates and Karnaugh Maps

Question 1

(a) B1 all four Q values correct: 0, 0, 0, 1
(a) Answer: Q = 0, 0, 0, 1
(b) B1 rows A=0,B=0 and A=0,B=1 correct: 0, 1
(b) B1 rows A=1,B=0 and A=1,B=1 correct: 1, 0
(b) Answer: Q = 0, 1, 1, 0
(c) B1 NAND (accept NOT-AND)
(c) Answer: NAND gate
(d) B1 Q = NOT(A + B), oe e.g. Q = (A+B)'
(d) Answer: Q = NOT(A + B)

Question 2

(a) M1 NAND term correctly represented as NOT(A.B) or (A.B)'
(a) A1 correct final expression Q = NOT(A.B) + C, oe
(a) Answer: Q = NOT(A.B) + C
(b) B1 A.B column fully correct: 0,0,0,0,0,0,1,1
(b) B1 NOT(A.B) column fully correct: 1,1,1,1,1,1,0,0
(b) B1 Q column fully correct: 1,1,1,1,1,1,0,1
(b) Answer: Q = 1,1,1,1,1,1,0,1 (only row A=1,B=1,C=0 gives Q=0)

Question 3

(a) M1 factorises correctly: A.(B+B')
(a) A1 Q = A cao, using B+B'=1
(a) Answer: Q = A
(b) M1 factorises correctly: A.(1+B)
(b) A1 Q = A cao, using 1+B=1
(b) Answer: Q = A
(c) M1 applies the distributive law (A+B).(A+C) = A+(B.C) with C=B': Q = A + B.B'
(c) A1 B.B' = 0, so Q = A + 0
(c) A1 Q = A cao
(c) Answer: Q = A

Question 4

(a) B1 NOT(A.B) = NOT A + NOT B, oe e.g. (A.B)' = A' + B'
(a) Answer: NOT(A.B) = NOT A + NOT B
(b) B1 NOT(A+B) = NOT A . NOT B, oe e.g. (A+B)' = A'.B'
(b) Answer: NOT(A+B) = NOT A . NOT B
(c) M1 applies De Morgan's law: NOT(NOT A . NOT B) = A + B
(c) M1 substitutes to give Q = (A+B) + A.B
(c) M1 applies absorption law A + A.B = A (with X=A+B, Y=B) to reduce (A+B)+A.B to A+B
(c) A1 Q = A + B cso
(c) Answer: Q = A + B

Question 5

(a) B1 S = A XOR B, oe
(a) Answer: S = A XOR B
(b) B1 C = A.B
(b) Answer: C = A.B
(c) B1 S column fully correct: 0, 1, 1, 0
(c) B1 C column fully correct: 0, 0, 0, 1
(c) Answer: S = 0,1,1,0 and C = 0,0,0,1
(d) B1 a half adder only has two inputs (A and B)
(d) B1 it has no third, carry-in input, so it cannot incorporate a carry produced by a previous column; a full adder (with a Cin input) is needed for this
(d) Answer: A half adder has only two inputs and no carry-in input, so it cannot combine a carry from a previous column with the two data bits; a full adder is required.

Question 6

(a) M1 recognises S is the XOR of the three inputs, e.g. combining A XOR B first
(a) A1 S = (A XOR B) XOR Cin, oe A XOR B XOR Cin
(a) Answer: S = A XOR B XOR Cin
(b) M1 recognises Cout is 1 whenever at least two of the three inputs are 1, expressed as a sum of the pairwise AND terms
(b) A1 Cout = A.B + B.Cin + A.Cin, oe (e.g. (A.B) + (Cin.(A XOR B)))
(b) Answer: Cout = A.B + B.Cin + A.Cin
(c) B1 the first half adder takes inputs A and B, producing a partial sum and a partial carry
(c) B1 the second half adder takes the partial sum and Cin as its two inputs, producing the final Sum output, S, and a second carry
(c) B1 the two carry outputs (from the first and second half adders) are combined using the OR gate to produce Cout
(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) B1 S correct for rows 1-4: 0, 1, 1, 0
(d) B1 S correct for rows 5-8: 1, 0, 0, 1
(d) B1 Cout correct for rows 1-4: 0, 0, 0, 1
(d) B1 Cout correct for rows 5-8: 0, 1, 1, 1
(d) Answer: S = 0,1,1,0,1,0,0,1 and Cout = 0,0,0,1,0,1,1,1

Question 7

(a) B1 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 D
(a) Answer: The clock signal controls the moment at which the D input value is stored and the output is allowed to change.
(b) B1 the output only changes state when the clock signal transitions from 1 (high) to 0 (low), i.e. on the falling edge
(b) Answer: The output only updates on the falling (high-to-low) transition of the clock signal.
(c) B1 cycles 1-2 correct: 1, 1
(c) B1 cycles 3-4 correct: 0, 0
(c) B1 cycle 5 correct: 1
(c) Answer: Q = 1, 1, 0, 0, 1
(d) B1 each D-type flip-flop stores a single bit of data persistently, until the next active clock edge, providing memory/storage
(d) B1 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 together
(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 8

(a) B1 group 1: the four cells where BC=01 or BC=11 (both rows of A), i.e. C=1
(a) B1 group 2: the four cells where BC=11 or BC=10 (both rows of A), i.e. B=1
(a) Answer: Group 1: C=1 (columns BC=01, 11). Group 2: B=1 (columns BC=11, 10).
(b) M1 each group of four reduces to a single literal, since A varies freely within each group: group 1 gives C, group 2 gives B
(b) A1 Q = B + C, oe
(b) Answer: Q = B + C
(c) B1 states the truth table value for this row: Q = 1
(c) B1 substitutes into the simplified expression: B+C = 0+1 = 1, which matches
(c) Answer: Truth table Q=1; B+C = 0+1 = 1. They match.

Question 9

(a) B1 row AB=00 correct: 0, 0, 1, 0
(a) B1 row AB=01 correct: 0, 0, 1, 0
(a) B1 row AB=11 correct: 1, 1, 1, 1
(a) B1 row AB=10 correct: 0, 0, 1, 0
(a) Answer: AB=00: 0,0,1,0 | AB=01: 0,0,1,0 | AB=11: 1,1,1,1 | AB=10: 0,0,1,0
(b) B1 the entire AB=11 row (four cells) represents the term A.B
(b) B1 the entire CD=11 column (four cells) represents the term C.D
(b) Answer: Row AB=11 gives A.B; column CD=11 gives C.D.
(c) B1 Q = A.B + C.D
(c) Answer: Q = A.B + C.D
(d) B1 correctly evaluates the map/original value at this input as Q=1 (row AB=10, column CD=11)
(d) B1 substitutes into the simplified expression: A.B+C.D = (1.0)+(1.1) = 0+1 = 1, which matches
(d) Answer: Both give Q=1 for A=1,B=0,C=1,D=1.

Question 10

(a) B1 any Boolean/logic function (e.g. NOT, AND, OR) can be built using NAND gates alone
(a) Answer: Any logic function can be constructed using only NAND gates.
(b) B1 connect both inputs of the NAND gate to the same signal, A: output = NOT(A.A) = NOT A
(b) Answer: Tie both NAND inputs to A; output = NOT(A.A) = NOT A.
(c) B1 the first NAND gate takes inputs A and B, giving output NOT(A.B)
(c) B1 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.B
(c) Answer: NAND1(A,B) = NOT(A.B); NAND2 with both inputs = NAND1's output gives NOT(NOT(A.B)) = A.B.
(d) M1 applies De Morgan's law: NOT(NOT A . NOT B) = NOT(NOT A) + NOT(NOT B)
(d) A1 = A + B cso
(d) B1 NAND gates 1 and 2, each wired as inverters (inputs tied together), produce NOT A and NOT B respectively
(d) B1 NAND gate 3 takes NOT A and NOT B as its two inputs, giving NOT(NOT A . NOT B) = A + B
(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 11

(a) B1 rows 1-4 correct: 0, 0, 0, 1
(a) B1 rows 5-8 correct: 0, 1, 1, 1
(a) Answer: Q = 0,0,0,1,0,1,1,1
(b) B1 the pair at BC=11 (both rows of A) gives the term B.C
(b) B1 the pair at A=1, BC=01 and BC=11 gives the term A.C
(b) B1 the pair at A=1, BC=11 and BC=10 gives the term A.B
(b) Answer: Three overlapping pairs, all sharing the cell A=1,B=1,C=1: B.C, A.C, A.B
(c) B1 Q = A.B + A.C + B.C, oe any order
(c) Answer: Q = A.B + A.C + B.C
(d) B1 three 2-input AND gates are needed, one for each of the product terms A.B, A.C and B.C
(d) B1 two 2-input OR gates are needed, since a 2-input OR gate can only combine two signals at a time and three terms must be combined (e.g. first OR combines A.B and A.C, second OR combines that result with B.C)
(d) Answer: 3 AND gates and 2 OR gates.