離散數(shù)學(第4.1-4.3) 陳瑜

1、陳瑜Email：134028388008/6/2022離散數(shù)學計算機學院8/6/20221計算機科學與工程學院第4章的主要內(nèi)容1.學習關系的數(shù)學定義、表示方法、性質(zhì)及運算；2.掌握兩類在實踐中非常重要的二元關系：等價關系、偏序關系；8/6/20222計算機科學與工程學院本節(jié)課主要內(nèi)容1.關系的定義2.關系的表示3.關系的性質(zhì)8/6/20223計算機科學與工程學院第四章 二元關系萬事萬物之間總可以根據(jù)需要確定相應的關系。從數(shù)學的角度看，這類聯(lián)系就是某個集合中元素之間的關系。在第三章我們討論了集合及其元素，本章討論集合中元素之間的關系。關系是表征事物的結構及其內(nèi)在的聯(lián)系。研究事物結構,主要是研究關

2、系。關系的概念應用廣泛,在計算機科學中起著重要的作用,如數(shù)據(jù)結構,數(shù)據(jù)庫,數(shù)字邏輯,情報檢索,算法分析,編譯,人工智能等領域它都是很重要的數(shù)學工具。8/6/20224計算機科學與工程學院第四章 二元關系萬事萬物之間總可以根據(jù)需要確定相應的關系。從數(shù)學的角度看，這類聯(lián)系就是某個集合中元素之間的關系。在第三章我們討論了集合及其元素，本章討論集合中元素之間的關系。關系是表征事物的結構及其內(nèi)在的聯(lián)系。研究事物結構,主要是研究關系。關系的概念應用廣泛,在計算機科學中起著重要的作用,如數(shù)據(jù)結構,數(shù)據(jù)庫,數(shù)字邏輯,情報檢索,算法分析,編譯,人工智能等領域它都是很重要的數(shù)學工具。8/6/20225計算機科學與

3、工程學院第四章 二元關系萬事萬物之間總可以根據(jù)需要確定相應的關系。從數(shù)學的角度看，這類聯(lián)系就是某個集合中元素之間的關系。在第三章我們討論了集合及其元素，本章討論集合中元素之間的關系。關系是表征事物的結構及其內(nèi)在的聯(lián)系。研究事物結構,主要是研究關系。關系的概念應用廣泛,在計算機科學中起著重要的作用,如數(shù)據(jù)結構,數(shù)據(jù)庫,數(shù)字邏輯,情報檢索,算法分析,編譯,人工智能等領域它都是很重要的數(shù)學工具。8/6/20226計算機科學與工程學院41 二元關系及其表示關系是一個基本的概念,通俗地說,所謂關系,是指對象之間的相互聯(lián)系,它表征事物的結構。如自然界中的“引力關系”,人與人之間的“父子關系”,“上下級關系

4、“,”同志關系”,“同學關系”,對象間的“位置關系”,兩個數(shù)間的“大于”,“等于”,“整除關系”,兩個變量之間的“函數(shù)關系”,計算機部件間的“聯(lián)結關系”,程序間的“調(diào)用關系”,8/6/20227計算機科學與工程學院41 二元關系及其表示為表達元素之間的關系，可用英文字母R表示所定義的關系。 如： 1）當元素x關于元素y具有指定的關系R時，則 表示成：xRy； 2）當x關于y不具有指定的關系R時，則表示成：xRy 此外，還可以用另外的形式來表達關系。如可以用笛卡爾序偶（x，y）來表達xRy的意義。下面的定義就將這兩種表示法聯(lián)系了起來。8/6/20228計算機科學與工程學院41 二元關系及其表示為

5、表達元素之間的關系，可用英文字母R表示所定義的關系。 如： 1）當元素x關于元素y具有指定的關系R時，則 表示成：xRy； 2）當x關于y不具有指定的關系R時，則表示成：xRy 此外，還可以用另外的形式來表達關系。如可以用笛卡爾序偶（x，y）來表達xRy的意義。下面的定義就將這兩種表示法聯(lián)系了起來。8/6/20229計算機科學與工程學院41 二元關系及其表示為表達元素之間的關系，可用英文字母R表示所定義的關系。 如： 1）當元素x關于元素y具有指定的關系R時，則 表示成：xRy； 2）當x關于y不具有指定的關系R時，則表示成：xRy 此外，還可以用另外的形式來表達關系。如可以用笛卡爾序偶（x，

6、y）來表達xRy的意義。下面的定義就將這兩種表示法聯(lián)系了起來。8/6/202210計算機科學與工程學院定義4-1.1設A和B都是已知集合，R是A到B的一個確定的二元關系，那么R就是AB的一個合于 R=(x,y)AB的子集合。按照定義4-1.1， xRy (x，y) R。 同理， xRy (x，y) R。可以看出，采用集合表示關系便于對關系進行處理。定義4-1.1定義的二元關系可以很容易擴展到n元關系。例如： 存在于集合A1，A2，An的元素間的n元關系可以定義為： A1A2An的子集合。本課程著重討論二元關系。 8/6/202211計算機科學與工程學院定義4-1.1設A和B都是已知集合，R是A

7、到B的一個確定的二元關系，那么R就是AB的一個合于 R=(x,y)AB的子集合。按照定義4-1.1， xRy (x，y) R。 同理， xRy (x，y) R?？梢钥闯?，采用集合表示關系便于對關系進行處理。定義4-1.1定義的二元關系可以很容易擴展到n元關系。例如： 存在于集合A1，A2，An的元素間的n元關系可以定義為： A1A2An的子集合。本課程著重討論二元關系。 8/6/202212計算機科學與工程學院定義4-1.1設A和B都是已知集合，R是A到B的一個確定的二元關系，那么R就是AB的一個合于 R=(x,y)AB的子集合。按照定義4-1.1， xRy (x，y) R。 同理， xRy

8、(x，y) R。可以看出，采用集合表示關系便于對關系進行處理。定義4-1.1定義的二元關系可以很容易擴展到n元關系。例如： 存在于集合A1，A2，An的元素間的n元關系可以定義為： A1A2An的子集合。本課程著重討論二元關系。 8/6/202213計算機科學與工程學院例1：設A=1，2，B=2，3，4。定義關系R=(1,2),(2,2),(2,4),那么就有：1R2，2R2，2R4，但1R3， 1R4， 2R3。例2：設A=1，3，4，6，8 。定義R為A到A的模3同余關系，那么R=(1,1),(1,4),(3,3),(3,6),(4,1),(4,4),(6,3),(6,6),(8,8)。例

9、3：設A和B是兩個集合，那么AB的子集和AB自身是A到B的兩個二元關系，分別稱為空關系和全關系。8/6/202214計算機科學與工程學院例1：設A=1，2，B=2，3，4。定義關系R=(1,2),(2,2),(2,4),那么就有：1R2，2R2，2R4，但1R3， 1R4， 2R3。例2：設A=1，3，4，6，8 。定義R為A到A的模3同余關系，那么R=(1,1),(1,4),(3,3),(3,6),(4,1),(4,4),(6,3),(6,6),(8,8)。例3：設A和B是兩個集合，那么AB的子集和AB自身是A到B的兩個二元關系，分別稱為空關系和全關系。8/6/202215計算機科學與工程學

10、院例1：設A=1，2，B=2，3，4。定義關系R=(1,2),(2,2),(2,4),那么就有：1R2，2R2，2R4，但1R3， 1R4， 2R3。例2：設A=1，3，4，6，8 。定義R為A到A的模3同余關系，那么R=(1,1),(1,4),(3,3),(3,6),(4,1),(4,4),(6,3),(6,6),(8,8)。例3：設A和B是兩個集合，那么AB的子集和AB自身是A到B的兩個二元關系，分別稱為空關系和全關系。8/6/202216計算機科學與工程學院例4：在數(shù)據(jù)庫中，常將用表格的方式表示出來的文件看作是關系R，如下表是一個學生學籍管理的一個數(shù)據(jù)庫：則此時有關系RA1A2A6，其中

11、系別與班級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/202217計算機科學與工程學院關系的表示法1.集合表示法由于關系也是一種特殊的集合，所以集合的兩種基本的表示法也可以用到關系的表示中。即可用枚舉法和敘述法來表示關系。例5：設A2,B3,關系R如定義集合N上的“小于等于”關系：R|(x,yN)(xy)。8/6/202218計算機科學與工程學院關系的表示法1.集合表示法由于關系也是一種特殊的集合，所以集合

12、的兩種基本的表示法也可以用到關系的表示中。即可用枚舉法和敘述法來表示關系。例5：設A2,B3,關系R如定義集合N上的“小于等于”關系：R|(x,yN)(xy)。8/6/202219計算機科學與工程學院2.關系圖法（有向圖表示法）設Aa1,a2,a3,.,an,Bb1,b2,b3,.,bm，R是設a1,a2,a3,.,an和b1,b2,b3,.,bm分別為圖中的節(jié)點，用“?！北硎荆蝗鏡,則從ai到bj可用一有向邊aibj相連。為對應圖中的有向邊。從A到B的一個二元關系，則對應于關系R之關系圖有如下規(guī)定：如R是定義在A上的關系，則對應于關系R有如下規(guī)定：設a1,a2,.,an為圖中節(jié)點，用“。”表

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

14、j相連。為對應圖中的有向邊；如R,則從ai到ai用一帶箭頭的小圓環(huán)表示ai 8/6/202221計算機科學與工程學院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é)點，用“?！北硎尽Ｈ鏡,則從ai到aj可用一有向邊aiaj相連。為對應圖中的有向邊；如R,則從ai

15、到ai用一帶箭頭的小圓環(huán)表示ai 8/6/202222計算機科學與工程學院例6：設A是六個程序，考慮它們之間的一種調(diào)用關系R，如Pi可調(diào)用Pj,則有R,現(xiàn)假設R, 則此關系R的關系圖如下：8/6/202223計算機科學與工程學院例6：設A是六個程序，考慮它們之間的一種調(diào)用關系R，如Pi可調(diào)用Pj,則有R,現(xiàn)假設R, 則此關系R的關系圖如下：8/6/202224計算機科學與工程學院例6：2)設Aa1,a2,a3,a6是六個人，B1，2，3是三套房間，考慮A到B之間的一種住宿關系R，如ai住房間j,則有R,現(xiàn)假設：R, 則此關系R的關系圖如下：8/6/202225計算機科學與工程學院例6：2)設A

16、a1,a2,a3,a6是六個人，B1，2，3是三套房間，考慮A到B之間的一種住宿關系R，如ai住房間j,則有R,現(xiàn)假設：R, 則此關系R的關系圖如下：8/6/202226計算機科學與工程學院3.關系矩陣表示法 設Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm，R是從A到B的一個二元關系， 稱矩陣MR(rij)nm為關系R的關系矩陣或鄰接矩陣，其中：顯然，關系矩陣是布爾矩陣。注意 在寫關系矩陣時，首先應對集合A和B中的元素進行排序，不同的排序會得到不同的關系矩陣。當集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。 8/6/202227計算機科學與工程學院3

17、.關系矩陣表示法 設Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm，R是從A到B的一個二元關系， 稱矩陣MR(rij)nm為關系R的關系矩陣或鄰接矩陣，其中：顯然，關系矩陣是布爾矩陣。注意 在寫關系矩陣時，首先應對集合A和B中的元素進行排序，不同的排序會得到不同的關系矩陣。當集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。 8/6/202228計算機科學與工程學院例7：設A2，3，4，B1，2，4。考慮從A到B的“大于等于”關系R和“小于等于”關系S：R,，S,。寫出R，S的關系矩陣。解：8/6/202229計算機科學與工程學院例7：設A2，3，4，B1

18、，2，4?？紤]從A到B的“大于等于”關系R和“小于等于”關系S：R,，S,。寫出R，S的關系矩陣。解：8/6/202230計算機科學與工程學院4.2 關系的性質(zhì)1.自反性與反自反性定義4-1.3 設R是集合A上的二元關系，對任意的xA,都滿足R，則稱R是自反的，或稱R具有自反性，即R在A上是自反的(x)(xA)(R)=1對任意的xA,都滿足R，則稱R是反自反的，或稱R具有反自反性，即R在A上是反自反的(x)(xA)(R)=1 or (x)(xA)(R)=08/6/202231計算機科學與工程學院4.2 關系的性質(zhì)1.自反性與反自反性定義4-1.3 設R是集合A上的二元關系，對任意的xA,都滿足

19、R，則稱R是自反的，或稱R具有自反性，即R在A上是自反的(x)(xA)(R)=1對任意的xA,都滿足R，則稱R是反自反的，或稱R具有反自反性，即R在A上是反自反的(x)(xA)(R)=1 or (x)(xA)(R)=08/6/202232計算機科學與工程學院例8： 設A=a,b,c,d， R=,。因為A中每個元素x，都有R，所以R是自反的。R的關系圖R的關系矩陣8/6/202233計算機科學與工程學院例8：設A=a,b,c,d， R=,。因為A中每個元素x，都有R，所以R是自反的。R的關系圖R的關系矩陣8/6/202234計算機科學與工程學院例8：(續(xù)1)S=,。S的關系圖S的關系矩陣因為A中

20、每個元素x，都有S，所以S是反自反的。8/6/202235計算機科學與工程學院例8：(續(xù)1)S=,。S的關系圖S的關系矩陣因為A中每個元素x，都有S，所以S是反自反的。8/6/202236計算機科學與工程學院例8：(續(xù)2)T=,。因為A中有元素b，使T，所以T不是自反的；因為A中有元素a，使T，所以T不是反自反的。T的關系圖T的關系矩陣8/6/202237計算機科學與工程學院例8：(續(xù)2)T=,。因為A中有元素b，使T，所以T不是自反的；因為A中有元素a，使T，所以T不是反自反的。T的關系圖T的關系矩陣8/6/202238計算機科學與工程學院結論任何不是自反的關系未必一定是反自反的關系，反之亦

21、然。即存在既不是自反的也不是反自反的關系。表現(xiàn)在關系圖上：關系R是自反的，當且僅當其關系圖中每個結點都有環(huán)；關系R是反自反的，當且僅當其關系圖中每個結點都無環(huán)。表現(xiàn)在關系矩陣上：關系R是自反的，當且僅當其關系矩陣的主對角線上全為1；關系R是反自反的當且僅當其關系矩陣的主對角線上全為0。 8/6/202239計算機科學與工程學院結論任何不是自反的關系未必一定是反自反的關系，反之亦然。即存在既不是自反的也不是反自反的關系。表現(xiàn)在關系圖上：關系R是自反的，當且僅當其關系圖中每個結點都有環(huán)；關系R是反自反的，當且僅當其關系圖中每個結點都無環(huán)。表現(xiàn)在關系矩陣上：關系R是自反的，當且僅當其關系矩陣的主對角

22、線上全為1；關系R是反自反的當且僅當其關系矩陣的主對角線上全為0。 8/6/202240計算機科學與工程學院結論任何不是自反的關系未必一定是反自反的關系，反之亦然。即存在既不是自反的也不是反自反的關系。表現(xiàn)在關系圖上：關系R是自反的，當且僅當其關系圖中每個結點都有環(huán)；關系R是反自反的，當且僅當其關系圖中每個結點都無環(huán)。表現(xiàn)在關系矩陣上：關系R是自反的，當且僅當其關系矩陣的主對角線上全為1；關系R是反自反的當且僅當其關系矩陣的主對角線上全為0。 8/6/202241計算機科學與工程學院對稱性與反對稱性定義4-1.4 設R是集合A上的二元關系，對任意的x,yA，如果R，那么R，則稱關系R是對稱的，

23、或稱R具有對稱性，即R在A上是對稱的 (x)(y)(xA)(yA)(R)(R)=1對任意的x,yA，如果R且R，那么x=y，則稱關系R是反對稱的，或稱R具有反對稱性，即R在A上是反對稱的 (x)(y)(xA)(yA)(R)(R)(x=y)=18/6/202242計算機科學與工程學院對稱性與反對稱性定義4-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上是反對稱的 (x)(y)(xA

24、)(yA)(R)(R)(x=y)=18/6/202243計算機科學與工程學院例9：設A=a,b,c,d， R1=,R2=, R1的關系圖R1的關系矩陣是對稱的是反對稱的R2的關系圖R2的關系矩陣8/6/202244計算機科學與工程學院例9：設A=a,b,c,d， R1=,R2=, R1的關系圖R1的關系矩陣是對稱的是反對稱的R2的關系圖R2的關系矩陣8/6/202245計算機科學與工程學院例9：設A=a,b,c,d， R1=,R2=, R1的關系圖R1的關系矩陣是對稱的是反對稱的R2的關系圖R2的關系矩陣8/6/202246計算機科學與工程學院例9：設A=a,b,c,d， R1=,R2=, R

25、1的關系圖R1的關系矩陣是對稱的是反對稱的R2的關系圖R2的關系矩陣8/6/202247計算機科學與工程學院例9：(續(xù)1)R3=,R4=, 既不是對稱的，也不是反對稱的R3的關系圖R3的關系矩陣既是對稱的，也是反對稱的R4的關系圖R4的關系矩陣8/6/202248計算機科學與工程學院例9：(續(xù)1)R3=,R4=, 既不是對稱的，也不是反對稱的R3的關系圖R3的關系矩陣既是對稱的，也是反對稱的R4的關系圖R4的關系矩陣8/6/202249計算機科學與工程學院例9：(續(xù)1)R3=,R4=, 既不是對稱的，也不是反對稱的R3的關系圖R3的關系矩陣既是對稱的，也是反對稱的R4的關系圖R4的關系矩陣8/

26、6/202250計算機科學與工程學院例9：(續(xù)1)R3=,R4=, 既不是對稱的，也不是反對稱的R3的關系圖R3的關系矩陣既是對稱的，也是反對稱的R4的關系圖R4的關系矩陣8/6/202251計算機科學與工程學院結論任何不是對稱的關系未必一定是反對稱的關系，反之亦然。即存在既不是對稱的也不是反對稱的關系，也存在既是對稱的也是反對稱的關系。表現(xiàn)在關系圖上：關系R是對稱的當且僅當其關系圖中，任何一對結點之間，要么有方向相反的兩條邊，要么無任何邊；關系R是反對稱的當且僅當其關系圖中，任何一對結點之間，至多有一條邊。表現(xiàn)在關系矩陣上：關系R是對稱的當且僅當其關系矩陣為對稱矩陣，即rij=rji，i,j

27、=1,2, ,n；關系R是反對稱的當且僅當其關系矩陣為反對稱矩陣，即rijrji=0，i,j=1,2,n，ij。 8/6/202252計算機科學與工程學院結論任何不是對稱的關系未必一定是反對稱的關系，反之亦然。即存在既不是對稱的也不是反對稱的關系，也存在既是對稱的也是反對稱的關系。表現(xiàn)在關系圖上：關系R是對稱的當且僅當其關系圖中，任何一對結點之間，要么有方向相反的兩條邊，要么無任何邊；關系R是反對稱的當且僅當其關系圖中，任何一對結點之間，至多有一條邊。表現(xiàn)在關系矩陣上：關系R是對稱的當且僅當其關系矩陣為對稱矩陣，即rij=rji，i,j=1,2, ,n；關系R是反對稱的當且僅當其關系矩陣為反對

28、稱矩陣，即rijrji=0，i,j=1,2,n，ij。 8/6/202253計算機科學與工程學院結論任何不是對稱的關系未必一定是反對稱的關系，反之亦然。即存在既不是對稱的也不是反對稱的關系，也存在既是對稱的也是反對稱的關系。表現(xiàn)在關系圖上：關系R是對稱的當且僅當其關系圖中，任何一對結點之間，要么有方向相反的兩條邊，要么無任何邊；關系R是反對稱的當且僅當其關系圖中，任何一對結點之間，至多有一條邊。表現(xiàn)在關系矩陣上：關系R是對稱的當且僅當其關系矩陣為對稱矩陣，即rij=rji，i,j=1,2, ,n；關系R是反對稱的當且僅當其關系矩陣為反對稱矩陣，即rijrji=0，i,j=1,2,n，ij。 8

29、/6/202254計算機科學與工程學院傳遞性定義4-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/202255計算機科學與工程學院傳遞性定義4-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/202256計算機科學與工程學院例10: 模運算 mod： n mod d為d除n的余

30、數(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/202257計算機科學與工程學院結論表現(xiàn)在關系圖上：關系R是傳遞的當且僅當其關系圖中，任何三個結點x,y,z（可以相同）之間，若從x到y(tǒng)有一條邊存在，從y到z有一條邊存在，則從x到z一定有一條邊存在。表現(xiàn)在關系矩陣上：關系R是傳遞的當且僅當其關系矩陣中，對任意i、j和k 1,2,3,n，若rij=1且rjk=1，必有rik=1。8/6/202258計

31、算機科學與工程學院結論表現(xiàn)在關系圖上：關系R是傳遞的當且僅當其關系圖中，任何三個結點x,y,z（可以相同）之間，若從x到y(tǒng)有一條邊存在，從y到z有一條邊存在，則從x到z一定有一條邊存在。表現(xiàn)在關系矩陣上：關系R是傳遞的當且僅當其關系矩陣中，對任意i、j和k 1,2,3,n，若rij=1且rjk=1，必有rik=1。8/6/202259計算機科學與工程學院4.3 關系的運算1.關系的交、并、補、差運算 設R，S都是集合A到B的兩個關系，則：RS|(xRy)(xSy)RS|(xRy)(xSy) R-S=|(xRy)(xSy) |(xRy) RS= |RSRS 根據(jù)定義，由于AB是相對于R的全集，所

32、以AB-R,且RAB,R。8/6/202260計算機科學與工程學院例11：設Aa,b,c,B1,2，R,，S,，則：RSRSR-S8/6/202261計算機科學與工程學院例11：設Aa,b,c,B1,2，R,，S,，則：RSRSR-S,，；,；,AB-R。8/6/202262計算機科學與工程學院關系的復合運算定義4-3.2設R是一個從集合A到集合B的二元關系，S是從集合B到集合C的二元關系(也可簡單地描述為R：AB，S：BC)，則R與S的復合關系（合成關系）RS是從A到C的關系，并且：RS|(xA)(zC)(y)(yB)(xRy)(ySz)運算“”稱為復合運算。8/6/202263計算機科學與

33、工程學院復合關系的矩陣表示R與S的復合關系（合成關系）RS也可以用矩陣來表示。 設R，S都是集合A= a1，a2，a3，.，an上的二元關系，MR(rij)， MS(sij)， =(mij)則 =MR*MS 這里的“*”運算類似矩陣乘法運算，但須將元素間的乘法改成邏輯與，將加法改成邏輯或，即 mij=(ri1s1j)(ri2s2j) (rinsnj)8/6/202264計算機科學與工程學院例12： 設 R,S,，分別是定義為從AB和從BC的關系，其中ABC1,2,3,4。1）用集合方法求RS，SR，RR，SS。則：RS,；SR,；RR,；SS,。8/6/202265計算機科學與工程學院例12：

34、 設 R,S,，分別是定義為從AB和從BC的關系，其中ABC1,2,3,4。1）用集合方法求RS，SR，RR，SS。則：RS,；SR,；RR,；SS,。8/6/202266計算機科學與工程學院例12（續(xù)）：2）用關系圖求RS。 RSR。SABCAC1。1。11。12。2。22。23。3。33。34。4。44。48/6/202267計算機科學與工程學院例12（續(xù)）：3) 用關系矩陣求RS。MRS MR* MS*顯然，復合運算不具有可換性，即： RS SR。但是，復合運算具有可結合性。8/6/202268計算機科學與工程學院例12（續(xù)）：3) 用關系矩陣求RS。MRS MR* MS*顯然，復合運算

35、不具有可換性，即： RS SR。但是，復合運算具有可結合性。8/6/202269計算機科學與工程學院關系的冪設R是集合A上的二元關系，則可定義R的n次冪Rn（n0），該Rn也是A上的二元關系，定義如下：1.R0IA|aA；(恒等關系)2.R1R ；3.Rn+1RnRRRn。容易證明，RmRnRm+n,(Rm)nRmn。8/6/202270計算機科學與工程學院關系的逆運算定義4-3.3 設R是一個從集合A到集合B的二元關系，則從B到A的關系R-1|R稱為R的逆關系,運算“-1”稱為逆運算。注意：關系是一種集合，逆關系也是一種集合，因此，如果R是一個關系，則R-1和都是關系，但R-1和是完全不同的

36、兩種關系，千萬不要混淆。8/6/202271計算機科學與工程學院關系的逆運算定義4-3.3 設R是一個從集合A到集合B的二元關系，則從B到A的關系R-1|R稱為R的逆關系,運算“-1”稱為逆運算。注意：關系是一種集合，逆關系也是一種集合，因此，如果R是一個關系，則R-1和都是關系，但R-1和是完全不同的兩種關系，千萬不要混淆。8/6/202272計算機科學與工程學院例4.13設Aa,b,c,d,B1,2,3,R是從A到B的一個關系，R,，則：R-1如用關系圖表示逆關系，則僅將關系圖中的有向邊的方向改變成相反方向。如用關系矩陣表示逆關系，則MR-1MRT。,。8/6/202273計算機科學與工程

37、學院例4.13設Aa,b,c,d,B1,2,3,R是從A到B的一個關系，R,，則：R-1如用關系圖表示逆關系，則僅將關系圖中的有向邊的方向改變成相反方向。如用關系矩陣表示逆關系，則MR-1MRT。,。8/6/202274計算機科學與工程學院例4.13設Aa,b,c,d,B1,2,3,R是從A到B的一個關系，R,，則：R-1如用關系圖表示逆關系，則僅將關系圖中的有向邊的方向改變成相反方向。如用關系矩陣表示逆關系，則MR-1MRT。,。8/6/202275計算機科學與工程學院例4.13(續(xù))關系圖和關系矩陣如下：8/6/202276計算機科學與工程學院關系運算的性質(zhì)定理4-3.1設R,S,T分別是

38、從集合A到集合B，集合B到集合C，集合C到集合D的二元關系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(RS)T，則由復合運算知,至少存在cC,使得：RS，T。R(ST),又對于RS，則至少存一個bB，使得R，S。因此,由S,T,有ST，又由R和ST，知：所以(RS)TR(ST)。同理可證：R(ST)(RS)T。由集合性質(zhì)知：(RS)TR(ST)。(按定義證明）8/6/202277計算機科學與工程學院關系運算的性質(zhì)定理4-3.1設R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1

39、)設(RS)T，則由復合運算知,至少存在cC,使得：RS，T。R(ST),又對于RS，則至少存一個bB，使得R，S。因此,由S,T,有ST，又由R和ST，知：所以(RS)TR(ST)。同理可證：R(ST)(RS)T。由集合性質(zhì)知：(RS)TR(ST)。(按定義證明）8/6/202278計算機科學與工程學院關系運算的性質(zhì)定理4-3.1設R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(RS)T，則由復合運算知,至少存在cC,使得：RS，T。R(ST),又對于RS，則至少存一個bB，使得R，S。因此,由

40、S,T,有ST，又由R和ST，知：所以(RS)TR(ST)。同理可證：R(ST)(RS)T。由集合性質(zhì)知：(RS)TR(ST)。(按定義證明）8/6/202279計算機科學與工程學院關系運算的性質(zhì)定理4-3.1設R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(RS)T，則由復合運算知,至少存在cC,使得：RS，T。R(ST),又對于RS，則至少存一個bB，使得R，S。因此,由S,T,有ST，又由R和ST，知：所以(RS)TR(ST)。同理可證：R(ST)(RS)T。由集合性質(zhì)知：(RS)TR(ST

41、)。(按定義證明）8/6/202280計算機科學與工程學院關系運算的性質(zhì)定理4-3.1設R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(RS)T，則由復合運算知,至少存在cC,使得：RS，T。R(ST),又對于RS，則至少存一個bB，使得R，S。因此,由S,T,有ST，又由R和ST，知：所以(RS)TR(ST)。同理可證：R(ST)(RS)T。由集合性質(zhì)知：(RS)TR(ST)。(按定義證明）8/6/202281計算機科學與工程學院證明（續(xù)）2) 采用謂詞公式的等價式進行證明(RS)-1 RS （bB)RS （bB)R-1S-1 S-1R-1(RS)-1S-1R-1。 8/6/202282計算機科學與工程學院定理4-3.2設R是從集合A到集合B的關系，S1、S2是從集合B到集合C的關系，T是從集合C到集合D的關系，則：R(S1S2)(RS1)(RS2)R(S1S2)(RS1)(RS2)(S1S2)T(S