Discrete Mathematics II

MAT 141Dr. S. Epp

Discrete Mathematics II

Review Guide

1. Be sure you can give careful definitions for the following terms without referring to any notes: subset, proper subset, equality of sets, union of sets, intersection of sets, difference of sets, complement of a set, Cartesian product of sets, formal language over an alphabet, power set of a set, disjoint sets, partition of a set, logarithm with base b of a positive number x, one-to-one function, onto function, one-to-one correspondence, cardinality, countable set. Also be sure you can use these terms correctly in sentences and work with concrete examples involving them.

2. What is the difference between  and ?

3. How do you use an element argument to prove that one set is a subset of another set?

4. How are the procedural versions of set definitions used to prove properties of sets?

5. What is an “algebraic method” for proving that one set equals another set?

6. What is the “two-step method” for showing that two sets are equal? [Answer: Show that each is equal to the same set.]

7. Why is the empty set a subset of every set?

8. What is the special method used to show that a set equals the empty set?

9. How do you draw an arrow diagram for a function defined on a finite set?

10. Given a function defined by an arrow diagram or by a formula, how do you find values of the function, the range of the function, and the inverse image of an element in its co-domain? (Be sure you can work with the variety of different functions used in the exercises.)

11. How do you show that two functions are equal? How do you compute the composition of two functions that are given by arrow diagrams?

12. How do you determine with certainty whether functions are one-to-one and onto – both for functions defined on finite and on infinite sets?

13. How do you determine if a given function has an inverse function, and how do you find the inverse function if it exists?

14. What is the pigeonhole principle? (Be sure you can apply it in the kinds of cases explored in the exercises for the course.)

15. How do you show that one set has the same cardinality as another? How do you show that a given set is countable?

16. How do you construct a next-state table for an automaton given the transition diagram for the automaton? How do you construct a transition diagram for an automaton given its next-state table?

17. How do you find the state to which an automaton goes if the characters of a string are input to it? How do you find the language accepted by an automaton?

18. Given a simple formal language, how do you construct an automaton to accept the language?

19. How do you compute terms of a recursively defined sequence?

20. What is the “recursive paradigm”? How do you develop recurrence relations for sequences that are variations of the towers of Hanoi sequence, the Fibonacci sequence, and the sequence whose terms are the number of bit strings with a certain property?

21. What is the method of iteration for solving a recurrence relation? (Be sure you can use it to solve recurrence relations that are similar to those in the exercises. Also be sure you know how to simplify answers using the formula for the sum of the first n integers and the formula for the sum of the first n powers of a real number r.)

22. How is mathematical induction used to check that the solution to a recurrence relation is correct?

23. Be sure you can give careful definitions for the following terms without referring to any notes:order of a function, binary relation from a set A to a set B, reflexive binary relation, symmetric binary relation, transitive binary relation, equivalence relation on a set, equivalence class of an equivalence relation, connected graph, and tree.

24. How do you use the definition of O-notation to show that a given polynomial function has a certain order?

25. What is the theorem on polynomial orders?

26. What is the order of an algorithm segment?

27. How do you find the number of times a loop will iterate when an algorithm segment is executed? How do you use the theorem on polynomial orders to help find the order of an algorithm segment?

28. How are the basic properties of logarithmic functions derived? (See assigned exercises in Chapters 7 and 9.)

29. Given the definition of a binary relation as a subset of a Cartesian product, how do you determine whether one element is related to another?

30. How do you draw an arrow diagram or a directed graph for a binary relation?

31. Given a binary relation, how do you determine whether the relation is reflexive, symmetric, or transitive, and how do you justify this determination with a proof or counterexample?

32. Given an equivalence relation, how do you determine the equivalence classes of the relation? How do you prove basic properties of equivalence classes?

33. Be sure you understand the meaning of the following terms so that you can answer questions involving them: simple graph, complete graph on n vertices, degree of a vertex in a graph, total degree of a graph, walk in a graph, path in a graph, Euler circuit in a graph, Hamiltonian circuit in a graph, connected component of a graph, circuit-free graph, and tree.

34. Be sure you know how to apply the following theorems: that the total degree of a graph is twice the number of its edges, that the total degree of a graph is even, that any graph has an even number of edges of odd degree, that a graph has an Euler circuit if, and only if, the graph is connected and every vertex has even degree, that every tree with at least two vertices has a vertex of degree 1, and that any tree with n vertices has n-1 edges, and that any connected graph with n vertices and n-1 edges is a tree.