Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

14:332:212 Discrete Mathematics – Midterm

2022

1.  (10 pts)

Let H(x,y) be the statement “x is from high school y” . Let C(x,z) be the statement “x is from University z”. Let F(x,y) be   the statement “x and y know each other” . Use quantifiers to express the following statement: In every university, there are at least two students who are from the same high school.

2. (10 pts)

Prove that ifn is an integer and 2  + 1 is odd, then n must be even (use two proofs, by contraposition and contradiction)

3. (5+5+5=15 pts)

For (1) and (2) below, determine whether they are True or False. For (3), provide all non-empty subsets ofthe given set.

(1)  ∅ ∈ {{∅}, {{∅}}}

(2)  {∅} ⊂ {{∅}, {{∅}}}

(3)  {{1}, {2, 3, 4}, 5}

4. (5+5+5=15pts)

Answer the following questions regarding sets:

(1) Let  be the function from ℜ to ℜ defined as () =  . Find  −1 ({||| < 1}).

(2) If || = 5, || = 3, and there is only one shared element, calculate | ∪ | .

(3) Determine if the function () = | − 1|,  ∈ ℜ, is one-to-one and draw a diagram of it.

5. (5+5=10 pts)

(1) Prove that 2  + 4 + 17 is Θ(2) (specify C and k)  (2) Determine whether the function log(3  + 1) is O(log x).

6. (5 pts) Use the insertion sort to put the sequence 6, 2, 5, 3, 9, 1 in an increasing order, please list all the steps.

7. (5+5+5=15 pts)

(1) Calculate the product of two binary expansions: (10101011)2  and (10011)2 .

(2) Find the prime factorization of 3003.

(3) Use the Euclidean Algorithm to calculate the greatest common divisor of 52 and 169.

9. (10 pts) Show that if x and y are both positive integers, then (2 − 1)  (2 − 1) = 2   − 1.