Rewriting statements with quantifiers to full detail
I'm not sure where you think you are confused. Each time, you have replaced the quantified variables ($x$ and $y$), with the appropriate logical connectives for the predicate for the set of possible values and getting the correct answer.
Or do you not understand how you got your own answers?
- (a) $\forall x \forall y\, \big(P(x) ∨ Q(y)\big)$
To make sure you understand the steps, we split the task up. Do the innermost bound variable first, simplify, then do the outermost bound variable.
$\forall x \forall y\, \big(P(x) ∨ Q(y)\big) \\\equiv \forall x \big((P(x)\vee Q(a))\wedge(P(x)\vee Q(b))\big) \\\equiv \forall x \big(P(x)\vee \big(Q(a)\wedge Q(b)\big)\Big) \\\equiv \Big(P(a)\vee \big(Q(a)\wedge Q(b)\big)\Big)\wedge \Big(P(b)\vee \big(Q(a)\wedge Q(b)\big)\Big) \\\equiv \big(P(a)\wedge P(b)\big)\vee \big(Q(a)\wedge Q(b)\big) $
Which is what you've gotten.
- (b) $\exists x\, P(x) ∧ \exists x\,Q(x)$
Again, to be sure split the task; do each bound variable one at a time
$\exists x\, P(x) ∧ \exists x\,Q(x) \\\equiv \big(P(a)\vee P(b)\big) \wedge \exists x\, Q(x) \\\equiv \big(P(a)\vee P(b)\big) \wedge \big(Q(a)\vee Q(b)\big)$
Which is almost what you had gotten. Which is what you have (after your edit).
Zak
Updated on August 01, 2022Comments
-
Zak over 1 year
The question i have for an assignment is the following
Let P and Q be predicates on the set S, where S has two elements, say, S = {a, b}. Then the statement ∀xP(x) can also be written in full detail as P(a) ∧ P(b). Rewrite each of the statements below in a similar fashion, using P, Q, and logical operators, but without using quantifiers.
- (a) $\forall x \forall y\, \big(P(x) ∨ Q(y)\big)$
- (b) $\exists x\, P(x) ∧ ∃x\,Q(x)$
- (c) $\exists x\, \exists y\,\big(P(x) ∧ Q(y)\big)$
- (d) $\forall x\,\exists y\,(P(x) ∧ Q(y))$
What throws me off entirely is the x and y, what i would write for a and b:
- (a) $\big(P(a) ∧ P(b)\big) ∨ \big(Q(a) ∧ Q(b)\big)$
- (b) $\big(P(a) ∨ P(b)\big) ∧ \big(Q(a) ∨ Q(b)\big)$
however i know theres something wrong because x and y affect it.... how would i go about this properly?