第三章 集合與關(guān)系

第三章集合與關(guān)系第1頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示[定義3-5.1]若則是一個二元關(guān)系。即：序偶作為元素的任何集合。２．關(guān)系表示方法（1）枚舉法（直觀法、列舉法）設(shè)R表示二元關(guān)系，用表示特定的序偶，若，則也可寫成：xRy。\第2頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示例：二元關(guān)系定義如圖：可寫成：由定義可見：關(guān)系是一個集合，∴定義集合的方法都可以來定義關(guān)系。第3頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示（2）謂詞公式表示法前面講述，一個集合可用謂詞公式來表達，所以關(guān)系也可用謂詞公式來表達。例：實數(shù)集合R上的“>”關(guān)系可表達為：大于關(guān)系：“>”= 父子關(guān)系：“F”=第4頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示（3）關(guān)系矩陣表示法規(guī)定：(a)二元關(guān)系<x,y>中的序偶中左元素表示行，右元素表示列；(b)若，則在對應(yīng)位置記上“1”，否則為“0”。第5頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示例1：設(shè)并定義為列出關(guān)系矩陣：第6頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示

是Ｘ→Ｙ的全域關(guān)系，

例2：設(shè)X={a,b,c},Y={1,2},R2是Ｘ→Ｙ的關(guān)系，第7頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示（4）關(guān)系圖表示法規(guī)定：(a)把Ｘ、Ｙ集合中的元素以點的形式全部畫在平面上；(b)若，則xi和yi之間畫一箭頭弧線，反之不畫任何聯(lián)線。例：是X中的二元關(guān)系，第8頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示用關(guān)系圖表示：第9頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示３．關(guān)系的定義域和值域：[定義]設(shè)S是一個二元關(guān)系，D(s)是所有客體x的集合，對于一些y來說，若有，則稱D(s)為S的定義域（簡稱“域”），即設(shè)R(S)是所有客體y的集合，對于一些X來說，若有，則稱集合R(S)是S的值域（簡稱“值”）,即：第10頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示

例：X={1,2,3,4,5,6},R為X到Y(jié)的二元關(guān)系：，則一般情況，稱X為R的前域，稱Y為R的陪域。第11頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示４．關(guān)系和笛卡爾乘積笛卡爾乘積的任何子集都可以定義一種二元關(guān)系。例：X={1,2,3,4}，Y={1,2}，則均為二元關(guān)系。

第12頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示５．三個特殊關(guān)系：空白關(guān)系，全域關(guān)系，恒等關(guān)系[定義]集合X2定義了X集合中的一種關(guān)系，通稱為X中的全域關(guān)系，用Ex表示：空集也是的一個子集，它也定義了一種關(guān)系稱為空白關(guān)系；X集合中的恒等關(guān)系，

在全域關(guān)系和恒等關(guān)系中前域=定義域，陪域=值域。第13頁，課件共117頁，創(chuàng)作于2023年2月§3.4關(guān)系及其表示例：Ｘ=｛Ｔ，Ｆ｝則同一域上的關(guān)系,可進行集合的所有運算。第14頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)１．自反性：

[定義]設(shè)Ｒ是Ｘ集合中的二元關(guān)系，對于每一個（所有的）有,則稱Ｒ是自反關(guān)系,X中R是自反的例：設(shè)是自反的關(guān)系。R的關(guān)系矩陣第15頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)[定義]設(shè)R是X中的二元關(guān)系，對于每一個，有xx，則稱R是反自反的關(guān)系，表示成：R是X中的反自反的關(guān)系xx。例：設(shè)X={1,2,3},

第16頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)２．對稱性[定義]設(shè)R是X中的二元關(guān)系，對于每一個來講，如果每當有xRy，則必有yRx，則稱R是X中的對稱關(guān)系，并表示成：R是X中的對稱關(guān)系

S4既不是自反的，又不是反自反的第17頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)例：設(shè)X={1,2,3},R={<1,1><2,1><1,2><3,2><2,3>}則R是對稱的關(guān)系[定義]設(shè)R是X集合中的二元關(guān)系，對于每一個

來講，如果每當xRy和yRx就必有x=y，則稱R是反對稱的關(guān)系。第18頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)即當且僅當X中的R才是反對稱的。討論定義：（1）前件為“T”，則x=y也為“T”,則為反對稱的；（2）前件為“F”，則有三種情況：后件（x=y）不論是真還是假，命題公式為“T”。下面舉例說明：第19頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)例：設(shè)X={a,b,c}均是反對稱的第20頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)例：X={a,b,c},下列關(guān)系不是對稱的，也不是反對稱的第21頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)X上的恒等關(guān)系是自反、對稱、反對稱的。第22頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)X上的全域關(guān)系：

是自反的，對稱的

X上的空關(guān)系是反自反、對稱、反對稱的。第23頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)３．傳遞性：

[定義]設(shè)R是X中的二元關(guān)系，對于每一個來說，如果每當

，就必有

則稱R是可傳遞的，并表示成：X中R可傳遞討論定義：（1）前件為“T”，

則xRz也為“T”，R是可傳遞的；（2）前件為“F”，有三種情況后件不論是真還是假，命題為“T”，則R是可傳遞的

第24頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)

例：設(shè)X={a,b,c}，則下列關(guān)系均是可傳遞的第25頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)下列關(guān)系是不可傳遞的：第26頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)４．確定二元關(guān)系性質(zhì)舉例（1）設(shè)X={1,2,3}，反自反，反對稱，可傳遞的；反對稱的；第27頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)自反，對稱，反對稱，可傳遞的；自反，對稱，可傳遞的；反自反的，對稱的，反對稱的，可傳遞的。第28頁，課件共117頁，創(chuàng)作于2023年2月§3.5關(guān)系的性質(zhì)（2）若

，則X上的空關(guān)系自反的，反自反的，對稱的，反對稱的，可傳遞的。從定義上看前件為假，后件不論是真還是假，命題為“T”，第29頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算一、關(guān)系的集合運算：關(guān)系是有序?qū)?，集合的元素對關(guān)系仍然適用。定理1：設(shè)R和S是從A到B的兩個關(guān)系，則R∩S，R∪S，R-S，~R，R⊕S仍是從A到B的關(guān)系。第30頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算二、復(fù)合關(guān)系：引例：a，b，c三人，a，b是兄妹關(guān)系，b，c是母子關(guān)系，則a，c是舅甥關(guān)系。如設(shè)R是兄妹關(guān)系，S是母子關(guān)系，則R與S的復(fù)合T是舅甥關(guān)系，而S與R復(fù)合是母女關(guān)系。又如：R是父子關(guān)系，R與R的復(fù)合是祖孫關(guān)系。第31頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算1、復(fù)合關(guān)系的定義（關(guān)系的復(fù)合運算）定義3-7.1：設(shè)X，Y，Z是三個集合，設(shè)R為X到Y(jié)的關(guān)系，S為Y到Z的關(guān)系，則R?S為R和S的復(fù)合關(guān)系，表示為：第32頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算1、復(fù)合關(guān)系的定義（關(guān)系的復(fù)合運算）說明：（1）R與S能進行復(fù)合的必要條件是R的值域所屬集合B與S定義域所屬集合B是同一集合，否則就不能復(fù)合。（2）<x，z>有這個復(fù)合關(guān)系的定義為至少有一個中間橋梁的元素y，使<x,y>∈R與<y,z>∈S（3）RS為新的二元關(guān)系（4）RSX×Z第33頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算例1：設(shè)A={1,2,3,4,5},B={3,4,5},C={1,2,3},R是A到B的關(guān)系，S是B到C的關(guān)系。R={<x,y>|x+y=6}={<1,5>,<2,4>,<3,3>}S={<y,z>|y-z=2}={<3,1><4,2><5,3>}則R?S=？R?S={<1,3>，<2,2>，<3,1>}第34頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算例2：設(shè)A={1,2,3,4,5}，R,S均為A→A的關(guān)系，且R={<1,2><3,4><2,2>}S={<4,2><2,5><3,1><1,3>}S?R={<4,2><3,2><1,4>}∴“?”是不可交換的。則R?S={<1,5><3,2><2,5>}第35頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算∴“?”是不可交換的。說明：（1）R是A到B的關(guān)系，S是B到C的關(guān)系，R?S有定義，而S?R根本不能復(fù)合。（2）若A=C，則R?S是A上的關(guān)系，而S?R是B上的關(guān)系，不可能相等。（3）若A=B=C，R、S均為A上的關(guān)系，R?S和S?R也是A上的關(guān)系，一般地R?S和S?R不可能相等。第36頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算定理：設(shè)則有：復(fù)合關(guān)系圖可見復(fù)合關(guān)系滿足結(jié)合律

第37頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算由關(guān)系復(fù)合的結(jié)合律可知關(guān)系R本身所組成的復(fù)合關(guān)系可以寫成：R?R，R?R?R，…，分別記作R（2），R（3），…定義：給定集合X，R是X中的二元關(guān)系，設(shè)nN，則R的n次冪Rn可以定義為：（1）R0=X集合中的恒等關(guān)系

（2）Rn+1=

Rn?R

第38頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算例3設(shè)R，S是I+中的二元關(guān)系，且則：第39頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算例4若|X|=n，則X中的二元關(guān)系R的冪次值是有限的。一般不用求出超過X的基數(shù)次冪。

第40頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算2、復(fù)合關(guān)系的矩陣表示設(shè)有三個集合：

設(shè)R為X到Y(jié)的關(guān)系，S為Y到Z的關(guān)系：而|X|=m,|Y|=n,|Z|=p，則關(guān)系矩陣第41頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算2、復(fù)合關(guān)系的矩陣表示例5：設(shè)X={1,2,3,4,5},R,S均是X中的二元關(guān)系，R={<1,2><3,4><2,2>},S={<4,2><2,5><3,1><1,3>}第42頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算３．逆關(guān)系

[定義3-7.2]設(shè)X,Y是二個集合，若R是X→Y的關(guān)系，從Y→X的關(guān)系，稱為R的逆關(guān)系，用表示，或用Rc表示。討論定義：（1）只要將R中每一個序偶中的元素全部調(diào)換位置,就可得到R的逆關(guān)系

，故||=|R|（2）設(shè)的關(guān)系矩陣為的轉(zhuǎn)置矩陣；（3）在R的關(guān)系圖中，只要把所有箭頭改換方向就可得到的關(guān)系圖。（自回路箭頭改變與否無關(guān)）

第43頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算3、逆關(guān)系例6：X={0,1,2}，R={<0,0><0,1><1,2><2,2>},={<0,0><1,0><2,1><2,2>},第44頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算定理3-7.1設(shè)R，R1，R2都是從A到B的二元關(guān)系，則下列各式成立。第45頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算定理3-7.2設(shè)T為從X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，證明第46頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算例：

，試求：

第47頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算第48頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算定理3-7.3設(shè)R為X上的二元關(guān)系，則（1）R是對稱的，當且僅當R=Rc（2）R是反對稱的，當且僅當R∩Rc

Ix第49頁，課件共117頁，創(chuàng)作于2023年2月3.6關(guān)系的運算證明：①充分性：R是對稱的對于任一②必要性：R是對稱的，∴對任一∴R一定是對稱的∴第50頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算[定義3-8.1]給定集合X，R是X中的二元關(guān)系，若有另一關(guān)系R’滿足下列條件：（1）R’是自反的（對稱，可傳遞的）；（2）（3）對于任一自反（對稱，傳遞的）關(guān)系R’’，若，則

則稱R’是R的自反（對稱，傳遞的）閉包，并依次用r(R),s(R),t(R)來表示之。第51頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算討論定義：（1）由（2）知，R’是在R的基礎(chǔ)上添加元素（有序?qū)Γ唬?）由（1）知，R添加元素其目標是使R’具有自反性（對稱性、傳遞性）（3）由（3）知，在添加后使之具有自反性的所有關(guān)系中R’是最小的一個，即要在保證其具有自反性的前提下，要盡量少添加元素，沒必要的元素不要加入。第52頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算例：設(shè)X={a,b},R={<a,a><a,b>}，r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},t(R)={<a,a><a,b>}=R例：求t(R)需要特別小心，要進行多次添項。設(shè)X={a,b,c},R={<a,b><b,c><c,a>}，求r(R),s(R),t(R)解：r(R)=s(R)=t(R)={<a,b><b,c><c,a><a,c><b,a><c,b><a,a><b,b><c,c>}第53頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算從關(guān)系圖中可以看到：（1）r（R）是在R的基礎(chǔ)上添加自回路，使得每點均有自回路。（2）s（R）是在R中兩點間只有一條弧的情況下，再添加一條反向弧，使得兩點間或是0條弧，或是兩條弧，原來兩點間沒有弧不能添加。（3）t（R）是在R中如結(jié)點a通過有向路能通到x，則添加一條從a到x的有向弧，其中包括如a能達到自身，則必須添從a到a的自回路。第54頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算[定理3-8.1]給定集合X，R是X中的二元關(guān)系，那么：（1）當且僅當r(R)=R，則R是自反的；（2）當且僅當s(R)=R，則R是對稱的；（3）當且僅當t(R)=R，則R是可傳遞的。第55頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算[定理3-8.2]R是X中的二元關(guān)系是X中的恒等關(guān)系，則有證明：按定義證：（1）設(shè)，則R’是自反的，

（3）設(shè)有任一R’’也是自反的，且則第56頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算[定理3-8.3]給定集合X，R是X中的二元關(guān)系，則有[定理3-8.4]設(shè)X是一集合，R是X中的二元關(guān)系，則：第57頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算例：X={a,b,c},R={<a,b><b,c><c,a>}，|X|=3,則[定理3-8.5]設(shè)|X|=n，R是X中的二元關(guān)系，則第58頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算說明：Rk的每條弧就是在R中，任何一點x，經(jīng)過k條弧組成的有向路到達y，則<x，y>∈Rk而傳遞閉包t(R)就是在R中如點x經(jīng)過任何條弧能到達y，則x到y(tǒng)應(yīng)直接有一條有向弧，故定理[3-8.4]就是t(R)要在R的基礎(chǔ)上并上R2，R3…而如A是有限集合|A|=n，如在x點有超過n步能到達y點，則必有一條更短的有向路，至多n步可以到達y，所以得到[3-8.5]。第59頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算例：X={a,b,c,d},R={<a,b><b,c><c,d>},則第60頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算[定理]設(shè)X是一集合，R是X中的二元關(guān)系，則有：（1）r(S(R))=S(r(R));（2）r(t(R))=t(r(R));（3）t(S(R))S(t(R))。第61頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算證明：（1）r(S(R))常用下列符號表示一些閉包：“R加”：

，傳遞閉包，

“R星”：

，自反可傳遞閉包，

第62頁，課件共117頁，創(chuàng)作于2023年2月§3.7關(guān)系的閉包運算例：設(shè)X={a,b,c},R={<a,b><c,c>}（1）rS(R)=r{<a,b><b,a><c,c>}={<a,b><b,a><c,c><a,a><b,b>}Sr(R)=s{<a,b><c,c><a,a><b,b>}={<a,b><b,a><c,c><a,a><b,b>}（2）rt(R)=r{<a,b><c,c>}={<a,b><c,c><a,a><b,b>}tr(R)=t{<a,b><c,c><a,a><b,b>}={<a,b><c,c><a,a><b,b>}（3）tS(R)=t{<a,b><c,c><b,a>}={<a,b><c,c><b,a><a,a><b,b>}St(R)=S{<a,b><c,c>}={<a,b><c,c><b,a>}

∴t(S(R))

St(R)

第63頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋[定義1]給定一非空集合A，又設(shè)若（1）（2）則稱S為A的覆蓋。例1：S={a,b,c}，A={{a,b},{b,c}}，B={{a},{a,b},{c}}，C={{a},,{c}}，D={{a},,{a,c}}均為S的覆蓋。第64頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋[定義1]給定一非空集合A，又設(shè)若（1）（2）則稱S為A的覆蓋。例2：四個半圓覆蓋一正方形。第65頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋[定義2]給定一非空集合S，設(shè)非空集合如果有：或（i,j=1,2…,m）則稱集合A是集合S的一個劃分。第66頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋討論定義：（1）劃分和覆蓋主要差別在第（2）條；（2）劃分A中的元素，稱為劃分的類，在定義中均是A中的一個類，類的個數(shù)稱為劃分的秩；（3）若A為有限集合，則A的秩是有限的，為|A|，若A為無限集合，則劃分的秩是無限的；（4）集合的劃分必定是一個覆蓋，而覆蓋不一定是劃分；（5）集合S上的秩最大的劃分稱最大劃分，最小的稱最小劃分。第67頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋例3：設(shè)S={a,b,c}，下列均為S的一個劃分：=2（秩）；最大劃分，秩為3；最小劃分，秩為1。=2（秩）；=2（秩）；第68頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋例4：四個直角三角形組成了正方形的一個劃分秩=4第69頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋[定義]設(shè)A和A’是非空集合S的二種劃分，并可表示成：

若A’的每一個類

都是A的某一個類的子集，則稱劃分A’是劃分A的加細，或講A’加細了A，若A’加細了A且則稱A’是A的真加細。討論定義：A’加細了A，一定有|A’|≥|A|（秩），若|A’|>|A|，則一定為真加細。第70頁，課件共117頁，創(chuàng)作于2023年2月§3.8集合的劃分和覆蓋例：S={a,b,c,d}，S的劃分：A={{a,b},{c,d}},A’={{a}{c,d}}，則A’是A的真加細A’’={{a}{c}gtcfrfs},則A’’是A的真加細第71頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類[定義3-10.1]設(shè)R為定義在集合A上的一個關(guān)系，若R是自反的、對稱的和傳遞的，則R稱為等價關(guān)系。如果R是一個等價關(guān)系，<a，b>∈R稱a等價于b，記作a~b。

（1）在一群人的集合上年齡相等的關(guān)系是等價關(guān)系，而朋友關(guān)系不一定是等價關(guān)系，因為它可能不是傳遞的。（2）命題公式間的邏輯等值關(guān)系是等價關(guān)系。（3）集合上的恒等關(guān)系和全域關(guān)系都是等價關(guān)系。（4）在同一平面上直線之間的平行關(guān)系，三角形之間的相似關(guān)系都是等價關(guān)系。第72頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類例1A={1，2，3，4，5，6，7}，R是A上的“模3同余”關(guān)系，為整數(shù)}即x≡y(mod3)試驗證R是等價關(guān)系，畫出R的關(guān)系圖，列出R的關(guān)系矩陣

第73頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類（2）R的關(guān)系矩陣

解：（1）R={<1,1><1,4><1,7><2,2><2,5><3,3><3,6><4,1><4,4><4,7><5,2><5,5><6,6><6,3><7,7><7,4><7,1>}從圖中可以看出，該等價關(guān)系將A分成3個類{1,4,7},{2,5,8},{3,6},類內(nèi)均有關(guān)系，而類間均沒有關(guān)系R滿足自反、對稱和可傳遞的，∴R是一等價關(guān)系第74頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類[定義]設(shè)m∈I+x，y∈I，若對于某個整數(shù)n有：（x-y）=n×m，則稱x模m等于y，記作：x≡y(modm)

[定理]任何集合X

I，（I的任何子集X中）的模m等價，是一個等價關(guān)系。

第75頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類[定義3-10.2]設(shè)R為集合A上的等價關(guān)系，對于任何a∈A，集合[a]R

={x|x∈A，aRx}稱為元素a形成的R等價類。討論定義：（1）等價類[a]R是一個集合，由定義可見[a]R

A

（2）[a]R中的元素是等價關(guān)系中，所有與a具有關(guān)系的元素所組成的集合，且[a]R≠

第76頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類例：設(shè)X=N，關(guān)系R={可被3整除}

是一等價關(guān)系，則R可以找出三個等價類：={0，3，6，9…}，此集合中的元素除以3的余數(shù)為“0”；

={1，4，7，10…}，此集合中的元素除以3的余數(shù)為“1”；={2，5，8，11…}，此集合中的元素除以3的余數(shù)為“2”。第77頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類例：設(shè)X={a,b,c,d}，R是X中的等價關(guān)系，R={<a,a><b,b><a,b><b,a><c,c><d,d><c,d><d,c>}則第78頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類[定理]設(shè)X是一個集合，R是X中的等價關(guān)系，則（1）若，則

（2）若xRy，則（3）

（3）若xy，則第79頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類例：X為全班同學(xué)的集合，則班中同姓關(guān)系是一個等價關(guān)系，（1）任何一個人均∈某一個等價類，王某某∈[王]

R

張某∈

[張]R…

（2）任何二個姓的等價類，只有二種可能一種：[王]R=[李]R

二種：[王]R[李]R=

（3）全班同學(xué)的集合=同姓關(guān)系等價類的并集=[王][李]…（4）所有等價類的集合，一定導(dǎo)致全班同學(xué)集合的一個劃分：A={[王]R，[李]R….}第80頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類[定理3-10.2]設(shè)X是一非空集合，R是X中的等價關(guān)系，R等價類的集合{[x]R|x∈X}是X的一個劃分，且此集合稱為X按R的商集，用表示之。例：設(shè)X={x1,x2…..xn}

（1）X集合中的全域關(guān)系，，它是一個等價關(guān)系，∴X按

R1的商集它形成了X的一個最小劃分第81頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類（2）X中的恒等關(guān)系它形成了X的一個最大劃分例：X為全班同學(xué)的集合，|X|=n,(n∈N)（1）同學(xué)關(guān)系R1是一個等價關(guān)系，

（2）按指紋的相同關(guān)系R2是一個等價關(guān)系，它形成了全班同學(xué)的最大劃分第82頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類（3）同姓關(guān)系R3是一等價關(guān)系{[張]R3，[李]R3，…}它形成了全班同學(xué)的既不是最大，又不是最小劃分第83頁，課件共117頁，創(chuàng)作于2023年2月§3.9等價關(guān)系與等價類[定理3-10.3]X是一非空集合，A為X的一個劃分，且 A={A1,A2,….An}，則由A導(dǎo)出的X中的一個等價關(guān)系

例：X＝{a,b,c,d}，A={{a,b},{c,d}}則R＝({a,b}×{a,b})({c,d}×{c,d})={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}

由此我們看到：集合X上的等價關(guān)系與X的劃分之間有對應(yīng)關(guān)系。第84頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系[定義3-11.1]給定一個集合X，R是X中的二元關(guān)系，如果R是自反、對稱的，則稱R是相容關(guān)系。例：設(shè)X={ball,bed,dog,let,egg},5個英文單詞定義X中一個二元關(guān)系：R={

有相同的字母}則R是自反的，對稱的，但不可傳遞∵(ballRbed)(bedRegg)(ballRegg)則R={<1,1><1,2><2,1><1,4><4,1><2,2><2,3><3,2><2,4><4,2><2,5><5,2><3,3><3,5><5,3><4,4><4,5><5,4><5,5>}第85頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系第86頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系[定義3-11.2]設(shè)X是一個集合，R是X上的相容關(guān)系，假定AX，若對于A中任意兩個元素a1，a2有a1Ra2，稱A是由相容關(guān)系R產(chǎn)生的相容類。第87頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系[定義3-11.3]設(shè)X是一個集合，R是X中的相容關(guān)系，假定AX，若任一x∈A都與A中的其它所有元素有相容關(guān)系，而（X-A）中沒有一個元素與A中的所有元素有相容關(guān)系，則稱子集A為相容關(guān)系R的一個最大相容類。

例：上例中

均是X中的最大相容類,且定義了X的一個覆蓋。同樣已知X集合的一個覆蓋第88頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系則一定可以求出相對應(yīng)的相容關(guān)系來：討論等價關(guān)系和相容關(guān)系后可得到結(jié)論：集合X上的相容關(guān)系R的所有最大相容類集合{A1,A2,….Am}構(gòu)成集合X的一個覆蓋。即：而集合X上的等價關(guān)系R的所有等價類集合構(gòu)成X的一個劃分第89頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系求最大相容類的方法：關(guān)系圖法：確定最大完全多邊形每個頂點都與其他所有頂點相聯(lián)結(jié)的多邊形。(1)孤立結(jié)點是最大的完全多邊形；(2)二個相互聯(lián)結(jié)的結(jié)點是最大完全多邊形；(3)三角形是三個結(jié)點的最大完全多邊形；第90頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系(4)四個結(jié)點；(5)五個結(jié)點;畫出簡化相容關(guān)系的關(guān)系圖后，先結(jié)點最多的完全多邊形，以后逐次減少。第91頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系例：已知相容關(guān)系圖，求出最大相容類第92頁，課件共117頁，創(chuàng)作于2023年2月§3.10相容關(guān)系最大相容類集合為第93頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系1、偏序關(guān)系[定義3-12.1]設(shè)R是非空集合A上的關(guān)系，如果R具有自反性、反對稱性和傳遞性，則R是A上的偏序關(guān)系，并把關(guān)系R記作“”。序偶<A，>稱作偏序集。討論定義：（1）“”不是指普通實數(shù)中的≤關(guān)系，而是代表更為普遍的關(guān)系（具有自反，反對稱和可傳遞性的關(guān)系）；（2）如果<x，y>∈，則記作xy，讀作“x小于或等于y”第94頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系1、偏序關(guān)系例1、設(shè)集合A={a，b，c}，A上的關(guān)系R為：R={<a，a>，<a，b>，<a，c>，<b，b>，<b，c>，<c，c>}，從關(guān)系圖來驗證R是偏序關(guān)系第95頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系例2、設(shè)A是非零自然數(shù)集，R是A上的整除關(guān)系，驗證R是偏序關(guān)系。（1）

x∈A，因x能整除x，∴R具有自反性。（2）

x，y∈A，如x能整除y，且y能整除x，則x=y。即<x，y>∈R，<y，x>∈R，則x=y，即R具有反對稱性。（3）

x，y，z∈A，如<x，y>∈R，<y，z>∈R，即x能整除y，y能整除z，則x能整除z，∴<x，z>∈R，∴R具有傳遞性。∴R是A上的偏序關(guān)系。第96頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系2、擬序關(guān)系設(shè)R是非空集合A上的關(guān)系，如果R具有反自反性和傳遞性，則R是A上的擬序關(guān)系，并把關(guān)系R記作“”。序偶<A，>稱作擬序集。討論定義：（1）“”不是指普通實數(shù)中的＜關(guān)系，而是代表擬序關(guān)系；（2）如果<x，y>∈，則記作xy，讀作“x小于y”第97頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系2、擬序關(guān)系例3、A={1，2，3，4}，R是A上的大于關(guān)系。R={<a，b>|a>b，a，b∈A>則R={<2，1>，<3，1>，<3，2>，<4，1>，<4，2>，<4，3>}注：<3，1>∈R，在實數(shù)中3大于1，因其是擬序關(guān)系，寫作“31”，讀作“3小于1”，該小于是擬序的“小于”，而不同于真正實數(shù)中的小于。

第98頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系2、擬序關(guān)系定理：設(shè)R是集合A上的擬序關(guān)系，則R是反對稱的。證明：（反證法）設(shè)R不是反對稱的。則a，b∈A，a≠b且<a，b>∈R,<b，a>∈R，因R是傳遞的，∴<a,a>∈R，<b,b>∈R。與R是反自反的矛盾，∴R具有反對稱性。

第99頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系2、擬序關(guān)系定理：設(shè)R是集合A上的擬序關(guān)系，則R是反對稱的。說明：（1）由自反性和傳遞性可以推出反對稱（2）擬序關(guān)系具有反自反性、反對稱性和可傳遞性。（3）擬序和偏序的區(qū)別在于反自反性和自反性。若R是偏序關(guān)系，則R-IA是擬序關(guān)系若R是擬序關(guān)系，則R∪IA是偏序關(guān)系

第100頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系3、全序關(guān)系[定義3-12.4]設(shè)R是A上的偏序關(guān)系，

若

a，b∈A，則ab和ba，兩者必居其一，則稱R為A上的全序關(guān)系，或稱線序關(guān)系。（1）整除關(guān)系R，集合的包含關(guān)系，公式的重言蘊含關(guān)系均是偏序關(guān)系。（2）實數(shù)中的<，>，集合的真子集均是全序關(guān)系。（3）實數(shù)中的≤，≥是全序關(guān)系。第101頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系4、哈斯圖描述偏序集的關(guān)系圖，可以簡化為哈斯圖，其簡化規(guī)則為：（1）用“”表示R中的結(jié)點（2）所有結(jié)點的自回路均省略（3）省略所有弧上的箭頭，適當排列A中的元素位置，如ab，則a畫在b的下方。（4）如ab，bc，則必有ac，a到b有邊，b到c有邊，則a到c的無向弧必須省略。第102頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系4、哈斯圖例4、畫出下列偏序集合的哈斯圖。（1）<{1,2,3,4,5,6},R>R={<1,1><2,2><3,3><4,4><5,5><6,6><1,2><1,3><1,4><1,5><1,6><2,4><2,6><3,6>}第103頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系4、哈斯圖例4、畫出下列偏序集合的哈斯圖。（2）A={a,b,c>，包含關(guān)系R

是上的偏序關(guān)系。則<,R

>是偏序集，其哈斯圖如下：第104頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系4、哈斯圖例4、畫出下列偏序集合的哈斯圖。（3）A={1,2,3，4>，≤是實數(shù)上的小于等于關(guān)系，因<A，≤>不僅是偏序關(guān)系，而且是全序關(guān)系，全序關(guān)系的哈斯圖是一條線故又稱線序，即任何兩個元素均存在大小關(guān)系。第105頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系例5、已知偏序集合<A，>的哈斯圖如圖，寫出集合A和關(guān)系第106頁，課件共117頁，創(chuàng)作于2023年2月3.11序關(guān)系5、最大元、最小元、極大元、極小元定義：設(shè)<A，>是偏序集，集