Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are the following expressions equivalent?

¬∃x(student(x) ∧ learn(x))
∀x(student(x) ∧ learn(x))
¬∀x(student(x) ∧ learn(x))
share|improve this question
4  
I see that ∃x(teacher(x) ∧ senseofhumor(x)). If only it were ∀x... –  anon Apr 25 '12 at 20:42
add comment

3 Answers

up vote 7 down vote accepted

Note that you have several expressions of quantified logic which all share the same predicate:

(student(x) ∧ learn(x))

We can just replace this predicate with a single combined predicate:

P(x) = (student(x) ∧ learn(x)).

Regarded this way, your question boils down to this: are these equivalent?

¬∃x P(x)
∀x P(x)
¬∀x P(x)

You can see that the P(x) is not important at all since it is a common element; you're asking whether the quantifiers themselves are equivalent.

We can look at all three possible pairs of these to show they are not.

  1. Obviously ∀ is the logical opposite of ¬∀.

  2. ¬∃ is mutually exclusive with ∀: if there does not exist even one instance, how can there exist all?

  3. Finally ¬∀ and ¬∃ are not the same either. One means "not all" and the other means "none".

In summary: "none", "all" and "not all" are different quantifiers.

Another thing

Note that all our expressions have a free variable. No, not x of course, but the function P. So what we are saying here is that for all possible instantiations of the function P, those quantifiers are not equivalent. However, we could instantiate P such that some of the expressions are equivalent.

For instance if we were to forget about student(x) ∧ learn(x) and take P(X) = (x == x). The predicate asserts that x is equal to itself. When we plug this into ∀x P(x) we now have something in which all variables are instantiated and bound, and so we can evaluate it down to a single truth value. Yes, for all X, it is true that X is equal to itself! So this statement is true. Next, ¬∀x P(x) is false since it asserts that not all X's are equal to themselves. And ¬∃x P(x) is also false since it asserts that no X is equal to itself. Since ¬∀x P(x) and ¬∃x P(x) are both false, they are equivalent (under the given instantiation of the function P, not in general for any function P!)

In logic we always have to keep in mind whether we are talking about the formulas themselves, or concrete instantiations in which symbols are substituted with concretes, or something in between: partial instantiations in which some symbols are substituted with instances, and others free.

Two formulas may not be equivalent (in the sense that we can find a combination of variables which instantiate them and yield a different truth value). But instantiations can be equivalent (yield the same truth value, or the same truth value for all remaining instantiations of variables hitherto not instantiated).

share|improve this answer
add comment

No. See Wikipedia: De_Morgan's_laws#Extensions. $$ \lnot \exists x (S(x) \land L(x)) \equiv \forall x \lnot (S(x) \land L(x)) \\ \lnot \forall x (S(x) \land L(x)) \equiv \exists x \lnot (S(x) \land L(x)) \\ $$ Also, by De Morgan's again: $$ \lnot (S(x) \land L(x)) \equiv (\lnot S(x) \lor \lnot L(x)) $$

share|improve this answer
add comment

No formalism should be required to see that they are not equivalent. In plain English, the first one says that there is nothing that is a student who learns. (I used nothing instead of no one to allow for the possibility that the domain of discourse includes things that aren’t people.) The second says that everything in the domain of discourse is a student who learns. And the third says that it’s not the case that everything in the domain of discourse is a student who learns, or in other words, there is something that is not a student who learns (either because it’s not a student, or because it doesn’t learn, or both).

In particular, the last two are clearly incompatible: one is the negation of the other, so exactly one of them can be true.

share|improve this answer
    
Careful, careful! "In plain English" might lead you astray when dealing with formal logic (although not here, of course). –  chx Apr 25 '12 at 23:48
    
@chx: True, but in elementary settings it’s a useful starting point, even if you have to go on to find a formal justification. –  Brian M. Scott Apr 26 '12 at 12:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.