ProofsOutlineMotivation (1)Motivation (2)TerminologyTheorems: ExampleProofs: A General How to (1)Proofs: A General How to (2)Slide 9Rules of InferenceRules of Inference: Modus PonensRules of Inference: AdditionRules of Inference: SimplificationRules of inference: ConjunctionRules of Inference: Modus TollensRules of Inference: ContrapositiveRules of Inference: Hypothetical SyllogismRules of Inference: Disjunctive SyllogismRules of Inference: ResolutionProofs: Example 1 (1)Proofs: Example 1 (2)Proofs: Example 2 (1)Proofs: Example 2 (2)If and Only IfExample (iff)Slide 26Fallacies (1)Little ReminderFallacies (2)Slide 30Proofs with QuantifiersProofs with Quantifiers: Example (1)Proofs with Quantifiers: Example (2)Slide 34Types of ProofsTrivial Proofs (1)Trivial Proofs (2)Vacuous ProofsDirect ProofsProof by Contrapositive (indirect proof)Proof by Contrapositive: ExampleProof by ContradictionProof by Contradiction: ExampleProof by CasesProof by Cases: ExampleExistence ProofsUniqueness ProofsUniqueness Proof: ExampleCounter ExamplesCounter Examples: ExampleCounter Examples: A Word of CautionProof StrategiesProofsSections 1.5, 1.6 and 1.7 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] Logic and QuantifiersCSCE 235, Fall 20082Outline•Motivation•Terminology•Rules of inference: •Modus ponens, addition, simplification, conjunction, modus tollens, contrapositive, hypothetical syllogism, disjunctive syllogism, resolution,•Examples•Fallacies•Proofs with quantifiers•Types of proofs:•Trivial, vacuous, direct, by contrapositive (indirect), by contradiction (indirect), by cases, existence and uniqueness proofs; counter examples•Proof strategies: •Forward reasoning; Backward reasoning; AlertsPredicate Logic and QuantifiersCSCE 235, Fall 20083Motivation (1)•“Mathematical proofs, like diamonds, are hard and clear, and will be touched with nothing but strict reasoning.” -John Locke•Mathematical proofs are, in a sense, the only true knowledge we have. •They provide us with a guarantee as well as an explanation (and hopefully some insight).Predicate Logic and QuantifiersCSCE 235, Fall 20084Motivation (2)•Mathematical proofs are necessary in CS–You must always (try to) prove that your algorithm •terminates •is sound, complete, optimal, •finds optimal solution–You may also want to show that it is more efficient than another method–Proving certain properties of data structures may lead to new, more efficient or simpler algorithms–Arguments may entail assumptions. You may want to prove that the assumptions are valid.Predicate Logic and QuantifiersCSCE 235, Fall 20085Terminology•A theorem is a statement that can be shown to be true (via a proof).•A proof is a sequence of statements that form an argument•Axioms or postulates are statements taken to be self evident or assumed to be true.•A lemma (plural lemmas or lemmata) is a theorem useful withing the proof of a theorem•A corollary is a theorem that can be established from theorem that has just been proven. •A proposition is usually a ‘less’ important theorem.•A conjecture is a statement whose truth value is unknown.•The rules of inference are the means used to draw conclusions from other assertions, and to derive an argument or a proof.Predicate Logic and QuantifiersCSCE 235, Fall 20086Theorems: Example•Theorem–Let a, b, and c be integers. Then•If a|b and a|c then a|(b+c)•If a|b then a|bc for all integers c•If a|b and b|c, then a|c•Corrolary:–If a, b, and c are integers such that a|b and a|c, then a|mb+nc whenever m and n are integers•What is the assumption? What is the conclusion?Predicate Logic and QuantifiersCSCE 235, Fall 20087Proofs: A General How to (1)•An argument is valid –if whenever all the hypotheses are true, –the conclusion also holds•From a sequence of assumptions, p1, p2, …, pn, you draw the conclusion p. That is:(p1 p2 … pn) qPredicate Logic and QuantifiersCSCE 235, Fall 20088Proofs: A General How to (2)•Usually a proof involves proving a theorem via intermediate steps•Example–Consider the theorem ‘If x>0 and y>0, then x+y>0’–What are the assumptions?–What is the conclusion?–What steps should we take?–Each intermediate step in the proof must be justified.Predicate Logic and QuantifiersCSCE 235, Fall 20089Outline•Motivation•Terminology•Rules of inference: •Modus ponens, addition, simplification, conjunction, modus tollens, contrapositive, hypothetical syllogism, disjunctive syllogism, resolution,•Examples•Fallacies•Proofs with quantifiers•Types of proofs•Proof strategiesPredicate Logic and QuantifiersCSCE 235, Fall 200810Rules of Inference•Recall the handout on the course web page –http://www.cse.unl.edu/~cse235/files/LogicalEquivalences.pdf•In textbook, Table 1 (page 66) contains a Cheat Sheet for Inference rulesPredicate Logic and QuantifiersCSCE 235, Fall 200811Rules of Inference: Modus Ponens•Intuitively, modus ponens (or law of detachment) can be described as the inference: p implies q; p is true; therefore q holds•In logic terminology, modus ponens is the tautology:(p (p q)) q•Note: “therefore” is sometimes denoted , so we have:p q and p, qPredicate Logic and QuantifiersCSCE 235, Fall 200812Rules of Inference: Addition•Addition involves the tautologyp (p q)•Intuitively, –if we know that p is true–we can conclude that either p or q are true (or both)•In other words: p (p q)•Example: I read the newspaper today, therefore I read the newspaper or I ate custard–Note that these are not mutually exclusivePredicate Logic and QuantifiersCSCE 235, Fall 200813Rules of Inference: Simplification•Simplification is based on the tautology(p q) p•So we have: (p q) p•Example: Prove that if 0 < x < 10, then x 0•0 < x < 10 (0 < x) (x < 10)•(x 0) (x < 10) (x 0) by simplification•(x 0) (x 0) (x = 0) by addition•(x 0) (x = 0) (x 0) Q.E.D.Predicate Logic and QuantifiersCSCE 235, Fall 200814Rules of inference: Conjunction•The conjunction is almost trivially intuitive. It is based on the following tautology:((p) (q)) (p q)•Note the subtle difference though:–On the left-hand side, we independently know p and q to
View Full Document
Unlocking...