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

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

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

3、系。,3.1 集合的基本概念,子集A?B：A中的每個(gè)元素都是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個(gè)元素 ,即2|A|個(gè)。冪集又記為2A。,3.1 集合的基本概念,1、交集：A?B={由同時(shí)屬于A與B的元素組成}2、并集：A?B={由屬于A或?qū)儆贐的元素組成}3、差集：A-B={由屬于A但不屬于B的元素組成}4、

5、余集(補(bǔ)集)：?A={全集U中不屬于A的元素組成}=U-A5、對(duì)稱(chēng)差：A?B= (A?B)-(A?B) {由屬于A與B的并集但不屬于A與B的交集元素組成},3.2 集合的運(yùn)算與性質(zhì),【定義3.2.3】（集合相等） 設(shè)A、B是兩個(gè)集合，若A?B、B?A，則稱(chēng)兩個(gè)集合A與B相等，記為A=B。 集合的運(yùn)算性質(zhì)：（與命題邏輯類(lèi)同：? ∨, ? ∧, ? ?）冪等律：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 集合的運(yùn)算與性質(zhì),|A|=集合A的元素個(gè)數(shù)。,3.3 有窮集的計(jì)數(shù),定理3.3.1：（包含排斥原理） |A1?A2|=|A1|+|A2|-|A1?A2| 因?yàn)楣膊糠炙懔藘纱危?例：A1={藍(lán)球隊(duì)}，|A1|=10，A2={足球隊(duì)}，|A2|=13，雙重身份球員3人，請(qǐng)問(wèn)這二個(gè)球隊(duì)總共多少人？ 解：|A1?A2|=|A1|+|A2|-|A1?A2|=10+1

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

9、同時(shí)參加二隊(duì)的有多少人？ 解：|A1?A2?A3|=?|Ai|-?|Ai?Aj|+?|Ai?Aj?Ak| 58=(38+15+20)-?|Ai?Aj|+3 ?|Ai?Aj|=18，即同時(shí)參加二隊(duì)的有18人。,例題：求在[1,300]的整數(shù)中，能被3或5或7整除的整數(shù)的個(gè)數(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í)整除的個(gè)數(shù)：|A3?A5|=[300/15]=20 能被3與7同時(shí)整除的個(gè)數(shù)：|A3?A7|=[300/21]=14 能被5與7同時(shí)整除的個(gè)數(shù)：|A5?A7|=[300/35]=8 能被3、5、7同時(shí)整除的個(gè)數(shù)：|A3?A5?A7|=2 能被3或被5或被7整除的個(gè)數(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 有窮集的計(jì)數(shù),小結(jié)：一、基本概念 集合、子集、冪集二、集合的運(yùn)算及性質(zhì) 1、交、并、差、余（補(bǔ)）、對(duì)稱(chēng)差 2、有窮集合的計(jì)數(shù)（包含互斥原理）要求：熟練掌握集合的運(yùn)算及其相關(guān)性質(zhì)。,3.1-3.3小結(jié),【定義3.4.1】（序偶）將有固定次序的兩個(gè)對(duì)象寫(xiě)在一塊，稱(chēng)為序偶，即有秩序的兩個(gè)對(duì)象，記為或。,

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

13、如：，，，，三維空間中點(diǎn)的坐標(biāo) 等?！径x3.4.4】如果是n-1元組，而,xn>是序偶，則稱(chēng)為為n元組。,3.4 序偶,【定義3.5.1】（直積） 令A(yù)、B是兩個(gè)集合，稱(chēng)集合{|x?A, y?B}為A與B的直積或笛卡爾積，記為A?B。（直積的結(jié)果是一個(gè)集合?。?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ù)乘運(yùn)算),易證直積具有以下性質(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個(gè)集合，稱(chēng)n元組的集合{|x1?A1, x2?A2,…, xn?An}為A1,A2,…,An的直積或笛卡爾積，記為A1?A2?…?An。,我們僅證明(1)。對(duì)任意的 ∈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)系。 例如：人類(lèi)集合中的父子、兄弟、同學(xué)、同鄉(xiāng)等關(guān)系；實(shí)數(shù)之間的大于、小于、等于關(guān)系；兩條直線間的平行、 垂直等關(guān)系；集合間的包含、元素與集合的屬于等等都是關(guān)系。 兩個(gè)個(gè)體之間的關(guān)系稱(chēng)為二元關(guān)系；三個(gè)以上個(gè)體之間的關(guān)系稱(chēng)為多元關(guān)

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

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

19、 R1={前后兩個(gè)元素的序號(hào)一樣} ={,,}關(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的元素均畫(huà)成一個(gè)點(diǎn)，如果序偶?R，則從點(diǎn)x畫(huà)一條有向邊到點(diǎn)y。,3.6 關(guān)系及其表示,如：A={1,2,3,4,5,6,7,8}， R={,,,,,,, ,,, , , ,,} 注：序偶前后元素的集合相同時(shí)，關(guān)系圖還可簡(jiǎn)化！,3.6 關(guān)系及其表示,如：A={1,2,3,4,5}， R={,,,,,,, ,, ,}，則其關(guān)系圖如下：,關(guān)系圖：令R?A?B，將A、B的元素均畫(huà)成一個(gè)點(diǎn)，如果序偶?R，則

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

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

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

24、G的第j列相乘時(shí)，“乘法”變?yōu)椤昂先?”，“加法”變?yōu)椤拔鋈?”。 如：上例中MF的第1行與MG的第3列相乘化為：(1?1)?(1?0)?(0?0)，結(jié)果為1。,【定義3.7.2】（關(guān)系的逆）稱(chēng){|?F }為F的逆，記為F-1,如：A={1,2,3}，F(xiàn)={,,}。 則F-1={,,}請(qǐng)同學(xué)們自己考慮一下，關(guān)系的矩陣與關(guān)系逆的矩陣有什么聯(lián)系？（轉(zhuǎn)置）關(guān)系的復(fù)合與關(guān)系逆運(yùn)算的性質(zhì)：（請(qǐng)同學(xué)們自證！） (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，則稱(chēng)R是自反的。 【定義3.8.2】(反自反關(guān)系):設(shè)關(guān)系R?A?A，若?x?A，都有?R，則稱(chēng)R是反自反的。,3.8 關(guān)系的分類(lèi),如: A={1,2,3} R1={,,,} 自反的! R2={} 反自反的! R3=

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

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

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

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

30、，若當(dāng)?R,?R時(shí)，有?R，則稱(chēng)R為可傳遞關(guān)系。,可傳遞表示R中兩個(gè)序偶的復(fù)合仍在R中,即R?R?R例：A={a,b,c}，判斷以下關(guān)系R是否可傳遞： R={,,,} 解： R?R={,,,}? {,,,} ={,,,}?R 所以關(guān)系R不可傳遞。,3.8 關(guān)系的分類(lèi),,,,,,,,,R,R,R?R,可傳遞表示R中兩個(gè)序偶的復(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)系的分類(lèi),MR?R的某些非零元素沒(méi)有在MR中出現(xiàn)。,可傳遞表示R中兩個(gè)序偶的復(fù)合仍在R中,即R?R?R再如：A={1,2,3}，判斷以下關(guān)系是否可傳遞： R1={,,,} 解： R1?R1={,,,}? {,,,}

32、 ={,,} ?R故可傳遞觀察關(guān)系矩陣：,,,,,,,3.8 關(guān)系的分類(lèi),MR?R的所有非零元素都在MR中出現(xiàn)。,記為：MR?R≤ MR,本節(jié)小結(jié)：關(guān)系的分類(lèi)：1、自反關(guān)系：?x?A??R ? IA?R2、反自反關(guān)系：?x?A??R ? IA?R=?3、對(duì)稱(chēng)關(guān)系：?R??R ? R=R-14、反對(duì)稱(chēng)關(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)： 自反:主對(duì)角線均為1； 反自反:主對(duì)角線均為0 對(duì)稱(chēng):M=MT ； 反對(duì)稱(chēng):M?MT后只有主對(duì)角非0 傳遞:R2?R即M2?M,3.8 關(guān)系的分類(lèi),3.7-3.8 小結(jié),小結(jié):一、關(guān)系的運(yùn)算 關(guān)系的復(fù)合、關(guān)系的逆二、關(guān)系的分類(lèi) 自反、反自反，對(duì)稱(chēng)、反對(duì)稱(chēng)，可傳遞要求：掌握關(guān)系的基本運(yùn)算及其性質(zhì)，關(guān)系的分類(lèi)及不同類(lèi)型的關(guān)系在關(guān)系矩陣中的表現(xiàn)。,

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

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

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

37、，若滿足R”?A?A且R?R”，必然有R‘?R”。 （R'的最小性） 即：對(duì)稱(chēng)閉包是包含R的所有對(duì)稱(chēng)關(guān)系中，序偶數(shù)量最少的一個(gè)。R的對(duì)稱(chēng)閉包常記為：s(R),例3.9.2：令A(yù)={1,2,3}，R={,,,},求R的對(duì)稱(chēng)閉包。解：由于關(guān)系R中，序偶的逆序偶不在R中，所以R不是對(duì)稱(chēng)關(guān)系，添加該序偶可得： s(R)={,,,,}由求解過(guò)程可知：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，滿足如下條件，則稱(chēng)R'為R的可傳遞閉包： (1) R'可傳遞； （R'的可傳遞性） (2) R?R'； （R'對(duì)R的包含性） (3) 任一可傳遞關(guān)系R”，若滿足R”?A?A且R?R”，必然有R'?R” （R'的最小性） 即：可傳遞閉包是包含R的所有可傳遞關(guān)系中

39、，序偶數(shù)量最少的一個(gè)。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ù)合出來(lái)的序偶投入到R中即得到R2?R。新序偶與舊序偶又復(fù)合出二代新序偶。 若二代新序偶已在R2?R中，則

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

41、{|x-y=3k，k為整數(shù)} 判斷:R是否為等價(jià)關(guān)系。解：(1) ?x?A,因x-x=0=3*0 ，故?R，自反 (2) ?R ?x-y=3k ?y-x=3(-k) ??R 對(duì)稱(chēng) (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】(等價(jià)類(lèi))設(shè)R為集合A上的等價(jià)關(guān)系。

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

43、三個(gè)等價(jià)類(lèi)： [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 等價(jià)關(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ù)集合， （類(lèi)似前例）可證R是等價(jià)關(guān)系。Z關(guān)于R有m個(gè)等價(jià)類(lèi)：[0],[1],……,[m-1]；[r]={x|x=mk+r,k為整數(shù)}={x|mod(x,m)=r} ，0≤r<m,3.10 等價(jià)關(guān)系,如：取m=4, R有4個(gè)

45、不同的等價(jià)類(lèi)； ［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是等價(jià)關(guān)系，A1,A2,…,Ak是基于R得到的

46、等價(jià)類(lèi)，則稱(chēng)集合{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得到三個(gè)等價(jià)類(lèi)： 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 等價(jià)關(guān)系,【定義3.10.3】(商集)設(shè)R?A?A，R是等價(jià)關(guān)系，A1,A2,…,Ak是基于R得到的等價(jià)類(lèi)，則稱(chēng)集合{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個(gè)等價(jià)類(lèi)：[0],[1],……,[m-1]

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

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

50、能夠找出劃分{1,4,7},{2,5,8},{3,6} 反過(guò)來(lái)，能否由劃分構(gòu)造等價(jià)關(guān)系？,3.10 等價(jià)關(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 等價(jià)關(guān)系,【定理3.10.2】 設(shè)A1,A2,…,Ak是A的劃分，R=A1?A1?A2?A2?…?Ak?Ak，則R是等價(jià)關(guān)系。,證明：（略） (1)?x?A，由劃分的定義可知，x肯定屬于某個(gè)子集Ai，所以?Ai?Ai，故?R,R自反。 (2)若?R，

52、則至少屬于某個(gè)子集Ai的直積，設(shè)?Ai?Ai，由于Ai的直積關(guān)系是對(duì)稱(chēng)的，故?Ai?Ai?R,故R對(duì)稱(chēng)。 (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è)錯(cuò)，只能?Ai?Ai。因Ai的直積是可傳遞關(guān)系，故?Ai?Ai?R，故R可傳遞。,3.10 等價(jià)關(guān)系,本次課小結(jié),小結(jié)：一、關(guān)系的閉包

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

54、?A，如果R是自反、反對(duì)稱(chēng)、可傳遞的，則稱(chēng)之稱(chēng)為偏序關(guān)系。,例題：設(shè)A=實(shí)數(shù)集，R是實(shí)數(shù)中“小于等于”關(guān)系，即： R={|x,y是實(shí)數(shù)，且x?y}，則R是偏序關(guān)系。證明： (1)?x?A(實(shí)數(shù))，有x?x，故?R，即為自反關(guān)系； (2)若?R,?R，則x?y且y?x,故x=y,故反對(duì)稱(chēng)； (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，因?yàn)閤|x，因此?R，即自反； (2) 若x|y,y|x即y=kx,x=my(k、m為整數(shù))，則有x=m(kx), 故mk=1,故k=m=1，故x=y，故反對(duì)稱(chēng)； (3) 若x|y,y|z即y=kx,z=my，則z=m(kx)=mkx，即x|z，故可傳遞。,注： 1、偏序關(guān)系可理解為廣義的“小于等于”關(guān)系， 記為“?”。

56、 2、當(dāng)??時(shí)，寫(xiě)成x?y，（主要為了直觀）。 3、當(dāng)?? 但x?y時(shí)，記成x<y，即嚴(yán)格小于。,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可比，因?yàn)?R即2?4 2與5不可比，因?yàn)?R,?R,【定義3

57、.11.2】(x與y可比)設(shè)R?A?A是偏序關(guān)系，x與y是A中的元素，若序偶與至少有一個(gè)在R中，則稱(chēng)x與y是可比的。,3.11 偏序關(guān)系,偏序關(guān)系圖的繪制：若??即x?y，將中“小”的元素x置于下方，“大”的元素y置于上方，即將箭頭所指的對(duì)象畫(huà)在上方。例題：設(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中任意兩個(gè)元素都可比，則稱(chēng)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組成的一個(gè)整體稱(chēng)為偏序集，記為。,3.11 偏序關(guān)系,注：以后說(shuō)到偏序關(guān)系時(shí)，可理解為偏序集,哈斯圖：將偏序關(guān)系圖繪制成箭頭都朝上方；然后去掉所有箭頭、自旋邊、復(fù)合邊，得到的簡(jiǎn)化圖稱(chēng)為哈斯圖。,3.11 偏序關(guān)系,如： A={?,{1},{2},{1,2}}，R={:x?y,x?A,y?A},哈斯圖中，如果某個(gè)元素y在元素

62、x的直接上方，即：x?A, y?A, x<y，??z?A,使得x<z<y則稱(chēng)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，則稱(chēng)y0是B的最大元。即y0與B的每個(gè)元素都可比，且比其

63、大。（最小元類(lèi)似定義）,B={a,b,c,d,e,f,g,h} 無(wú)最大元、無(wú)最小元,B={1~ 8} 有最小,B={1,2,4,8} 有最大與最小,B={b,c,d,e,f} 有最大元,3.11 偏序關(guān)系,極大元：不存在x使?R，即哈圖無(wú)元居其上極小元：不存在x使?R，即哈圖無(wú)元居其下,極大元：{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，則稱(chēng)y是B的上界。即：y與B中每個(gè)元素都可比，且都比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中有最小元，則稱(chēng)該最小元稱(chēng)為B的上確界。,設(shè)：B={b,c}其上界的集合為{f,d,e}無(wú)最小元，無(wú)上確界,設(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，則稱(chēng)y是B的下界。即：y與B中每個(gè)元素都可比，且都比B中的元素小。,3.11 偏序關(guān)系,下確界：在偏序集中，B?A，設(shè)C為B的所有下界元素的集合，若C中有最大元，則稱(chēng)該最大元為B的下確界。,設(shè)：B={f,d,e}其下界集合為{b,c}無(wú)最大元，無(wú)下確界,設(shè)：

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