TAOCP 7.1.2 Exercise 50

Let $x_1x_2x_3x_4$ be the binary representation of $0,\dots,15$ (with $x_1$ the most significant bit).

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.2: Boolean Evaluation

Exercise 50. [24] [24] What are the prime implicants and prime clauses of the prime-number function (35)? Express that function in (a) DNF (b) CNF of minimum length.

Verified: yes
Solve time: 4m51s

Let $x_1x_2x_3x_4$ be the binary representation of $0,\dots,15$ (with $x_1$ the most significant bit). The function $f$ is defined by

$$ f=1 \iff {x_1x_2x_3x_4}\in {2,3,5,7,11,13}. $$

Hence the minterms are

$$ m_2,m_3,m_5,m_7,m_{11},m_{13}. $$

1. Prime implicants

We determine all maximal adjacency groupings in the 4-variable K-map.

From $m_2=0010$

It differs from $m_3=0011$ in $x_4$, giving

$$ m_2,m_3 ;\Rightarrow; \neg x_1 \neg x_2 x_3. $$

From $m_3=0011$

It has three 1-adjacencies:

  • with $m_2$: $\neg x_1\neg x_2 x_3$
  • with $m_7=0111$: $\neg x_1 x_3 x_4$
  • with $m_{11}=1011$: $\neg x_2 x_3 x_4$

Thus it participates in three prime implicants.

From $m_5=0101$

Adjacencies:

  • with $m_7=0111$:

$$ \neg x_1 x_2 x_4 $$

  • with $m_{13}=1101$:

$$ x_2 \neg x_3 x_4 $$

From $m_7=0111$

Already accounted for via maximal pairings above.

From $m_{11}=1011$

Only adjacency is with $m_3$, giving:

$$ \neg x_2 x_3 x_4. $$

From $m_{13}=1101$

Only adjacency is with $m_5$, giving:

$$ x_2 \neg x_3 x_4. $$

Prime implicants (complete set)

No grouping extends further in any case, since each 3-literal implicant would require adding a second 1-cell that does not exist in the required subcubes.

Thus the prime implicants are:

$$ \boxed{ \neg x_1\neg x_2 x_3,; \neg x_1 x_3 x_4,; \neg x_2 x_3 x_4,; \neg x_1 x_2 x_4,; x_2 \neg x_3 x_4 }. $$

2. Minimum DNF

We identify essential implicants.

  • $m_2$ is covered only by $\neg x_1\neg x_2 x_3$, so it is essential.
  • $m_{11}$ is covered only by $\neg x_2 x_3 x_4$, so it is essential.
  • $m_{13}$ is covered only by $x_2 \neg x_3 x_4$, so it is essential.

So we must include:

$$ \neg x_1\neg x_2 x_3,\quad \neg x_2 x_3 x_4,\quad x_2 \neg x_3 x_4. $$

These cover:

  • $m_2$
  • $m_{11}$
  • $m_{13}$
  • $m_3$ (via either of the first two)
  • $m_5$ (via the third)
  • $m_7$ remains uncovered.

To cover $m_7$, we may use either:

$$ \neg x_1 x_3 x_4 \quad \text{or} \quad \neg x_1 x_2 x_4. $$

Hence any minimum DNF has 4 terms. One valid minimal choice is:

$$ \boxed{ f= (\neg x_1\neg x_2 x_3) ;\lor; (\neg x_2 x_3 x_4) ;\lor; (x_2 \neg x_3 x_4) ;\lor; (\neg x_1 x_3 x_4) }. $$

3. Prime clauses and minimum CNF

We determine maximal groups of zeros:

$$ {0,1,4,6,8,9,10,12,14,15}. $$

Group 1: ${0,1,8,9}$

Here $x_2=0$ and $x_3=0$, hence the clause

$$ (x_2 \lor x_3). $$

Group 2: ${4,6,12,14}$

Here $x_2=1$ and $x_4=0$, hence

$$ (\neg x_2 \lor x_4). $$

Group 3: ${8,10,12,14}$

Here $x_1=1$ and $x_4=0$, hence

$$ (\neg x_1 \lor x_4). $$

CNF verification

All zeros satisfy all three clauses, and every prime minterm satisfies each clause as well.

No clause can be enlarged without including a 1-cell, so all three are prime clauses.

Minimum CNF

$$ \boxed{ f = (x_2 \lor x_3) ;\land; (\neg x_2 \lor x_4) ;\land; (\neg x_1 \lor x_4) }. $$

Final answer summary

Prime implicants

$$ \neg x_1\neg x_2 x_3,; \neg x_1 x_3 x_4,; \neg x_2 x_3 x_4,; \neg x_1 x_2 x_4,; x_2 \neg x_3 x_4. $$

Minimum DNF

Any 4-term cover of the form above, e.g.

$$ (\neg x_1\neg x_2 x_3)\vee(\neg x_2 x_3 x_4)\vee(x_2 \neg x_3 x_4)\vee(\neg x_1 x_3 x_4). $$

Prime clauses

$$ (x_2 \lor x_3),;(\neg x_2 \lor x_4),;(\neg x_1 \lor x_4). $$

Minimum CNF

$$ (x_2 \lor x_3)\land(\neg x_2 \lor x_4)\land(\neg x_1 \lor x_4). $$