Discrete Mathematics for Computer Science

CH H AH PI TH EI iRa 3 l I Relations Human language has many words and phrases to describe relationships between or among object ...

158 CHAPTER 3 Relations Table 3.1 SpecialDeck of Cards SpecialDeck 10 of Clubs Jack of Clubs King of Clubs 10 of Hearts Jack of ...

Binary Relations 159 Definition 1. A binary relation is a set of ordered pairs. A binary relation on a set X is a set of ordered ...

160 CHAPTER 3 Relations Other familiar examples of relations arise when we consider family trees. Tradition- ally, a special not ...

Binary Relations 161 Table 3.5 IsMarriedTo Relation IsMarriedTo John Mary Mary John Peter Elaine Elaine Peter Maude Harold Harol ...

162 CHAPTER 3 Relations Similar relations are defined on N and R. When the set X is clear from the context, the subscript X will ...

Operations on Binary Relations 163 For three distinct positions on the board, define the relation Between to consist of the or- ...

164 CHAPTER 3 Relations (x, y) E < if and only if (y, x) E > The formalization of this property is stated next. Definition ...

Operations on Binary Relations 165 Hence, (R U S)-^1 - R-^1 U S-1 (c) This proof is left as an exercise for the reader. 0 3.2.2 ...

166 CHAPTER 3 Relations Exercises For the people in the family tree (see Figure 3.2), build tables for the following rela- tion ...

Special Types of Relations 167 (a) LeN o LeN (b) Le.' (c) LtDRo LtR (d) Challenge: LtN o LtN (e) Challenge: LtD o GtN (f) Let Ne ...

168 CHAPTER 3 Relations 3.4.1 Reflexive and Irreflexive Relations Clearly, 3 < 3 is true, but 3 < 3 is not true. This dist ...

Special Types of Relations 169 The difference between < and < that we have discussed is formalized in Definition 2. Defini ...

170 CHAPTER 3 Relations One can see that a binary relation on R is symmetric if and only if its graph is sym- metric about the d ...

Special Types of Relations 171 Definition 4. Let R be a binary relation on a set X. R is antisymmetric if (y, x) 0 R whenever (x ...

172 CHAPTER 3 Relations (b) For any set X, the empty relation 0 is a symmetric, antisymmetric, and irreflexive relation on X. If ...

Special Types of Relations 173 Theorem 4. A binary relation R is transitive if and only if R o R C R. Proof This just restates t ...

174 CHAPTER 3 Relations Definition 6. Let R be a binary relation on a set X. For n E N, the nth power of R, denoted R', is defin ...

Special Types of Relations 175 Theorem 5. Let R be a binary relation on a set X. Then: (a) R U Idx is the smallest reflexive rel ...

176 CHAPTER (^3) Relations Example 13. Consider the relation Supervises in some business. The relation is usually irreflexive, t ...