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$
4
  • $\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
    Commented Sep 9, 2016 at 2:35
  • $\begingroup$ You are correct. Hence, "every car is either "not white" or uses diesel" is the right interpretation. $\endgroup$
    – Sarvesh Ravichandran Iyer
    Commented Sep 9, 2016 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$
    – aduh
    Commented Sep 9, 2016 at 2:36
  • $\begingroup$ @aduh I've seen that being used quite often in definitions. $\endgroup$
    – Natalie Clarius
    Commented Sep 9, 2016 at 13:44

2 Answers 2

Reset to default
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$

You must log in to answer this question.

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