Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top