《離散數(shù)學(xué)第四章：二元關(guān)系和函數(shù).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第四章：二元關(guān)系和函數(shù).ppt（80頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、二元關(guān)系和函數(shù),第四章,2,第4章 二元關(guān)系與函數(shù),4.1 集合的笛卡兒積與二元關(guān)系 4.2 關(guān)系的運(yùn)算 4.3 關(guān)系的性質(zhì) 4.4 關(guān)系的閉包 4.5 等價(jià)關(guān)系和偏序關(guān)系 4.6 函數(shù)的定義和性質(zhì) 4.7 函數(shù)的復(fù)合和反函數(shù),3,4.1 集合的笛卡兒積和二元關(guān)系,有序?qū)?笛卡兒積及其性質(zhì) 二元關(guān)系的定義 二元關(guān)系的表示,4,有序?qū)Φ男再|(zhì)： 1） 有序性 （當(dāng)x y時(shí)） 2） 與 相等的充分必要條件是 = x=u y=v,例4.1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3,4.1 二元關(guān)系的概念,1. 有序?qū)?序偶：由兩個(gè)元素x和y按一定
2、順序 排成二元組，記作： 。其中x稱作第 一個(gè)元素；y稱作第二個(gè)元素。,5,實(shí)例 ： 1.空間直角坐標(biāo)系中的坐標(biāo) 是有序三元組 2. 圖書館記錄是一個(gè)有序六元組.,2. 有序n元組：一個(gè)有序 n (n3) 元組 是一個(gè)有序?qū)Γ渲械谝粋€(gè)元素是一個(gè)有序 n-1元組，即 , xn= 。,我們將來的研究重點(diǎn)為有序二元組，即有序?qū)?序偶,6,例4.2 A=1,2,3, B=a,b,c,C= AB =,,,,,, ,, BA =,,,,,, , , AA=,,,,,, ,, AC= CA= ,3. 笛卡兒積：設(shè)A, B為集合，用A中元素為第一個(gè)元素，B中元素為第二個(gè)元素，構(gòu)成有序
3、對(duì). 所有這樣的有序?qū)M成的集合叫做 A與B 的笛卡兒積 記作AB, 即 AB = | xA yB 。,7,笛卡兒積的性質(zhì)： 1. 不適合交換律 ABBA (AB, A, B) 2.若A或B中有一個(gè)為空集，則AB就是空集. A=B= 3. 若|A|=m, |B|=n, 則 |AB|=mn 4.不適合結(jié)合律 (AB)CA(BC) (A,B,C) 例： A=1,B=2,C=3 AB=, (AB)C=,3= BC=, A(BC) = ,8,二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系 例3 甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。 比賽結(jié)果可
4、表示為： ， ， ，其中表示x勝y，它表示了集合甲,乙,丙中元素之間的一種勝負(fù)關(guān)系. 例4 有A、B、C3個(gè)人和四項(xiàng)工作G1、 G2、 G3、 G4，已知A可以從事工作G1和G4，B可以從事工作G3，C可以從事工作G1和G2. 那么，人和工作之間的對(duì)應(yīng)關(guān)系可以記作 R , , , ,
5、空, 且它的元素都是有序?qū)?以有序?qū)? 元素的集合) （2）集合是空集 則稱該集合為一個(gè)二元關(guān)系, 簡稱為關(guān)系，記作R.,,10,5.從A到B的關(guān)系與A上的關(guān)系 設(shè)A,B為集合, AB的任何子集所定義的二元 關(guān)系叫做從A到B的二元關(guān)系, 當(dāng)A=B時(shí)則叫做 A上 的二元關(guān)系.,例5 A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么 R1, R2, R3, R4是從 A 到 B 的二元關(guān)系, R3和R4同時(shí)也是 A上的二元關(guān)系. 計(jì)數(shù)： |A|=n, |B|=m, |AB|= nm , AB的子集有 個(gè). 所以 A到B上有 個(gè)不同的二元關(guān)系. |A|=n,
6、 |AA|= , AA的子集有 個(gè). 所以 A上有 個(gè)不同的二元關(guān)系. 例如 |A|=3, 則 A上有512個(gè)不同的二元關(guān)系.,11,A上重要關(guān)系的實(shí)例,設(shè) A 為任意集合， 是 A 上的關(guān)系，稱為空關(guān)系 EA, IA 分別稱為全域關(guān)系與恒等關(guān)系，定義如下： EA=|xAyA=AA IA=|xA例如, A=1,2, 則 EA=,,, IA=,注： IA; IA,12,A上重要關(guān)系的實(shí)例（續(xù)）,小于等于關(guān)系 LA, 整除關(guān)系DA, 包含關(guān)系R定義： LA=| x,yAxy, DA=| x,yAx整除y, R=| x,yP(A)xy, A是某集合. 類似的還可以定義大于等于關(guān)系
7、, 小于關(guān)系, 大于關(guān)系, 真包含關(guān)系等等.,13,實(shí)例,例如 A = 1, 2, 3, B =a, b, 則 LA=,,,,, DA=,,,,,P(B)=,a,b,a,b, 則 B上的包含關(guān)系是 R=,,,,, ,,,,14,關(guān)系的表示,表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖 關(guān)系矩陣：若A=x1, x2, , xm，B=y1, y2, , yn，R是從A到B的關(guān)系，以A元素為行，B元素為列，MR = rij mn, 其中 rij = 1 R，否則rij = 0。 關(guān)系圖：若A= x1, x2, , xm，R是從A上的關(guān)系，R的關(guān)系圖是GR=, 以A中元素為結(jié)點(diǎn)，如果 R，
8、則從 xi 到 xj 有一條有向邊. 注意：A, B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖僅適于表示A上的關(guān)系,15,實(shí)例,A=1,2,3,4, R=,,,,, R的關(guān)系矩陣MR和關(guān)系圖GR如下： 習(xí)題：4.1,練習(xí),1.令A(yù)=1,2,3;B=a,b,求R1=,,,的關(guān)系矩陣。 2.令A(yù)=1,2,3;求R2=,,,的關(guān)系圖。 3. 令F=,,,，G=,,,求FG, GF, FF。（方法自選）,17,基本運(yùn)算定義 定義域、值域、域 逆、合成、限制、像 基本運(yùn)算的性質(zhì) 冪運(yùn)算 定義 求法 性質(zhì),4.2 關(guān)系的運(yùn)算,4.2 關(guān)系的運(yùn)算,,關(guān)系R的定義域： domR = x
9、| (y)R (即R中有序組的第一個(gè)元素構(gòu)成的集合),關(guān)系R的值域： ranR =y | (x)R (即R中有序組的第二個(gè)元素構(gòu)成的集合),一、關(guān)系的定義域與值域,關(guān)系R的域： fldR = domR ranR,19,關(guān)系的基本運(yùn)算定義,例1 R=,,,, 則 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4,20,關(guān)系的基本運(yùn)算定義（續(xù)）,R1 = | R RS = | | z ( S R) 例2 R=, , , S=, , , , R1=, , , RS =, , , SR =, , ,二. 逆與合成,21,合成運(yùn)算的
10、圖示方法,利用圖示（不是關(guān)系圖）方法求合成 R=, , , S=, , , , RS = , , , SR =, , ,,R,S,S,R,S RR S,22,實(shí)例 R=, , , R1=, R1=2,4 R1,2=,, R= R1,2=2, 4,三 限制和像： 已知二元關(guān)系F 和集合A F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA),注意：,FAF, FA ranF,23,四. 關(guān)系運(yùn)算的基本性質(zhì),,(1),(2),(3) 不滿足交換律： F GG
11、F,(4) 滿足結(jié)合律： F G H=F (G H),(5),25,五. A上關(guān)系的冪運(yùn)算,設(shè)R為A上的關(guān)系, n為自然數(shù), 則 R 的 n次冪定義為： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意： 對(duì)于A上的任何關(guān)系R1和R2都有 R10 = R20 = IA 對(duì)于A上的任何關(guān)系 R 都有 R1 = R,26,(1) 定義法：對(duì)于集合表示的關(guān)系R，計(jì)算 Rn 就是n個(gè)R左復(fù)合 . (2) 矩陣乘法：矩陣表示就是n個(gè)矩陣相乘, 其中相加采用邏輯加. （線性代數(shù)，邏輯乘法） (3) 關(guān)系圖法：若點(diǎn)a經(jīng)k(k=1,2,,n)條線可到達(dá)點(diǎn)b，則在 的
12、關(guān)系圖上，a到b有線相連。 例3 設(shè)A=a,b,c,d, R=,,,, 求R的各次冪, 分別用矩陣和關(guān)系圖表示.解 R與R2的關(guān)系矩陣分別為,,六. 冪的求法：,27,同理，R0=IA, R3和R4的矩陣分別是： 因此M4=M2, 即R4=R2. 因此可以得到R2=R4=R6=, R3=R5=R7=,,,28,R0, R1, R2, R3,的關(guān)系圖如下圖所示,關(guān)系圖法,結(jié)論： 僅當(dāng)A有回路時(shí)，上述結(jié)論成立。,當(dāng)圖中沒有回路時(shí)：,30,七. 冪的性質(zhì)：,當(dāng)關(guān)系圖有回路時(shí)：,(2),(3),31,證明（2）：用數(shù)學(xué)歸納法 若n=0, 則有 RmR0=RmIA=Rm=Rm+0 假設(shè)RmRn=
13、Rm+n, 則有RmRn+1=Rm (RnR)=(RmRn) R=Rm+n+1 。,冪運(yùn)算的性質(zhì)（續(xù)）,證明（3）： 若n=0, 則有 假設(shè) 則有,課后習(xí)題：4.2，4.3，4.13,4.3 關(guān)系的性質(zhì),,R的關(guān)系矩陣：主對(duì)角線元素全是1,R的關(guān)系圖：每個(gè)頂點(diǎn)都有環(huán),自反性： x A 有R (R是A上的關(guān)系),關(guān)系矩陣：主對(duì)角線元素全是0,關(guān)系圖： 每個(gè)頂點(diǎn)都沒有環(huán),反自反性：x A R,例1： A=1,2,3, R1=, R2=,, R3=,,, R4=,, R5=,,既不是自反的也不是非自反的,自反的,自反的,既不是自反的也不是非自反的,反自反的,例1：,是自反的一定不
14、是反自反的；是反自反的一定不是自反的,！在自反性方面R有3種可能：自反的；反自反的；既非自反又非反自反的,對(duì)稱性：若 R，則 R,關(guān)系矩陣：對(duì)稱陣(aij=aji),關(guān) 系 圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊。,反對(duì)稱性：若 R且xy，則 R,關(guān)系矩陣：如果rij = 1，且 i j，則rji = 0,關(guān)系圖： 如果兩個(gè)頂點(diǎn)之間有邊，一定是只有一條有向邊。,！R= |xR既是對(duì)稱關(guān)系又是反對(duì)稱關(guān)系,例2：,A=1,2,3, R1=,,, R2=,, R3=,, R4=,, R5=,,,反對(duì)稱的,既對(duì)稱又反對(duì)稱的,對(duì)稱的,反對(duì)稱的,既非對(duì)稱又非反對(duì)稱的,！在對(duì)稱性方面R有4種可能：
15、對(duì)稱的；反對(duì)稱的；既對(duì)稱又反對(duì)稱的；既非對(duì)稱又非反對(duì)稱的,,傳遞性：若 R且 R，則 R,關(guān)系圖：如果頂點(diǎn)xi到xj有邊， xj到xk有邊，則從xi到xk有邊,！若a可經(jīng)過兩條或兩條以上的線到達(dá)b，則 R,例3：,A=1,2,3,4, R1=,, R2=, R3=,, R4=,,, R5=,,,,,傳遞的,傳遞的,非傳遞的,傳遞的,非傳遞的,！在傳遞性方面，R有兩種可能：傳遞的；非傳遞的。,練習(xí)：,自反的,對(duì)稱的,反對(duì)稱的,傳遞的,自反的,對(duì)稱的,傳遞的,反自反的,反對(duì)稱的,反對(duì)稱的,傳遞的,課后習(xí)題：4.4，4.12,根據(jù)關(guān)系圖判斷關(guān)系的綜合性質(zhì)：,,4.4 關(guān)系的閉包運(yùn)算,閉包：設(shè)RAA，
16、,自反閉包 記作 r(R),對(duì)稱閉包 記作 s(R),傳遞閉包 記作 t(R),那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱之為R的自反閉包；,包含R而使之具有傳遞性質(zhì)的最小關(guān)系，稱之為R的傳遞閉包。,一、定義,包含R而使之具有對(duì)稱性質(zhì)的最小關(guān)系，稱之為R的對(duì)稱閉包。,,冪運(yùn)算：設(shè)RAA，kN，約定,(1) R0 = IA = | xA,(2) R1 = R,(3) Rk+1 = Rk R,二、計(jì)算方法,為了有效地計(jì)算關(guān)系R的各種閉包，先引進(jìn)關(guān)系的冪運(yùn)算概念。,邏輯運(yùn)算方法：設(shè)R是A上的任一關(guān)系，則,(1) r (R) = RIA,(2) s (R) = RR,(3) t (R) = RR2R
17、3 Rn-1,矩陣形式：(M為R的關(guān)系矩陣),(1) Mr = M + E（單位矩陣）,(2) Ms = M + M (M 是M的轉(zhuǎn)置),(3) Mt = M+M2 +.+Mn-1,其中“ +” 均表示“ 邏輯加”,關(guān)系圖法：,(1) 自反閉包圖：對(duì)沒有加環(huán)的點(diǎn)加環(huán),(2) 對(duì)稱閉包圖：單邊的加方向相反的邊,(3) 傳遞閉包圖：若Ai經(jīng)過兩條或兩條以 上的邊可到達(dá)Aj，且無 邊則加邊,例4.10 設(shè)A=a,b,c,d，A上的關(guān)系,求 r (R)，s (R) 和 t (R),解：1.邏輯求法： r(R) = RIA,=, , ,, , , , ,R=,,,,=
18、R,,,三、實(shí)例,=, , ,, , ,= R,,,s (R) = RR,t (R) = RR2R3 Rn-1,= R,,,,,,=, ,,,, ,,,R=,,,,2.矩陣運(yùn)算：,R=,,,,3.關(guān)系圖方法：,課后習(xí)題：4.14,R,r(R),t(R),s(R),,4.5 等價(jià)關(guān)系和偏序關(guān)系,,等價(jià)關(guān)系：集A上的關(guān)系R是自反的, 對(duì)稱的和傳遞的。,一、等價(jià)關(guān)系及用途,例4.5.1：A=1,2,3,,8，R=|x y(mod 3) 則 147，258，36,設(shè) R 是一個(gè)等價(jià)關(guān)系, 若R, 稱 x 等價(jià)于y, 記做 xy.,相容關(guān)系： R是集A上的關(guān)系，且R是自反的，對(duì)稱的,(1)在一群人的集合
19、上年齡，姓名相同的關(guān)系是等價(jià)關(guān)系, 而朋友關(guān)系是相容關(guān)系，因?yàn)樗赡懿皇莻鬟f的. (2)動(dòng)物是按種屬分類的；“具有相同種屬性”的關(guān)系是動(dòng) 物集合上的等價(jià)關(guān)系. (3)集合上的恒等關(guān)系和全域關(guān)系都是等價(jià)關(guān)系. (4)在同一平面上三角形之間的相似關(guān)系是等價(jià)關(guān)系,但直 線間的平行關(guān)系不是等價(jià)關(guān)系也不是相容關(guān)系,因?yàn)樗?是自反的.,例子：,！等價(jià)關(guān)系一定是相容關(guān)系；相容關(guān)系不一定是等價(jià)關(guān)系,,等價(jià)類： R是集A上的等價(jià)關(guān)系，對(duì)于任一aA，,aR=x | aRx, xA,被稱為a的等價(jià)類。,即：xR=y | xy,在例4.5.1中： 1R =4R =7R =1,4,7; 2R =5R =8R =2,5
20、,8; 3R =6R =9R =3,6,9;,等價(jià)類的性質(zhì)：R是非空集合，對(duì)任意的x，yA，下面的結(jié)論成立：,(1) xR 且xR A (等價(jià)類為A的子集),(2) 若xy則xR =yR ，反之成立。,(3) 若xRy，則xR yR = ,集A在等價(jià)關(guān)系R下的商集：設(shè)R為非空集A上的等價(jià)關(guān)系，A在R下的商集記作A/R， A/R=xR | xA.(集合的集合）,例4.5.1的商集為： A/R=1,4,7,2,5,8,3,6,9,注意：A/EA = A A/IA=x|xA,集A的劃分：令=A/R， 滿足以下性質(zhì)：,(1) ,(2) 中任意兩個(gè)元素不交,(3) 中所有元素的并集為A,則 為A的
21、劃分。,集合A上的劃分是不唯一的,,對(duì)于集合A，若給定一個(gè)等價(jià)關(guān)系，則我們可唯一確定一個(gè)商集,集合A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的。,集合A上的一個(gè)商集可唯一確定A上的一個(gè)劃分,例4.5.2 設(shè)A=1,2,3，求出A上所有的等價(jià)關(guān)系：,解：先求A的各種劃分：只有1個(gè)劃分塊的劃分1，具有兩個(gè)劃分塊的劃分2， 3，和4，具有3個(gè)劃分塊5。,設(shè)對(duì)應(yīng)于劃分i 的等價(jià)關(guān)系 Ri，i = 1,2,5，則有,R5 = ，，,R1 = ，，，,R2 = ，,R3 = ，,R4 = ，,，，，,，，,，，,，,，，,，,，,，，,,偏序關(guān)系：集合A上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，記作“ ” 。,二、偏序關(guān)
22、系及用途,設(shè)R為偏序關(guān)系, 如果R, 則記作x y, 讀作“x小于等于y”. 注意: 這里的“小于等于”不是指數(shù)的大小, 而是在偏序關(guān)系中的順序性.,例4.5.3 設(shè)A=1,2,3，求出A上的大于等于關(guān)系：,解： =,,,,,,其中： 1 1, 2 1, 2 2, 3 1, 3 2, 33,,偏序關(guān)系例子：,（1）任何集合A上的恒等關(guān)系,（2）集合A的冪集P(A)上的包含關(guān)系,（4）正整數(shù)集上的整除關(guān)系都是偏序關(guān)系.,（3）實(shí)數(shù)集上的小于等于，大于等于關(guān)系,,相關(guān)概念：,偏序集：集合A和偏序關(guān)系R 構(gòu)成一個(gè)偏序集， 記作。如：,等,可比：對(duì)于任意兩個(gè)元素x和y，若xy或y x， 則x與y是可比
23、的,全序關(guān)系與全序集：若A中任意兩個(gè)元素都是可比的， 則R為全序關(guān)系； 為全序集。,蓋?。喝绻鹸y，且不存在z使x z y (不是間接的), 則稱y能蓋住x。,例：,,鍋，籠屜，鍋蓋,火車臥鋪的下鋪，中鋪，上鋪,例4.5.4 設(shè)A=1,2,3,4，求出A上的整除關(guān)系：,解: R整除=,,,, ,,,,則：2,3能蓋住1；4能蓋住2；4不能蓋住1,,偏序集的哈斯圖,(1) 去掉箭頭；（蓋?。?(2) 去掉間接關(guān)系；（傳遞）,(3)去掉環(huán)。（自反的）,哈斯圖實(shí)例,例4.5.5：畫出 和,,全序關(guān)系的哈斯圖：,全序集中全部元素可以排序，它的哈斯圖為一條直線。也稱為線序集。,集合A上的
24、偏序關(guān)系與哈斯圖是一一對(duì)應(yīng)的。,課后習(xí)題：4.16,(2) 若yA，使得 (x)(xAyx)，則稱y是A的極大元 (沒有比我大的),(1) 若yA，使得 (x)(xAxy)，則稱y是A的極小元 (沒有比我小的 ),偏序集中的一些特殊元素,設(shè)是偏序集,極小元與極大元一定存在，不一定唯一,(3) 如果yA，使得(x)(xAyx)為真，則y是A的最小元 (比誰都小 ),(4) 如果yB，使得(x)(xB xy)為真，則y是B的最大元 (比誰都大),最小元與最大元或唯一或不存在,例子：,左圖：極小元為1;極大元為5,9,6,8,7 最小元為1;沒有最大元。,右圖：極小元為 ;極大元為a,b,c
25、 最小元為 ; 最大元為a,b,c。,上圖：極小元為a,b,c,g;極大元為a,f,h 沒有最小元也沒有最大元。,結(jié)論 (1):最小元一定是極小元；最大元一定是極大元. (2):孤立點(diǎn)既是極小元又是極大元,(6) 若yA，使得(x)(xB yx)為真，則稱y是B的下界（比B中每一個(gè)都?。?(7) 令C=y | y為B的上界，則稱C的最小元為B的上確界或最小上界（上界的最小元）,(8) 令D =y | y為B的下界，則D的最大元為B的下確界或最大下界（下界的最大元）,(5) 若yA，使得(x)(xB xy)為真，則稱y是B的上界（比B中每一個(gè)都大）,設(shè)是偏序集, B A,對(duì)以下哈斯
26、圖，令B = 2，3，6 , 則B的上界為6,12; B的下界為1; B的上確界為6;下確界為1.,例子：,令C = 2,4, 則C的上界為4,8,12; C的下界為1,2; C的上確界為4;下確界為2.,考慮下圖中的偏序集.令B = b, c, d , 則B的下界和最大下界都不存在, 上界有d和f, 最小上界為d.,結(jié)論 (1):上界和下界不一定存在，不一定唯一。 (2):上確界和下確界或者不存在或者唯一。 (3):集合的最小元就是它的最大下界，最大元 就是它的最小上界；反之不對(duì).,課后習(xí)題：4.6,小結(jié)與學(xué)習(xí)要求：,了解二元關(guān)系的定義和表示方法；熟練掌握關(guān)系的性質(zhì)和運(yùn)算；特別是冪，合成和三種閉包運(yùn)算;理解等價(jià)關(guān)系和偏序關(guān)系，明確它們?cè)诿枋鲅芯繉?duì)象的結(jié)構(gòu)和特點(diǎn)時(shí)重要作用 (即分類和覆蓋)。它們?cè)谟?jì)算機(jī)科學(xué)中有重要應(yīng)用。 重點(diǎn)：關(guān)系的表示方法；關(guān)系的合成，冪運(yùn)算；關(guān)系性質(zhì)判斷；閉包求法；哈斯圖畫法；哈斯圖的八個(gè)特殊元素的求法。,作業(yè)二,課后習(xí)題： 4.1，4.2，4.3，4.4，4.6，4.12，4.13，4.14，4.16,
離散數(shù)學(xué)第四章：二元關(guān)系和函數(shù).ppt
