CMSC 150 Final Examination | Complete Solution

University of Maryland University College CMSC 150 – Introduction to Discrete Structures
Final Examination
1. (10 pts) For each the following groups of sets, determine whether they form a partition for the set of integers. Explain your answer.
a. A1 = {n  Z : n > 0}
A2 = {n  Z : n < 0}
b. B1 = {n  Z : n = 2k, for some integer k}
B2 = {n  Z : n = 2k + 1, for some integer k}
B3 = {n  Z : n = 3k, for some integer k}
2. (10 pts) Define f: Z  Z by the rule f(x) = 6x + 1, for all integers x.
a. Is f onto?
b. Is f one-to-one?
c. Is it a one-to-one correspondence?
d. Find the range of f.
Explain each of your answers.
3. (10 pts) f: R R and g: R  R are defined by the rules:
f(x) = x2 + 2  x  R
g(y) = 2y + 3  y  R
Find f ◦ g and g◦ f.
4. (10 pts) Determine whether the following binary relations are reflexive, symmetric, antisymmetric and transitive:
a. x R y  xy ≥ 0  x, y  R
b. x R y  x > y  x, y  R
c. x R y  |x| = |y|  x, y  R
For each of the above, indicate whether it is an equivalence relation or a partial order. If it is a partial order, indicate whether it is a total order. If it is an equivalence relation, describe its equivalence classes.
5. (10 pts) Determine whether the following pair of statements are logically equivalent. Justify your answer using a truth table.
p  (q  r) and p  q  r
6. (10 pts) Prove or disprove the following statement:
 n ,m Z, If n is even and m is odd, then n + m is odd
Then write the negation of this statement and prove or disprove it.
7. (10 pts) Prove the following by induction:
i=1n 3i – 2 = 3𝑛2−𝑛2
8. (10 pts) Use the permutation formula to calculate the number permutations of the set {V, W, X, Y, Z} taken three at a time. Also list these permutations.
9. (10 pts) Translate the following English sentences into statements of predicate
calculus that contain double quantifiers and explain whether it is a true
statement.
a. Every rational number is the reciprocal of some other rational
number.
b. Some real number is bigger than all negative integers.
10. (10 pts) Consider the following graph:
In each case, answer the question and then write the rationale for your answer.
a. Is this graph connected?
b. Is this a simple graph?
c. Does this graph contain any cycles?
d. Does this graph contain an Euler cycle?
e. Is this graph a tree?