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

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

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

3、有2|A1A2An|個不同的子集。因此，以A1A2An為基的不同關系共有2|A1A2An|個。8/6/20225計算機科學與工程學院例51在數(shù)據(jù)庫中，常將用表格的方式表示出來的文件看作是關系R，如下表是一個學生學籍管理的一個數(shù)據(jù)庫：則此時有關系RA1A2A6，其中系別與班級A1學號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計算機科學與工程學院二元關系定義5-1.2設A，B為兩個集合，AB的任何一個子集R

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

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

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

7、會得到不同的關系矩陣。當集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。 8/6/202212計算機科學與工程學院例5.5設A2，3，4，B1，2，4?？紤]從A到B的“大于等于”關系R和“小于等于”關系S：R,，S,。寫出R，S的關系矩陣。解：8/6/202213計算機科學與工程學院52 關系的性質1、自反性與反自反性定義5-1.3 設R是集合A上的二元關系，對任意的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計算機科學與工程學院例5.5設A=a,b,c,d， R=,。因為A中每個元素x，都有R，所以R是自反的。R的關系圖R的關系矩陣8/6/202215計算機科學與工程學院例5.5(續(xù)1)S=,。S的關系圖S的關系矩陣因為A中每個元素x，都有S，所以S是反自反的。8/6/202216計算機科學與工程學院例5.5(續(xù)2)T=,。因為A中有元素b，使T，所以T不是自反的；因為A中有元素a，使T，所以T不是反自反的。T的關系圖T的關系矩陣8/6/202217計算機科學與工程學院結論任何不是自反的關系未必一定是反自反的關系，反之亦然。即存在既不是自反的也不是反

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

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

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

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

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

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

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