1
$\begingroup$

I'm looking for a counterexample for the following (false) equality. It should exist.

$n$ is an odd integer.

$f(x_1, x_2 .. x_n)$ is a boolean expression in 3 CNF form with boolean variables x.

$A = \exists x_1 \forall x_2 \exists x_3 \forall x_4 ... \forall x_{n-1} \exists x_n: f(x_1..x_n)$

Note that the exists and forall are alternating and that the expression begins and ends with exist.

$B = \forall x_2 \forall x_4 \forall x_6 .. \forall x_{n-1} \exists x_1 \exists x_3 .. \exists x_n : f(x_1..x_n)$

Somehow I have a flawed proof that implies $A=B$. I'm looking for a simple counterexample, a 3 CNF formula with few variables, so I can find the flaw in my proof.

$\endgroup$
2
$\begingroup$

The equality is correct for $n=1$, so let's take $n = 3$. Let $f(x_1,x_2,x_3) = [x_1 \neq x_2]$. Statement $B$ states that for every $x_2$ there exists $x_1 \neq x_2$, which is correct. Statement $A$ states that there exists $x_1$ which is different from all $x_2$, which is incorrect.

$\endgroup$
  • $\begingroup$ The domain should really be boolean, not integer. edit: By the way, let me check if this works for the "Integer" range {0,1}. Perhaps it works :) $\endgroup$ – Albert Hendriks Mar 24 '16 at 12:50
  • $\begingroup$ Fixed. But I believe you could have fixed it yourself. Try to be more resourceful. $\endgroup$ – Yuval Filmus Mar 24 '16 at 12:51

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.