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.
