2
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2018 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, 2018 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, 2018 at 6:32

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't see anything in the question that guarantees $\sigma(F) \vDash \sigma^2(F)$. $\endgroup$
    – D.W.
    Sep 24, 2018 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$ Sep 24, 2018 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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