Cheap and Secure Web Hosting Provider : See Now

Counterexample for equality in Quantified Boolean Formula

, , No Comments
Problem Detail: 

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.

Asked By : Albert Hendriks
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback