ProofsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSection 1.5 of [email protected] duction 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).NotesIntro duction I IMathematical 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.NotesIntro ductionTerminologyIA 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 stateme nts taken to be self-evident, orassumed to be true.ILemmas and corollaries are also (certain 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 methods of proof.NotesTheoremsExampleConsider, 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?NotesProofs: 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) → qNotesProofs: 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.NotesRules 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.NotesRules 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.NotesRules 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.NotesRules 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).NotesRules 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 be true. Therefore, we conclude that theright hand side, a logical conjunction is true.NotesRules 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 can conclude that Knuth was not a UNLstudent.NotesRules 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!NotesRules 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.NotesRules 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.NotesRules 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.NotesExample 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.NotesExample 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.NotesExample IIAssume that the statementsI(p → q)I(r → s)Ir ∨ pto be true. Assume that q is false.Show that s must be true.NotesExample 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
View Full Document
Unlocking...