How are $ \exists x (P(x) ⊕ Q(x)) $ and $(\exists x P(x)) ⊕ (\exists x Q(x))$ not logically equivalent?

1.3k Views Asked by At

I want to know how these two statements are not logically equivalent. From what I have done I am getting them as logically equivalent. I have started as letting $P(x) = x$ is even and $Q(y) = y$ is odd.

For your convience if you want to copy the question $\exists x(P(x) ⊕ Q(x))$ and (\exists x P(x)) ⊕ (\exist x Q(x))$

⊕ = exclusive or

2

There are 2 best solutions below

3
On BEST ANSWER

The number 4 is even and not odd. Therefore $P(4) \oplus Q(4)$ is true. Therefore $\exists x(P(x) \oplus Q(x))$ is true, as witnessed by $x=4$.

$\exists x P(x)$ is true, as witnessed by $x=4$. $\exists x Q(x)$ is true, as witnessed by $x=3$. Since both are true, $(\exists x P(x)) \oplus (\exists x Q(x))$ is false.

Since one statement is true and the other is false, they are not logically equivalent.

0
On

How are ∃x(P(x) ⊕ Q(x)) and (∃xP(x)) ⊕ (∃xQ(x)) not logically equivalent?

The first states that there exists something for which either P or Q holds but not both.

The second states there either exists something for which P holds, or there exists something for which Q holds, but both do not exist.


By way of counter example, let's talk about integers. Let P(x) be the statement that an integer is odd. Let Q(x) be the statement that an integer is even.

There exists at least one integer which is either odd or even but not both at once. That is all of them, in fact. So ∃x(P(x) ⊕ Q(x)) holds.

It isn't so that you can either find an odd integer, or an even integer, but you cannot find an example of both. So (∃xP(x)) ⊕ (∃xQ(x)) does not hold.

Hence the statements cannot be equivalent.