8
$\begingroup$

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?

Thanks


Edit

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

$\endgroup$

2 Answers 2

13
$\begingroup$

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).$

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

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .