2
$\begingroup$

I was wondering how one would negate an existential quantifier over a logical conjunction. As an example, suppose that I have the statement: "There exists a car that is white and doesn't use diesel".

I am recognizing this as saying: $\exists x \in C: \ (P(x) \land Q(x))$, where $C$ is the set of all cars, and $P$ is the statement that "a car is white" while $Q$ is the statement "doesn't use diesel".

My question is if the statement can be represented using these quantifiers, and if so, what the negation would be. Would the negation be:

$$ \neg \exists x \in C: \ (P(x) \land Q(x)) \implies \forall x \in C \ : \ \neg P(x) \lor \neg Q(x) $$

?

In other words, the negation is: "All cars are either not white or use diesel"? Thanks.

$\endgroup$
  • $\begingroup$ Yes, that is correct. I discussed it in my answer to your other question Please do not ask the same question three times before you have digested the answers to the first. $\endgroup$ – Ross Millikan Sep 9 '16 at 2:35
  • $\begingroup$ You are correct. Hence, "every car is either "not white" or uses diesel" is the right interpretation. $\endgroup$ – астон вілла олоф мэллбэрг Sep 9 '16 at 2:35
  • $\begingroup$ This is right, except the symbol $\in$ is usually not used in sentences of first-order logic. Just write, for example, $\exists x (Px \wedge Qx)$. If you want to specify that $x$ is a car, then write $\exists x (Cx \wedge Px \wedge Qx)$ $\endgroup$ – grndl Sep 9 '16 at 2:36
  • $\begingroup$ @aduh I've seen that being used quite often in definitions. $\endgroup$ – lemontree Sep 9 '16 at 13:44
1
$\begingroup$

More briefly and idiomatically, the negation is:

All white cars use diesel.

That's because $(\neg A \lor B) \equiv (A\to B)$.

$\endgroup$
1
$\begingroup$

Yes, this is correct.

Negating the statement corresponds to negation of the whole formula (i.e. putting the negation in front of the existential quantifier).

Saying "It is not true that there exists a car which is white and doesn't use diesel" translates as

$\neg \exists x \in C : (P(x) \land Q(x))$

which is, by law of quantifier negation, equivalent to

$\forall x \in C : \neg (P(x) \land Q(x))$

and can again, by one of DeMorgan's laws, be transformed to to

$\forall x \in C : \neg (P(x) \lor \neg Q(x))$

Statements of the form $\neg \exists x P(x)$ can always be rewritten as $\forall x \neg P(x)$, i.e. "There is no thing to which the property applies" is equivalent to "To all things the property does not apply".

$\endgroup$

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.