Notes Proofs Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Section 1 5 of Rosen cse235 cse unl edu Notes Introduction I 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 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 Notes Introduction II Mathematical proofs are necessary in computer science for several reasons I An algorithm must always be proven correct I You may also want to show that its more efficient than other method This requires a proof I Proving certain properties of data structures may lead to new more efficient or simpler algorithms I Arguments may entail assumptions It may be useful and or necessary to make sure these assumptions are actually valid Notes Introduction Terminology I A theorem is a statement that can be shown to be true via a proof I A proof is a sequence of statements that form an argument I Axioms or postulates are statements taken to be self evident or assumed to be true I 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 I A conjecture is a statement whose truth value is unknown I The rules of inferences are the means used to draw conclusions from other assertions These form the basis of various methods of proof Notes Theorems Example 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 What is the assumption Conclusion Notes Proofs A General How To I 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 Notes Proofs A General How To II 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 Conclusion What steps would you take Each step of a proof must be justified Notes Rules of Inference 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 Notes Rules 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 terms modus ponens is the tautology p p q q Notation note therefore is sometimes denoted so we have p and p q q Notes Rules of Inference Addition Addition involves the tautology p p q Intuitively if we know p to be 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 1 1 Note that these are not mutually exclusive Notes Rules of Inference Simplification Simplification is based on the tautology p q p so that we have p q p Example Prove that if 0 x 10 then x 0 I 0 x 10 x 0 x 10 I x 0 x 10 implies that x 0 by simplification I x 0 implies x 0 x 0 by addition I x 0 x 0 x 0 Notes Rules of Inference Conjunction The 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 we independently know p and q to be true Therefore we conclude that the right hand side a logical conjunction is true Notes Rules of Inference Modus Tollens 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 Notes Rules of Inference Contrapositive 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 Notes Rules of Inference Hypothetical Syllogism Based on the tautology p q q r p r 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 Notes Rules of Inference Disjunctive Syllogism A disjunctive syllogism is formed on the basis of the tautology p q p q 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 q must hold Example The sky is either clear or cloudy Well it isn t cloudy therefore the sky is clear Notes Rules of Inference Resolution For resolution we have the following tautology p q p r q r Essentially if we have two true disjunctions that have mutually exclusive propositions then we can conclude that the disjunction of the two non mutually exclusive propositions is true Notes Example I The best way to become accustomed to proofs is to see many examples To begin with we give a direct proof of the following theorem Theorem The sum of two odd integers is even Notes Example I Proof Let n m be odd integers Every odd integer x can be written as x 2k 1 for some other integer k Therefore let n 2k1 1 and m 2k2 1 Then consider n m 2k1 1 2k2 1 2k1 2k2 1 1 Associativity Commutativity 2k1 2k2 2 Algebra 2 k1 k2 1 Factoring By definition 2 k1 k2 1 is an even number therefore n m is even Notes Example II Assume that the statements I p q I r s I r p to be true Assume that q is false Show that s must be true Notes Example II Proof Proof I Since p q and q are true p is true by modus tollens i e p must be false I Since r p and p are true r is true by disjunctive syllogism I Since r s is true and r is true s is true by modus ponens I Q E D 2 2 Latin quod erat demonstrandum meaning that which …
View Full Document
Unlocking...