Logical equivalence of $\forall x \ P(x) \lor \forall x \ Q(x) $ and $\forall x \ \forall y \ (P(x) \lor Q(y) )$.

117 Views Asked by At

Show that $\forall x \ P(x) \lor \forall x \ Q(x) $ and $\forall x \ \forall y \ (P(x) \lor Q(y) )$ are logically equivalent.

I tried to consider three cases:

  • $\forall x \ P(x)$ is true,

  • $\forall x \ Q(x)$ is true or

  • both of them are true. (I'm stuck here and don't have any idea).

1

There are 1 best solutions below

11
On BEST ANSWER

Using the method of analytic tableaux: start with the negation of

$$((\forall xP(x)\lor\forall xQ(x)))\leftrightarrow(\forall x\forall y(P(x)\lor Q(y)))\tag{1}$$

then apply a series of contradiction-hunting rules to establish that $(1)$ is what's known as a tautology, like so:

enter image description here