COT3100 Spring 2001 Practice problems for the test 2 Relations 1 Let A 1 2 3 B w x y z and C 4 5 6 Define the relation R A B S B C and T B C where R 1 w 3 w 2 x 1 y S w 5 x 6 y 4 y 6 and T w 4 w 5 y 5 a Determine R S T and R S R T S T w 4 w 5 x 6 y 4 y 5 y 6 R S T 1 4 1 5 1 6 2 6 3 4 3 5 R S 1 4 1 5 1 6 2 6 3 5 R T 1 4 1 5 3 4 3 5 R S R T 1 4 1 5 1 6 2 6 3 4 3 5 b Determine R S T and R S R T S T w 5 R S T 1 5 3 5 R S R T 1 4 1 5 3 5 2 Consider the relation T over real numbers T a b a2 b2 1 Define all properties of this relation reflexive irreflexive symmetric anti symmetric and transitive Not reflexive for example a 0 5 a a T Not irreflexive a 1 2 a a T Symmetric for any real a b a b T b a T because a2 b2 1 b2 a2 1 Not anti symmetric counterexample 0 1 T and 1 0 T Not transitive counterexample 0 1 T 1 0 T but 0 0 T 3 Let R A A be a symmetric relation Prove that t R is symmetric Proof Assume R A A is symmetric To prove that t R is symmetric we need to show that if a b t R then b a t R So pick arbitrary a b t R 1 By the definition of transitive closure 1 implies that there is a path from a to b in R By the definition of a path it means that there are some elements a0 a a1 a2 an b A such that a0 a1 a1 a2 an 1 an R But since R is symmetric by assumption all inverted pairs belong to R as well i e an an 1 a2 a1 a1 a0 R It signifies that R contains the path from an b to a0 a By the definition of the transitive closure it implies that b a t R 4 Prove or disprove the following propositions about arbitrary relations on A a R1 R2 symmetric R1 R2 is symmetric Proof Assume R1 and R2 are symmetric To prove that R1 R2 is symmetric we need to show that if a b R1 R2 then b a R1 R2 So take arbitrary a b R1 R2 It implies that either a b R1 or a b R2 In the first case a b R1 implies b a R1 by symmetric property of R1 and b a R1 R2 by the union property In the second case a b R2 implies b a R2 by symmetric property of R2 and then b a R1 R2 by the union property So in both cases we showed that b a R1 R2 is implied b R1 R2 transitive R1 R2 is transitive Proof Assume R1 and R2 are transitive To prove that R1 R2 is transitive we need to show that if a b R1 R2 and b c R1 R2 then a c R1 R2 So assume that a b R1 R2 1 and b c R1 R2 2 By the intersection definition we can imply from 1 that a b R1 and a b R2 Similar we can imply from 2 that b c R1 and b c R2 Then by the transitive property of R1 we have that a c R1 3 and similar from the transitive property of R2 we have that a c R2 4 3 and 4 imply that a c R1 R2 by the definition of intersection QED 5 Prove or disprove that for any relation R A A ts R st R The following counterexample can be used to disprove that ts R st R Take A 1 2 3 R 1 2 2 3 then st R 1 2 2 1 2 3 3 2 1 3 3 1 ts R 1 2 2 1 2 3 3 2 1 3 3 1 1 1 2 2 3 3 is not a subset of st R since 1 1 ts R and 1 1 st R 6 Let R be a symmetric and transitive relation on set S Furthermore suppose that for every x S there is an element y S such that xRy Prove that R is equivalence relation Proof Assume R is a symmetric and transitive relation on set S and for every x S there is an element y S such that xRy To prove that R is equivalence relation we need to prove that R is also reflexive i e for every x S xRx Take any x S then by assumption there exists an element y S such that xRy By symmetric property of R xRy implies yRx By transitive property of R xRy and yRx imply xRx So we proved that for any x S xRx 5 Prove that a relation R on a set A is transitive if and only if R2 R We need to prove i if R is transitive then R2 R and ii if R2 R then R is transitive i assume that R is transitive To prove that R2 R we need to show that if a b R2 then a b R So take any a b R2 By the definition of R2 as a composition R with itself it implies that there exists some x A such that a x R and x b R By the transitive property of R a x R and x b R imply a b R QED ii assume that R2 R To prove that R is transitive we need to show that if a x R and x b R then a b R So assume that a x R and x b R Then by the definition of composition a b R R R2 Since R2 R by assumption a b R2 results in a b R QED 6 Determine whether the relation represented by the directed graph is reflexive irreflexive symmetric anti symmetric and transitive b a The relation is not reflexive because c c R d R is not irreflexive because it contains some loops R is symmetric R is not anti symmetric c R is not transitive because c b R and b c R but c c R 7 Let A denote an arbitrary non empty set and let R denote a binary relation R A A Answer the following two parts independently of each other a Suppose R is transitive Prove that the inverse relation R 1 is also transitive where R 1 is defined as R 1 a b b a R We need to show that if a b R …
View Full Document
Unlocking...