x
Contents
3.2 Operations on Binary Relations 163
3.2.1 Inverses 163
3.2.2 Composition 165
3.3 Exercises 166
3.4 Special Types of Relations 167
3.4.1 Reflexive and Irreflexive Relations 168
3.4.2 Symmetric and Antisymmetric Relations 169
3.4.3 Transitive Relations 172
3.4.4 Reflexive, Symmetric, and Transitive Closures 173
3.4.5 Application: Transitive Closures in Medicine and Engineering 176
3.5 Exercises 178
3.6 Equivalence Relations 181
3.6.1 Partitions 183
3.6.2 Comparing Equivalence Relations 186
3.7 Exercises 188
3.8 Ordering Relations 191
3.8.1 Partial Orderings 191
3.8.2 Linear Orderings 194
3.8.3 Comparable Elements 196
3.8.4 Optimal Elements in Orderings 196
3.8.5 Application: Finding a Minimal Element 198
3.8.6 Application: Embedding a Partial Order 200
3.9 Exercises 201
3.10 Relational Databases: An Introduction 202
3.10.1 Storing Information in Relations 203
3.10.2 Relational Algebra 204
3.11 Exercises 211
3.12 Chapter Review 212
3.12.1 Summary 213
3.12.2 Starting to Review 215
3.12.3 Review Questions 216
3.12.4 Using Discrete Mathematics in Computer Science 217