0

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))$

Hamed
  • 6,793
javaderek
  • 37

2 Answers2

2

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.

YoTengoUnLCD
  • 13,384
0

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.

Clive Newstead
  • 64,925
  • Thanks for the comment, i'm confused from where P(x) is 'x is odd' and Q(x) is 'x is even', where the variable x ranges over the integers. How can ∀x(P(x)⇒Q(x)) exist as a consideration? – javaderek Oct 22 '15 at 03:29
  • 1
    I'm not sure what you mean... $\forall x(P(x) \Rightarrow Q(x))$ means "for all integers $x$, if $x$ is odd then $x$ is even", which is a false statement. – Clive Newstead Oct 22 '15 at 03:31
  • That's what I mean, isn't that the the example demonstration you posted? – javaderek Oct 22 '15 at 03:33
  • 1
    Right, but $(\forall xP(x)) \Rightarrow (\forall xQ(x))$ is true, which demonstrates that the two are not equivalent. – Clive Newstead Oct 22 '15 at 03:39
  • I think I see the confusion in my understanding; this (∀xP(x))⇒(∀xQ(x)) seen as true. – javaderek Oct 22 '15 at 03:45
  • I'm not sure how to describe (∀xP(x))⇒(∀xQ(x)) in words. If all integers are odd, then all integers are even? – javaderek Oct 22 '15 at 03:49
  • How can (∀xP(x))⇒(∀xQ(x)) exist as a consideration then? – javaderek Oct 22 '15 at 03:56
  • I see by rules of nonsense? If nonsense then nonsense is always true? – javaderek Oct 22 '15 at 04:14
  • By general rules of implication, if p then q, p is false, and q is false, then the implication is true. – javaderek Oct 22 '15 at 04:19
  • However, if I were state an axiom of consideration, ∀x(P(x)⇒Q(x)) cannot exist as a consideration, also (∀xP(x))⇒(∀xQ(x)) cannot exist as a consideration, therefore they are equivalent in that sense? – javaderek Oct 22 '15 at 04:22
  • "If im not correct, then im not true". "If im wrong, then im not right". hmm – javaderek Oct 22 '15 at 04:27
  • This is just a expression of nonsense, as I could simply say, "If im not correct, then im right" Then when or what is I'm. – javaderek Oct 22 '15 at 04:30
  • If I'm not god then im not a human? – javaderek Oct 22 '15 at 04:48
  • Thus according to our prescription to the "rules of implication", ∀x(P(x)⇒Q(x))≢(∀xP(x))⇒(∀xQ(x)), however their consideration does not exist. – javaderek Oct 22 '15 at 05:11