Discrete Mathematics for Computer Science

Special Types of Relations 177 erides level, and so on. This is a transitive closure operation: including one test triggered inc ...

178 CHAPTER 3 Relations input for both gates g and h. Otherwise, when two lines cross, such as the output line of h and the outp ...

Exercises 179 (d) IsSiblingOfOrEquals on the set of all people (e) IsCousinOfOrEquals on the set of all people Prove your assert ...

180 CHAPTER 3 Relations R = {(1, 2), (2, 3), (3, 4)} (a) Find the reflexive closure of R. (b) Find the symmetric closure of R. ( ...

Equivalence Relations 181 rnEquivalence Relations Equivalence relations generalize the familiar relation of equality (=). More s ...

182 CHAPTER 3 Relations Symmetric: If n =-m(mod p), then (n - m) = pk for some k e Z. So, (m - n)= p(-k), giving m =- n(mod p). ...

Equivalence Relations 183 Example 5. (a) On R, define x - y if Ix - y I < 0.01. Then, -' is reflexive and symmetric, but it i ...

184 CHAPTER 3 Relations Definition 4. Let -be an equivalence relation on a set X. For any x e X, let [x] = {y •X :x -y} [x ] is ...

Equivalence Relations 185 Solution. The equivalence classes are [10 of Hearts] = {10 of Hearts, King of Hearts) [King of Hearts] ...

186 CHAPTER 3 Relations Proof (a) First, prove that - is an equivalence relation. Reflexive: Let x c X, and show that x - x. Sin ...

Equivalence Relations 187 D C P S a i II He a I a b d e o n ii rt s s d s S I I Figure 3.9 Equivalence classes of SameSuit (dash ...

188 CHAPTER 3 Relations Application: UNION-FIND The UNION-FIND algorithm has a set of elements X and a relation R defined on X a ...

Exercises 189 Determine which of the following five relations defined on Z are equivalence relations: (a) {(a,b) E Z x Z: (a & ...

190 CHAPTER 3 Relations Prove Theorem 4. There is an old, fallacious proof that if a relation is both symmetric and transitive, ...

Ordering Relations 191 Ordering Relations In this section, we discuss two very important classes of relations, the partial order ...

192 CHAPTER 3 Relations {0,1,2} {0,1,31 10,2,31 {1,2,31 {0} {1} {2) (3) Figure 3.12 Odd subsets of {0, 1, 2, 3}. Example 3. (a) ...

Ordering Relations 193 8 12 (^4 6 10) \ 2 3' 5 7 11 Figure 3.14 Divides for {0, 1,2,..., 121. Example 6. Let X be a collection o ...

194 CHAPTER 3 Relations Solution. We must show that R is reflexive, antisymmetric, and transitive. Reflexive: Let U, V C X. If U ...

Ordering Relations 195 Solution. Given two words, we will say that the one occurring first in the dictionary is less than (<) ...

196 CHAPTER 3 Relations 3.8.3 Comparable Elements Definition 3. Let R be a partial or linear ordering on a set X. Elements x, y ...