FinalExam CMSC 150, Summer 2013 Introduction to Discrete Structures Reece Harris, Instructor August 12, 2013 • Unless otherwise marked, each problem carries a maximum value of 1 point. The grade will be the number of points divided by the total possible times 100 to obtain the percentage. • General Instructions: You may take as much time as you wish and use whatever references you can find except your answers must be your own work. • In the last section do show your work where appropriate. 1
1 True-False 1 point for each question with a correct answer, 0 point if unanswered, and -1 point if incorrect. Do be Careful: Guessing could result with a score of 0 points with half correct and half incorrect! 1. An antisymmetric relation is a relation that is not symmetric. 2. Equivalent propositional statements have the same truth values for every truth value assignment to the component statements. 3. An Eulerian trail is the same as an Eulerian circuit. 4. If a graph has an Euler cycle, it also has a Hamiltonian cycle. 5. Let P(x, y) be the sentence “ x divides y ” where the domain is the set of integers. The sentence ?xP(x, y), y is a free variable. 6. P(x, y) is defined in the previous problem. The sentence ?xP(x, y) has a truth value. 7. P(x, y) is defined in the previous problem. The sentence ?x(?yP(x, y)), has a truth value. 8. P(x, y) is defined in the previous problem. P(6, 3) is false. 9. Given a set S with 11 elements. The number of possible equivalence classes that can be defined on S is exactly two. 10. Given the three statements P(1), P(2), P(3) with P(1) ? P(2), P(2) ? P(3), and you are also given that P(1) is true, but P(3) can sometimes be false. 11. In the statement of the theorem “twice an odd integer is even,” an existential quantifier is understood. 12. To prove the conjecture that “If Denver is a capital, then Colorado is a state,” it is sufficient to prove that “If Colorado is a state, then Denver is a Capitol.” 13. The set of all subsets of a n-set…