0
$\begingroup$
  • Consider the following predicate formulas.

    $F1: \forall x \exists y ( P(x) \to Q(y) ).$

    $F2: \exists x \forall y ( P(x) \to Q(y) ).$

    $F3: \forall x P(x) \to \exists y Q(y).$

    $F4: \exists x P(x) \to \forall y Q(y).$

    Answer the following questions with brief justification.

    (a) Does $F1$ logically imply $F2$?

    (b) Does $F1$ logically imply $F3$?

    (c) Does $F1$ logically imply $F4$?

    (d) Does $F2$ logically imply $F1$?

    (e) Does $F2$ logically imply $F3$?

    (f) Does $F2$ logically imply $F4$?

    (g) Does $F3$ logically imply $F1$?

    (h) Does $F3$ logically imply $F2$?

    (i) Does $F3$ logically imply $F4$?

    (j) Does $F4$ logically imply $F1$?

    (k) Does $F4$ logically imply $F2$?

    (l) Does $F4$ logically imply $F3$?


Logically implies really confuses me. Attempt:

Writing it in English first:

F1: We have that $x$ never satisfies $P$ or there is a $y$ that satisfies $Q$

F2: For some $x$ $P$ isn't satisfied, or $y$ always satisfies $Q$

F3: Some $x$ doesn't satisfy $P$ or some $y$ satisfies $Q$

F4: $x$ never satisfies $P$ or $y$ always satisfies Q

By definition of logically implies: A formula $F$ logically implies a formula $F'$ iff every interpretation that satisfies $F$ satisfies $F'$

So:

(a) So for $F1$ $x$ never satisfies $P$ meaning it'll always be true whereas some $x$ can satisfy P in $F2$, thus this doesn't logically imply.

(b) ... yeah I don't know how to explain any of this - any assistance even tips are appreciated I'm stumped

Apparently $b$ is true I don't get it though.

according to $F1$, $x$ never satisfies $P$ and by prepositional logic of $p \to q$ is not p or q.

then $F1$ is always true whereas $F3$ there can exist a P that satisfies Q and some y that doesn't satisfy Q so every interpretation doesn't satisfy? I'm understanding this poorly.

$\endgroup$
0
$\begingroup$

$F_1$ says for all $x$, there exists a y such that $P(x)$ implies $Q(y)$.

$F_2$ says for there exists a $x$, for all $y$ such that $P(x)$ implies $Q(y)$.

$F_3$ says that for all $x$, if $P(x)$ holds, then there exists a $y$ such that $Q(y)$.

$F_4$ says that there exists a $x$, such that if $P(x)$, then for all $y$, $Q(y)$ holds.

The first one means that for all values of $x$, there exists some value of y such that the $P(x)$ implies $Q(y)$.

The second one says that there exists a common $x$ for all $y$ such that $P(x)$ implies $Q(y)$.

Both of them aren't the same, which is what you have pointed out too and you can solve the rest of them in the same way.

Also, a good way would be to some concrete example and see if it holds or not. It makes the intuition a bit easier.

EDIT: If you want more help with logical implications, there's a book called How To Prove It by Daniel Velleman whose first two chapters deal with logic, which is a good read.

$\endgroup$

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.