第3周起每周一交作业,作业成绩占总成绩的15%; 平时不定期的进行小测验,占总成绩的 1503 期中考试成绩占总成绩的20%;期终考试成绩占总成绩的 50% zhym@fudan.edu.cn 张宓13212010027 fudan. edu,cn BBS id: abchjsabc软件楼103 杨侃10302010007@ fudan,edu,cn 程义婷11302010050 fudan.,edu,cn BBS id: chengyiting 刘雨阳13212010013 fudan. edu,cn,软件楼405 liy(fudan. edu,cn李弋
第3周起每周一交作业，作业成绩占总成绩的15%； 平时不定期的进行小测验，占总成绩的 15%； 期中考试成绩占总成绩的20%；期终考试成绩占总成绩的 50% zhym@fudan.edu.cn 张宓 13212010027@fudan.edu.cn BBS id:abchjsabc 软件楼103 杨侃 10302010007@fudan.edu.cn 程义婷 11302010050@fudan.edu.cn BBS id:chengyiting 刘雨阳 13212010013@fudan.edu.cn，软件楼405 liy@fudan.edu.cn 李弋
2. Composition Definition 2.14: Let r be a relation from a to B, and r be a relation from B to c. The composition of R and r,, we write R,R1, is a relation from a to c. and is defined R,=la, c there exist some beB so that (a,b)∈R1and(b,c)∈R2, where a∈ A and ceo (R, is a relation from A to B, and R, is a relation from b to c (2)commutative law? X R1={(a1,b1),(a2b3),(a1,b2) R2={(b4a1),(b4C1),(b2,a2,(b3C2)
2.Composition Definition 2.14: Let R1 be a relation from A to B, and R2 be a relation from B to C. The composition of R1 and R2 , we write R2 R1 , is a relation from A to C, and is defined R2 R1={(a,c)|there exist some bB so that (a,b)R1 and (b,c)R2 , where aA and cC}. (1)R1 is a relation from A to B, and R2 is a relation from B to C (2)commutative law? R1={(a1 ,b1 ), (a2 ,b3 ), (a1 ,b2 )} R2={(b4 ,a1 ), (b4 ,c1 ), (b2 ,a2 ), (b3 ,c2 )}
Associative law? Forr caB. rcbxc and rccXd R3(R2R1)=(R3R2)R1 subset ofAXd For any(a2d)∈R3(R2R1),(a,d)∈?(R3R2)R1, Similarity,(R3oRyR,ER3(rori Theorem 2.3: Letr be a relation from a to B, R be a relation from b to C, Ra be a relation from c to D. Then R3(R2or=(r3oR)R,(Associative law
Associative law? For R1 A×B, R2B×C, and R3C×D R3 (R2 R1 )=?(R3 R2 )R1 subset of A×D For any (a,d)R3 (R2 R1 ), (a,d)?(R3 R2 )R1 , Similarity, (R3 R2 )R1R3 (R2 R1 ) Theorem 2.3：Let R1 be a relation from A to B, R2 be a relation from B to C, R3 be a relation from C to D. Then R3 (R2 R1 )=(R3 R2 )R1 (Associative law)
Definition 2. 15: Let r be a relation on A, and neN. The relation Rn is defined as follows (1)RO=(a, a)laEA)), we write IA (2R叶+=RRn, Theorem 2, 4 Let r be a relation on A. and m,n∈N.Then (RmoR=Rmtn (2)(Rm=Rmm
Definition 2.15: Let R be a relation on A, and nN. The relation Rn is defined as follows. (1)R0 ={(a,a)|aA}), we write IA . (2)Rn+1=RRn . Theorem 2.4: Let R be a relation on A, and m,nN. Then (1)RmRn=Rm+n (2)(Rm) n=Rmn
A={a1,a2,…,anB,B={b1,b2…,bm I and kg be relations from A to B R RIX i, mR2=(i M RIUR2(X MRnR2=(xr∧y) V01∧01 001000 111101 Example:A={2,3,4},B={1,3,5,7 R1={(2,3),(2,5),2,7),(3,5)、3,7),(45),(4,7) R2={(25)3,3),(4,1)4,7) Inverse relation R- of R: Mp-=M., MpT is the transpose of M R
A={a1 ,a2 ,,an },B={b1 ,b2 ,,bm} R1 and R2 be relations from A to B. MR1=(xij), MR2=(yij) MR1∪R2=(xijyij) MR1∩R2=(xijyij) 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 Example:A={2,3,4},B={1,3,5,7} R1={(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7)} R2={(2,5),(3,3),(4,1),(4,7)} Inverse relation R-1 of R : MR-1=MR T , MR T is the transpose of MR
A={a1;a2,…,an3,B={b1,b2,…,bm}, C={c1,C2,,}, Ri be a relations from a to B, MRi(Xi )mxn, R2 be a relation from b to c. m R2 (y )nyr The n r composition R2r, ofr and r22 MRoR-((Xk Ayn)
A={a1 ,a2 ,,an },B={b1 ,b2 ,,bm }, C={c1 ,c2 ,,cr }, R1 be a relations from A to B, MR1=(xij)mn , R2 be a relation from B to C, MR2=(yij) nr . The composition R2 R1 of R1 and R2 , i k kj m r n k R R M x y = = (( )) 1 2 1
Example: R=((a, b),(b, a),(a, c), is not symmetrIc +(c,a)→>R={(a,b),(b,a)2(a2C),(c,a)},R Is symmetric Closure
Example：R={(a,b),(b,a),(a,c)},is not symmetric + (c,a),R'={(a,b),(b,a),(a,c), (c,a)}，R' is symmetric. Closure
2.5 Closures of relations 1 Introduction Construct a new relation r‘,s.t,RcR’, erl particular propel smallest relation closure Definition 2.17: Letr be a relation on a set a.r is called the reflexive(symmetric, transitive) closure of R, we write r(R)(S(R),t(R) or R), if there is a relation R with reflexivity(symmetry, transitivity) containing r such thatR is a subset of every relation with reflexivity(symmetry, transitivity) containing R
2.5 Closures of Relations 1.Introduction Construct a new relation R‘, s.t. RR’, particular property, smallest relation closure Definition 2.17: Let R be a relation on a set A. R' is called the reflexive(symmetric, transitive) closure of R, we write r(R)(s(R),t(R) or R+ ), if there is a relation R' with reflexivity (symmetry, transitivity) containing R such that R' is a subset of every relation with reflexivity (symmetry, transitivity) containing R
Condition: IR is reflexivity(symmetry, transitivity) 2)RCR 3)For any reflexive(symmetric, transitive) relation R If RcR then rcR Example: If R is symmetric, S(R)=? If R is symmetric, then S(R=R Contrariwise, If s(R)=R, then r is symmetric R is symmetric if only if S(R)=R Theorem 2.5: Letr be a relation on a set A. Then (1)R is reflexive if only if r(R)=R (2)R is symmetric if only if S(R)=R 3R is transitive if only if t(R)=R
Condition: 1)R' is reflexivity(symmetry, transitivity) 2)RR' 3)For any reflexive(symmetric, transitive) relation R", If RR", then R'R" Example：If R is symmetric, s(R)=? If R is symmetric，then s(R)=R Contrariwise, If s(R)=R，then R is symmetric R is symmetric if only if s(R)=R Theorem 2.5: Let R be a relation on a set A. Then (1)R is reflexive if only if r(R)=R (2)R is symmetric if only if s(R)=R (3)R is transitive if only if t(R)=R
Theorem 2.6: Let r, andr be relations on A, and rCR. Then (1r(R1r(R2); (2)s(R1)s(R2); 3)t(R1)t(R2) Proofs:(3)R1cR2→t(R1∈t(R2) Because r CR2, +RIst(R,) t(R2): transitivity
Theorem 2.6: Let R1 and R2 be relations on A, and R1R2 . Then (1)r(R1 )r(R2 )； (2)s(R1 )s(R2 )； (3)t(R1 )t(R2 )。 Proof: (3)R1R2t(R1 )t(R2 ) Because R1R2， R1t(R2 ) t(R2 ) :transitivity