Boolean Algebra & Logic Gates

Question 1 [12]

(a) $-93$ in 8-bit two's complement. [4]

• $+93 = 0101\,1101_2$ (64+16+8+4+1). [1]
• Invert: $1010\,0010$. [1]
• Add 1: $1010\,0011$. [1]
• Hex: $1010\,0011 = \text{0xA3}$. [1]

(b) Byte 0xB6 = $1011\,0110_2$. [1]

• (i) Unsigned $= 128+32+16+4+2 = 182$. [1]
• (ii) Signed: MSB=1 so negative. Two's complement: value $= 182-256 = -74$. [1]

(c) $59 + 87$: [5]

• $59 = 0011\,1011$, $87 = 0101\,0111$. [1]
• Sum: $0011\,1011 + 0101\,0111 = 1001\,0010$ (= 146 unsigned). [2]
• Interpreted signed: MSB=1 → $146-256 = -110$. [1]
• Overflow: two positives gave a negative sign → overflow occurred. (Carry into MSB = 1, carry out of MSB = 0; they differ ⇒ overflow.) [1]

Question 2 [14]

(a) Function is XOR. $F = A\oplus B = \overline{A}B + A\overline{B}$. [2]

(b) Truth table: [2]

(c) 4-NAND XOR proof: [6] Let $N(x,y)=\overline{xy}$.

• $G_1 = N(A,B) = \overline{AB}$. [1]
• $G_2 = N(A,G_1) = \overline{A\cdot\overline{AB}} = \overline{A(\overline{A}+\overline{B})} = \overline{A\overline{B}}$. [1.5]
• $G_3 = N(B,G_1) = \overline{B\cdot\overline{AB}} = \overline{B(\overline{A}+\overline{B})} = \overline{\overline{A}B}$. [1.5]
• $G_4 = N(G_2,G_3) = \overline{\overline{A\overline{B}}\cdot\overline{\overline{A}B}} = A\overline{B} + \overline{A}B$ (De Morgan). [2] This equals $A\oplus B$. ∎

(d) Propagation delay: [4]

• $G_1$ is level 1; $G_2,G_3$ are level 2 (fed by $G_1$); $G_4$ is level 3. [2]
• Critical path: input → $G_1$ → $G_2$(or $G_3$) → $G_4$ = 3 gates in series. [1]
• Worst-case delay $= 3\times 4 = 12\text{ ns}$. [1]

Question 3 [12]

(a) Canonical SOP (m1,m2,m4,m7): [3] $F = \overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + ABC$ (1 mark for correct set, deduct for each wrong term; full 3 for all correct.)

(b) Maxterms are the remaining $M(0,3,5,6)$: [3] $F = (A+B+C)(A+\overline{B}+\overline{C})(\overline{A}+B+\overline{C})(\overline{A}+\overline{B}+C)$

(c) Simplify $\overline{A}BC + A\overline{B}C + ABC + AB\overline{C}$: [6]

• Combine $\overline{A}BC + ABC = BC$ (distributive/complement $A+\overline{A}=1$). [2]
• Combine $A\overline{B}C$... use $ABC$ again via idempotent $ABC+ABC$. Take $A\overline{B}C + ABC = AC$. [2]
• Combine $ABC + AB\overline{C} = AB$. [1]
• Result: $F = BC + AC + AB$ (majority function). [1]

Question 4 [12]

(a) K-map (rows AB, cols CD; order 00,01,11,10): [4]

(minterms: 0,2 in AB=00; 5,7 in AB=01; 8,10 in AB=10; 13,15 in AB=11; d=1,3 in AB=00)

(b) Grouping: [6]

• Ones at 5,7,13,15 → columns CD=01,11 with $B=1,D=1$: group $BD$. [2]
• Ones at 0,2,8,10 (with don't-cares 1,3 available in AB=00):
  • Group $\overline{B}\,\overline{D}$ covers 0,2,8,10. [2]
  • The don't-cares 1,3 could extend but are not needed; using $\overline{B}\,\overline{D}$ alone is minimal.
• Minimal SOP: $F = BD + \overline{B}\,\overline{D}$ [1] This is the XNOR of $B$ and $D$: $F = \overline{B\oplus D}$. Don't-cares not needed for minimality. [1]

(c) Two-level: 2 AND gates (each 2-input) + 1 OR gate = 3 gates. (One AND needs $\overline{B},\overline{D}$ via inverters, not counted as 2-input AND/OR.) [2]

Question 5 [10]

(a) QM combination for $\sum m(0,1,2,5,6,7)$: [7]

Group by 1s (3-bit):

• 0 ones: 000 (0)
• 1 one: 001(1), 010(2)
• 2 ones: 101(5), 110(6)
• 3 ones: 111(7)

Combine size-2:

• 0-1: 00– (0,1)
• 0-2: 0–0 (0,2)
• 1-5: –01 (1,5)
• 2-6: –10 (2,6)
• 5-7: 1–1 (5,7)
• 6-7: 11– (6,7)

Combine size-4: none combine (differing patterns don't pair with matching dashes). Prime implicants: (0,1)=$\overline{A}\,\overline{B}$; (0,2)=$\overline{A}\,\overline{C}$; (1,5)=$\overline{B}C$; (2,6)=$C\overline{... }$ wait: (2,6)=–10 → $B\overline{C}$; (5,7)=$AC$; (6,7)=$AB$. [7]

PIs: $\overline{A}\,\overline{B},\ \overline{A}\,\overline{C},\ \overline{B}C,\ B\overline{C},\ AC,\ AB$.

(b) PI chart (minterms 0,1,2,5,6,7): [3]

No single essential PI (each minterm covered ≥2 ways). A minimal cover needs 3 PIs, e.g.: $F = \overline{A}\,\overline{B} + B\overline{C} + AC$ (covers 0,1 / 2,6 / 5,7 — all six minterms). Alternative equally minimal: $\overline{A}\,\overline{C}+\overline{B}C+AB$. [3]

[
  {"claim":"-93 in 8-bit two's complement equals 0xA3 (163 as unsigned pattern)","code":"val=(-93)%256; result = (val==0xA3)"},
  {"claim":"0xB6 as signed 8-bit is -74","code":"u=0xB6; s=u-256 if u>=128 else u; result = (s==-74)"},
  {"claim":"59+87 signed 8-bit overflows to -110","code":"r=(59+87)%256; s=r-256 if r>=128 else r; result = (r==0b10010010 and s==-110)"},
  {"claim":"Q3(c) majority: minterm sum of BC+AC+AB equals AND/OR combos over the 4 given terms","code":"A,B,C=symbols('A B C'); f=(~A&B&C)|(A&~B&C)|(A&B&C)|(A&B&~C); g=(B&C)|(A&C)|(A&B); result = simplify_logic(f)==simplify_logic(g)"},
  {"claim":"Q4 minimal F = BD + ~B~D equals XNOR of B,D over minterm set","code":"A,B,C,D=symbols('A B C D'); mins=[0,2,5,7,8,10,13,15]; dc=[1,3]; f=(B&D)|(~B&~D); vals=[]; \nfrom itertools import product\nok=True\nfor a,b,c,d in product([0,1],repeat=4):\n    idx=a*8+b*4+c*2+d\n    fv=1 if f.subs({A:a,B:b,C:c,D:d}) else 0\n    if idx in mins:\n        ok=ok and fv==1\n    elif idx in dc:\n        pass\n    else:\n        ok=ok and fv==0\nresult = ok"},
  {"claim":"Q5 F=~A~B + B~C + AC covers exactly m(0,1,2,5,6,7)","code":"A,B,C=symbols('A B C'); f=(~A&~B)|(B&~C)|(A&C); cov=set(); \nfrom itertools import product\nfor a,b,c in product([0,1],repeat=3):\n    if f.subs({A:a,B:b,C:c}): cov.add(a*4+b*2+c)\nresult = cov=={0,1,2,5,6,7}"}
]