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.

  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 24 '18 at 0:40
  • $\begingroup$ It is for the formula $F$ given at the beginning I.e. the CNF formula that I have. $\endgroup$ – RTK Sep 24 '18 at 1:40
  • $\begingroup$ if $F\vDash \sigma(F)$ held for all CNF formula $F$, then $\sigma$ would be the identity. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ I don't see anything in the question that guarantees $\sigma(F) \vDash \sigma^2(F)$. $\endgroup$ – D.W. Sep 24 '18 at 14:49
  • $\begingroup$ @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)$. $\endgroup$ – Yuval Filmus Sep 24 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.