CS2233 Discrete Mathematical Structures

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.