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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2016 at 12:50
  • $\begingroup$ Fixed. But I believe you could have fixed it yourself. Try to be more resourceful. $\endgroup$
    – Yuval Filmus
    Mar 24, 2016 at 12:51

Your Answer

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

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