What are proofs? (informal) The following submission from an anonymous engineer to the January, 1902 edition of Popular Mechanics caught my eye. Seems like something every Boy/Girl Scout and Architect should know. “HOW TO USE THE WATCH AS A COMPASS: Very few people are aware of the fact that in a watch they are always provided with a compass, with which, when the sun is shining, the cardinal points can be determined. All one has to do is to point the hour hand to the sun and south is exactly half way between the hour and the figure 12 on the watch. This may seem strange to the average reader, but it is easily explained. While the sun is passing over 180 degrees (east to west) the hour hand of the watch passes over 360 degrees (from 6 o'clock to 6 o'clock). Therefore the angular movement of the sun in one hour corresponds to the angular movement of the hour hand in half an hour; hence, if we point the hour hand toward the sun the line from the point midway between the hour hand and 12 o'clock to the pivot of the hands will point to the south. — Engineer.” They give an argument of correctness; is that really a proof? Well, there are some ambiguities: Do I hold the watch vertically, or, in the plane of the sun's arc? Certainly I can't hold it up-side down, even though this isn't explicitly stated. Furthermore, the correctness of the reasoning relies on some unstated assumptions. E.g., the sun is at its highest (northernmost) point of its transit at noon. Is this actually true? Does it depend on the time of year? I'm not exactly sure (and will have to sit down and scratch my head and draw pictures of orbits, to convince myself). Certainly there are at least a couple of caveats: even beyond account for Daylight Savings Time, the solar-time and clock-time only align at time-zone boundaries, and they drift up to an hour apart, before the next boundary rectifies the difference. Is this presuming I'm in the northern hemisphere? What if I'm on the equator? To be fair, the intent of this anecdote was to give enough evidence to convince you, not necessarily to be a complete, stand-alone self-contained proof. But in writing out a careful proof, one is forced to consider all the points just made; being forced to understand these can lead you to better understand the procedure yourself. But be careful to distinguish between something which sounds reasonable, and something that you're certain of.

An argument by form How can we tell true proofs from false ones? What, exactly, are the rules of a proof? These are the questions which will occupy us. Proofs are argument by form. We'll illustrate this with three parallel examples of a particular proof form called syllogism. 1All people are mortal.Premise 2Socrates is a person.Premise 3Therefore, Socrates is mortal.Syllogism, lines 1,2

1All [substitution ciphers] are [vulnerable to brute-force attacks].Premise 2The [Julius Caesar cipher] is a [substitution cipher].Premise 3Therefore, the [Julius Caesar cipher] is [vulnerable to brute-force attacks].Syllogism, lines 1,2

Note that you don't need to know anything about cryptography to know that the conclusion follows from the two premises. (Are the premises indeed true? That's a different question.) 1All griznoxes chorble happily.Premise 2A floober is a type of griznox.Premise 3Therefore, floobers chorble happily.Syllogism, lines 1,2

You don't need to be a world-class floober expert to evaluate this argument, either. Lewis Carroll, a logician, has developed many whimsical examples of syllogisms and simple reasoning. (Relatedly, note how the social context of Carroll's examples demonstrates some feminist issues in teaching logic.) As you've noticed, the form of the argument is the same in all these. If you are assured that the first two premises are true, then, without any true understanding, you (or a computer) can automatically come up with the conclusion. A syllogism is one example of a inference rule — that is, a rule form that a computer can use to deduce new facts from known ones.

Some non-proofs Of course, not all arguments are valid proofs. Identifying invalid proofs is just as interesting as identifying valid ones.


Homer: Ah, not a bear in sight.  The Bear Patrol must be working.
Lisa:  That's specious reasoning, Dad.
Homer: Thank you, honey.
Lisa:  By your logic, this rock keeps tigers away.
Homer: Oh?  How does it work?
Lisa:  It doesn't work.
Homer: Uh-huh.
Lisa:  It's just a stupid rock.
Homer: Uh-huh.
Lisa:  But I don't see any tigers around here, do you?
  [pause]
Homer: Lisa, I want to buy your rock!
  [A moment's hesitation … and money changes hands.]

(From The Simpsons Much Apu About Nothing.) If Lisa isn't around, who will identify specious reasoning for us? We can certainly use her approach of finding other particular examples that follow the same argument, yet lead to a clearly erroneous conclusion. Suppose that my friend makes the following argument: 1Warm cola tastes bad.Premise 2Warm salt-water tastes bad.Premise 3Therefore, mixing them together tastes bad. “Common-sense conclusion”, lines 1,2

I'm skeptical, so I have a sip; sure enough, the conclusion is indeed true. But is the proof correct — does the “common-sense conclusion” rule actually hold? In order to refute the form of the argument, we can try similar arguments which have the same form but a false conclusion (as Lisa did). 1Ice-cold coke tastes good.Premise 2Ice coffee tastes good.Premise 3Therefore, mixing them together tastes good. “Common-sense conclusion”, lines 1 and 2.

After another unfortunate sip, I verify that this conclusion is not true, and therefore my friend's reasoning is at fault. My friend responds by claiming that the “common-sense conclusion” is too valid; the rule is that bad-taste is preserved upon mixing, not that any taste is preserved. While I'm inclined to believe that, we realize we can still test this more refined rule: can you come up with an instance of mixing together bad-tasting things and ever getting a yummy result? (Say, salt and flour, which can be mixed and baked to get delicious saltines! The argument continues, about whether the form of the argument precludes baking, and so on.) The end result (after I take some antacid) is that we have a clearer understanding of the initially vague “common-sense conclusion”, and stricter rules about when it applies. Thus, refining the argument has led us to a greater understanding. The above examples are a bit frivolous, but the procedure of looking for counterexamples applies to many real-world dilemmas. It also highlights the difference between a correct proof, and a faulty proof that might still happen to lead to a true result. (By the way, this is the exact same skill used when trying to come up with an algorithm for a problem: “well, the algorithm works for this input, but can I find a something that makes one of the steps fail?” If so, you then try refining your algorithm “well, I can add a test to take care of that problem; is that enough so that it always works?”) Solve this statement for [X]: It is wrong to ban [X]. Such a ban would punish those reasonable citizens who would use [X] responsibly, while those who really want to abuse [X] will be able to get it anyway, through a black market which will only subsidize other criminal activities. This argument is or has been commonly used for varying topics — marijuana, alcohol, all drugs, handguns, birth control, prostitution, encryption technology. The interesting part, is that the traditional Left and Right political positions each use this argument for some of these items, while rejecting the argument when used for other items. A more rational response is to either accept all the above, or none of the above, or to realize that the stated argument wasn't everything — that there might be implicit assumptions or arguments which actually do distinguish between these cases (the different interpretations of “[X]”). Being able to articulate the differences is essential. The more refined arguments may be more nuanced, and less able to fit into a sound-bite, but lead to a better understanding of one's own values. And sometimes, upon reflection, one may realize that some of the implicit values or premises are things they actually disagree with, once they are precisely spelled out. In real-world issues, there are often many subtleties, and short arguments that sound airtight might be glossing over factors which are important in practice. During daylight, there is no need to have headlights (or running lights) on: there's already plenty of light for everybody to see each other by. Even during the day, headlights slightly increase how quickly other drivers see you during (say) a routine, tenth-of-a-second glance in their mirror. When in a turn-only lane, there is absolutely no need to signal — since there's only one way to turn, a signal can't communicating any information to other drivers! Glib, but not true: Other defensive drivers presumably know you have only one legal option, but they don't know that you know that, and they are planning reactions in case you surprise them with a sudden illegal maneuver. By signaling, you give them information which helps them better plan for yet other contingencies. Furthermore, it also gives you more confidence that other drivers are expecting your turn, reducing your suspicion that they're about to pull a surprise maneuver on you. (True, these are all low-probability events which almost always turn out to be unnecessary. But avoiding accidents is all about minimizing risks for the one moment events do spiral out of control.) “You'll lose weight if and only if you burn more calories than you take in. All those diet-plan books can never get around this, and all their details are pointless.” True, calorie intake and expenditure solely determine weight loss/gain. But after some thought, we can get examples where the above logic overlooks some relevant differences: If your friend told you they were switching from a diet of 2000 calories of balanced short-term and long-term energy sources (sugars, proteins, and carbs) to a diet of 2000 calories worth of Pixy Stix at breakfast plus a Flintstones multivitamin, would you be optimistic that they would have the willpower to strictly follow the new plan? The two plans are equal when counting calories, but in actuality one really is a better plan. (Even more exaggeratedly, consider a daily plan of 2000 calories of sugar while never drinking any water—since water has no calories, it can't affect your calorie count, according to the above claim.) These contrived counterexamples help illustrate that it's conceivable that there can be a difference between diet plans, so the initial claim isn't technically true. The point illustrated is that often real-world arguments incorrectly imply that their result follows from the form of the argument, when in fact the form is not valid in the way a syllogism is. This fallacy can be illuminated by finding a different domain in which the argument fails. The practice of searching for domains which invalidate the argument can help both sides of a debate hone in on bringing the unspoken assumptions to light. The original argument, if its conclusion is indeed true, must be patched either by adding the unspoken assumptions or fixing the invalid form. Mistakes in syllogisms are hard to make: what are the only two ways to have an error in a syllogism? The argument isn't actually in syllogism form. For example, the following is an incorrect syllogism: 1All people don't know my file's password. Premise (Equivalent to “Nobody knows my file's password”, but reworded to be of the required form “All somethings have some property.”.) 2All hackers are people. Premise 3Therefore, my file is secure from hackers. Incorrect syllogism, lines 1,2

To be a syllogism, the conclusion would have to be “all hackers don't know my file's password.” The file might or might not be secure, but the above doesn't prove it. One of the two premises is wrong. 1All people don't know my file's password. Premise, but possibly false 2All hackers are people. Premise, but possibly false 3Therefore, all hackers don't know my file's password. Syllogism, lines 1,2

This proof fails, of course, if some hackers are non-people (e.g., programs), or if some people know the password. (In fact, presumably you know the password!) Of course, even if a proof fails, the conclusion might be true for other reasons. An incorrect argument doesn't prove the conclusion's opposite!

Other Inference Rules Of course, there are more ways to deduce things, beyond a syllogism. Who decides what the valid inference rules are? Is it always clear when people have used the inference rules correctly?

Glimpses of two different WaterWorld boards Consider the following argument about WaterWorld boards: 1(A) is next to exactly onepirate. Premise, from either subfigure 2(A) has only one unexplored neighbor. Premise, from either subfigure 3If you are an unexpected location next to (A), then you contain apirate. Incorrect conclusion

This conclusion is not valid; while it is correct for the first board shown, it is incorrect for the second. (I make this mistake all the time when playing WaterWorld too quickly, arrggh! — The Author.) The problem is that the author of the argument presumably meant to conclude “all explored neighbors of (A) contain a pirate”. Before we can study exact proofs, we need a way of writing exactly what we mean. This will occupy us for the next section.

The need for a precise language These previous glitches in the WaterWorld arguments both arise, of course, because we were sloppy about what each sentence meant exactly. We used informal English — a fine language for humans, who can cope with remarkable amounts of ambiguity -- but not a good language for specifying arguments. Laws and contracts are really written in a separate language from English — legalese — full of technical terms with specific meanings. This is done because, while some ambiguity is tolerable in 99% of human interaction, the remaining 1% can be very problematic. Even so, legalese still contains intentionally ambiguous terms: When, exactly, is a punishment “cruel and unusual”? What exactly is the “community standard” of indecency? The legal system tries to simultaneously be formal about laws, yet also be flexible to allow for unforeseen situations and situation-specific latitude. (The result of this tension is the position of Judge.) Court decisions, while dense reading, are often the model of well-presented arguments. Consider, from a previous example, the statement “…[this is something] every Boy/Girl Scout and Architect should know”. Does this mean all people who are both a scout and architect, or everybody who is at least one or the other? Genuinely ambiguous, in English! (Often, “and/or” is used to mean “one or the other or possibly both”.) We'll next look at a way to specify some concepts non-ambiguously, at least for WaterWorld. We need to be more careful about how we state our facts and how we use these known facts to deduce other facts. Remember, faulty reasoning might not just mean losing a silly game. Hardware and software bugs can lead to significant bodily harm (Imagine software bugs in an airplane autopilot or surgical robot system), security loopholes (e.g., in Mozilla or IE), or expensive recalls. One reaction to the above arguments is “Well, big deal — somebody made a mistake (mis-interpreting or mis-stating a claim); that's their problem. (And sheesh, they sure are dolts!)” But as a programmer, that's not true: Writing large systems, human programmers will err, no matter how smart or careful or skilled they are. Type-checkers catch some errors upon compilation, and test suites catch their share of bugs, but many still remain in real-world software. Thus we are looking for systemic ways to reduce and catch errors, with the ultimate ideal of being able to prove programs correct. Other professions have checklists, protocols, and regulations to minimize human error; programming is no different, except that the industry is still working on exactly what the checklists or training should be. Someday, a license will be required for practicing software, at least for software involved with life-safety. In our study of formal logic, we'll need three things: Syntax (language) — a precise syntax and vocabulary for expressing concepts without ambiguity, Propositional logic, First-order logic (propositional logic, plus relations and quantifiers) Semantics (meaning) and modeling — how to connect these formal languages to whatever topic we want to reason about (including our software). Reasoning (proofs) — methods of deducing new facts from old. We'll see three types of reasoning, and how to use them for each of our two logics: Truth tables Boolean Algebra Inference Rules We'll visit these topics in an interleaved manner — first propositional logic (immediately with its semantics) and three methods of reasoning for it; then first-order logic and an in-depth look at its interpretations, and finally the methods of reasoning for first-order logic. We'll begin with a particular syntax — propositional logic for the game of WaterWorld — before using this syntax to formally deduce safe moves.