CSE211 - Homework 2 - Solved

Discrete Mathematics


Problem 1: Sets                                                                                                                                         (2+2+2+2+2=10 points)

Which of the following sets are equal? Show your work step by step.

(a)    {t : t is a root of x2 – 6x + 8 = 0}

(b)   {y : y is a real number in the closed interval [2, 3]}

(c)    {4, 2, 5, 4}

(d)   {4, 5, 7, 2} - {5, 7}

(e)    {q: q is either the number of sides of a rectangle or the number of digits in any integer between 11 and 99}

(Solution)
1

– Homework #2                                                                                                                                                                                        2

Problem 2: Cartesian Product of Sets                                                                                                                      (15 points)

Explain why (A × B) × (C × D) and A × (B × C) × D are not the same.

(Solution)
Problem 3: Cartesian Product of Sets in Algorithms
(25 points)

Let A, B and C be sets which have different cardinalities. Let (p, q, r) be each triple of A × B × C where p ∈ A, q ∈ B and r ∈ C. Design an algorithm which finds all the triples that are satisfying the criteria: p ≤ q and q ≥ r. Write the pseudo code of the algorithm in your solution.

For example: Let the set A, B and C be as A = { 3, 5, 7 }, B = { 3, 6 } and C = { 4, 6, 9 }. Then the output should be : { (3, 6, 4), (3, 6, 6), (5, 6, 4), (5, 6, 6) }.

(Note: Assume that you have sets of A, B, C as an input argument.)

(Solution)
 

 

for write a condition do

end

When you want to write a while loop, you can use:

while write a condition do

          If you need to return, use return end

For any additional things you have to do while writing your pseudo code, Google ”How to use algorithm2e in Latex?”.

 

– Homework #2                                                                                                                                                                                        3

Problem 4: Relations                                                                                                                    (3+3+3+3+3+3+3=21 points)

Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive, where (x, y) ∈ R if and only if (a) x 6= y.

(Solution)

(b)   xy ≥ 1.

(Solution)

(c)    x = y + 1 or x = y - 1.

(Solution)

(d)   x is a multiple of y.

(Solution)

(e)    x and y are both negative or both nonnegative.

(Solution)

(f)     x ≥ y2. (Solution)

(g)    x = y2.

(Solution)
Problem 5: Functions

If f and f ◦ g are one-to-one, does it follow that g is one-to-one? Justify your answer.

(Solution)
(15 points)
Problem 6: Inverse of Functions
(7+7=14 points)
Let f be the function from R to R defined by f(x) = x2. Find

(a) f−1 ({ x | 0 < x < 1 })

(Solution)

(b)f−1 ({ x | x > 4 })

(Solution)