# Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?

Suppose we have a CNF formula $$F$$ and a permutation $$\sigma$$ of its literals such that for any literal $$x, \sigma(\neg x)=\neg \sigma(x)$$ and $$F \vDash \sigma(F)$$.

Does it hold that $$F \equiv \sigma(F)$$?

It is the case when $$\sigma$$ is a syntactic or even a semantic symmetry of $$F$$ but I don't know if it hold for any permutation that respects the hypothesis above.

• Do you mean that $F \vDash \sigma(F)$ holds for all $F$ or for a single specific $F$? It'd be great if you could edit the question to clarify that. – D.W. Sep 24 '18 at 0:40
• It is for the formula $F$ given at the beginning I.e. the CNF formula that I have. – RTK Sep 24 '18 at 1:40
• if $F\vDash \sigma(F)$ held for all CNF formula $F$, then $\sigma$ would be the identity. – RTK Sep 24 '18 at 6:32

The crucial observation is that if $$A \vDash B$$ then also $$\sigma(A) \vDash \sigma(B)$$. This follows since all $$\sigma$$ does is rename variables and flip some variables. For example, if $$\sigma(x) = \lnot y$$, $$\sigma(y) = z$$, and $$\sigma(z) = x$$, then $$A(x,y,z) \vDash B(x,y,z)$$ implies also $$A(\lnot y, z, x) \vDash B(\lnot y, z, x)$$.
Let $$G$$ be the set of all permutations of literals satisfying your condition. I claim that $$G$$ forms a group with respect to composition. Since $$G$$ is finite and composition is associative, it suffices to check that it is closed under composition. Indeed, if $$\sigma(\lnot x) = \lnot \sigma(x)$$ and $$\tau(\lnot x) = \lnot \tau(x)$$ then $$\sigma(\tau(\lnot x)) = \sigma(\lnot\tau(x)) = \lnot\sigma(\tau(x))$$.
Since $$G$$ is a group, $$\sigma^{|G|}$$ is the identity. If $$F \vDash \sigma(F)$$ then, applying $$\sigma$$ on both sides, we get $$\sigma(F) \vDash \sigma^2(F)$$. More generally, we get $$\sigma^n(F) \vDash \sigma^{n+1}(F)$$, and so $$\sigma^n(F) \vDash \sigma^m(F)$$ whenever $$m \geq n$$. In particular, choosing $$n = 1$$ and $$m = |G|$$, we obtain $$\sigma(F) \vDash F$$.
The group $$G$$ is known as the signed symmetric group, denoted $$B_n$$, where $$n$$ is the number of variables.
• I don't see anything in the question that guarantees $\sigma(F) \vDash \sigma^2(F)$. – D.W. Sep 24 '18 at 14:49
• @D.W. Suppose that $\phi(x,y,z) \vDash \psi(x,y,z)$. Then also $\phi(\lnot y, z, x) \vDash \psi(\lnot y, z, x)$. This corresponds to applying $\sigma$ on both sides of $F \vDash \sigma(F)$. – Yuval Filmus Sep 24 '18 at 14:53