1、第三章 集合與關系 31 集合的概念和表示法1集合論起源：起源16世紀末，數(shù)學危機（理發(fā)師：只給那些不給自己理發(fā)的人理發(fā)，不給那些給自己理發(fā)的人理發(fā)）（理發(fā)師？屬于那一類？）定義集合的方法在邏輯上來說，有矛盾1876-1908，cantor奠定了集合論基礎(樸素集合論)20世紀初，zermole建立的公理化集合論，解決了悖論（公理化集合論）231、集合概念及表示 （1）集合概念一般地說，把具有相同性質(zhì)的一些東西，匯集成一個整體，就形成一個集合。例如：教室內(nèi)的桌子；全國的高等學校；自然數(shù)的全體；直線上的點。分類有限集：集合的元素個數(shù)是限的。無限集：集合的元素個數(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注意：集合的元素可以是一個集合。例如：S=a,1,2,p,q， qq，但qS。II 敘述法：利用一些規(guī)則，來決定某一事物是否屬于該集合。例如：S1=x|x是正奇數(shù)S2=x|x是中國的省S3=y|y=a或y=b。另外，用P(x)表示任何謂詞，則x|P(x)可表示集合。62、集合相等外延性原理：兩個集合是相等的，當且僅當它們有相同的成員。 兩個集合A和B相等，記作：

3、A=B， 兩個集合不相等，則記作AB。7例如：設A是小于10的素數(shù)集合，即A=2,3,5,7，設代數(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注意：集合沒有次序之分，集合中的元素可以重復。83、子集（1）概念定義3-1.1 設A、B是任意兩個集合，假設A是每一個元素是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）應用定理3-1.1 集合A和B相等的充分必要條件是這兩個集合互為子集。104、真子集 定義3-1.3 如果集合A的每一個元素都屬于B，但集合B中至少有一個元素不屬于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 對于任意一個集合A，A。注意：I 對于每一個非空集合A，至少有兩個不同的子集：A和，即：

5、AA和A。我們稱A和為平凡子集。II 一般來說，A的每一個元素都能確定A的一個子集，即若aA，則aA。136、全集定義3-1.4 在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集。記作：E。(x)(xE)恒真。Ex|P(x)P(x)，P(x)任何謂詞。注意：全集概念相當于論域 設全集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)。注意：對于一個元素個數(shù)為n的全集E，其可能的子集個數(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個元素，則其冪集P (A)有2n個元素。 16（3）編碼 引入一種編碼，用來唯一地表示有限冪集的元素。 例如：Sa,b,c P (S)=Si|iJ其中：J=i|i是二進制數(shù)且000i111則：S011=S3=b,c,S110=S6=a,b。一般地P (S)=S0,S1,S2n-1即：P (S)=Si|iJ其中：1731習題作業(yè)P86（6）c）；（7）；（10）32 集合的運算18191、集合的交（1）概念定義3

7、-2.1 設任意兩個集合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 設A是所有矩形的集合，B是平面上所有菱形的集合，AB是正方形的集合。21例題1 設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個集合A1,A2,An的交可記為：例如：A1=1,2,8,A2=2,8,

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

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

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

11、為任意兩個集合，A和B的對稱差為集合S，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。記作：ABS= AB=(AB)(BA)=對稱差的定義如圖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的文氏圖可得出下列關系。AB=(AB)(BA)(AB)AB=(AB)(AB)4332 習題 P95（5）c；（9）34 序偶與笛卡爾積44451、序偶 例如：34張華高于李明。中國處于亞洲。46（1）概念 一般地說，兩個具有固定次序的客體組成一個序偶，它常常表示兩個客體之間的關

12、系。例如：;注意：序偶可看作具有兩個元素的集合。但與集合不同的是元素在序偶中有確定的次序。例如：在集合中：a,b=b,a 在序偶中：=47（2）相等定義3-4.1 兩個序偶相等，=,iff x=u,y=v。注意：序偶中的兩個元素可以屬于不同的集合，可代表不同類型的事物。在序偶中，a稱第一元素，b稱第二元素。48（3）推廣 三元組是一個序偶，其第一元素也是一個序偶。形如：,z,z=,w,iff=,z=w即：x=u,y=v,z=w。約定：三元組,z記作注意： 當xy時， ,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元組可簡寫為，第i個元素xi稱作n元組的第i個坐標。502、笛卡爾乘積（1）概念定義3-4.2 令A和B是任意兩個集合，若序偶的第一個成員是A的元素，第二個成員是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、關系定理3-4.1 設A，B，C為任意三個集合，則有：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）笛卡爾乘積與子集之間的關系一、左右兩邊同時直積上相同的集合定理3-4.2 若C，則AB(ACBC)(CACB)56二、左右兩邊直積上不同的集合定理3-4.3 設A、B、C、D為四個非空集合，則ABCD的充要條件為AC，BD。57（3）推廣約定：A1A2A3=(A1A2)A3A1A2A3A4=(A1A2A3)A4 一般地，A1A2An=

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

16、或xRy。例如：在實數(shù)中的關系可記作：=|x,y是實數(shù)且xy。62（2）域定義3-5.2 令R為二元關系，由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 設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、直積與關系（1）概念定義3-5.3 令X和Y是任意兩個集合，直積XY的子集R稱作X

17、到Y的關系。如圖3.5.1所示。dom RX,ran RY，由例題1表明：HAB，dom HA,ran HB,FLD H=dom H ranHAB。 65（2）特殊關系1）全域關系和空關系把XY的兩個平凡子集XY和，分別稱為X到Y的全域關系和空關系。2）二元關系當X=Y時，關系R是XY的子集，這時稱R為在X上的二元關系。664、恒等關系定義3-5.4 設IX是X上的二元關系且滿足IX=|xX，則稱為Ix上是恒等關系。例如：A=1,2,3，則 IA=,。675、關系的運算例題4 設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的兩個關系，則Z、S的并、交、補、差仍是X到Y的關系。696、二元關系表示（1）關系矩陣 設給定兩個有限集合X=x1,x2,xm,Y=y1,y2,yn，R為從X到Y的一個二元關系。則對應關系R有一個關系矩陣MR=rijmn，其中：(i=1,2,m; j=1,2,n)70注意：1）根據(jù)X集合中的元素的個數(shù)確定行數(shù)；根據(jù)Y集合中元素的個數(shù)確定列數(shù)。2）行和列對應的位置與X和Y集合中元素出現(xiàn)的次序是一一對應的。即：第i行對應X集合中第i個元素，第j列對應Y集合中第j個元素。3）根據(jù)序偶是否屬于R，確定關系矩陣中行和列對應元素的值（1或0）。71例題5 設X=x1,

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

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

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

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

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

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

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

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

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

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

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

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

31、R)st(R)114注意：Ix的自身合成關系和逆關系是其本身。Ix與其它關系R的合成是R本身。關系的運算（包含特殊運算）都是X上的二元關系。1151-8習題作業(yè)P127（1）；（2）a）b)；(5);（7）c39 集合的劃分和覆蓋 1161171、覆蓋與劃分 （1）概念定義3-9.1 若把一個集合A分成若干個叫做分塊的非空子集，使得A中每個元素至少屬于一個分塊，那么這些分塊的全體構成的集合叫做A的一個覆蓋。如果A中每一個元素屬于且僅屬于一個分塊，那么這些分塊的全體構成的集合叫做A的一個劃分(或分劃)。 118等價定義定義3-9.1 令A為給定非空集合， 其中 集合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是劃分。小結：1）若是劃分則必是覆蓋，其逆不真。2）任一個集合的最小劃分，就是由這個集合全部元素組成的一個分塊集合。如：G就是最小劃分。即：S中包含分塊最少的。3）任一個集合的最大劃分是由每個元素構成一個單元素分塊的集合。如：E就是最大劃分。4）給定集合A的劃分并不是唯一的，但已知一個集合很容易構造出一種劃分。1202、交叉劃分（1）概念定義3-9.2 若A

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

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

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

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

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

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

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

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

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

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

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

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

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

46、的前域和值域在f中，f的前域就是 函數(shù)y=f(x)的定義域記作dom f=X, f的值域ran fY,有時也記作Rf，即： Rf=y|(x)(xX)(y=f(x)集合Y稱為f的共域，ran f亦稱為函數(shù)的象集合。 165例1設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 判斷下列關系中哪個構成函數(shù)。a. f=|x1,x2Nx1+x210b. f=|y1,y2Ry22=y1c. f=|x1,x2N,x2為小于x1的素數(shù)個數(shù) 1662、函數(shù)相等定義4-1.2 設函數(shù)f: AB, g: CD

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