# CS2233 Discrete Mathematical Structures

CS2233 Discrete Mathematical Structures

CS2233 Discrete Mathematical Structures
CS2233 Discrete Mathematical Structures Homework 3 Due 10/20/21 before 11:59pm Annotate all your proofs with comments/text in order to receive full credit. 1. Contrapositive and contradiction (4 points) Consider the following claim: For all integers mand n, if ( m n) is odd then mis odd or nis odd. (1) (2 points) Prove the claim using a proof by contrapositive (2) (2 points) Prove the claim using a proof by contradiction 2. Equivalence (4 points) Prove the following for all x2 R: x is rational ,x 5 is rational ,x=3 is rational. 3. Proof by cases (3 points) Use a proof by cases to show that: (max(x; y) + min( x; y))2 + min( x; y) max( x; y) = x2 + 3 xy+y2 where x; y; z2R. 4. Rational, irrational (4 points) (1) (2 points) Prove or disprove that if xy is an irrational number, then xor y is also an irrational number. (2) (2 points) Prove that if x2 is irrational, then xis irrational. ( Hint: try a proof by contrapositive) 5. Sets (6 points) (1) (1.5 points) Use set builder notation to give a description of the set f 3; 2; 1;0 ;1 ;2 ;3 ;4 ;5 g . (2) (2 points) Let A= fa; b; c g, B =fx; y g, and C=f5;10 g. Find A B C and C A B. (3) (2.5 points) Let A= f1;4 ;8 ;16 gand B=f2;4 ;16 ;32 ;64 g. Find A[B, A B,A nB ,B nA , and jP(A )j. 6. Set Theorems (3 points) Prove A[(A B) = A.