離散數(shù)學(xué)第四章(第3講)課件

1、4 關(guān)系的運(yùn)算關(guān)系的復(fù)合定義：設(shè) （R關(guān)系）， （S關(guān)系）， 于是可獲得：（RS）的關(guān)系，稱 RS為R和S的復(fù)合關(guān)系，并規(guī)定為： 例：設(shè)A=1,2,3,4,5，R,S均為AA的關(guān)系，且R= S=則 RS= SR= 討論：（1） RS SR，因此“”是不可交換的。（2）RS為新的二元關(guān)系，且RS為X Z上的二元關(guān)系。定理：設(shè) 則有： 即:關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律. 定義給定集合X，R是X中的二元關(guān)系，設(shè) 于是R的n次冪 可以定義成：例：多個(gè)相同的二元關(guān)系R 復(fù)合復(fù)合運(yùn)算的矩陣表示： 設(shè)有三個(gè)集合： 而|X|=m,|Y|=n,|Z|=p，則關(guān)系矩陣：例：設(shè)X=1,2,3,R,S均是X中的二元關(guān)系，

2、R=, S= 0 1 00 1 01 0 0MR=0 1 10 0 11 0 0MS=（0 0）（1 0）（0 1）=00 0 10 0 10 1 1MRS=2逆關(guān)系 定義:設(shè)X,Y是二個(gè)集合，若R是XY的關(guān)系，從YX的關(guān)系，稱為R的逆關(guān)系，用 表示，或用 表示。例：X=0,1,2，R= =2逆關(guān)系 討論定義：（1）只要將R中每一個(gè)序偶中的元素全部調(diào)換位置，就可得到R的逆關(guān)系 。（2 ） 的關(guān)系矩陣為 的轉(zhuǎn)置矩陣； （3）在R的關(guān)系圖中，只要把所有箭頭改換方向就可得到的關(guān)系圖。（自回路箭頭改變與否無關(guān)） 定理設(shè) ，則可有： 同樣 證明：對于任一 來講，若有 同理可證R一定是對稱的 定理:設(shè)R是

3、集合X中的二元關(guān)系，當(dāng)且僅當(dāng)則R才是對稱的。證明：充分性：R是對稱的 對于任一 必要性： R是對稱的， 對任一 定理：給定集合X,Y, ，于是可有： 3.閉包運(yùn)算定義：給定集合X，R是X中的二元關(guān)系，若有另一關(guān)系R滿足下列條件： （1） R 是自反的（對稱，可傳遞的）； （2） 則稱R是R的自反（對稱，傳遞的）閉包，并依次用r(R), s(R), t(R)來表示。4關(guān)系的運(yùn)算，則 （3）對于任一自反（對稱，傳遞的）關(guān)系 ，若 例：設(shè)A=1,2,3，R為AA的關(guān)系，且R= R= 具有自反性質(zhì)R= 具有自反性質(zhì)R是包含R的具有自反性質(zhì)的最小的二元關(guān)系討論定義： （1）已知一個(gè)集合中的二元關(guān)系R，則

4、r(R), s(R), t(R)是包含R的具有自反（對稱，傳遞）性質(zhì)的最小的二元關(guān)系,它們是唯一的； （2）若R不是自反（對稱，傳遞）的，則我們可以補(bǔ)上最少序偶，使之變?yōu)樽苑?、對稱、傳遞關(guān)系，從而得到r(R), s(R), t(R)；定理：給定集合X，R是X中的二元關(guān)系，于是可有： （1）當(dāng)且僅當(dāng)r(R)=R，則R是自反的； （2）當(dāng)且僅當(dāng)s(R)=R，則R是對稱的； （3）當(dāng)且僅當(dāng)t(R)=R，則R是可傳遞的。該定理說明：若R是自反（對稱，傳遞）的，則r(R), s(R), t(R)就是R本身。定理：R是X中的二元關(guān)系,是X中的恒等關(guān)系， 則有 證明：按定義證：（1）設(shè) ，則R是自反的， （

5、3）設(shè)有任一包含R的二元關(guān)系R也是自反的，即則 例：設(shè)X=a,b,c,R=，求r(R)解：r(R)= 定理：給定集合X，R是X中的二元關(guān)系，則有 例：設(shè)X=a,b,c,R=，求s(R)s(R)= 定理：設(shè)X是一集合，R是X中的二元關(guān)系，則： 例：X=a,b,c,R=，|X|=3,計(jì)算t(R)例：X=a,b,c,d,R=,計(jì)算t(R) 定理：設(shè)|X|=n，R是X中的二元關(guān)系，則 例：設(shè)X=a,b,R= ，求r(R),s(R),t(R)r(R) = s(R) = t(R) = =R定理：設(shè)X是一集合，R是X中的二元關(guān)系，則有： r(S(R) = S(r(R)r(t(R) = t(r(R)S(t(R) t(S(R)證明： r(s(R)r(S(R) =