What is a Proof?PropositionsThe Axiomatic MethodOur AxiomsProofs in PracticeProving an ImplicationMethod #1Method #2 - Prove the ContrapositiveProving an ``If and Only If''Method #1: Prove Each Statement Implies the OtherMethod #2: Construct a Chain of IffsHow to Write Good ProofsPropositional FormulasCombining Propositions``Not'', ``And'' and ``Or''``Implies''``If and Only If''Propositional Logic in Computer ProgramsA Cryptic NotationLogically Equivalent ImplicationsLogical DeductionsMassachusetts Institute of Technology Course Notes, Week 16.042J/18.062J, Fall ’05: Mathematics for Computer Science September 7Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised September 1, 2005, 856 minutesProofs1 What is a Proof?A proof is a method of ascertaining truth. But what constitutes a proof differs among fields.• Legal truth is ascertained by a jury based on allowable evidence presented at trial.• Authoritative truth is ascertained by a trusted person or organization.• Scientific truth is hypothesized, and the hypothesis is confirmed or refuted by experiments.• Probable truth is obtained from statistical analysis of sample data. For example, public opin-ion is ascertained by polling a small random sample of people.• Philosophical proof involves careful exposition and persuasion based on consistency andplausibility. The best example is “Cogito ergo sum,” a Latin sentence that translates as “Ithink, therefore I am.” It comes from the beginning of a 17th century essay by the Mathe-matician/Philospher, Ren´e Descartes, and it is one of the most famous quotes in the world:do a web search on the phrase and you will be flooded with hits.Deducing your existence from the fact that you’re thinking about your existence is a prettycool and persuasive-sounding first axiom. However, with just a few more lines of proof inthis vein, Descartes goes on to conclude that there is an infinitely beneficent God. This ain’tMath.Mathematics also has a specific notion of “proof.”Definition. A formal proof of a proposition is a chain of logical deductions leading to the propositionfrom a base set of axioms.The three key ideas in this definition are highlighted: proposition, logical deduction, and axiom.In the next sections, we’ll discuss these three ideas along with some basic ways of organizingproofs.Copyright © 2005, Prof. Albert R. Meyer. All rights reserved.2 Course Notes, Week 1: Proofs2 PropositionsDefinition. A proposition is a statement that is either true or false.This definition sounds very general, but it does exclude sentences such as, “Wherefore art thouRomeo?” and “Give me an A!”.But not all propositions are mathematical. For example, “Albert’s wife’s name is ‘Irene’ ” happensto be true, and could be proved with legal documents and testimony of their children, but it’s nota mathematical statement.Mathematically meaningful propositions must be about well-defined mathematical objects likenumbers, sets, functions, relations, etc., and they must be stated using mathematically meaning-ful terminology, like ‘AND’ and ‘FORALL’. It’s best to illustrate this with a few examples aboutnumbers and planar maps that are all mathematically meaningful.Proposition 2.1. 2 + 3 = 5.This proposition is true.Proposition 2.2. Let p(n) ::= n2+ n + 41.∀n ∈ N. p(n) is a prime number.The symbol ∀ is read “for all”. The symbol N stands for the set of natural numbers, which are 0,1, 2, 3, . . . (ask your TA for the complete list). The period after the N is just a separator betweenphrases.A prime is a natural number greater than one that is not divisible by any other natural numberother than 1 and itself, for example, 2, 3, 5, 7, 11, . . . .Let’s try some numerical experimentation to check this proposition: p(0) = 41 which is prime.p(1) = 43 which is prime. p(2) = 47 which is prime. p(3) = 53 which is prime. . . . p(20) = 461which is prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking throughn = 39 and confirm that p(39) = 1601 is prime.But if n = 40, then p(n) = 402+ 40 + 41 = 41 · 41, which is not prime. Since the expressionis not prime for all n, the proposition is false! In fact, it’s not hard to show that no nonconstantpolynomial can map all natural numbers into prime numbers. The point is that in general youcan’t check a claim about an infinite set by checking a finite set of its elements, no matter howlarge the finite set. Here are two even more extreme examples:Proposition 2.3. a4+b4+c4= d4has no solution when a, b, c, d are positive integers. In logical notation,letting Z+denote the positive integers, we have∀a ∈ Z+∀b ∈ Z+∀c ∈ Z+∀d ∈ Z+. a4+ b4+ c46= d4.Strings of ∀’s like this are usually abbreviated for easier reading:∀a, b, c, d ∈ Z+. a4+ b4+ c46= d4.Euler (pronounced “oiler”) conjectured this 1769. But the proposition was proven false 218 yearslater by Noam Elkies at a liberal arts school up Mass Ave. He found the solution a = 95800, b =217519, c = 414560, d = 422481.Course Notes, Week 1: Proofs 3Proposition 2.4. 313(x3+ y3) = z3has no solution when x, y, z ∈ N.This proposition is also false, but the smallest counterexample has more than 1000 digits!Proposition 2.5. Every map can be colored with 4 colors so that adjacent1regions have different colors.This proposition is true and is known as the “four-color theorem”. However, there have beenmany incorrect proofs, including one that stood for 10 years in the late 19th century before themistake was found. An extremely laborious proof was finally found in 1976 by mathematiciansAppel and Haken who used a complex computer program to categorize the four-colorable maps;the program left a couple of thousand maps uncategorized, and these were checked by handby Haken and his assistants—including his 15-year-old daughter. There was a lot of debateabout whether this was a legitimate proof: the argument was too big to be checked without acomputer, and no one could guarantee that the computer calculated correctly, nor did anyonehave the energy to recheck the four-colorings of thousands of maps that was done by hand. Fi-nally, about five years ago, a humanly intelligible proof of the four color theorem was found (seehttp://www.math.gatech.edu/ thomas/FC/fourcolor.html).2Proposition 2.6 (Goldbach). Every even integer greater than 2 is the sum of two primes.No one knows whether this proposition is true or false. This is the
View Full Document
Unlocking...