第3章-集合與關(guān)系楊圣洪版教材

1、離 散 數(shù) 學,授課教師：劉慧明,Email：huiming@qust.edu.cn青島科技大學青島市鄭州路53號(四方校區(qū)) 郵編:266042,第三章 集合與關(guān)系,第三章 集合與關(guān)系,引言 集合論是研究集合的數(shù)學理論，包含了集合、元素和成員關(guān)系等最基本的數(shù)學概念。集合論是現(xiàn)代數(shù)學的基礎(chǔ)，它的基本概念已滲透到數(shù)學的所有領(lǐng)域。集合論、命題邏輯與一階邏輯共同構(gòu)成了數(shù)學的公理化基礎(chǔ)。本章主要學習集合的概念、運算、性質(zhì)、計數(shù)、序偶

2、和關(guān)系等。,第三章 集合與關(guān)系,集合：由一堆物件構(gòu)成的整體。（集合沒有精確的定義）描述集合常用的方法： 1、枚舉法:列出集合中的所有對象。 如：青科大教學樓={一教,二教,三教,弘毅樓,明德樓} 2、描述法:描述集合各對象的性質(zhì)。 如：偶數(shù)集={除以2，余為0的所有整數(shù)}元素：構(gòu)成集合的對象稱為元素。 元素是無序的，重復(fù)的元素視為同一元素； 元素與集合之間的關(guān)系有“屬于∈”或“不屬于?”二種關(guān)

3、系。,3.1 集合的基本概念,子集A?B：A中的每個元素都是B的元素。（A包含于B，或B包含A）冪集P(A)：P(A)={A的所有子集構(gòu)成的集合}。如：A={1,2,3} A000={},——空集（常記為φ） A001={3}, A010={2}, A100={1}, A011={2,3}, A101={1,3}, A110={1,2}, A111={1,2,3}

4、 P(A)={A000,A001,A010,A011,A100,A101,A110,A111} ={φ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} P(A)其有23個元素 ,即2|A|個。冪集又記為2A。,3.1 集合的基本概念,1、交集：A?B={由同時屬于A與B的元素組成}2、并集：A?B={由屬于A或?qū)儆贐的元素組成}3、差集：A-B={由屬于A但不屬于B的元素組成}4、

5、余集(補集)：?A={全集U中不屬于A的元素組成}=U-A5、對稱差：A?B= (A?B)-(A?B) {由屬于A與B的并集但不屬于A與B的交集元素組成},3.2 集合的運算與性質(zhì),【定義3.2.3】（集合相等） 設(shè)A、B是兩個集合，若A?B、B?A，則稱兩個集合A與B相等，記為A=B。 集合的運算性質(zhì)：（與命題邏輯類同：? ∨, ? ∧, ? ?）冪等律：A?A=A， A?A=A結(jié)合律：A?B?C=A?(B?C)=(

6、A?B)?C A?B?C= A?(B?C)=(A?B)?C交換律：A?B=B?A， A?B=B?A分配律：A?(B?C)=(A?B)?(A?C) A?(B?C)=(A?B)?(A?C)同一律：A??=A ； 零律：A??=?排中律：A??A=E ； 矛盾律：A??A=?吸收律：A?(B?A)=A， A?(B?A)=A (大吃小)德摩律：?(A?B)= ?A??B， ?(A?B

7、)=?A??B雙重否定律：??A=A,3.2 集合的運算與性質(zhì),|A|=集合A的元素個數(shù)。,3.3 有窮集的計數(shù),定理3.3.1：（包含排斥原理） |A1?A2|=|A1|+|A2|-|A1?A2| 因為公共部分算了兩次！ 例：A1={藍球隊}，|A1|=10，A2={足球隊}，|A2|=13，雙重身份球員3人，請問這二個球隊總共多少人？ 解：|A1?A2|=|A1|+|A2|-|A1?A2|=10+1

8、3-3=20人,n個集合的包含排斥原理: |A1?A2?…?An|= ?|Ai|-?|Ai?Aj|+?|Ai?Aj?Ak| -?|Ai?Aj?Ak?AL|…+(-1)n-1|A1?A2?…?An| 記憶方法：“+”奇數(shù)個集合相交 “-”偶數(shù)個集合相交,3.3 有窮集的計數(shù),例題：設(shè)校足球隊隊員有38人，藍球隊隊員有15人，排球隊隊員有20人，三隊總?cè)藬?shù)為58人，同時參加3個隊的球員有3人，請問

9、同時參加二隊的有多少人？ 解：|A1?A2?A3|=?|Ai|-?|Ai?Aj|+?|Ai?Aj?Ak| 58=(38+15+20)-?|Ai?Aj|+3 ?|Ai?Aj|=18，即同時參加二隊的有18人。,例題：求在[1,300]的整數(shù)中，能被3或5或7整除的整數(shù)的個數(shù)。 解： 設(shè)A3表示能被3整除的數(shù)，|A3|=[300/3]=100； A5表示能被5整除的數(shù)，|A5|=[300/5]=60；

10、 A7表示能被7整除的數(shù)，|A7|=[300/7]=42； 則能被3與5同時整除的個數(shù)：|A3?A5|=[300/15]=20 能被3與7同時整除的個數(shù)：|A3?A7|=[300/21]=14 能被5與7同時整除的個數(shù)：|A5?A7|=[300/35]=8 能被3、5、7同時整除的個數(shù)：|A3?A5?A7|=2 能被3或被5或被7整除的個數(shù)：|A3?A5?A7|=|A3|+|A5|+|A7|-|A3?A5

11、|-|A3?A7|-|A5?A7|+|A3?A5?A7|=100+60+42-20-14-8+2=162,3.3 有窮集的計數(shù),小結(jié)：一、基本概念 集合、子集、冪集二、集合的運算及性質(zhì) 1、交、并、差、余（補）、對稱差 2、有窮集合的計數(shù)（包含互斥原理）要求：熟練掌握集合的運算及其相關(guān)性質(zhì)。,3.1-3.3小結(jié),【定義3.4.1】（序偶）將有固定次序的兩個對象寫在一塊，稱為序偶，即有秩序的兩個對象，記為或。,

12、3.4 序偶,【定義3.4.2】 令與是二個序偶，如果x=u、y=v，那么稱這兩個序偶相等。記為=。,在日常生活中，有許多事物是成對出現(xiàn)的，并且這對事物之間具有一定的次序，如：天地,夫妻,乾坤等，反過來就不習慣。,如：,,,…；平面坐標等 注意：序偶與是不同的，次序不能亂，就如同與表示的是不同坐標點一樣。,序偶的概念可推廣到三元組、四元組、多元組：【定義3.4.3】如果是序偶，且,z>也是一個序偶，則稱為三元組。

13、如：，，，，三維空間中點的坐標 等?！径x3.4.4】如果是n-1元組，而,xn>是序偶，則稱為為n元組。,3.4 序偶,【定義3.5.1】（直積） 令A(yù)、B是兩個集合，稱集合{|x?A, y?B}為A與B的直積或笛卡爾積，記為A?B。（直積的結(jié)果是一個集合?。?3.5 直積或笛卡爾積,如：A={1,2,3},B={a,b,c} A?B={1,2,3}?{a,b,c} ={,,,,,, ,

14、,} B?A={a,b,c}?{1,2,3} ={,,,,,, ,,} 由于?，所以A?B?B?A。直積不滿足交換律若A,B是有窮集合，則有|A×B|=|A|·|B| (·為數(shù)乘運算),易證直積具有以下性質(zhì)：1、A?(B?C)= A?B?A?C2、A?(B?C)= A?B?A?C 3、(B?C)?A = B?A?C?A4、(B?C)?A =

15、B?A?C?A5、A?B ? A?C?B?C ? C?A?C?B6、A?B,C?D ? A?C?B?D,3.5 直積或笛卡爾積,【定義3.5.2】令A(yù)1,A2,…,An是n個集合，稱n元組的集合{|x1?A1, x2?A2,…, xn?An}為A1,A2,…,An的直積或笛卡爾積，記為A1?A2?…?An。,我們僅證明(1)。對任意的 ∈A×(B∪C) ? x∈A∧y∈(B∪C) ? x∈A∧(y∈B∨y

16、∈C)?(x∈A∧y∈B)∨(x∈A∧y∈C)?∈A×B∨∈A×C?∈(A×B)∪(A×C),關(guān)系是客觀世界存在的普遍現(xiàn)象， 它描述了事物之間存在的某種聯(lián)系。 例如：人類集合中的父子、兄弟、同學、同鄉(xiāng)等關(guān)系；實數(shù)之間的大于、小于、等于關(guān)系；兩條直線間的平行、 垂直等關(guān)系；集合間的包含、元素與集合的屬于等等都是關(guān)系。 兩個個體之間的關(guān)系稱為二元關(guān)系；三個以上個體之間的關(guān)系稱為多元關(guān)

17、系。 我們主要討論二元關(guān)系。,3.6 關(guān)系及其表示,關(guān)系并不限于同一類事物之間，也存在于不同事物之間。 如：旅客住店的關(guān)系：假設(shè)有張、王、李、趙四人，分別住在1，2，3號三個房間，其中：張住1號，李住1號，王住2號，趙住3號。若分別以a、b、c、d表示四人，R表示住宿關(guān)系，則住宿關(guān)系R可表示為： R={,,,}。 可以看出這里的住宿關(guān)系R是序偶的集合。,3.6 關(guān)系及其表示,【定義】一個序偶的集合就稱為一個二

18、元關(guān)系，常用符號R表示。二元關(guān)系也簡稱關(guān)系。 若個體a與b之間存在關(guān)系R，則記作aRb，或∈R。,若規(guī)定關(guān)系R中序偶的x∈A, y∈B，（如上面的住店關(guān)系），這樣的序偶構(gòu)成的關(guān)系R，稱之為從A到B的一個二元關(guān)系。由A×B的定義知，從A到B的任何二元關(guān)系，均是A×B的子集。,3.6 關(guān)系及其表示,實際上，一個序偶的集合就確定了一個二元關(guān)系。,如：A?B={1,2,3}?{a,b,c}={,,, ,,,,,}

19、 R1={前后兩個元素的序號一樣} ={,,}關(guān)系除了可用序偶集合的形式表示外，還可用關(guān)系矩陣、關(guān)系圖表示。,3.6 關(guān)系及其表示,關(guān)系矩陣：設(shè)R?A×B，A=｛a1,a2,…,am｝，B={b1, b2,…,bn｝，那么R的關(guān)系矩陣MR為一m×n矩陣，它的第i,j分量rij只取值0或1，其中：,3.6 關(guān)系及其表示,如：A?B={1,2,3}?{a,b,c} R={,,},關(guān)系圖：令R?A?B

20、，將A、B的元素均畫成一個點，如果序偶?R，則從點x畫一條有向邊到點y。,3.6 關(guān)系及其表示,如：A={1,2,3,4,5,6,7,8}， R={,,,,,,, ,,, , , ,,} 注：序偶前后元素的集合相同時，關(guān)系圖還可簡化！,3.6 關(guān)系及其表示,如：A={1,2,3,4,5}， R={,,,,,,, ,, ,}，則其關(guān)系圖如下：,關(guān)系圖：令R?A?B，將A、B的元素均畫成一個點，如果序偶?R，則

21、從點x畫一條有向邊到點y。,3.6 關(guān)系及其表示,關(guān)系R的集合表達式、關(guān)系圖、關(guān)系矩陣三者可以唯一相互確定，并且它們各有各的特點， 可以根據(jù)不同的需要選用不同的表達方式。,3.4-3.6 小結(jié),小結(jié):一、基本概念 序偶、笛卡爾積、關(guān)系二、關(guān)系R的三種表達方式 集合表達式、關(guān)系圖、關(guān)系矩陣要求：掌握關(guān)系及其表達方法。,日常生活中經(jīng)常遇到關(guān)系的傳遞（復(fù)合）：如：設(shè)R1表示父與子的關(guān)系 (毛澤東)R1(毛岸青)，(

22、毛岸青)R1(毛新宇) 前一個關(guān)系R1與后一個關(guān)系R1復(fù)合（傳遞），可得到“毛澤東”與“毛新宇”的關(guān)系為雙重父子關(guān)系——爺孫關(guān)系。再如：設(shè)R2表示兄和弟的關(guān)系 (毛岸英)R2(毛岸青)，(毛岸青)R1(毛新宇) R2與R1復(fù)合，可得到“毛岸英”與“毛新宇”的關(guān)系——伯侄關(guān)系。需要在離散數(shù)學中引入關(guān)系的復(fù)合運算。注意上面關(guān)系傳遞（復(fù)合）的特點：前一個關(guān)系的后一個元素與后面關(guān)系的前一個元素是相同的。,3.7 關(guān)系

23、的復(fù)合與關(guān)系的逆（關(guān)系的運算）,目的是為了更好地表述現(xiàn)實。,【定義3.7.1】設(shè)關(guān)系F?A?A，G?A?A，稱集合{|?t(?F,?G)}為F與G的復(fù)合，記為F?G（因G在右邊，又稱之為G對F的右復(fù)合）,3.7 關(guān)系的復(fù)合與關(guān)系的逆,如：F={,}， G={,,} F ? G={,,},3.7 關(guān)系的復(fù)合與關(guān)系的逆,復(fù)合運算的關(guān)系矩陣表示為： M(F ? G)=M(F) ? M(G) 注：MF的第i行與M

24、G的第j列相乘時，“乘法”變?yōu)椤昂先?”，“加法”變?yōu)椤拔鋈?”。 如：上例中MF的第1行與MG的第3列相乘化為：(1?1)?(1?0)?(0?0)，結(jié)果為1。,【定義3.7.2】（關(guān)系的逆）稱{|?F }為F的逆，記為F-1,如：A={1,2,3}，F(xiàn)={,,}。 則F-1={,,}請同學們自己考慮一下，關(guān)系的矩陣與關(guān)系逆的矩陣有什么聯(lián)系？（轉(zhuǎn)置）關(guān)系的復(fù)合與關(guān)系逆運算的性質(zhì)：（請同學們自證?。?(1)結(jié)合律： (

25、P?R)?S=P?(R?S) (2)復(fù)合的逆：(P?R)-1= R-1?P-1,3.7 關(guān)系的復(fù)合與關(guān)系的逆,【定義3.8.1】(自反關(guān)系):設(shè)關(guān)系R?A?A，若?x?A，都有?R，則稱R是自反的。 【定義3.8.2】(反自反關(guān)系):設(shè)關(guān)系R?A?A，若?x?A，都有?R，則稱R是反自反的。,3.8 關(guān)系的分類,如: A={1,2,3} R1={,,,} 自反的! R2={} 反自反的! R3=

26、{,}，因為?R3不是自反的 因為?R3, ?R3,故不是反自反的由定義可知，“自反”關(guān)系矩陣的主對角線元素都為1，“反自反”關(guān)系矩陣的主對角線元素都為0。,如:A={1,2,3} R1={,,,} 自反的! R2={} 反自反! R3={,}不是自反 ,不是反自反.,,,,3.8 關(guān)系的分類,如:A={1,2,3} R1={,,,} 自反的! R2={} 反

27、自反! R3={,}不是自反 ,不是反自反.,R1自反，每個結(jié)點都有自旋(環(huán)),R2反自反,每個結(jié)點都沒有自旋(環(huán)),R3既非自反，也非反自反,3.8 關(guān)系的分類,【定義3.8.3】（全域關(guān)系）若關(guān)系R=A?A，則稱R為全域關(guān)系，記為EA,在全域關(guān)系中，由于直積的每個序偶都在關(guān)系R中，所以其關(guān)系矩陣全是1，主對角線肯定也為1，故是自反關(guān)系。,【定義3.8.4】（恒等關(guān)系）若所有形如的序偶都在關(guān)系R中，R中也只有這種形式的序偶，則稱

28、R為恒等關(guān)系，記為IA，IA={|?x?A},恒等關(guān)系的關(guān)系矩陣為單位陣；若R是自反關(guān)系，則恒等關(guān)系IA?R。,3.8 關(guān)系的分類,【定義3.8.5】(對稱關(guān)系)設(shè)關(guān)系R?A?A，若當?R時，有?R，則稱R為對稱關(guān)系?！径x3.8.6】(反對稱關(guān)系)設(shè)關(guān)系R?A?A，若當?R且x?y時，有?R，(即:若?R，?R?x=y），則稱R為反對稱關(guān)系。,如: A={1,2,3} R1={,} 對稱 R2={,,} 反

29、對稱 R3={,,} 因?R1不對稱,因與成對出現(xiàn),也不是反對稱,3.8 關(guān)系的分類,,,,,,,如: A={1,2,3} R1={,} 對稱 R2={,,} 反對稱 R3={,,} 因?R1不對稱,因與成對出現(xiàn),也不是反對稱。,對稱關(guān)系的關(guān)系矩陣為對稱矩陣，即MRT=MR反對稱關(guān)系的關(guān)系矩陣，在非對角線上非零元素都不對稱。,3.8 關(guān)系的分類,【定義3.3.8】(可傳遞關(guān)系):設(shè)關(guān)系R?A?A

30、，若當?R,?R時，有?R，則稱R為可傳遞關(guān)系。,可傳遞表示R中兩個序偶的復(fù)合仍在R中,即R?R?R例：A={a,b,c}，判斷以下關(guān)系R是否可傳遞： R={,,,} 解： R?R={,,,}? {,,,} ={,,,}?R 所以關(guān)系R不可傳遞。,3.8 關(guān)系的分類,,,,,,,,,R,R,R?R,可傳遞表示R中兩個序偶的復(fù)合仍在R中,即R?R?R例：

31、A={a,b,c}，判斷以下關(guān)系R 是否可傳遞： R={,,,} 解： R?R={,,,}?R，關(guān)系R不可傳遞。觀察關(guān)系矩陣：,3.8 關(guān)系的分類,MR?R的某些非零元素沒有在MR中出現(xiàn)。,可傳遞表示R中兩個序偶的復(fù)合仍在R中,即R?R?R再如：A={1,2,3}，判斷以下關(guān)系是否可傳遞： R1={,,,} 解： R1?R1={,,,}? {,,,}

32、 ={,,} ?R故可傳遞觀察關(guān)系矩陣：,,,,,,,3.8 關(guān)系的分類,MR?R的所有非零元素都在MR中出現(xiàn)。,記為：MR?R≤ MR,本節(jié)小結(jié)：關(guān)系的分類：1、自反關(guān)系：?x?A??R ? IA?R2、反自反關(guān)系：?x?A??R ? IA?R=?3、對稱關(guān)系：?R??R ? R=R-14、反對稱關(guān)系：?R,?R?x=y 或：?R且x?y??R ? R?R-1?IA5、傳遞關(guān)系：?R,?R?

33、?R ? R2?R在關(guān)系矩陣中的表現(xiàn)： 自反:主對角線均為1； 反自反:主對角線均為0 對稱:M=MT ； 反對稱:M?MT后只有主對角非0 傳遞:R2?R即M2?M,3.8 關(guān)系的分類,3.7-3.8 小結(jié),小結(jié):一、關(guān)系的運算 關(guān)系的復(fù)合、關(guān)系的逆二、關(guān)系的分類 自反、反自反，對稱、反對稱，可傳遞要求：掌握關(guān)系的基本運算及其性質(zhì)，關(guān)系的分類及不同類型的關(guān)系在關(guān)系矩陣中的表現(xiàn)。,

34、實際應(yīng)用中，有時會遇到這樣的問題：給定了某一關(guān)系R，該關(guān)系不具有所要求的某種性質(zhì)（如對稱性、自反性、可傳遞性等），要使其具有這一性質(zhì)，就需要對原關(guān)系進行擴充；但是，我們希望所進行的擴充是“最小”的，這種關(guān)系的擴充就是對原關(guān)系的、針對某一性質(zhì)的閉包運算。,3.9 關(guān)系的閉包,3.9 關(guān)系的閉包,【定義3.9.1】(自反閉包)設(shè)關(guān)系R?A?A，若存在關(guān)系R'?A?A，滿足如下條件，則稱R'為R的自反閉包： (1) R&

35、#39;自反； （R'的自反性） (2) R?R'； （R'對R的包含性） (3) 任一自反關(guān)系R”，若滿足R”?A?A且R?R”，必然有R'?R” （R'的最小性） 即：自反閉包是包含R的所有自反關(guān)系中，序偶數(shù)量最少的一個。R的自反閉包常記為：r(R),例3.9.1：令A(yù)={1,2,3}，R={,,}，求R的自反閉包。解：自反關(guān)系應(yīng)包含序偶，，，而

36、R中缺少序偶，補充可得： r(R)={,,,}由求解過程可知：r(R)=R?IA,3.9 關(guān)系的閉包,,,3.9 關(guān)系的閉包,【定義3.9.2】(對稱閉包)設(shè)關(guān)系R?A?A，若存在關(guān)系R'?A?A，滿足如下條件，則稱R'為R的對稱閉包： (1) R'對稱； （R'的對稱性） (2) R?R'； （R'對R的包含性） (3) 任一對稱關(guān)系R”

37、，若滿足R”?A?A且R?R”，必然有R‘?R”。 （R'的最小性） 即：對稱閉包是包含R的所有對稱關(guān)系中，序偶數(shù)量最少的一個。R的對稱閉包常記為：s(R),例3.9.2：令A(yù)={1,2,3}，R={,,,},求R的對稱閉包。解：由于關(guān)系R中，序偶的逆序偶不在R中，所以R不是對稱關(guān)系，添加該序偶可得： s(R)={,,,,}由求解過程可知：s(R)=R?RT.,,,3.9 關(guān)系的閉包,3.9 關(guān)系的閉包,【

38、定義3.9.3】(可傳遞閉包)設(shè)關(guān)系R?A?A，若存在關(guān)系R'?A?A，滿足如下條件，則稱R'為R的可傳遞閉包： (1) R'可傳遞； （R'的可傳遞性） (2) R?R'； （R'對R的包含性） (3) 任一可傳遞關(guān)系R”，若滿足R”?A?A且R?R”，必然有R'?R” （R'的最小性） 即：可傳遞閉包是包含R的所有可傳遞關(guān)系中

39、，序偶數(shù)量最少的一個。R的可傳遞閉包常記為：t(R),例3.9.3： 設(shè)A={a,b,c,d}，R={,,,, }，求其傳遞閉包。解：（傳遞閉包的求解較為繁瑣，只介紹求解思路) 先求R2，若R2?R則R是傳遞關(guān)系，即不添序偶就得傳遞關(guān)系，傳遞閉包就是R。 若R2?R，表示復(fù)合產(chǎn)生的序偶不在R中，為了可傳遞，故將復(fù)合出來的序偶投入到R中即得到R2?R。新序偶與舊序偶又復(fù)合出二代新序偶。 若二代新序偶已在R2?R中，則

40、R2?R已是可傳遞關(guān)系，則它就是傳遞閉包，即t(R)= R2?R。 否則將二代新序偶放入R中，得到R3?R2?R。 重復(fù)以上過程，直到得到一個傳遞關(guān)系。,3.9 關(guān)系的閉包,等價關(guān)系是集合劃分的一個重要工具，在代數(shù)系統(tǒng)、圖論與其它學科中有著重要的應(yīng)用。,3.10 等價關(guān)系,【定義3.10.1】(等價關(guān)系)設(shè)關(guān)系R?A?A，如果R是自反的、對稱的、可傳遞的，則稱之為等價關(guān)系。,例：設(shè)A={1,2,3,4,5,6,7,8}，R=

41、{|x-y=3k，k為整數(shù)} 判斷:R是否為等價關(guān)系。解：(1) ?x?A,因x-x=0=3*0 ，故?R，自反 (2) ?R ?x-y=3k ?y-x=3(-k) ??R 對稱 (3) ?R,?R ?x-y=3k,y-z=3m ?x-z=3(k+m) ??R 可傳遞x-y=3k（k為整數(shù)），也可表示為：3|(x-y)——整除,【定義3.10.2】(等價類)設(shè)R為集合A上的等價關(guān)系。

42、對每一a∈A，將A中所有與a等價的元素所構(gòu)成的集合記為[a]R， 即形式化為： [a]R=｛x|x∈A∧xRa｝稱[a]R為a關(guān)于R所生成的等價類，簡稱a的等價類，簡記為[a]，a稱為[a]R的代表元素。,3.10 等價關(guān)系,簡言之：A中彼此等價的元素所組成的子集合,稱為A關(guān)于R的等價類。,A中彼此等價的元素所組成的子集合,稱為A關(guān)于R的等價類。,如上例：A={1,2,3,4,5,6,7,8}，R={：3|(x-y)}

43、三個等價類： [1]={1,4,7} （也可記為[4]或[7]） [2]={2,5,8} （也可記為[5]或[8]） [3]={3,6} （也可記為[6]）注意到：[1]中元素被3除，余數(shù)皆為1； [2]中元素被3除，余數(shù)皆為2； [3]中元素被3除，余數(shù)皆為0。x-y=3k(k為整數(shù))或3|(x-y)，即表示x和y被3除所得余數(shù)相同。,3.10 等價關(guān)系,,同余,例題

44、：（同余關(guān)系）考察整數(shù)集合Z中的二元關(guān)系 R={〈x，y〉：m|(x-y), m∈Z+} ={〈x，y〉：x≡y(mod m), m∈Z+}其中“|”表示整除關(guān)系，Z+表示正整數(shù)集合， （類似前例）可證R是等價關(guān)系。Z關(guān)于R有m個等價類：[0],[1],……,[m-1]；[r]={x|x=mk+r,k為整數(shù)}={x|mod(x,m)=r} ，0≤r<m,3.10 等價關(guān)系,如：取m=4, R有4個

45、不同的等價類； ［0］=｛…，-12,-8,-4,0,4，8,12，…｝=｛x|4整除x｝ ［1］=｛…，-11,-7,-3,1,5, 9,13，…｝=｛x|4除x余1｝ ［2］=｛…，-10,-6,-2,2,6,10,14，…｝=｛x|4除x余2｝ ［3］=｛…，-9, -5,-1,3,7,11,15，…｝=｛x|4除x余3｝,【定義3.10.3】(商集)設(shè)R?A?A，R是等價關(guān)系，A1,A2,…,Ak是基于R得到的

46、等價類，則稱集合{A1,A2,…,Ak}為A關(guān)于R的商集，記為A/R。,如上例：A={1,2,3,4,5,6,7,8} R={|x-y=3k，k為整數(shù)} 基于R得到三個等價類： A1={1,4,7}=[1]，A2={2,5,8}=[2]，A3={3,6}=[3] 商集：A/R={A1,A2,A3}={[1],[2],[3]} ={{1,4,7}, {2,5,8}, {3,6}},3.

47、10 等價關(guān)系,【定義3.10.3】(商集)設(shè)R?A?A，R是等價關(guān)系，A1,A2,…,Ak是基于R得到的等價類，則稱集合{A1,A2,…,Ak}為A關(guān)于R的商集，記為A/R。,例題：（Z關(guān)于模m的同余關(guān)系） 整數(shù)集合Z中的二元關(guān)系R， R={〈x，y〉：m|(x-y), m∈Z+} ={〈x，y〉：x≡y(mod m), m∈Z+} Z關(guān)于R有m個等價類：[0],[1],……,[m-1]

48、 商集：Z/R={[0],[1],[2],……，[m-1]},3.10 等價關(guān)系,【定理3.10.1】 設(shè)R?A?A，R是等價關(guān)系，A1,A2,…,Ak是利用R得到的k個不同的等價類，則A1,A2,…,Ak為集合A的劃分。,【定義3.10.4】(劃分)設(shè)A1,A2,…,Ak是A的子集，若i≠j時Ai∩Aj=Φ，并且A=A1?A2?…?Ak ，則稱A1,A2,…,Ak為A的一個劃分。,3.10 等價關(guān)系,證明（略）：只要證明（1）不同的

49、等價類互不相交（即i≠j時Ai∩Aj=Φ）；（2）所有等價類的并集等于原集合（即A=A1?A2?…?Ak）。,如前例：A={1,2,3,4,5,6,7,8} R={|x-y=3k，k為整數(shù)}基于R得到三個等價類： A1={1,4,7}，A2={2,5,8}，A3={3,6}A1,A2,A3就是A的一個劃分： (1) i≠j時Ai∩Aj=Φ (2) A=A1?A2?A3問題： 由等價關(guān)系

50、能夠找出劃分{1,4,7},{2,5,8},{3,6} 反過來，能否由劃分構(gòu)造等價關(guān)系？,3.10 等價關(guān)系,如前例：A={1,2,3,4,5,6,7,8} R={|x-y=3k，k為整數(shù)} A1={1,4,7}，A2={2,5,8}，A3={3,6}觀察到： R={,,,,,, ,,} ? {,, ,,,,,, } ? {,,,} ={1,4,7}

51、5;{1,4,7} ? {2,5,8}×{2,5,8} ? {3,6}×{3,6} = A1?A1 ? A2?A2 ? A3?A3,3.10 等價關(guān)系,【定理3.10.2】 設(shè)A1,A2,…,Ak是A的劃分，R=A1?A1?A2?A2?…?Ak?Ak，則R是等價關(guān)系。,證明：（略） (1)?x?A，由劃分的定義可知，x肯定屬于某個子集Ai，所以?Ai?Ai，故?R,R自反。 (2)若?R，

52、則至少屬于某個子集Ai的直積，設(shè)?Ai?Ai，由于Ai的直積關(guān)系是對稱的，故?Ai?Ai?R,故R對稱。 (3)只要證明：若?Ai?Ai，則?Ai?Ai。假設(shè)?Aj?Aj，其中i?j。由?Ai?Ai有x?Ai,y?Ai，由?Aj?Aj，有y?Aj,z?Aj，故y?Ai又y?Aj，這不可能，故假設(shè)錯，只能?Ai?Ai。因Ai的直積是可傳遞關(guān)系，故?Ai?Ai?R，故R可傳遞。,3.10 等價關(guān)系,本次課小結(jié),小結(jié)：一、關(guān)系的閉包

53、 自反閉包 r(R)=R?IA 對稱閉包 s(R)=R?RT 可傳遞閉包 t(R)二、等價關(guān)系與集合的劃分 等價關(guān)系、等價類、商集、集合劃分要求：掌握閉包、等價關(guān)系等相關(guān)概念； 掌握自反閉包與對稱閉包的求法。,等價關(guān)系和偏序關(guān)系都是數(shù)據(jù)處理的重要工具：等價關(guān)系用于對數(shù)據(jù)進行分類；偏序關(guān)系則用于對數(shù)據(jù)進行排序。,3.11 偏序關(guān)系,【定義3.11.1】(偏序關(guān)系)設(shè)關(guān)系R?A

54、?A，如果R是自反、反對稱、可傳遞的，則稱之稱為偏序關(guān)系。,例題：設(shè)A=實數(shù)集，R是實數(shù)中“小于等于”關(guān)系，即： R={|x,y是實數(shù)，且x?y}，則R是偏序關(guān)系。證明： (1)?x?A(實數(shù))，有x?x，故?R，即為自反關(guān)系； (2)若?R,?R，則x?y且y?x,故x=y,故反對稱； (3)若?R,?R，則x?y且y?z，故x?z,R可傳遞。,例題：設(shè)A=自然數(shù)集，R是自然數(shù)集中的整除關(guān)系，即：

55、 R={: x|y}，則R是偏序關(guān)系。證明： (1) ?x?A，因為x|x，因此?R，即自反； (2) 若x|y,y|x即y=kx,x=my(k、m為整數(shù))，則有x=m(kx), 故mk=1,故k=m=1，故x=y，故反對稱； (3) 若x|y,y|z即y=kx,z=my，則z=m(kx)=mkx，即x|z，故可傳遞。,注： 1、偏序關(guān)系可理解為廣義的“小于等于”關(guān)系， 記為“?”。

56、 2、當??時，寫成x?y，（主要為了直觀）。 3、當?? 但x?y時，記成x<y，即嚴格小于。,3.11 偏序關(guān)系,例題：設(shè)A={1,2,3,4,5,6}，考慮整除關(guān)系 R={:x|y} R={,,,,,, , ,,,,, , } ?R，可記為1?2,也可記為1?R，可記為2?2,不可記為2?R即2?4 4與2可比，因為?R即2?4 2與5不可比，因為?R,?R,【定義3

57、.11.2】(x與y可比)設(shè)R?A?A是偏序關(guān)系，x與y是A中的元素，若序偶與至少有一個在R中，則稱x與y是可比的。,3.11 偏序關(guān)系,偏序關(guān)系圖的繪制：若??即x?y，將中“小”的元素x置于下方，“大”的元素y置于上方，即將箭頭所指的對象畫在上方。例題：設(shè)A={1,2,3,4,5,6}，考慮整除關(guān)系 R={:x|y} R={,,,,,, , ,,,,, , },3.11 偏序關(guān)系,例題：設(shè)A={1,2,3,4

58、,5,6}，考慮整除關(guān)系 R={:x|y} R={,,,,,, , ,,,,, , },3.11 偏序關(guān)系,1,4,2,6,3,5,例題：設(shè)A={1,2,3,4,5,6}，考慮整除關(guān)系 R={:x|y} R={,,,,,, , ,,,,, , },3.11 偏序關(guān)系,1,4,2,6,3,5,例題：設(shè)A={1,2,3,4,5,6}，考慮整除關(guān)系 R={:x|y} R={,,,,,, ,

59、 ,,,,, , },3.11 偏序關(guān)系,1,4,2,6,3,5,【繪制結(jié)束】,如：1、A={1,2,3,4,5,6}，考慮小于等于關(guān)系： R={:x?y} 全序關(guān)系2、B={1,2}, A={?,{1,2}}，考慮包含關(guān)系： R={:x?y,x?A,y?A} 全序關(guān)系3、B={1,2}, A={?,{1},{2},{1,2}}，考慮包含關(guān)系： R={:x?y,x?A,y?A}

60、 偏序關(guān)系,【定義3.11.3】(全序關(guān)系)設(shè)R?A?A是偏序關(guān)系，若A中任意兩個元素都可比，則稱R為A上的全序關(guān)系（或線序關(guān)系）,3.11 偏序關(guān)系,例： 1、A={1,2,3,4,5,6}，R={:x?y}，偏序集 2、B={1,2}, A={?,{1},{2},{1,2}} R1={:x?y,x?A,y?A}， 偏序集 3、B={1,2}, A={?,{1,2}} R2=

61、{:x?y,x?A,y?A}， 偏序集 ,【定義3.11.6】(偏序集)設(shè)R?A?A是偏序關(guān)系，將集合A與偏序關(guān)系R組成的一個整體稱為偏序集，記為。,3.11 偏序關(guān)系,注：以后說到偏序關(guān)系時，可理解為偏序集,哈斯圖：將偏序關(guān)系圖繪制成箭頭都朝上方；然后去掉所有箭頭、自旋邊、復(fù)合邊，得到的簡化圖稱為哈斯圖。,3.11 偏序關(guān)系,如： A={?,{1},{2},{1,2}}，R={:x?y,x?A,y?A},哈斯圖中，如果某個元素y在元素

62、x的直接上方，即：x?A, y?A, x<y，??z?A,使得x<z<y則稱y蓋住x。,如：B={1,2}, A={?,{1},{2},{1,2}} R1={：x?y,x?A,y?A} 偏序集： {1}蓋住?, {2}蓋住?, 但{1,2}并不蓋住?.,3.11 偏序關(guān)系,最大元：設(shè)是偏序集，B?A,y0?B,若?x?B,均有?R，則稱y0是B的最大元。即y0與B的每個元素都可比，且比其

63、大。（最小元類似定義）,B={a,b,c,d,e,f,g,h} 無最大元、無最小元,B={1~ 8} 有最小,B={1,2,4,8} 有最大與最小,B={b,c,d,e,f} 有最大元,3.11 偏序關(guān)系,極大元：不存在x使?R，即哈圖無元居其上極小元：不存在x使?R，即哈圖無元居其下,極大元：{a,f,h},極小元：{a,b,c,g},極大元：{8,6,9,5,7},極小元：{1},3.11 偏序關(guān)系,上界：設(shè)在偏序集中，B?A

64、，y?A，若?x?B都有?R，則稱y是B的上界。即：y與B中每個元素都可比，且都比B中的元素大。,設(shè)：B={b,c}其上界有：f,d,e,設(shè)：B={1,2}其上界有：2、4、6、8,3.11 偏序關(guān)系,上確界：在偏序集中，B?A，設(shè)C為B的所有上界元素的集合，若C中有最小元，則稱該最小元稱為B的上確界。,設(shè)：B={b,c}其上界的集合為{f,d,e}無最小元，無上確界,設(shè)：B={1,2}其上界的集合為{2,4,6,8}最小元

65、(上確界)為 2,3.11 偏序關(guān)系,設(shè)：B={f,d,e}其下界為b和c,設(shè)：B={8,4,6,2}其下界為1和2,下界：設(shè)在偏序集中，B?A，y?A，若?x?B都有?R，則稱y是B的下界。即：y與B中每個元素都可比，且都比B中的元素小。,3.11 偏序關(guān)系,下確界：在偏序集中，B?A，設(shè)C為B的所有下界元素的集合，若C中有最大元，則稱該最大元為B的下確界。,設(shè)：B={f,d,e}其下界集合為{b,c}無最大元，無下確界,設(shè)：

66、B={8,4,6,2}其下界集合為{1,2}最大元(下確界)為 2,3.11 偏序關(guān)系,小結(jié)：基本概念1、偏序關(guān)系（自反、反對稱、可傳遞），偏序集；2、可比，全序關(guān)系；3、最大元、最小元，極大元、極小元；4、上界、上確界，下界、下確界。要求：1、掌握相關(guān)的概念，會畫Hasse圖；2、會求一個子集的極小(大)元,最小(大)元,上界與下界,上確界及下確界。,本次課小結(jié),一、集合論初步1.集合的表示,空集、全集、子集、冪