IntroductionHow ToRules of InferenceExamplesFallaciesProofs With QuantifiersTypes of ProofsProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsProofsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSection 1.5 of [email protected] / 82ProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsIntroduction I“A proof is a proof. What kind of a proof? It’s a proof. Aproof is a proof. And when you have a good proof, it’sbecause it’s proven.” –Jean Chr´etien“Mathematical proofs, like diamonds, are hard and clear, andwill be touched with nothing but s trict re asoning.” –JohnLockeMathematical proofs are, in a sense, the only truly absolute knowledgewe can have. They provide us with a guarantee as well as anexplanation (and hopefully some deep insight).2 / 82ProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsIntroduction IIMathematical proofs are necessary in computer science for severalreasons.An algorithm must always be proven correct.You may also want t o show that its more efficient than othermethod. This requires a proof.Proving certain properties of data structures may lead to new,more efficient or simpler algorithms.Arguments may entail assumptions. It may be useful and/ornecessary to m ake sure these assumptions are actually valid.3 / 82ProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsIntroductionTerminologyA theorem is a stateme nt that can be shown to be true (via aproof).A proof is a sequence of statements that form an argument.Axioms or postulates are statements taken to be self-evident, orassumed to be true.Lemmas and corollaries are also (certain types of) theorems. Aproposition (as opposed to a proposition in logic) is usually usedto denote a fact for which a proof has been omitted.A conjecture is a statement whose truth value is unknown.The rules of inferences are the me ans used to draw conclusionsfrom other assertions. These form the basis of various methods ofproof.4 / 82ProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsTheoremsExampleConsider, for example, Fermat’s Little Theorem.Theorem (Fermat’s Little Theorem)If p is a prime which does not divide the integer a, thenap−1= 1(mod p).What is the assumption? Conclusion?5 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsProofs: 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 theconclusion p. That is;(p1∧ p2∧ ··· ∧ pn) → q6 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsProofs: 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 arethe assumptions? Conclusion? What steps would you take?Each step of a proof must be justified.7 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules of InferenceRecall the handout on the course web page http://www.cse.unl.edu/~cse235/files/LogicalEquivalences.pdfof logical equivalences.Table 2 contains a Cheat Sheet for Inference rules.8 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules of InferenceModus PonensIntuitively, modus ponens (or law of detachment) can be described asthe inference, “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.9 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules of InferenceAdditionAddition involves the tautologyp → (p ∨ q)Intuitively, if we know p to be true, we can conclude that either p or qare true (or both).In other words, p ∴ p ∨ q.ExampleI read the newspaper today, therefore I read the newspaper or I atecustard.aaNote that these are not mutually exclusive.10 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules 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.0 < x < 10 ≡ (x > 0) ∧ (x < 10)(x > 0) ∧ (x < 10) implies that x > 0 by simplification.x > 0 implies (x > 0) ∨ (x = 0) by addition.(x > 0) ∨ (x = 0) ≡ (x ≥ 0).11 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules of InferenceConjunctionThe conjunction is almost trivially intuitive. It is based on thetautology((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 thatthe right hand side, a logical conjunction is true.12 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules 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 thenwe can 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.13 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules of InferenceContrap ositi veThe tautology(p → q) → (¬q → ¬p)is called the contrapositive.If you are having trouble proving that p implies q in a direct manner,you can try to prove the contrapositive inste ad!14 / 82ProofsCSE235IntroductionHow ToRules ofInferenceExamplesFallaciesProofs WithQuantifiersTypes ofProofsRules of InferenceHyp othetical 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 makeany money, you will starve. Therefore, if you don’t get a job, you willstarve.15 / 82ProofsCSE235IntroductionHow ToRules
View Full Document
Unlocking...