Proof Techniques Proving If-and-Only-If Statements Product of Odd Numbers is Odd x,yZ>0,xy is odd if and only if both x and y are odd. Proof. ("If" Part) We show that if both x and y are odd, then xy is odd. ... ( "Only if" Part) We need to prove that if xy is odd, then both x and y are odd. Q.5) What method/strategy would you use? A) Generalizing from Generic Particular B) Proof try Cases C) Proof by Contrapositive Proof Techniques Exercise: King of a Round-Robin Tournament If a team o has the highest number of wins, then o is a king. Q.1) The claim in symbolic form is A) MK B) M(0)K(o) C) oL,M(0)K(0) D) 0L,M(0)K(0) Predicates to simplify the notation L : set of teams K(u): " u is a king" M(u) : "u has the most wins" B(u,v):"u beats v " I(u,v) : "u beats some other team that beats v Proof Techniques Exercise: King of a Round-Robin Tournament If a team o has the highest number of wins, then o is a king. Proof. (by contradiction) Suppose, to the contrary, that Q.2) A) K(0) B) 0L, such that K(0) C) 0L, such that M(0)K(0) D) If K(0), then M(0) Proof Techniques Exercise: King of a Round-Robin Tournament If a team o has the highest number of wins, then o is a king. Proof. (Proof by contradiction) Suppose, to the contrary, that there is a team such that o has the most wins, but is not a king. Then, there is a team uL such that u beats o and Q.3) A) vL such that B(v,u)B(o,u) B) vL,B(o,v)B(u,v) C) vL,B(o,v)B(v,u) K(0)u=0,B(0,u)(v, such that B(0,v)B(v,u))