Skip to content
CampusPrep
CS-304 · Digital Systems/Quick Revision Short Notes

Digital Systems (CS-304) - Unit 1 Short Notes

How unit 1 is examined

Number conversions, binary codes, Boolean algebra and functions, gates, K-maps, SOP-POS and NAND-NOR realisation; conversions, K-maps and NAND/NOR design carry most marks.

Review of number systems and number base conversions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A number system of base $r$ uses $r$ digits, and each digit position carries a weight that is a power of $r$; <mark>a digital system uses binary because a switch has exactly two stable states, ON and OFF</mark>.

Key points.

  1. Binary suits hardware because two stable states are easy to build and reliable, while decimal would need ten distinguishable voltage levels.
  2. Binary has high noise immunity, since the two levels are far apart and a small disturbance does not flip a bit.
  3. Binary needs only simple switching circuits, and it matches Boolean algebra (1 = true, 0 = false).
  4. Base $r$ to decimal: $N=\sum d_i r^i$, with negative powers after the point.
  5. Decimal to base $r$: divide the integer part repeatedly by $r$ and read remainders bottom-up; multiply the fraction repeatedly by $r$ and read the integer carries top-down (it may never terminate).
  6. Binary, octal and hex convert by grouping bits in 3s or 4s outward from the point; other pairs go via decimal.
  7. Complements: $(r-1)$'s $=(r^n-1)-N$ and $r$'s $=(r-1)$'s$+1$; to subtract $A-B$ add the complement of $B$.
  8. 9's or 1's complement: an end-around carry is added back, and if there is no carry the answer is negative, the complement of the sum. 10's or 2's complement: discard the carry for a positive answer, and with no carry take the complement of the sum for a negative one.

Solved conversions.

Given Result
$(41.513)_{10}$ $101001.100000110101_2=51.4065_8=29.835_{16}$ (fraction not exact)
$(138.32)_{10}$ $10001010.010100011110_2=212.2436_8=8A.51E_{16}$
$1024$; $23.25$ $2^{10}=10000000000_2$; $10111.01_2$ (0.25→0.5→1.0 gives .01)
$23$; $5.5$; $47.6$ $10111$; $101.1$; $101111.1001\,1001\ldots_2$
$(250.5)_{10}$ $372.4_8=3322.2_4$
$(5621.125)_{10}$; $(5621)_{16}$ $12765.1_8$; $0101\,0110\,0010\,0001_2$
$(B2F8)_{16}\to$ octal $1\,011\,001\,011\,111\,000=131370_8$
$(113.2)_8\to$ binary $001\,001\,011.010=1001011.01_2$
$(01000111)_2\to$ Gray; $(249)_{10}\to$ BCD $01100100$; $0010\,0100\,1001$
$(A2B.1A)_{16}\to$ decimal $2603+\tfrac{1}{16}+\tfrac{10}{256}=2603.1015625$
$(516)_7$ $5\cdot49+7+6=258_{10}=102_{16}$
$(2ED)_{16}$ $0010\,1110\,1101_2=1355_8$
$(2C6B.F2)_{16}$ $10110001101011.11110010_2=26153.744_8=11371.9453125_{10}$
$(1111)_2$; $10010.1011_2$; $(753)_8$ $15$; $18.6875$; $491$
$(4A3)_{16}$; $(101101.101)_2$; $(45.625)_{10}$ $0100\,1010\,0011$; $45.625$; $101101.101$
$(110101101)_2$; $(74)_{10}$ Excess-3; $(11011101)_2$ Gray $1AD_{16}$; $1010\,0111$; $10110011$
$(35614)_7$ $9223_{10}=5407_{12}$ (divide by 12: remainders 7, 0, 4, 5)
864: 9's, 10's complement $999-864=135$; $136$

Subtraction.

  • $FB2-DAB=207_{16}$ (borrow 16); $53BA-2BCD=27ED_{16}$; $113-57=56$.
  • $34-49$ by 9's complement: $99-49=50$, $34+50=84$, no carry, so negative: $-(99-84)=-15$; direct $34-49=-15$.
  • $X=111.101$, $Y=101.110$: $X+Y=1101.011$. $X-Y$: 2's complement of $Y$ is $010.010$, sum $1\,001.111$, discard carry, so $+1.111$. $Y-X$: $101.110+000.011=110.001$, no carry, so $-1.111$.
  • BCD $83+34$: $1000\,0011+0011\,0100=1011\,0111$; tens digit $>9$, add $0110$: $0001\,0001\,0111=117$.

Answer frame. Open with the base rule; show the division and multiplication steps for each number in two short columns; group bits for octal and hex; close with the boxed final answers in bold. For subtraction, write the complement, the add, the carry rule and the sign.

Pitfall: Reading division remainders top-down, or forgetting to pad zeros when grouping outward from the point, gives a wrong answer.

Asked: [7 marks] (Nov 2018) Why use binary and not decimal in digital electronics? Asked: [7 marks] (Nov 2018) Subtract FB2-DAB, 53BA-2BCD, 113-57. Asked: [7 marks] (Nov 2018) Convert 1111 to base 10; 10010.1011; 23, 5.5, 47.6 to binary. Asked: [7 marks] (Nov 2018) Subtract 49 from 34 using 9's complement; also directly. Asked: [7 marks] (Nov 2019, Dec 2020) Convert 41.513 (and 138.32) to binary, octal, hex. Asked: [7 marks] (Nov 2019) $(2C6B.F2)_{16}$ to base 2, 8, 10. Asked: [7 marks] (May 2019) $(5621.125)_{10}$ to octal; $(5621)_{16}$ to binary. Asked: [7 marks] (Jun 2020) X = 111.101, Y = 101.110: x+y, x-y, y-x by 2's complement. Asked: [7 marks] (Nov 2022) Convert 1024 and 23.25 to binary. Asked: [7 marks] (Jun 2023, Dec 2025) B2F8 to octal; 113.2 to binary; Gray; BCD; A2B.1A to decimal (Dec 2025 also 753, 4A3, 45.625, 74 Excess-3, Gray). Asked: [7 marks] (Dec 2023) Add 83 and 34 in BCD; convert $(35614)_7$ to base 12. Asked: [7 marks] (Dec 2024) $(516)_7$; 250.5 to base 8, 4; 2ED to base 8, 2; 9's and 10's complement of 864.

Binary codes

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A binary code assigns each decimal digit or symbol a fixed group of bits; <mark>in a weighted code each bit position has a fixed weight and the digit is the sum of the weights of its 1 bits</mark>.

Key points.

  1. BCD (8421) is a weighted code with weights 8, 4, 2, 1; digits 0-9 are 0000-1001 and 1010-1111 are invalid, so $249=0010\,0100\,1001$.
  2. 2421 is weighted (2, 4, 2, 1) and self-complementing, so the 9's complement of a digit is its bitwise inverse; 5211 behaves the same way.
  3. 84-2-1 has weights 8, 4, -2, -1 and is also self-complementing.
  4. Excess-3 is unweighted and self-complementing; it is BCD plus 0011, which avoids the all-zero code.
  5. Gray code changes one bit between consecutive numbers: $G_n=B_n$ and $G_i=B_{i+1}\oplus B_i$.
  6. Decimal 6: BCD $0110$, Excess-3 $1001$, Gray $0101$, 84-2-1 $1010$ ($8-2$), 2421 $1100$ ($2+4$).
  7. BCD to Excess-3 converter: 10-15 never occur, so they are don't-cares. Excess-3 outputs for 0-9 run $0011,0100,\ldots,1100$.

$$E_3=B_3+B_2B_1+B_2B_0,\quad E_2=B_2'B_1+B_2'B_0+B_2B_1'B_0',\quad E_1=B_1\odot B_0,\quad E_0=B_0'$$

  1. Binary to Gray converter: $G_3=A$, $G_2=A\oplus B$, $G_1=B\oplus C$, $G_0=C\oplus D$; three XOR gates and no other logic. The 16 Gray outputs for 0-15 are 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 424 338" width="424" height="338" role="img" aria-label="Binary ABCD to Gray G3G2G1G0; X1-X3 are XOR gates (A^B, B^C, C^D)"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L363,40" marker-end="url(#ah1)"/><path class="e" d="M58.2,45.5 L191.9,85.6" marker-end="url(#ah1)"/><path class="e" d="M58.6,122.3 L191.4,95.7" marker-end="url(#ah1)"/><path class="e" d="M58.2,131.5 L191.9,171.6" marker-end="url(#ah1)"/><path class="e" d="M58.6,208.3 L191.4,181.7" marker-end="url(#ah1)"/><path class="e" d="M58.2,217.5 L191.9,257.6" marker-end="url(#ah1)"/><path class="e" d="M58.6,294.3 L191.4,267.7" marker-end="url(#ah1)"/><path class="e" d="M230.6,95.3 L363.4,121.9" marker-end="url(#ah1)"/><path class="e" d="M230.6,181.3 L363.4,207.9" marker-end="url(#ah1)"/><path class="e" d="M230.6,267.3 L363.4,293.9" marker-end="url(#ah1)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="212" cy="91.6" r="18"/><text class="t" x="212" y="91.6" dy=".35em" text-anchor="middle">X1</text><circle class="n" cx="212" cy="177.6" r="18"/><text class="t" x="212" y="177.6" dy=".35em" text-anchor="middle">X2</text><circle class="n" cx="212" cy="263.6" r="18"/><text class="t" x="212" y="263.6" dy=".35em" text-anchor="middle">X3</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">G3</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">G2</text><circle class="n" cx="384" cy="212" r="18"/><text class="t" x="384" y="212" dy=".35em" text-anchor="middle">G1</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">G0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Binary ABCD to Gray G3G2G1G0; X1-X3 are XOR gates (A^B, B^C, C^D)</figcaption></figure>

Answer frame. Weighted code: define, then two codes (8421 and 2421) with weight rows and one example each, then the self-complementing remark. Converter designs: write the 16-row truth table (BCD ones list 10-15 as X), plot a K-map per output, give the equations, draw the gate circuit, and close with the gate count.

Asked: [7 marks] (Jun 2020) What are weighted codes? Explain any two. Asked: [7 marks] (Jun 2020) Design a combinational circuit to convert binary ABCD to Gray code. Asked: [7 marks] (Nov 2022) Design a combinational circuit to convert BCD to Excess-3 code. Asked: [7 marks] (Dec 2024) Represent decimal 6 in Excess-3, BCD, Gray, 84-2-1 and 2421.

Boolean algebra

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. Boolean algebra is the algebra of two-valued variables (0, 1) with the operations AND, OR and NOT; ==De Morgan's theorem states $(A+B)'=A'B'$ and $(AB)'=A'+B'$==.

Key points.

  1. The laws are commutative, associative, distributive ($A+BC=(A+B)(A+C)$), identity ($A+0=A$, $A\cdot1=A$), complement ($A+A'=1$, $AA'=0$), idempotent, absorption ($A+AB=A$).
  2. Duality: swapping AND with OR and 0 with 1 in a true identity gives another true identity.
  3. De Morgan proof by truth table (both sides equal in all four rows):
A B $(A+B)'$ $A'B'$ $(AB)'$ $A'+B'$
0 0 1 1 1 1
0 1 0 0 1 1
1 0 0 0 1 1
1 1 0 0 0 0
  1. Proof by complement: $(A+B)+A'B'=1$ and $(A+B)A'B'=0$, so $A'B'$ is the complement of $A+B$; it extends to any number of variables.
  2. Identity $A+BC=(A+B)(A+C)$: RHS $=A+AC+AB+BC=A(1+B+C)+BC=A+BC$.

Answer frame. State both theorems, give the truth table, add the complement proof, and close with the duality remark. For the identity, expand the RHS, apply absorption, and state LHS = RHS.

Pitfall: The paper's identity $A+BC=(A+B)(C+D)$ is false as printed (A=1, B=C=D=0 gives 1 against 0); prove the intended $(A+B)(A+C)$ and say so.

Asked: [7 marks] (Nov 2018) State and prove De Morgan's theorem. Asked: [7 marks] (Nov 2018) Prove $A+(B\cdot C)=(A+B)\cdot(C+D)$.

Boolean functions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A Boolean function maps binary variables to a binary output using AND, OR and NOT, and can be given as an expression, a truth table ($2^n$ rows) or a logic circuit; <mark>a function is written canonically as a sum of minterms $\sum m$ or a product of maxterms $\prod M$</mark>.

Key points.

  1. A minterm is an AND of all variables, and a maxterm is an OR of all variables, each in true or complemented form.
  2. $\sum m$ lists rows where $F=1$, and $\prod M$ lists rows where $F=0$; the two index lists together cover $0$ to $2^n-1$.
  3. To expand a product term, multiply by $(v+v')$ for each missing variable $v$.
  4. To read a circuit, name each gate output and combine them from inputs to output, then fill the truth table gate by gate.
  5. A don't-care $\phi$ may be 0 or 1, so $k$ don't-cares stand for $2^k$ functions.

Solved.

  • $F=(xy+z)(y+xz)=xy+yz+xz=\sum m(3,5,6,7)=\prod M(0,1,2,4)$.
  • Circuit: $P=AB$, $Q=P\oplus B=A'B$, $R=B'$, $S=(R+C)'=BC'$, so $z=Q+S=A'B+BC'$; the truth table gives $z=1$ only for $ABC=010,011,110$.
  • $f_3=f_1f_2$: certain 1s are 3, 5, 9; only 6 is undetermined (1 with a don't-care), and 11, 12, 7 are 0. So $f_3=\sum(3,5,9)+\phi(6)$, 2 functions.
  • $f_4=f_1+f_2$: 1s are 0, 1, 3, 4, 5, 6, 8, 9, 10; don't-cares 7, 11, 12, so 8 functions.
  • Network $f=f_1f_2+f_3$, with $f_1=xz+x'z'=\sum(0,2,5,7,8,10,13,15)$: where $f_1=0$ the terms 3, 6, 11, 12 need $f_3$, so $f_3=\sum(3,6,11,12)$; $f_2$ must be 1 at 0, 10 and 0 at 2, 5, 7, 8, 13, 15, so $f_2=w'x'y'+wyz'$.

Answer frame. Expand or read off the minterms first, then list $\sum m$, then complement for $\prod M$, then verify by checking the two lists partition all rows. For don't-care counting, classify each minterm as 1, 0 or $\phi$ and count $2^k$.

Asked: [7 marks] (Dec 2020) Give the Boolean expression and truth table (with intermediate gate outputs) for the given circuit. Asked: [7 marks] (Nov 2022) $f_1,f_2$ each represent four functions: find $f_3=f_1f_2$ and $f_4=f_1+f_2$ and how many functions each represents. Asked: [7 marks] (Nov 2022) Find $f_2$, $f_3$ so that $f_1f_2+f_3=\sum(0,3,6,10,11,12)$ with $f_1=xz+x'z'$. Asked: [7 marks] (Dec 2024) Express $(xy+z)(y+xz)$ as sum of minterms and product of maxterms.

Logic gates

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A logic gate is an electronic circuit with one or more inputs and one output that performs a basic Boolean operation, and it is the building block of every digital system; ==NAND is AND followed by NOT, $Y=\overline{AB}$, and NOR is OR followed by NOT, $Y=\overline{A+B}$==.

Key points.

  1. Basic gates are AND ($Y=AB$), OR ($Y=A+B$) and NOT ($Y=A'$).
  2. Universal gates are NAND and NOR, because either alone can build every other gate and any Boolean function.
  3. Special gates are XOR ($Y=A\oplus B$, high when inputs differ) and XNOR ($Y=A\odot B$, high when inputs are equal).
  4. NAND is 0 only when all inputs are 1, and NOR is 1 only when all inputs are 0.
A B AND OR NAND NOR XOR XNOR
0 0 0 0 1 1 0 1
0 1 0 1 1 0 1 0
1 0 0 1 1 0 1 0
1 1 1 1 0 0 0 1

NOT: input 0 gives 1, input 1 gives 0. Draw the standard symbols beside each row: bubble on the output for NAND, NOR, XNOR and NOT; curved input side for OR, NOR, XOR, XNOR.

Answer frame. Open with the definition; classify into basic, universal and special gates; draw each symbol with its expression and 2-input truth table; for universal gates add one line saying why (see NAND-NOR); close by naming which gates are universal.

Asked: [7 marks] (Nov 2018, Jun 2020) Define NAND and NOR gates with truth tables and output expressions; what are universal gates and why are they called so? Asked: [14 marks] (Jun 2023, Dec 2025) What are logic gates? Describe the various types; short note on logic gates.

Simplification of Boolean functions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. Simplification reduces an expression to fewer terms and literals using Boolean laws, so the circuit needs fewer gates.

Key points.

  1. Use $XX'=0$, $X+X'=1$, absorption and $X+X'Y=X+Y$ to remove literals.
  2. Merge identical sum factors first: $(C'+D)(C'+D+E)=C'+D$ (absorption).
  3. Then $(AB+C+D)(C'+D)=ABC'+ABD+CD+C'D+D=ABC'+D$.
  4. So $f=D+ABC'$.

Asked: [7 marks] (Nov 2018) Simplify $f=(AB+C+D)(\bar C+D)(\bar C+D+E)$.

Karnaugh map methods

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A Karnaugh map (K-map) is a graphical method that arranges the $2^n$ minterms of a function in a grid whose neighbouring cells differ in one variable, so adjacent 1s can be grouped to give a minimal expression; <mark>a group of $2^k$ adjacent 1s eliminates $k$ variables</mark>.

Key points.

  1. Rows and columns are labelled in Gray order (00, 01, 11, 10), so cells sharing an edge differ in one bit, and the map wraps around top-bottom and left-right.
  2. Groups must be rectangles of $1, 2, 4, 8, 16$ cells; make each as large as possible and cover every 1 at least once.
  3. Don't-cares are used only where they enlarge a group; they need not be covered.
  4. A prime implicant (PI) is a group that cannot be enlarged; an essential PI covers a 1 that no other PI covers, and it must appear in every solution.
  5. For SOP group the 1s; for POS group the 0s and write each group as a sum of complemented literals.
  6. A minimal SOP is not unique when two choices of PIs cover the remaining 1s at equal cost.
  7. Compared with Boolean algebra, a K-map is visual and systematic but practical only up to 4-5 variables:
Basis Boolean algebra K-map
Method Algebraic laws and postulates Graphical grouping
Variables Any number Up to 4-5
Effort Needs trial and skill Mechanical
Errors Easy to miss a law Errors show as missed groups
Result Not always minimal Minimal by construction

Example. $F(w,x,y,z)=\sum(0,1,2,4,5,6,8,9,12,13,14)$, rows $wx$, columns $yz$:

wx \ yz 00 01 11 10
00 1 1 0 1
01 1 1 0 1
11 1 1 0 1
10 1 1 0 0

Octet $y'$ (0,1,4,5,8,9,12,13), quad $xz'$ (4,6,12,14), quad $w'z'$ (0,2,4,6): F = y' + xz' + w'z'.

More solved (each drawn on its own map).

  • $\sum(1,3,5,7,9,10,12,13)$: $F=A'D+C'D+ABC'+AB'CD'$; complementing the 0s gives POS $F=(A+D)(A'+B'+C')(A'+C'+D')(B+C+D)$.
  • $f=A'+AC'+A'B'C+ABC'D+ABCD=\sum(0..3,4..7,8,9,12,13,15)$: f = A' + C' + BD.
  • $y=A'B'C'+B'C+A'B=\sum(0,1,2,3,5)$: y = A' + B'C.
  • $\prod M(1,3,5,7,8,9,11,12)+d(2,10)$: $F=\sum m(0,4,6,13,14,15)+d(2,10)$; PIs $W'Z'$ (0,4,6, using 2), $WXZ$ (13,15), $WXY$ (14,15), $YZ'$ (6,14, using 2,10); EPIs $W'Z'$ and $WXZ$. Minimal SOP $W'Z'+WXZ+WXY$ or $W'Z'+WXZ+YZ'$ (cost 7 literals): not unique.
  • $Y=\sum m(1,4,8,12,13,15)+d(3,14)$: Y = AB + A'B'D + AC'D' + BC'D'; AND-OR circuit.
  • $\sum m(1,2,3,5,7)$: F = C + A'B; AND-OR or NAND-NAND.
  • Design: $Y=1$ iff $A=C=1$ (B, D free): 16-row table with $Y=1$ for rows 10, 11, 14, 15; one quad (A=1, C=1) gives Y = AC, a single AND gate.

Answer frame. Open with the K-map definition; draw the labelled grid with Gray-coded axes; circle the groups; write the product term for each group; add them; close with the minimal expression. For design questions add the truth table first and the gate diagram last.

Pitfall: Labelling axes 00, 01, 10, 11 instead of Gray order 00, 01, 11, 10 puts wrong cells together and breaks every group.

Asked: [7 marks] (Nov 2018) Minimise $F=\sum(1,3,5,7,9,10,12,13)$ using a K-map and give the POS form. Asked: [7 marks] (Nov 2019, Dec 2025) Simplify $F(wxyz)=\sum(0,1,2,4,5,6,8,9,12,13,14)$ using a K-map; also $\sum m(1,2,3,5,7)$ with the logic diagram. Asked: [7 marks] (May 2019) What is a K-map? Simplify $f=\bar A+A\bar C+\bar A\bar B C+AB\bar C D+ABCD$. Asked: [7 marks] (Jun 2020) What is Boolean algebra? Compare it with a K-map; simplify $y=\bar A\bar B\bar C+\bar B C+\bar A B$. Asked: [10 marks] (Dec 2020) Design a 4-input circuit where $Y$ is high iff $A$ and $C$ are high: truth table, K-map, circuit. Asked: [7 marks] (Nov 2022) Find PIs, EPIs of $\prod M(1,3,5,7,8,9,11,12)+d(2,10)$; minimal SOP and uniqueness. Asked: [7 marks] (Dec 2023) Reduce $Y=\sum m(1,4,8,12,13,15)+d(3,14)$ with K-maps and implement with basic gates.

SOP-POS simplification

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. Sum of products (SOP) is an OR of AND terms, and product of sums (POS) is an AND of OR terms; <mark>SOP is read from the 1s of the K-map, and POS from the 0s with each literal complemented</mark>.

Key points.

  1. SOP group the 1s (and useful don't-cares) and write each group as a product; two-level AND-OR, or NAND-NAND.
  2. POS group the 0s (and useful don't-cares); each group gives a sum in which a variable appears complemented if it is 1 in the group; two-level OR-AND, or NOR-NOR.
  3. Canonical forms are $\sum m$ (rows where $F=1$) and $\prod M$ (rows where $F=0$).
  4. Complementing the minimal SOP of $F'$ gives the minimal POS of $F$.
  5. XNOR is expanded as $W'\odot Y=W'Y+WY'$ before simplifying.

Solved.

  • $F=\sum(0,1,2,3,7,8,10)+d(5,6,11,15)$: SOP $x'z'+w'z$; grouping the 0s (4, 9, 12, 13, 14) gives $F'=xz'+wz$, so POS $F=(x'+z)(w'+z')$.
  • $X'+X(X+Y')(Y+Z')=X'+X(Y+Z')=X'+Y+Z'$; this is already a single sum, so SOP and POS are $X'+Y+Z'$ (canonical $\prod M(5)$).
  • $F=WX'(Y'+Z')+X'Z'(W'Y+WY')=WX'Y'+WX'Z'+X'YZ'+WX'Y'Z'$; the second term is covered, giving F = WX'Y' + X'YZ' = $\sum(2,8,9,10)$.
  • NOR-NOR needs POS: zeros of $F$ give $F=X'(W+Y)(Y'+Z')=\overline{X+\overline{W+Y}+\overline{Y'+Z'}}$: NOR(W,Y), NOR(Y',Z') and X into a 3-input NOR, with Y', Z' from NOR inverters.
  • $F(x,y,z)=(xy+z)(y+xz)=xy+yz+xz=\sum m(3,5,6,7)=\prod M(0,1,2,4)$.

Answer frame. Open by naming the two forms; plot the K-map with d marked; group 1s for SOP, then group 0s for POS; write both results; for NOR-NOR, apply double complement to the POS and draw the circuit; close with the two expressions.

Asked: [7 marks] (Dec 2020, Jun 2023) Simplify $F$ with don't-cares $d$ in SOP and POS; convert $X'+X(X+Y')(Y+Z')$ to SOP and POS. Asked: [7 marks] (Nov 2022) Simplify $WX'(Y'+Z')+X'Z'(W'\odot Y)$ to minimal SOP and implement with NOR-NOR. Asked: [7 marks] (Dec 2024) Express $F=(xy+z)(y+xz)$ as a sum of minterms and a product of maxterms.

NAND-NOR implementation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. NAND and NOR are universal gates because each alone can realise NOT, AND and OR, and hence any function; <mark>a SOP maps to a two-level NAND-NAND circuit and a POS maps to NOR-NOR</mark>.

Key points.

  1. NAND: NOT $=\overline{AA}$, AND $=\overline{\overline{AB}}$ (NAND then NAND-as-NOT), OR $=\overline{\overline A\,\overline B}$.
  2. NOR: NOT $=\overline{A+A}$, OR $=\overline{\overline{A+B}}$, AND $=\overline{\overline A+\overline B}=AB$.
  3. Steps for NAND-NAND: simplify to SOP, double-complement, apply De Morgan once so the form is $F=\overline{\overline{T_1}\;\overline{T_2}\cdots}$, each $\overline{T_i}$ a NAND; single literals needing a complement use a NAND inverter.
  4. Steps for NOR-NOR: write POS, double-complement and use De Morgan on the inner complement.
  5. NAND from NOR: $\overline{AB}=\overline{\,\overline{\overline A+\overline B}\,}$, four NOR gates (two inverters, one NOR giving AB, one inverter).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 596 252" width="596" height="252" role="img" aria-label="NAND from NOR: N1, N2 invert A and B; N3 gives AB; N4 (inputs tied) inverts to Y = (AB)'"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah2)"/><path class="e" d="M59,212 L148,212" marker-end="url(#ah2)"/><path class="e" d="M184.8,50.5 L280.5,114.4" marker-end="url(#ah2)"/><path class="e" d="M184.8,201.5 L280.5,137.6" marker-end="url(#ah2)"/><path class="e" d="M317,126 L406,126" marker-end="url(#ah2)"/><path class="e" d="M446,126 L535,126" marker-end="url(#ah2)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">N1</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">N2</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">N3</text><circle class="n" cx="427" cy="126" r="18"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">N4</text><circle class="n" cx="556" cy="126" r="18"/><text class="t" x="556" y="126" dy=".35em" text-anchor="middle">Y</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">NAND from NOR: N1, N2 invert A and B; N3 gives AB; N4 (inputs tied) inverts to Y = (AB)'</figcaption></figure>

Solved.

  • $F=A(B+CD)+BC'=AB+ACD+BC'$, so $F=\overline{\overline{AB}\cdot\overline{ACD}\cdot\overline{BC'}}$: NAND for AB, ACD and BC' (C' from NAND(C,C)), then one 3-input NAND: 5 gates.
  • $F=AB+A'C=\overline{\overline{AB}\cdot\overline{A'C}}$: NAND(A,A) for $A'$, two NANDs for AB and A'C, one output NAND: 4 gates.
  • $y'z'+w'x'z'+w'xyz'+wyz'$: all eight $z=0$ cells are 1, so $F=z'$: one NAND(z,z) or NOR(z,z).

Answer frame. Open with why NAND and NOR are universal; draw NOT, OR, AND (or NAND) from the named gate, each with its expression; for functions, simplify, apply double complement, then draw the two-level circuit; close with the gate count.

Asked: [7 marks] (Nov 2019, Dec 2025) Implement $F=A(B+CD)+BC'$ (and $F=AB+A'C$) with NAND gates only. Asked: [7 marks] (May 2019) Design a NAND gate using NOR gates only. Asked: [7 marks] (Dec 2023) Explain how the basic gates are realised using NOR gates. Asked: [7 marks] (Dec 2024) Simplify $y'z'+w'x'z'+w'xyz'+wyz'$ and implement with universal gates only.

Last-minute revision

  • Binary uses two stable states, high noise immunity and simple switching.
  • Decimal to binary: integer by repeated division by 2, fraction by repeated multiplication by 2.
  • Octal groups 3 bits and hex groups 4 bits from the radix point.
  • 9's complement is $(10^n-1)-N$, and 10's is that plus 1; 34-49 by 9's complement gives -15.
  • $(41.513)_{10}=101001.100000110101_2$; $(23.25)_{10}=10111.01_2$; $(249)_{10}$ BCD $=0010\,0100\,1001$.
  • Decimal 6: BCD 0110, Excess-3 1001, Gray 0101, 84-2-1 1010, 2421 1100.
  • Gray: $G_i=B_{i+1}\oplus B_i$; Excess-3: $E_1=B_1\odot B_0$, $E_0=B_0'$.
  • De Morgan: $(A+B)'=A'B'$, $(AB)'=A'+B'$.
  • $(xy+z)(y+xz)=\sum m(3,5,6,7)=\prod M(0,1,2,4)$.
  • K-map: axes in Gray order; a group of $2^k$ cells drops $k$ variables; SOP from 1s, POS from 0s.
  • NAND and NOR are universal; SOP goes to NAND-NAND and POS to NOR-NOR.

Memory hooks

  • Fractions multiply, integers divide: remainders bottom-up, carries top-down.
  • 3 for octal, 4 for hex, group from the point.
  • Gray = neighbours XOR; MSB copies down.
  • K-map axes go 00-01-11-10, never 10 before 11.
  • Break the bar, change the sign: De Morgan turns AND into OR.
  • NAND-NAND for SOP, NOR-NOR for POS.

Coverage checklist

  • Review of number systems and number base conversions: all 12 number-system and complement questions (Nov 2018 - Dec 2025).
  • Binary codes: weighted codes, binary to Gray, BCD to Excess-3, decimal 6 in five codes.
  • Boolean algebra: De Morgan proof, identity proof.
  • Boolean functions: circuit to expression, don't-care counting, network design, canonical forms.
  • Logic gates: NAND/NOR definitions, types of gates.
  • Simplification of Boolean functions: algebraic simplification of the Nov 2018 expression.
  • Karnaugh map methods: all 7 K-map questions including PI/EPI, design and comparison.
  • SOP-POS simplification: SOP and POS with don't-cares, NOR-NOR, canonical forms.
  • NAND-NOR implementation: NAND-only, NAND from NOR, basic gates from NOR, universal-gate implementation.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in