離散數(shù)學(xué)(第11講)

1、馮偉森Email138081922758/6/2022離散數(shù)學(xué)計算機學(xué)院8/6/20221計算機科學(xué)與工程學(xué)院主要內(nèi)容1、關(guān)系的定義2、關(guān)系的表示3、關(guān)系的性質(zhì)8/6/20222計算機科學(xué)與工程學(xué)院第五章 二元關(guān)系 在第三章我們討論了集合及其元素，本章討論集合中元素之間的關(guān)系。關(guān)系是表征事物的結(jié)構(gòu)及其內(nèi)在聯(lián)系。 研究事物結(jié)構(gòu),主要是研究關(guān)系。關(guān)系的概念應(yīng)用廣泛,在計算機科學(xué)中起著重要的作用,如數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)庫,數(shù)字邏輯,情報檢索,算法分析,編譯,人工智能等領(lǐng)域它都是很重要的數(shù)學(xué)工具。8/6/20223計算機科學(xué)與工程學(xué)院51 二元關(guān)系及其表示1、關(guān)系的定義 關(guān)系是一

2、個基本的概念,通俗地說,所謂關(guān)系,是指對象之間的相互聯(lián)系,它表征事物的結(jié)構(gòu)。如自然界中的“引力關(guān)系”,人與人之間的“父子關(guān)系”,“上下級關(guān)系“,”同志關(guān)系”,“同學(xué)關(guān)系”,對象間的“位置關(guān)系”,兩個數(shù)間的“大于”,“等于”,“整除關(guān)系”,兩個變量之間的“函數(shù)關(guān)系”,計算機部件間的“聯(lián)結(jié)關(guān)系”,程序間的“調(diào)用關(guān)系”,8/6/20224計算機科學(xué)與工程學(xué)院定義5-1.1設(shè)A1,A2,An為n個非空集合，稱A1A2An的任意子集R為以A1A2An為基的n元關(guān)系。特別：當(dāng)R時，則稱R為空關(guān)系；當(dāng)RA1A2An時，則稱R為全關(guān)系。由于A1A2An的任何子集都是一個n元關(guān)系，按照子集的定義，A1A2An共

3、有2|A1A2An|個不同的子集。因此，以A1A2An為基的不同關(guān)系共有2|A1A2An|個。8/6/20225計算機科學(xué)與工程學(xué)院例51在數(shù)據(jù)庫中，常將用表格的方式表示出來的文件看作是關(guān)系R，如下表是一個學(xué)生學(xué)籍管理的一個數(shù)據(jù)庫：則此時有關(guān)系RA1A2A6，其中系別與班級A1學(xué)號A2姓名A3性別A4年齡A5籍貫A694081-11王雷男18四川94081-13李華男19江蘇94081-22張江男17北京94082-14趙小容女18云南94082-22陳濤男19廣東94082-31黃靜女19山東8/6/20226計算機科學(xué)與工程學(xué)院二元關(guān)系定義5-1.2設(shè)A，B為兩個集合，AB的任何一個子集R

4、所定義的二元關(guān)系稱為從A到B的二元關(guān)系，簡稱關(guān)系。如R是從A到A的二元關(guān)系，則稱R為A上的二元關(guān)系。設(shè)有一序偶：R，常把這一事實記為xRy，讀作“x對y有關(guān)系R”。如R，則記為xRy，讀作“x對y沒有關(guān)系R”。由于任何AB的子集都是一個二元關(guān)系，按照子集的定義，知AB共有2|A|B|個不同的子集。因此，從A到B不同的關(guān)系共有2|A|B|個。8/6/20227計算機科學(xué)與工程學(xué)院關(guān)系的表示法1.集合表示法由于關(guān)系也是一種特殊的集合，所以集合的兩種基本的表示法也可以用到關(guān)系的表示中。即可用枚舉法和敘述法來表示關(guān)系。例5.2設(shè)A2,B3,關(guān)系R如定義集合N上的“小于等于”關(guān)系：R|(x,yN)(xy

5、)。8/6/20228計算機科學(xué)與工程學(xué)院2.關(guān)系圖法設(shè)Aa1,a2,a3,.,an,Bb1,b2,b3,.,bm，R是設(shè)a1,a2,a3,.,an和b1,b2,b3,.,bm分別為圖中的節(jié)點，用“。”表示；如R,則從ai到bj可用一有向邊aibj相連。為對應(yīng)圖中的有向邊。從A到B的一個二元關(guān)系，則對應(yīng)于關(guān)系R之關(guān)系圖有如下規(guī)定：如R是定義在A上的關(guān)系，則對應(yīng)于關(guān)系R有如下規(guī)定：設(shè)a1,a2,.,an為圖中節(jié)點，用“?！北硎尽Ｈ鏡,則從ai到aj可用一有向邊aiaj相連。為對應(yīng)圖中的有向邊；如R,則從ai到ai用一帶箭頭的小圓環(huán)表示ai 8/6/20229計算機科學(xué)與工程學(xué)院例5.3設(shè)A是六個

6、程序，考慮它們之間的一種調(diào)用關(guān)系R，如Pi可調(diào)用Pj,則有R,現(xiàn)假設(shè)R, 則此關(guān)系R的關(guān)系圖如下：8/6/202210計算機科學(xué)與工程學(xué)院例5.42）設(shè)Aa1,a2,a3,a6是六個人，B1，2，3是三套房間，考慮A到B之間的一種住宿關(guān)系R，如ai住房間j,則有R,現(xiàn)假設(shè)：R,則此關(guān)系R的關(guān)系圖如下：8/6/202211計算機科學(xué)與工程學(xué)院3.關(guān)系矩陣設(shè)Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm，R是從A到B的一個二元關(guān)系， 稱矩陣MR(rij)nm為關(guān)系R的關(guān)系矩陣或鄰接矩陣，其中：顯然，關(guān)系矩陣是布爾矩陣。注意 在寫關(guān)系矩陣時，首先應(yīng)對集合A和B中的元素進行排序，不同的排序

7、會得到不同的關(guān)系矩陣。當(dāng)集合以枚舉法表示時，如果沒有對集合的元素排序，則默認(rèn)枚舉的次序為元素的排序。 8/6/202212計算機科學(xué)與工程學(xué)院例5.5設(shè)A2，3，4，B1，2，4?？紤]從A到B的“大于等于”關(guān)系R和“小于等于”關(guān)系S：R,，S,。寫出R，S的關(guān)系矩陣。解：8/6/202213計算機科學(xué)與工程學(xué)院52 關(guān)系的性質(zhì)1、自反性與反自反性定義5-1.3 設(shè)R是集合A上的二元關(guān)系，對任意的xA,都滿足R，則稱R是自反的，或稱R具有自反性，即R在A上是自反的(x)(xA)(R)=1對任意的xA,都滿足R，則稱R是反自反的，或稱R具有反自反性，即R在A上是反自反的(x)(xA)(R)=1 o

8、r (x)(xA)(R)=08/6/202214計算機科學(xué)與工程學(xué)院例5.5設(shè)A=a,b,c,d， R=,。因為A中每個元素x，都有R，所以R是自反的。R的關(guān)系圖R的關(guān)系矩陣8/6/202215計算機科學(xué)與工程學(xué)院例5.5(續(xù)1)S=,。S的關(guān)系圖S的關(guān)系矩陣因為A中每個元素x，都有S，所以S是反自反的。8/6/202216計算機科學(xué)與工程學(xué)院例5.5(續(xù)2)T=,。因為A中有元素b，使T，所以T不是自反的；因為A中有元素a，使T，所以T不是反自反的。T的關(guān)系圖T的關(guān)系矩陣8/6/202217計算機科學(xué)與工程學(xué)院結(jié)論任何不是自反的關(guān)系未必一定是反自反的關(guān)系，反之亦然。即存在既不是自反的也不是反

9、自反的關(guān)系。表現(xiàn)在關(guān)系圖上：關(guān)系R是自反的，當(dāng)且僅當(dāng)其關(guān)系圖中每個結(jié)點都有環(huán)；關(guān)系R是反自反的，當(dāng)且僅當(dāng)其關(guān)系圖中每個結(jié)點都無環(huán)。表現(xiàn)在關(guān)系矩陣上：關(guān)系R是自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上全為1；關(guān)系R是反自反的當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上全為0。 8/6/202218計算機科學(xué)與工程學(xué)院對稱性與反對稱性定義5-1.4 設(shè)R是集合A上的二元關(guān)系，對任意的x,yA，如果R，那么R，則稱關(guān)系R是對稱的，或稱R具有對稱性，即R在A上是對稱的 (x)(y)(xA)(yA)(R)(R)=1對任意的x,yA，如果R且R，那么x=y，則稱關(guān)系R是反對稱的，或稱R具有反對稱性，即R在A上是反對稱的 (

10、x)(y)(xA)(yA)(R)(R)(x=y)=18/6/202219計算機科學(xué)與工程學(xué)院例5.6設(shè)A=a,b,c,d， R1=,R2=, R1的關(guān)系圖R1的關(guān)系矩陣是對稱的是反對稱的R2的關(guān)系圖R2的關(guān)系矩陣8/6/202220計算機科學(xué)與工程學(xué)院例5.6(續(xù)1)R3=,R4=, 既不是對稱的，也不是反對稱的R3的關(guān)系圖R3的關(guān)系矩陣既是對稱的，也是反對稱的R4的關(guān)系圖R4的關(guān)系矩陣8/6/202221計算機科學(xué)與工程學(xué)院結(jié)論任何不是對稱的關(guān)系未必一定是反對稱的關(guān)系，反之亦然。即存在既不是對稱的也不是反對稱的關(guān)系，也存在既是對稱的也是反對稱的關(guān)系。表現(xiàn)在關(guān)系圖上：關(guān)系R是對稱的當(dāng)且僅當(dāng)其關(guān)

11、系圖中，任何一對結(jié)點之間，要么有方向相反的兩條邊，要么無任何邊；關(guān)系R是反對稱的當(dāng)且僅當(dāng)其關(guān)系圖中，任何一對結(jié)點之間，至多有一條邊。表現(xiàn)在關(guān)系矩陣上：關(guān)系R是對稱的當(dāng)且僅當(dāng)其關(guān)系矩陣為對稱矩陣，即rij=rji，i,j=1,2, ,n；關(guān)系R是反對稱的當(dāng)且僅當(dāng)其關(guān)系矩陣為反對稱矩陣，即rijrji=0，i,j=1,2,n，ij。 8/6/202222計算機科學(xué)與工程學(xué)院傳遞性定義5-1.4 設(shè)R是集合A上的二元關(guān)系，對任意的x,y,zA，如果R且R，那么R，則稱關(guān)系R是傳遞的，或稱R具有傳遞性，即R在A上是傳遞的(x)(y)(z)(xA)(yA)(zA)(R)(R)(R)=1 8/6/2022

12、23計算機科學(xué)與工程學(xué)院例5.7模運算 mod： n mod d為d除n的余數(shù) n mod d =j 讀為“n 模 d 余j” 如果整數(shù)m和整數(shù)n關(guān)于模d的余數(shù)相同，稱m和n（關(guān)于模d）是同余的，寫為nm(mod d)xRy xy(mod m) m為確定的整數(shù)R是對稱的、自反的、傳遞的關(guān)系，但不是反自反的和反對稱的8/6/202224計算機科學(xué)與工程學(xué)院結(jié)論表現(xiàn)在關(guān)系圖上：關(guān)系R是傳遞的當(dāng)且僅當(dāng)其關(guān)系圖中，任何三個結(jié)點x,y,z（可以相同）之間，若從x到y(tǒng)有一條邊存在，從y到z有一條邊存在，則從x到z一定有一條邊存在。表現(xiàn)在關(guān)系矩陣上：關(guān)系R是傳遞的當(dāng)且僅當(dāng)其關(guān)系矩陣中，對任意i,j,k1,2

13、,3,n，若rij=1且rjk=1，必有rik=1。8/6/202225計算機科學(xué)與工程學(xué)院53 關(guān)系的運算設(shè)R，S都是集合A到B的兩個關(guān)系，則：RS|(xRy)(xSy)RS|(xRy)(xSy) R-S=|(xRy)(xSy)|(xRy) RS= |RSRS 1、關(guān)系的交、并、補、差運算根據(jù)定義，由于AB是相對于R的全集，所以AB-R,且RAB,R。8/6/202226計算機科學(xué)與工程學(xué)院例5.8設(shè)Aa,b,c,B1,2，R,，S,，則：RSRSR-S,，；,；,AB-R。8/6/202227計算機科學(xué)與工程學(xué)院關(guān)系的復(fù)合運算設(shè)R是一個從集合A到集合B的二元關(guān)系，S是從集合B到集合C的二元

14、關(guān)系(也可簡單地描述為R：AB，S：BC)，則R與S的復(fù)合關(guān)系（合成關(guān)系）RS是從A到C的關(guān)系，并且：RS|(xA)(zC)(y)(yB)(xRy)(ySz)運算“”稱為復(fù)合運算。8/6/202228計算機科學(xué)與工程學(xué)院復(fù)合關(guān)系的矩陣表示 R與S的復(fù)合關(guān)系（合成關(guān)系）RS也可以用矩陣來表示。 設(shè)R，S都是集合A= a1，a2，a3，.，an上的二元關(guān)系，MR(rij)， MS(sij)， =(mij)則 =MR*MS 這里的“*”運算類似矩陣乘法運算，但須將元素間的乘法改成邏輯與，將加法改成邏輯或，即 mij=(ri1s1j)(ri2s2j) (rinsnj)8/6/202229計算機科學(xué)與工

15、程學(xué)院例5.9設(shè)R,S,，分別是定義為從AB和從BC的關(guān)系，其中ABC1,2,3,4。1).用集合方法求RS，SR，RR，SS。則：RS,；SR,；RR,；SS,。8/6/202230計算機科學(xué)與工程學(xué)院例5.10 RSR。SABCAC1。1。11。12。2。22。23。3。33。34。4。44。42).用關(guān)系圖求RS。3).用關(guān)系矩陣求RS。MRS MR* MS*8/6/202231計算機科學(xué)與工程學(xué)院關(guān)系的冪定義5-1.5設(shè)R是集合A上的二元關(guān)系，則可定義R的n次冪Rn（n0），該Rn也是A上的二元關(guān)系，定義如下：1.R0IA|aA；2.R1R ；3.Rn+1RnRRRn。容易證明，RmRnRm+n,(Rm)nRmn。8/6/202232計算機科學(xué)與工程學(xué)院關(guān)系的逆運算定義5-1.6設(shè)R是一個從集合A到集合B的二元關(guān)系，則從B到A的關(guān)系R-1|R稱為R的逆關(guān)系,運算“-1”稱為逆運算。注意：關(guān)系是一種集合，逆關(guān)系也是一種集合，因此，如果R是一個關(guān)系，則R-1和都是關(guān)