Negations, Contrapositives, and Happiness

One of the first skills I teach students in CS103 is how to take the negations of different classes of statements, such as universally-quantified statements, existentially-quantified statements, vacuous truths, and implications. The goal is to help students get comfortable with proofs by contradiction and contrapositive as early as possible.

I accidentally stumbled on this little exercise, which is very effective at forcing students to pause and see how all these concepts interact:

What is the contrapositive of the statement “if someone is happy, then everyone is happy?”

  1. If everyone is happy, then someone is happy.
  2. If someone is not happy, then everyone is not happy.
  3. If everyone is not happy, then someone is not happy.
  4. If everyone is happy, then someone is not happy.
  5. If someone is not happy, then everyone is happy.

What is the negation of the statement “if someone is happy, then everyone is happy?

  1. If someone is not happy, then everyone is not happy.
  2. If someone is happy, then someone is not happy.
  3. Someone is happy and everyone is not happy.
  4. Someone is happy and someone is not happy.
  5. Someone is not happy and everyone is not happy.

If you haven’t practiced taking contrapositives and negating formulas recently, it’s worth taking a minute to answer these question for yourself before moving on. (The answers are scattered throughout the rest of this post)

These problems tend to really throw students when they’re getting started and they’re excellent at launching helpful conversations. There are a number of reasons why.

First, the statement at the core of these questions – “if someone is happy, then everyone is happy” – is hard to wrap your head around in a mathematical sense. A plain English reading of this statement leads most people to conclude that it’s totally false. The fact that one person is happy doesn’t cause other people to be happy. But if you interpret this statement in a mathematical sense – as in something given by the first-order logic statement (\exists x. Happy(x)) \to (\forall x. Happy(x)) – then the meaning is totally different. That implication is a material conditional, and the truth or falsity of the statement depends on the world in which you evaluate it. So for most students, learning to work with this statement at all involves first recognizing that they’re not dealing with implications or conditionals in the familiar sense of the term.

The second challenge with answering these questions is that they require students to have a fairly good understanding of how to negate universally-quantified statements, existentially-quantified statements, and implications. This is an area I’ve found students to be perennially perplexed by when they’re getting started. Let’s take the contrapositive, for example. Most students can recall independently that

  • the negation of a statement of the form \forall x. P(x) is \exists x. \lnot P(x),
  • the negation of a statement of the form \exists x. P(x) is \forall x. \lnot P(x), and
  • the contrapositive of the implication A \to B is \lnot B \to \lnot A,

but they don’t realize how to assemble them together. The majority of students I’ve had will correctly realize that they need to negate the antecedent and consequent and swap their roles, but don’t recognize that negating the statements “someone  is happy” and “everyone is happy” involves negating universally-quantified and existentially-quantified statements.

Then there’s the fact that the correct answer, in some sense, looks wrong. If you negate the antecedent and consequent and swap their order, you get back (in first-order logic) the statement (\exists x. \lnot Happy(x)) \to (\forall x. \lnot Happy(x)), which renders in English as “if someone is not happy, then everyone is not happy.” Many students going through a process-of-elimination through the answers will rule this one out because it initially looks like the antecedent and consequent were negated but not swapped.

And finally, there’s a big question that comes up about why, if this really is the contrapositive, it means the same thing as the original statement. Why do the statements “if someone is happy, then everyone is happy” and “if someone is not happy, then everyone is not happy” mean the same thing?

The best way I know to answer that question is to move on to the next part and think about the negation of the statement. Seeing when this statement isn’t true sheds a lot of light on when it is true.

Again, negating this statement gives students a lot of trouble. Most students get this one wrong by choosing the option “if someone is happy, then someone is not happy,” or, in first-order logic, (\exists x. Happy(x)) \to (\exists x. \lnot Happy(x)). The issue here is that the negation of an implication of the form A \to B is A \land \lnot B, rather than A \to \lnot B. The correct answer is “someone is happy and someone is sad.”

So why is that statement the negation of the original one (or its contrapositive)? I like asking students to mull this one over. If you think about it, if you’re in a room where there’s a happy person and a sad person, then the claim “if someone is happy, then everyone is happy” is false, since the sad person disproves it, and the claim “if someone is not happy, then everyone is not happy” is also false because of the happy person. (Most students don’t find that part too hard to get). On the other hand, imagine that you have a room where everyone is happy or everyone is sad. If everyone is happy, then the statement “if someone is happy, then everyone is happy” is trivially true (“trivially” in the sense of “it’s an implication with a true consequent” rather than “obviously,”), and the statement “if someone is not happy, then everyone is not happy” is vacuously true. There’s a similar argument to be made for the case where everyone is sad.

Because this simple statement touches on so many topics – what implications mean, how to take a contrapositive, how to negate universally-quantified and existentially-quantified statements, negating implications, and vacuous truths – I’ve found that it’s an excellent conversation starter. If I see someone struggling with first-order logic, I’ll often ask this question and have them work through it.

So there you have it – a tiny little implication that leads to a ton of interesting edge cases on the boundaries of logic and language. I doubt I’m the first person to have stumbled on this one, and I hope that it finds a use somewhere outside of CS103!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s