5
$\begingroup$

Sometimes, but not always, quantifiers distribute over logical operations. Determine which of the following pairs of statements are equivalent. In the case of nonequivalent pairs, give an example of propositional functions $P(x)$ and $Q(x)$ for which the paired statements are not equivalent.

This is what I wrote.

a. $(\forall x)[P(x) \land Q(x)]$ and $(\forall x)P(x) \land (\forall x)Q(x)$

Left: There exists all values of $x$ for $P(x)$ and $Q(x)$.

Right: There exists all values of $x$ for $P(x)$ and there exists all values of $x$ for $Q(x)$

Example: Let $P(x)$ = positive numbers and $Q(x)$ = $x^2 \geq 0$

All values of $x$ are positive numbers and satisfy $x^2 \geq 0$.

All values of $x$ are positive numbers and all values of $x$ satisfy $x^2 \geq 0$.

These statements are equivalent.

b. $[\exists x][P(x) \land Q(x)]$ and $(\exists x)P(x) \land (\exists x)Q(x)$

Left: There exists some values of $x$ for $P(x)$ and $Q(x)$.

Right: There exists some values of $x$ for $P(x)$ and there exists some values of $x$ for $Q(x)$.

Example: Let $P(x)$ = negative numbers and $Q(x)$ = $x^2+8x+12=0$.

Some values of $x$ are negative numbers and satisfies $x^2+8x+12=0$.

Some values of $x$ are negative numbers and some values of $x$ satisfy $x^2+8x+12=0$

These statements are equivalent.

c. $(\forall x)[P(x) \lor Q(x)]$ and $(\forall x)P(x) \lor (\forall x)Q(x)$

Left: There exists all values of $x$ for $P(x)$ or $Q(x)$.

Right: There exists all values of $x$ for $P(x)$ or there exists all values of $x$ for $Q(x)$.

Example: Let $P(x)$ = positive numbers and $Q(x)$ = negative numbers.

All values of $x$ are positive numbers or negative numbers.

All values of $x$ are positive numbers or all values of $x$ are negative numbers.

These statements are equivalent.

Edit: I could partly see why this problem isn't equivalent.

$(\forall x)[P(x) \lor Q(x)]$ and $(\forall x)P(x) \lor (\forall x)Q(x)$

The first part would be for all $x$ $P(x) \lor Q(x)$ and the second part would be for all $x$ in $P(x)$ or for all $x$ in $Q(x).

All x values need to be valid for $P(x)$ or $Q(x)$. It seems that I'm choosing $P(x)$ or $ Q(x)$ but everything for x needs to hold. This might work for the second part, but not for the first. So, maybe I could give this as an example.

$P(x) = x^2 \geq 0$ and $Q(x) = x \le 0$? All $x$ is positive in $P(x)$ or all $x$ is negative in $Q(x)$, but this can't work for $(\forall x)[P(x) \lor Q(x)]$ It's like saying that all $x$ will be satisfied in $P(x)$ or $Q(x)$ but positive numbers don't work for $x \le 0$ and negative numbers don't work for $x^2 \geq 0$

d. $[\exists x][P(x) \lor Q(x)$ and $[\exists x][P(x) \lor [\exists x][Q(x)].$

Left: There exists some values of $x$ for $P(x)$ or $Q(x)$.

Right: There exists for some values of $x$ for $P(x)$ or there exists some values of $x$ for $Q(x)$.

Example: Let $P(x)$ = positive numbers and $Q(x)$ = $x^2-6x+8=0$

There are some values of $x$ that are positive numbers or satisfy $x^2-6x+8=0$

There are some values of $x$ that are positive numbers or there are some values of $x$ that satisfy $x^2-6x+8=0$

These statements are equivalent.

e. $(\forall x)[P(x) \rightarrow Q(x)]$ and $(\forall x)P(x) \rightarrow (\forall x)Q(x)$

Left: If all values of $x$ satisfy $P(x)$, then it must satisfy $Q(x)$.

Right: If all values of $x$ satisfy $P(x)$, then all values of $x$ must satisfy $Q(x)$.

Example: If $x = 2$ satisfies $P(x)$, then $x = 2$ must satisfy $Q(x)$

These statements are equivalent.

Edit: for e.. (∀x)[P(x)→Q(x)] and (∀x)P(x)→(∀x)Q(x) The first part means if P then Q for all x. The second part means If for all x in P, then for all x in Q. This is not equivalent. The second part throws everything off Maybe the example should be that if I wake up early everyday, then I go to school. P(x) = wake up early everyday and Q(x) = go to school the second part would be that I have to wake up early all the time and go to school all the time. I don't go to school on weekends. In fact, it's closed on Sunday. would that be right?

to revise it a bit... I could put that if I wake up early every weekday, then I go to school for (∀x)[P(x)→Q(x)]...the second part would mean that if I wake up early every weekday, then I go to school every weekday. Sometimes there are holidays, there is Spring Break, or I could be sick.

f. $(\forall x)[P(x) \leftrightarrow Q(x)]$ and $(\forall x)P(x) \leftrightarrow (\forall x)Q(x)$

Left: All values of $x$ are satisfied if and only if $P(x)$ lies within $Q(x)$.

Right: If all values of $x$ satisfies $P(x)$, then all values of $x$ satisfies $Q(x)$ Conversely, if all values of $x$ satisfies $Q(x)$, then all values of $x$ satisfies $P(x)$.

Edit:

For, $(\forall x)[P(x) \leftrightarrow Q(x)]$

  1. For all x, there is $P(x)$ if and only if there is $Q(x)$

We need to construct a truth table. If Q is P, then it's a tautology. Also, if P is Q, then it's a tautology.

For, $(\forall x)P(x) \leftrightarrow (\forall x)Q(x)$

Let $P(x)$ = divisible by 4 $Q(x)$ = divisible by 8.

  1. If every x is in $P(x)$, then every x is in $Q(x)$. If every x is divisible by 4, then every x is divisible by 8.

This is only true for some x. For example, let $x = 24$. If 24 is divisible by 4, then the result is 6. Also, if 24 is divisible by 8, then the result is 3.

If we let $x = 36$, it would be divisible by 4, but not 8.

  1. If every x is in $Q(x)$, then every x is in $P(x)$.

If every x is divisible by 8, then every x is divisible by 4.

This condition only works for certain values of x.

Let $ x = 48$. If 48 is divisible by 8, then the result is 6. If 48 is divisible by 4, then the result is 12.

If we let $ x = 28$, it's divisible by 4, but not divisible by 8.

As a result, these statements are not equivalent.

This isn't right. I know I could translate them, but giving examples is obviously not a decent way to do a proof for this type of problem. What did I do wrong? How do I really prove that these pairs are equivalent? Do I have to use the rules from the quantifiers?

$\endgroup$
  • $\begingroup$ You can prove that two statements are not equivalent by giving one example where one statement is true and the other is false. But to show that statements are equivalent you need a general argument. Depending on the level of the course, your instructor may be looking for an informal explanation or a more detailed proof. $\endgroup$ – David Jan 30 '14 at 3:58
  • $\begingroup$ Also may I suggest that you need to be much more careful with your language. "There exists all values of $x$ for $P(x)$ and $Q(x)$" is very confusing because "there exists" and "for all" are different quantifiers. Better to say, "for all $x$ the statement $P(x)\wedge Q(x)$ is true" and take it from there. $\endgroup$ – David Jan 30 '14 at 3:59
  • $\begingroup$ ahhh... suppose that I want to make a detailed proof or maybe an explanation or whatever is easier... where do I begin? Sorry about the wordiness. I'm new to this. $\endgroup$ – usukidoll Jan 30 '14 at 4:04
  • $\begingroup$ OH! So for the $\exists x$ I should put for some x the statement.... $P(x) \land Q(x)$ is true and the other side would be for some x, the statement would be for some x $P(x)$ and for some x $Q(x)$ is true $\endgroup$ – usukidoll Jan 30 '14 at 4:09
  • $\begingroup$ Example: In b), we do not have equivalence. Example $P(x)$ says $x-1=0$ and $Q(x)$ says $x-2=0$. Then $\exists x(P(x)\land Q(x))$ is false, but $\exists xP(x)\land \exists xQ(x)$ is true. Or (more fun) $P(x)$ could say $x$ is a camel, and $Q(x)$ could say $x$ is a toad. $\endgroup$ – André Nicolas Jan 30 '14 at 4:12
2
$\begingroup$

Here is a start for (a), then you can try the rest again and see whether you are still happy with your previous answers.

So, first part of (a): if you know that $\forall x\ [P(x)\wedge Q(x)]$ is true, can you be certain that $[\forall x\ P(x)]\wedge[\forall x\ Q(x)]$ is true? I have inserted extra brackets to make the meaning absolutely clear.

Well, if the first statement is true, then for every $x$, the statement $P(x)\wedge Q(x)$ is true. But then $P(x)$ must be true, never mind $Q(x)$, and since this is the case for all $x$, the statement $\forall x\ P(x)$ is true. For a similar reason, $\forall x\ Q(x)$ is true. Therefore $[\forall x\ P(x)]\wedge[\forall x\ Q(x)]$ is true.

Second part of (a): if you know that $[\forall x\ P(x)]\wedge[\forall x\ Q(x)]$ is true, can you be certain that $\forall x\ [P(x)\wedge Q(x)]$ is true?

Well, assume $[\forall x\ P(x)]\wedge[\forall x\ Q(x)]$ is true. Then both the statements $\forall x\ P(x)$ and $\forall x\ Q(x)$ are true. So for any $x$ we see that $P(x)$ is true and $Q(x)$ is true, so $P(x)\wedge Q(x)$ is true. Since this is the case for all $x$, the statement $\forall x\ [P(x)\wedge Q(x)]$ is true.

So the two statements are equivalent.

$\endgroup$
2
$\begingroup$

Here is another way to do part a), in contrast to David's method:


LEMMA $0$

$\forall x [P(x) \wedge Q(x)]$

...law of specialization...

$\implies \forall x [P(x)]$

LEMMA $1$

$\forall x [P(x) \wedge Q(x)]$

...law of specialization...

$\implies \forall x [Q(x)]$

LEMMA $2$

$ \top$

...idempotency of $\wedge$...

$= \top \wedge \top$

...instantiation LEMMA $0$ and LEMMA $1$...

$= (\forall x [P(x) \wedge Q(x)] \implies \forall x [P(x)]) \wedge (\forall x [P(x) \wedge Q(x)] \implies \forall x [Q(x)])$

...factoring law for $\implies$...

$= \forall x [P(x) \wedge Q(x)] \implies (\forall x [P(x)] \wedge \forall x [Q(x)])$


LEMMA $3$

$\forall x [P(x)] \wedge \forall x [Q(x)]$

...identity law for $\wedge$...

$= \forall x [P(x) \wedge \top] \wedge \forall x [Q(x)]$

...context law: assume right conjunct...

$= \forall x [P(x) \wedge \forall x [Q(x)]] \wedge \forall x [Q(x)]$

...law of specialization...

$\implies \forall x [P(x) \wedge Q(x)] \wedge \forall x [Q(x)]$

...law of specialization...

$\implies \forall x [P(x) \wedge Q(x)]$

...by law of transitivity for \implies...

$\forall x [P(x)] \wedge \forall x [Q(x)] \implies \forall x [P(x) \wedge Q(x)]$


THEOREM $0$

$ \top$

...idempotency of $\wedge$...

$= \top \wedge \top$

...instantiation of LEMMA $2$ and LEMMA $3$...

$=(\forall x [P(x) \wedge Q(x)] \implies (\forall x [P(x)] \wedge \forall x [Q(x)])) \wedge (\forall x [P(x)] \wedge \forall x [Q(x)] \implies \forall x [P(x) \wedge Q(x)])$

...law of double implication...

$=\forall x [P(x) \wedge Q(x)] = (\forall x [P(x)] \wedge \forall x [Q(x)]))$


Therefore, by THEOREM $1$:

$\top = (\forall x [P(x) \wedge Q(x)] = (\forall x [P(x)] \wedge \forall x [Q(x)]))$

$Q.E.D.$


Thus, you can easily prove for equivalency, and also easily learn how to create a counter example if two quantified statements are not equivalent. I leave it to you to approach the other parts of the question in a similar manner, if you like this method.

$\endgroup$
  • $\begingroup$ I haven't learned this method :S $\endgroup$ – usukidoll Jan 30 '14 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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