第四章二元關(guān)系

第四章二元關(guān)系第1頁(yè)，共162頁(yè)，2023年，2月20日，星期三第四章二元關(guān)系4.1關(guān)系的基本概念4.2關(guān)系的性質(zhì)4.3關(guān)系的表示4.4關(guān)系的運(yùn)算4.5特殊關(guān)系第2頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.1關(guān)系的基本概念定義：任一序偶的集合確定一個(gè)二元關(guān)系R，R中任一序偶<x,y>可記作<x,y>∈R或xRy，稱為x與y有關(guān)系R。否則，記作或例

R1={<x,y>|x>y,x和y是實(shí)數(shù)}一、關(guān)系的定義第3頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系的定義定義：令X和Y是任意兩個(gè)集合，直積X×Y的子集R稱作X到Y(jié)的關(guān)系。X×Y有兩個(gè)平凡子集若

，則稱R為X到Y(jié)空關(guān)系若R=X×Y，則稱R為X到Y(jié)的全域關(guān)系當(dāng)X=Y時(shí)，關(guān)系R是直積X×X的子集，稱R為X上的二元關(guān)系。IX={<x,x>|x∈X}稱為X上的恒等關(guān)系。第4頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系的定義例：設(shè)集合A={a,b},B={2,5,8}則令則均是由A到B的關(guān)系。同理，則是由B到A的關(guān)系。同理，則是由B到B的關(guān)系。第5頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系的定義例：設(shè)集合A={2,3,5,9}，試給出集合A上的小于或等于關(guān)系，大于或等于關(guān)系。解：令集合A上的小于或等于關(guān)系為R1，大于或等于關(guān)系為R2，根據(jù)定義有：

第6頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系的定義定義：設(shè)且為n個(gè)任意集合，(a)稱R為間的n元關(guān)系；(b)若n=2，則稱R為A1到A2的二元關(guān)系；(c)若，則稱R為空關(guān)系；若，則稱R為全關(guān)系；(d)若，則稱R為A上的n元關(guān)系。第7頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系的定義例：令則稱R1是N上的一元關(guān)系，R2是N上的二元關(guān)系，R3是N上的三元關(guān)系。如無特殊指定，“關(guān)系”概指二元關(guān)系。第8頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系的相等定義：設(shè)R1為X到Y(jié)上的二元關(guān)系，R2為A到B上的二元關(guān)系，如果：（1）X=A

（2）Y=B（3）把R1和R2作為集合看，R1=R2。則稱二元關(guān)系R1和R2相等，記作R1=R2第9頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系的相等例：設(shè)R1為從Z到I+的二元關(guān)系，R2和R3都是I上的二元關(guān)系從集合的觀點(diǎn)來看，R1=R2=R3。但是就二元關(guān)系來說，R2=R3，不等于R1。第10頁(yè)，共162頁(yè)，2023年，2月20日，星期三三、關(guān)系的定義域和值域關(guān)系R(從A到B的關(guān)系)的定義域(簡(jiǎn)稱為域)定義為：關(guān)系R的值域定義為：顯然，有第11頁(yè)，共162頁(yè)，2023年，2月20日，星期三三、關(guān)系的定義域和值域例：設(shè)A={2,3,5},B={2,6,7,8,9}，由A到B的關(guān)系R定義為：當(dāng)且僅當(dāng)a整除b時(shí)，有aRb?？傻?D(R)={2,3}R(R)={2,6,8,9}AB第12頁(yè)，共162頁(yè)，2023年，2月20日，星期三第四章二元關(guān)系4.1關(guān)系的基本概念4.2關(guān)系的性質(zhì)4.3關(guān)系的表示4.4關(guān)系的運(yùn)算4.5特殊關(guān)系第13頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.2關(guān)系的性質(zhì)定義：設(shè)R為A上的二元關(guān)系(1)若對(duì)每個(gè)，皆有，則稱R為自反的。用式子來表述即是：R是自反的(2)若對(duì)每個(gè)，皆有，則稱R為反自反的。用式子來表述即是：R是反自反的

第14頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.2關(guān)系的性質(zhì)(3)對(duì)任意的

，若則，就稱R為對(duì)稱的。用式子來表述即是：R是對(duì)稱的(4)對(duì)任意的

，若且，則x=y，就稱R為反對(duì)稱的。用式子來表述即是：R是反對(duì)稱的

第15頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.2關(guān)系的性質(zhì)(5)對(duì)任意的

，若且則，就稱R為可傳遞的。用式子來表述即是：R是可傳遞的第16頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.2關(guān)系的性質(zhì)例1：考慮自然數(shù)集合上的普通相等關(guān)系“=”，大于關(guān)系“>”和大于等于關(guān)系“”具有的性質(zhì)。

解：(1)“=”關(guān)系是自反的、對(duì)稱的、反對(duì)稱的、可傳遞的；(2)“>”關(guān)系是反自反的、反對(duì)稱的、可傳遞的；(3)“”關(guān)系是自反的、反對(duì)稱的、可傳遞的。第17頁(yè)，共162頁(yè)，2023年，2月20日，星期三例:A={1,2,3},A上的關(guān)系:R1={<1,1><1,2><2,1>}R2={<1,3><1,2><2,3>}R3={<1,1><3,3>}R4={<1,1><2,2><3,3><1,2><1,3><2,1>}判斷以上關(guān)系各有哪些性質(zhì)。解：(1)既不是自反又不是反自反，是對(duì)稱的，不是傳遞的。(2)反自反的，反對(duì)稱的，傳遞的。第18頁(yè)，共162頁(yè)，2023年，2月20日，星期三(3)既不是自反又不是反自反的，既是對(duì)稱又是反對(duì)稱的，傳遞的。(4)是自反的，既不是對(duì)稱又不是反對(duì)稱的，不是傳遞的。自反與反自反不交，存在既不是自反又不是反自反的關(guān)系。對(duì)稱與反對(duì)稱相交，存在既是對(duì)稱又是反對(duì)稱的關(guān)系，也存在既不是對(duì)稱也不是反對(duì)稱的關(guān)系。第19頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.2關(guān)系的性質(zhì)例2：空集上的二元關(guān)系的性質(zhì)。對(duì)稱的、反對(duì)稱的、反自反的、可傳遞的第20頁(yè)，共162頁(yè)，2023年，2月20日，星期三集合的壓縮和開拓定義：設(shè)R為集合A上的二元關(guān)系且，則稱S上的二元關(guān)系為R在S上的壓縮，記為，并稱R為在A上的開拓。第21頁(yè)，共162頁(yè)，2023年，2月20日，星期三集合的壓縮和開拓定理：設(shè)R為A的二元關(guān)系且，那么：(1)若R是自反的，則也是自反的；(2)若R是反自反的，則也是反自反的；(3)若R是對(duì)稱的，則也是對(duì)稱的；(4)若R是反對(duì)稱的，則也是反對(duì)稱的；(5)若R是可傳遞的，則也是可傳遞的；第22頁(yè)，共162頁(yè)，2023年，2月20日，星期三第四章二元關(guān)系4.1關(guān)系的基本概念4.2關(guān)系的性質(zhì)4.3關(guān)系的表示4.4關(guān)系的運(yùn)算4.5特殊關(guān)系第23頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.3關(guān)系的表示定義：設(shè)A和B為任意的非空有限集，R為任意一個(gè)從A到B的二元關(guān)系。以中的每個(gè)元素為結(jié)點(diǎn)．對(duì)每個(gè)皆畫一條從x到y(tǒng)的有向邊，這樣得到的一個(gè)圖稱為關(guān)系R的關(guān)系圖。一、關(guān)系圖例：A={1,2,4};B={3,5,6};關(guān)系R={<1,3>,<2,6>,<2,5>}A124B356第24頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系圖例：設(shè)A={2,3,4,5,6},B={6,7,8,12}，從A到B的二元關(guān)系R為畫出其關(guān)系圖。解：先求出R第25頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系圖

對(duì)稱關(guān)系反對(duì)稱關(guān)系第26頁(yè)，共162頁(yè)，2023年，2月20日，星期三一、關(guān)系圖如果關(guān)系圖中每個(gè)結(jié)點(diǎn)上都有環(huán)，則R是自反的；

如果關(guān)系圖中每個(gè)結(jié)點(diǎn)上都沒有環(huán)，則R是反自反的；如果關(guān)系圖中兩頂點(diǎn)間有邊，必是一對(duì)方向相反的邊，則R是對(duì)稱的；如果關(guān)系圖中兩頂點(diǎn)間有邊，必是一條有向邊,則R是反對(duì)稱的；如果關(guān)系圖中頂點(diǎn)xi到xj有邊，xj到xk有邊，則xi到xk必有邊，則R是可傳遞的。第27頁(yè)，共162頁(yè)，2023年，2月20日，星期三例:判斷下圖中的關(guān)系分別具有哪些性質(zhì)。第28頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系矩陣定義：給定兩個(gè)有限集合X={x1,x2,…,xm}和Y={y1,y2,…,yn}，R是從X到Y(jié)的二元關(guān)系，如果有：

則稱[rij]m×n是R的關(guān)系矩陣，記作MR。

第29頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系矩陣?yán)涸O(shè)A={1,2,3},B={a,b,c},R是A到B的二元關(guān)系，并且，試畫出R的關(guān)系圖，給出關(guān)系矩陣。第30頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系矩陣。

例：設(shè)A={1,2,3,4},R為定義在A上的二元關(guān)系，R={<2,1>,<3,1>,<3,2>,<4,1>}，寫出關(guān)系矩陣。第31頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系矩陣如果關(guān)系矩陣主對(duì)角線上的記入值全為1，則R是自反的；

如果主對(duì)角線上的記入值全為0，則R是反自反的；如果矩陣關(guān)于主對(duì)角線是對(duì)稱的，則R是對(duì)稱的；如果矩陣關(guān)于主對(duì)角線是反對(duì)稱的，(亦即rij=1時(shí)則一定有rji=0),則R是反對(duì)稱的；第32頁(yè)，共162頁(yè)，2023年，2月20日，星期三二、關(guān)系矩陣如果對(duì)于任意的i,j,k,rij=1并且rjk=1時(shí)一定有rik=1，則R是可傳遞的；如果存在i,j,k,rij=1并且rjk=1時(shí)，有rik不等于1，則R是不可傳遞的；第33頁(yè)，共162頁(yè)，2023年，2月20日，星期三第四章二元關(guān)系4.1關(guān)系的基本概念4.2關(guān)系的性質(zhì)4.3關(guān)系的表示4.4關(guān)系的運(yùn)算4.5特殊關(guān)系第34頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4關(guān)系的運(yùn)算注意：由于關(guān)系也是特殊的集合，因此集合的運(yùn)算也適用于關(guān)系中。設(shè)R1和R2是從A到B的二元關(guān)系，那么也是從A到B的二元關(guān)系，它們分別被稱為二元關(guān)系R1和R2的交、并、差分和對(duì)稱差分。第35頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4關(guān)系的運(yùn)算例：設(shè)集合A={a,b,c}，B={d,e}，定義A到B的二元關(guān)系R1={<a,d>,<a,e>,<b,d>,<c,e>}R2={<a,d>,<b,e>,<c,d>}則第36頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4關(guān)系的運(yùn)算4.4.1關(guān)系的合成4.4.2關(guān)系的求逆運(yùn)算4.4.3關(guān)系的閉包運(yùn)算第37頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4.1關(guān)系的合成定義：設(shè)R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，于是可用R?S表示從X到Z的關(guān)系，通常稱它是R和S的合成關(guān)系，用式子表示即是：第38頁(yè)，共162頁(yè)，2023年，2月20日，星期三例：給定關(guān)系R和S，并且則第39頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的合成注意：設(shè)是R從集合X到集合Y的關(guān)系，S是從集合Y到集合Z的關(guān)系，于是有：如果R關(guān)系的值域與S關(guān)系的定義域的交集是個(gè)空集，則合成關(guān)系R?S也是個(gè)空關(guān)系；對(duì)于合成關(guān)系R?S來說，它的定義域是集合X的子集，而它的值域則是Z的子集，事實(shí)上，它的定義域是關(guān)系R的定義域的子集，它的值域是關(guān)系S的值域的子集。第40頁(yè)，共162頁(yè)，2023年，2月20日，星期三試求R和S的合成關(guān)系，并給出合成關(guān)系的關(guān)系矩陣。解:例：給定集合X={1,2,3,4}，Y={2,3,4}和Z={1,2,3}。設(shè)R是從X到Y(jié)的關(guān)系，并且S是從Y到Z的關(guān)系，并且R和S給定成：第41頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的合成第42頁(yè)，共162頁(yè)，2023年，2月20日，星期三合成關(guān)系的矩陣表達(dá)設(shè)集合X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp},R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，MR和MS第i行第j列的元素分別是aij和bij，它們是0或者1。則合成關(guān)系關(guān)系矩陣上的元素為定義布爾運(yùn)算：0+0=0，1+0=0+1=1+1=11?1=1，0?1=1?0=0?0=0對(duì)兩個(gè)關(guān)系矩陣求其合成時(shí)，其運(yùn)算法則與一般矩陣的乘法是相同的，但其中的加法運(yùn)算和乘法運(yùn)算應(yīng)改為布爾加和布爾乘。第43頁(yè)，共162頁(yè)，2023年，2月20日，星期三合成關(guān)系的矩陣表達(dá)和圖解例：求合成關(guān)系的關(guān)系矩陣第44頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的合成定理：給定集合X,Y,Z和W，設(shè)R1是從X到Y(jié)的關(guān)系，R2和R3是Y到Z的關(guān)系，R4是從Z到W的關(guān)系，于是有：第45頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的合成證明：任取元素當(dāng)且僅當(dāng)存在某一個(gè)能使和第46頁(yè)，共162頁(yè)，2023年，2月20日，星期三證明：任取元素當(dāng)且僅當(dāng)存在某一個(gè)能使和關(guān)系的合成第47頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的合成

合成運(yùn)算是對(duì)關(guān)系的二元運(yùn)算，使用這種運(yùn)算，能夠由兩個(gè)關(guān)系生成一個(gè)新的關(guān)系，對(duì)于這個(gè)新的關(guān)系又可進(jìn)行合成運(yùn)算，從而生成其它關(guān)系。

定理：設(shè)R1是從X到Y(jié)的關(guān)系，R2是從Y到Z的關(guān)系，R3是從Z到W的關(guān)系，于是有第48頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的合成第49頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的冪定義：給定集合X，R是X中的二元關(guān)系。設(shè)，于是R的n次冪Rn可定義成

(a)R0是集合X中的恒等關(guān)系IX，亦即(b)

第50頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的冪定理：給定集合X，R是X中的二元關(guān)系。設(shè)，于是可有例：給定集合X={a,b,c}，R1,R2,R3,R4是X中的關(guān)系，并給定給出這些關(guān)系的各次冪第51頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的冪解：第52頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的冪定理：設(shè)X是含有n個(gè)元素的有限集合，R是X中的二元關(guān)系。于是存在這樣的s和t，能使，證明：集合X中的每一個(gè)二元關(guān)系都是

的子集，X有n個(gè)元素，有n2個(gè)元素，有個(gè)元素，每一個(gè)元素都是的一個(gè)子集，也是一種二元關(guān)系，因而，在X中有個(gè)不同的二元關(guān)系。所以，不同的二元關(guān)系R的冪不會(huì)多于個(gè)。但是序列中有項(xiàng)，因此這些的方冪中至少有兩個(gè)是相等的。證畢。

第53頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4關(guān)系的運(yùn)算4.4.1關(guān)系的合成4.4.2關(guān)系的求逆運(yùn)算4.4.3關(guān)系的閉包運(yùn)算第54頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4.2關(guān)系的求逆運(yùn)算定義：設(shè)R是從X到Y(jié)的關(guān)系，將R中每一序偶元素次序互換得到的集合稱為R的逆關(guān)系，記作Rc，即Rc={<y,x>|<x,y>∈R}例：設(shè)集合X={1,2,3,4},Y={a,b,c},R是集合X到Y(jié)二元關(guān)系，R={<1,a><2,b><3,c>}

則Rc={<a,1><b,2><c,3>}逆關(guān)系的關(guān)系矩陣：原關(guān)系矩陣轉(zhuǎn)置逆關(guān)系的關(guān)系圖：原關(guān)系圖中顛倒弧線上箭頭的方向。第55頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的求逆運(yùn)算定理：給定集合X和Y，R、R1、R2是從X到Y(jié)的關(guān)系，于是有：第56頁(yè)，共162頁(yè)，2023年，2月20日，星期三(a)(Rc)c=R證明：設(shè)是R的任意元素。于是所以有(Rc)c=R。

關(guān)系的求逆運(yùn)算第57頁(yè)，共162頁(yè)，2023年，2月20日，星期三(b)(R1∪R2)c=R1c∪R2c證明：關(guān)系的求逆運(yùn)算得證第58頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的求逆運(yùn)算證明：得證。第59頁(yè)，共162頁(yè)，2023年，2月20日，星期三證明：因?yàn)椋谑怯嘘P(guān)系的求逆運(yùn)算得證。第60頁(yè)，共162頁(yè)，2023年，2月20日，星期三合成關(guān)系的求逆運(yùn)算定理：設(shè)R是從集合X到Y(jié)的關(guān)系。S是從集合Y到Z的關(guān)系。于是有(R○S)c=Sc○Rc證明：對(duì)于任何<z,x>∈(R○S)c利用關(guān)系矩陣也可以理解，的轉(zhuǎn)置和是一樣的。第61頁(yè)，共162頁(yè)，2023年，2月20日，星期三合成關(guān)系的求逆運(yùn)算例：給定關(guān)系矩陣MR和MS。則：第62頁(yè)，共162頁(yè)，2023年，2月20日，星期三定理：設(shè)R是集合X中的關(guān)系，a)R自反的，當(dāng)且僅當(dāng)IXRb)R反自反的，當(dāng)且僅當(dāng)IX∩R=c)R是對(duì)稱的，當(dāng)且僅當(dāng)

R=Rcd)R是反對(duì)稱的，當(dāng)且僅當(dāng)

R∩RcIX

e)R是可傳遞的，當(dāng)且僅當(dāng)R○RR利用關(guān)系的運(yùn)算判定關(guān)系的性質(zhì)第63頁(yè)，共162頁(yè)，2023年，2月20日，星期三即RRc；證明:c)(充分性)若R=Rc則即R是對(duì)稱的。(必要性)設(shè)R是對(duì)稱的，那么對(duì)任何對(duì)任何即Rc

R必要性證明完畢。第64頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系運(yùn)算對(duì)性質(zhì)的影響自反性反自反對(duì)稱性反對(duì)稱可傳遞RC√√√√√R1∩R2√√√√√R1∪R2√√√××R1-R2×√√√×R1○R2√××××第65頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4關(guān)系的運(yùn)算4.4.1關(guān)系的合成4.4.2關(guān)系的求逆運(yùn)算4.4.3關(guān)系的閉包運(yùn)算第66頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.4.3關(guān)系的閉包運(yùn)算閉包的定義：給定集合X，R是X中的二元關(guān)系。如果有另一個(gè)關(guān)系滿足

（1）是自反的(對(duì)稱的、可傳遞的)；（2）（3）對(duì)于任何自反的(對(duì)稱的、可傳遞的)關(guān)系，如果，則則稱關(guān)系為R的自反的(對(duì)稱的，可傳遞的)閉包。并用r(R)表示的R自反閉包，用s(R)表示R的對(duì)稱閉包，用t(R)表示R的可傳遞閉包。

第67頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算定理：給定集合X，R是X中的關(guān)系。于是可有(a)當(dāng)且僅當(dāng)，R才是自反的。(b)當(dāng)且僅當(dāng)，R才是對(duì)稱的。(c)當(dāng)且僅當(dāng)，R才是傳遞的。

第68頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算定理：設(shè)X是任意集合，R是X中的二元關(guān)系，IX是X中的恒等關(guān)系。于是可有在整數(shù)集合中，小于關(guān)系“<”的自反閉包是“≤”；恒等關(guān)系IX的自反閉包是IX。不等關(guān)系“≠”的自反閉包是全域關(guān)系；空關(guān)系的自反閉包是恒等關(guān)系。

第69頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算定理：給定集合X，R是X中的二元關(guān)系。于是可有

在整數(shù)集合中，小于關(guān)系“<”的對(duì)稱閉包是不等關(guān)系“≠”；小于或等于關(guān)系“≤”的對(duì)稱閉包是全域關(guān)系；恒等關(guān)系IX的對(duì)稱閉包是IX；不等關(guān)系“≠”的對(duì)稱閉包是不等關(guān)系“≠”。第70頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算定理：給定集合X，R是X中的二元關(guān)系。于是可有第71頁(yè)，共162頁(yè)，2023年，2月20日，星期三例：設(shè)A={a,b,c},R是A上的二元關(guān)系，R={<a,b><b,c><c,a>}求r(R),s(R),t(R)。解：r(R)=R∪IX={<a,b><b,c><c,a><a,a><b,b><c,c>}s(R)=R∪RC

={<a,b><b,c><c,a><b,a><c,b><a,c>}t(R)=R∪R2∪

R3∪…=R∪R2∪

R3={<a,b><b,c><c,a><b,a><c,b><a,c><a,a><b,b><c,c>}第72頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算當(dāng)A是有限集時(shí)，A上只有有限個(gè)不同的關(guān)系，因此，若，則第73頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系圖求閉包r(R)：在R的關(guān)系圖中，把沒有環(huán)的結(jié)點(diǎn)上加上環(huán)，其它不變。S(R)：在R的關(guān)系圖中，把單向邊改為雙向邊，其它不變。t(R)：在R的關(guān)系圖中，對(duì)每個(gè)結(jié)點(diǎn)

x，分別找出可以到達(dá)的終點(diǎn)y，若x到y(tǒng)沒有有向邊，則添加一條有向邊，直到添加完畢。第74頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣求閉包r(R)：s(R)：t(R)：第75頁(yè)，共162頁(yè)，2023年，2月20日，星期三Warshall算法（1）A：=M；（2）i：=1；（3）對(duì)所有j，如果A[j,i]=1，則對(duì)k=1,2,…,nA[j,k]=A[j,k]+A[i,k];（4）i加1；（5）如果i≤n，則轉(zhuǎn)到步驟（3），否則停止。第76頁(yè)，共162頁(yè)，2023年，2月20日，星期三例：設(shè)A={a,b,c},R是A上的二元關(guān)系，R={<a,b><b,c><c,a>}求t(R)。解：t(R)=R∪R2∪

R3∪…=R∪R2∪

R3={<a,b><b,c><c,a><b,a><c,b><a,c><a,a><b,b><c,c>}第77頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算定理：設(shè)X是集合，R是X中的二元關(guān)系，于是有（1）如果R是自反的，那么s(R),t(R)也是自反的；（2）如果R是對(duì)稱的，那么r(R),t(R)也是對(duì)稱的；（3）如果R是可傳遞的，那么r(R)也是可傳遞的。第78頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算證明（1）：若R是自反的，則對(duì)于所有的

都有

即s(R),t(R)是自反的第79頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算證明(2):若R是對(duì)稱的，則對(duì)于任何<x,y>∈R都有<y,x>∈R，則<x,y>∈R∪IX

及<y,x>∈R∪IX，即r(R)是對(duì)稱的。又因?yàn)榭芍猼(R)也是對(duì)稱的，得證。第80頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算證明（3）：若R是可傳遞的，即當(dāng)時(shí)有，假定存在討論四種情況第81頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算定理：設(shè)X是集合，R是集合中的二元關(guān)系，于是有證明：第82頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算證明（b）：因?yàn)?，，而?duì)于所有的有，以及。根據(jù)這些關(guān)系式，可有于是第83頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算證明（c）：如果，則，根據(jù)對(duì)稱閉包的定義，有。首先構(gòu)成上式兩側(cè)的可傳遞閉包，再依次構(gòu)成兩側(cè)的對(duì)稱閉包,可以求得以及。而ts(R)是對(duì)稱的，所以，從而有。第84頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系的閉包運(yùn)算注意：（1）通常用R+表示R的可傳遞閉包t(R)，并讀作“R加”。（2）通常用R*表示R的自反可傳遞閉包tr(R)，并讀作“R星”。第85頁(yè)，共162頁(yè)，2023年，2月20日，星期三第四章二元關(guān)系4.1關(guān)系的基本概念4.2關(guān)系的性質(zhì)4.3關(guān)系的表示4.4關(guān)系的運(yùn)算4.5特殊關(guān)系第86頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5特殊關(guān)系4.5.1集合的劃分和覆蓋4.5.2等價(jià)關(guān)系4.5.3相容關(guān)系4.5.4次序關(guān)系4.5.5偏序集合與哈斯圖第87頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5.1集合的劃分和覆蓋定義：給定非空集合S，設(shè)非空集合A={A1,A2,…,An}，如果有則稱集合A是集合S的覆蓋。注意：集合的覆蓋不唯一。例如：S={a,b,c}，A={{a,b},{b,c}}，B={{a},{b,c}}，A和B都是集合S的覆蓋。第88頁(yè)，共162頁(yè)，2023年，2月20日，星期三集合的劃分和覆蓋定義：給定非空集合S，設(shè)非空集合A={A1,A2,…,An}，如果有則稱集合A是集合S的一個(gè)劃分。例如：S={a,b,c}，A={{a,b},{c}}，B={{a},{b,c}}，A和B都是集合S的劃分。第89頁(yè)，共162頁(yè)，2023年，2月20日，星期三集合的劃分和覆蓋劃分中的元素Ai稱為劃分的類。劃分的類的數(shù)目叫劃分的秩。劃分是覆蓋的特定情況，即中元素互不相交的特定情況。集合的劃分不唯一。第90頁(yè)，共162頁(yè)，2023年，2月20日，星期三集合的劃分和覆蓋例：設(shè)S={1,2,3}，考慮下列集合S的覆蓋S的覆蓋S的覆蓋、劃分，秩為2S的覆蓋、劃分，秩為1，最小劃分S的覆蓋、劃分，秩為3，最大劃分第91頁(yè)，共162頁(yè)，2023年，2月20日，星期三定義:若{A1,A2,…Ar}與{B1,B2,…,Bs}是同一集合A的兩種劃分,則其中所有Ai∩Bj≠組成的集合，稱為是原來兩種劃分的交叉劃分。定理：{A1,A2,…Ar}與{B1,B2,…,Bs}是同一集合A的兩種劃分，則其交叉劃分亦是原集合的一種劃分。第92頁(yè)，共162頁(yè)，2023年，2月20日，星期三定義:若{A1,A2,…Ar}與{B1,B2,…,Bs}是同一集合A的兩種劃分,若對(duì)每一個(gè)Ai都有Bj使AiBj，則{A1,A2,…Ar}稱為是{B1,B2,…,Bs}的加細(xì)。定理：任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。第93頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5特殊關(guān)系4.5.1集合的劃分和覆蓋4.5.2等價(jià)關(guān)系4.5.3相容關(guān)系4.5.4次序關(guān)系4.5.5偏序集合與哈斯圖第94頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5.2等價(jià)關(guān)系定義：設(shè)X是任意集合,R是集合中的二元關(guān)系。如果R是自反的、對(duì)稱的和可傳遞的，則稱R是等價(jià)關(guān)系。即滿足以下幾點(diǎn)：如果R是集合X中的等價(jià)關(guān)系，則R的域是集合X自身，所以稱R是定義于集合X中的關(guān)系。第95頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5.2等價(jià)關(guān)系例如

數(shù)的相等關(guān)系是任何數(shù)集上的等價(jià)關(guān)系。

又例如一群人的集合中姓氏相同的關(guān)系也是等價(jià)關(guān)系。但朋友關(guān)系不是等價(jià)關(guān)系，因?yàn)樗豢蓚鬟f。

第96頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系例：給定集合X={1,2,…,7}，R是X中的二元關(guān)系，并且給定成試證明R是等價(jià)關(guān)系。解：R的關(guān)系矩陣如下：第97頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系R的關(guān)系圖如下：第98頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系注意：上例是模數(shù)系統(tǒng)中模等價(jià)關(guān)系的特定情況。設(shè)R+是正整數(shù)集合，m是個(gè)正整數(shù)。對(duì)于來說，可將R定義成。這里，“x-y可被m整除”等價(jià)于命題“當(dāng)用m去除x和y時(shí)，它們都有同樣的余數(shù)”。故關(guān)系R也稱為模m同余關(guān)系。第99頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系定理：任何集合中的模m相等關(guān)系，是一個(gè)等價(jià)關(guān)系。證明：要證明R是個(gè)等價(jià)關(guān)系，就必須證明R是自反的、對(duì)稱的和可傳遞的。(1)對(duì)于任何來說，因?yàn)閤-x=0?m，所以有。因此，模m相等關(guān)系是自反的。第100頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系(2)對(duì)于任何來說，如果，則存在某一個(gè)，能使x-y=n?m。于是可有y-x=(-n)?m，因此有，即模m相等關(guān)系是對(duì)稱的。(3)設(shè)，和。于是存在，能使和。而，從而可有，即模m相等關(guān)系是可傳遞的。第101頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)類定義：設(shè)是集合A上的等價(jià)關(guān)系，則A

中等價(jià)于元素的所有元素組成的集合稱為生成的等價(jià)類，用表示，即定義：設(shè)R是集合A上的等價(jià)關(guān)系，若元素aRb，則稱a與b等價(jià)，或稱b與a等價(jià)。第102頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)類例：設(shè)X={a,b,c,d}，R是X中的等價(jià)關(guān)系，并把R給定成則：第103頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)類的性質(zhì)1.對(duì)任意

,因?yàn)閷?duì)于任意的∈X,有，所以

設(shè)X是一集合，R是X上的等價(jià)關(guān)系2.如果，則3.對(duì)于所有的，或者，或者證明：分兩種情況討論(1)xRy(2)xR'y第104頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)類的性質(zhì)(1)xRy故。類似地可以證明由上得若，則xRz

，

由R的對(duì)稱性有zRx，

又由R的傳遞性有zRy

，因此(2)xR'y假設(shè),因此有且，故于是由xRz,zRb，得xRy，與xR'y相矛盾第105頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)類的性質(zhì)4.證明：假定，對(duì)于某個(gè)，有。由于，會(huì)有，因而。設(shè)，于是因而

證畢。第106頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)類的性質(zhì)例

設(shè)A={a,b,c,d}，A上的關(guān)系R是A上的等價(jià)關(guān)系

同一個(gè)等價(jià)類中元素均相互等價(jià)。不同等價(jià)類中的元素互不等價(jià)。由A的各元素所生成的等價(jià)類必定覆蓋A，決定了集合A的一種劃分。第107頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分定理：設(shè)R是非空集合X中的等價(jià)關(guān)系。R的等價(jià)類的集合X/R=，是X的一個(gè)劃分。

定義：設(shè)R是非空集合X中的等價(jià)關(guān)系。R的各元素生成的等價(jià)類集合叫按R去劃分X的商集，記作X/R。第108頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分例：設(shè)X={a,b,c,d}，R是X中的等價(jià)關(guān)系，并把R給定義成則：集合X的一個(gè)劃分為{[a]R,[c]R}即{{a,b},{c,d}}第109頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分例

設(shè)X={a,b,c,d}，X上的關(guān)系R是X上的等價(jià)關(guān)系集合X的一個(gè)劃分為{[a]R,[d]R}即{{a,b,c},7vvx1lp}可以看出，給定集合的一個(gè)等價(jià)關(guān)系，就可以寫出一種劃分。第110頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分例：令R是整數(shù)集合I中的“模3同余”關(guān)系，R可給定成求I的元素所生成的R等價(jià)類。解：等價(jià)類是可以看出，等價(jià)關(guān)系可以構(gòu)造集合的一個(gè)劃分。

第111頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分定理：設(shè)C是非空集合X的一個(gè)劃分，則由這個(gè)劃分所確定的下述關(guān)系R必定是個(gè)等價(jià)關(guān)系，并稱R為由C劃分導(dǎo)出的X中的等價(jià)關(guān)系。

證明：要證明R是個(gè)等價(jià)關(guān)系，就必須證明R是自反的、對(duì)稱的和可傳遞的。(a)由于C是X的劃分，C必定覆蓋X。對(duì)任意的，必有X屬于C的某一個(gè)元素S。所以對(duì)于每一個(gè)，都有xRx，即R是自反的。第112頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分證明：（b）假定xRy。于是存在一個(gè)，且和，所以有yRx。因此，R是對(duì)稱的。（c）假定xRy和yRz。于是存在兩個(gè)元素和，且和，所以有。這樣就有S1=S2，因此，。從而xRz，所以有R是可傳遞的。綜上，R是個(gè)等價(jià)關(guān)系。證畢。第113頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分例：設(shè)X={a,b,c,d,e}和C={{a,b},{c},{d,e}}。試寫出由劃分C導(dǎo)出的X中的等價(jià)關(guān)系。解：用R表示這個(gè)等價(jià)關(guān)系，（每一個(gè)類做笛卡爾乘積）注意：集合中的等價(jià)關(guān)系能夠生成該集合的劃分，反過來集合中的任何一種劃分又能確定一種等價(jià)關(guān)系。

第114頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分定理：設(shè)R1和R2為非空集合A上的等價(jià)關(guān)系，則R1=R2，當(dāng)且僅當(dāng)A/R1=A/R2。即集合A上的等價(jià)關(guān)系與集合A的劃分一一對(duì)應(yīng)。

第115頁(yè)，共162頁(yè)，2023年，2月20日，星期三等價(jià)關(guān)系與集合的劃分有時(shí)，用不同的方法定義的兩種等價(jià)關(guān)系，可能會(huì)產(chǎn)生同一個(gè)劃分。例如，設(shè)集合X={1,2,…,9}，R1和R2是X中的兩種關(guān)系，并把R1和R2規(guī)定成兩者雖然定義不同，但是R1=R2“劃分”的概念和“等價(jià)關(guān)系”的概念本質(zhì)上是相同的。

第116頁(yè)，共162頁(yè)，2023年，2月20日，星期三特殊的等價(jià)關(guān)系全域關(guān)系：令等價(jià)關(guān)系R1=XX，這里X的每一個(gè)元素與X的所有元素都有R1的關(guān)系。按R1劃分X的商集乃是集合{X}。等價(jià)關(guān)系R1是全域關(guān)系。全域關(guān)系會(huì)造成集合X的最小劃分。

例:設(shè)X={1,2},R是X上的全域關(guān)系R={<1,1><1,2><2,1><2,2>}則[1]R=[2]R={1,2}

商集X/R={{1，2}}={X}最小劃分第117頁(yè)，共162頁(yè)，2023年，2月20日，星期三特殊的等價(jià)關(guān)系恒等關(guān)系R：X的每一個(gè)元素僅關(guān)系到它自身，而不關(guān)系到其它元素。顯然，R是個(gè)恒等關(guān)系。按R劃分X的商集，僅由單元素集合組成。恒等關(guān)系R會(huì)造成集合X的最大劃分。這些劃分均稱作X的平凡劃分。例:設(shè)X={1,2},R是X上的恒等關(guān)系R={<1,1><2,2>}則[1]R={1}，[2]R={2}

商集X/R={{1}，{2}}最大劃分第118頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5特殊關(guān)系4.5.1集合的劃分和覆蓋4.5.2等價(jià)關(guān)系4.5.3相容關(guān)系4.5.4次序關(guān)系4.5.5偏序集合與哈斯圖第119頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5.3相容關(guān)系定義：給定集合X中的二元關(guān)系R，如果R是自反的，對(duì)稱的，則稱R是相容關(guān)系，記作r。也就是說，可以把R規(guī)定成：顯然，所有的等價(jià)關(guān)系都是相容關(guān)系，但相容關(guān)系并不一定是等價(jià)關(guān)系。

第120頁(yè)，共162頁(yè)，2023年，2月20日，星期三相容關(guān)系例如，設(shè)集合X={2166,243,375,648,455}，X中的關(guān)系可以看出R是自反的和對(duì)稱的，因此是一相容關(guān)系。令x1=2166,x2=243,x3=375,x4=648,x5=455，則x1Rx2,x2Rx3，但是x1R‘x3，可以看出相容關(guān)系不一定是可傳遞的。第121頁(yè)，共162頁(yè)，2023年，2月20日，星期三相容關(guān)系的表示在相容關(guān)系中，如果有xRy，則稱x和y是相容的。例如前面的例子中，X={2166,243,375,648,455}，令x1=2166,x2=243,x3=375,x4=648,x5=455把R寫出來是第122頁(yè)，共162頁(yè)，2023年，2月20日，星期三相容關(guān)系的表示R的關(guān)系矩陣如下由于相容關(guān)系是自反的，因而矩陣對(duì)角線上的各元素都應(yīng)是l；相容關(guān)系是對(duì)稱的，所以矩陣關(guān)于主對(duì)角線也是對(duì)稱的。這樣，僅給出關(guān)系矩陣下部的三角形部分也就夠了。第123頁(yè)，共162頁(yè)，2023年，2月20日，星期三相容關(guān)系的表示R的關(guān)系圖如下由于相容關(guān)系的自反性和對(duì)稱性，關(guān)系圖中的所有結(jié)點(diǎn)上都有環(huán)邊；有相容關(guān)系的兩個(gè)結(jié)點(diǎn)間都有往返弧線。如果找們刪除全部結(jié)點(diǎn)上的環(huán)邊，并且用一條直線取代兩結(jié)點(diǎn)間的兩條弧線，這樣就可以把圖簡(jiǎn)化第124頁(yè)，共162頁(yè)，2023年，2月20日，星期三最大相容類定義：設(shè)r是集合X中的相容關(guān)系，如果且對(duì)于A中任意兩個(gè)元素a1和a2有a1ra2，則稱A是由相容關(guān)系r產(chǎn)生的相容類。定義：設(shè)r是集合X中的相容關(guān)系，不能真包含在任何其他相容類中的相容類，稱作最大相容類，記作Cr。X-Cr中沒有任何元素與Cr所有元素有相容關(guān)系第125頁(yè)，共162頁(yè)，2023年，2月20日，星期三最大相容類設(shè)集合X={2166,243,375,648,455}，X中的關(guān)系令x1=2166,x2=243,x3=375,x4=648,x5=455，則{x1,x2},

{x1,x2,x4},{x2,x3},{x2,x3,x5},{x2,x4,x5}都是相容類而{x1,x2,x4},{x2,x3,x5},{x2,x4,x5}是最大相容類第126頁(yè)，共162頁(yè)，2023年，2月20日，星期三最大相容類尋找最大相容類的方法：關(guān)系圖法關(guān)系矩陣法第127頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系圖法尋找最大相容類關(guān)系圖法的實(shí)質(zhì)在于尋找出“最大完全多邊形”。所謂最大完全多邊形，系指每一個(gè)頂點(diǎn)都與其它所有頂點(diǎn)相連結(jié)的多邊形。集合中僅關(guān)系到它自身的結(jié)點(diǎn)，是一個(gè)最大完全多邊形。不都與其它的結(jié)點(diǎn)相連接的一條直線所連接的兩個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)最大完全多邊形。三角形的三個(gè)頂點(diǎn)構(gòu)成一個(gè)最大完全多邊形，對(duì)角線相連的四邊形的四個(gè)頂點(diǎn)構(gòu)成一個(gè)最大完全多邊形，正五角星的五個(gè)頂點(diǎn)構(gòu)成一個(gè)最大完全多邊形，正六邊形的六個(gè)頂點(diǎn)也是一個(gè)最大完全多邊形。一個(gè)最大完全多邊形對(duì)應(yīng)一個(gè)最大相容類。第128頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系圖法尋找最大相容類三角形x1x2x4,x2x3x5,x2x4x5是最大完全多變形；與他們對(duì)應(yīng)的最大相容類是X1={x1,x2,x4},X2={x2,x3,x5},X3={x2,x4,x5}第129頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系圖法尋找最大相容類例：下圖中，給出了兩個(gè)相容關(guān)系圖。試求出它們的所有最大完全多邊形,并求出與它們相應(yīng)的最大相容類。最大完全多邊形有：四邊形1234線段25，36和56；與它們相應(yīng)的最大相容類分別是：{1，2，3，4}，{2，5}，{3，6}，{5，6}。第130頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系圖法尋找最大相容類最大完全多邊形有：三角形123，136，356和孤立結(jié)點(diǎn)4；與它們相對(duì)應(yīng)的最大相容類分別是：{1，2，3}，{1，3，6}，{3，5，6}和{4}。第131頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類首先制定簡(jiǎn)化了的關(guān)系矩陣，繼之按下列步驟求出各最大相容類：(1)僅與它們自身有相容關(guān)系的那些元素，能夠分別單獨(dú)地構(gòu)成最大相容類，因此從矩陣中刪除這些元素所在的行和列。(2)從簡(jiǎn)化矩陣的最右一列開始向左掃描，直到發(fā)現(xiàn)至少有一個(gè)非零記入值的列。該列中的非零記入值，表達(dá)了相應(yīng)的相容偶對(duì)。列舉出所有這樣的偶對(duì)。第132頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類(3)繼續(xù)往左掃描，直到發(fā)現(xiàn)下一個(gè)至少有一個(gè)非零記入值的列。列舉出對(duì)應(yīng)于該列中所有非零記入值的相容偶對(duì)。在這些發(fā)現(xiàn)的相容偶對(duì)中，如果有某一個(gè)元素與先前確定了的相容類中的所有元素都有相容關(guān)系，則將此元素合并到該相容類中去；如果某一個(gè)元素僅與先前確定了的相容類中的部分元素有相容關(guān)系，則可用這些互為相容的元素組成一個(gè)新的相容類。刪除已被包括在任何相容類中的那些相容偶對(duì)，并列舉出尚未被包含在任何相容類中的所有相容偶對(duì)。(4)重復(fù)步驟(3)，直到掃描過簡(jiǎn)化矩陣的所有列。

最后，僅包含孤立元素的那些相容類，也是最大相容類。第133頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類例：寫出下圖中的相容關(guān)系相對(duì)應(yīng)的簡(jiǎn)化矩陣，并求出最大相容類。2131141115010060010112345第134頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類解：這里沒有孤立結(jié)點(diǎn)，故可忽略步驟(1)。根據(jù)步驟(2)和(3)可有(a)右起第一列上是l，故有相容偶對(duì){5，6}。(b)第二列上全是0。第三列上有兩個(gè)1。與它們相對(duì)應(yīng)的相容偶對(duì)是{3，4}和{3，6}，于是可有{5，6}，{3，4}，{3，6}。(c)第四列上有三個(gè)1，故有{2，3}，{2，4}和{2，5}，于是可有{5，6}，{3，4}，{3，6}，{2，3}，{2，4}，{2，5}可以看出，相容偶對(duì){2，3}和{2，4}中的元素2，與相容偶對(duì){3，4)中的兩個(gè)元素都有相容關(guān)系，故可把它們合并成一個(gè)相容類{2，3，4}。于是可有{2，3，4}，{5，6}，{3，6}，{2，5}。第135頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類(d)第五列有三個(gè)1，故有{1，2}，{1，3}和{l，4}。于是可有{2，3，4}，{5，6}，{3，6}，{2，5}，{1，2}，{l，3}，{1，4}又可看出，相容偶對(duì){1，2}，{1，3}和{1，4}中的元素1，與相容類{2，3，4}中的所有元素都有相容關(guān)系，故可以把它們合并成一個(gè)相容類{1，2，3，4}．于是可有{l，2，3，4}，{5，6}，{3，6}，{2，5}。這些都是最大相容類。第136頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類例：寫出下圖中的相容關(guān)系相對(duì)應(yīng)的簡(jiǎn)化矩陣，并求出最大相容類。213115001610111235第137頁(yè)，共162頁(yè)，2023年，2月20日，星期三關(guān)系矩陣法尋找最大相容類解：這里結(jié)點(diǎn)4是個(gè)孤立結(jié)點(diǎn)，故在矩陣中刪除了相應(yīng)的行和列。根據(jù)步驟(2)和(3)可有(1) {4}(2) {4}，{5,6}(3) {4},{5,6},{3,5},{3,6}，合并后有{4},{3,5,6}(4) {4},{3,5,6},{2,3}(5){4},{3,5,6},{2,3}

,{1,2},{1,3},{1,6}，合并后有{4},{3,5,6},{1,2,3},{1,3,6}

，這里，相容偶對(duì){1,3},{1,6}中的元素1，與相容類{3,5,6}中的部分元素有相容關(guān)系，故組成了相容類{1,3,6}。這些相容類都是最大相容類。第138頁(yè)，共162頁(yè)，2023年，2月20日，星期三相容關(guān)系與集合的覆蓋仍然以X={2166,243,375,648,455}為例令x1=2166,x2=243,x3=375,x4=648,x5=455，X1={x1,x2,x4},X2={x2,x3,x5},X3={x2,x4,x5}在集合X1，X2和X3中，同一個(gè)集合內(nèi)的元素都是相容的。X=X1

。因此，集合A={X1,X2,X3}定義了集合X的一個(gè)覆蓋，但它不能構(gòu)成集合X的一個(gè)劃分。

結(jié)論：集合中的相容關(guān)系能夠定義集合的覆蓋；而集合中的等價(jià)關(guān)系能夠確定集合的劃分。第139頁(yè)，共162頁(yè)，2023年，2月20日，星期三相容關(guān)系與集合的覆蓋定義：在集合X上給定相容關(guān)系r，其最大相容類的集合稱作集合X的完全覆蓋，記作Cr(X)。定理：給定集合A的覆蓋{A1,A2,…,An}，由它確定的關(guān)系R=A1×A1∪A2×A2∪

…∪

An×An是相容關(guān)系。定理：集合X上相容關(guān)系r與完全覆蓋Cr(X)存在一一對(duì)應(yīng)。

第140頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5特殊關(guān)系4.5.1集合的劃分和覆蓋4.5.2等價(jià)關(guān)系4.5.3相容關(guān)系4.5.4偏序集合與哈斯圖第141頁(yè)，共162頁(yè)，2023年，2月20日，星期三4.5.4偏序關(guān)系定義：設(shè)R是集合P中的二元關(guān)系。如果R是自反的、反對(duì)稱的和可傳遞的，亦即有則稱R是集合P中的偏序關(guān)系，簡(jiǎn)稱偏序。序偶<P,≤>稱為偏序集合。第142頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序關(guān)系通常用符號(hào)“≤”表示偏序。這樣，符號(hào)≤就不單純意味著實(shí)數(shù)中的“小于或等于”關(guān)系。事實(shí)上，這是從特定情況中，借用符號(hào)≤去表示更為普遍的偏序關(guān)系。對(duì)于偏序關(guān)系來說，如果有且x≤y，則按不同情況稱它是“小于或等于”，“包含”，“在之前”等等。如果R是集合P中的偏序關(guān)系，則也是P中的偏序關(guān)系。如上所述，如果用≤表示R，則用≥表示。如果<P,≤>是一個(gè)偏序集合，則<P,≥>也是一個(gè)偏序集合，稱<P,≥>是<P,≤>的對(duì)偶。第143頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序關(guān)系例：設(shè)R是實(shí)數(shù)集合?！靶∮诨虻扔凇标P(guān)系是R中的偏序關(guān)系；這個(gè)關(guān)系的逆關(guān)系“大于或等于”關(guān)系也是R中的偏序關(guān)系。例：設(shè)是A的冪集。X中的包含關(guān)系是個(gè)偏序關(guān)系；這個(gè)關(guān)系的逆關(guān)系也是個(gè)偏序關(guān)系。

設(shè)I+是正整數(shù)集合，且,當(dāng)且僅當(dāng)存在z，能使xz=y，才有“x整除y”(可寫成x|y)，換言之，“y是x的整倍數(shù)”?！罢焙汀罢稊?shù)”互為逆關(guān)系，它們都是I+中的偏序關(guān)系。

第144頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序關(guān)系例：設(shè)I+={2,3,6,8}，≤是I+中的“整除”關(guān)系。試表達(dá)出“整除”和“整倍數(shù)”關(guān)系。

解：“整除”關(guān)系≤為“整倍數(shù)”關(guān)系是≥實(shí)數(shù)集合R中的“小于”關(guān)系<和“大于”關(guān)系>，都不是偏序關(guān)系，因?yàn)樗鼈兌疾皇亲苑吹?。但它們是?shí)數(shù)集合中的另一種關(guān)系——擬序關(guān)系。第145頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序集合與哈斯圖像表達(dá)相容關(guān)系時(shí)用簡(jiǎn)化關(guān)系圖一樣，通常使用較為簡(jiǎn)便的偏序集合圖——哈斯(Hass)圖來表達(dá)偏序關(guān)系。

定義：設(shè)是一個(gè)偏序集，如果對(duì)任何，x≤y和x≠y，而且不存在任何其它元素

能使x≤z和z≤y，即成立，則稱元素y覆蓋x。并且記COVP={<x,y>|x,y∈P,y蓋住x}第146頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序集合與哈斯圖在哈斯圖中，（1）用小圈表示每個(gè)元素。（2）如果有，且x≤y和x≠y，則把表示x的小圈畫在表示y的小圈之下。（3）如果y覆蓋x，則在x和y之間畫上一條直線。這樣，所有的邊的方向都是自下朝上，故可略去邊上的全部箭頭表示。第147頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序集合與哈斯圖例如：設(shè)P1={1,2,3,4}，≤是“小于或等于”關(guān)系，則是個(gè)全序集合。設(shè)，≤是P2中的包含關(guān)系，則是全序集合．試畫出和的哈斯圖．

注意：雖然兩個(gè)全序關(guān)系的定義不同，但它們可能具有同樣結(jié)構(gòu)的哈斯圖解：第148頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序集合與哈斯圖例：設(shè)集合X={2,3,6,12,24,36}，≤是X中的偏序關(guān)系并定義成：如果x整除y，則x≤y。試畫的哈斯圖。第149頁(yè)，共162頁(yè)，2023年，2月20日，星期三偏序集合與哈斯圖例：設(shè)集合X={a,b}，是它的冪集。的元素間的偏序關(guān)系≤是包含關(guān)系。試畫出的哈斯圖。注意：對(duì)于給定偏序集合來說，其哈斯圖不是唯一的。由的哈斯圖，可以求得其對(duì)偶的哈斯圖．只需把它的哈斯圖反轉(zhuǎn)180?即可，使得原來是頂部的結(jié)點(diǎn)變成底部上各結(jié)點(diǎn)。第150頁(yè)，共16