$\forall x[P(x) \vee Q(x)]$ is not $\equiv (\forall xP(x) \vee ∀xQ(x))$

519 Views Asked by At

I have a question from a discrete math text,

Determine whether $\forall x[P(x) \vee Q(x)]$ and $\forall xP(x) \to \forall xQ(x)$ have the same truth value.

Thus far using the definitions from my book $\forall x[P(x) \to Q(x)] ≡ \forall x[\neg P(x) \vee Q(x)]$.

Now I've read a theorem that, $\forall x[\neg P(x) \vee Q(x)]$ is not $\equiv (\forall xP(x) \vee ∀xQ(x))$.

However, this to me does not constitute as proof, rather assumption.

Now my question, how do you prove $\forall x[\neg P(x) \vee Q(x)]$ is not $\equiv (\forall xP(x) \vee ∀xQ(x))$

2

There are 2 best solutions below

0
On

Consider $Q(x)= \neg P(x)$

Then $\forall x (P(x) \rightarrow Q(x)) \equiv \forall x (P(x)\rightarrow\neg P(x))\equiv \forall x\neg P(x)$.

While $\left(\forall x P(x)\rightarrow \forall x Q(x) \right) \rightarrow (\forall x P(x) \rightarrow \forall x \neg P(x)) $.

The second one is clearly unsatisfiable, while the first one is not.

14
On

Consider the example where $P(x)$ is '$x$ is odd' and $Q(x)$ is '$x$ is even', where the variable $x$ ranges over the integers. This example demonstrates both that $$\forall x (P(x) \Rightarrow Q(x)) \not\equiv (\forall x P(x)) \Rightarrow (\forall x Q(x))$$ and that $$\forall x (P(x) \vee Q(x)) \not\equiv (\forall x P(x)) \vee (\forall x Q(x))$$ since in both cases the left-hand side is true but the right-hand side is false.

You should try to work out the details, but let me know in the comments if you have trouble.