prenex normal form quantifiers predicates

192 Views Asked by At

Are these if and only if equalities always true ?

1 - $\exists x \exists y \;(P(x) \;and \;Q(y))\Leftrightarrow \exists x P(x) \; and \;\exists y \;Q(y)$

2- $\exists x \exists y \;(P(x) \;or \;Q(y))\Leftrightarrow \exists x P(x) \; or \;\exists y \;Q(y)$

3- $\forall x \forall y \; (P(x) \;or \;Q(y)) \Leftrightarrow \forall x P(x) \;or\; \forall y Q(y) $

4- $\forall x \forall y \; (P(x) \;and \;Q(y)) \Leftrightarrow \forall x P(x) \;and\; \forall y Q(y) $

1

There are 1 best solutions below

5
On

They all hold. (1): If $P(x_0)$ and $Q(y_0)$ are both true, then certainly $P(x_0)$ and $Q(y_0)$ is. Similarly, if either of those holds, then $P(x_0)$ or $Q(y_0)$ is true.

For the universally quantified sentences, the same argument gets the right-to-left implications. For the left-to-right in 3, suppose I had $x_0, y_0$ so $P(x_0)$ and $Q(y_0)$ were both false. Then the left-hand side would fail as well. So, by the contrapositive, if I get the left-hand side I get at least one disjunct on the right. Think you can extend the argument to (4) now?