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

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

2、系。關(guān)系的概念應(yīng)用廣泛,在計算機科學(xué)中起著重要的作用,如數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)庫,數(shù)字邏輯,情報檢索,算法分析,編譯,人工智能等領(lǐng)域它都是很重要的數(shù)學(xué)工具。8/6/20224計算機科學(xué)與工程學(xué)院第四章 二元關(guān)系萬事萬物之間總可以根據(jù)需要確定相應(yīng)的關(guān)系。從數(shù)學(xué)的角度看，這類聯(lián)系就是某個集合中元素之間的關(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/20225計算機科學(xué)與

3、工程學(xué)院第四章 二元關(guān)系萬事萬物之間總可以根據(jù)需要確定相應(yīng)的關(guān)系。從數(shù)學(xué)的角度看，這類聯(lián)系就是某個集合中元素之間的關(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/20226計算機科學(xué)與工程學(xué)院41 二元關(guān)系及其表示關(guān)系是一個基本的概念,通俗地說,所謂關(guān)系,是指對象之間的相互聯(lián)系,它表征事物的結(jié)構(gòu)。如自然界中的“引力關(guān)系”,人與人之間的“父子關(guān)系”,“上下級關(guān)系

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

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

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

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

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

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

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

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

12、的兩種基本的表示法也可以用到關(guān)系的表示中。即可用枚舉法和敘述法來表示關(guān)系。例5：設(shè)A2,B3,關(guān)系R如定義集合N上的“小于等于”關(guān)系：R|(x,yN)(xy)。8/6/202219計算機科學(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é)點，用“?！北?/p>

13、示。如R,則從ai到aj可用一有向邊aiaj相連。為對應(yīng)圖中的有向邊；如R,則從ai到ai用一帶箭頭的小圓環(huán)表示ai 8/6/202220計算機科學(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é)點，用“?！北硎?。如R,則從ai到aj可用一有向邊aia

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

15、到ai用一帶箭頭的小圓環(huán)表示ai 8/6/202222計算機科學(xué)與工程學(xué)院例6：設(shè)A是六個程序，考慮它們之間的一種調(diào)用關(guān)系R，如Pi可調(diào)用Pj,則有R,現(xiàn)假設(shè)R, 則此關(guān)系R的關(guān)系圖如下：8/6/202223計算機科學(xué)與工程學(xué)院例6：設(shè)A是六個程序，考慮它們之間的一種調(diào)用關(guān)系R，如Pi可調(diào)用Pj,則有R,現(xiàn)假設(shè)R, 則此關(guān)系R的關(guān)系圖如下：8/6/202224計算機科學(xué)與工程學(xué)院例6：2)設(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/202225計算機科學(xué)與工程學(xué)院例6：2)設(shè)A

16、a1,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/202226計算機科學(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中的元素進行排序，不同的排序會得到不同的關(guān)系矩陣。當(dāng)集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。 8/6/202227計算機科學(xué)與工程學(xué)院3

17、.關(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中的元素進行排序，不同的排序會得到不同的關(guān)系矩陣。當(dāng)集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。 8/6/202228計算機科學(xué)與工程學(xué)院例7：設(shè)A2，3，4，B1，2，4?？紤]從A到B的“大于等于”關(guān)系R和“小于等于”關(guān)系S：R,，S,。寫出R，S的關(guān)系矩陣。解：8/6/202229計算機科學(xué)與工程學(xué)院例7：設(shè)A2，3，4，B1

18、，2，4?？紤]從A到B的“大于等于”關(guān)系R和“小于等于”關(guān)系S：R,，S,。寫出R，S的關(guān)系矩陣。解：8/6/202230計算機科學(xué)與工程學(xué)院4.2 關(guān)系的性質(zhì)1.自反性與反自反性定義4-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 or (x)(xA)(R)=08/6/202231計算機科學(xué)與工程學(xué)院4.2 關(guān)系的性質(zhì)1.自反性與反自反性定義4-1.3 設(shè)R是集合A上的二元關(guān)系，對任意的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計算機科學(xué)與工程學(xué)院例8： 設(shè)A=a,b,c,d， R=,。因為A中每個元素x，都有R，所以R是自反的。R的關(guān)系圖R的關(guān)系矩陣8/6/202233計算機科學(xué)與工程學(xué)院例8：設(shè)A=a,b,c,d， R=,。因為A中每個元素x，都有R，所以R是自反的。R的關(guān)系圖R的關(guān)系矩陣8/6/202234計算機科學(xué)與工程學(xué)院例8：(續(xù)1)S=,。S的關(guān)系圖S的關(guān)系矩陣因為A中

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

21、然。即存在既不是自反的也不是反自反的關(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/202239計算機科學(xué)與工程學(xué)院結(jié)論任何不是自反的關(guān)系未必一定是反自反的關(guān)系，反之亦然。即存在既不是自反的也不是反自反的關(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)系矩陣的主對角

22、線上全為1；關(guān)系R是反自反的當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上全為0。 8/6/202240計算機科學(xué)與工程學(xué)院結(jié)論任何不是自反的關(guān)系未必一定是反自反的關(guān)系，反之亦然。即存在既不是自反的也不是反自反的關(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/202241計算機科學(xué)與工程學(xué)院對稱性與反對稱性定義4-1.4 設(shè)R是集合A上的二元關(guān)系，對任意的x,yA，如果R，那么R，則稱關(guān)系R是對稱的，

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

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

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

26、6/202250計算機科學(xué)與工程學(xué)院例9：(續(xù)1)R3=,R4=, 既不是對稱的，也不是反對稱的R3的關(guān)系圖R3的關(guān)系矩陣既是對稱的，也是反對稱的R4的關(guān)系圖R4的關(guān)系矩陣8/6/202251計算機科學(xué)與工程學(xué)院結(jié)論任何不是對稱的關(guān)系未必一定是反對稱的關(guān)系，反之亦然。即存在既不是對稱的也不是反對稱的關(guān)系，也存在既是對稱的也是反對稱的關(guān)系。表現(xiàn)在關(guān)系圖上：關(guān)系R是對稱的當(dāng)且僅當(dāng)其關(guān)系圖中，任何一對結(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

27、=1,2, ,n；關(guān)系R是反對稱的當(dāng)且僅當(dāng)其關(guān)系矩陣為反對稱矩陣，即rijrji=0，i,j=1,2,n，ij。 8/6/202252計算機科學(xué)與工程學(xué)院結(jié)論任何不是對稱的關(guān)系未必一定是反對稱的關(guān)系，反之亦然。即存在既不是對稱的也不是反對稱的關(guān)系，也存在既是對稱的也是反對稱的關(guān)系。表現(xiàn)在關(guān)系圖上：關(guān)系R是對稱的當(dāng)且僅當(dāng)其關(guān)系圖中，任何一對結(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)系矩陣為反對

28、稱矩陣，即rijrji=0，i,j=1,2,n，ij。 8/6/202253計算機科學(xué)與工程學(xué)院結(jié)論任何不是對稱的關(guān)系未必一定是反對稱的關(guān)系，反之亦然。即存在既不是對稱的也不是反對稱的關(guān)系，也存在既是對稱的也是反對稱的關(guān)系。表現(xiàn)在關(guān)系圖上：關(guān)系R是對稱的當(dāng)且僅當(dāng)其關(guān)系圖中，任何一對結(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

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

30、數(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/202257計算機科學(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和k 1,2,3,n，若rij=1且rjk=1，必有rik=1。8/6/202258計

31、算機科學(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和k 1,2,3,n，若rij=1且rjk=1，必有rik=1。8/6/202259計算機科學(xué)與工程學(xué)院4.3 關(guān)系的運算1.關(guān)系的交、并、補、差運算 設(shè)R，S都是集合A到B的兩個關(guān)系，則：RS|(xRy)(xSy)RS|(xRy)(xSy) R-S=|(xRy)(xSy) |(xRy) RS= |RSRS 根據(jù)定義，由于AB是相對于R的全集，所

32、以AB-R,且RAB,R。8/6/202260計算機科學(xué)與工程學(xué)院例11：設(shè)Aa,b,c,B1,2，R,，S,，則：RSRSR-S8/6/202261計算機科學(xué)與工程學(xué)院例11：設(shè)Aa,b,c,B1,2，R,，S,，則：RSRSR-S,，；,；,AB-R。8/6/202262計算機科學(xué)與工程學(xué)院關(guān)系的復(fù)合運算定義4-3.2設(shè)R是一個從集合A到集合B的二元關(guān)系，S是從集合B到集合C的二元關(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/202263計算機科學(xué)與

33、工程學(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/202264計算機科學(xué)與工程學(xué)院例12： 設(shè) R,S,，分別是定義為從AB和從BC的關(guān)系，其中ABC1,2,3,4。1）用集合方法求RS，SR，RR，SS。則：RS,；SR,；RR,；SS,。8/6/202265計算機科學(xué)與工程學(xué)院例12：

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

35、不具有可換性，即： RS SR。但是，復(fù)合運算具有可結(jié)合性。8/6/202269計算機科學(xué)與工程學(xué)院關(guān)系的冪設(shè)R是集合A上的二元關(guān)系，則可定義R的n次冪Rn（n0），該Rn也是A上的二元關(guān)系，定義如下：1.R0IA|aA；(恒等關(guān)系)2.R1R ；3.Rn+1RnRRRn。容易證明，RmRnRm+n,(Rm)nRmn。8/6/202270計算機科學(xué)與工程學(xué)院關(guān)系的逆運算定義4-3.3 設(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)系，但R-1和是完全不同的

36、兩種關(guān)系，千萬不要混淆。8/6/202271計算機科學(xué)與工程學(xué)院關(guān)系的逆運算定義4-3.3 設(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)系，但R-1和是完全不同的兩種關(guān)系，千萬不要混淆。8/6/202272計算機科學(xué)與工程學(xué)院例4.13設(shè)Aa,b,c,d,B1,2,3,R是從A到B的一個關(guān)系，R,，則：R-1如用關(guān)系圖表示逆關(guān)系，則僅將關(guān)系圖中的有向邊的方向改變成相反方向。如用關(guān)系矩陣表示逆關(guān)系，則MR-1MRT。,。8/6/202273計算機科學(xué)與工程

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

38、從集合A到集合B，集合B到集合C，集合C到集合D的二元關(guān)系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(shè)(RS)T，則由復(fù)合運算知,至少存在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計算機科學(xué)與工程學(xué)院關(guān)系運算的性質(zhì)定理4-3.1設(shè)R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關(guān)系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1

39、)設(shè)(RS)T，則由復(fù)合運算知,至少存在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計算機科學(xué)與工程學(xué)院關(guān)系運算的性質(zhì)定理4-3.1設(shè)R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關(guān)系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(shè)(RS)T，則由復(fù)合運算知,至少存在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計算機科學(xué)與工程學(xué)院關(guān)系運算的性質(zhì)定理4-3.1設(shè)R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關(guān)系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(shè)(RS)T，則由復(fù)合運算知,至少存在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計算機科學(xué)與工程學(xué)院關(guān)系運算的性質(zhì)定理4-3.1設(shè)R,S,T分別是從集合A到集合B，集合B到集合C，集合C到集合D的二元關(guān)系，則：1)(RS)TR(ST)2)(RS)-1S-1R-1證明：1)設(shè)(RS)T，則由復(fù)合運算知,至少存在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計算機科學(xué)與工程學(xué)院證明（續(xù)）2) 采用謂詞公式的等價式進行證明(RS)-1 RS （bB)RS （bB)R-1S-1 S-1R-1(RS)-1S-1R-1。 8/6/202282計算機科學(xué)與工程學(xué)院定理4-3.2設(shè)R是從集合A到集合B的關(guān)系，S1、S2是從集合B到集合C的關(guān)系，T是從集合C到集合D的關(guān)系，則：R(S1S2)(RS1)(RS2)R(S1S2)(RS1)(RS2)(S1S2)T(S