Practice problems for the test#2COT3100 Spring’2001Practice problems for the test#2Relations. 1. Let A ={1, 2, 3}, B ={w, x, y, z}, and C = {4, 5, 6}. Define the relation R AB, S BC, and T BC, 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 (RS) (RT).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)}RS = {(1, 4), (1, 5), (1, 6), (2, 6), (3, 5)}, RT = {(1, 4), (1, 5), (3, 4), (3, 5)}(RS)(RT) = {(1, 4), (1, 5), (1, 6), (2, 6), (3, 4), (3, 5)}.b) Determine R (S T ) and (RS) (RT).S T ={(w, 5)}; R (S T ) ={(1, 5), (3, 5)};(RS)(RT) = {(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 AA be a symmetric relation. Prove that t(R) is symmetric. Proof. Assume R AA 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=bA such that (a0, a1), (a1, a2), … (an1, an)R. But since R is symmetric by assumption, all inverted pairs belongto R as well, i. e. (an, an1), …, (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 R1R2 is symmetric.Proof. Assume R1 and R2 are symmetric. To prove that R1R2 is symmetric we need toshow that if (a, b) R1R2, then (b, a) R1R2. So, take arbitrary (a, b) R1R2. 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) R1R2 by the union property. In the second case, (a, b) R2 implies (b, a) R2 by symmetric property of R2, and then (b, a) R1R2 by the union property. So, in both cases we showed that (b, a) R1R2.is implied. b) R1, R2 transitive R1R2 is transitive.Proof. Assume R1 and R2 are transitive. To prove that R1R2 is transitive, we need to show that if (a, b) R1R2 and (b, c) R1R2 then (a, c) R1R2. So, assume that (a, b) R1R2 (1) and (b, c) R1R2 (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) R1R2 by the definition of intersection. QED. 5. Prove or disprove that for any relation R AA 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 xS there is an element yS such that xRy. Prove that R is equivalence relation.Proof. Assume R is a symmetric and transitive relation on set S and for every xS there isan element yS such that xRy. To prove that R is equivalence relation we need to prove that R is also reflexive, i.e. for every xS xRx. Take any xS, then by assumption there exists an element yS 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 xS xRx.5. Prove that a relation R on a set A is transitive if and only if R2R. We need to prove: i) if R is transitive, then R2R. and ii) if R2R. then R is transitive. i) assume that R is transitive. To prove that R2R. 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. QEDii) assume that R2R.. 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) RR =R2. Since R2R 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.The relation is not reflexive because (c, c) R.R is not irreflexive, because it contains some loops.R is symmetric. R is not anti-symmetric. abcdR 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 AA. Answer the following two parts independently of each other:(a) Suppose R is transitive. Prove that the inverse relation R1 is also transitive, where R1 is defined as R1 = {(a, b) | (b, a) R}.We need to show that if (a, b)R1 and (b, c)R1, then (a, c)R1. Assume there are some(a, b)R1 and (b, c)R1 (if not, R1 is transitive and we have nothing to prove). By the definition of inverse relation (a, b)R1 implies (b, a)R and (b, c)R1 implies (c, b)R. By the transitive property of R (c, b)R and (b, a)R imply (c, a)R. By the definition of inverse relation (c, a)R implies (a, c)R1. QED.(b) Suppose R and R is irreflexive (that is, there does not exist any a A suchthat (a, a) R). Prove that either R is not
View Full Document
Unlocking...