Math 2305

Final Sample

1. Define the following (5 points each)

a) An equivalence relation.

b) A rooted tree.

c) A forest.

d) A tree.

e) The number of permutations r of a set n. _nP_r

f) The empty set.

g) Two sets are disjoint.

h) A simple path in a graph.

i) A function from A to B is onto.

j) An Hamilton Circuit.

k) A Geometric sequence.

2. Put the following into symbols (5 points each)

a) Being divisible by 3 is a necessary condition for divisibility by 9

b) Every dog is cute or a good worker.

3. How do you modify the induction technique to prove that a statement is true for all multiples of 5 {0, 5, 10, 15, ...}? (10 points)

4.What is required for an argument form to be valid?(10 points)

5. What is the converse of P -> Q? (5 points)

6. Complete the following induction proofs: (15 points each)

a) pg. 257 #17

b) pg. 266 #10

c) pg. 266 #21

d) pg. 257 #12

7. Complete the following truth tables. (5 points each)

a) ( p v r ) <-> ( q v r)

b) [ p ^ ( ~p v q ) ] -> q

8. Complete the following proof. (10 points)

( ~p v q ) -> r

s v ~q

p -> t

~p -> t

( ~p ^ r ) -> ~s

Therefor ~q

9. Draw the Venn Diagram for the expression (5 points)

( A union B^c ) intersect [( A union B ) - C ]

10. Give an expression for the following Venn Diagram. (5 points)

11. Are the following true or false. Explain. (10 points each)

a) If A is a subset of B then A union C is a subset of B union C

b) For all sets A & B, if for all sets C, C intersect A = C intersect B then A = B.

12. What is the power set of the set { 0, {0}, {1}, {} }? (10 points)

13. Show that each of the following is false. Explain. (10 points each)

a) If A is a subset of B then A intersect ( B intersect C)^c is not empty.

b) If A is a subset of B then A^c is a subset of B^c.

14. If you roll a pair of dice then what is the chance that the sum is under 5? (10 points)

15. Given a set of 16 parents, in how many ways can 2 coaches, 3 assistant coaches, and a score keeper be chosen? (10 points)

16. If 5 boards out of 20 are bad, what is the chance that a sample of six will have at least 3 bad boards? (10 points)

17. How many distinct letter sequences can be made using each of the letters in the word MISUNDERSTANDINGS once? (5 points)

18. Given a standard 52 card deck, how many different 5 card hands are there with three of a kind ( XXXYZ)? ( 10 points)

19. Draw a graph with the following adjacency matrix. (10 points)

1	0	1	2
0	0	1	0
0	2	1	2
0	1	1	0

20. Give all of the values of n such that a complete graph with n vertices has an Euler Circuit. ( 5 points)

21. Draw a graph with 8 vertices that has an Euler Path but does not have an Euler CIrcuit. (5 points)

22. Draw a complete graph with 6 vertices. (5 points)

23. Draw a complete bipartite 3, 2 graph. (5 points)

24. Explain the differences between the following (5 points each)

a) Closed Path & Simple Path.

b) Walk & Path.

25. Are the following graphs isomorphic. If yes show the mapping. If no show the property.

26. Describe how to find the number of paths of length 6 from vertex 3 to vertex 9. (10 points)

27. Draw a forest with 4 trees. (5 points)

28. Describe how to find a minimal spanning tree for the following graph. (20 points)

29. Explain why the set of fractions a/b with b not 0 with the following relation is or is not an equivalence relation. (10 points)

a/b R c/d iff a*c = b*d

30. Find a formula for each of the following recursive sequences. ( 10 points each)

a) a₁ = 2, k over 1 a_k = 2 a_k-1 + 3

b) a₁ = 2, a₂ = 4, for k over 2 use a_k = 2 a_k-1 - a_k-2

c) a₀ = 0, a₁ = 1, for k over 1 use a_k = 5 a_k-1 - 6 a_k-2

31. Show that the following is an equivalence relation and give the equivalence classes. ( 20 points)

On the positive integers _mR_n iff 4 | (m-n)

32. Does symmetric & transitive guarantee reflexive? Why? Explain. (10 points)

33. What are the requirements for a function to have an inverse? Why is each of the requirements needed? (10 (points)