14:332:212 Discrete Mathematics – Midterm 2022
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.
8. (5+5=10 pts)
(1) Find 128129 17.
(2) Find 220 + 330 + 440 + 550 7.
9. (10 pts) Show that if x and y are both positive integers, then (2 − 1) (2 − 1) = 2 − 1.
2022-05-07