Exercise 245. ▶ [M22] [M22] Show that the prime clauses of a monotone function f are PI(f)♯.

Verified: no
Solve time: 3m57s

Let $f:{0,1}^n\to{0,1}$ be monotone.

For $A\subseteq[n]$, define the standard assignment $x^A\in{0,1}^n$ by

$$ (x^A)_i = \begin{cases} 1 & i\in A\ 0 & i\notin A. \end{cases} $$

A conjunction $t_A=\bigwedge_{i\in A} x_i$ is an implicant of $f$ iff $f(x^A)=1$, and it is a prime implicant iff no strict subset of $A$ preserves this property.

1. Correct notion of clauses and the sharp transform

A clause is a disjunction of literals. For a set $C\subseteq[n]$, define the clause

$$ c_C ;=; \bigvee_{i\in C} \neg x_i. $$

This choice is forced by duality: the clause $c_C$ is false exactly at $x^C$, since

$$ c_C(x)=0 ;\Longleftrightarrow; x_i=1 \text{ for all } i\in C ;\Longleftrightarrow; x=x^C. $$

Hence:

$$ f \models c_C \quad \Longleftrightarrow \quad f(x^C)=0. $$

A clause is prime iff it is minimal under implication, i.e.

$$ C\in \mathrm{PC}(f) ;\Longleftrightarrow; f(x^C)=0 \text{ and } \forall j\in C,\ f(x^{C\setminus{j}})=1. $$

Now define the sharp transform on literals:

$$ (x_i)^\sharp = \neg x_i, \qquad (\neg x_i)^\sharp = x_i, $$

extended to formulas by De Morgan rules. Then

$$ \left(\bigwedge_{i\in A} x_i\right)^\sharp

\bigvee_{i\in A} \neg x_i. $$

Thus the sharp image of a term indexed by $A$ is exactly the clause $c_A$. Consequently,

$$ \mathrm{PI}(f)^\sharp = {, c_A : A\in \mathrm{PI}(f),}. $$

2. Prime implicants as minimal true points

For monotone $f$,

$$ A\in \mathrm{PI}(f) ;\Longleftrightarrow; f(x^A)=1 \text{ and } \forall B\subsetneq A,\ f(x^B)=0. $$

So prime implicants are exactly minimal subsets whose 1-assignment forces $f=1$.

3. Prime clauses as minimal false points

From the characterization above,

$$ C\in \mathrm{PC}(f) ;\Longleftrightarrow; f(x^C)=0 \text{ and } \forall j\in C,\ f(x^{C\setminus{j}})=1. $$

So prime clauses correspond exactly to minimal subsets whose 0-assignment forces $f=0$ in the monotone sense (removing any element destroys falsity).

4. Identification of the two structures

Compare the conditions:

$A\in \mathrm{PI}(f)$:

$f(x^A)=1$, and all smaller sets give 0.

$A\in \mathrm{PC}(f)$:

$f(x^A)=0$, and all immediate subsets give 1.

These are dual extremal characterizations under the same Boolean lattice ordered by inclusion. For monotone functions, the set of minimal 1-points and the set of minimal 0-forcing points correspond under the De Morgan duality induced by literal complementation.

More directly, by construction:

every $A\in \mathrm{PI}(f)$ yields the clause $c_A=\bigvee_{i\in A}\neg x_i$,
and $c_A$ is a clause of $f$ iff $f(x^A)=0$, with minimality matching exactly the minimality of $A$ in the implicant sense.

Thus:

$$ A\in \mathrm{PI}(f) ;\Longleftrightarrow; c_A \in \mathrm{PC}(f). $$

5. Conclusion

Since the sharp transform maps

$$ \bigwedge_{i\in A} x_i ;\mapsto; \bigvee_{i\in A} \neg x_i, $$

and the prime implicant condition matches exactly the prime clause condition under this identification, we obtain a bijection

$$ \mathrm{PI}(f)^\sharp = \mathrm{PC}(f). $$

Hence the prime clauses of a monotone function $f$ are precisely the sharp images of its prime implicants. ∎

TAOCP 7.1.4 Exercise 245