My textbook gave the following

$ \forall x_0 (\exists x_1 \ x_0=(\mathbf{O''} \cdot x_1) \vee \exists x_1 \ x_0=((\mathbf{O''} \cdot x_1)+\mathbf{O'})) $,

then commented on the syntax and why the brackets are so important here, etc...

However, for this example, I gave

$ \forall x_0 \ \exists x_1 (\ x_0=(\mathbf{O''} \cdot x_1) \vee x_0=(\mathbf{O''} \cdot x_1)+\mathbf{O'}) $.

To me these are equivalent, but my text didn't mention this form and didn't necessarily suggest it's equivalent to the first.

So are they equivalent or the way I'm using $ \ \exists x_1 $ gives my formula a different meaning?



In other words, can the existential quantifier be "factored" like I did?


The claim that either there is some object that is $P$ or there is some object that is $Q$, $\exists x_1 P(x_1) \lor \exists x_1 Q(x_1)$, is logically equivalent to the claim that there is some object that is either $P$ or $Q$, $\exists x_1 (P(x_1) \lor Q(x_1))$:

$\exists x_1 P(x_1) \lor \exists x_1 Q(x_1) \iff \exists x_1 (P(x_1) \lor Q(x_1))$.

Notice the same is not true for existential quantification with conjunction. For example, there exists a cat and there exists a dog, $\exists x \text{Cat}(x) \land \exists x \text{Dog}(x)$, but this does not exactly mean there exists something which is both a cat and a dog, $\exists x (\text{Cat}(x) \land \text{Dog}(x))$.

enter image description here

As a caveat to the preceding image, it would be true to say that all objects are both a cat and a dog, $\forall x (\text{Cat}(x) \land \text{Dog}(x))$, if and only if all objects are a cat and all objects are a dog, $\forall x \text{Cat}(x) \land \forall x \text{Dog}(x).$

  • 1
    $\begingroup$ One fine day with a woof and a purr $\endgroup$ – Git Gud Aug 8 '18 at 8:37

The existential quantifier distributes over disjunction. So the two sentences are indeed logically equivalent.

  • 1
    $\begingroup$ Great article, thanks. $\endgroup$ – Stephen Aug 7 '18 at 21:01

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.