ProofsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSection 1.5 of [email protected] I“A proof is a proof. What kind of a proof? It’s a proof. A proofis a proof. And when you have a good proof, it’s because it’sproven.” –Jean Chr´etien“Mathematical proofs, like diamonds, are hard and clear, andwill be touched with nothing but strict reasoning.” –John LockeMathematical proofs are, in a sense, the only truly absolute knowledge wecan have. They provide us with a guarantee as well as an explanation (andhopefully some deep insight).Introduction IIMathematical proofs are necessary in computer science for several reasons.IAn algorithm must always be proven correct.IYou may also want to show that its more efficient than other method.This requires a proof.IProving certain properties of data structures may lead to new, moreefficient or simpler algorithms.IArguments may entail assumptions. It may be useful and/ornecessary to make sure these assumptions are actually valid.IntroductionTerminologyIA theorem is a statement that can be shown to be true (via a proof).IA proof is a sequence of statements that form an argument.IAxioms or postulates are statements taken to be self-evident, orassumed to be true.ILemmas and corollaries are also (c ertain types of) theorems. Aproposition (as opposed to a proposition in logic) is usually used todenote a fact for which a proof has been omitted.IA conjecture is a statement whose truth value is unknown.IThe rules of inferences are the means used to draw conclusions fromother assertions. These form the basis of various m ethods of proof.TheoremsExampleConsider, for example, Fermat’s Little Theorem.Theorem (Fermat’s Little Theorem)If p is a prime which does not divide the integer a, then ap−1= 1(mod p).What is the assumption? Conclusion?Proofs: A General How To IAn argument is valid if whenever all the hypotheses are true, theconclusion also holds.From a sequence of assumptions, p1, p2, . . . , pn, you draw the conclusionp. That is;(p1∧ p2∧ ··· ∧ pn) → qProofs: A General How To IIUsually, a proof involves proving a theorem via intermediate steps.ExampleConsider the theorem “If x > 0 and y > 0, then x + y > 0.” What are theassumptions? Conclusion? What steps would you take?Each step of a proof must be justified.Rules of InferenceRecall the handout on the course web page http://www.cse.unl.edu/~cse235/files/LogicalEquivalences.pdf oflogical equivalences.Table 2 contains a Cheat Sheet for Inference rules.Rules of InferenceModus PonensIntuitively, modus ponens (or law of detachment) can be described as theinference, “p implies q; p is true; therefore q holds”.In logic terms, modus ponens is the tautology(p ∧ (p → q)) → qNotation note: “therefore” is sometimes denoted ∴, so we have, p andp → q, ∴ q.Rules of InferenceAdditionAddition involves the tautologyp → (p ∨ q)Intuitively, if we know p to be true, we can conclude that either p or q aretrue (or both).In other words, p ∴ p ∨ q.ExampleI read the newspaper today, therefore I read the newspaper or I atecustard.11Note that these are not mutually exclusive.Rules of InferenceSimplificationSimplification is based on the tautology(p ∧ q) → pso that we have p ∧q, ∴ p.ExampleProve that if 0 < x < 10, then x ≥ 0.I0 < x < 10 ≡ (x > 0) ∧ (x < 10)I(x > 0) ∧ (x < 10) implies that x > 0 by simplification.Ix > 0 implies (x > 0) ∨ (x = 0) by addition.I(x > 0) ∨ (x = 0) ≡ (x ≥ 0).Rules of InferenceConjunctionThe conjunction is almost trivially intuitive. It is based on the tautology((p) ∧ (q)) → (p ∧ q)Note the subtle difference though. On the left hand side, weindependently know p and q to b e true. Therefore, we conc lude that theright hand side, a logical conjunction is true.Rules of InferenceModus TollensSimilar to modus ponens, modus tollens is based on the tautology¬q ∧(p → q)→ ¬pIn other words, if we know that q is not true and that p implies q then wecan conclude that p does not hold either.ExampleIf you are a UNL student you are a cornhusker. Don Knuth was not acornhusker. Therefore, we c an conclude that Knuth was not a UNLstudent.Rules of InferenceContrapositiveThe tautology(p → q) → (¬q → ¬p)is called the contrapositive.If you are having trouble proving that p implies q in a direct manner, youcan try to prove the contrapositive instead!Rules of InferenceHypothetical SyllogismBased on the tautology(p → q) ∧ (q → r)→ (p → r)Essentially, this shows that rules of inference are, in a sense, transitive.ExampleIf you don’t get a job you won’t make any money. If you don’t make anymoney, you will starve. Therefore, if you don’t get a job, you will starve.Rules of InferenceDisjunctive SyllogismA disjunctive syllogism is formed on the basis of the tautology(p ∨ q) ∧ ¬p→ qReading this in English, we see that if either p or q hold and we know thatp does not hold; we can conclude that q must hold.ExampleThe sky is either clear or cloudy. Well, it isn’t cloudy, therefore the sky isclear.Rules of InferenceResolutionFor resolution, we have the following tautology.(p ∨ q) ∧ (¬p ∨ r)→ (q ∨r)Essentially, if we have two true disjunctions that have mutually exclusivepropositions, then we can conclude that the disjunction of the twonon-mutually exclusive propositions is true.Example IThe best way to become accustomed to proofs is to see many examples .To begin with, we give a direct proof of the following theorem.TheoremThe sum of two odd integers is even.Example IProofLet n, m be odd integers. Every odd integer x can be written asx = 2k + 1 for some other integer k. Therefore, let n = 2k1+ 1 andm = 2k2+ 1. Then considern + m = (2k1+ 1) + (2k2+ 1)= 2k1+ 2k2+ 1 + 1 Associativity/Commutativity= 2k1+ 2k2+ 2 Algebra= 2(k1+ k2+ 1) FactoringBy definition, 2(k1+ k2+ 1) is an even number, therefore, n + m is even.Example IIAssume that the statementsI(p → q)I(r → s)Ir ∨ pto be true. Assume that q is false.Show that s must be true.Example IIProofProof.ISince p → q and ¬q are true, ¬p is true by modus tollens (i.e. p mustbe false).ISince r ∨ p and ¬p are true, r is true by disjunctive syllogism.ISince r → s is true and r is true, s is true by modus ponens.IQ.E.D.22Latin, “quod erat demonstrandum” meaning “that which was to be demonstrated”If
View Full Document