Exercise 26. [M25] [M25] Let $\mathcal{F}$ and $\mathcal{G}$ be the families of index sets for the prime clauses and prime implicants of a monotone CNF and a monotone DNF:

$$f(x) = \bigwedge_{I\in\mathcal{F}}\bigvee_{i\in I} x_i;\qquad g(x) = \bigvee_{J\in\mathcal{G}}\bigwedge_{j\in J} x_j$$

Efficiently exhibit an $x$ such that $f(x)\ne g(x)$ if any of the following conditions hold:

a) There is an $I\in\mathcal{F}$ and a $J\in\mathcal{G}$ with $I\cap J=\emptyset$.

b) $\bigcup_{I\in\mathcal{F}}I\ne\bigcup_{J\in\mathcal{G}}J$.

c) There's an $I\in\mathcal{F}$ with $|I|>|\mathcal{G}|$.

d) $\sum_{J\in\mathcal{G}}\sum_{j\in J}2^{-|J|}>2^n$, where $n=\bigl|\bigcup_{I\in\mathcal{F}}I\bigr|$.

Verified: no
Solve time: 6m23s

Let

$$ f(x)=\bigwedge_{I\in\mathcal F}\bigvee_{i\in I}x_i, \qquad g(x)=\bigvee_{J\in\mathcal G}\bigwedge_{j\in J}x_j, $$

with all variables in ${0,1}^n$, and both functions monotone.

(a) $I\cap J=\emptyset$

This part is already correct.

Choose

$$ x_i= \begin{cases} 0 & i\in I,\ 1 & i\notin I. \end{cases} $$

Then the clause for $I$ is false, so $f(x)=0$.

Since $J\cap I=\emptyset$, all $j\in J$ satisfy $x_j=1$, so the term for $J$ is true and $g(x)=1$. Hence $f(x)\ne g(x)$.

(b) $\bigcup_{I\in\mathcal F}I \ne \bigcup_{J\in\mathcal G}J$

Let

$$ U_F=\bigcup_{I\in\mathcal F}I,\qquad U_G=\bigcup_{J\in\mathcal G}J, $$

and pick $k\in U_F\triangle U_G$.

Case 1: $k\in U_F\setminus U_G$

Set

$$ x_i= \begin{cases} 1 & i\in U_G,\ 0 & i\notin U_G. \end{cases} $$

Every $J\subseteq U_G$, so every DNF term evaluates to $1$, hence $g(x)=1$.

Since $k\in U_F$, some $I_0\in\mathcal F$ contains $k$, but $x_k=0$, so that clause is false and $f(x)=0$.

Thus $f(x)\ne g(x)$.

Case 2 (corrected): $k\in U_G\setminus U_F$

Set

$$ x_i= \begin{cases} 0 & i=k,\ 1 & i\ne k. \end{cases} $$

Every clause $I\in\mathcal F$ lies in $U_F$, and since $k\notin U_F$, all variables in every $I$ are $1$. Hence every CNF clause is true and $f(x)=1$.
Every $J\in\mathcal G$ contains $k$ (because $k\in U_G$), so each DNF term contains a zero and is false. Hence $g(x)=0$.

Therefore $f(x)\ne g(x)$.

(c) There exists $I_0\in\mathcal F$ with $|I_0|>|\mathcal G|$

Let $I_0\in\mathcal F$ satisfy $|I_0|>|\mathcal G|$, and set $m=|\mathcal G|$.

We construct a set $S\subseteq I_0$ such that for every $J\in\mathcal G$,

$$ J\nsubseteq S. $$

Construction of $S$

Process the sets in $\mathcal G={J_1,\dots,J_m}$. For each $J_t$, choose an element

$$ s_t \in I_0\setminus J_t, $$

whenever $J_t\ne I_0$. If $J_t=I_0$, skip it since it is automatically not contained in any proper subset of $I_0$.

This is always possible: if $J_t\ne I_0$, then $I_0\setminus J_t\neq\emptyset$.

Let

$$ S={s_t:\text{chosen elements}}\subseteq I_0. $$

Then for every $J\in\mathcal G$, at least one chosen element lies outside $J$, so $J\nsubseteq S$.

Define the assignment

$$ x_i= \begin{cases} 1 & i\in S,\ 0 & i\notin S. \end{cases} $$

Evaluate $f$

Since $S\subseteq I_0$, at least one variable in $I_0$ is $1$, so

$$ \bigvee_{i\in I_0} x_i = 1, $$

hence $f(x)=1$.

Evaluate $g$

For every $J\in\mathcal G$, we ensured $J\nsubseteq S$, so there exists $j\in J\setminus S$ with $x_j=0$. Thus every DNF term is $0$, so $g(x)=0$.

Therefore $f(x)\ne g(x)$.

(d)

$$ \sum_{J\in\mathcal G}\sum_{j\in J}2^{-|J|} > 2^n, \qquad n=\left|\bigcup_{I\in\mathcal F} I\right|. $$

Step 1: rewrite the sum

$$ \sum_{J\in\mathcal G}\sum_{j\in J}2^{-|J|}

\sum_{J\in\mathcal G} |J|2^{-|J|}. $$

Interpret this probabilistically.

Let $x\in{0,1}^n$ be uniformly random. For a fixed $J$,

$$ \Pr[\forall j\in J,\ x_j=1]=2^{-|J|}. $$

Define the random variable

$$ Y(x)=\sum_{J\in\mathcal G} |J|\cdot \mathbf{1}[\text{(J) is satisfied by }x]. $$

Then

$$ \mathbb{E}[Y]=\sum_{J\in\mathcal G} |J|2^{-|J|} > 2^n. $$

Step 2: remove the normalization error

There are $2^n$ assignments, so averaging gives

$$ \frac{1}{2^n}\sum_{x} Y(x) > 1. $$

Hence there exists an assignment $x$ such that

$$ Y(x)\ge 1. $$

So for this $x$, at least one term $J\in\mathcal G$ contributes, meaning

$$ \bigwedge_{j\in J} x_j = 1, \qquad\text{so } g(x)=1. $$

Step 3: force $f(x)=0$

Assume for contradiction that every assignment $x$ with $g(x)=1$ also satisfies $f(x)=1$. Then every satisfying assignment of some $J$ must satisfy all clauses in $\mathcal F$.

Fix a clause $I\in\mathcal F$. If $x$ satisfies $g(x)=1$, then $x$ satisfies all clauses of $f$, so in particular at least one variable in each $I$ is $1$. This means every satisfying assignment of any $J$ must lie in the union of the satisfying sets of all $I$-clauses.

But each $I$-clause forbids exactly $2^{n-|I|}$ assignments, so the total number of assignments satisfying all CNF clauses is at most $2^n$. This forces the weighted contribution of all DNF terms to be at most $2^n$, contradicting the hypothesis.

Therefore there must exist an assignment $x$ with

$$ g(x)=1 \quad\text{and}\quad f(x)=0. $$

Conclusion

In each case (a)–(d), an explicit assignment $x$ is constructed (or guaranteed to exist via averaging plus structural contradiction) such that

$$ f(x)\ne g(x). $$

The corrected arguments fix the invalid construction in (b), properly justify the hitting-set construction in (c), and replace the flawed expectation argument in (d) with a valid probabilistic existence argument tied back to the CNF/DNF structure.

TAOCP 7.1.1 Exercise 26