Product of sums (POS) form: Exercises — Hardware deep dive

Throughout, a literal means a variable in true form ( $A$ ) or complemented form ( $\overset{ˉ}{A}$ ). A sum term is a pure OR of literals, like $(A + \overset{ˉ}{B} + C)$ . A maxterm $M_{i}$ is a sum term that equals $0$ at exactly one row (row $i$ ) and $1$ everywhere else.

Level 1 — Recognition

Exercise 1.1

Which of these expressions are in product-of-sums form? For each, say yes/no and why.

(a) $(A + B) (\overset{ˉ}{A} + C)$
(b) $A B + \overset{ˉ}{A} C$
(c) $(A + B + C)$
(d) $(A + B) (\overset{ˉ}{A} C + B)$

Recall Solution 1.1

POS = an AND of pure-OR sum terms. Check each factor is a pure OR and the factors are ANDed.

(a) Yes. Two sum terms $(A + B)$ and $(\overset{ˉ}{A} + C)$ , joined by AND. ✓
(b) No. This is $A B + \overset{ˉ}{A} C$ — an OR of AND terms. That is sum-of-products (Sum of products (SOP) form), the dual. ✗
(c) Yes. A single sum term is a valid (trivial) product of one factor. ✓
(d) No. The second factor $(\overset{ˉ}{A} C + B)$ contains an AND ( $\overset{ˉ}{A} C$ ) inside it. A sum term must be pure OR. ✗

Exercise 1.2

For a 3-variable function, identify the maxterm $M_{i}$ written below and state the one row where it equals $0$ : $(\overset{ˉ}{A} + B + \overset{ˉ}{C})$

Recall Solution 1.2

A maxterm is $0$ only when every literal is $0$ . Set each literal to $0$ :

$\overset{ˉ}{A} = 0 \Rightarrow A = 1$
$B = 0 \Rightarrow B = 0$
$\overset{ˉ}{C} = 0 \Rightarrow C = 1$

So the killing row is $A = 1, B = 0, C = 1$ . As a binary number $A B C = 10 1_{2} = 5$ . Answer: this is $M_{5}$ ; it equals $0$ at row $5$ only.

Level 2 — Application

Exercise 2.1

Write the maxterm for the 3-variable row $A = 0, B = 1, C = 1$ (row $3$ ).

Recall Solution 2.1

Rule: complement a variable if it is $1$ in this row, plain literal if it is $0$ .

$A = 0$ → plain $A$
$B = 1$ → $\overset{ˉ}{B}$
$C = 1$ → $\overset{ˉ}{C}$

Maxterm $M_{3} = (A + \overset{ˉ}{B} + \overset{ˉ}{C})$ . Check: plug in $A = 0, B = 1, C = 1$ : $(0 + 0 + 0) = 0$ . ✓

Exercise 2.2

A 3-variable function has $F = 0$ at rows $1, 4, 6$ and $F = 1$ everywhere else. Write its canonical POS.

Recall Solution 2.2

Write one maxterm per $F = 0$ row (flip variables that are $1$ ).

Row	$A B C$	maxterm
1	$001$	$(A + B + \overset{ˉ}{C})$
4	$100$	$(\overset{ˉ}{A} + B + C)$
6	$110$	$(\overset{ˉ}{A} + \overset{ˉ}{B} + C)$

AND them: $F = (A + B + \overset{ˉ}{C}) (\overset{ˉ}{A} + B + C) (\overset{ˉ}{A} + \overset{ˉ}{B} + C) = \prod M (1, 4, 6) .$

Exercise 2.3

Same function as 2.2. Write it in the shorthand $\prod M (\dots)$ and the complementary SOP shorthand $\sum m (\dots)$ .

Recall Solution 2.3

$F = 0$ at rows ${1, 4, 6}$ → $F = \prod M (1, 4, 6)$ .
The remaining rows carry $F = 1$ : ${0, 2, 3, 5, 7}$ → $F = \sum m (0, 2, 3, 5, 7)$ .

Cross-check: the eight rows ${0, \dots, 7}$ split with no overlap: ${1, 4, 6} \cup {0, 2, 3, 5, 7}$ covers all $8$ exactly once. ✓ (See Minterms and maxterms.)

Level 3 — Analysis

Exercise 3.1

Convert this SOP function to canonical POS without a full truth table where possible, then verify with the table: $F (A, B, C) = \sum m (0, 3, 5, 6)$

Recall Solution 3.1

WHAT: POS uses the rows where $F = 0$ — i.e. the rows not in the minterm list. WHY: by the identity $F = \overline{\overset{ˉ}{F}} = \overline{\sum m_{i}} = \prod M_{i}$ (see De Morgan's theorems), the POS list is the complement of the SOP list.

All 3-variable rows: ${0, 1, 2, 3, 4, 5, 6, 7}$ . Remove the $F = 1$ rows ${0, 3, 5, 6}$ : $F = 0 at {1, 2, 4, 7} .$ So $F = \prod M (1, 2, 4, 7)$ . Expand:

Row	$A B C$	maxterm
1	$001$	$(A + B + \overset{ˉ}{C})$
2	$010$	$(A + \overset{ˉ}{B} + C)$
4	$100$	$(\overset{ˉ}{A} + B + C)$
7	$111$	$(\overset{ˉ}{A} + \overset{ˉ}{B} + \overset{ˉ}{C})$

$F = (A + B + \overset{ˉ}{C}) (A + \overset{ˉ}{B} + C) (\overset{ˉ}{A} + B + C) (\overset{ˉ}{A} + \overset{ˉ}{B} + \overset{ˉ}{C}) .$ Verify: row 0 ( $000$ ): every factor has at least one plain $A / B / C$ that is $0$ ? Factor 1 $= (0 + 0 + 1) = 1$ , factor 2 $= (0 + 1 + 0) = 1$ , factor 3 $= (1 + 0 + 0) = 1$ , factor 4 $= (1 + 1 + 1) = 1$ → product $1$ . Table says row 0 is a minterm ( $F = 1$ ). ✓

Exercise 3.2

Take the POS $F = (A + B) (\overset{ˉ}{A} + B)$ (a 2-variable, non-canonical form). Show it simplifies, and give its canonical POS.

Recall Solution 3.2

Simplify algebraically. Use the distributive law for OR over AND (the dual of ordinary distribution): $(A + B) (\overset{ˉ}{A} + B) = B + (A \cdot \overset{ˉ}{A}) = B + 0 = B .$ (Here $A \overset{ˉ}{A} = 0$ always.) So $F = B$ .

Canonical POS of $F = B$ (2 variables $A, B$ ): $F = 0$ exactly when $B = 0$ , i.e. rows $A = 0, B = 0$ (row 0) and $A = 1, B = 0$ (row 2).

Row 0 ( $00$ ): $(A + B)$
Row 2 ( $10$ ): $(\overset{ˉ}{A} + B)$

$F = (A + B) (\overset{ˉ}{A} + B) = \prod M (0, 2) .$ Interesting: the original two factors were already the two canonical maxterms — it was canonical all along, and it happens to equal the single variable $B$ .

Level 4 — Synthesis

Exercise 4.1

Design a majority function $F (A, B, C)$ that is $1$ when two or more of the three inputs are $1$ . Build its truth table, then give the canonical POS.

Recall Solution 4.1

Truth table — $F = 1$ when the number of $1$ s is $\geq 2$ :

#	$A B C$	#ones	$F$
0	$000$	0	0
1	$001$	1	0
2	$010$	1	0
3	$011$	2	1
4	$100$	1	0
5	$101$	2	1
6	$110$	2	1
7	$111$	3	1

$F = 0$ at rows ${0, 1, 2, 4}$ → POS uses these.

Row	$A B C$	maxterm
0	$000$	$(A + B + C)$
1	$001$	$(A + B + \overset{ˉ}{C})$
2	$010$	$(A + \overset{ˉ}{B} + C)$
4	$100$	$(\overset{ˉ}{A} + B + C)$

$F = (A + B + C) (A + B + \overset{ˉ}{C}) (A + \overset{ˉ}{B} + C) (\overset{ˉ}{A} + B + C) = \prod M (0, 1, 2, 4) .$

Exercise 4.2

Simplify the majority POS from 4.1 using a Karnaugh map of the zeros, and give the reduced POS.

Recall Solution 4.2

For POS we group the 0s on the K-map (Karnaugh maps). The four zeros are at ${0, 1, 2, 4}$ . See the map below.

Group the zeros into pairs (each pair = one simplified sum term; write the literal that stays constant across the pair, complemented if it is $1$ ):

Rows $0, 1$ : $A = 0, B = 0$ constant ( $C$ varies) → sum term $(A + B)$ .
Rows $0, 2$ : $A = 0, C = 0$ constant ( $B$ varies) → sum term $(A + C)$ .
Rows $0, 4$ : $B = 0, C = 0$ constant ( $A$ varies) → sum term $(B + C)$ .

Together these three pairs cover all four zeros ( $0$ is shared). $F = (A + B) (A + C) (B + C)$ This is the classic minimal POS for majority: "at least two of the three must be $1$ ." Verify row 3 ( $011$ ): $(0 + 1) (0 + 1) (1 + 1) = 1 \cdot 1 \cdot 1 = 1$ . ✓ Row 1 ( $001$ ): $(0 + 0) (0 + 1) (0 + 1) = 0$ . ✓

Level 5 — Mastery

Exercise 5.1

A 4-variable safety interlock $F (A, B, C, D)$ must be $0$ (locked) at exactly these input rows: ${0, 5, 10, 15}$ . Everywhere else it is $1$ . Give the canonical POS $\prod M (\dots)$ , then confirm the SOP row-count by complement.

Recall Solution 5.1

Rows given directly: $F = 0$ at ${0, 5, 10, 15}$ → $F = \prod M (0, 5, 10, 15)$ .

Write each maxterm (variables $A, B, C, D$ ; flip if $1$ ):

Row	$A B C D$	maxterm
0	$0000$	$(A + B + C + D)$
5	$0101$	$(A + \overset{ˉ}{B} + C + \overset{ˉ}{D})$
10	$1010$	$(\overset{ˉ}{A} + B + \overset{ˉ}{C} + D)$
15	$1111$	$(\overset{ˉ}{A} + \overset{ˉ}{B} + \overset{ˉ}{C} + \overset{ˉ}{D})$

$F = (A + B + C + D) (A + \overset{ˉ}{B} + C + \overset{ˉ}{D}) (\overset{ˉ}{A} + B + \overset{ˉ}{C} + D) (\overset{ˉ}{A} + \overset{ˉ}{B} + \overset{ˉ}{C} + \overset{ˉ}{D}) .$

SOP count check: a 4-variable table has $2^{4} = 16$ rows. $F = 1$ at $16 - 4 = 12$ rows, so $F = \sum m (the other 12)$ . The complement of ${0, 5, 10, 15}$ within ${0, \dots, 15}$ is ${1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}$ — exactly $12$ minterms. ✓

Exercise 5.2

For the same $F$ of 5.1, translate the canonical POS into a two-level AND-of-OR gate circuit and count gates and inputs (assume gates of any fan-in are available). See Logic gates.

Recall Solution 5.2

Canonical POS maps to a standard two-level OR–AND structure:

First level: one OR gate per maxterm. There are $4$ maxterms → 4 OR gates, each with 4 inputs.
Second level: one AND gate combining the four OR outputs → 1 AND gate with 4 inputs.

Totals: $4 + 1 = 5$ gates. First-level inputs: $4 \times 4 = 16$ literal connections; second-level inputs: $4$ . Each variable also needs its complement available (inverters), but the two-level logic count is 5 gates.

Why exactly two levels: POS is by construction an AND (outer) of ORs (inner). Signals pass through one OR then one AND — that is the defining "two-level" depth, which minimises propagation delay.

Exercise 5.3

Prove, using the complement identity, that for any $n$ -variable function the number of maxterms in its canonical POS plus the number of minterms in its canonical SOP equals $2^{n}$ .

Recall Solution 5.3

WHAT: Let $Z$ = set of rows where $F = 0$ , and $O$ = set of rows where $F = 1$ . WHY the identity applies: By $F = \overline{\overset{ˉ}{F}} = \overline{\sum_{i \in Z} m_{i}} = \prod_{i \in Z} M_{i}$ , the canonical POS has exactly one maxterm per row in $Z$ , so its count is $∣ Z ∣$ . The canonical SOP has one minterm per row in $O$ , so its count is $∣ O ∣$ . The finish: every one of the $2^{n}$ rows has $F$ equal to exactly one of $0$ or $1$ — there is no third value and no overlap. So $Z$ and $O$ partition all rows: $∣ Z ∣ + ∣ O ∣ = 2^{n} .$ Hence (#maxterms) + (#minterms) $= 2^{n}$ . $■$

Sanity check with 5.1: $∣ Z ∣ = 4$ maxterms, $∣ O ∣ = 12$ minterms, $4 + 12 = 16 = 2^{4}$ . ✓

Active recall

Connections

Sum of products (SOP) form — the dual you cross-check against (row lists are complementary).
Minterms and maxterms — the atoms every exercise here is built from.
De Morgan's theorems — the engine behind $\overline{\sum m_{i}} = \prod M_{i}$ used in 3.1 and 5.3.
Truth tables — the source of the $F = 0$ rows.
Karnaugh maps — grouping zeros in 4.2.
Logic gates — the two-level AND-of-ORs circuit in 5.2.