# Does “$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$” hold given that $\sigma(F)\equiv F$ for a CNF formula $F$ built on a set $L$ of literals?

Suppose we have a CNF formula $$F$$ built on the set of literals $$L=\{x_1,\neg x_1,\cdots,x_n,\neg x_n\}$$ where each variable is used in at least one clause of $$F$$. Consider a permutation $$\sigma$$ of $$L$$ such that $$\sigma(F)$$ is logically equivalent to $$F$$ i.e. $$\sigma(F)\equiv F$$.

Does it hold that $$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$$ ?

I tried to find a counter example without success.

No. Suppose $$F$$ is the formula
$$(x_1 \lor x_2) \land (\neg x_1 \lor x_2) \land (x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_2) \land (x_1 \lor \neg x_1) \land (x_2 \lor \neg x_2),$$
and consider the permutation $$\sigma$$ such that $$\sigma(x_1)=x_2$$, $$\sigma(x_2)=\neg x_1$$, $$\sigma(\neg x_1)=x_1$$, and $$\sigma(\neg x_2)=\neg x_2$$.
Then $$\sigma(F) \equiv F$$, but $$\sigma(\neg x_1) \ne \neg \sigma(x_1)$$.
• @RTK, I don't know. As a starting point, I suggest writing a program to exhaustively search all possible CNF formulas on two variables $x_1,x_2$ and all possible permutations and seeing what you find. There are only $2^{16} \times 4!$ combinations, so that should be easily feasible on a computer. – D.W. Apr 7 '19 at 2:53