FinalExam CMSC 150, Summer 2013 Introduction to Discrete Structures Reece Harris, Instructor August...

Question

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 has n2 elements. 2 14. The principle of inclusion-exclusion requires that the sets A and B should be disjoint in order to find the number of elements in A ? B. 15. The number of combinations of r objects selected from a set of n where n>r> 1, is fewer than the number of permutations of r objects constructed from the set of n objects. 16. The number of all functions from an n-set to a 3-set is 3n. 17. Let S = {0, 1} with the very simple relation h = {(1, 1)}. This relation is transitive. 18. Every binary tree with n edges has 2n vertices. 19. Every relation is a function. 20. The negation of “All men are mortal.” is “All men are immortal.” 21. There is a tree with 6 vertices and such that the degree of every vertex is greater than 1. 22. If there is a cycle in a graph, then this graph cannot be a tree. 23. The number of injective functions from the set {a, b, c, d, e, f} into {1, 2, 3} is 0. 24. A collection of numbers defined recursively by: (a) S(1) = 7 (b) S(n)=3 * S(n - 1) + 2 for n = 2 contains the number 215. 2 Multiple Choice 1. The converse of “If I either misplaced my keys or forgot the combination, then I cannot open my car door” is: a. If I cannot open my car door, then I either misplaced my keys or forget the combination. b. If I did not misplace my keys and I did not forget the combination, then I can open my car door. 3 c. If I can open my car door, then I did not misplace my keys and I did not forget the combination. d. If I can open my car door, then I did misplace my keys and I did not forget the combination. e. None of the above. 2. Over the set of integers, let R be the relation defined by xRy means: x - y is divisible by 7. The number of sets in this equivalence relation is: a. infinite b. 8 c. This is not an equivalence relation d. 7 e. None of the above. 3. Let S = {{Ø}, {{Ø}, Ø}}. |S| is equal to : a. 0 b. 1 c. 2 d. 3 e. None of the above. 4. Let the universe for these statements be the positive integers. The statements: D2(x) = “ x is divisible by 2” and D6(x) = “x is divisible by 6.” A formal statement that states divisibility by 6 guarantees divisibility by 2 is: a. ?x,(D2(x) ? D6(x)) b. ?x,(D6(x) ? D2(x)) c. ?x,(D2(x) ? ¬D6(x)) d. ?x,(D6(x) ? ¬D2(x)) e. None of the above. 4 5. The negation of the statement ?x ? N, x2 = 2) is a. ?x ? N, x2 = 2 b. ?x ? N, x2 = 2 c. ?x ? N, x2 = 2 d. None of the above are correct. 6. In how many ways can five distinct Martians and five distinct Jovians be seated around a circular table? a. C(10, 5)2 b. 5!2 c. 5!2/10 d. 9! e. None the above are correct. 7. Which of these statements are sufficient to guarantee a given graph T is a tree. a. T is acyclic. b. T has n-1 edges. c. T is acyclic and has n-1 edges d. None of the above are sufficient. 8. How many non-isomorphic graphs are there with 3 vertices? a. 2 b. 3 c. 4 d. 6 e. None of the above are correct. 5 9. ¬(p ? q) ? q is logically equivalent (=) to: a. q b. ¬q c. c (symbol for a contradiction) d. (p ? q) e. None of the above 10. The negation of the statement “I missed the train but my watch was not slow” is: a. I did not miss the train and my watch was not slow. b. I missed the train or my watch was slow. c. I did not miss the train or my watch was slow. d. I missed the train or my watch was not slow. e. None of the above. 3 Other Problems 1. (3 points) Write out the formal structure of this deduction, then decide whether it is valid argument giving your reasons why you think it is a valid deduction (from Lewis Carroll): (a) Nothing intelligible ever puzzles me. (b) Logic puzzles me. (c) Therefore, logic is unintelligible. 2. Let the universe be the set of integers, and let G(x, y) be the sentence “x2 = y” for x and y variables with values in this domain. Using this sentence G, write in the language of the predicate logic the sentence: “There is an integer whose square is 25.” 6 3. Let the universe be all animals. Write in the language of the predicate logic with proper quantifiers and parentheses the statement: “Some cats chase any dog.” Let C(x) be “x is a cat, D(x), “ x is a dog”, and Ch(r,s), “r chases s”. 4. (3) Let the universal set be the set R of real numbers, X = {a ? R |-7 a  0. b) ?x ? D, if x is less then 0 then x is even. c) ?x ? D, if x is even then x = 0. d) ?x ? D, if the ones digit of x is 2, then the tens digit is 3 or 4. e) ?x ? D, if the ones digit of x is odd, then the tens digit is even. 11. (2) Complete the following truth table by filling in the blanks with T or F as appropriate. P Q ¬P P ? Q ¬P ? (P ? Q) [¬P ? (P ? Q)] ? Q T T T F F T F F (1 point) Is the proposition in the final column a tautology? 12. (1 point) Calculate R(6). R(1) = 2, R(2) = 3, and, R(n)=(R(n - 1)2 ) * R(n - 2),n> 2 8 13. (3) Prove the following statement for all positive integers n using mathematical induction: 1 + 3 + 5 + ... + (2n - 1) = n2. You must execute all steps clearly and distinctly for full credit. 14. (2) Suppose that A and B are sets. Give a formal proof of the statement Please, no examples! An example will be no proof of this general theorem which holds for ANY pair of sets A and B satisfying the given condition.: ?A, B ((A-B)?(B -A) = A ? B) ? (A n B = Ø). Hint: Use a proof by contradiction. 15. Given vertices {1, 2, 3, 4} and the edge set {1, 2}, {2, 4}, {2, 3}, {3, 4}, {4, 1}}. Explain why the subgraph with the same vertices but with the edge set {1, 2}, {2, 3}, {3, 4}, {4, 1}} is not an induced subgraph. 9 Out[20]= 1 2 3 4 5 16. For the above graph, determine whether it has an Eulerian trail and give your reasons why it does or does not have an Eulerian trail. Congratulations! This is the End. END OF THE FINAL EXAM for CMSC150 Summer 2013

Robert · Accepted Answer

Final Exam CMSC 150, Summer 2013 
Introduction to Discrete Structures
1. True False 
 
1. False 
2. True 
3. False 
4. False 
5. True 
6. False 
7. True 
8. True 
9. False 
10. False 
11. False 
12. False 
13. True 
14. false 
15. True 
16. True 
17. True 
18. False 
19. False 
20. True 
21. False 
22. True 
23. True 
24. True 
2 Multiple Choice 
 
1. The converse of “If I either misplaced my keys or forgot the combination, 
then I cannot open my car door” is: 
a. If I cannot open my car door, then I either misplaced my keys or 
forget the combination. 
b. If I did not misplace my keys and I did not forget the combination, 
then I can open my car door. 
c. If I can open my car door, then I did not misplace my keys and I 
did not forget the combination. 
d. If I can open my car door, then I did misplace my keys and I did 
not forget the combination. 
e. None of the above. 
 
 
2. Over the set of integers, let R be the relation defined by xRy means: 
x − y is divisible by 7. The number of sets in this equivalence relation 
is: 
a. infinite 
b. 8 
c. This is not an equivalence relation 
d. 7 
e. None of the above. 
 
 
3. Let S = {{∅}, {{∅}, ∅}}. |S| is equal to : 
a. 0 
b. 1 
c. 2 
d. 3 
e. None of the above. 
 
 
4. Let the universe for these statements be the positive integers. The 
statements: D2(x) = “ x is divisible by 2” and D6(x) = “x is divisible 
by 6.” A formal statement that states divisibility by 6 guarantees 
divisibility by 2 is: 
a. ∃x, (D2(x) → D6(x)) 
b. ∀x, (D6(x) → D2(x)) 
c. ∃x, (D2(x) ∧￢D6(x)) 
d. ∀x, (D6(x) ∧￢D2(x)) 
e. None of the above. 
 
5. The negation of the statement ∀x ∈ N, x2 = 2) is 
a. ∃x ∈ N, x2 = 2 
b. ∀x ∈ N, x2 _= 2 
c. ∃x ∈ N, x2 _= 2 
d. None of the above are correct. 
 
6. In how many ways can five distinct Martians and five distinct Jovians 
be seated around a circular table? 
a. C(10, 5)2 
b. 5!2 
c. 5!

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...

Answer To: FinalExam CMSC 150, Summer 2013 Introduction to Discrete Structures Reece Harris, Instructor August...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment