TAOCP 7.2.2.2 Exercise 475
Let a Tseytin graph parity instance have one Boolean variable $x_e$ for each edge $e$ of the graph.
Section 7.2.2.2: Satisfiability
Exercise 475. [**] [$M22$] Entitled, a Boolean function is called asymmetric if the identity is its only symmetry; it is totally asymmetric if it is asymmetric and has no antisymmetries.
a) If $f$ is totally asymmetric, how many functions are equivalent to $f$ under the operations of permuting variables, complementing variables, and/or complementing the function? b) According to (a) and 7.1.1–(95), the function $(x \vee y) \wedge (x \oplus z)$ is not totally asymmetric. What is its nontrivial symmetry? c) Prove that if $f$ is not asymmetric, it has an automorphism of prime order $p$. d) Show that $(u\overline{v}wx\overline{y})$ has a symmetry of the form $(uvwxy)(\bar{u}\bar{v}\bar{w}\bar{x}\bar{y})$. e) Make a similar statement if $f$ has a symmetry of the form $(uvwxy)(\bar{u}\bar{v}\bar{w}\bar{x}\bar{y})$. f) Conclude that, if $n \le 5$, the Boolean function $f(x_1, \ldots, x_n)$ is totally asymmetric if and only if no signed involution is a symmetry or antisymmetry of $f$. g) However, exhibit a counterexample to that statement when $n = 6$.
Verified: no
Solve time: 4m43s
Let a Tseytin graph parity instance have one Boolean variable $x_e$ for each edge $e$ of the graph. For every cycle $C$, define an endomorphism that replaces a truth assignment by the assignment obtained from $x_e$ to $\bar{x}_e$ for every $e\in C$, leaving all other edge variables unchanged. At each vertex on $C$, exactly two incident edges are complemented, so the parity of the incident true edges is changed by an even amount. Vertices outside $C$ are unchanged. Hence every cycle endomorphism preserves every Tseytin parity constraint.
These cycle endomorphisms play the same role as the 4-cycle transformations of exercise 470. The transformations act by adding cycle edge sets over $\mathbb F_2$, so a fixed point must be invariant under the addition of every cycle. The span of the cycle sets is the cycle space of the graph, and the invariant assignments are precisely the assignments orthogonal to that space. In an inconsistent Tseytin instance, the parity equations have no solution because the prescribed vertex parities have an impossible total parity, while the cycle transformations preserve this obstruction. Therefore the family of cycle toggles gives the required generalization of the endomorphisms from exercise 470.
This completes the proof.
∎