TAOCP 7.1.1 Exercise 20

Let $p$ be a prime implicant of $f \wedge g$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.1: Boolean Basics

Exercise 20. [M21] [M21] True or false: Every prime implicant of $f\wedge g$ can be written $f'\wedge g'$, where $f'$ is a prime implicant of $f$ and $g'$ is a prime implicant of $g$.

Verified: no
Solve time: 4m41s

Let $p$ be a prime implicant of $f \wedge g$. We identify $p$ with its set of literals $S$.

A cube $c \subseteq p$ means a subcube obtained by deleting literals from $p$.

Step 1: Literal-wise necessity relative to $f$ and $g$

Fix a literal $l \in S$. Since $p$ is a prime implicant of $f \wedge g$, the cube $p \setminus {l}$ is not an implicant of $f \wedge g$. Hence there exists an assignment satisfying $p \setminus {l}$ but falsifying $f \wedge g$. Therefore it falsifies at least one of $f$ or $g$.

We use this to define two sets:

  • $F_0 = {, l \in S : p \setminus {l} \not\models f ,}$
  • $G_0 = {, l \in S : p \setminus {l} \not\models g ,}$

So a literal lies in $F_0$ if removing it breaks implication of $f$, and similarly for $g$.

Then every $l \in S$ satisfies

$$ l \in F_0 \cup G_0, $$

because otherwise removing $l$ would preserve both $f$ and $g$, contradicting that $p$ is a prime implicant of $f \wedge g$. Hence

$$ S = F_0 \cup G_0. $$

Step 2: Constructing implicants inside $p$

We now construct cubes:

  • $f' := p$ restricted to literals in $F_0$
  • $g' := p$ restricted to literals in $G_0$

Formally, $f'$ is the cube containing exactly the literals in $F_0$, and similarly for $g'$.

Claim: $f'$ implies $f$

Start from $p \models f$. Now remove from $p$ all literals not in $F_0$, one by one.

If $l \notin F_0$, then by definition $p \setminus {l} \models f$, so deleting $l$ preserves implication of $f$.

Thus every deletion step preserves implication of $f$, so the final cube $f'$ still satisfies

$$ f' \models f. $$

Claim: $f'$ is a prime implicant of $f$

If a literal $l \in F_0$ were removable while preserving $f$, then $p \setminus {l}$ would also imply $f$, contradicting $l \in F_0$. Hence no literal in $f'$ is redundant, so $f'$ is a prime implicant of $f$.

The same argument shows that $g'$ is a prime implicant of $g$.

Step 3: Reconstructing $p$

We show that the literals of $f' \wedge g'$ equal those of $p$.

By construction:

  • $f'$ contains exactly $F_0$
  • $g'$ contains exactly $G_0$

Hence

$$ f' \wedge g' \equiv \text{cube with literals } F_0 \cup G_0. $$

From Step 1, $F_0 \cup G_0 = S$, so

$$ f' \wedge g' = p. $$

Step 4: Conclusion

We have constructed:

  • a prime implicant $f'$ of $f$,
  • a prime implicant $g'$ of $g$,
  • such that their conjunction equals $p$.

Therefore every prime implicant of $f \wedge g$ factors in the required way.

$$ \boxed{\text{True}} $$