Page 654 - Discrete Mathematics and Its Applications

Key Terms and Results 633

66. Schedule the tasks needed to build a house, by specifying 67. Find an ordering of the tasks of a software project if the
their order, if the Hasse diagram representing these tasks Hasse diagram for the tasks of the project is as shown.
is as shown in the figure.
Completion
Completion β test
Interior fixtures
Exterior fixtures
α test
Carpeting Interior painting
Develop module A Integrate modules
Flooring Exterior painting Develop module B
Write
Wall-board documentation Develop module C
Plumbing Wiring
Exterior siding Develop system Set up
Roof requirements test sites
Framing Write functional requirements
Foundation
Determine user needs

Key Terms and Results

TERMS closure of a relation R with respect to a property P: the re-
lation S (if it exists) that contains R, has property P, and
binary relation from A to B: a subset of A × B
relation on A: a binary relation from A to itself (i.e., a subset is contained within any relation that contains R and has
property P
of A × A)
S ◦ R: composite of R and S path in a digraph: a sequence of edges (a, x 1 ), (x 1 ,x 2 ),...,
R −1 : inverse relation of R (x n−2 ,x n−1 ), (x n−1 ,b)suchthattheterminalvertexofeach
n
R : nth power of R edge is the initial vertex of the succeeding edge in the se-
reflexive: a relation R on A is reflexive if (a, a) ∈ R for all quence
a ∈ A circuit (or cycle) in a digraph: a path that begins and ends at
symmetric: a relation R on A is symmetric if (b, a) ∈ R when- ∗ the same vertex
ever (a, b) ∈ R R (connectivity relation): the relation consisting of those
antisymmetric: a relation R on A is antisymmetric if a = b ordered pairs (a, b) such that there is a path from a to b
whenever (a, b) ∈ R and (b, a) ∈ R equivalence relation: a reflexive, symmetric, and transitive
transitive: a relation R on A is transitive if (a, b) ∈ R and relation
(b, c) ∈ R implies that (a, c) ∈ R equivalent: if R is an equivalence relation, a is equivalent to
b if aRb
n-ary relation on A 1 ,A 2 ,...,A n : a subset of A 1 × A 2 ×
[a] R (equivalence class of a with respect to R): the set of all
··· × A n
relational data model: a model for representing databases us- elements of A that are equivalent to a
ing n-ary relations [a] m (congruence class modulo m): the set of integers con-
primary key: a domain of an n-ary relation such that an n- gruent to a modulo m
tuple is uniquely determined by its value for this domain partition of a set S: a collection of pairwise disjoint nonempty
subsets that have S as their union
composite key: the Cartesian product of domains of an n-ary partial ordering: a relation that is reflexive, antisymmetric,
relation such that an n-tuple is uniquely determined by its and transitive
values in these domains poset (S, R): a set S and a partial ordering R on this set
selection operator: a function that selects the n-tuples in an comparable: the elements a and b in the poset (A, ) are
n-ary relation that satisfy a specified condition comparable if a b or b a
projection: a function that produces relations of smaller de- incomparable: elements in a poset that are not comparable
gree from an n-ary relation by deleting fields total (or linear) ordering: a partial ordering for which every
join: a function that combines n-ary relations that agree on pair of elements are comparable
certain fields totally (or linearly) ordered set: a poset with a total (or linear)
directed graph or digraph: a set of elements called vertices ordering
and ordered pairs of these elements, called edges well-ordered set: a poset (S, ), where is a total order
loop: an edge of the form (a, a) and every nonempty subset of S has a least element