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 1 6.042J/18.062J, Fall ’05: Mathematics for Computer Science September 7 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised September 1, 2005, 856 minutes Proofs 1 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 and plausibility. The best example is “Cogito ergo sum,” a Latin sentence that translates as “I think, 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 pretty cool and persuasive-sounding first axiom. However, with just a few more lines of proof in this vein, Descartes goes on to conclude that there is an infinitely beneficent God. This ain’t Math. Mathematics also has a specific notion of “proof.” Definition. A formal proof of a proposition is a chain of logical deductions leading to the proposition from 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 organizing proofs. Copyright © 2005, Prof. Albert R. Meyer.��2 Course Notes, Week 1: Proofs 2 Propositions Definition. 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 thou Romeo?” and “Give me an A!”. But not all propositions are mathematical. For example, “Albert’s wife’s name is ‘Irene’ ” happens to be true, and could be proved with legal documents and testimony of their children, but it’s not a mathematical statement. Mathematically meaningful propositions must be about well-defined mathematical objects like numbers, 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 about numbers 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 between phrases. A prime is a natural number greater than one that is not divisible by any other natural number other 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) = 461 which is prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through n = 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 expression is not prime for all n, the proposition is false! In fact, it’s not hard to show that no nonconstant polynomial can map all natural numbers into prime numbers. The point is that in general you can’t check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set. Here are two even more extreme examples: Proposition 2.3. a4 +b4 +c4 = d4 has no solution when a, b, c, d are positive integers. In logical notation, letting Z+ denote the positive integers, we have 4∀a ∈ Z+∀b ∈ Z+∀c ∈ Z+∀d ∈ Z+ . a 4 + b4 + c = d4 . Strings of ∀’s like this are usually abbreviated for easier reading: 4∀a, b, c, d ∈ Z+ . a 4 + b4 + c = d4 . Euler (pronounced “oiler”) conjectured this 1769. But the proposition was proven false 218 years later 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 3 Proposition 2.4. 313(x3 + y3) = z3 has 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 adjacent1 regions have different colors. This proposition is true and is known as the “four-color theorem”. However, there have been many incorrect proofs, including one that stood for 10 years in the late 19th century before the mistake was found. An extremely laborious proof was finally found in 1976 by mathematicians Appel 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 hand by Haken and his assistants—including his 15-year-old daughter. There was a lot of debate about whether this was a legitimate proof: the argument was too big to be checked without a computer, and no one could guarantee that the computer calculated correctly, nor did anyone have 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 (see
View Full Document
Unlocking...