Rewriting statements with quantifiers to full detail

1,466

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

Share:
1,466
Zak
Author by

Zak

Updated on August 01, 2022

Comments

  • Zak
    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?