Introduction I Proofs 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 Slides by Christopher M Bourke Instructor Berthe Y Choueiry Mathematical proofs like diamonds are hard and clear and will be touched with nothing but strict reasoning John Locke Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics 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 Sections 1 5 1 6 and 1 7 of Rosen cse235 cse unl edu Introduction II Introduction Terminology Mathematical proofs are necessary in computer science for several reasons 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 An algorithm must always be proven correct I I You may also want to show that its more efficient than other method This requires a proof Axioms or postulates are statements taken to be self evident or assumed to be true I I Proving certain properties of data structures may lead to new more efficient or simpler algorithms 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 Arguments may entail assumptions It may be useful and or necessary to make sure these assumptions are actually valid 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 Theorems Proofs A General How To I 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 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 Rules of Inference 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 Recall the handout on the course web page http www cse unl edu cse235 files LogicalEquivalences pdf of logical equivalences Table 1 page 66 contains a Cheat Sheet for Inference rules Each step of a proof must be justified Rules of Inference Rules of Inference Modus Ponens Addition Addition involves the tautology 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 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 Rules of Inference Rules of Inference Simplification Conjunction 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 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 Rules of Inference Rules of Inference Modus Tollens Contrapositive 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 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 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 Rules of Inference Hypothetical Syllogism Disjunctive Syllogism Based on the tautology p q q r p r A disjunctive syllogism is formed on the basis of the tautology p q p q Essentially this shows that rules of inference are in a sense transitive 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 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 The sky is either clear or cloudy Well it isn t cloudy therefore the sky is clear Rules of Inference Example I 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 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 Example I Example II 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 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 If And Only If Proof Proof I If you are asked to show an equivalence i e p q if and only if you must show an implication in both directions 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 …
View Full Document
Unlocking...