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)]$
- 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.
- 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.
- 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?
