關(guān)系的運算教學課件

1、關(guān)系的運算教學課件關(guān)系的運算教學課件22022/9/9一、關(guān)系的定義域、值域、域 定義：設(shè)R是二元關(guān)系，由 R的所有x組成的集合稱為R的定義域(前域），記作domR；使 R的所有y組成的集合稱為R的值域，記作ranR。domR = x | y (R) ；ranR = y | x (R) 定義： R的域，即fldR = domR ranR 42022/9/6一、關(guān)系的定義域、值域、域 定義：設(shè)R32022/9/9二、關(guān)系的逆運算及其性質(zhì)定義：二元關(guān)系R的逆關(guān)系記為R1 R1 = | R例1：R=, , , ，求R1 R1=, , , 52022/9/6二、關(guān)系的逆運算及其性質(zhì)定義：二元關(guān)系R的4

2、2022/9/9二、關(guān)系的逆運算及其性質(zhì) 關(guān)系逆運算的相關(guān)性質(zhì)： 定理1：設(shè)R是任意的關(guān)系, 則(1) (R1)1=R(2) domR1=ranR, ranR1=domR問題：關(guān)系R和R1的關(guān)系矩陣之間有怎樣的聯(lián)系？互為轉(zhuǎn)置矩陣。62022/9/6二、關(guān)系的逆運算及其性質(zhì) 關(guān)系逆運算52022/9/9二、關(guān)系的逆運算及其性質(zhì) 設(shè)R、S是任意的二元關(guān)系，(RS)-1= R-1S-1(RS)-1= R-1S-1(R)-1= (R-1)(R-S)-1= R-1-S-1 RSR-1S-172022/9/6二、關(guān)系的逆運算及其性質(zhì) 設(shè)R、S是任意62022/9/9兄弟父子叔侄RSRS引例：82022/9

3、/6兄弟父子叔侄RSRS引例：72022/9/9三、關(guān)系的復合運算及其性質(zhì)定義：二元關(guān)系R、S的復合運算記作RS RS = | y (RS) 例2：R=, , , S=, , , , RS =, , SR =, , , 92022/9/6三、關(guān)系的復合運算及其性質(zhì)定義：二元關(guān)系R82022/9/9三、關(guān)系的復合運算及其性質(zhì)問題： 如果將RS的關(guān)系矩陣記為MRS ， R的關(guān)系矩陣記為MR， S的關(guān)系矩陣記為MS ， 則MRS和MR ,MS之間有怎樣的關(guān)系？102022/9/6三、關(guān)系的復合運算及其性質(zhì)問題： 如果將92022/9/9三、關(guān)系的復合運算及其性質(zhì)e.g. A=a,b, R=, S=,

4、RS =112022/9/6三、關(guān)系的復合運算及其性質(zhì)e.g. A=102022/9/9三、關(guān)系的復合運算及其性質(zhì)例3：給定集合X=0,1,2中的兩個關(guān)系如下：試求復合關(guān)系： R1 R2 R1 ， R1 (R2 R1 )122022/9/6三、關(guān)系的復合運算及其性質(zhì)例3：給定集合112022/9/9三、關(guān)系的復合運算及其性質(zhì)解：R1 = ,R2 = R1 R2 R1 = , =,R1 (R2 R1 ) = , , =,132022/9/6三、關(guān)系的復合運算及其性質(zhì)解：R1 = 122022/9/9三、關(guān)系的復合運算及其性質(zhì)復合運算的相關(guān)性質(zhì)： 定理2: 設(shè)F, G, H是任意的關(guān)系, 則 (1

5、) (FG)H=F(GH) (2) (FG)1= G1F1定理3：設(shè)RAA，則RIA=IAR=R142022/9/6三、關(guān)系的復合運算及其性質(zhì)復合運算的相關(guān)132022/9/9三、關(guān)系的復合運算及其性質(zhì)定理4：若F,G,H是任意的二元關(guān)系，則 F(GH)= FG FH (GH)F =GF HF F(GH) FG FH (GH)F GF HF152022/9/6三、關(guān)系的復合運算及其性質(zhì)定理4：若F,142022/9/9四、關(guān)系的“限制”運算及其性質(zhì)例4：R=, , , RAR R1=, R=R1,2=, , , 定義：二元關(guān)系R在集合A上的限制 即RA = |RxA定理5：設(shè)F為關(guān)系，A,B為

6、集合，則：F(AB)=FAFBF(AB)=FAFB162022/9/6四、關(guān)系的“限制”運算及其性質(zhì)例4：R=152022/9/9五、集合在關(guān)系下的“像”及性質(zhì) 定義：A 在R下的像記作RA，RA = ran(RA)例5：R=, , , RA ranR R1=ran(R1)=ran,=2,4R1,2= ran(R1,2)=2,3,4定理5：設(shè)F為關(guān)系，A,B為集合，則： FAB=FA FB FAB FA FB172022/9/6五、集合在關(guān)系下的“像”及性質(zhì) 定義162022/9/9六、關(guān)系的冪運算及其性質(zhì) 定義：設(shè)R為A上的關(guān)系, n為自然數(shù), 則 R 的 n次冪定義為： (1) R0= |

7、 xA =IA (2) Rn+1 = RnR 對于A上的任何關(guān)系R1和R2都有： R10 = R20 = IA 對于A上的任何關(guān)系 R 都有： R1 = R 182022/9/6六、關(guān)系的冪運算及其性質(zhì) 定義：設(shè)172022/9/9六、關(guān)系的冪運算及其性質(zhì) 關(guān)系冪運算的求解方法：用集合表示給出R時，通過n-1次的右復合得到Rn ；用關(guān)系矩陣M給出R時， Rn的關(guān)系矩陣由n個M相乘得到；用關(guān)系圖G給出R時，具體步驟見例題。 192022/9/6六、關(guān)系的冪運算及其性質(zhì) 關(guān)系冪運算182022/9/9例6: 設(shè)A=a,b,c,d, R=, 求R的各次冪, 分別用矩陣和關(guān)系圖表示.解: R0IA它的

8、關(guān)系矩陣記作M0六、關(guān)系的冪運算及其性質(zhì)202022/9/6例6: 設(shè)A=a,b,c,d, R192022/9/9六、關(guān)系的冪運算及其性質(zhì)R2對應的關(guān)系矩陣為M2R對應的關(guān)系矩陣為M212022/9/6六、關(guān)系的冪運算及其性質(zhì)R2對應的關(guān)系矩202022/9/9同理，R3和R4的矩陣分別是：因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=R7=六、關(guān)系的冪運算及其性質(zhì)222022/9/6同理，R3和R4的矩陣分別是：因此M4=212022/9/9R0, R1, R2, R3,的關(guān)系圖如下圖所示：六、關(guān)系的冪運算及其性質(zhì)R0R1R2=R4=R6=,R3=R5=R7=232022/9/6R0, R1, R2, R3,的關(guān)系圖222022/9/9六、關(guān)系的冪運算及其性質(zhì) 定理7： 設(shè)A為n元集, R是A上的關(guān)系, 則存在自然數(shù) s 和 t, 使得 Rs = Rt.冪運算的性質(zhì):定理6： 設(shè) R 是 A 上的關(guān)系, m, nN, 則 (1) RmRn=Rm+n (2) (Rm)n=Rmn 242022/9/6六、關(guān)系的冪運算及其性質(zhì) 定理7： 232022/9/9六、