Discrete Math

Math 221 questions attached!

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

(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?