Wednesday, July 22, 2009

Wednesday Math, Vol. 80: Implication

Logic has been considered a part of philosophy for several thousand years. In the mid 1800's, a group of English mathematicians took it upon themselves to turn logic into a part of the mathematical field, foremost among them being George Boole, Augustus DeMorgan and Charles Dodgson, known better by his pen name Lewis Carroll. In mathematical logic, the variables like P and Q stand in for statements like "The moon is made of green cheese." or "It's Tuesday." or "The door is open." A statement can either be true (T) or false (F). There are modern extensions of logic where statements can be somewhere between true and false, and this field is called fuzzy logic. Regular logic is tricky enough, so let's stick to that for the time being.

Once we have statements, logic starts dealing with compound statements. The simplest logical operators are AND (denoted with a ^) and OR (denoted with a v). The compound statement "P AND Q" is only true is both P and Q are true, while "P OR Q" is true unless both P is false and Q is false.

Then there's implication, stated either as "P IMPLIES Q" or "IF P, THEN Q". Implication has been a very important concept in logic ever since the Greeks started talking about Socrates being a man and all men being mortal, but it's a little trickier than AND or OR.

The first statement in an implication is the premise. If the premise of an implication is false, the entire implication is considered to be true, the only way for an implication to be false is for the premise to be true while the conclusion is false.

This is an odd idea, but let's think of it in terms of a law like the legal age to buy alcohol. We can think of the law as "Buying alcohol IMPLIES you are 21 years or older." There are four possible situations, three of them legal and one illegal.

You buy alcohol AND you are 21 years or older (legal.)
You buy alcohol AND you are NOT 21 years or older (illegal.)
You do NOT buy alcohol AND you are 21 years or older (legal.)
You do NOT buy alcohol AND you are NOT 21 years or older (legal.)

If you don't buy alcohol, the premise of the implication is false and the entire implication is true. There is no way to break this law if you never buy alcohol. The only illegal situation is for the premise to be true, in this case, buying alcohol, and the conclusion to be false, being less than 21 years old.

While this can be explained to most people's satisfaction relatively easily, implication can make logic something of a hornet's nest. One of the important concepts in logic is the tautology, a compound statement that is always true. The simplest tautology is "P OR NOT P", which is to say, either the moon is made of green cheese or the moon is not made of green cheese. It has to be one way or the other, so we can't go wrong with this statement, it's always true. The next simplest tautology is reverse implication, "P IMPLIES Q OR Q IMPLIES P". Because implication works the same as "NOT P OR Q", reverse implication can be translated at "P OR NOT P OR Q OR NOT Q", and it's always true.

But it doesn't sound always true.

It's raining implies it's Tuesday or it's Tuesday implies it's raining.

I'm a man implies I'm a woman or I'm a woman implies I'm a man.

Those last two statements are 100% true, regardless of what day it is or if it's raining or not or in the second case, the gender of the speaker. They work because if one of the statements is false, it is the premise in an implication which must be true, and with an OR statement, one true part is enough. The other possibility is that both statements are true, and then the reverse implication is fine as well.

We are lead to believe that logic is the way the mind is supposed to work if operating properly. I teach my students that logic is a game with rules, and you have to learn the rules, even if sometimes it creates always true statements that don't sound like they make sense.


dguzman said...

This kind of logic talk makes my brain tired. I like your point, that logic is a game with rules; otherwise, it's too overwhelming to think about.

Matty Boy said...

Hi, dg. I just want you to know that I appreciate your comments on Wednesday Math posts, though I know they aren't your favorites.

47th Problem of Euclid said...

At UNC, I used to take the bus with a logic PhD student. He used to constantly remind me that the kind of logic that mathematicians use is hopelessly obsolete by logician standards: using the Law of the Excluded Middle, that contemporary logic has rejected along with bivalent truth schemes. The problem is that proofs fall apart without the Law of the Excluded Middle (try proving that $\sqrt{2}$ is irrational without it).

Matty Boy said...

I wasn't aware of the modern version of logic. I remember in my undergraduate career having people talk about doing math without the Axiom of Choice. Lots of proofs crumble to the ground without that one as well.