## Description

Question 1: Family Issues

Mary has two kids, Peter and Robert. Robert has a daughter named Elena, Peter is the

father of Christine and John, and Christine is the mother of Daniel.

a) Write down the relation R = {(a, b) | a is a parent of b} defined on the set P of the

seven people, so that it reflects the family structure specified above. Use the set

notation and the matrix notation.

b) Use the matrix notation as your starting point for computing the transitive closure of

R. Apply the Boolean power method we discussed in class. Once you have derived

the matrix representing the transitive closure of R, also translate it into set notation.

c) What does the transitive closure of R specify? What name could you give it?

Question 2: Count the Relations

For the following questions, list the different relations or orderings and count how many

of them there are.

a) How many different equivalence relations can we define on the set A = {x, y, z}?

b) How many different partial orderings can we define on the set A = {a, b}?

c) How many different total orderings can we define on the set A = {p, q}?

Question 3: Relations

Determine whether the following relations are reflexive, irreflexive, symmetric,

asymmetric, antisymmetric, and/or transitive (no proof necessary):

a) The empty relation R = ∅ defined on the natural numbers.

b) The complete relation R = N×N defined on the natural numbers.

c) The relation R on the positive integers where aRb means a | b (i.e., a divides b).

d) The relation R on the positive integers where aRb means a < b.

e) The relation R on the positive integers where aRb means a ≥ b.

f) The relation R on {w, x, y, z} where R = {(w, w), (w, x), (x, w), (x, x), (x, z), (y, y), (z,

y), (z, z)}.

g) The relation R on the integers where aRb means a2 = b2

.

Question 4: Possible and Impossible Graphs

Do the following graphs exist? If so, draw an example. If not, give a reason for it.

a) A simple graph with 6 vertices, whose degrees are 2, 2, 2, 3, 4, 4.

b) A simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7.

c) A simple graph with 4 vertices, whose degrees are 1, 2, 3, 3.

d) A simple graph with 5 vertices, whose degrees are 2, 3, 4, 4, 4.

e) A simple graph with 4 vertices, whose degrees are 1, 1, 2, 4.

f) A simple digraph with 3 vertices with in-degrees 0, 1, 2 and out-degrees 0, 1, 2.

g) A simple digraph with 3 vertices with in-degrees 1, 1, 1 and out-degrees 1, 1, 1.

h) A simple digraph with 4 vertices with in-degrees 0, 1, 2, 2 and out-degrees 0, 1, 1, 3.

i) A simple digraph with 5 vertices with in-degrees 0, 1, 2, 4, 5 and out-degrees

0, 3, 3, 3, 3.

j) A simple digraph with 4 vertices with in-degrees 0, 1, 1, 2 and out-degrees 0, 1, 1, 1.

Question 5 (Bonus): Equivalent Integers

Let us define the following equivalence relation R on the set S = {2, 3, 4, … 21}: R =

{(a, b) | a and b have the same number of unique prime factors}. For example, 15 and 18

are related under R, because both of them have two unique prime factors (15 = 3·5, 18 =

2·32

).

a) As you know, any equivalence relation partitions the set on which it is defined into

equivalence classes. Write down the partitioning of S by the equivalence relation R.

b) Define an equivalence relation Q on the same set S that partitions it into exactly 10

equivalence classes. Write down the definition of Q and the resulting partitioning of S.