Discrete Math
7.1
5. For each of the following relations, determine whether the
relation is reflexive, symmetric, antisymmetric, or transitive.
a) R ⊆ Z+ X Z+ where a R b if a|b (read “a divides b,”
as defined in Section 4.3).
b) R is the relation on Z where a R b if a|b.
c) For a given universe U and a fixed subset C of U, define
R on P(U) as follows: For A, B ⊆ U we have A R B if
A ∩ C = B ∩ C.
d) On the set A of all lines in R2, define the relation R for
two lines L1, L2 by L1 R L2 if L1 is perpendicular to L2.
e) R is the relation on Z where x R y if x + y is odd.
f ) R is the relation on Z where x R y if x − y is even.
g) Let T be the set of all triangles in R2. Define R on T by
t1 R t2 if t1 and t2 have an angle of the same measure.
h) R is the relation on Z x Z where (a, b) R (c, d) if a ≤ c.
[Note: R ⊆ ( Z x Z ) X ( Z x Z ).]
6. Which relations in Exercise 5 are partial orders? Which are
equivalence relations?
7.2
18. For A = {v, w, x, y, z}, each of the following is the (0, 1)-
matrix for a relation R on A. Here the rows (from top to bottom)
and the columns (from left to right) are indexed in the
order v, w, x, y, z. Determine the relation R ⊆ A x A in each
case, and draw the directed graph G associated with R.
a) M(R) = 0 1 1 0 0
1 0 1 1 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0
b) M(R) = 0 1 1 1 0
1 0 1 0 0
1 1 0 0 1
1 0 0 0 1
0 0 1 1 0
7.3
20. For X = {0, 1}, let A = X x X. Define the relation R
on A by (a, b) R (c, d) if (i) a <c; or (ii) a = c and b ≤ d.
(a) Prove that R is a partial order for A. (b) Determine all minimal
and maximal elements for this partial order. (c) Is there
a least element? Is there a greatest element? (d) Is this partial
order a total order?
7.4
4. For A = {1, 2, 3, 4, 5, 6}, R = {(1, 1), (1, 2), (2, 1), (2, 2),
(3, 3), (4, 4), (4, 5), (5, 4), (5, 5), (6, 6)} is an equivalence relation
on A. (a) What are [1], [2], and [3] under this equivalence
relation? (b) What partition of A does R induce?
8.1
1. Let S be a finite set with |S| = N and let c1, c2, c3, c4 be
four conditions, each of which may be satisfied by one or more
of the elements of S. Prove that N(c2c3c4) = N(c1c2c3c4) +
N(c1c2c3c4).
12. In how many ways can Troy select nine marbles from a bag
of twelve (identical except for color), where three are red, three
blue, three white, and three green?
8.2
4. Let A = {1, 2, 3, . . . , 10}, and B = {1, 2, 3, . . . , 7}. How
many functions f : A→B satisfy |f (A)| = 4? How many have
|f (A)| ≤ 4?
5. In how many ways can one distribute ten distinct prizes
among four students with exactly two students getting nothing?
How many ways have at least two students getting nothing?