1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 6Milos [email protected] Sennott SquareInformal proofsM. HauskrechtCS 441 Discrete mathematics for CSProofs• The truth value of some statements about the world are obvious and easy to assess• The truth of other statements may not be obvious, ……. But it may still follow (be derived) from known facts about the worldProof: shows that the truth value of such a statement follows from (or can be inferred) from the truth value of other statementsImportant questions:– When is the argument correct?– How to construct a correct argument, what method to use?2M. HauskrechtCS 441 Discrete mathematics for CSTheorems• Theorem: a statement that can be shown to be true.– Typically the theorem looks like this:(p1  p2  p3  … pn )  q• Example:Fermat’s Little theorem: – If p is a prime and a is an integer not divisible by p, then:Premisesconclusionpapmod11Premises (hypotheses)conclusionM. HauskrechtCS 441 Discrete mathematics for CSFormal proofsAllow us to infer from new True statements from known True statementsaxiomspremisesconclusion++provedtheoremsTrueTrue ?3M. HauskrechtCS 441 Discrete mathematics for CSFormal proofsSteps of the proof for statements in the propositional logic are argued using: • Equivalence rules• Rules of inference (e.g. modus ponens)axiomspremisesconclusion++provedtheoremsTrueTrue ?M. HauskrechtCS 441 Discrete mathematics for CSProofs using rules of inferenceTranslations:• Assumptions: ¬ p  q, r  p, ¬ r  s, s t• We want to show: tProof: • 1. ¬ p  q Hypothesis• 2. ¬ p Simplification• 3. r  p Hypothesis• 4. ¬ r Modus tollens (step 2 and 3)• 5. ¬ r  s Hypothesis• 6. s Modus ponens (steps 4 and 5)• 7. s t Hypothesis• 8. t Modus ponens (steps 6 and 7)• end of proof4M. HauskrechtCS 441 Discrete mathematics for CSInformal proofsProving theorems in practice:• The steps of the proofs are not expressed in any formal language as e.g. propositional logic• Steps are argued less formally using English, mathematical formulas and so on• One must always watch the consistency of the argument made, logic and its rules can often help us to decide the soundness of the argument if it is in question• We use (informal) proofs to illustrate different methods of proving theorems M. HauskrechtCS 441 Discrete mathematics for CSMethods of proving theoremsBasic methods to prove the theorems:• Direct proof–p  q is proved by showing that if p is true then q follows• Indirect proof– Show the contrapositive ¬q  ¬p. If ¬q holds then ¬p follows• Proof by contradiction– Show that (p  ¬ q) contradicts the assumptions• Proof by cases• Proofs of equivalence–p  q is replaced with (p  q)  (q  p)Sometimes one method of proof does not go through as nicely as the other method. You may need to try more than one approach.5M. HauskrechtCS 441 Discrete mathematics for CSDirect proof•p  q is proved by showing that if p is true then q follows• Example: Prove that “If n is odd, then n2is odd.” Proof:• Assume the hypothesis is true, i.e. suppose n is odd. • Then n = 2k + 1, where k is an integer. n2= (2k + 1)2= 4k2+ 4k + 1 = 2(2k2+ 2k) + 1• Therefore, n2is odd. M. HauskrechtCS 441 Discrete mathematics for CSIndirect proof• To show p  q prove its contrapositive ¬q  ¬p • Why? p  q and ¬q  ¬p are equivalent !!!• Assume ¬q is true, show that ¬p is true.Example: Prove If 3n + 2 is odd then n is odd.Proof:• Assume n is even, that is n = 2k, where k is an integer.• Then: 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k+1) • Therefore 3n + 2 is even.• We proved ¬ “n is odd”  ¬ “3n + 2 is odd”. This is equivalent to “3n + 2 is odd”  “n is odd”. 6M. HauskrechtCS 441 Discrete mathematics for CSProof by contradiction• We want to prove p  q• The only way to reject (or disprove) p  q is to show that (p ¬q ) can be true• However, if we manage to prove that either q or ¬ p is True then we contradict (p  ¬q ) – and subsequently p  q must be true• Proof by contradiction. Show that the assumption (p  ¬q ) leads either to q or ¬ p which generates a contradiction.M. HauskrechtCS 441 Discrete mathematics for CSProof by contradiction• We want to prove p  q • To reject p  q show that (p  ¬q ) can be true• To reject (p  ¬q ) show that either q or ¬ p is TrueExample: Prove If 3n + 2 is odd then n is odd.Proof:• Assume 3n + 2 is odd and n is even, that is n = 2k, where k an integer.7M. HauskrechtCS 441 Discrete mathematics for CSProof by contradiction• We want to prove p  q • To reject p  q show that (p  ¬q ) can be true• To reject (p  ¬q ) show that either q or ¬ p is TrueExample: Prove If 3n + 2 is odd then n is odd.Proof:• Assume 3n + 2 is odd and n is even, that is n = 2k, where k an integer.• Then: 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)• Thus 3n + 2 is even. This is a contradiction with the assumption that 3n + 2 is odd. Therefore n is odd. M. HauskrechtCS 441 Discrete mathematics for CSVacuous proofWe want to show p  q• Suppose p (the hypothesis) is always false • Then p  q is always true.Reason:•F  q is always T, whether q is True or FalseExample:• Let P(n) denotes “if n > 1 then n2> n” is TRUE. • Show that P(0).Proof:• For n=0 the premise is False. Thus P(0) is always true.8M. HauskrechtCS 441 Discrete mathematics for CSTrivial proofsWe want to show p  q• Suppose the conclusion q is always true • Then the implication p  q is trivially true.• Reason:•p T is always T, whether p is True or FalseExample:• Let P(n) is “if a >=b then an>= bn ”• Show that P(0)Proof:a0>=b0is 1=1 trivially true.M. HauskrechtCS 441 Discrete mathematics for CSProof by cases• We want to show p1  p2  …  pn  q • Note that this is equivalent to – (p1  q)  (p2  q)  …  (pn  q)• Why?• p1  p2  …  pn  q <=> (useful)• ¬ (p1  p2  …  pn)  q <=> (De Morgan)• (¬p1  ¬p2  …  ¬pn)  q <=> (distributive)• (¬p1  q)  (¬p2  q)  … (¬pn  q) <=>