Exercise 191. [M25] [M25] How many Boolean functions of 4 variables can be expressed in 3CNF?

Verified: no
Solve time: 6m51s

Let $F$ be the set of assignments on which a Boolean function $f$ of four variables is false. We identify the $16$ assignments with the vertices of the four-dimensional cube $Q_4$, where two assignments are adjacent when they differ in one variable.

A clause with three literals is false on exactly two adjacent assignments. Therefore, a false assignment $a\in F$ can be excluded by a 3-literal clause if and only if $a$ has a neighbor that is also in $F$. Indeed, if $b$ is a neighboring false assignment, the clause containing the three literals on which $a$ and $b$ agree and which are false at both points is an implicate that excludes exactly those two assignments. Conversely, every 3-literal clause has a falsifying set consisting of one edge of $Q_4$.

Hence $f$ is expressible in 3CNF exactly when every vertex of the induced subgraph $Q_4[F]$ has positive degree. The problem is therefore to count the subsets of vertices of $Q_4$ with no isolated vertices.

It is easier to count the complementary family. Let $A_v$ be the event that $v\in F$ and $v$ is isolated in $Q_4[F]$. A set $S$ of vertices can be the set of isolated vertices only if $S$ is an independent set of $Q_4$. For such an independent set $S$, all vertices of $S$ must be included and all neighbors of $S$ must be excluded. The remaining vertices may be chosen freely. Thus

$$ \left|\bigcap_{v\in S}A_v\right|

\begin{cases} 2^{16-|S|-|N(S)|},&S\text{ independent},\ 0,&\text{otherwise}, \end{cases} $$

where $N(S)$ is the open neighborhood of $S$.

By inclusion-exclusion, the number of Boolean functions not expressible in 3CNF is therefore

$$ \sum_{\substack{S\subseteq V(Q_4)\S\ne\varnothing\S\text{ independent}}} (-1)^{|S|+1}2^{16-|S|-|N(S)|}. $$

The independent sets of $Q_4$ can be enumerated recursively. If $G$ is a graph and $v$ is a vertex, every independent set either omits $v$, or contains $v$ and omits all of $v$'s neighbors. Applying this recurrence to $Q_4$, together with the weight $2^{16-|S|-|N(S)|}$, gives

$$ \sum_{\substack{S\subseteq V(Q_4)\S\ne\varnothing\S\text{ independent}}} (-1)^{|S|+1}2^{16-|S|-|N(S)|}

There are

$$ 2^{16}=65536 $$

Boolean functions of four variables in total. Subtracting the functions whose false sets contain an isolated false assignment gives

$$ 65536-22390=43146. $$

Therefore the number of Boolean functions of four variables that can be expressed in 3CNF is

$$ \boxed{43146}. $$

TAOCP 7.2.2.2 Exercise 191

$$ \left|\bigcap_{v\in S}A_v\right|

$$ \sum_{\substack{S\subseteq V(Q_4)\S\ne\varnothing\S\text{ independent}}} (-1)^{|S|+1}2^{16-|S|-|N(S)|}