復(fù)合關(guān)系逆關(guān)系

1、1第二部分 集合論主要內(nèi)容集合3-1 集合概念和表示法3-2 集合運(yùn)算 3-4 序偶與笛卡爾積3-5 關(guān)系及其表示 3-6 關(guān)系性質(zhì)3-7 復(fù)合關(guān)系和逆關(guān)系3-8 關(guān)系閉包運(yùn)算3-9 集合劃分與覆蓋3-10 等價(jià)關(guān)系與等價(jià)類 3-11 相容關(guān)系3-12 序關(guān)系函數(shù)4.1 函數(shù)基本概念4.2 復(fù)合函數(shù)與逆函數(shù)1/422第一部分 數(shù)理邏輯上節(jié)內(nèi)容回顧3-5 關(guān)系及其表示 3-5. 1 關(guān)系關(guān)系：序偶集合定義域、值域、域 3-5. 2 一些特殊關(guān)系空關(guān)系、恒等關(guān)系、全域關(guān)系關(guān)系交并補(bǔ)差還是關(guān)系 3-5. 3 關(guān)系表示序偶集合形式關(guān)系矩陣MR關(guān)系圖GR3-4 序偶和笛卡爾積序偶概念和表示 =,z,z

2、x,笛卡爾積AB=|xAyB不滿足交換律、結(jié)合律與、 滿足分配率2/423第二部分 集合論主要內(nèi)容集合3-1 集合概念和表示法3-2 集合運(yùn)算 3-4 序偶與笛卡爾積3-5 關(guān)系及其表示 3-6 關(guān)系性質(zhì)3-7 復(fù)合關(guān)系和逆關(guān)系3-8 關(guān)系閉包運(yùn)算3-9 集合劃分與覆蓋3-10 等價(jià)關(guān)系與等價(jià)類 3-11 相容關(guān)系3-12 序關(guān)系函數(shù)4.1 函數(shù)基本概念4.2 復(fù)合函數(shù)與逆函數(shù)3/42（1） 自反性(reflexivity)（2） 反自反性( irreflexivity)（3） 對(duì)稱性(symmetry)（4） 反對(duì)稱性( antisymmetry)（5） 傳遞性(transitivity)3

3、-6 關(guān)系性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性4/42需要指出：從X到Y(jié)關(guān)系R是XY 子集，即RXY，而XY （XY）（XY）所以R （XY）（XY）令Z= XY，則RZZ所以，我們今后通常限于討論同一集合上關(guān)系。第二部分 集合論需要注意：關(guān)系和運(yùn)算關(guān)系：= 不相交 朋友 同學(xué) 父子運(yùn)算： 自反性反自反性對(duì)稱性反對(duì)稱性傳遞性5/42自反性reflexivity：設(shè)R為定義在A上二元關(guān)系，即RAA, 假如對(duì)于每一個(gè)xA，有xRx (R)，則稱二元關(guān)系R是自反。 R在A上是自反 (x)( xA xRx) R在A上是非自反 (x)( xA R)。定理： R是自反 IA RMR主對(duì)角線上元素全為1G

4、R每個(gè)頂點(diǎn)處都有自環(huán)。第二部分 集合論自反性反自反性對(duì)稱性反對(duì)稱性傳遞性6/42自反性(舉例)：恒等關(guān)系、全域關(guān)系實(shí)數(shù)：= ：|x,y都是實(shí)數(shù)且xy幾何圖形：三角形全等：|AB、相同 數(shù)理邏輯： 、：|PQ 、|PQ是重言式集合論： ：|A B第二部分 集合論第二部分 集合論自反性反自反性對(duì)稱性反對(duì)稱性傳遞性7/42反自反性irreflexivity：設(shè)RAA, 假如對(duì)于每一個(gè)xA，有R，則稱二元關(guān)系R是反自反。R在A上是反自反 (x)(xA R )。R在A上是非反自反 (x)( xA xRx)定理： R是反自反 IAR= MR主對(duì)角線上元素全為0 GR每個(gè)頂點(diǎn)處均無自回路（無環(huán)）。第二部分

5、集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性8/42反自反性(舉例)：空關(guān)系實(shí)數(shù)：、：|x,y都是實(shí)數(shù)且xy數(shù)理邏輯：|PQ是重言式 中“”取 、 、 時(shí)集合論：、 ：|A B注意：非自反不一定是反自反。即存在相關(guān)系既不是自反也不是反自反。第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性9/42對(duì)稱性symmetry：設(shè)RAA, 假如對(duì)于每個(gè)x,yA，每當(dāng) xRy，就有 yRx，則稱集合A上關(guān)系R是對(duì)稱。R在A上對(duì)稱 (x)(y)(xAyAxRyyRx).R非對(duì)稱 (x)(y)(xAyAxRyyRx)定理： R是對(duì)稱 MR是對(duì)稱 GR任何兩個(gè)頂點(diǎn)之間若有邊, 則必

6、有兩條方向相反有向邊. 第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性10/42對(duì)稱性(舉例)：空關(guān)系、恒等關(guān)系、全域關(guān)系實(shí)數(shù)：、= ：|x,y都是實(shí)數(shù)且x=y幾何圖形：三角形全等：|AB、相同 數(shù)理邏輯：|PQ是重言式 中“”取 、 、 時(shí)集合論：、不相交 ：|AB=整數(shù)：同余人之間關(guān)系：同學(xué)關(guān)系、朋友關(guān)系、鄰居關(guān)系第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性11/42反對(duì)稱性antisymmetry：設(shè)RAA,假如對(duì)于每個(gè)x,yA,每當(dāng) xRy和yRx，必有x=y，則稱集合A上關(guān)系R是反對(duì)稱。R是反對(duì)稱 (x)(y)

7、(xAyA xRy yRx x=y ) (x)(y)(xAyA xy xRy yRx ).R非反對(duì)稱 (x)(y)(xA yA xRy yRx xy)定理：R是反對(duì)稱 在MR中, xixj(ij rij=1rji=0) 在GR中, xixj(ij), 若有有向邊, 則必沒有。第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性12/42反對(duì)稱性(舉例)：空關(guān)系實(shí)數(shù)：、數(shù)理邏輯： |P Q是重言式 集合論： ：|A B人之間關(guān)系：父與子關(guān)系整數(shù)：整除關(guān)系：|x,y都是整數(shù)且x|y注意：非對(duì)稱不一定反對(duì)稱；可能有某種關(guān)系即是對(duì)稱又是反對(duì)稱。比如：A=1,2,3, S=

8、, S在A上即是對(duì)稱又是反對(duì)稱。N=, N在A上即不是對(duì)稱又不是反對(duì)稱。第二部分 集合論，恒等關(guān)系、=、 、=第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性13/42傳遞性transitivity：設(shè)RAA, 假如對(duì)于任意x,y,zA, 每當(dāng)xRy，yRz時(shí)就有xRz，稱關(guān)系R在A上是傳遞。R在A上是傳遞 (x)(y)(z)(xAyAzAxRyyRzxRz)R非傳遞(x)(y)(z)(xAyAzAxRy yRzxRz)。定理：R是傳遞 在GR中, xi xj xk(ijk), 若有有向邊和, 則必有 。第二部分 集合論第二部分 集合論第二部分 集合論第二部分

9、 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性14/42傳遞性(舉例)：空關(guān)系、恒等關(guān)系、全域關(guān)系實(shí)數(shù)：、=、整數(shù)：同余、整除關(guān)系：|x,y都是整數(shù)且x|y幾何圖形：三角形全等：|AB、相同數(shù)理邏輯： 、：|PQ是重言式 集合論：、 ：|A B人之間關(guān)系：同姓、同性別自反性與反自反性是相互矛盾，不能同時(shí)成立對(duì)稱性和反對(duì)稱性不矛盾、能夠同時(shí)成立第二部分 集合論第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性15/42例1：在 N = 1,2, 上：、 ： |xNyNxy自反,反對(duì)稱,傳遞、：|xNyNxy反自反,反對(duì)稱,傳遞D=|xNyNx|y (整除關(guān)系)自反,反

10、對(duì)稱,傳遞IN=|xNyNx=y (恒等關(guān)系)自反,對(duì)稱,反對(duì)稱,傳遞EN=|xNyN=NN (全域關(guān)系)自反,對(duì)稱,傳遞第二部分 集合論第二部分 集合論第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性思索：左邊敘述是否完全正確？有沒有不嚴(yán)謹(jǐn)?shù)胤剑?6/42例2：判斷以下關(guān)系所含有性質(zhì)。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7 =第二部分 集合論反對(duì)稱,傳遞反對(duì)稱自反,對(duì)稱,傳遞對(duì)稱自反,反對(duì)稱,傳遞 反自反，對(duì)稱，反對(duì)稱 ，傳遞第二部分 集合論第二部分 集合論第二部分 集合論第二部分 集合論自反性對(duì)稱性反對(duì)稱性傳遞性反自反性17/4

11、2第二部分 集合論自反性反自反性對(duì)稱性反對(duì)稱性傳遞性定義集合關(guān)系矩陣關(guān)系圖xA,有RxA,有R若R則R若R,且xy, 則 R若R 且R 則RIARRIA=R=RcRRcIARRR主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij1, 且ij, 則rji0M2中1位置, M中對(duì)應(yīng)位置都是1每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)兩點(diǎn)之間有邊, 是一對(duì)方向相反邊兩點(diǎn)之間有邊,是一條有向邊點(diǎn)xi到xj有邊, xj 到xk有邊, 則xi到xk也有邊 18/42設(shè) A=1,2,3，下面分別給出集合A上三個(gè)關(guān)系關(guān)系圖，試判斷它們性質(zhì)。 （2）非自反，也不是反自反，非對(duì)稱，反對(duì)稱， 可傳遞。 （3）是自反，對(duì)

12、稱，可傳遞，不是反自反，也不是反對(duì)稱。 解 （1）是自反，非對(duì)稱，不是反對(duì)稱，不可傳遞 19/42小結(jié): 本節(jié)介紹了關(guān)系基本性質(zhì)及其判別方法。作業(yè)：第二部分 集合論 P113 (3)(6)P109 (2)(5) b) d)20/4221第二部分 集合論主要內(nèi)容集合3-1 集合概念和表示法3-2 集合運(yùn)算 3-4 序偶與笛卡爾積3-5 關(guān)系及其表示 3-6 關(guān)系性質(zhì)3-7 復(fù)合關(guān)系和逆關(guān)系3-8 關(guān)系閉包運(yùn)算3-9 集合劃分與覆蓋3-10 等價(jià)關(guān)系與等價(jià)類 3-11 相容關(guān)系3-12 序關(guān)系函數(shù)4.1 函數(shù)基本概念4.2 復(fù)合函數(shù)與逆函數(shù)21/423-7.1 復(fù)合關(guān)系3-7.2 逆關(guān)系3-7.3

13、 關(guān)系運(yùn)算性質(zhì)3-7.4 關(guān)系矩陣與關(guān)系圖3-7 復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖22/42運(yùn)算性質(zhì)復(fù)合 (composite)關(guān)系:設(shè)R為X到Y(jié)關(guān)系，S為從Y到Z關(guān)系，則RS稱為R和S復(fù)合關(guān)系，表示為：RS= | xXzZ(y)(yYRS).定義（屈婉玲版）：二元關(guān)系R, S右復(fù)合運(yùn)算 RS = ( | y (R S) 復(fù)合關(guān)系逆關(guān)系矩陣與圖23/42B=離散數(shù)學(xué), 高等數(shù)學(xué), 大學(xué)物理, 大學(xué)英語, 體育課C=吃飯, 睡覺, 打豆豆, 變成豆豆A=周一早晨, 周二下午, 周三下午，周四早晨，周五下午RS=, R=, , , ，S=, , , , 復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖

14、24/42社交六度分割原理：地球上任何兩個(gè)人之間間隔不超出6個(gè)人第二部分 集合論A=地球上人；R=|x,y A, 且x與y認(rèn)識(shí)RR2R3R4R5R6=AA你隔壁老王家孩子同學(xué)同事親戚朋友認(rèn)識(shí)特朗普復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖25/42逆(inverse)關(guān)系 : 設(shè)R是X到Y(jié)二元關(guān)系，則從Y到X二元關(guān)系Rc (R-1)定義為： Rc = |R.整數(shù)集合上“”關(guān)系逆關(guān)系是“”關(guān)系。人群中父與子關(guān)系逆關(guān)系是子與父關(guān)系。輕易看出(Rc) c=R第二部分 集合論復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖26/42第二部分 集合論 RS = SR =, , , , , 栗子： R = , , , S = , ,

15、, , , , , Rc = 利用圖示（不是關(guān)系圖）方法求復(fù)合關(guān)系復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖27/4228關(guān)系運(yùn)算性質(zhì)1 設(shè)F是任意關(guān)系, 則 (1) (Fc)c=F (2) domFc= ranF, ranFc= domF證 (1) 任取, 由逆定義有 (Fc)c Fc F.所以有(Fc)c=F.(2) 任取x, xdomFc y(Fc) y(F) xranF 所以有 domFc=ranF. 同理可證 ranFc=domF.28/4229設(shè)F, G, H是任意關(guān)系, 則(1) 結(jié)合律：(FG)H = F(GH)(2) (FG)c = GcFc(1)證 任取, (FG)H t (FGH)

16、t ( s (FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH)關(guān)系運(yùn)算性質(zhì)229/4230性質(zhì)2證實(shí)(2) (FG)c = GcFc證 任取, (FG)c FG t (FG) t (GcFc) Gc Fc所以 (F G)c = Gc Fc 30/4231關(guān)系運(yùn)算性質(zhì)3設(shè)R為A上關(guān)系, 則 RIA= IAR=R證任取 RIA t (RIA) t (Rt=y) R RR yA R IA RIA同理可證 IAR=R31/4232關(guān)系運(yùn)算性質(zhì)4分配率：F,G,H為任意關(guān)系，則 (1) F(GH) = FGFH (2) (GH)F = G

17、FHF (3) F(GH) FGFH (4) (GH)F GFHF(3)證 任取, F(GH) t (FGH) t (FGH) t (FG)(FH) t (FG)t (FH) FGFH FGFH所以有 F(GH) FGFH注意：復(fù)合運(yùn)算對(duì)并滿足分配律，對(duì)交滿足“弱”分配律(GH) H)GH) FH=32/4233推廣分配率結(jié)論能夠推廣到有限多個(gè)關(guān)系 R(R1R2Rn) = RR1RR2RRn (R1R2Rn)R = R1RR2RRnR R(R1R2 Rn) RR1RR2 RRn (R1R2 Rn)R R1RR2R RnR 33/4234關(guān)系運(yùn)算性質(zhì)5(1) (R1 R2) c= R1 c R2

18、 c (2) (R1R2) c= R1 c R2 c(3) (AB)c= BA(4) (R)c = Rc, 這里R AB-R(5) (R1-R2)c = R1c - R2c34/4235關(guān)系冪運(yùn)算定義：設(shè) R 為 A 上關(guān)系, n為自然數(shù), 則 R n 次冪定義為：(1) R0 = | xA = IA(2) Rn+1 = RnR注意：對(duì)于A上任何關(guān)系 R1 和 R2 都有 R10 = R20 = IA 對(duì)于A上任何關(guān)系 R 都有 R1 = R35/42關(guān)系矩陣性質(zhì)：(1) MRc= (MR)T. ( T表示矩陣轉(zhuǎn)置)(2) MR1 R2 = MR1MR2 (表示布爾乘法, 其中加法使用邏輯, 乘法使用邏輯 )逆關(guān)系關(guān)系圖性質(zhì)：關(guān)系 Rc 圖形是將關(guān)系R圖形中弧箭頭方向反置。復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖36/42例題: 設(shè) A=a,b,c, R1=, R2=, 用MR1, MR2確定MR1c , MR2c, MR1R1, MR1R2, MR2R1, 從而求出它們集合表示式.復(fù)合關(guān)系逆關(guān)系運(yùn)算性質(zhì)矩陣與圖37/42 1 1 0 1 1 0MR1= 1 0 1 MR1c= 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0MR2= 0 0 1 MR2c= 1 0 0 0 0 0 1 1 0 0 1 1 MR1R2 =MR1 MR2= 0 1 1 0 0 0R1R2