Assignment 1

Discrete Math Review

1. Given A={1,2,3} and B={a,b} Find

  1. A X B
  2. B X A
  3. B X B

2. Given A = {1,2} B = {a,b,c} C = {c,d } Find

  1. (A X B) Ç (A X C)
  2. A X (B X C)

3. Given A = {1,2,3,4} and B = {x,y,z}. Consider the following relation from A to B:

R = {<1,y>, <1,z>, <3,y>, <4,x>, <4,z>}
  1. Determine the matrix of the relation R.
  2. Draw the directed graph of R
  3. Find R-1
  4. Determine the domain and range of R.

4. Give examples of relations R on A = {1, 2, 3} having the stated property.

  1. R is both symmetric and anti-symmetric
  2. R is neither symmetric nor anti-symmetric
  3. R is transitive but R È R-1 is not transitive

5. Given A = {1, 2, 3, 4}. Consider the following relation in A:

R = {<1,1>, <2,2>, <2,3>, <3,2>, <4,2>, <4,4>}
  1. Draw the directed graph of R.
  2. Explain: Is R 1) reflexive 2) symmetric 3) transitive 4) anti-symmetric?

6. Let X = {1,2,3,4}. Determine whether or not each relation below is a function from X to X.

  1. f = {<2,3>, <1,4>, <2,1>, <3,2>, <4,4>}

  2. g = {<3,1>, <4,2>, <1,1>}

  3. h= {<2,1>, <3,4>, <1,4>, <2,1>, <4,4>}

7. Classify the functions below (injective, surjective, bijective):

    a. N = { 0, 1, 2, …}

        f: N -> N

    f(x) = x + x

    b. f : Z -> N

        f(n) = |n|

8.  Consider a binary relation (for example: has_child(x,y)) defined on a set of humans that forms a tree structure.  What are the properties of a relation that impose a tree structure on a set?