Math 220: Discrete Mathematics
Final Exam
Attempt all problems. Show all of your work.
No notes, textbooks, calculators, or outside help may be used on this exam.
1. (5 points) Draw a truth table to show that the statement P ∨(Q∧ ∼ P ). is equivalent
to the statement P ∨ Q.
2. (5 points) Give the negation of the following statement P :
∀r ∈ R, (r > 0 ⇒ (∃n ∈ N such that 1/n < r)).
3. (5 points) Prove that
1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1
for all natural numbers n.
4. (5 points) Show that 6|(7n − 1) for all n ∈ N.
5. (10 points) Show that the product of a nonzero rational number and an irrational
number is irrational.
6. (10 points) Define a function f : R → R by:
x − 2
f (x) = x − 4
1
if x 6= 4
.
if x = 4
Show that f is a bijection.
7. (10 points) Let S be the power set of {1, 2, 3}
(a) Determine which one of the following two relations is not an equivalence relation. (You only need to explain why your selection is not an equivalence
relation. You are not required to explain why the other one is an equivalence
relation.)
i. AR1 B iff A ∩ B 6= ∅.
ii. AR2 B iff |A| = |B|.
(b) For the relation above that is an equivalence relation, find the associated partition of S into equivalence classes.
1 8. (10 points) Let A = R × R and let R be the relation on A given by (a, b)R(c, d) iff
either a < c or else we have both a = c and b ≤ d.
(a) Show that R is a partial order.
(b) Determine whether or not R is a total order.
9. (10 points) The graph below represents a group of computers in a dorm, and the
distance between them. We would like to network them, using the least amount of
wire possible.
A
2
14
E
5
10
8
10
I
B
11
17
F
3
11
20
C
G
15
12
10
J
9
K
D
H
18
6
L
Use Kruskal’s Algorithm to find a minimal spanning tree on the graph shown above.
(Please clearly highlight which edges you use and circle the numbers on those edges.)
Find the amount of wire used in the resulting network.
10. (10 points) Find an Eulerian circuit on the graph below, indicating your path by
drawing arrows and numbering the edges in the order that you traverse them.
A
D
B
E
C
F
G
H
Write down the row corresponding to the vertex E in the adjacency matrix for the
graph above. (Please order the vertices in alphabetical order.)
2 11. (20 points) For the following probability questions, you only need to set up the
correct expression. You do not need to simplify your answers.
(a) A committee of 7 is to be chosen from a group of 5 Republicans, 6 Democrats,
and 4 Independents. Find the probability that at least one person from each
political affiliation is included.
(b) Find the probability that a random arrangement of the letters of
ABRACADABRA begins with ABCD.
(c) Two fair dice are rolled and your score is determined by the number facing up
which is the greater of the two. Thus if you roll a 3 and a 2, your score is 3,
and if you roll a pair of 3s your score is still 3. Find the probability that your
score is odd.
(d) 5 cards are dealt from a standard 52 deck of cards. (Recall that this deck can
be divided into 4 suits (♥, ♦, ♣, ♠) and into 13 ranks (2−10, J, Q, K, A).) Find
the probability that it contains 4 of a kind (i.e. 4 cards of the same rank).
(e) Three kids find a cluster of 15 quarters that have fallen on the ground and
each attempts to pick up as many as they can (rushing to grab them before
the others do). Find the probability that each child gets at least 2 quarters.
3