ProofsSP22 MATH/CS 240: Discrete MathematicsUW-MadisonReference: zyBook chapter 2SP22 MATH/CS 240: Discrete Mathematics Proofs 1 / 23What is a proof?DefinitionA proof of a proposition P is a sequence of propositions which ends with P, obtainedby applying inference rules to premises.We will not use the above definition in this course. Instead:Definition (sociological)A proof is a valid argument which has sufficient detail to convince the reader that thestatement being proved is true.When I and your TAs read your proofs, we need to be convinced that you know yourstuff!SP22 MATH/CS 240: Discrete Mathematics Proofs 2 / 23Learning objectives1Recognize what constitutes a valid proof2Given a statement to prove, recognize which proof techniques are useful3Write correct proofs which are easily understandable in terms of:structurecontentProof-writing is a skill. Like any other skill, one gets better at it with practice.SP22 MATH/CS 240: Discrete Mathematics Proofs 3 / 23First step: How to start a proof?In order to prove a statement, we have to first recognize its logical form:What are the variables (if any)?What are the predicates (if any)?Which variables have quantifiers? Are they existential or universal? What orderare the quantifiers in?The answers to the above questions will determine how our proof begins, what proofstrategies are possible, etc.If a statement begins with a universal quantifier ∀x, then a proof should start withLet x be a blah.where blah refers to an element in the scope of x.If a statement begins with an existential quantifier ∃x, then a proof should start bychoosing a particular x in the scope of x.One has to choose x with care; we’ll discuss this later.SP22 MATH/CS 240: Discrete Mathematics Proofs 4 / 23Direct proofMany of the statements we will ask you to prove have the form∀x(P(x) → Q(x)),such as “for every integer x, if x is even, then x2is even”.A direct proof of such a statement proceeds as follows:1Begin by writing “Let x be such that P(x) holds.”2Present a sequence of logical steps which shows that Q(x) holds.Step 1 does not mean to fix a particular x such that P(x) holds. One way to thinkabout it is that the only property that we can use about x is that P(x) holds.SP22 MATH/CS 240: Discrete Mathematics Proofs 5 / 23Prove that if an integer is even, then its square is even.Proof: Let x be an even integer. We want to prove that x2is even.Since x is even, let k be an integer such that x = 2k.Then we havex2= (2k)2= 4k2.To show that x2is even, define l = 2k2.Since k is an integer, l is an integer as well.We conclude that x2= 2l where l is an integer, i.e., x2is even.SP22 MATH/CS 240: Discrete Mathematics Proofs 6 / 23Prove that the sum of two rational numbers is rational.Proof: Let x1and x2be rational numbers. We want to prove that x1+ x2is rational.Fix integers p1and q16= 0 such that x1= p1/q1. Fix integers p2and q26= 0 such thatx2= p2/q2. Then:x1+ x2=p1q1+p2q2=p1q2+ p2q1q1q2.Note that p1q2+ p2q1is an integer because p1, q2, p2and q1are all integers.Note that q1q2is a nonzero integer because q1and q2are both nonzero integers.We conclude that x1+ x2is a rational number.SP22 MATH/CS 240: Discrete Mathematics Proofs 7 / 23Prove that if x and y are positive real numbers, thenxy+yx≥ 2.Proof: We shall work backwards. To show thatxy+yx≥ 2, we can start by clearingthe denominators. Since y is positive, it suffices to show thatx +y2x≥ 2y .To show this, since x is positive, it suffices to show thatx2+ y2≥ 2xy .To show this, it suffices to show thatx2− 2xy + y2≥ 0or equivalently(x − y )2≥ 0.This is true because x − y is a real number, and the square of a real number is alwaysnonnegative.(Alternatively, one could work forwards: See zyBook Proof 2.4.1.)SP22 MATH/CS 240: Discrete Mathematics Proofs 8 / 23Proof technique 2: Proof by contrapositiveSuppose we are trying to prove p → q.If assuming that p is true does not seem to get you anywhere, you should considerassuming, instead, that q fails.If you are then able to show that p fails, then you have constructed a proof of¬q → ¬p (which is the contrapositive of p → q).SP22 MATH/CS 240: Discrete Mathematics Proofs 9 / 23Proof technique 2: Proof by contrapositiveProve that for all a ∈ Z, if a2is even, then a is even.Proof: We shall prove the contrapositive of the given statement.Assume that a ∈ Z is not even, i.e., a is odd. (We assume that every integer is eithereven or odd.)That means that there is some integer k such that a = 2k + 1.Thena2= (2k + 1)2= 4k2+ 4k + 1.We group terms to show that a2is odd:4k2+ 4k + 1 = 2(2k2+ 2k) + 1.This shows that a2is not even, as desired.SP22 MATH/CS 240: Discrete Mathematics Proofs 10 / 23Proof technique 2: Proof by contrapositiveProve that if x is a rational number and xy is an irrational number, then y is irrational.This statement has the form∀x∀y ((R(x) ∧ Q(x, y)) → ¬R(y ))≡ ∀x∀y (R(y ) → ¬(R(x) ∧Q(x, y))) contrapositive≡ ∀x∀y (R(y ) → (¬R(x) ∨¬Q(x, y))) De Morgan’swhich is still a little awkward to prove. (One can do so by cases; see later slides.)Alternatively, the given statement is also equivalent to∀x∀y ((R(y ) ∧R(x)) → ¬Q(x, y)),which isIf x and y are rational numbers, then xy is rational as well.SP22 MATH/CS 240: Discrete Mathematics Proofs 11 / 23Proof technique 3: Proof by contradictionOn an island, every person is one of two types:knights, who always tell the truth, andknaves, who always lie.On this island, you meet two different people A and B:A says “B is a knight.”B says “A and I are different types of people.”Is A a knight or a knave? (Smullyan 1978)We shall prove that A is a knave.Proof: Suppose, towards a contradiction, that A is a knight.Then A is telling the truth, so B is a knight as well.Then B is telling the truth, so A and B are different types of people.But A and B are both knights, contradiction.We conclude that A is a knave.SP22 MATH/CS 240: Discrete Mathematics Proofs 12 / 23Proof technique 3: Proof by contradictionIf we want to prove a statement q by contradiction:1Assume that q fails.2Derive some contradiction r ∧ ¬r.Noter need not have any obvious connection to q.A proof of p → q by contrapositive is a special case of proof by contradiction. Supposewe are able to prove that ¬q → ¬p. Then we could do a proof by contradictioninstead, as follows.Suppose, towards a contradiction, that p → q fails, i.e., p ∧¬q holds. Since ¬q → ¬p,we conclude that p