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

1、 第四章二元關(guān)系1 序偶與笛卡爾積2 關(guān)系及其表示3 關(guān)系的性質(zhì)4 關(guān)系的運算5 等價關(guān)系與劃分6 相容關(guān)系與覆蓋7 偏序關(guān)系1 序偶與笛卡爾乘積 1 序偶定義由二個具有給定次序的客體所組成的序列稱為序偶。記作x，y 例：XY二維平面上的一個點的坐標x，y就是一個序偶。說明： (1)在序偶中二個元素要有確定的排列次序。 若ab時，則a，bb，a 若x，y=a，b（x=a y=b） (2) 多重序元： 三元組：x，y，z =x，y，z n元組： x1，x2，x3，xn= x1,xn2 笛卡爾乘積定義設(shè)A，B為二個任意集合，若序偶的第一個成員（左元素）是A的一個元素，序偶的第二個成員（右元素）是B

2、的一個元素，則所有這樣的序偶構(gòu)成的集合稱為A和B的笛卡爾乘積。 記作：A B=x，y|（xA）（yB）例：設(shè)A=1，2 ， B=a，b，則： AB=1，a,1，b,2，a,2，b BA=a，1,a，2,b，1,b，2 A B B A ， 即“”是不滿足交換律。例：設(shè)A=a，b，B=1，2，C=z,則:(AB)C = a,1,a,2,b,1,b,2z = a,1,z,a,2,z,b,1,z,b,2,z A ( BC ) =a ， b 1,z,2,z=a,1,z,a,2,z,b,1,z,b,2,z（A B） C A （B C） ,“”不滿足結(jié)合律。 定理若A，B，C是三個集合，則有： A（B C）

3、=（AB） （AC） A（B C）=（AB） （AC） （A B） C=（AC） （BC） （A B） C=（AC） （BC） 證明:A(B C)=(AB) (AC)證明：設(shè)是A（B C）中的任一元素，則： A（B C） |xA yB C |xA yB yC |(xA yB) (xA yC) (AB) (AC) 即 A(B C) = (AB) (AC)例：設(shè)A= 1 ，B=1，2，C=2，3,則 A（B C）= 1 1，2，3 = 1,1,1,2,1,3 （AB）（AC）= 1 1，2 1 2，3 = 1,1,1,2,1,3 例：設(shè)A= 1 ，B=1，2，C=2，3,則： A（B C）= 1

4、2 = 1,2 （AB）（AC） =1,1,1,2 1,2,1,3 =1,2 注：n個集合的笛卡兒乘積的定義 ：A2 = AAA3 = AAAAn = AAAn個A2 關(guān)系及其表示1 關(guān)系 定義：指事物之間（客體之間）的相互聯(lián)系。 在數(shù)學(xué)上關(guān)系可表達集合中元素間的聯(lián)系。 序偶a，b可以反映a，b二個元素之間具有某 種關(guān)系。 定義以序偶作為元素的任何集合是一個二元關(guān)系。 由定義可知：二元關(guān)系是一個集合。 設(shè)R表示二元關(guān)系， 若 R, 用 xRy 表示， 若 R ，則也可寫成：x R y。關(guān)系表示方法（1）枚舉法（列舉法） 例：二元關(guān)系R定義如下圖： 可用枚舉法表示為：（2）謂詞公式表示法 一個集

5、合可用謂詞公式來表達，所以二元關(guān)系也可用謂詞公式來表達。例：實數(shù)集合R上的“”關(guān)系可表達為：“”= （3）關(guān)系矩陣表示法 設(shè)二元關(guān)系 R 是A B上的二元關(guān)系，關(guān)系矩陣表示法描述如下： (a)集合A中的元素表示矩陣的行元素，集合B中的元素表示矩陣的列元素； (b)若 R ，則在關(guān)系矩陣對應(yīng)位置記上“1”，否則記為“0”。 例：設(shè)A=a，b，c， B=1，3，4， R1 是AB上的二元關(guān)系，給出R1的關(guān)系矩陣.R1= abc134101110MR1 =110例：設(shè)X=a，b，c， Y=1，2， R2 是XY上的二元關(guān)系， 給出R2的關(guān)系矩陣.例：設(shè)X=a，b，c， Y=1，2， R3 是X Y上

6、的二元關(guān)系且R3= ， 給出R3的關(guān)系矩陣.例：設(shè)X=1，2，3，4， R4 是X X上的二元關(guān)系，給出R4的關(guān)系矩陣.R4= 100110M R4 =1110000000（4）關(guān)系圖表示法設(shè)R為集合XY上的二元關(guān)系，關(guān)系矩陣圖表示法描述如下：(a)把集合、中的元素以點的形式全部畫在平面上；(b)若 R ，則在x和y之間畫一帶箭頭弧線，其箭頭指向y。反之不畫任何聯(lián)線。 例：設(shè)X=1，2，3，4， R1 是X 上的二元關(guān)系，給出R1的關(guān)系圖。R1= . 關(guān)系的前域和值域 定義設(shè)R是一個二元關(guān)系，由 R的所有序偶的第一元素x組成的集合dom R稱R的前域,即定義 R的前域和值域的并集稱做R的域,記

7、做FLD R, 即:FLD R=dom R ran R定義設(shè)R是一個二元關(guān)系，由 R的所有序偶的第二元素y組成的集合ran R稱R的值域,即例：X=1,2,3,4,5,6,Y=a,b,c,d,e,f, R為X到Y(jié)的二元關(guān)系.dom R=1,2,3,4ran R=a,b,c,dFLD R=1,2,3,4,a,b,c,d關(guān)系和笛卡爾乘積笛卡爾乘積的任何子集都可以定義一種二元關(guān)系。例：X=1,2,3,4，Y=1,2 思考： 集合XY上可以產(chǎn)生多少種二元關(guān)系？S1,S2都是XY的子集，并且它們二元關(guān)系。 S1=|x X yYx y=三個特殊關(guān)系：全域關(guān)系，空關(guān)系，恒等關(guān)系定義集合A2定義了A集合中的一種關(guān)系，該關(guān)系稱為 A中的全域關(guān)系，用EA表示：例：A=1，2,則集合A上的全域關(guān)系為： EA = 定義空集也是 AxA的一個子集，它也定義了一種關(guān)系,稱為空關(guān)系，用