5.1_Relations_and_their_Properties5.2n-ary_relations.pptVIP

? ? (R1 - R2) -1 = R1 -1 - R2 -1 ? If R1 í R2 then R1-1 í R2 -1 Example Show that (R1 è R2) -1 = R1 -1 è R2 –1 Proof: Let (x,y)? (R1 è R2) -1 ? (y, x)? (R1 è R2) ? (y, x)? R1 ?(y, x)? R2 ? (x, y)? R1-1 ?(x, y)? R2-1 ? (x, y)? (R1-1 è R2-1) Example Show that (R1 - R2) -1 = R1 -1 - R2 -1 Proof: Let (x,y)? (R1 - R2) -1 ? (y, x)? (R1 - R2) ? (y, x)? R1 ?(y, x)? R2 ? (x, y)? R1-1 ?(x, y) ? R2-1 ? (x, y)? (R1-1 - R2-1) CompositionDefinition: Suppose? R1 is a relation from A to B? R2 is a relation from B to C.Then the composition of R2 with R1, denoted R2oR1 is the relation from A to C:If x, y is a member of R1 and y, z is a member of R2 then x, z is a member of R2oR1.__________________ Note: For x, z to be in the composite relation R2oR1 there must exist a y in B, and x, y is a member of R1 and y, z is a member of R2 . . . .Note: We read them right to left as in functions._________________Example: R={(1,1), (1,4), (2,3), (3,1), (3,4)} S={(1,0), (2,0), (3,1), (3,2), (4,1)} S?R ={(1,0), (1,1), (2,1), (2,2), (3,0),(3,1)} Think: R ? S =? _______________ Example If F，G are relations on set N， F={(x,y)|x,y ?N ? y=x2},G= {(x,y)|x,y ?N ? y=x+1} For arbitrary x?N, FoG= {(x,y)|x,y ?N ? y= (x+1)2} GoF= {(x,y)|x,y ?N ? y= x2+1} FoG ? GoF Example Let R、S、P be relations，then (RoS)oP=Ro(SoP) Proof: Let (x,w) ? (RoS)oP ??z[(x,z) ? P ?(z,w) ? (RoS)) ?z ?y[(y,w)?R ? (x,z) ?P ?(z,y) ?S] ?y[(y,w)?R ? (x,y) ?SoP] (x,w) ? Ro(SoP) Therefore: (RoS)oP=Ro(SoP) Example Let R1 and R2 be relations from A to B. If A = B, then (R1oR2) -1 = R2-1o R1-1 Proof: Let (x,y) ?(R1oR2)-1 ? (y,x) ?R1oR2 ? ?z((y,z) ? R2 ?(z,x) ? R1 ) ? ?z((z,y) ? R2-1 ?(x, z) ? R1-1) ? (x,y) ?R2-1 oR1-1 Let F,G and H be relations,then (1) Fo(G?H)= FoG ? FoH (2) Fo(G?H)? FoG? FoH (3) (G?H) oF = (GoF ) ? (HoF) (4) (G?H) oF? GoF? HoF Think: how to prove them? Sho