DOC PREVIEW
UNL CSCE 235 - Proofs

This preview shows page 1-2-3-4-5-39-40-41-42-43-44-78-79-80-81-82 out of 82 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 82 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionHow ToRules of InferenceExamplesFallaciesProofs With QuantifiersTypes of ProofsProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsProofsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.5, 1.6, and 1.7 of [email protected] / 46ProofsCSE235IntroductionHow 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 strict reasoning.” –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 / 46ProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsIntroduction IIMathematical proofs are necessary in computer science for severalreasons.An algorithm must always be proven correct.You may also want to show that its more effic ient 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 make sure these assumptions are actually valid.3 / 46ProofsCSE235IntroductionHow ToExamplesFallaciesProofs WithQuantifiersTypes ofProofsIntroductionTerminologyA theorem is a statement 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 t rue.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 c onclusionsfrom other assertions. These form the basis of various methods ofproof.4 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow 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 ass umptions, p1, p2, . . . , pn, you draw theconclusion p. That is;(p1∧ p2∧ ··· ∧ pn) → q6 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow 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 1 (page 66) contains a Cheat Sheet for Inference rules.8 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow 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 c an conclude that Knuth was not a UNLstudent.13 / 46ProofsCSE235IntroductionHow 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 instead!14 / 46ProofsCSE235IntroductionHow 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 / 46ProofsCSE235IntroductionHow ToRules


View Full Document

UNL CSCE 235 - Proofs

Documents in this Course
Logic

Logic

77 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Proofs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Proofs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Proofs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?