Question 1 of 6: Truth table, canonical and minimal POS, NOR-only synthesis

Question 1 (12 marks) — Truth table, canonical and minimal POS, NOR-only synthesis

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A three-variable switching function written as a sum of three product terms, $f = AB\overline{C} + BC + A\overline{B}C$, with the variable order $(A,B,C)$ and $A$ the most significant bit.

Find. (a) the complete truth table, (b) the canonical product-of-sums, (c) the minimal product-of-sums from a K-map, and (d) a minimum-gate NOR-only circuit.

Approach. Expand each product term into the minterms it covers to fill the truth table, read the maxterms off the rows where $f=0$ for the canonical POS, loop the zeros on a K-map to minimise the POS, then apply De Morgan twice to turn that POS into a NOR-NOR array.

1. Expand each product term into minterms. A product term missing $k$ variables covers $2^{k}$ minterms. $AB\overline{C}$ is fully specified, so it covers only $m_{6}$ (110). $BC$ omits $A$, so it covers $m_{3}$ (011) and $m_{7}$ (111). $A\overline{B}C$ is fully specified and covers $m_{5}$ (101). Collecting these gives the on-set $f = \sum m(3,5,6,7)$.
2. (a) Write the truth table. Every row not in the on-set carries $f=0$, so the off-set is $\{m_{0}, m_{1}, m_{2}, m_{4}\}$.

   Truth table of $f(A,B,C)$

   Row	A	B	C	f
   m0	0	0	0	0
   m1	0	0	1	0
   m2	0	1	0	0
   m3	0	1	1	1
   m4	1	0	0	0
   m5	1	0	1	1
   m6	1	1	0	1
   m7	1	1	1	1

   Reading the table across, $f=1$ exactly when at least two of the three inputs are 1 — this function is the three-input majority function, which is a useful check on everything that follows.
3. (b) Read the canonical POS off the zero rows. Each row with $f=0$ contributes one maxterm, and in a maxterm a variable appears uncomplemented when its row value is 0 (the opposite of the minterm convention). Rows 0, 1, 2 and 4 give $M_{0}=(A+B+C)$, $M_{1}=(A+B+\overline{C})$, $M_{2}=(A+\overline{B}+C)$ and $M_{4}=(\overline{A}+B+C)$, so$$f = \prod M(0,1,2,4) = (A+B+C)\,(A+B+\overline{C})\,(A+\overline{B}+C)\,(\overline{A}+B+C)$$Four sum terms of three literals each — 12 literals in total, which part (c) will cut in half.
4. (c) Minimise on the K-map by looping the zeros. To obtain a minimal POS directly, group the cells where $f=0$: each group of $2^{k}$ zeros collapses to one sum term. The off-set is $\{m_{0},m_{1},m_{2},m_{4}\}$, and $m_{0}$ pairs with each of the other three.
   Q1(c) K-map of $f$. Loops are drawn on the ZEROS, so each loop yields one sum term of the POS.
   The three pairs are $(m_{0},m_{1})$, which holds $A=0$ and $B=0$ fixed while $C$ changes, giving the sum term $(A+B)$; $(m_{0},m_{2})$, holding $A=0$ and $C=0$, giving $(A+C)$; and $(m_{0},m_{4})$, holding $B=0$ and $C=0$, giving $(B+C)$. Each of $m_{1}$, $m_{2}$ and $m_{4}$ has only one zero neighbour, so all three loops are essential and no smaller cover exists:$$\boxed{\,f = (A+B)\,(A+C)\,(B+C)\,}$$The literal count drops from 12 to 6, and the majority reading is confirmed: the product is 1 only when at least two inputs are 1.
5. (d) Convert the minimal POS to a NOR-only circuit. A POS maps onto a NOR-NOR array in exactly the way a SOP maps onto NAND-NAND. Apply the involution law and then De Morgan to the whole expression:$$f = \overline{\overline{(A+B)(A+C)(B+C)}} = \overline{\ \overline{(A+B)} + \overline{(A+C)} + \overline{(B+C)}\ }$$The inner terms are the outputs of three two-input NOR gates, and the outer complement of their sum is one three-input NOR. Because every literal appears uncomplemented, no inverters are needed:$$\boxed{\,f = \mathrm{NOR}\big(\mathrm{NOR}(A,B),\ \mathrm{NOR}(A,C),\ \mathrm{NOR}(B,C)\big)\ \Rightarrow\ 4\ \text{NOR gates}\,}$$
   Q1(d) minimum NOR-only realisation: three two-input NORs feeding one three-input NOR.
   Four gates is the minimum here. Starting instead from the SOP would need inverters for $\overline{B}$ and $\overline{C}$ plus a wider array, so the POS route is the cheaper one for this function.