TAOCP 7.2.2.2 Exercise 190
Define the Boolean function $H(x_1,x_2,x_3,x_4)$ by H(x_1,x_2,x_3,x_4)= \begin{cases} 0,&(x_1,x_2,x_3,x_4)=(0,0,0,0),\\ 1,&\text{otherwise}.
Section 7.2.2.2: Satisfiability
Exercise 190. [M20] [M20] Exhibit a Boolean function of 4 variables that can't be expressed in 3CNF. (No auxiliary variables are allowed: Only $x_1$, $x_2$, $x_3$, and $x_4$ may appear.)
Verified: yes
Solve time: 1m14s
Solution
Define the Boolean function $H(x_1,x_2,x_3,x_4)$ by
$$ H(x_1,x_2,x_3,x_4)= \begin{cases} 0,&(x_1,x_2,x_3,x_4)=(0,0,0,0),\ 1,&\text{otherwise}. \end{cases} $$
Suppose, for contradiction, that $H$ has a 3CNF representation. Thus there is a collection of clauses $C_1,\ldots,C_m$, each containing at most three literals, such that
$$ H=C_1\land C_2\land\cdots\land C_m . $$
Because
$$ H(0,0,0,0)=0, $$
at least one clause, say $C_i$, must be false when
$$ x_1=x_2=x_3=x_4=0. $$
A negative literal $\bar{x}_j$ has value $1$ under this assignment, so a clause that is false under the all-zero assignment cannot contain any negative literals. Therefore every literal of $C_i$ is among
$$ x_1,x_2,x_3,x_4. $$
The clause $C_i$ contains at most three literals, so there is some index $j$ for which $x_j$ does not occur in $C_i$. Consider the assignment
$$ x_j=1,\qquad x_r=0\quad(r\ne j). $$
Every literal occurring in $C_i$ is some $x_r$ with $r\ne j$, and all such variables have value $0$. Hence $C_i$ is false for this assignment. Since a conjunction containing a false clause is false, the assumed 3CNF representation gives
$$ H(x_1,x_2,x_3,x_4)=0 $$
for this assignment.
The assignment is not $(0,0,0,0)$, because $x_j=1$, so the definition of $H$ gives
$$ H(x_1,x_2,x_3,x_4)=1. $$
This contradiction shows that no 3CNF formula using only the variables $x_1,x_2,x_3,x_4$ can represent $H$.
Therefore the required Boolean function is
$$ H(x_1,x_2,x_3,x_4)=1 $$
for all assignments except
$$ (x_1,x_2,x_3,x_4)=(0,0,0,0), $$
where it has value $0$. Hence
$$ \boxed{H(x_1,x_2,x_3,x_4)= \begin{cases} 0,&0000,\ 1,&\text{all other assignments}. \end{cases}} $$
This completes the proof.
∎