Exercises 179
(d) IsSiblingOfOrEquals on the set of all people
(e) IsCousinOfOrEquals on the set of all people
Prove your assertions.
- Since relations are sets, it is possible to define union, intersection, relative complement,
and absolute complement on pairs of relations. A natural question is which properties
of the original relations still hold for the resulting new relation. Fill in the following
table with Y/N, representing YES and NO, respectively. If the entry is N, find an
example that shows the property is not preserved under the operation. For instance,
enter a Y in the first row, second column, if the intersection of two reflexive relations
is still reflexive; otherwise, enter an N.
Relative Absolute
Union Intersection Complement Complement
Reflexive
Irreflexive
Symmetric
Antisymmetric
Transitive
- Let A = {a, b, c, d}. Define the relations R 1 and R 2 on A as
R= {(a, a), (a, b), (b, d)}
and
R2 = {(a, d), (b, c), (b, d), (c, b)}
Find
(a) R 1 o R2
(b) R 2 o RI
(c) R
2
(d) R2
- Find a set A with n elements and a relation R on A such that R^1 , R2.. R are all
distinct.
- In the example involving the family tree (see Figure 3.2);
(a) What is the transitive and reflexive closure of IsParentOf?
(b) What is the transitive and reflexive closure of IsMarriedTo?
- Let X = {a, b, c, d, e}. Let R, be the relation on X with elements {(a, b), (a, c), (d,
e)}. Let R 2 be the relation on X with elements {(a, b), (b, c), (c, d), (d, e), (e, a)}. For
each of these relations, find the following:
(a) The smallest relation on X that contains R and is reflexive
(b) The smallest relation on X that contains R and is symmetric
(c) The smallest relation on X that contains R and is transitive
(d) The smallest relation on X that contains R and is reflexive and transitive
- Let X = {1, 2, 3, 4}, and define a relation R on X as
