Final Exam Review - 2021 261 PDF

Preview

Summary

The review for the final exam....

Description

MAT 2358: Discrete Mathematical Structures (261) Final Exam Review 1 What to expect: Exam 1 consists of 13 questions, some are multiple choice. You will have all necessary tables to use during the exam. Bring a calculator that is not your cell phone.

2 How to study: Review the important concepts. Make sure you know how to properly apply the definitions of concepts. Go through practice problems – but! make sure you try to do them without looking at your notes or any references. Feel free to email me questions!

3 Problems to study/review for the exam: • Any of the textbook homework problems (not just the suggested problems!) • Any of the problems from the quizzes • Any problems from sections we’ve covered in the textbook • Any problems/examples we’ve discussed in class

4 Some Review Problems 1. Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q . 2. Give the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions “I’ll finish my discrete mathematics homework.” and “I’ll go to the mall this weekend.” 3. Define the converse and contrapositive of a conditional statement. 4. Given a compound proposition, show the negation of that compound proposition. 5. Describe the two different ways to that two compound propositions are logically equivalent, or to show that a compound proposition is a tautology. 6. Show in the two different ways that ¬p ∨ (r → ¬q) and ¬p ∨ ¬q ∨ ¬r are logically equivalent. 7. Give an example of the a predicate P (x, y) such that ∃x∀yP (x, y) and ∀y∃xP (x, y) have different truth values. 8. Use the rules of inference to show that if ∀x(P (x) ∨ Q(x)) and ∀x((¬P (x) ∧ Q(x)) → R(x)) are true, then ∀x(¬R(x) → P (x)) is also true, where the domains of all quantifiers are the same.

1

MATH 2358(261) Exam date: Tuesday, May 11, 2021 9. Prove or disprove that the product of two irrational numbers is irrational. 10. Prove or disprove that the product of a nonzero rational number and an irrational number is irrational. 11. Prove or disprove that the difference of a nonzero rational number and an irrational number is rational. 12. Use a proof by contraposition to show that if x + y ≥ 2, where x and y are real numbers, then x ≥ 1 or y ≥ 1. 13. Prove that if n is an odd integer, then there is a unique integer k such that n is the sum of k − 2 and k + 3. 14. Give the definition of a A ⊆ B for sets A and B. Give a concrete example of a set that is a subset of another set. 15. Give the definition of A − B for sets A and B. Give concrete examples of A, B, and A − B . 16. For a family of sets , 3, ..., i} where i is a positive integer, determine or describe S Ai = {0, 1,T2∞ A and the sets given by ∞ i i=1 i=1 Ai . 17. Given sets A and B, define A × B . 18. Give the definitions of a one-to-one function and an onto function. 19. Given an expression, decide if it is a function. 20. Given a function, decide if it is one-to-one or onto. 21. Give the definition of a divides b. Show that 3|12. 22. Give the definition of a ≡ b(mod m). Show that 4 ≡ 28(mod 6). 23. Show that 937 is an inverse of 13 modulo 2436. 24. Find an inverse of 4 modulo 9. 25. Solve the congruence 4x ≡ 5(mod 9) using the inverse of 4 modulo 9. 26. Use prime factorization to find lcm(12, 18). 27. Use prime factorization to find lcm(256, 125). 28. Use the Euclidean algorithm to find gcd(12, 18). 29. Use the Euclidean algorithm to find gcd(1529, 14039). P 30. Prove using mathematical induction that ni=1 i2 = n(n+1)(2n+1) for all n ≥ 1. 6 P 31. Prove using mathematical induction that ni=1 i = n(n+1) for all n ≥ 1. 2 32. Prove using mathematical induction that for all n ∈ N, 8n − 3n is divisible by 5. 33. Define what it means for a graph to have an Euler path, an Euler circuit, a Hamilton path, and a Hamilton circuit. 2

MATH 2358(261) Exam date: Tuesday, May 11, 2021

34. Define what it means for a pair of graphs to be isomorphic. Describe how one might check to see if two graphs are isomorphic. 35. Define what it means for two graphs to be homeomorphic. 36. State Kuratowski’s Theorem. Given a graph, decide if it is planar. 37. Is it possible to remove one vertex (and all edges incident with that vertex) from K6 to produce a planar graph? What about K5 ? 38. Given a graph, decide if it has an Euler path, an Euler circuit, a Hamilton path, and/or a Hamilton circuit. 39. Define what it means for a graph to be planar. 40. Given a pair of graphs, decide if they are isomorphic. If so, show the mapping between the vertex sets. If not, describe why they are not isomorphic. 41. Given the following list of numbers: 12, 4, 5, 27, 14, 25, 8, 3, 100, 15; create a binary search tree for this list. 42. Given an ordered rooted tree, in which order do you visit the vertices if you conduct a preorder traversal, an inorder traversal, and a postorder traversal? 43. Given a connected weighted graph, find a minimum spanning tree using Prim’s Algorithm. 44. Given a connected weighted graph, find a minimum spanning tree using Kruskal’s Algorithm.

3...