Proofs CSE235 Proofs Introduction How To Examples Fallacies Proofs With Quantifiers Slides by Christopher M Bourke Instructor Berthe Y Choueiry Types of Proofs Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 82 Section 1 5 of Rosen cse235 cse unl edu Introduction I Proofs CSE235 Introduction How To A proof is a proof What kind of a proof It s a proof A proof is a proof And when you have a good proof it s because it s proven Jean Chre tien Examples Fallacies Proofs With Quantifiers Types of Proofs 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 truly absolute knowledge we can have They provide us with a guarantee as well as an explanation and hopefully some deep insight 2 82 Introduction II Proofs CSE235 Introduction Mathematical proofs are necessary in computer science for several reasons How To Examples Fallacies Proofs With Quantifiers Types of Proofs An algorithm must always be proven correct You may also want to show that its more efficient than other method 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 or necessary to make sure these assumptions are actually valid 3 82 Introduction Terminology Proofs CSE235 A theorem is a statement that can be shown to be true via a proof Introduction How To Examples Fallacies Proofs With Quantifiers Types of Proofs 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 Lemmas and corollaries are also certain types of theorems A proposition as opposed to a proposition in logic is usually used to 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 means used to draw conclusions from other assertions These form the basis of various methods of proof 4 82 Theorems Example Proofs CSE235 Introduction How To Examples Fallacies Proofs With Quantifiers Consider 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 Types of Proofs What is the assumption Conclusion 5 82 Proofs A General How To I Proofs CSE235 Introduction How To Rules of Inference Examples Fallacies Proofs With Quantifiers Types of Proofs 6 82 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 q Proofs A General How To II Proofs CSE235 Introduction Usually a proof involves proving a theorem via intermediate steps How To Rules of Inference Examples Fallacies Proofs With Quantifiers Types of Proofs 7 82 Example Consider the theorem If x 0 and y 0 then x y 0 What are the assumptions Conclusion What steps would you take Each step of a proof must be justified Rules of Inference Proofs CSE235 Introduction How To Rules of Inference Examples Fallacies Proofs With Quantifiers Types of Proofs 8 82 Recall the handout on the course web page http www cse unl edu cse235 files LogicalEquivalences pdf of logical equivalences Table 2 contains a Cheat Sheet for Inference rules Rules of Inference Modus Ponens Proofs CSE235 Introduction How To Rules of Inference Examples Intuitively modus ponens or law of detachment can be described as the inference p implies q p is true therefore q holds In logic terms modus ponens is the tautology Fallacies Proofs With Quantifiers Types of Proofs 9 82 p p q q Notation note therefore is sometimes denoted so we have p and p q q Rules of Inference Addition Proofs CSE235 Addition involves the tautology Introduction p p q How To Rules of Inference Examples Intuitively if we know p to be true we can conclude that either p or q are true or both Fallacies Proofs With Quantifiers In other words p p q Types of Proofs Example I read the newspaper today therefore I read the newspaper or I ate custard a a 10 82 Note that these are not mutually exclusive Rules of Inference Simplification Proofs CSE235 Simplification is based on the tautology Introduction p q p How To Rules of Inference Examples so that we have p q p Fallacies Example Proofs With Quantifiers Prove that if 0 x 10 then x 0 Types of Proofs 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 82 Rules of Inference Conjunction Proofs CSE235 Introduction How To Rules of Inference Examples The conjunction is almost trivially intuitive It is based on the tautology p q p q Fallacies Proofs With Quantifiers Types of Proofs 12 82 Note the subtle difference though On the left hand side we independently know p and q to be true Therefore we conclude that the right hand side a logical conjunction is true Rules of Inference Modus Tollens Proofs CSE235 Introduction How To Rules of Inference Examples Fallacies Proofs With Quantifiers Types of Proofs 13 82 Similar to modus ponens modus tollens is based on the tautology q p q p In other words if we know that q is not true and that p implies q then we can conclude that p does not hold either Example If you are a UNL student you are a cornhusker Don Knuth was not a cornhusker Therefore we can conclude that Knuth was not a UNL student Rules of Inference Contrapositive Proofs CSE235 Introduction How To Rules of Inference Examples Fallacies Proofs With Quantifiers Types of Proofs 14 82 The 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 Rules of Inference Hypothetical Syllogism Proofs CSE235 Introduction Based on the tautology How To p q q r p r Rules of Inference Examples Fallacies Proofs With Quantifiers Types of Proofs 15 82 Essentially this shows that rules of inference are in a sense transitive Example If you don t get a job you won t make any money If you don t make any money you will starve Therefore if you don t get a job you will starve Rules of Inference Disjunctive Syllogism Proofs CSE235 Introduction How To Rules of Inference A disjunctive syllogism is formed on the basis of the tautology p q p q Examples Fallacies Proofs With Quantifiers Types of Proofs 16 82 Reading this in English we see that if either p or q hold and we know that p does not hold we can conclude that
View Full Document
Unlocking...