Discrete Mathematics for Computer Science

Chapter Review 213

property. Focusing on reflexive, symmetric, and transitive relations leads to equivalence

relations and partitions. Focusing on antisymmetric and transitive relations leads to par-

tial and total orders. When discussing ordering relations, it is important to understand the

notion of comparable elements. Special comparable elements include minimal, minimum,

maximal, and maximum elements. Finally, the chapter deals with relations in the context

of the operations that are used by a relational database.

Applications in this chapter include lexicographical or dictionary ordering, finding a

minimal element, and embedding a partial order in a total order. The examples dealing with

relational databases point out the operations that are used for processing queries in such a

database.

3.12.1 Summary

3.1 and 3.2 Summary

TERMS

binary relation n-tuples

composition property

deck of 52 cards query

empty relation relations

equality relation ternary relation

family tree trivial relation

identity relation unary relation

inverse universal relation

irreflexiv void relation

n-ary relation

3.4 Summary

TERMS
antisymmetric reflexive closure
graph reflexive and transitive closure
irreflexive symmetric
nth power of R symmetric closure
R + transitive
R* transitive closure
reflexive

THEOREMS

"A relation R on a set X is reflexive if and The reflexive closure of a relation R on a

only if IDx C R. set X is R U IDx.

"A relation R on a set X is irreflexive if and The symmetric closure of a relation R on a

only if R n Idx = 0. set X is R U R-^1.

"A relation R on a set X is symmetric if and The transitive closure of a relation R on a

only if R = R-1. set X is R+.

"A relation R on a set X is transitive if and The reflexive and transitive closure of a

only if R o R C R. relation R on a set X is R*.