Boolean Algebra & Logic Gates

Q1 (10 marks)

(a) $-45$ in 8-bit two's complement:

• $45 = 00101101_2$ (magnitude). (1)
• Invert bits: $11010010$. (1)
• Add 1: $11010010 + 1 = 11010011$. (1)
• Answer: $-45 = 11010011_2$. (1)

(b) From $11010011$:

• Hex: group in nibbles $1101\,0011 = D3_{16}$. (1.5)
• Octal: group in threes from right $11\,010\,011 = 323_8$. (1.5)

(c) $(-45)+(+19)$:

• $-45 = 11010011$, $+19 = 00010011$. (1)
• Sum: $11010011 + 00010011 = 11100110$. (1)
• $11100110$ is negative; invert+1 → $00011010 = 26$, so value $= -26$ ✓ (since $-45+19=-26$). No overflow: two operands of opposite sign can never overflow (carry-in = carry-out of sign bit). (1)

Q2 (10 marks)

(a) Truth table (F = 1 for odd number of 1s): (4, ½ per row)

(b) This is the 3-input XOR (parity) function. $F = (A \oplus B) \oplus C$. (2)

(c) XOR outputs 1 iff its inputs differ; cascading XORs accumulates the parity. Looking at the table, F=1 exactly on rows where the count of 1s is odd (1 or 3). Each XOR effectively counts a "toggle," so the final output reports whether the total number of set bits is odd — the definition of odd parity. (4) (2 for correct link to odd-count rows, 2 for coherent parity explanation)

Q3 (10 marks)

$F = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$

• Factor last two terms: $AB\overline{C} + ABC = AB(\overline{C}+C) = AB\cdot 1 = AB$ — Distributive + Complement + Identity. (3)
• Now $F = \overline{A}BC + A\overline{B}C + AB$.
• Group $\overline{A}BC + ABC'$... instead combine $\overline{A}BC$ with $ABC$ (re-add $ABC$ using idempotent $AB = AB + ABC$): $ABC + \overline{A}BC = BC(A+\overline{A}) = BC$ — Idempotent / Distributive / Complement. (3)
• Similarly $A\overline{B}C + ABC = AC(B+\overline{B}) = AC$. (2)
• So $F = AB + BC + AC$ (consensus form, minimal). (2)

Final: $F = AB + AC + BC$.

Q4 (10 marks)

(a) De Morgan's theorems: (2) $\overline{A+B} = \overline{A}\cdot\overline{B}, \qquad \overline{A\cdot B} = \overline{A}+\overline{B}$

(b) OR from NAND: (5)

• $A + B = \overline{\overline{A+B}} = \overline{\overline{A}\cdot\overline{B}}$ (De Morgan). (2)
• $\overline{A}$ = A NANDed with itself = $\overline{A\cdot A}$; similarly $\overline{B}$. (1)
• $\overline{\overline{A}\cdot\overline{B}}$ = NAND of $\overline{A}$ and $\overline{B}$. (1)
• Total NAND gates: 2 (inverters) + 1 (final NAND) = 3 NAND gates. (1)

(c) NAND is universal because any Boolean function can be realised using NAND gates alone — NOT, AND, and OR can all be constructed from NAND, and {AND, OR, NOT} is a functionally complete set. (3)

Q5 (12 marks)

(a) K-map (rows AB, cols CD in Gray order 00,01,11,10): (4)

Minterms 0,1,2,5,6,8,9,10,14 = 1; 7,11,15 = d; rest = 0. (m3 = 0.)

(b) Minimal SOP groups: (6)

• $\overline{B}\,\overline{C}$ — cells 0,1,8,9 (AB=00/10, CD=00/01). (2)
• $C\overline{D}$ — cells 2,6,10,14 (all rows, CD=10). (2)
• $B\overline{C}D$ or use d(7): group 5,7 with... choose $\overline{A}\,D$? Cover m5. Group 1,5 = $\overline{A}\,\overline{C}D$; using d7: 5,7 = $\overline{A}BD$. Simplest cover of m5: $\overline{A}\,\overline{C}\,D$ (cells 1,5) or with don't cares group 5,7,13?,15 — 15 is d, 13=0. Take 5,7,15,13 invalid (13=0). Use 5,7 + d15,d... Group $BD$ needs 5,7,13,15 but 13=0. So cover m5 via $\overline{A}D$ (cells 1,5,3d,7d) valid since 3=? m3=0, not d. So $\overline{A}D$ covers 1,3,5,7 but 3=0 → invalid. Use $\overline{A}\,\overline{C}D$ (1,5). (2)

Minimal SOP: $F = \overline{B}\,\overline{C} + C\overline{D} + \overline{A}\,\overline{C}D$.

(c) Don't-cares (7,11,15) allowed larger groupings (extending prime implicants across those cells), reducing the total literal count versus treating them as 0. Accept any reasoned statement of literal saving. (2)

Q6 (8 marks)

(a) Quine–McCluskey for $\sum m(0,1,2,5,6,7)$: (5)

Binary minterms grouped by 1-count:

• Group0: 0 = 000
• Group1: 1 = 001, 2 = 010
• Group2: 5 = 101, 6 = 110
• Group3: 7 = 111

Combine adjacent (differ in 1 bit):

• 0,1 = 00- ; 0,2 = 0-0
• 1,5 = -01 ; 2,6 = -10
• 5,7 = 1-1 ; 6,7 = 11-

Second combination:

• (none combine further into size-4 — check pairs share dash & differ 1 bit: no valid 4-cell groups).

Prime implicants: $\overline{A}\,\overline{B}$ (00-), $\overline{A}\,\overline{C}$ (0-0), $\overline{B}\,C$ (-01), $B\overline{C}$ (-10), $AC$ (1-1), $AB$ (11-). (5)

(Minimal cover e.g. $F = \overline{A}\,\overline{B} + \overline{B}C + B\overline{C} + AB$ or similar — full accept for correct PI list.)

(b) Total worst-case delay $= 4 + 6 + 3 = 13$ ns. Series delays add because each gate can only begin switching after its input (the previous gate's output) has settled; the signal must propagate through each stage sequentially. (3)

[
  {"claim":"45 magnitude then two's complement gives 11010011","code":"val=45\nbits=format(val,'08b')\ninv=''.join('1' if b=='0' else '0' for b in bits)\ntc=format(int(inv,2)+1,'08b')\nresult=(tc=='11010011')"},
  {"claim":"11010011 base2 equals D3 hex and 323 octal","code":"n=int('11010011',2)\nresult=(format(n,'X')=='D3' and format(n,'o')=='323')"},
  {"claim":"-45 + 19 = -26 in 8-bit two's complement (11100110)","code":"a=(-45)&0xFF\nb=19&0xFF\ns=(a+b)&0xFF\nsigned=s-256 if s>=128 else s\nresult=(s==0b11100110 and signed==-26)"},
  {"claim":"F=A'BC+AB'C+ABC'+ABC simplifies to AB+AC+BC","code":"A,B,C=symbols('A B C')\nfrom sympy.logic.boolalg import Or,And,Not,simplify_logic\nF=Or(And(Not(A),B,C),And(A,Not(B),C),And(A,B,Not(C)),And(A,B,C))\nG=Or(And(A,B),And(A,C),And(B,C))\nresult=(simplify_logic(F)==simplify_logic(G))"},
  {"claim":"total series propagation delay 4+6+3 = 13 ns","code":"result=(4+6+3==13)"}
]