Page 655 - Discrete Mathematics and Its Applications

634 9 / Relations

lexicographic order: a partial ordering of Cartesian products compatible total ordering for a partial ordering: a total or-
or strings dering that contains the given partial ordering
Hasse diagram: a graphical representation of a poset where topological sort: the construction of a total ordering compat-
loops and all edges resulting from the transitive property ible with a given partial ordering
are not shown, and the direction of the edges is indicated
by the position of the vertices RESULTS
maximal element: an element of a poset that is not less than
any other element of the poset The reflexive closure of a relation R on the set A equals R ∪ ,
minimal element: an element of a poset that is not greater than where ={(a, a) | a ∈ A}.
any other element of the poset The symmetric closure of a relation R on the set A equals
greatest element: an element of a poset greater than all other R ∪ R −1 , where R −1 ={(b, a) | (a, b) ∈ R}.
elements in this set The transitive closure of a relation equals the connectivity re-
least element: an element of a poset less than all other elements lation formed from this relation.
in this set Warshall’s algorithm for finding the transitive closure of a re-
upper bound of a set: an element in a poset greater than all lation
other elements in the set Let R be an equivalence relation. Then the following three
lower bound of a set: an element in a poset less than all other statements are equivalent: (1) aRb; (2) [a] R ∩[b] R =∅;
elements in the set (3) [a] R =[b] R .
least upper bound of a set: an upper bound of the set that is The equivalence classes of an equivalence relation on a set A
less than all other upper bounds form a partition of A. Conversely, an equivalence relation
greatest lower bound of a set: a lower bound of the set that canbeconstructedfromanypartitionsothattheequivalence
is greater than all other lower bounds classes are the subsets in the partition.
lattice: a partially ordered set in which every two elements The principle of well-ordered induction
have a greatest lower bound and a least upper bound The topological sorting algorithm

Review Questions

1. a) What is a relation on a set? c) How can the 4-ary relation containing names of stu-
b) How many relations are there on a set with n elements? dents, their addresses, telephone numbers, and majors
and the 4-ary relation containing names of students,
2. a) What is a reflexive relation? their student numbers, majors, and numbers of credit
b) What is a symmetric relation? hours be combined into a single n-ary relation?
c) What is an antisymmetric relation? 6. a) Explain how to use a zero–one matrix to represent a
relation on a finite set.
d) What is a transitive relation?
b) Explain how to use the zero–one matrix representing a
3. Give an example of a relation on the set {1, 2, 3, 4} that is
relation to determine whether the relation is reflexive,
a) reflexive, symmetric, and not transitive. symmetric, and/or antisymmetric.
b) not reflexive, symmetric, and transitive. 7. a) Explain how to use a directed graph to represent a re-
c) reflexive, antisymmetric, and not transitive. lation on a finite set.
d) reflexive, symmetric, and transitive. b) Explain how to use the directed graph representing a
relation to determine whether a relation is reflexive,
e) reflexive, antisymmetric, and transitive.
symmetric, and/or antisymmetric.
4. a) How many reflexive relations are there on a set with n
elements? 8. a) Define the reflexive closure and the symmetric closure
of a relation.
b) How many symmetric relations are there on a set with b) How can you construct the reflexive closure of a rela-
n elements?
tion?
c) How many antisymmetric relations are there on a set c) How can you construct the symmetric closure of a re-
with n elements? lation?
5. a) Explain how an n-ary relation can be used to represent d) Find the reflexive closure and the symmetric closure
information about students at a university. of the relation {(1, 2), (2, 3), (2, 4), (3, 1)} on the set
{1, 2, 3, 4}.
b) How can the 5-ary relation containing names of stu-
dents, their addresses, telephone numbers, majors, and 9. a) Define the transitive closure of a relation.
grade point averages be used to form a 3-ary relation b) Can the transitive closure of a relation be obtained by
containing the names of students, their majors, and including all pairs (a, c) such that (a, b) and (b, c) be-
their grade point averages? long to the relation?