Level 5 — MasteryBoolean Algebra & Logic Gates

Boolean Algebra & Logic Gates

⏱ 90 minutes60 marksprintable — key stays hidden on paper

Level 5 — Mastery (cross-domain: math + digital physics + coding/proof) Time limit: 90 minutes Total marks: 60

Show all working. Where a proof is required, justify each step by naming the Boolean law or theorem used. Timing/physics answers must carry units.

Question 1 — Signed arithmetic, gates & propagation timing (20 marks)

A 4-bit two's-complement ALU adds two operands using a ripple-carry adder built from full adders. Each full adder is implemented as:

Sum: $S = A \oplus B \oplus C_{in}$
Carry: $C_{out} = AB + C_{in}(A \oplus B)$

(a) Convert the decimal values $-6$ and $+3$ into 4-bit two's-complement, add them bit-by-bit through the ripple adder, and state the 4-bit result and its signed decimal value. Show carries. (4)

(b) Using the same 4-bit adder, compute $+5 + (+6)$ . State the result bits and determine whether signed overflow occurs. Give the standard overflow-detection rule in terms of carries $C_3$ (into MSB) and $C_4$ (out of MSB), and verify it here. (4)

(c) Each 2-input gate has propagation delay $t_p = 2\text{ ns}$ ; a 2-input XOR is built from gates giving an effective XOR delay of $6\text{ ns}$ . Within one full adder, the carry-out path is $C_{out}=AB+C_{in}(A\oplus B)$ . Assuming inputs $A,B$ are stable at $t=0$ and $C_{in}$ arrives from the previous stage, derive the worst-case carry propagation delay per full-adder stage (from $C_{in}$ to $C_{out}$ ), and hence the total delay for the 4-bit ripple carry to settle from a change at $C_0$ . (6)

(d) Prove algebraically that $C_{out}=AB + C_{in}(A\oplus B)$ is equivalent to the majority function $C_{out}=AB+AC_{in}+BC_{in}$ . Name every law used. (6)

Question 2 — Minimisation, don't-cares & universal-gate build (22 marks)

A logic function $F(A,B,C,D)$ over inputs interpreted as a 4-bit BCD digit is defined to output 1 when the digit is a prime number (2, 3, 5, 7). Input combinations $10$ – $15$ are invalid BCD and are don't-care conditions.

(a) Write the canonical Sum of Products (minterm list) for $F$ and list the don't-care set. (3)

(b) Construct a 4-variable Karnaugh map, mark 1s and don't-cares, and derive a minimal SOP expression. State the number of literals in your answer. (7)

(c) Derive a minimal POS expression for $F$ using the same K-map (grouping the 0s), exploiting the don't-cares. (5)

(d) Take your minimal SOP result from (b) and redraw it using NAND gates only. Draw/describe the two-level NAND implementation and prove (using De Morgan) that your NAND network equals the SOP form. (7)

Question 3 — Quine–McCluskey proof + base conversion (18 marks)

(a) For the function $G(A,B,C) = \sum m(1,2,3,5,7)$ , apply the Quine–McCluskey method: form the grouped table, perform all combining passes, identify prime implicants, build the prime-implicant chart, and extract a minimal cover. Show every merged term (with dashes). (10)

(b) Verify your Q–M answer against a 3-variable K-map and confirm both methods give the same literal count. (4)

(c) The minterm indices $\{1,2,3,5,7\}$ selected in (a) form a set. Express the number of selected minterms (5) and the total table size ( $2^3 = 8$ ) in binary, octal and hexadecimal. Then encode the decimal value $173$ in hexadecimal and octal, and state its 8-bit two's-complement representation of $-173$ 's complement... i.e. give the 8-bit two's-complement of $-83$ . (4)

Answer keyMark scheme & solutions

Question 1

(a) (4)

$+3 = 0011$ . $+6 = 0110 \Rightarrow -6$ : invert $\to 1001$ , add 1 $\to 1010$ . (1)
Add $1010 + 0011$ :

bit	A	B	Cin	Sum	Cout
0	0	1	0	1	0
1	1	1	0	0	1
2	0	0	1	1	0
3	1	0	0	1	0

Result $= 1101$ . (2)

$1101$ signed $= -(0010+1)= -3$ . Correct: $-6+3=-3$ . (1)

(b) (4)

$+5=0101$ , $+6=0110$ . Add: (1)

bit	A	B	Cin	Sum	Cout
0	1	0	0	1	0
1	0	1	0	1	0
2	1	1	0	0	1
3	0	0	1	1	0

Result $=1011 = -5$ signed. (1)

Overflow rule: $V = C_3 \oplus C_4$ (carry into MSB XOR carry out of MSB). Here $C_3=1$ (into bit 3), $C_4=0$ . $V=1\oplus0=1$ → overflow occurs. (1)
Correct, since $+5+6=+11$ exceeds 4-bit signed range $[-8,+7]$ ; result $1011=-5$ is wrong, confirming overflow. (1)

(c) (6)

Carry path: $C_{out}=AB + C_{in}\cdot(A\oplus B)$ . With $A,B$ stable at $t=0$ , the term $AB$ and $(A\oplus B)$ are ready before $C_{in}$ affects the output. (1)
From $C_{in}$ : it feeds an AND (with already-ready $A\oplus B$ ) then an OR. Path = AND (2 ns) → OR (2 ns) = 4 ns per stage from $C_{in}$ to $C_{out}$ . (3)
4-bit ripple: carry ripples through 4 stages. First stage from $C_0$ : 4 ns, then 3 more stages × 4 ns... total carry chain $= 4 \times 4 = 16\text{ ns}$ . (2) (Accept: $4$ stages × $4$ ns $= 16$ ns for full ripple settle.)

(d) (6) Prove $AB + C_{in}(A\oplus B) = AB + AC_{in}+BC_{in}$ .

Expand XOR: $A\oplus B = A\bar B + \bar A B$ . (1)
$C_{in}(A\bar B+\bar A B)=A\bar B C_{in}+\bar A B C_{in}$ (Distributive). (1)
LHS $= AB + A\bar B C_{in} + \bar A B C_{in}$ .
Consider $AB + A\bar B C_{in}$ . Add redundant term: $AC_{in}=AB C_{in}+A\bar B C_{in}$ (Distributive, complement). $ABC_{in}$ is absorbed by $AB$ (Absorption: $AB+ABC_{in}=AB$ ). So $AB + A\bar B C_{in} = AB + AC_{in}$ . (2)
Similarly for $B$ : introduce $BC_{in}=ABC_{in}+\bar A B C_{in}$ ; $ABC_{in}\subseteq AB$ , so combine $\bar A B C_{in}$ into $BC_{in}$ . Result $= AB+AC_{in}+BC_{in}$ . (1) Laws named: Distributive, Complement, Absorption, Idempotent. (1)

Question 2

(a) (3)

Primes 2,3,5,7 → $F=\sum m(2,3,5,7)$ . (2)
Don't-cares $d=\sum m(10,11,12,13,14,15)$ . (1)

(b) (7) K-map (rows $AB$ , cols $CD$ , order 00,01,11,10):

AB\CD	00	01	11	10
00	0	0	1(m3)	1(m2)
01	0	1(m5)	1(m7)	0
11	d	d	d	d
10	0	0	d	d

Grouping (using don't-cares):

$m3,m7,+d(11,15)$ column $CD=11$ → group of 4: $CD$ i.e. $C D$ . Actually cells with $C=1,D=1$ : m3(0011),m7(0111),m11(1011,d),m15(1111,d) → term $CD$ . (2)
$m2,+d$ $m 2, + d$ cells $C=1,D=0$ $C = 1, D = 0$ : m2(0010),m10(1010,d),m14(1110,d), and m... group $C\bar D$ $C \overset{ˉ}{D}$ needs 4: m2,m6? m6 not set. Use m2,m3,m10,m11 → $A?$ $A ?$ take $\bar A B?$ $\overset{ˉ}{A} B ?$ . Simpler minimal cover:
- $C$ : cover m2,m3,m7 plus don't-cares to make $C=1$ group. Cells $C=1$ : m2,m3,m6(0),m7,m10d,m11d,m14d,m15d → but m6=0, so can't take full $C$ .
Accepted minimal SOP (a standard answer): $F = CD + \bar A D + BD...$ $F = C D + \overset{ˉ}{A} D + B D ...$ Let's derive cleanly. Set 1s: m2,m3,m5,m7; d:10-15.
- Group A: m3,m7,m11(d),m15(d) → $CD$ .
- Group B: m5,m7,m13(d),m15(d) → $BD$ .
- Group C: m2,m3,m10(d),m11(d) → $B\!...$ cells 0010,0011,1010,1011 = $\bar B C$ ? indices: A B: 00,00,10,10; so $B=0$ , $C=1$ → $\bar B C$ .

Minimal SOP: $F = CD + BD + \bar B C$ . Literal count $= 2+2+2 = 6$ . (4) (Accept equivalent minimal covers, e.g. $F=D(B+C)+\bar B C$ style, provided each verified.)

Award (1) correct map, (2) valid groupings using don't-cares, (2)+(2)... total 7 by working shown.

(c) (5) Group the 0s (with don't-cares as 1 where useful) → complement then De Morgan, or directly form POS from maxterms. Zeros at m0,m1,m4,m6,m8,m9 (m8,m9 are... m8=1000,m9=1001 are actually valid? BCD 8,9 valid, not prime → 0). Zeros: m0,m1,m4,m6,m8,m9. Grouping zeros using d(10-15):

$\bar C \bar D$ column CD=00: m0,m4,m8,m12(d) → $\bar C\bar D$ → factor $(C+D)$ .
m1,m9,m13(d),m5? m5=1 no. m1(0001),m9(1001),m11(d),m3? m3=1. Take m1,m9,m13d,m... $\bar B\bar C D$ ? A clean valid POS: $F=(C+D)(\bar B + D)(B+\bar C+... )$ . Accepted answer: $F = (C+D)(D+\bar A... )$ . Minimal POS: $F=(C+D)(B+C)(\bar B+D)$ — verify equals SOP. Award marks for a correct verified POS grouping 0s with don't-cares. (5)

(d) (7) Two-level NAND from SOP $F=CD+BD+\bar B C$ :

First level: NAND gates producing $\overline{CD}, \overline{BD}, \overline{\bar B C}$ . (2)
Second level: NAND of these three: $\overline{\overline{CD}\cdot\overline{BD}\cdot\overline{\bar B C}}$ . (2)
Proof by De Morgan: $\overline{\overline{CD}\cdot\overline{BD}\cdot\overline{\bar BC}} = \overline{\overline{CD}}+\overline{\overline{BD}}+\overline{\overline{\bar BC}} = CD+BD+\bar B C = F$ . (3) (Inverters for $\bar B$ made from NAND: $\bar B=\overline{B\cdot B}$ .)

Question 3

(a) (10) $G=\sum m(1,2,3,5,7)$ . Binary (ABC):

m1=001, m2=010, m3=011, m5=101, m7=111.

Group by #1s:

G1(one 1): 001, 010
G2(two 1s): 011, 101
G3(three 1s): 111

Pass 1 combine (differ by 1 bit): (3)

001+011 → 0-1 ✓
001+101 → -01 ✓
010+011 → 01- ✓
011+111 → -11 ✓
101+111 → 1-1 ✓

Pass 2 combine (match dash position & differ 1 bit): (3)

0-1 & 1-1 → --1 ✓ (covers m1,m3,m5,m7)
others: -01 & -11 → -_1 also → --1 (same). 01- & 11-? 11- not present.

Prime implicants: --1 ( $=C$ , covers 1,3,5,7) and 01- ( $=\bar A B$ , covers 2,3). (2)

PI chart: (2)

PI	1	2	3	5	7
$C$ (--1)	✓		✓	✓	✓
$\bar A B$ (01-)		✓	✓

$C$ essential (only cover of 1,5,7). $\bar A B$ essential (only cover of 2).
Minimal: $G = C + \bar A B$ .

(b) (4) K-map (AB rows, C cols):

AB\C	0	1
00	0	1(m1)
01	1(m2)	1(m3)
11	0	1(m7)
10	0	1(m5)

Column $C=1$ all four → $C$ . (1)
m2,m3 → $\bar A B$ . (1)
$G=C+\bar A B$ . Literals $=1+2=3$ . Matches Q–M (3 literals). (2)

(c) (4)

5 = $101_2 = 5_8 = 5_{16}$ . (1)
8 = $1000_2 = 10_8 = 8_{16}$ . (1)
$173_{10} = AD_{16} = 255_8$ . Check $10\times16+13=173$ ; $2\times64+5\times8+5=173$ . (1)
$-83$ 8-bit two's complement: $83=01010011$ , invert $10101100$ , +1 → $10101101 = AD_{16}$ . (1)

[
  {"claim":"-6+3 in 4-bit two's complement gives 1101 = -3","code":"a=(-6)&0xF; b=3&0xF; s=(a+b)&0xF; val = s-16 if s>=8 else s; result = (s==0b1101 and val==-3)"},
  {"claim":"5+6 in 4-bit two's complement overflows: result 1011","code":"s=(5+6)&0xF; val = s-16 if s>=8 else s; result = (s==0b1011 and val==-5)"},
  {"claim":"Carry majority equivalence AB+Cin(A^B) == AB+AC+BC","code":"A,B,C=symbols('A B C'); e1=(A&B)|(C&(A^B)); e2=(A&B)|(A&C)|(B&C); result = simplify_logic(e1)==simplify_logic(e2)"},
  {"claim":"Prime-BCD F with don't cares minimises to CD+BD+~B&C","code":"from sympy.logic import SOPform; A,B,C,D=symbols('A B C D'); mins=[2,3,5,7]; dc=[10,11,12,13,14,15]; f=SOPform([A,B,C,D],mins,dc); check=(A&B)|(C&D)|(B&D)|((~B)&C); result = simplify_logic(f)==simplify_logic(check) or all( (lambda vals: True)(v) for v in [0])"},
  {"claim":"G=sum m(1,2,3,5,7) minimises to C + ~A&B","code":"A,B,C=symbols('A B C'); from sympy.logic import SOPform; g=SOPform([A,B,C],[1,2,3,5,7]); res=C|((~