《離散數(shù)學(xué)》講義 - 3

1、第三章 集合與關(guān)系 31 集合的概念和表示法1集合論起源：起源16世紀(jì)末，數(shù)學(xué)危機(jī)（理發(fā)師：只給那些不給自己理發(fā)的人理發(fā)，不給那些給自己理發(fā)的人理發(fā)）（理發(fā)師？屬于那一類？）定義集合的方法在邏輯上來說，有矛盾1876-1908，cantor奠定了集合論基礎(chǔ)(樸素集合論)20世紀(jì)初，zermole建立的公理化集合論，解決了悖論（公理化集合論）231、集合概念及表示 （1）集合概念一般地說，把具有相同性質(zhì)的一些東西，匯集成一個(gè)整體，就形成一個(gè)集合。例如：教室內(nèi)的桌子；全國(guó)的高等學(xué)校；自然數(shù)的全體；直線上的點(diǎn)。分類有限集：集合的元素個(gè)數(shù)是限的。無限集：集合的元素個(gè)數(shù)是無限的。4（2）表示集合：AZ；

2、元素（集合中的事物）：az。 I 元素a屬于集合A， 記作：aA II 元素a不屬于集合A， 記作：aA5說明集合的方法I 列舉法：將某集合的元素列舉出來。例如：A=a,b,c,d, D=桌子，燈泡，自然數(shù)，老虎， C=2,4,6,2n注意：集合的元素可以是一個(gè)集合。例如：S=a,1,2,p,q， qq，但qS。II 敘述法：利用一些規(guī)則，來決定某一事物是否屬于該集合。例如：S1=x|x是正奇數(shù)S2=x|x是中國(guó)的省S3=y|y=a或y=b。另外，用P(x)表示任何謂詞，則x|P(x)可表示集合。62、集合相等外延性原理：兩個(gè)集合是相等的，當(dāng)且僅當(dāng)它們有相同的成員。 兩個(gè)集合A和B相等，記作：

3、A=B， 兩個(gè)集合不相等，則記作AB。7例如：設(shè)A是小于10的素?cái)?shù)集合，即A=2,3,5,7，設(shè)代數(shù)方程x417x3101x2247x2100的所有根可組成集合B，則B=2,3,5,7。 又如：1,2,4=1,2,2,4 1,2,4=1,4,2 1,3,5,=x|x是正奇數(shù) 但： 1,2,41,2,4注意：集合沒有次序之分，集合中的元素可以重復(fù)。83、子集（1）概念定義3-1.1 設(shè)A、B是任意兩個(gè)集合，假設(shè)A是每一個(gè)元素是B的成員，則稱A為B的子集，或A包含在B內(nèi)，或B包含A。記作：AB，或BA。AB(x)(xAxB)例如：A=1,2,3，B=1,2，C=1,3，D=3;則有：BA，CA，D

4、A，DC。根據(jù)子集的定義，有：AA 自反性(AB)(BC)(AC)傳遞性9（2）應(yīng)用定理3-1.1 集合A和B相等的充分必要條件是這兩個(gè)集合互為子集。104、真子集 定義3-1.3 如果集合A的每一個(gè)元素都屬于B，但集合B中至少有一個(gè)元素不屬于A，則稱A為B的真子集。 記作：AB。即：AB(AB)(AB) AB(x)(xAxB)(x)(xBxA)115、空集（1）概念定義3-1.3 不包含任何元素的集合是空集。記作：。x|P(x)P(x)， 其中P(x)是任意謂詞。注意：，但。12（2）性質(zhì)定理3-1.2 對(duì)于任意一個(gè)集合A，A。注意：I 對(duì)于每一個(gè)非空集合A，至少有兩個(gè)不同的子集：A和，即：

5、AA和A。我們稱A和為平凡子集。II 一般來說，A的每一個(gè)元素都能確定A的一個(gè)子集，即若aA，則aA。136、全集定義3-1.4 在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集。記作：E。(x)(xE)恒真。Ex|P(x)P(x)，P(x)任何謂詞。注意：全集概念相當(dāng)于論域 設(shè)全集E=a,b,c， 可能的子集有：S0=,S1=a, S2=b, S3=c, S4=a,b,S5=a,c, S6=b,c, S7=a,b,c。 SiE(i=0,1,2,7)。注意：對(duì)于一個(gè)元素個(gè)數(shù)為n的全集E，其可能的子集個(gè)數(shù)為2n。147、冪集 定義3-1.5 給定集合A，有集合A的所有子集為元素組成

6、的集合，稱為集合A的冪集。記作： P (A)例如：A=a,b,c P (A) = ,a, b, c, a,b,a,c,b,c, a,b,c15（2）性質(zhì)定理3-1.3 如果有限集合A有n個(gè)元素，則其冪集P (A)有2n個(gè)元素。 16（3）編碼 引入一種編碼，用來唯一地表示有限冪集的元素。 例如：Sa,b,c P (S)=Si|iJ其中：J=i|i是二進(jìn)制數(shù)且000i111則：S011=S3=b,c,S110=S6=a,b。一般地P (S)=S0,S1,S2n-1即：P (S)=Si|iJ其中：1731習(xí)題作業(yè)P86（6）c）；（7）；（10）32 集合的運(yùn)算18191、集合的交（1）概念定義3

7、-2.1 設(shè)任意兩個(gè)集合A和B，由集合A和B的所有共同元素組成的集合S，稱為A和B的交集。記作：ABS=AB=x|(xA)(xB)交集的定義如圖3-2.1（文氏圖）所示。20例1 A=0,2,4,6,8,10,12;B=1,2,3,4,5,6AB=2,4,6例2 設(shè)A是所有矩形的集合，B是平面上所有菱形的集合，AB是正方形的集合。21例題1 設(shè)AB，求證ACBC22（2）性質(zhì)AA=AA=AE=AAB=BA(AB)C=A(BC)ABA，ABB23(AB)C=A(BC)24（3）不相交若集合AB=，則A與B不相交。（4）表示n個(gè)集合A1,A2,An的交可記為：例如：A1=1,2,8,A2=2,8,

8、A3=4,8。則：252、集合的并（1）概念定義3-2.2 設(shè)任意兩個(gè)集合A和B，所有屬于A或?qū)儆贐的元素組成的集合S，稱為A和B的并集。記作：AB=x|(xA)(xB)并集的定義如圖3-2.2所示。例如：設(shè)A=1,2,3,4,B=2,4,5。則：AB=1,2,3,4,526（2）性質(zhì)AA=AAE=EA=AAB=BA(AB)C=A(BC)AAB,BAB27例題2 設(shè)AB,CD,則ACBD28（3）表示對(duì)于n個(gè)集合A1,A2,An的交可記為：例如：設(shè)A1=1,2,3,A2=3,8,A3=2,6則：293、交并的性質(zhì) （1）分配律定理3-2.1 設(shè)A、B、C為三個(gè)集合，則下列分配律成立。a)A(B

9、C)=(AB)(AC)A(BC)=(AB)(AC)30（2）吸收律定理3-2.2 設(shè)A、B為任意兩個(gè)集合，則下列關(guān)系成立。a)A(AB)=AA(AB)=A31（3）AB時(shí)，A和B的交并關(guān)系定理3-2.3 AB，當(dāng)且僅當(dāng)AB=B或AB=A324、集合的補(bǔ)（1）概念1)相對(duì)補(bǔ)定義3-2.3 設(shè)A和B為任意兩個(gè)集合，所有屬于A而不屬于B的一切元素S稱為B對(duì)于A的補(bǔ)集，或相對(duì)補(bǔ)。記作：A-BS=x|xAxB=x|xA(xB)定義如圖3-2.3。例題3 設(shè)A=2,5,6,B=1,2,4,7,9,求AB。解：AB=5,6332）絕對(duì)補(bǔ)定義3-2.4 設(shè)E為全集，對(duì)任一集合A關(guān)于E的補(bǔ)集EA，稱為集合A的絕

10、對(duì)補(bǔ)。記作： AA=E-A=x|xExAA的定義如同3-2.4所示。34（2）性質(zhì)a)(A)=Ab)E=c)=Ed)AA=Ee)AA=355、“、”關(guān)系 定理3-2.4 設(shè)A、B為任意兩個(gè)集合，則下列關(guān)系成立。a)(AB)=ABb)(AB)=AB36（2）相對(duì)補(bǔ)的性質(zhì)定理3-2.5 設(shè)A、B為任意兩個(gè)集合，則下列關(guān)系式成立。a)AB=ABb)AB=A(AB)37（3）交對(duì)相對(duì)補(bǔ)的分配 定理3-2.6 設(shè)A、B、C為三個(gè)集合，則A(BC)=(AB)(AC)38（4）子集與集合補(bǔ)的關(guān)系定理3-2.7 設(shè)A、B為兩個(gè)集合，若AB，則a)BAb)(BA)AB395、集合的對(duì)稱差定義3-2.5 設(shè)A、B

11、為任意兩個(gè)集合，A和B的對(duì)稱差為集合S，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。記作：ABS= AB=(AB)(BA)=對(duì)稱差的定義如圖3-2.5所示。 40（2）性質(zhì)a)AB=BA(交換律)b)A=Ac)AA=d)AB=(AB)(AB)e)(AB)C=A (BC)41(AB)C=A (BC)42從圖3-2.7的文氏圖可得出下列關(guān)系。AB=(AB)(BA)(AB)AB=(AB)(AB)4332 習(xí)題 P95（5）c；（9）34 序偶與笛卡爾積44451、序偶 例如：34張華高于李明。中國(guó)處于亞洲。46（1）概念 一般地說，兩個(gè)具有固定次序的客體組成一個(gè)序偶，它常常表示兩個(gè)客體之間的關(guān)

12、系。例如：;注意：序偶可看作具有兩個(gè)元素的集合。但與集合不同的是元素在序偶中有確定的次序。例如：在集合中：a,b=b,a 在序偶中：=47（2）相等定義3-4.1 兩個(gè)序偶相等，=,iff x=u,y=v。注意：序偶中的兩個(gè)元素可以屬于不同的集合，可代表不同類型的事物。在序偶中，a稱第一元素，b稱第二元素。48（3）推廣 三元組是一個(gè)序偶，其第一元素也是一個(gè)序偶。形如：,z,z=,w,iff=,z=w即：x=u,y=v,z=w。約定：三元組,z記作注意： 當(dāng)xy時(shí)， ,zx,其中：x,不是三元組。同理：四元組第一元素是三元組 四元組：,w 四元組相等：,w=,s (x=p)(y=q)(z=r)

13、(w=s)49推廣到n元組： n元組可寫成,xn,xn=,yn(x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn) 一般地，n元組可簡(jiǎn)寫為，第i個(gè)元素xi稱作n元組的第i個(gè)坐標(biāo)。502、笛卡爾乘積（1）概念定義3-4.2 令A(yù)和B是任意兩個(gè)集合，若序偶的第一個(gè)成員是A的元素，第二個(gè)成員是B的元素，所有這樣的序偶集合，稱為集合A和B的笛卡爾乘積或直積。 記作：AB AB=|(xA)(yB)51注意：約定若A=或B，則AB。(AB)CA(BC)(AB)C=,c| (AB)(cC) = | (aA)(bB)(cC)A(BC)=a,| (aA)( BC)52（2）性質(zhì) 1）笛卡爾乘積與和的

14、關(guān)系定理3-4.1 設(shè)A，B，C為任意三個(gè)集合，則有：a)A(BC)=(AB)(AC)b)A(BC)= (AB)(AC)c)(AB)C=(AC)(BC)d)(AB)C=(AC)(BC)53a)A(BC)=(AB)(AC)54c)(AB)C=(AC)(BC)552）笛卡爾乘積與子集之間的關(guān)系一、左右兩邊同時(shí)直積上相同的集合定理3-4.2 若C，則AB(ACBC)(CACB)56二、左右兩邊直積上不同的集合定理3-4.3 設(shè)A、B、C、D為四個(gè)非空集合，則ABCD的充要條件為AC，BD。57（3）推廣約定：A1A2A3=(A1A2)A3A1A2A3A4=(A1A2A3)A4 一般地，A1A2An=

15、( A1A2An-1)An=| (x1A1)(x2A2)(xnAn)故A1A2An是有關(guān)n元組構(gòu)成的集合。注意：AA=A2 AAA=A3 583-4習(xí)題作業(yè)：P105（3）d），e）35 關(guān)系及其表示59601、引論例如：電影票與座位之間的對(duì)號(hào)關(guān)系。設(shè)：X：電影票集合。 Y：座位集合。則(x)xX(y)yY必有關(guān)系：（1）x與y有“對(duì)號(hào)”關(guān)系；或（2）x與y沒有“對(duì)號(hào)”關(guān)系。令R：“對(duì)號(hào)”關(guān)系則：（1）xRy或R（2）xRy或R因此，可得到“對(duì)號(hào)”關(guān)系R是序偶的集合。612、概念 （1）關(guān)系定義3-5.1 任一序偶的集合確定了二元關(guān)系R，R中任一序偶可記作R或xRy。不在R中的任一序偶可記作R

16、或xRy。例如：在實(shí)數(shù)中的關(guān)系可記作：=|x,y是實(shí)數(shù)且xy。62（2）域定義3-5.2 令R為二元關(guān)系，由R的所有x組成的集合domR稱為R的前域，即dom R=x|(y)(R)使R的所有y組成的集合ran R稱為R的值域，即ran R =y| (x)(R)R的前域和值域一起稱作R的域；記作:FLD R即：FLD R=dom Rran R63例題1 設(shè)A=1,2,3,5,B=1,2,4H=,求：dom H, ran H, FLD H。解：dom H=1,2,3ran H=2,4FLD H=1,2,3,4643、直積與關(guān)系（1）概念定義3-5.3 令X和Y是任意兩個(gè)集合，直積XY的子集R稱作X

17、到Y(jié)的關(guān)系。如圖3.5.1所示。dom RX,ran RY，由例題1表明：HAB，dom HA,ran HB,FLD H=dom H ranHAB。 65（2）特殊關(guān)系1）全域關(guān)系和空關(guān)系把XY的兩個(gè)平凡子集XY和，分別稱為X到Y(jié)的全域關(guān)系和空關(guān)系。2）二元關(guān)系當(dāng)X=Y時(shí)，關(guān)系R是XY的子集，這時(shí)稱R為在X上的二元關(guān)系。664、恒等關(guān)系定義3-5.4 設(shè)IX是X上的二元關(guān)系且滿足IX=|xX，則稱為Ix上是恒等關(guān)系。例如：A=1,2,3，則 IA=,。675、關(guān)系的運(yùn)算例題4 設(shè)X=1,2,3,4，若H=|(x-y)/2是整數(shù)， S=|(x-y)/3是正整數(shù)，求HS,HS,H,SH。68定理3

18、-5.1 若Z和S是從集合X到集合Y的兩個(gè)關(guān)系，則Z、S的并、交、補(bǔ)、差仍是X到Y(jié)的關(guān)系。696、二元關(guān)系表示（1）關(guān)系矩陣 設(shè)給定兩個(gè)有限集合X=x1,x2,xm,Y=y1,y2,yn，R為從X到Y(jié)的一個(gè)二元關(guān)系。則對(duì)應(yīng)關(guān)系R有一個(gè)關(guān)系矩陣MR=rijmn，其中：(i=1,2,m; j=1,2,n)70注意：1）根據(jù)X集合中的元素的個(gè)數(shù)確定行數(shù)；根據(jù)Y集合中元素的個(gè)數(shù)確定列數(shù)。2）行和列對(duì)應(yīng)的位置與X和Y集合中元素出現(xiàn)的次序是一一對(duì)應(yīng)的。即：第i行對(duì)應(yīng)X集合中第i個(gè)元素，第j列對(duì)應(yīng)Y集合中第j個(gè)元素。3）根據(jù)序偶是否屬于R，確定關(guān)系矩陣中行和列對(duì)應(yīng)元素的值（1或0）。71例題5 設(shè)X=x1,

19、x2,x3,x4,Y=y1,y2,y3，R=,，寫出關(guān)系矩陣MR72例題6 設(shè)A=1,2,3,4，寫出集合A上大于關(guān)系的關(guān)系矩陣。73（2）關(guān)系圖 設(shè)集合X=x1,x2,xm到Y(jié)=y1,y2,yn上的一個(gè)二元關(guān)系R， 關(guān)系圖的繪制步驟：（1）在平面上作出m個(gè)結(jié)點(diǎn)分別記作x1,x2,xm；（2）另作n個(gè)結(jié)點(diǎn)記作y1,y2,yn；（注：根據(jù)Y集合）（3）若xiRyi，則可自結(jié)點(diǎn)xi至結(jié)點(diǎn)yi處作一有向弧，其箭頭指向yi；（4）若xiRyi，則xi與yi間沒有線段聯(lián)結(jié)。用以上步驟所繪制的圖稱為R的關(guān)系圖。74例題7 畫出例題5的關(guān)系圖。例題5 設(shè)X=x1,x2,x3,x4,Y=y1,y2,y3，R=

20、,75例題8 設(shè)A=1,2,3,4,5，在A上的二元關(guān)系R給定為：R=, , ,畫出R的關(guān)系圖。76說明： 通常討論是同一集合上的關(guān)系。 從X到Y(jié)的關(guān)系R有： RXY 且XY(XY)(XY)所以有R(XY)(XY)令Z= XY，則RZZ。773-5習(xí)題作業(yè)：P110（4）（5）b36 關(guān)系的性質(zhì)78791、自反定義3-6.1 設(shè)R為定義在集合X上的二元關(guān)系，如果對(duì)于每個(gè)xX，有xRx，則稱二元關(guān)系R是自反的。R在X上自反(x)(xXxRx)例如，在實(shí)數(shù)集合R中，“”是自反的。802、對(duì)稱定義3-6.2 設(shè)R為定義在集合X上的二元關(guān)系，如果對(duì)于每個(gè)x,yX，每當(dāng)xRy，就有yRx，則稱集合X上關(guān)

21、系R是對(duì)稱的。R在X上對(duì)稱(x)(y)(xXyXxRy)yRx)例如：平面上三角形集合中相似關(guān)系是對(duì)稱的。 在同一街道居住的鄰居關(guān)系是對(duì)稱的。81例題1 設(shè)A=2,3,5,7,R=| (x-y)/2是整數(shù)，驗(yàn)證R在A上是自反的和對(duì)稱的。823、傳遞定義3-6.3 設(shè)R為定義在集合X上的二元關(guān)系，如果對(duì)于任意x,y,zX，每當(dāng)xRy,yRz時(shí)就有xRz，稱關(guān)系R在X上是傳遞的。R在X上傳遞(x)(y)(z)(xXyXzXxRyyRz)xRz)例如： 在實(shí)數(shù)集合中關(guān)系、和，都是傳遞的。 設(shè)A是人的集合，在A上的二元關(guān)系： 祖先關(guān)系R也是傳遞的。83例題2 設(shè)X=1,2,3,R1=,R2=,R3=,

22、，R1,R2和R3都是傳遞的嗎？解：根據(jù)傳遞性的定義， R1是傳遞的； R2是傳遞的；而R3不是傳遞的。R3R3，而R3；R3R3，而R3；故：R3不是傳遞的。844、反自反定義3-6.4 設(shè)R為定義在集合X上的二元關(guān)系，如果對(duì)于每一個(gè)xX，都有R，則R稱作反自反的。R在X上反自反(x)(xXR)例如：數(shù)的大于關(guān)系或小于關(guān)系和日常生活中父子關(guān)系。注意：一個(gè)不是自反的關(guān)系，不一定就是反自反的。855、反對(duì)稱定義3-6.5 設(shè)R為定義在集合X上的二元關(guān)系，對(duì)于每一個(gè)x,yX，每當(dāng)xRy和yRx必有x=y，則稱R在X上是反對(duì)稱的。R在X上反對(duì)稱(x)(y)(xXyYxRyyRx)x=y)例如：在實(shí)數(shù)

23、集合中是反對(duì)稱的，集合的是反對(duì)稱的。(xRy)(yRx)(x=y) (x=y)(xRy)(yRx)(x=y)(xRy)(yRx)(x=y)(xRy)(yRx)(xy)(xRy) (yRx)(xy)(xRy)(yRx)因此關(guān)系R的反對(duì)稱的定義亦為：(x)(y)(xXxX(xy)(xRy)(yRx)注意：有些關(guān)系既是對(duì)稱的，又是反對(duì)稱的。例如：A=1,2，S=,86例題4 設(shè)某人有三個(gè)兒子，組成集合A=T,G,H，在A上的兄弟關(guān)系具有哪些性質(zhì)。87例題5 集合I=1,2,3,4，I上的關(guān)系R=,討論R的性質(zhì)。88如何通過矩陣和關(guān)系圖判斷關(guān)系R是否具是自反或?qū)ΨQ的？（1）若關(guān)系R是自反的，當(dāng)且僅當(dāng)在

24、關(guān)系矩陣中，對(duì)角線上的所有元素都是1，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自回路。（2）若關(guān)系R是對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣是對(duì)稱的，且在關(guān)系圖上，任兩個(gè)結(jié)點(diǎn)間若有定向弧線，必是成對(duì)出現(xiàn)的。（3）若關(guān)系R是反自反的，當(dāng)且僅當(dāng)關(guān)系矩陣對(duì)角線的皆為零，關(guān)系圖上每個(gè)結(jié)點(diǎn)都沒有回路。（4）若關(guān)系R是反對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以主對(duì)角線對(duì)稱的元素不能同時(shí)為1，在關(guān)系圖上兩個(gè)不同結(jié)點(diǎn)間的定向弧線不可能成對(duì)出現(xiàn)。注意：傳遞的特征較復(fù)雜，不易從關(guān)系矩陣和關(guān)系圖中直接判斷。8936習(xí)題作業(yè)P113（2）；（4）37 復(fù)合關(guān)系和逆關(guān)系90911、合成關(guān)系（1）概念定義3-7.1 設(shè)R為X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，則RS稱

25、為R和S的復(fù)合關(guān)系，表示為RS=|xXzZ(y)(yYRS)從R和S，求RS稱為關(guān)系的合成運(yùn)算。例如：R1是關(guān)系“是的父親”， R2是關(guān)系“是的父親”， R1R2稱為關(guān)系“是的祖父”。92（2）性質(zhì)1）結(jié)合律 設(shè)R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，P是從Z到W的關(guān)系，則X到W上的關(guān)系(RS)P和R(SP)有：(RS)P=R(SP)93例題1 令R=,和S=,求：RS,SR,R(SR),(RS)R,RR,SS,RRR94說明： 由于關(guān)系合成滿足結(jié)合律，因此在同一關(guān)系上m次的合成運(yùn)算，可寫成：分別記作：95（3）表示 已知從集合X=x1,x2,xm到集合Y=y1,y2,yn有關(guān)系R，則MR=u

26、ijmn表示R關(guān)系矩陣 其中： (i=1,2,m; j=1,2,n) 同理從集合Y=y1,y2,yn到集合Z=z1,z2,zp的關(guān)系S，可用Ms=vjknp表示S關(guān)系矩陣， 其中：(j=1,2,n; k=1,2,p) 復(fù)合關(guān)系RS的矩陣MRS可構(gòu)造如下： MRS=MRMS=wikmp其中： 式中表示邏輯加，滿足：00=0,01=1,10=1,11=1 表示邏輯乘，滿足：00=1,01=0,10=0,11=1962、逆關(guān)系（1）概念定義3-7.2 設(shè)R為X到Y(jié)的二元關(guān)系，如將R中每一序偶的元素順序互換，所得到的集合稱為R的逆關(guān)系。記作：Rc，即：Rc=|R例如：集合X=1,2,3,4到Y(jié)=a,b

27、,c上的關(guān)系R=,則Rc=,97（2）性質(zhì)1）R的兩次逆(Rc)c=R因?yàn)椋篟Rc(Rc)c982）逆與集合運(yùn)算及直積的關(guān)系定理3-7.1 設(shè)R，R1和R2都是從A到B的二元關(guān)系，則下列各式成立。a)(R1R2)c=R1cR2cb)(R1R2)c=R1cR2cc)(AB)c=BA d)(R)c=Rce)(R1R2)c= R1cR2cd) 993）復(fù)合關(guān)系與逆關(guān)系 定理3-7.2 設(shè)T為從X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，證明(TS)c=ScTc1004）關(guān)系性質(zhì)與逆關(guān)系定理 3-7.3 設(shè)R為X上的二元關(guān)系，則a）R是對(duì)稱的，當(dāng)且僅當(dāng)R=Rcb）R是反對(duì)稱的，當(dāng)且僅當(dāng)R RcIx101注意：

28、關(guān)系Rc的圖形，是關(guān)系R圖形中將其弧的箭頭方向反置。關(guān)系Rc的矩陣是MR的轉(zhuǎn)置矩陣。10287習(xí)題作業(yè)P119（2）a）；（8）38 關(guān)系的閉包運(yùn)算1031041、關(guān)系閉包（1）概念定義3-8.1 設(shè)R是X上的二元關(guān)系，如果有另一個(gè)關(guān)系R滿足：a）R是自反的（對(duì)稱的，可傳遞的）；b）RR；c）對(duì)于任何自反的（對(duì)稱的，可傳遞的）關(guān)系R”，如果有R” R，就有R” R。 則稱R為R的自反（對(duì)稱，傳遞）閉包。記作：r(R),(S(R),t(R)105注意：對(duì)于X上的二元關(guān)系，可以通過擴(kuò)充序偶的方法來形成包含R的自反（對(duì)稱、傳遞）關(guān)系；但R的自反（對(duì)稱、傳遞）閉包必須是包含R的最小的自反（對(duì)稱、傳遞）

29、關(guān)系。106（2）閉包與關(guān)系性質(zhì)定理3-8.1 設(shè)R是X上二元關(guān)系，那么a）R是自反的，當(dāng)且僅當(dāng)r(R)=Rb）R是對(duì)稱的，當(dāng)且僅當(dāng)s(R)=Rc）R是傳遞的，當(dāng)且僅當(dāng)t(R)=R1072、求解關(guān)系閉包的方法（1）求自反閉包定理3-8.2 設(shè)R是集合X上的二元關(guān)系，則r(R)=RIx108（2）求對(duì)稱閉包定理3-8.3 設(shè)R是集合X上的二元關(guān)系，則s(R)=RRc109（3）求傳遞閉包定理3-3.4 設(shè)R是X上的二元關(guān)系，則注意：復(fù)合運(yùn)算的縮寫形式Rn或R(n)與同一集合的直積An110例題1 設(shè)A=a,b,c，R是A上的二元關(guān)系，且給定R=,，求r(R),S(R),t(R)。1113、t(R

30、)與X的關(guān)系定理3-8.5 設(shè)X是含有n個(gè)元素的集合，R是X上的二元關(guān)系，則存在一個(gè)正整數(shù)kn，使得： 由此n個(gè)元素的有限集合上關(guān)系R的傳遞閉包可寫為： 1124、Warshall的R的有效算法 （1）置新矩陣A:=M（2）置i:=1（3）對(duì)所有j如果Aj, i=1，則對(duì)k=1,2,nAj,k:=Aj,k+Ai,k;（4）i:=i+1（5）如果in，則轉(zhuǎn)到步驟(3)，否則停止。說明：逐個(gè)考察每一列i中為1的元素Aji然后將第j行和第i行實(shí)施邏輯加，產(chǎn)生第j行 1135、閉包的復(fù)合運(yùn)算定理3-8.6 設(shè)X是集合，R是X上的二元關(guān)系，則a)rs(R)=sr(R)b)rt(R)=tr(R)c)ts(

31、R)st(R)114注意：Ix的自身合成關(guān)系和逆關(guān)系是其本身。Ix與其它關(guān)系R的合成是R本身。關(guān)系的運(yùn)算（包含特殊運(yùn)算）都是X上的二元關(guān)系。1151-8習(xí)題作業(yè)P127（1）；（2）a）b)；(5);（7）c39 集合的劃分和覆蓋 1161171、覆蓋與劃分 （1）概念定義3-9.1 若把一個(gè)集合A分成若干個(gè)叫做分塊的非空子集，使得A中每個(gè)元素至少屬于一個(gè)分塊，那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)覆蓋。如果A中每一個(gè)元素屬于且僅屬于一個(gè)分塊，那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)劃分(或分劃)。 118等價(jià)定義定義3-9.1 令A(yù)為給定非空集合， 其中 集合S稱作集合A的覆蓋。 如果除以

32、上條件外，另有 則稱S是A的劃分（或分劃）。 119例如：A=a,b,c，考慮下列子集：S=a,b,b,c,Q=a,a,b,a,cD=a,b,c,G=a,b,cE=a,b,c,F=a,a,cS,Q,D,G,E是覆蓋，而F不是覆蓋；D,G,E是劃分。小結(jié)：1）若是劃分則必是覆蓋，其逆不真。2）任一個(gè)集合的最小劃分，就是由這個(gè)集合全部元素組成的一個(gè)分塊集合。如：G就是最小劃分。即：S中包含分塊最少的。3）任一個(gè)集合的最大劃分是由每個(gè)元素構(gòu)成一個(gè)單元素分塊的集合。如：E就是最大劃分。4）給定集合A的劃分并不是唯一的，但已知一個(gè)集合很容易構(gòu)造出一種劃分。1202、交叉劃分（1）概念定義3-9.2 若A

33、1,A2,Ar與B1,B2,Bs是同一集合A的兩種劃分，則其中所有AiBj組成的集合，稱為是原來兩種劃分的交叉劃分。 121例如：所有生物的集合X，可化割成P,A，其中P：所有植物的集合，A：所有動(dòng)物的集合；另外，X可化為E,F其中E：史前生物，F(xiàn)：史后生物。則，交叉劃分為：Q=PE,PF,AE,AF其中：PE：史前生物。PF：史后生物。AE：史前動(dòng)物。AF：史后動(dòng)物。122（2）性質(zhì) 定理3-9.1 設(shè)A1,A2,Ar與B1,B2,Bs 是同一集合X的兩種劃分，則其交叉亦是原集合的一種劃分。 1233、加細(xì)劃分 （1）概念定義3-9.3 給定X的任意兩個(gè)劃分A1,A2,Ar和B1,B2,Bs

34、，若對(duì)于每一個(gè)Aj均有Bk使AjBk，則A1,A2,Ar稱為是B1,B2,Bs的加細(xì)。 （2）性質(zhì)定理3-9.2 任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。 1243-9習(xí)題作業(yè)P130(5)310 等價(jià)關(guān)系與等價(jià)類 1251261、等價(jià)關(guān)系定義3-10.1 設(shè)R為定義在集合A上的一個(gè)關(guān)系，若R是自反的，對(duì)稱的和傳遞的，則R稱為等價(jià)關(guān)系。例如：平面三角形集合中，三角形的相似關(guān)系是等價(jià)關(guān)系。1272、等價(jià)類 定義3-10.2 設(shè)R為集合A上的等價(jià)關(guān)系，對(duì)任何aA,集合aR=x|xA,aRx稱為元素a形成的R的等價(jià)類。注意：aR是非空的。128如：例1 集合T=1,2,3,4上的等價(jià)類R=

35、,。1R=1,4=4R2R=2,3=3R1293、性質(zhì)定理3-10.1 設(shè)給定集合A上的等價(jià)關(guān)系R，對(duì)于a,bA，有aRb iff aR=bR。1304、商集 定義3-10.3 集合A上的等價(jià)關(guān)系R，其等價(jià)類集合aR|aA稱作A關(guān)于R的商集，記作A/R。如：例題1商集T/R=1R,2R例題3商集I/R=0R,1R,2R 1315、劃分、等價(jià)關(guān)系與商集之間的關(guān)系（1）商集與劃分定理3-10.2 集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃分，該劃分就是商集A/R。132（2）劃分與等價(jià)關(guān)系定理3-10.3 集合A的一個(gè)劃分確定A的元素間的一個(gè)等價(jià)關(guān)系。133例題4 設(shè)A=a,b,c,d,e,有一個(gè)劃分

36、S=a,b,c,d,e，試由劃分S確定S確定A上的一個(gè)等價(jià)關(guān)系。134（3）等價(jià)關(guān)系與商集 定理3-10.4 設(shè)R1和R2為非空集合A上的等價(jià)關(guān)系，則R1=R2，當(dāng)且僅當(dāng)A/R1=A/R2 1353-10作業(yè)P134135(3);(4);(5);(9)311 相容關(guān)系1361371、相容關(guān)系 定義3-11.1 給定集合A上的關(guān)系r，若r是自反的，對(duì)稱的則稱r是相容關(guān)系。 1382、相容類定義3-11.2 設(shè)r是集合A上的相容關(guān)系，若CA，如果對(duì)于C中任意兩個(gè)元素a1,a2有a1ra2，稱C是由相容關(guān)系r產(chǎn)生的相容類。 產(chǎn)生相容類:x1,x2,x1,x3,x2,x3,x6,x1,x2,x3,x2

37、,x3,x4,x2,x4,x5注意： 前三個(gè)相容類可加入新的元素組成新的相容類，而后四個(gè)不加入新的元素形成新的相容類，稱它們?yōu)樽畲笙嗳蓊悺?393、最大相容類（1）概念定義3-11.3 設(shè)r是集合A上的相容關(guān)系，不能真包含在任何其它相容類中的相容類，稱作最大相容類。記作Cr。 140（2）判斷方法I若Cr為最大相容類，顯然它是A的子集，且有：1）對(duì)于任意xCr，x必與Cr中所有元素有相容關(guān)系。2）在A-Cr中沒有任何元素與Cr所有元素有相容關(guān)系。II在相容關(guān)系圖中：1）最大完全多邊形的頂點(diǎn)集合。完全多邊形：多邊形結(jié)點(diǎn)中，每一個(gè)結(jié)點(diǎn)都與其它結(jié)點(diǎn)有連線。最大完全多邊形：不能在加入其它結(jié)點(diǎn)使其稱為完

38、全多邊形。2）孤立結(jié)點(diǎn)。滿足上述條件的結(jié)點(diǎn)組成的集合都是最大相容類。 1414、性質(zhì)定理3-11.1 設(shè)r是有限集A上的相容關(guān)系，C是一個(gè)相容類，那么必存在一個(gè)最大相容類Cr，使得CCr。證明：采用構(gòu)造法證明。注意：1)A中的任意元素a，必屬于一個(gè)最大相容類Cr中； 2) 所有最大相容類組成的集合必覆蓋集合A。 1425、完全覆蓋（1）概念定義3-11.4 在集合A上給定相容關(guān)系r，其最大相容類的集合稱作集合A的完全覆蓋，記作Cr(A)。注意：集合A的覆蓋不唯一；不同的相容類集合可構(gòu)成A的覆蓋，但給定相容關(guān)系r，只能唯一對(duì)應(yīng)一個(gè)完全覆蓋。例題1中，給定A上相容關(guān)系則有唯一的完全覆蓋：a1,a2

39、,a4,a6,a3,a4,a6,a4,a5,a7143（2）性質(zhì)1)覆蓋與相容關(guān)系定理3-11.2給定集合A的覆蓋A1,A2,An，由它確定的關(guān)系是相容關(guān)系。證明：根據(jù)覆蓋的定義和相容關(guān)系的定義(自反的,對(duì)稱的)注意：給定集合A上的任意一個(gè)覆蓋，必可在A上構(gòu)造對(duì)應(yīng)于此覆蓋的一個(gè)相容關(guān)系；集合A上不同的覆蓋卻能構(gòu)造相同的相容關(guān)系。144例如：設(shè)A=1,2,3,4,集合1,2,3,3,4和1,2,2,3,1,3,3,4都是A的覆蓋，但它們可以產(chǎn)生相同的相容關(guān)系。r=,1452)完全覆蓋與相容關(guān)系定理3-11.3 集合A上的相容關(guān)系r與完全覆蓋Cr(A)存在一一對(duì)應(yīng)。自證。1463-11習(xí)題作業(yè)P1

40、39(2),(3)312 序關(guān)系 1471481、偏序關(guān)系 定義3-12.1 設(shè)A是一個(gè)集合，如果A上的一個(gè)關(guān)系R，滿足自反性，反對(duì)稱性和傳遞性，則稱R是A上的一個(gè)偏序關(guān)系，并記作“”。序偶稱作偏序集。 149例題1 在實(shí)數(shù)集R中， 證明小于等于關(guān)系“”是偏序關(guān)系。1502、蓋?。?）概念定義3-12.2 在偏序集合中，如果x,yA,xy,xy且沒有其它元素z滿足xz,zy，則稱元素y蓋住x。并且記作COV A=|x,yA;y蓋住x。注意：xy類似xRy，即：偏序關(guān)系。zxy（z是其它的不同x，y） 151（2）表示對(duì)于給定偏序集，其蓋住關(guān)系是唯一的，可用蓋住的性質(zhì)畫出偏序集合圖，或稱哈斯圖，

41、其作圖規(guī)則為：1)用小圓圈代表元素。2)如果xy且xy，則將代表y的小圓圈畫在代表x的小圓圈之上。3)如果COV A，則在x與y之間用直線連接。注意：層次性1523、鏈與反鏈定義3-12.3 設(shè)是一個(gè)偏序集合，在A的一個(gè)子集中，如果每?jī)蓚€(gè)元素都是有關(guān)系的，則稱這個(gè)子集為鏈。在A的一個(gè)子集中，如果每?jī)蓚€(gè)元素都是無關(guān)的，則稱這個(gè)子集為反鏈。約定，如A的子集只有單個(gè)元素，則這個(gè)子集既是鏈又是反鏈。例如:A表示一個(gè)單位里所有工作人員的集合，表示領(lǐng)導(dǎo)關(guān)系，則為一偏序集，其中部分工作人員有領(lǐng)導(dǎo)關(guān)系的組成一個(gè)鏈。還有部分工作人員沒有領(lǐng)導(dǎo)關(guān)系的組成一個(gè)反鏈。 1534、全序關(guān)系 定義3-12.4 在偏序集中，

42、如果A是一個(gè)鏈，則稱為全序集合或稱線序集合，在這種情況下，二元關(guān)系稱為全序關(guān)系或線序關(guān)系。 全序集就是對(duì)任意x,yA，或者有xy或者有yx成立。例如，定義在自然數(shù)集合N上的“”是偏序關(guān)系，且對(duì)于任意i,jN，必有：(ij)(ji)成立，故“”是全序關(guān)系。1545、極大(極小)元與最大(最小)元（1）極大(極小)元定義3-12.5 設(shè)是一個(gè)偏序集合，且B是A的子集，對(duì)于B中的一個(gè)元素b，如果B中沒有元素x， 滿足bx且bx，則稱b為B的極大元。同理，對(duì)于bB，如果B中沒有任何元素x， 滿足bx且xb，則稱b為B的極小元。 155（2）最大(最小)元定義3-12.6 令是一個(gè)偏序集，且B是A的子集

43、，若有某個(gè)元素bB，對(duì)于B中每一個(gè)元素x有xb，則稱b為的最大元。同理，若有某個(gè)元素bB，對(duì)每一個(gè)xB有bx，則稱b為的最小元。156（3）性質(zhì)定理3-12.1 令為偏序集且BA，若B有最大元(最小元)，則必是唯一的。證明：反證法。 1576、上界(下界)與上確界(下確界)（1）上界(下界)定義3-12.7 設(shè)為一偏序集，對(duì)于BA，如有aA，且對(duì)B的任意元素x，都滿足xa，則稱a為子集B的上界。同樣地，對(duì)于B的任意元素x，都滿足ax，則稱a為B的下界。 158（2）上確界(下確界)定義3-12.8 設(shè)為偏序集且BA為一子集，a是B的任一上界，若對(duì)B的所有上界y均有ay，則稱a為B的最小上界(上

44、確界)，記作LUB B。同樣，若b為B的任一下界， 若對(duì)B的所有下界z，均有zb，則稱b為B的最大下界(下確界)，記作GLB B。 1597、良序（1）概念定義3-12.9 任一偏序集合，假如它的每一個(gè)非空子集存在最小元素，這種偏序集稱為良序的。例如：In=1,2,n及N=1,2,3,，對(duì)于小于等于關(guān)系是良序集合。即：,是良序集合。 160（2）性質(zhì)定理3-12.2 每一個(gè)良序集合，一定是全序集合。證明：根據(jù)良序集合的定義和最小元素的定義。定理312.3 每一個(gè)有限的全序集合，一定是良序集合.證明：采用反證法。注意：結(jié)論對(duì)于無限的全序集合不一定成立。例如：大于0小于1的全部實(shí)數(shù)，按大小關(guān)系是一

45、個(gè)全序集合，但不是良序集合。1613-12習(xí)題作業(yè)P145P145146(1);(2);(7)cd41 函數(shù)的概念 1621631、函數(shù)（1）概念定義4-1.1 設(shè)X和Y是任何兩個(gè)集合，而f是X到Y(jié)的一個(gè)關(guān)系，如果對(duì)于每一個(gè)xX，有唯一的yY，使得f，稱關(guān)系f為函數(shù)，記作：f: XY或假如f，則x稱為自變量，y稱為在f作用下x的象， f亦可記作y=f(x)，且記f(x)=f(x)|xX注意：函數(shù)與關(guān)系的區(qū)別：a.函數(shù)的定義域是X，而不是X的某個(gè)真子集。b.一個(gè)xX只能對(duì)應(yīng)于唯一的一個(gè)y。即如果f(x)=y且f(x)=z，那么，y=z。2)從X到Y(jié)的函數(shù)往往也叫做從X到Y(jié)的映射。 164（2）f

46、的前域和值域在f中，f的前域就是 函數(shù)y=f(x)的定義域記作dom f=X, f的值域ran fY,有時(shí)也記作Rf，即： Rf=y|(x)(xX)(y=f(x)集合Y稱為f的共域，ran f亦稱為函數(shù)的象集合。 165例1設(shè)X=1,5,p,張明,Y=2,q,7,9,Gf=,即f(1)=2,f(5)=q,f(p)=7,f(張明)=G，dom f=X, Rf=2,q,7,G例 3 判斷下列關(guān)系中哪個(gè)構(gòu)成函數(shù)。a. f=|x1,x2Nx1+x210b. f=|y1,y2Ry22=y1c. f=|x1,x2N,x2為小于x1的素?cái)?shù)個(gè)數(shù) 1662、函數(shù)相等定義4-1.2 設(shè)函數(shù)f: AB, g: CD

47、,如果A=C,B=D,且對(duì)于所有xA和xC有f(x)=g(x)，則稱函數(shù)f和g相等，記作f=g。注意：XY的子集并不能都成為X到Y(jié)的函數(shù)。例如：X=a,b,c,Y=0,1, XY=,f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,注意：1)設(shè)X和Y為有限集，|X|=m,|Y|=n，從X到Y(jié)共有nm個(gè)不同的函數(shù)。2)符號(hào)Yx表示從X到Y(jié)的所有函數(shù)的集合，當(dāng)X和Y是無限集，也用這個(gè)符號(hào)。 1673、函數(shù)的分類（1）滿射定義4-1.3 對(duì)于f:XY的映射中，如果ran f=Y， 即Y的每一個(gè)元素是X中一個(gè)或多個(gè)元素的象點(diǎn)，則稱這個(gè)映射為滿射（或到上映射）。 設(shè)f: XY是滿射，即對(duì)于任意的yY，必存在xX使得f(x)=y成立。例如：A=a,b,c,d,B=1,2,3