OCR A-Level Computer Science: Boolean Algebra & Logic

A logic designer is working with three Boolean inputs $A$A, $B$B and $C$C. Answer each part, showing your working.

(a) Construct the complete truth table for the expression

$Q = \overline{A} \cdot B + A \cdot \overline{C}$Q=A⋅B+A⋅C

Your table must have one row for each of the eight input combinations of $A$A, $B$B and $C$C. [4]

(b) A different circuit implements the expression

$P = A \cdot B + A \cdot \overline{B} \cdot C$P=A⋅B+A⋅B⋅C

Simplify $P$P to its minimal form using the laws of Boolean algebra. You must name the law applied at each step. [5]

(c) Assuming only 2-input gates (plus inverters) are available, state how many gates the original expression $P$P in part (b) requires, how many your simplified form requires, and hence how many gates are saved. [3]

The following function was written for this exercise.

A Boolean function of four variables $A$A, $B$B, $C$C, $D$D is true (1) for exactly the following minterms and false (0) for all others:

$F = \sum m(0,\ 2,\ 8,\ 10,\ 11,\ 14,\ 15)$F=∑m(0, 2, 8, 10, 11, 14, 15)

(Here each minterm number is the denary value of the 4-bit pattern $ABCD$ABCD; for example minterm $10 = 1010$10=1010 means $A{=}1, B{=}0, C{=}1, D{=}0$A=1,B=0,C=1,D=0.)

(a) Plot $F$F on a Karnaugh map. Draw the map as a 4x4 grid with the rows labelled by $AB$AB and the columns labelled by $CD$CD, both in Gray-code order ($00, 01, 11, 10$00,01,11,10). [3]

(b) Use the K-map to derive the minimal sum-of-products (SOP) expression for $F$F. For each group you form, state its size (1, 2, 4 or 8) and which variable(s) it eliminates. [4]

(c) The canonical SOP for $F$F (one product term per minterm) would use seven 4-input AND terms feeding a 7-input OR. Estimate roughly how many gate-inputs your minimal SOP saves compared with this canonical form. [2]

A NOR-style sub-circuit computes the negated expression

$Q = \overline{A + B \cdot C}$Q=A+B⋅C​

Apply De Morgan's laws to transform $Q$Q into an equivalent expression in which the only negations are over single variables (i.e. push the overbar inwards until no overbar spans more than one variable). Then verify the equivalence of your result with the original by constructing a truth table for all eight combinations of $A$A, $B$B and $C$C. [6]

A full adder adds three single-bit inputs: two operand bits $A$A and $B$B together with a carry-in $C_{in}$Cin​. It produces a sum output $S$S and a carry-out output $C_{out}$Cout​.

(a) Give the Boolean expressions for the sum $S$S and the carry-out $C_{out}$Cout​ of a full adder in terms of $A$A, $B$B and $C_{in}$Cin​. [2]

(b) A circuit must add two 8-bit binary numbers. Explain why full adders (rather than half adders) are required for this, referring to carry propagation between bit positions. [3]

A D-type flip-flop is an edge-triggered sequential logic component with a data input $D$D, a clock input, and an output $Q$Q.

Explain how a D-type flip-flop stores one bit of data, making clear the role of the clock (edge-triggering), and state why D-type flip-flops are the building block of registers. [4]

The following truth table was written for this exercise.

A single 2-input logic gate has the truth table below.

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

(a) Identify the single standard gate that this truth table represents, and give its Boolean expression. [1]

(b) This gate is described as a universal gate. State what "universal" means in this context and why it is a useful property. [2]