TAOCP 7.2.2.2 Exercise 456

Exercise 456. [M21] $[M21]$ For how many functions $f(x_1, x_2, x_3, x_4)$ is (187) an endomorphism?

Verified: no
Solve time: 4m52s

Solution

Let $\tau$ denote the endomorphism given by (187). If $S$ is the set of satisfying assignments of $F$, the definition of endomorphism gives

$$ x\in S \implies x\tau\in S . $$

Hence $S$ is closed under $\tau$. Since there are only $2^4=16$ assignments, every sequence

$$ x,\ x\tau,\ x\tau^2,\ldots $$

eventually reaches a cycle. The cycle reached from an element of $S$ is contained in $S$, because every element along the orbit remains in $S$.

Tracing the directed graph of (187) gives the cycles

$$ (0011),\qquad (1010\ 0101\ 0110),\qquad (1000). $$

All other assignments eventually enter one of these cycles. Therefore every nonempty set of assignments closed under $\tau$ contains at least one of these three cycles.

Suppose that every cycle of $\tau$ contains an assignment satisfying a clause $C$. If $F$ is satisfiable, its solution set $S$ is a nonempty $\tau$-closed set. A cycle of $\tau$ is contained in $S$, and that cycle contains some assignment satisfying $C$. This assignment satisfies both $F$ and $C$, so $F\wedge C$ is satisfiable. The reverse implication is immediate because every solution of $F\wedge C$ is also a solution of $F$.

Thus the desired equivalence is guaranteed whenever every cycle of $\tau$ contains an assignment satisfying $C$.

This condition is also necessary. Suppose a cycle $Y$ contains no assignment satisfying $C$. A finite set of assignments can always be represented as the solution set of a CNF formula: for every assignment $z\notin Y$, include the clause consisting of the literals that are false under $z$. That clause excludes $z$ and is satisfied by every assignment in $Y$. The resulting formula has exactly the assignments in $Y$ as its solutions. Since $Y$ is closed under $\tau$, the map $\tau$ is an endomorphism of this formula. For this formula, $F$ is satisfiable but $F\wedge C$ is not. Hence a cycle without a satisfying assignment for $C$ prevents the equivalence from being guaranteed.

For part (a), consider

$$ C=124=\bar{1}2\bar{4}. $$

On the cycles of $\tau$, the clause is satisfied as follows:

$$ 0011:\bar{1}=1, $$

$$ 1010:\bar{4}=1, $$

$$ 0101:\bar{1}=1, $$

$$ 0110:\bar{1}=1, $$

$$ 1000:\bar{4}=1. $$

Every cycle contains assignments satisfying $C$, so the equivalence is guaranteed.

$$ \boxed{\text{(a) Yes}} $$

For part (b),

$$ C=234=x_2\vee x_3\vee x_4. $$

The cycle $(0011)$ contains assignments satisfying $C$ because $x_4=1$. The cycle $(1010\ 0101\ 0110)$ contains assignments satisfying $C$ because the three assignments have respectively

$$ x_3=1,\qquad x_2=1,\qquad x_2=1. $$

The cycle $(1000)$ has

$$ x_2=x_3=x_4=0, $$

so no assignment in that cycle satisfies $C$. By the necessity argument, this cycle supplies a counterexample.

$$ \boxed{\text{(b) No}} $$

For part (c),

$$ C=123=x_1\vee x_2\vee x_3. $$

The assignments on the cycles satisfy $C$ because

$$ 0011:x_3=1, $$

$$ 1010:x_1=1, $$

$$ 0101:x_2=1, $$

$$ 0110:x_2=1, $$

$$ 1000:x_1=1. $$

Every cycle contains a satisfying assignment for $C$, so the equivalence is guaranteed.

$$ \boxed{\text{(c) Yes}} $$

For part (d),

$$ C=34=x_3\vee x_4. $$

The cycle assignments satisfy $C$ except for the cycle $(1000)$:

$$ 0011:x_4=1, $$

$$ 1010:x_3=1, $$

$$ 0101:x_4=1, $$

$$ 0110:x_3=1, $$

while

$$ 1000:x_3=x_4=0. $$

The cycle $(1000)$ contains no assignment satisfying $C$, so the equivalence is not guaranteed.

$$ \boxed{\text{(d) No}} $$

This completes the proof.

∎