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)$.

  • $\begingroup$ Yeh, I did not think of formulas with tautological clauses. Does it still hold when the given formula is not allowed to contain tautological clauses? $\endgroup$ – RTK Apr 6 '19 at 23:48
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Apr 7 '19 at 2: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.