《二元關(guān)系和函數(shù)》PPT課件.ppt

第四章 二元關(guān)系和函數(shù),基本要求：了解關(guān)系與集合之間的聯(lián)系, 序偶與笛卡爾積, 二元關(guān)系的定義, 掌握關(guān)系圖和關(guān)系矩陣, 關(guān)系的性質(zhì), 等價關(guān)系、相容關(guān)系及序關(guān)系的概念及其相互間的區(qū)別, 掌握集合的覆蓋與劃分及等價類的概念, 掌握關(guān)系的合成運算、逆運算和閉包運算。掌握函數(shù)的定義, 函數(shù)與關(guān)系之間的關(guān)系, 函數(shù)的性質(zhì), 復合函數(shù)與逆函數(shù), 幾個重要的函數(shù)。,重點：序偶與笛卡爾積, 關(guān)系的性質(zhì), 等價關(guān)系和等價類與集合劃分的概念及其求證, 關(guān)系的合成、閉包運算, 相容關(guān)系和序關(guān)系。掌握函數(shù)的基本性質(zhì), 復合函數(shù)與反函數(shù)運算。 難點：正確地掌握關(guān)系的自反性、反自反性、對稱性、反對稱性和傳遞性, 等價關(guān)系及其證明方法, 傳遞閉包的正確運算及證明。相容關(guān)系與序關(guān)系的相互區(qū)分。雙射函數(shù), 復合函數(shù)與反函數(shù)。,第四章 二元關(guān)系和函數(shù),4.1 集合的笛卡爾積與二元關(guān)系 4.2 關(guān)系的運算 4.3 關(guān)系的性質(zhì) 4.4 關(guān)系的閉包 4.5 等價關(guān)系和偏序關(guān)系 4.6 函數(shù)的定義和性質(zhì) 4.7 函數(shù)的復合和反函數(shù),4.1 集合的笛卡兒積與二元關(guān)系,一、有序?qū)?定義4.1 由兩個元素 x 和 y (允許 x=y )按一定的順序排列成的二元組叫做一個有序?qū)?也稱序偶), 記作, 其中 x 是它的第一元素, y 是它的第二元素。 例：平面直角坐標系中點的坐標,有序?qū)Φ男再|(zhì)： 1. 有序性：當 xy 時, 。 2. 的充分必要條件是,例： = , 求 x, y。 解：3y 4 = 2, x+5 = y y = 2, x = 3,= x=u y=v,定義4.2 一個有序 n 元組(n3)是一個有序?qū)? 其中第一個元素是一個有序 n-1元組, 一個有序 n元組記作：, 即 , xn 例：空間直角坐標系中點的坐標 , 等, 都是有序3元組。 n 維空間中點的坐標或 n 維向量都是有序n元組。,二、笛卡爾積,定義4.3 設(shè)A, B為集合, 用A中元素為第一元素, B中元素為第二元素, 構(gòu)成有序?qū)? 所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積, 記作AB。符號化表示為 AB| xA y B 例：Aa, b, B0, 1, 2, 則 AB, , , , , BA, , , , , ,問：如果A中有m個元素, B中有n個元素, 則 AB 和 BA 中都有多少個元素? 答：mn 個 若AB, 則有 xA 和 yB。 若AB, 則有 xA 或者 y B.,笛卡兒積運算的性質(zhì),1. 若A, B中有一個空集, 則它們的笛卡兒積是空集, 即 BA 2. 當AB且A, B都不是空集時, 有 ABBA 所以, 笛卡兒積運算不適合交換律。 3. 當A, B, C都不是空集時, 有 (AB)CA(BC) 所以, 笛卡兒積運算不適合結(jié)合律。,性質(zhì)的證明,證明： A(BC)=(AB) (AC) 證：任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) A(BC) = (AB)(AC),例題,解： (1) 任取 AC xA yC xB yD BD,例： (1) 證明 A=B C=D AC=BD (2) AC=BD是否推出 A=B C=D ? 為什么？,(2) 不一定。反例如下： A=1, B=2, C=D=, 則 AC=BD 但是 AB。,笛卡兒積運算的性質(zhì),4. 笛卡兒積運算對或運算滿足分配律, 即 A(BC) (AB)(AC)； (BC)A (BA)(CA)； A(BC) (AB)(AC)； (BC)A (BA)(CA)。,證明 A(BC)(AB)(AC) 證： 對于任意的, A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC). A(BC)(AB)(AC)。,例4.1 設(shè)A=1, 2, 求: (A)A 解：(A)A , 1, 2, 1, 21, 2 , , , , , , , ,例4.2 設(shè)A, B, C, D為任意集合, 判斷以下等式是否成立, 說明為什么。 (1) (AB)(CD)(AC)(BD)； (2) (AB)(CD)(AC)(BD)； (3) (AB)(CD)(AC) (BD)； (4) (AB) (CD) (AC) (BD)。,解：(1) 成立。因為對于任意的 , (AB)(CD) xAB yCD xAxB yCyD AC BD (AC)(BD) (2) 不成立。舉一反例如下： 若AD, BC1 則有：(AB)(CD)BC, (AC)(BD)。 (3) 和 (4) 都不成立,例4.3 設(shè)A, B, C, D為任意集合, 判斷以下命題的真假。 (1) 若AC且BD, 則有ABCD。 (2) 若ABCD, 則有AC且BD. 解 (1) 命題為真。請思考：為什么？ (2) 命題為假。當AB時, 或者A且B時, 該命題的結(jié)論是成立的。但是當A和B之中僅有一個為時, 結(jié)論不一定成立, 例如, 令ACD, B1, 這時ABCD, 但 BD。,定義4.4 設(shè)A1, A2, , An是集合(n2), 它們的n階笛卡兒積, 記作A1A2An, 其中 AlA2An | x1Alx2A2xnAn 例: A=a, b, 則 A3=, , , , , , , ,三、二元關(guān)系的定義,所謂二元關(guān)系就是在集合中兩個元素之間的某種相關(guān)性。 例：甲、乙、丙三個人進行乒乓球比賽, 如果任何兩個人之間都要賽一場, 那么共要賽三場。假設(shè)三場比賽的結(jié)果是乙勝甲、甲勝丙、乙勝丙, 這個結(jié)果可以記作 , , , 其中表示 x 勝 y 。它表示了集合甲, 乙, 丙中元素之間的一種勝負關(guān)系。,例：有A, B, C三個人和四項工作, , , , 已知A可以從事工作, , B可以從事工作, C可以從事工作, 。那么人和工作之間的對應關(guān)系可以記作 R, , , , 這是人的集合A, B, C 到 工作的集合, , , 之間的關(guān)系。,定義4.5 如果一個集合為空集或者它的元素都是有序?qū)? 則稱這個集合是一個二元關(guān)系, 一般記作R。 對于二元關(guān)系R, 如果R, 可記作 xRy； 如果R, 可記作 x y。,四、從A到B的關(guān)系與A上的關(guān)系,定義4.6 設(shè)A, B為集合, AB的任何子集所定義的二元關(guān)系稱作從A到B的二元關(guān)系, 特別當AB時, 則叫做A上的二元關(guān)系。 關(guān)系 RAB, R 是從A到B的二元關(guān)系 關(guān)系 RAA, R 是A上的二元關(guān)系 計數(shù) A上有多少個不同的二元關(guān)系? |A|=n |AA|=n2 |P(AA)|=2n2 每一個子集代表一個A上的關(guān)系, 共 2n2個關(guān)系。,A上重要關(guān)系的特例,對于任何集合A, 空集是AA的子集, 叫做A上的空關(guān)系。 定義4.7 對任意集合A, 定義： EA=| xAyA =AA 全域關(guān)系 IA=| xA 恒等關(guān)系,例：A=0, 1, 2, 則 EA, , , , , , , , IA, , 。,集合A上的常見關(guān)系,小于或等于關(guān)系：LA=|x, yAxy。 其中：AR 整除關(guān)系：DB=|x, yBx整除y, 其中：BZ* , Z*是非零整數(shù)集 包含關(guān)系：R|x, yAxy, 其中：A是集合族。,例：設(shè) A=1, 2, 3, Ba, b 則 LA=, , , , , DA=, , , , ,例4.4 設(shè)Aa, b, R是P(A)上的包含關(guān)系, R|x, yP(A)xy 則有 P(A), a, b, A 。 R, , , , , , , , ,例：設(shè)A=1, 2, 3, 4, 下面各式定義的R都是A上的關(guān)系, 試用列元素法表示R。 (1) R= | x是y的倍數(shù) (2) R= | (x-y)2A (3) R= | x/y是素數(shù) (4) R= | xy,解： (1) R = , (2) R = , , (3) R = , , (4) R = EAIA = , , , , , , ,關(guān)系的表示,表示方式：關(guān)系的集合表達式、關(guān)系矩陣、關(guān)系圖 關(guān)系矩陣：若A=x1, x2, , xm, B=y1, y2, , yn, R是從A到B的關(guān)系, R的關(guān)系矩陣是布爾矩陣 MR = rij mn, 其中 rij = 1 R。,關(guān)系圖：若A= x1, x2, , xm, R是從A上的關(guān)系, R 的關(guān)系圖是GR=, 其中 A為結(jié)點集, R 為邊集, 如果屬于關(guān)系R, 在圖中就有一條從 xi 到 xj 的有向邊。 注意：A, B為有窮集 關(guān)系矩陣適于表示從 A 到 B 的關(guān)系或者 A上的關(guān)系 關(guān)系圖適于表示 A 上的關(guān)系,關(guān)系圖GR,例：設(shè)A1, 2, 3, 4, A上的關(guān)系 R, , , , 求：R的關(guān)系矩陣MR和關(guān)系圖GR 解：關(guān)系矩陣MR,4.2 關(guān)系的運算,一、關(guān)系的基本運算 1、關(guān)系的定義域、值域和域 定義4.8 設(shè) R XY, (1) R的定義域： dom R = x | y(R) X (2) R值域：ran R = y | x(R) Y (3) R的域：fld R = dom Rran R XY,dom R 是R的所有序偶的第一個元素構(gòu)成的集合 ran R 是R的所有序偶的第二個元素構(gòu)成的集合。 例：實數(shù)集R上的關(guān)系 S=|x,yRx2+y2=1, dom S = ran S = fld S = -1, 0,1。,例4.5 下列關(guān)系都是整數(shù)集Z上的關(guān)系, 分別求出它們的定義域和值域,(1) R1x, yZ xy； (2) R2x, yZ x2+y2=1； (3) R3x, yZ y2x； (4) R4x, yZ x y=3。 解 (1) dom R1 ran R1Z。 (2) R2, , , dom R2ran R2 0, 1, -1。 (3) domR3Z ranR32z | zZ, 即偶數(shù)集 (4) domR4ranR4-3, 3。,從 A 到 B 的某些關(guān)系 R 的圖解方法(不是R的關(guān)系圖) 1. 用封閉的曲線表示 R的定義域(或集合A)和值域 (或集合B)。 2. 從 x 到 y 畫一個箭頭, 如果 R,R2,R3,2、關(guān)系的逆與合成、限制和象,定義4.9 F, G為任意的關(guān)系, A為集合, 則 (1) F的逆記作 F-1, F-1| F (2) F與G的合成記作 FG, FG | z(GF) (3) F在A上的限制記作 FA, FA | FxA (4) A在F下的像記作FA, FAran (FA),例：設(shè) R=, , , S=, , , , 求：R1 , RS, SR 解：R1 = , , , RS =, , , SR =, , ,利用圖示方法求合成,S,R,RS,S,R,SR,例4.6 設(shè)F, G是N上的關(guān)系, 其定義為 F = | x, yNy = x2 G = | x, yNy = x + 1。 求：G1 、FG、GF、F1, 2、F1, 2 解：(1) G1 = | x, yNy = x -1 =, , , , , (2) FG = |z (GF) = | z (z = x +1 y = z2 ) = | x,yNy = (x +1)2,(3) GF = | z(FG) = | x,yN y = x2 +1 (4) F1,2=, (5) F1,2= ran (F1,2) = 1,4 注：合成運算不滿足交換律, 即對任何關(guān)系F、G, 有 FGGF,定理4.1 設(shè)F、G、H是任意的關(guān)系, 則有 (1) (F1)1 = F (2) dom F1 = ran F, ran F1 = dom F (3) (FG)HF(GH) (4) (FG)1 = G1F1 如何證明 ?,二、關(guān)系運算的性質(zhì),證：(1) 任取 , 由逆的定義有 (F1)1 F1 F (F1)1 =F (2) 任取 x, xdom F1 y(F1) y(F) xran F dom F1 = ran F 。 同理可證 ran F1 = dom F 。,(3) 任取, (FG)H t(H FG) t (Hs (G)F) ) t s (H GF) s (Ft (HG) s (FGH) F (G H) (FG)H =F(GH),(4) 任取, (FG)1 (FG) t (GF) t (F1G1) G1F1 (FG)1= G1F1 #,定理 設(shè)R為A上的關(guān)系, 則有 RIA = IAR = R 證：任取, RIA t ( IA R) t ( IA x=t R) R RIA = IAR = R #,定理4.2 設(shè)F、G、H為任意的關(guān)系, 則有 (1) F(GH) = FGFH (2) (GH)F = GFHF (3) F(GH) FGFH (4) (GH)F GFHF 注： 對不滿足分配律 如何證明 ?,證：(1) 任取 F(GH) z ( (GH)F) z (GH)F) z (GF)(HF) z (FG) z (FH) FGFH FGFH F (GH) = F GF H 同理可證 (2) (FG) H = F GF H,(3) 任取 F(GH) t (GH) F ) t (G) F ) t (GF) (HF) ) t(GF) t(HF) FG FH FGFH F (GH) F GF H 同理可證 (4) (FG) H F GF H #,三、A上關(guān)系的冪運算,定義4.10 設(shè) R 為A上的關(guān)系, n為自然數(shù), 則 R 的n次冪規(guī)定如下： (1) R0=| xA (2) Rn=Rn-1R, n1 由定義知： 對A上的任何關(guān)系R1, R2都有: R10=R20=IA 對A上的任何關(guān)系R恒有: R1=R0R=RR0=R,例4.8 設(shè) A = a, b, c, d, R = , , , , 求：R的各次冪。,關(guān)系冪Rn的求法,有窮集A上給定關(guān)系 R, 如何求 Rn ? 1. 集合運算：逐個計算R2=RR, R3= R2R, 2. 關(guān)系矩陣：設(shè)R的關(guān)系矩陣為 M , 計算關(guān)系矩陣的積 M*M, 在兩個矩陣相乘時, 第 i 行第 j 列的元素 rij 滿足下式(i, j=1, 2, 3, 4) rij = ri1 r1j + ri2 r2j + ri3 r3j + ri4 r4j 此處 + 是邏輯加, 即 0+0=0, 0+1=1, 1+0=1, 1+1=1,關(guān)系冪Rn的求解方法,3. 關(guān)系圖：對R的關(guān)系圖G中的任何一個結(jié)點x, 考慮從 x 出發(fā)的長為 n 的路徑, 如果路徑的終點是 y , 則在Rn的關(guān)系圖中有一條從 x 到 y 的有向邊。即： Rn,例4.8 設(shè) A = a, b, c, d, R = , , , , 求：R的各次冪。 解：R與R2的關(guān)系矩陣分別為,同理, R0=IA, R3和R4的矩陣分別是：,顯然, M4=M2, 即 R4=R2。 因此：R2=R4=R6=, R3=R5=R7= 對于有窮集A, A上關(guān)系 R 的不同冪只有有限個。,R0, R1, R2, R3, 的關(guān)系圖如下圖所示,四、冪運算的性質(zhì),定理 設(shè)A為n元集, R是A上的關(guān)系, 則存在自然數(shù) s, t , 使得 Rs=Rt。 證：R為A上的關(guān)系, 由|A|=n, A上的不同關(guān)系只有2n2個。 當列出R的各次冪：R0, R1, R2, R2n2, 必然存在自然數(shù) s, t 使得 Rs=Rt。 # 對于有窮集合A上的關(guān)系R, R的不同冪只有有限個。,四、冪運算的性質(zhì),定理4.3 設(shè) RAA, 且m, nN, 則 (1) RmRn = Rm+n, (2) (Rm)n = Rm n。 證：用歸納法證明,證：(1) 對于任意給定的 mN, 對 n 進行歸納 若 n=0, 則有：RmR0= RmIA= Rm=Rm+0 假設(shè) n=n 時成立, 即RmRn = Rm+n, 則當 n=n+1時, 有 RmRn+1 = Rm (RnR) = (RmRn) R = Rm+n R = Rm+n+1 由歸納法知, 對一切 m, nN 有 RmRn = Rm+n (2) 對于任意給定的 mN, 對 n 進行歸納 若 n=0, 則有：(Rm)0= IA= R0= Rm0 假設(shè) n=n 時成立, 即(Rm)n = Rm n, 則當 n=n+1時, 有 (Rm)n+1 = (Rm)nRm = (Rm n) Rm = Rm n+m = Rm(n+1) 由歸納法知, 對一切m, nN有 (Rm)n = Rm n。,關(guān)系是集合, 故第三章所定義的集合運算對關(guān)系都適用。 規(guī)定 關(guān)系運算中逆運算優(yōu)先于其它運算 所有的關(guān)系運算都優(yōu)先于集合運算,運算的優(yōu)先順序,4.3 關(guān)系的性質(zhì),關(guān)系的性質(zhì)是指集合中二元關(guān)系的性質(zhì), 這些性質(zhì)扮演著重要角色, 下面將定義這些性質(zhì), 并給出它的關(guān)系矩陣和關(guān)系圖的特點。 設(shè)R是A上的關(guān)系, R的性質(zhì)主要有以下5種： 自反性、反自反性、對稱性、反對稱性、 傳遞性,一、關(guān)系性質(zhì)的定義,令RAA, 則 R是自反的 (x)( xAR ) R是反自反的 (x)( xAR ) R是對稱的 (x)(y) ( x, yARR ) R是反對稱的 (x)(y) (x, yARRx=y) 關(guān)系R是傳遞的 (x)(y)(z) (x, y, zARRR,例：設(shè)A=1, 2, 3, R1, R2, R3是A上的關(guān)系, 其中 R1, R2, , , R3 問：R1, R2和R3是否為A上的自反或反自反關(guān)系？ 解： R2是自反的; R3是反自反的; R1既不是自反的也不是反自反的。 自反與反自反關(guān)系的關(guān)系矩陣、關(guān)系圖有何特點？,注意：任何一個不是自反的關(guān)系, 未必是反自反的；反之, 任何一個不是反自反的關(guān)系, 未必是自反的。 存在既不是自反的也不是反自反的二元關(guān)系。,例：設(shè)A1,2,3, R1, R2, R3和R4都是A上的關(guān)系, 其中 R1, , R2, , R3, , R4, , 問：R1, R2, R3和R4是否為A上對稱和反對稱的關(guān)系? 解：R1既是對稱也是反對稱的。 R2是對稱的但不是反對稱的。 R3是反對稱的但不是對稱的。 R4既不是對稱的也不是反對稱的。 對稱與反對稱關(guān)系的關(guān)系矩陣、關(guān)系圖有何特點？,例：設(shè)A1, 2, 3, R1, R2, R3是A上的關(guān)系, 其中 R1, , R2, , R3 問：R1, R2和R3是否為A上的傳遞關(guān)系? 解：R1 和 R3 是A上的傳遞關(guān)系, R2 不是A上的傳遞關(guān)系。,二、關(guān)系的性質(zhì)與關(guān)系矩陣、關(guān)系圖的關(guān)系,通過上面幾個實例, 看出： 若A上關(guān)系R是自反的, 則MR中主對角線上元素全為1(rii=1), 而GR中每個結(jié)點都有環(huán); 反之亦然。 若A上關(guān)系R是反自反的, 則MR中主對角線上元素全為0(rii=0), 而GR中每個結(jié)點都無環(huán); 反之亦然。, 若A上關(guān)系R是對稱的, 則MR是對稱矩陣(rij=rji), 而GR中任何兩結(jié)點若有弧必成對出現(xiàn); 反之亦然。 若A上關(guān)系R是反對稱的, 則MR中以主對角線為對稱元素不能同時為1(若rij=1(ij), 則有rji=0), 而GR中若兩結(jié)點間有弧不成對出現(xiàn); 反之亦然。, 若A上關(guān)系R是傳遞的, 則MR中若rij=rjk=1, 則 rik=1, 而GR中若有弧和則 必有弧; 反之亦然。 上述是正確的, 但不易從MR和GR中判定關(guān)系R傳遞性。, 任何集合上的相等關(guān)系是自反的、對稱的, 反對稱的和傳遞的, 但不是反自反的。 整數(shù)集合Z中, 關(guān)系是自反的、反對稱的和傳遞的, 但不是反自反的和對稱的。關(guān)系是反自反的, 反對稱的和傳遞的, 但不是自反的和對稱的。,常見關(guān)系的性質(zhì), 非空集合上的空關(guān)系是反自反的, 對稱的, 反對稱的和傳遞的, 但不是自反的。 空集合上的空關(guān)系則是自反的, 反自反的, 對稱的, 反對稱的和傳遞的。 非空集合上的全域關(guān)系是自反的, 對稱的和傳遞的, 但不是反自反的和反對稱的。,例：設(shè)A=1, 2, 3, 判斷下列關(guān)系的性質(zhì)。 R1=, , , R2=, , R3=, R4=, , R5= R6=, , 解：R1自反, 傳遞。 R2 對稱, 反自反, 不傳遞。 R3 不自反, 不反自反, 對稱, 反對稱, 傳遞。 R4 反對稱, 反自反。 R5 對稱, 反對稱, 傳遞。 R6 不對稱, 不反對稱, 反自反, 不傳遞。,設(shè)R1和R2是集合A上的關(guān)系, 它們具有某些性質(zhì), 那么, 在它們經(jīng)過、 等運算后得到的新關(guān)系是否具有原來的性質(zhì)呢？ 可以證明以下結(jié)論：,三、集合運算對關(guān)系性質(zhì)影響,可以證明以下結(jié)論：,1. R1、R2為A上的自反關(guān)系, 則 R1R2、R1R2仍為A上的自反關(guān)系。 2. R1、R2為A上的反自反關(guān)系, 則 R1R2、R1R2、R1R2仍是A上的反自反關(guān)系。 3. R1、R2為A上的對稱關(guān)系, 則 R1R2、R1R2、R1R2仍保持其對稱性。 4. R1、R2為A上的反對稱關(guān)系, 則 R1R2、R1R2仍保持其反對稱性, 但R1R2則不一定。 5. R1、R2是上的傳遞關(guān)系, 則 R1R2仍為A上的傳遞關(guān)系。,對于保持關(guān)系性質(zhì)的運算, 都可以經(jīng)過命題演算的方法給出一般的證明。 對于不保持關(guān)系性質(zhì)的運算, 都可舉一反例說明。,例：設(shè)R1、R2為A上的對稱關(guān)系, 證明：R1R2也是A上的對稱關(guān)系。 證：對任意的, R1R2 R1R2 R1R2 ( R1, R2對稱) R1R2 R1R2是A上的對稱關(guān)系。,四、關(guān)系性質(zhì)的等價描述,定理 設(shè)R為A上的關(guān)系, 則 (1) R在A上自反的 當且僅當 IAR (2) R在A上反自反的 當且僅當 RIA= (3) R在A上對稱的 當且僅當 R=R-1 (4) R在A上反對稱的 當且僅當 RR-1IA (5) R在A上傳遞的 當且僅當 RRR,(1) R在A上自反的 當且僅當 IAR,必要性。設(shè)R是自反的, 證 IAR 任取, R是A上自反的, 必有： IA x, y A x=y R 從而證明了 IAR 充分性。設(shè) IAR, 證R是自反的 任取x, 有: xA IA R 因此 R 在A上是自反的。,(2) R在A上反自反的 當且僅當 RIA=,必要性。設(shè) R是反自反的, 證 RIA= 用反證法。設(shè)RIA, 必存在RIA 。 由于IA是A上的恒等關(guān)系, 從而推出 xAR。 這與R在A上是反自反的相矛盾。 充分性。設(shè) RIA= , 證 R是反自反的 任取x, 則有: xA IA R 從而證明了R在A上是反自反的。,(3) R在A上對稱的 當且僅當 R=R-1,必要性。設(shè)R是對稱, 證 R=Rc 。 任取, 有： R R （ R對稱） R-1 R=R-1 充分性。設(shè) R=R-1 , 證R是對稱的。 任取, R=R-1 R R-1 R R在A上是對稱的。,關(guān)系的性質(zhì)三種等價條件,4.4 關(guān)系的閉包,閉包運算是關(guān)系運算中一種比較重要的特殊運算, 是對原關(guān)系的一種擴充。 在實際應用中, 有時會遇到這樣的問題, 給定的某個關(guān)系不具有某種性質(zhì), 要使其具有該性質(zhì), 就需對原關(guān)系進行擴充。 閉包運算是關(guān)系上的一元運算, 其目的是構(gòu)造一個新關(guān)系是包含該關(guān)系且具有某種性質(zhì)的最小關(guān)系。,定義4.11 設(shè)R是A(A)上的二元關(guān)系, R 的自反 ( 對稱、傳遞 ) 閉包是A上的關(guān)系R, 且R 滿足以下條件： R是自反的（對稱的、傳遞的） R R 對任何自反(對稱、傳遞)的關(guān)系 R , 若 R” R, 則 R” R。 將R的自反、對稱和傳遞閉包分別記為: r(R)、 s(R) 和 t(R) 。,一、閉包的定義,二、閉包的構(gòu)造方法,定理4.4 設(shè) R 是 A(A)上的二元關(guān)系, 則 r(R) = RIA s(R) = RR-1 t(R) = RR2 R3 P89 例 4.10,例 設(shè)A = a, b, c, d , R = , , , , 則R和r(R), s(R), t(R)的關(guān)系圖如下圖所示。,用關(guān)系圖、關(guān)系矩陣求閉包的一般方法,1. 關(guān)系矩陣MR (1) Mr(R)= MR+E（E為單位矩陣, +為邏輯加） (2) Ms(R)= MR+ MR（MR的轉(zhuǎn)置矩陣） (3) Mt(R)= MR+ MR2+ MR3+ 注意： 在上述等式中矩陣的元素相加時使用邏輯加。,用關(guān)系圖、關(guān)系矩陣求閉包的一般方法,2. 關(guān)系圖GR r(R)的關(guān)系圖：檢查GR的每個頂點, 哪個結(jié)點上沒有環(huán)就添加上一個環(huán)即可。 s(R)的關(guān)系圖：將GR中的單向邊全部改為雙向邊即可。 t(R)的關(guān)系圖：依次檢查R的關(guān)系圖GR的每個結(jié)點 x, 把從 x 出發(fā)的長度不超過 n (|A|=n)的所有路徑的終點找到。如果x到該結(jié)點無邊, 就加上一條邊即可。,定理1 設(shè)R是非空集合A上的關(guān)系, 則 R是自反的 當且僅當 r(R)=R R是對稱的當且僅當 s(R)=R R是傳遞的當且僅當 t(R)=R,三、閉包的主要性質(zhì),證：只證明, 余下自證。 若R是自反的, 則由定義可知, R具有對R所要求的性質(zhì), 故 r(R)=R； 反之, 若r(R)=R, 則由前面定義知, R 是自反的。 # 由閉包的定義可以知道, 構(gòu)造關(guān)系R的閉包方法就是向R中加入必要的有序?qū)? 使其具有所希望的性質(zhì)。下面定理體現(xiàn)了這一點,定理2 設(shè)R1和R2是非空集合A上的關(guān)系, 且 R1R2, 則 1. r(R1) r(R2) 2. s(R1) s(R2) 3. t(R1) t(R2) 證： 1. 由閉包的定義 (1)、(2) 知：r(R2)是自反的, 且R2r(R2)。 R1R2, R1 r(R2) 又由閉包定義 (3) 知：r(R1) r(R2)。 類似地可證明2和3。,定理3 設(shè) RAA, 則 1. 若R是自反的, 則 s(R) 與 t(R) 也是自反的。 2. 若R是對稱的, 則 r(R) 與 t(R) 也是對稱的。 3. 若R是傳遞的, 則 r(R) 是傳遞的。,定理4 設(shè) RAA, 則 rs(R) = sr(R) rt(R) = tr(R) st(R) ts(R),4.5 等價關(guān)系與偏序關(guān)系,一、等價關(guān)系的定義與實例 定義4.12 設(shè)R是非空集合A上二元關(guān)系, 若R是自反的、對稱的和傳遞的, 則稱R為A上的等價關(guān)系。設(shè)R是一個等價關(guān)系, 如果R, 稱 a 等價于 b, 記作 ab。 由于R是對稱的, a等價b即b等價a, 反之亦然, a與b 彼此等價。,鑒于空集合上的二元關(guān)系是等價關(guān)系, 是一種平凡情形, 因此, 一般討論非空集合上的等價關(guān)系。 模m等價是Z或其子集上的等價關(guān)系, 并且是一類重要的等價關(guān)系。,例4.11 A=1, 2, , 8, P91 R = |x, yAxy(mod 3), 其中 xy(mod 3) 叫做 x 與 y 模 3相等, 即 x 除以 3 的余數(shù)與 y 除以 3 的余數(shù)相等。 關(guān)系圖如下所示：,例4.11 A=1, 2, , 8, R = |x, yAxy(mod 3), 不難驗證R 是 A上的等價關(guān)系。 (1) xA, 有xx(mod 3) R 是自反的 (2) x, yA, 若xy(mod 3), 則有yx(mod 3), R 是對稱的 (3) x, y, zA, 若xy(mod 3), yz(mod 3), 則有xz(mod 3), R 是傳遞的,1. 等價類 定義4.13 設(shè)R為非空集合A上的等價關(guān)系, 對 xA, 令 xR= y| yAxRy 則稱 xR 為 x關(guān)于R的等價類, 簡稱 x的等價類, 簡記為 x 。,二、等價類及其性質(zhì),例4.11 A=1, 2, , 8, R = |x, yAxy(mod 3), 前已驗證 R 是A上的等價關(guān)系 則 A上模3同余等價關(guān)系的等價類: 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6,定理4.5 設(shè)R是非空集合A上的等價關(guān)系, 則 xA, xR是A的非空子集。 x, yA, 若R, 則 x=y。 x, yA, 若R, 則 xy=。 x | xA =A 利用非空集合A及其上等價關(guān)系可以構(gòu)造一個新集合商集。,2. 等價類的性質(zhì),1. 商集 定義4.14 設(shè)R是非空集合A上的等價關(guān)系, 以R的所有等價類為元素的集合稱為A關(guān)于R的商集, 記作 A/R , 即 A/R = xR| xA ,三、商集與集合的劃分,該定義表明了, 與商集 A/R 有密切聯(lián)系的概念是集合的劃分。 如：設(shè) A=1, 2, , 8, 則 A上模3同余等價關(guān)系的商集: A/R =1, 4, 7, 2, 5, 8, 3, 6 A上恒等關(guān)系、全域關(guān)系的商集為： A/IA =1, 2, 3, 4, 5, 6, 7, 8 A/EA =1, 2, 3, 4, 5, 6, 7, 8,2. 集合的劃分 定義4.15 設(shè)A為非空集合, 若存在一個A的子集族 ( P(A) 滿足下面的條件： (1) (2) xy( x, y x y xy= ) (3) =A 則稱 是A的一個劃分, 稱 中的元素為A的劃分塊。,例4.14 設(shè) A=a, b, c, d, 給定1, 2, 3, 4, 5如下： (1) 1=a, b, c, d (2) 2= a, b, c, d (3) 3=a,b, c, a,d (4) 4=, a,b, c,d (5) 5=a, b,c 問：哪些是集合A的劃分？ 解：1和 2是集體A的劃分, 其余都不是。 為什么？,例4.15 設(shè) A =1, 2, 3, 求A上所有的等價關(guān)系。 解：如下圖, 先做出A的所有劃分。,這些劃分與A上的等價關(guān)系之間的一一對應是: 1對應全域關(guān)系EA, 5對應恒等關(guān)系IA, 2, 3和4分別對應于等價關(guān)系R2, R3和R4, 其中: R2 = , U IA R3 = , U IA R4 = , U IA,3. 商集與劃分的對應關(guān)系,商集A/R就是A的一個劃分, 不同的商集對應不同的劃分。 任給集體A的一個劃分, 如下定義A上的關(guān)系R： R=|x, yAx與y在的同一劃分塊中 則R為A上的等價關(guān)系, 且等價關(guān)系R所確定的商集就是。 A上的等價關(guān)系與A的劃分是一一對應,等價關(guān)系與劃分是兩個不同的概念, 表示方法也不同： 等價關(guān)系是序偶的集合, 劃分是子集的集合 給定劃分 , 求對應等價關(guān)系的方法： 設(shè) =A1, A2, , Am是集合A的一個劃分, 定義R為： R=|a, b Ai , i=1, 2, , m （即 R= A1A1A2A2AmAm） 則R是A上的等價關(guān)系, 且 = A/R。,1. 偏序關(guān)系的定義與實例 定義4.16 設(shè)R是非空集合A上的關(guān)系, 若R是自反的, 反對稱和傳遞的, 則稱R為A上的偏序關(guān)系, 記作 。 設(shè) 是偏序關(guān)系, , 則記作 x y, 讀作“小于或等于”。 注意：這里的“小于或等于”不是指數(shù)的大小, 而是在偏序關(guān)系中的順序性。,四、偏序關(guān)系,例：集合A上的恒等關(guān)系IA是A上的偏序關(guān)系。 實數(shù)集合上的小于或等于、正整數(shù)集上的整除關(guān)系、集合A的冪集P(A)上的包含關(guān)系是相應集合上的偏序關(guān)系。 包含關(guān)系, A B(常記: AB)是指A包含于B; 整除關(guān)系, 3 6 (常記: 3|6) 是指3整除6 若 R是A上的偏序, 則 R-1也是A上偏序。若用 表示 R, 則用 表示 R-1, 即 互為對偶。,定義4.17 一個集合A與A上的偏序關(guān)系R一起叫作偏序集, 記作 。 如: 整數(shù)集合Z和小于或等于關(guān)系構(gòu)成偏序集, 集合A的冪集P(A)和包含關(guān)系構(gòu)成偏序集。,2. 偏序集,定義4.18 設(shè)為偏序集, a, bA, 若a b 或 b a 成立, 則稱 a與b 是可比的 若a b (即 a b ab ), 且不存在 cA使得 acb, 則稱 b 蓋住 a 。 定義可知, 在偏序集中, a, bA, 可能有下述三種情況發(fā)生： a b (或 b a) a = b a 與 b 不可比,例：A=1, 2, 4, 6, 是A上的整除關(guān)系, 則有 2 蓋住 1, 4 和 6 蓋住 2, 但 4 不蓋住 1 4 與 6 不可比。,定義4.19 設(shè)為偏序集, 若 a, bA, a 與 b 都是可比的, 即 a, bA a bb a 則稱 為A上全序關(guān)系, 且稱為全序集,描述有窮集的偏序集。 利用偏序關(guān)系 的自反性、反對稱性和傳遞性可簡化關(guān)系圖哈斯(Hass)圖 在畫偏序集的哈斯圖時, 需適當排列 A 中元素的順序, 使得： 對于a, bA, 若a b, 則將 a 畫在 b 的下方； 考慮 b是否蓋住了a, 若 b蓋住 a, 則用一條線段連接 a 和 b。,3. 哈斯圖,例4.16 畫出和 的哈斯圖。 P94 由哈斯圖求偏序關(guān)系 例4.17 已知偏序集的哈斯圖 求：集合A和A上的偏序關(guān)系。,定義4.20 設(shè)為偏序集, BA, bB, 若(x)(xB b x )為真, 則稱 b為B的最小元 若(x)(xB x b )為真, 則稱 b為B的最大元 若(x)(xBx b )為真, 則稱 b為B的極小元 若(x)(xBb x )為真, 則稱 b為B的極大元,4. 偏序集中的特殊元素 P95,注意： 由定義知: 最小元與極小元是有區(qū)別的, 最小元是B中最小的元素, 它與B中其他元素都可比；而極小元不一定與B中元素都可比, 只要沒有比它小的元素, 它就是極小元 對于有窮集B, 極小元一定存在, 且可能有多個, 但最小元不一定存在, 若存在則必唯一 若B中只有一個極小元, 則它一定是B的最小元 類似地可討論極大元與最大元之間區(qū)別。,例 A= 1, 2, 3, 4, 5, 6, 7, 8, 偏序集的哈斯圖如圖所示。,求: 如下B中的最大元, 最小元, 極大元, 極小元 (1) B=1, 2, 3, 5 (2) B=2, 3, 4, 5, 6, 7 (3) B=4, 5, 8 (4) B=4, 5,解： (1) B=1, 2, 3, 5,(2) B=2, 3, 4, 5, 6, 7,最大元, 極大元: 5。 最小元, 極小元: 1。,無最大、最小元。 極大元: 6, 7, 極小元: 2, 3。,(3) B=4, 5, 8,最大元: 8, 無最小元。 極大元: 8, 極小元: 4, 5。,(4) B=4, 5,無最大元、最小元。 極大元: 4, 5, 極小元: 4, 5。,定義4.21 設(shè)為偏序集, BA, bA, 若(x)( xBx b)為真, 則稱 b為B的上界。 若(x)( xBb x)為真, 則稱 b為B的下界。 令Cy| y為B的上界, 則稱 C的最小元為B的最小上界或上確界, 記作：LUB B。 令Dy| y為B的下界, 則稱 D的最大元為B的最大下界或下確界, 記作：GLB B。,例 A= 1, 2, 3, 4, 5, 6, 7, 8, 偏序集的哈斯圖如圖所示。,求: B的上界, 下界, 上確界, 下確界 (1) B=2, 3, 4, 5, 7 (2) B=2, 5, 4, 6,解： (1) B=2, 3, 4, 5, 7 上界: 7, 8; 下界: 1; 上確界: 7; 下確界: 1。 (2) B=2, 4, 5, 6 上界: 8; 下界: 2, 1 上確界: 8; 下確界: 2。,性質(zhì)： 上界, 下界, 上確界, 下確界不一定存在。 上界、下界若存在, 不一定唯一。 上確界、下確界若存在, 則必唯一。 集合B 的最小元一定是 B 的下界, 并且也是 B 的最大下界; 反之不一定正確, B 的下界不一定是 B 的最小元, 因為它可能不是 B 中的元素; 類似地, 討論 B 的最大元與其上界的關(guān)系。,4.6 函數(shù)的定義和性質(zhì),函數(shù)概念是最基本的數(shù)學概念之一, 也是最重要的數(shù)學工具。 初中數(shù)學中函數(shù)定義為“對自變量每一確定值都有一確定的值與之對應的應變量”; 高中數(shù)學中函數(shù)又被定義為兩集合元素之間的映射。,函數(shù)是一種特殊的二元關(guān)系, 我們可以把函數(shù)看作輸入輸出關(guān)系; 它把一個集合(輸入集合)的元素變成另一個集體(輸出集合)的元素。 離散結(jié)構(gòu)之間的函數(shù)關(guān)系在計算機科學研究中也已顯示出極其重要的意義。 例如： 把計算機中輸入、輸出之間的關(guān)系看成是一種函數(shù) 在開關(guān)理論、自動機理論和可計算性理論等領(lǐng)域中, 函數(shù)是有著極其廣泛的應用。,一、函數(shù)的定義,1. 函數(shù)的定義 定義4.22 設(shè)F為二元關(guān)系, 若 xdom(F) 都存在唯一的 yranF, 使 xFy 成立, 則稱F為函數(shù)。 對于函數(shù)F, 如果有xFy , 則記作 y =F(x), 并稱 y 為F在 x 的函數(shù)值。 函數(shù)一般用小寫字母表示。,P95,說明,函數(shù)是特殊的關(guān)系：f XY, 則有 dom f = X, 不是 X 的真子集。 一個 x 只能對應唯一的一個 y 。 函數(shù)的定義式還可以寫成： f =|x( xX!y( yY y=f (x) ,2. 函數(shù)相等,定義 設(shè) f, g 是函數(shù), 則 f = g f gg f 。 由定義知, 如果兩個函數(shù) f 和 g 相等, 一定滿足下面兩個條件： (1) dom f = dom g (2) x dom f = dom g 恒有 f(x) = g(x),例：函數(shù) f(x)(x21)/(x+1), g(x)x1 不相等, 因為 dom f x | xRx1 dom gR 顯然, dom f dom g, 所以, 這兩個函數(shù)不相等。,定義4.23 設(shè)A、B是集合, 如果函數(shù) f 滿足以下條件 (1) dom f = A (2) ran f B 則稱 f 是從A到B的函數(shù), 記作 f :AB . 如：f : NN, f(x) = 2x g : NN, g(x) = 2 都是從N到N的函數(shù)。,例 判別下列關(guān)系中哪個能構(gòu)成函數(shù)。,a. f=|x1, x2N 且 x1+x210, x1不能取定義域中所有的值, 且x1對應多個x2, 該關(guān)系 f 不能構(gòu)成函數(shù)。,b. f=|y1, y2 R 且 y22=y1, 一個y1對應兩個y2 , f 不是函數(shù)。,c. f=|x1, x2 N 且 x2 為小于x1 的素數(shù)個數(shù),能夠成為函數(shù)。,3. 函數(shù)集合,由函數(shù)的定義可知, XY的子集并不能都成為從X到Y(jié)的函數(shù)。 例：設(shè) X=a, b, c, Y=0, 1, XY=, , , , , XY有26個可能的子集, 但其中只有23個子集定義為從X到Y(jié)的函數(shù)。 f0=, , f1=, , f2=, , f3=, , f4=, , f5=, , f6=, , f7=, , ,設(shè) X和 Y都為有限集, 分別有 m個和 n個不