Discrete Mathematics Exam
Table of Points for marking purposes. Do not write in this table. multiple-choice true-or-false short-answer long-answer TOTAL max points possible 12 9 15 24 60 points points obtained Multiple-Choice Questions. Write your choice in the answer box. No justification is needed. Q1. Let A = {1, 2} and let B = {s, t, u, v, w}. How many injective functions are there from A to B? A. 20 B. 25 C. 32 D. 0 E. 10 F. None of the previous answers. Answer: [2 points] Q2. Let R be the equivalence relation on the set A = {�6,�2, 0, 1, 4, 5, 6, 7, 15} defined by xRy () ⇣ x ⌘ y (mod 5) or x ⌘ �y (mod 5) ⌘ Which one (if any) of the following statements is true? A. {�6, 6} is an equivalence class with respect to R. B. [�2]R = [6]R. C. P = � {�6,�2}, {0}, {1, 4, 5, 6, 7, 15} is the partition of A into equivalence classes. D. P = � {�6, 1, 4, 6}, {�2, 7}, {0, 5, 15} is the partition of A into equivalence classes. E. 4R7. F. None of the above. Answer: [2 points] 2 Q3. One of the following statements is false. Which one? A. A \ (B [ C) = (A \ B) [ (A \ C) B. A \ (B [ C) = A [ (B [ C) C. A [ (B \ C) = A \ (B \ C) D. (A [ B) \ C = (A \ C) [ (B \ C) E. (A [B) [ C = (A [B) \ C Answer: [2 points] Q4. How many strings of length 6 with symbols from {a, b, c, d, e} start with ‘ace’ or end with ‘ee’ ? (this is inclusive or) A. 755 B. 36 C. 750 D. 35 E. 745 F. 34 Answer: [2 points] 3 Q5. Let G be a graph with 7 vertices and 10 edges. If every vertex of G has degree 2 or 3, then how many vertices of each degree does G have? A. G has 0 vertices of degree 2 and 7 vertices of degree 3. B. G has 1 vertex of degree 2 and 6 vertices of degree 3. C. G has 2 vertices of degree 2 and 5 vertices of degree 3. D. G has 3 vertices of degree 2 and 3 vertices of degree 3. E. G has 4 vertices of degree 2 and 3 vertices of degree 3. F. No such graph exists. Answer: [2 points] Q6. How many binary strings of length 7 contain at least 5 zeros? A. 21 B. 32 C. 96 D. 4 E. 49 F. 29 G. None of the above. Answer: [2 points] 4 True-or-False Questions. Circle the correct responses. No justification is needed. Q7. Consider the following three graphs: [1.5 points] G H L Circle the correct responses. G is a tree. T F H is a forest. T F L is a tree. T F Q8. Consider the following sets: [3 points] S = � Ø, 1, {1} and T = � 1, {Ø, 1} Circle the correct responses. |S ⇥ T | = 9. T F � {1} ✓ S T F |S \ T | = 2 T F � {1}, {1} � 2 T ⇥ S T F |S [ T | = 4 T F |P(T )| = 4 T F 5 Q9. Consider the following relation on the set : [2 points] xRy () x(1 + y) is even. What properties does the relation R possess? Circle the correct responses. R is reflexive. T F R is symmetric. T F R is antisymmetric. T F R is transitive. T F Q10. Consider the following propositions with atomic variables x and y: [2.5 points] P1 : x ^ ¬y P2 : ¬x _ ¬y P3 : x ! y C : y ! x Circle the correct responses. The set {P1, P2, P3} is a consistent set of propositions. T F The set {P1, P2} is a consistent set of propositions. T F The argument (P1 ^ P2 ^ P3) ! C is a valid argument. T F The compound proposition P1 ^ P2 ! C is a tautology. T F Compound propositions P1 and ¬P3 are logically equivalent. T F 6 Short-Answer Questions. Write your final answer in the answer box. Wherever indicated, you must briefly justify your answers to receive full marks. Q11. Let a, b. and c be propositional variables. Give a disjunctive normal form (DNF) for the following compound proposition: P : (a $ b) ^ (b _ ¬c) DNF for P : Justification: [1.5 points] 7 Q12. Fully evaluate the following expression: ✓ 9 6 ◆ + ✓ 9 7 ◆ = Justification: [1.5 points] Q13. Consider the following sequence: (0, 1, 2, 3, 4, 5, 5) (a) Does there exist a graph with the above degree sequence? Circle: YES NO If so, draw an example of such a graph; otherwise, briefly explain why no such graph exists. (b) Draw an example of a tree whose degree sequence is (1, 1, 1, 1, 3, 3). No justification is needed. [2 points] 8 Q14. Determine the coe�cient of 1 x8 in the expansion of ✓ 3x2 + 5 x4 ◆10 . Your answer may include unevaluated factorials, binomial coe�cients, powers, products, or sums. Coe�cient of x �8 : Justification: [2.5 points] 9 Q15. Give an example of a compound proposition P such that • P consists of the propositional variables x, y, and z (all three variables must be used). • P contains only the logical connectives ¬ and ! and P must contain both these connectives. • P is a contradiction (justification required below). Make sure your proposition P contains only the variables x, y, and z, the logical con- nectives ¬ and ! and appropriate parentheses. P = Justification that P is a contradiction: [2 points] 10 Q16. Let f : ! ⇥ be a function defined by f(x) = (x3, x4). [3.5 points] Answer the following questions regarding the above function f . To justify your answers, either give a proof or a concrete numerical counterexample. Is f is injective? Circle: YES NO Justification (proof or counterexample): Is f is surjective? Circle: YES NO Justification (proof or counterexample): Is f is invertible? Circle: YES NO No justification is needed for this part. 11 Q17. Which of the following four graphs are bipartite? [2 points] For each graph, circle the correct response and justify your answer by either giving a proper 2-colouring of the graph, or by indicating an odd cycle in the graph. G Is G bipartite? Circle: YES NO H Is H bipartite? Circle: YES NO K Is K bipartite? Circle: YES NO L Is L bipartite? Circle: YES NO 12 Long-Answer Questions. Detailed solutions are required. Q18. Let m be a positive integer. Give a proof by contradiction of the following statement: Statement: If 3m+1 marbles are placed into m jars, then at least one jar will contain at least 4 marbles. [5 points] 13 Q19. Use Mathematical Induction to prove that (2n)! is a multiple of 2n+1 for all integers n � 2. Clearly state the proposition to be proved, Basis of Induction, Induction Hypothesis, and Induction Step. Clearly indicate where the Induction Hypothesis is used in your proof. [5 points] 14 Q20. Use a truth tree to determine whether or not the proposition P below is a tautology. If you claim that P is not a tautology, give all counterexamples. P : � c _ (b ! ¬a) � $ ¬(a ^ b) Clearly indicate the root of the tree. Use the branching rules precisely as taught in class. Do not use equivalences. Do not skip steps or combine branching rules. Make sure your truth tree is fully grown. Complete truth tree: Is P a tautology? Circle: YES NO If you circled NO, give all counterexamples: [5 points] 15 Q21. Define a binary relation R on the set A = {binary strings of length 4} as follows: For all strings s, t 2 A, sRt if and only if s and t have the same number of ones. (a) Prove that R is an equivalence relation. (b) Give the equivalence class of the string s = ‘1010’ with respect to the relation R. h ‘1010’ i R = [5 points] 16 Q22a. Consider the following two graphs: [4 points]a b c d e f G z xw v u y H Are G and H isomorphic? If so, give an isomorphism between them and verify that your function is an isomorphism; otherwise, clearly explain why they are not isomorphic. Q22b. Now consider these two graphs: 5 6 7 8 1 2 3 4 K w x y z s t u v L Are K and L isomorphic? If so, give an isomorphism between them and verify that your function is an isomorphism; otherwise, clearly explain why they are not isomorphic. 17 Extra page for scrap work. :-) 18