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)
RZ+ 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?

Still stressed with your coursework?
Get quality coursework help from an expert!