Proofs Sections 1 5 1 6 and 1 7 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline 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 Alerts CSCE 235 Fall 2008 Predicate Logic and Quantifiers 2 Motivation 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 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 3 Motivation 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 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 4 Terminology 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 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 5 Theorems 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 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 6 Proofs 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 q CSCE 235 Fall 2008 Predicate Logic and Quantifiers 7 Proofs 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 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 8 Outline 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 strategies CSCE 235 Fall 2008 Predicate Logic and Quantifiers 9 Rules of Inference Recall the handout on the course web page http www cse unl edu cse235 files LogicalEqui valences pdf In textbook Table 1 page 66 contains a Cheat Sheet for Inference rules CSCE 235 Fall 2008 Predicate Logic and Quantifiers 10 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 terminology modus ponens is the tautology p p q q Note therefore is sometimes denoted so we have p q and p q CSCE 235 Fall 2008 Predicate Logic and Quantifiers 11 Rules of Inference Addition Addition involves the tautology p 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 exclusive CSCE 235 Fall 2008 Predicate Logic and Quantifiers 12 Rules 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 x 0 x 0 x 0 x 0 x 0 x 0 CSCE 235 Fall 2008 Predicate Logic and Quantifiers by simplification by addition Q E D 13 Rules 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 be true Therefore we conclude on the right hand side that a logical conjunction is true CSCE 235 Fall 2008 Predicate Logic and Quantifiers 14 Rules of Inference Modus Tollens Similar to the modus ponens modus tollens is based on the following 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 UNL student then you are cornhusker Don Knuth is not a cornhusker Therefore we can conclude that Don Knuth is not a UNL student CSCE 235 Fall 2008 Predicate Logic and Quantifiers 15 Rules of Inference Contrapositive The contrapositive is the following tautology p q q p Usefulness If you are having trouble proving the p implies q in a direct manner You can try to prove the contrapositive instead CSCE 235 Fall 2008 Predicate Logic and Quantifiers 16 Rules of Inference Hypothetical Syllogism Hypothetical syllogism is based on the following tautology p q q r p r Essentially this shows that the rules of inference are in a sense transitive Example If you don t get a job you won t have money If you don t have money you will starve Therefore if you don t get a job you ll starve CSCE 235 Fall 2008 Predicate Logic and Quantifiers 17 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 Then we can conclude that q must hold Example The sky is either blue or grey Well it isn t blue Therefore the sky is grey CSCE 235 Fall 2008 Predicate Logic and Quantifiers 18 Rules of Inference Resolution For resolution we have the following tautology p q p r q r Essentially If we
View Full Document
Unlocking...