离散数学课件----EquivalenceII.ppt

* * * * * * * * * * * * 同样,如果能举出例子证明等价式左部为假,则R不是传递的,否则就是传递的 * * * * * * * * * * * * * * * * * * * * * * * * * * * * Intersection Keeping Properties of Relation Reflexivity: ?x, ∵(x,x)? R1, (x,x)?R2, ∴(x,x)?R1?R2 Irreflexivity: supposing ?x, (x,x)?R1?R2, then (x,x)?R1, (x,x)?R2, contradiction. Symmetry: ?x,y, (x,y)?R1?R2 ? (x,y)?R1, (x,y)?R2，since R1 and R2 are symmetric，(y,x)?R1, (y,x)?R2, ∴(y,x)?R1?R2. Antisymmetry: ?x,y, supposing (x,y)?R1?R2, (y,x)?R1?R2, then (x,y), (y,x)?R1, and (x,y), (y,x)?R2, since R1 and R2 are both antisymmetric，x=y Transitivity:?x,y,z, if (x,y)?R1?R2, (y,z)?R1?R2, then (x,y), (y,z)?R1,and (x,y),(y,z)?R2, since R1and R2 are both transitive, (x,z)?R1, and (x,z)?R2, ∴(x,z)?R1?R2 Union Keeping Properties of Relation Reflexivity: ?x, ∵(x,x)?R1, (x,x)?R2, ∴(x,x)?R1?R2 Irreflexivity: supposing that ?x, (x,x)?R1?R2, then (x,x) ?R1 or (x,x)?R2, but R1and R2 are irreflexive Symmetry: ?x,y, if (x,y)?R1?R2, then (x,y)?R1 or (x,y)?R2, without losing generality, let (x,y)?R1，since R1 is symmetric, so, (y,x)?R1?R2 Antisymmetry: counterexample: R1={(a,b)}, R2={(b,a)} Transitivity: counterexample: R1={(a,b)}, R2={(b,a)} Operations on Relations (3) Composition Rule: If R1?A?B, R2?B?C, (A,B,C are sets) then: the composition of R1 and R2, written as R2°R1 is a relation from A to C, and R2°R1={(x,z)|x?A, z?C, and there exists some y?B，such that (x,y)?R1, (y,z)?R2} Composition of Relation (x,z)?R2°R1 if and only if x?A, z?C, and there exists some t?B，such that (x,t)?R1, (t,z)?R2 x t z R1 R2 R2°R1 Composition: Examples Let A={a,b,c,d}, R1, R2 are relations on A： R1 = {(a,a),(a,b),(b,d)} R2 = {(a,d),(b,c),(b,d),(c,b)} then: R2?R1 R1?R2 R1?R1 R2?R2 = {(a,d),(a,c)} = {(c,d)} = {(a,a),(a,b),(a,d)} = {(b,d), (c,c), (c,d)} Power of Composition Rn corresponds the relation defined by the path of length n in Digraph of R. Properties of Relation Composition(1) Associative Law (R3°R2) °R1 = R3°(R2°R1) (where, R1?A?B, R2?B?C, R3?C?D) Proof (x,y)?(R3