CHAPTER2SETTHEORYGlossaryset:集合subset:子集object,element,member：成員，元素paradox:悖論well-defined:良定，完全確定brace：花括號(hào)representation：表示sensible:有意義的rationalnumber：有理數(shù)emptyset:空集orderedpair：有序?qū)?，序偶Cartesianproduct:叉積，笛卡爾積Venndiagram:文氏圖contain(in):包含(于)universalset:全集finite(infinite)set:有限(無(wú)限)集cardinality:基數(shù)，勢(shì)powerset:冪集setoperation：集合運(yùn)算disjointsets：不相交集intersection：交union：并complement:補(bǔ)集，補(bǔ)元symmetricdifferenee:對(duì)稱差Booleanalgebra:布爾代數(shù)binaryoperation：二元運(yùn)算unaryoperation：一元運(yùn)算identity:么元，單位元inverse:逆元commutative:可交換的associative:可結(jié)合的distributive:可分配的idempotent:等冪的absorption:吸收DeMorgan'slaws:德摩根律binaryoperation：二元運(yùn)算unaryoperation：—元運(yùn)算unity：么(單位)元zero:零元dual:對(duì)偶relation：關(guān)系domain:定義域range：值域inverserelation:逆關(guān)系composition：復(fù)合reflexive:自反的antireflexive:反自反的symmetric:對(duì)稱的antisymmetric:反對(duì)稱的transitive:傳遞的reflexiveclosure:自反閉包symmetricclosure:對(duì)稱閉包transitiveclosure:傳遞閉包graph：無(wú)向圖vertex(vertices):頂點(diǎn)edge:邊directedgraph(digraph):有向圖initialvertex:起點(diǎn)terminalvertex:終點(diǎn)partialordering：偏序partiallyorderedset(poset):偏序集comparable:可比的totalordering,chain,linearordering：全序，鏈，線序Hassediagram:哈斯圖equivaleneerelation：等價(jià)關(guān)系equivaleneeclass:等價(jià)類mutuallyexclusive：互斥disjoint:不相交partition:劃分，分割function:函數(shù)，映射codomain：陪域preimage:原像image:像mapping：映射compositefunction：復(fù)合函數(shù)onto,surjective:到上函數(shù)，滿射onetoone,injective:單射，一對(duì)一函數(shù)bijection,one-to-onecorrespondence：雙射， 對(duì)應(yīng)permutation：置換，排列identityfunction：?jiǎn)挝缓瘮?shù)invertiblefunction：可逆函數(shù)本章內(nèi)容及教學(xué)要點(diǎn)：2?1IntroductiontoSets教學(xué)內(nèi)容：elements，sets，representationsofsets，subsets，propersubset，emptyset，universalset，finitesets，infinitesets，cardinality2?2OperationsonSets教學(xué)內(nèi)容：operationsonsets:intersection、union、setdifference、symmetricdifference、complement，powerset，orderedpair，Cartesianproduct，algebraicpropertiesofsetoperations2?3VennDiagrams教學(xué)內(nèi)容：Venndiagrams2?4BooleanAlegebras教學(xué)內(nèi)容：Booleanalgebras，binaryoperations，unaryoperations，unity，zero，complement2?5Relations教學(xué)內(nèi)容：relation，inverserelation，composition，propertiesofrelation，closure，graph，directedgraph(digraph)2?6PartiallyOrderedSets教學(xué)內(nèi)容：partialordering，poset，totalordering，Hassediagram2?7EquivalenceRelations教學(xué)內(nèi)容：equivalencerelation，equivalenceclass，partition2?8Functions教學(xué)內(nèi)容：function，domain，range，onto，one-to-one，bijection，inverse，identityfunction定理證明及例題解答IntroductiontoSets20世紀(jì)數(shù)學(xué)中最為深刻的活動(dòng)就是關(guān)于數(shù)學(xué)基礎(chǔ)的探討，集合論因是為了研究數(shù)學(xué)基礎(chǔ)而發(fā)展起來(lái)的.集合論是現(xiàn)代數(shù)學(xué)的基礎(chǔ)，是數(shù)學(xué)中不可或缺的基本描述工具.可以這樣講，現(xiàn)代數(shù)學(xué)與離散數(shù)學(xué)的“大廈”建立在集合論的基礎(chǔ)之上.集合論的研究起源于對(duì)數(shù)學(xué)的基礎(chǔ)研究：對(duì)數(shù)學(xué)的對(duì)象、性質(zhì)及其發(fā)生、發(fā)展的一般規(guī)律進(jìn)行的科學(xué)研究.德國(guó)數(shù)學(xué)家康托爾從1874年始，發(fā)表了一系列集合論方面的著作，從而創(chuàng)立了集合論.在自然科學(xué)中，除了研究處于孤立的個(gè)體之外，更重要的是將一些相關(guān)的個(gè)體放在一起進(jìn)行研究，這就直觀地產(chǎn)生了引入集合這一概念的要求.集合是最簡(jiǎn)單的數(shù)學(xué)對(duì)象.隨著計(jì)算機(jī)時(shí)代的到來(lái)，集合的元素已由傳統(tǒng)的“數(shù)集”和“點(diǎn)集”拓展成包含文字、符號(hào)、圖形、圖表和聲音等多媒體信息，構(gòu)成了各種數(shù)據(jù)類型的集合.從而集合論在編譯原理、開關(guān)理論、信息檢索、形式語(yǔ)言、數(shù)據(jù)庫(kù)和知識(shí)庫(kù)、CAD、CAM、CAI及AI等各個(gè)領(lǐng)域得到了廣泛的應(yīng)用.但數(shù)學(xué)家們不久就在康托爾的理論（我們稱之為樸素（古典）集合論）中發(fā)現(xiàn)了邏輯矛盾，即所謂的“悖論"（paradox，導(dǎo)致了數(shù)學(xué)發(fā)展史上的第三次危機(jī).其中最為著名的就是1901年羅素發(fā)現(xiàn)的''羅素悖論〃S={x|xS}.“羅素悖論〃的通俗表示是所謂的“理發(fā)師悖論”：一個(gè)村莊的理發(fā)師，自夸本村無(wú)人可比，宣稱他當(dāng)然不給自己刮胡子的人刮胡子，但卻給本村所有自己刮胡子的人刮胡子.哪么他是否應(yīng)當(dāng)給自己刮胡子？正是尋求解決第三次數(shù)學(xué)危機(jī)的各種努力，給數(shù)學(xué)基礎(chǔ)問(wèn)題的研究帶來(lái)了全新的轉(zhuǎn)機(jī).一部分?jǐn)?shù)學(xué)家開始把精力集中于解決具有“能行性”的問(wèn)題上.20世紀(jì)30年代中后期，圖靈對(duì)計(jì)算的本質(zhì)進(jìn)行了研究，從而實(shí)現(xiàn)了對(duì)計(jì)算本質(zhì)的真正認(rèn)識(shí).圖靈提出了'圖靈機(jī)”這一計(jì)算模型用來(lái)解決“能行計(jì)算”問(wèn)題，而電子計(jì)算機(jī)正是這種模型的具體實(shí)現(xiàn).Asetisanywell-definedcollectionofobjectsorelements.Wedon'tspecifywhatanobjectisandthedescriptionofasetasacollectionofobjectsisbasedontheintuitivenotionofanobject.Well-definedjustmeansthatitispossibletodecideifagivenobjectbelongstothecollectionornot.Almostallmathematicalobjectsarefirstofallsets.Thussettheoryis,inasense,thefoundationonwhichvirtuallyallofmathematicsisconstructed.一個(gè)集合是作為整體識(shí)別的、確定的、互相區(qū)別的一些事物的全體.嚴(yán)格地講，這只是一種描述，不能算是集合的定義.類似于幾何中的點(diǎn)、線、面等概念，在樸素集合論中，集合也是一種不加定義而直接引入的最基本的原始概念(一給出定義就要引入悖論(paradoxes)).而集合論中的其他概念，則都是從它出發(fā)給予了嚴(yán)格的定義.構(gòu)成集合的每個(gè)事物稱為這個(gè)集合的元素或成員(member,element).集合一般用大寫字母表示，元素用小寫字母表示.但這也不是絕對(duì)的，因?yàn)橐粋€(gè)集合可以是另外一個(gè)集合的元素.例2?1?1英文字母的集合，C語(yǔ)言的基本字符集，全體實(shí)數(shù)，計(jì)算機(jī)內(nèi)存單元集合.例2?1?2 {1,2,3}={2,1,3}={3,1,2}.例2?1?3常用集合：N,Z(Z+,Z-),P,Q,R,C,①(emptyset,空集).集合的表示：枚舉法(listingtheelementsofthesetbetweenbraces):Theorderoftheelementsofasetisnotimportant.Repeatedelementsinthelistingoftheelementsofasetcanbeignored；性質(zhì)描述法(specifyingapropertythattheelementsofthesethaveincommon)：S={x:P(x)}；定義2.1.1IfaisoneoftheobjectsofthesetA,wesaythataisanelementofAorabelongstoA.WeindicatethefactthatxisanelementofthesetAbywritingxeA,andweindicatethefactthatxisnotanelementofthesetAbywriting A.(如果x是集合A的一個(gè)元素，則稱x屬于A,記作xeA;否則稱x不屬于A,記作x電A)例2?1?41eN,0.5eQ,3.0eR,—1纟N,、2電Q.集合有三個(gè)重要的特性：互異性、無(wú)序性和確定性.定義2?1?2(Inclusionrelation，包含關(guān)系)IfeveryelementofAisalsoanelementofB,wesaythatAisasubsetofBorthatAiscontainedinBandwewriteA匸B.(設(shè)A和B是兩個(gè)集合.若A中的每個(gè)元素都是B的元素，則稱A是B的子集或稱B包含A、A包含于B,記作AB.)定義2.1.3(外延性原理)WesaythatA=BifthesetsAandBhavethesameelements.若A匸B但A工B,則稱A為B的真子集(propersubset)記作AuB，B稱為A的擴(kuò)集或超集(superset).例2.1.5下列各集合中，哪幾個(gè)分別相等?A1={a,b}(2)A2={b,a}A3={a,b,a}(4)A4={a,b,c}A5={x|(x-a)(x-b)(x-c)=0}A6={x|x2-(a+b)x+ab=0}例2.1.6NuQuRuC.定義2.1.4Theemptyset,denotedby①orby{},isthesetthatcontainsnoelements.TheuniversalsetUisaspecialandvolatilesetwhichcontainsalltheobjectsunderconsideration(在一定討論范圍內(nèi)，若所有集合均為某一集合的子集，則稱該集合為全集(universalset)，記為U)全集有多種選擇.通常全集不需要具體指明，但是有些時(shí)候則需要明確指明全集.空集是任何集合的子集(對(duì)任一集合A，有①匸A).對(duì)任一非空集合A，它至少有兩個(gè)不同的子集①和A，稱它們?yōu)锳的平凡子集(①匸A，A匸A).集合的包含關(guān)系(inclusionrelation)有如下性質(zhì)：(1)自反性：AA；反對(duì)稱性：AoB,B匸A二A=B;(3)傳遞性：AB,B匸C二A匸C.而集合的真包含關(guān)系(properinclusionrelation)貝9只有傳遞性AuB，BuCnAuC.顯然A匸B且B匸A。A=B.例2?1?7A=｛x|x2-x=0且xGR｝,B=｛0,1｝,則A=B.例2.1.8判斷下列命題的真假：①匸①，①w①，①匸｛①｝， ①w｛①｝，｛①｝w｛｛①｝｝，｛①｝w｛①，｛①｝｝，①匸｛｛①｝｝，｛①｝匸｛｛①｝｝定義2.1.5AsetAiscalledfiniteifithasndistinctelements,wherenwN.niscalledthecardinalityofAandisdenotedby|A|(基數(shù)或勢(shì)).基數(shù)為有限的集合稱為有限集(finiteset),否則稱為無(wú)限集(infiniteset)；I①1=0.例2?1?9N,I,Q+，R,C都是無(wú)限集；大于3且小于1的整數(shù)集是空集，H=｛x|xwR且X2+x+1=0｝是空集；偶素?cái)?shù)集是有限非空集.丨①1=0，|｛0,1｝1=2，|｛①｝|=1，|N|=n0，|R|=ni-ASSIGNMENTS：PP38：2，4，6，8，10，16，20，26SetOperations定義2.2.1IfAandBaresets,wedefinetheirunion(intersection)asthesetconsistingofallelementsthatbelongtoAorB(bothAandB)anddenoteitbyAuB(AnB).WedefinethesetdifferenceA-BasthesetofallelementsthatareinAbutarenotinBanddenoteitbyA-B.ThecomplementofasetA,denotedbyA，,isthesetU-A.WedefinethesymmetricdifferenceofAandBasthesetofallelementsthatbelongtoAorB,butnottobothAandB,anddenoteitbyA人B(A十B).設(shè)有集合A與B,則稱由A與B的公共元素組成的集合為A與B的交集，記作AcB,即AnB={x:xGA且xGB};Twosetsthathavenocommonelementsarecalleddisjointsets(若AcB=①(即A與B無(wú)公共元素)，則稱A與B不相交);稱由A與B的所有元素組成的集合為A與B的并集，記作AuB,即AuB={x:xGA或xeB}；類似地，我們可以定義AuBuC, A2u…uAn,AcBnC,(3)稱由屬于A但不屬于B的元素組成的集合為A與B的差，記作A-B,即A-B={x:xeA且XgB}.特別地，稱U-B為B的補(bǔ)集，記作B'(或B、?B).稱由屬于A但不屬于B的元素或?qū)儆贐但不屬于A的元素組成的集合為A與B的環(huán)和或?qū)ΨQ差，記為AAB,即AAB={x:(xeA且x電B)或(xeB且x電A)}=(A-B)u(B-A).例2.2.1設(shè)A={2，3}，B={1，5，8}，C={3，6}，U={1，…，10}，求AuB,CcB,A-B,B-A,B'.例2?2?2設(shè)A={2,3},B={1,5,8},U={1,???,10},求AAB,BAA,AaA,Aa①,UaA.集合運(yùn)算的性質(zhì)(Algebraicpropertiesofsetoperations)定理2?2?1ForarbitrarysetsAandB,A-B=AnB，.證明定理2?2?1定理2.2.2(DeMorgan'slaw)ForarbitrarysetsAandB,(а) (AcB)'=AruB'.(b)(AuB))=A，cB'-證明定理2?2?2定義2.2.2IfAisaset,thenthesetofallsubsetsofAiscalledthepowersetofAandisdenotedbyP(A).(設(shè)A為一個(gè)集合，稱由A的所有子集作為元素構(gòu)成的集合為A的冪集，記為P(A)(2A)，即P(A)={S: A})例2?2?3P(①)={①},P({①})={o,{o}},P({a})={o,{a}};設(shè)A={0,1},則P(A)={o,{0},{1},{0,1}}；設(shè)B={0,1,2},則P(B)={o,{0},{1},{2},{0,1},{0,2},{1,2},B}.定理2.2.3ForarbitrarysetsA,BandC,A匸AuB,B匸AuB；AcB匸A,AcB匸B;A-B匸A;A-B=AcB'；AaB=(A-B)u(B-A)A匸C,B匸C—AuB匸C;A匸B,A匸C—A匸BcC;A匸B—B'匸a，；oeP(A),AGP(A);A匸B—P(A)匸P(B);(б) P(A)uP(B)匸P(AuB);P(AcB)=P(A)cP(B);(8)若A是有限集，貝則|P(A)|=2|A|.例2.2.4設(shè)A，B是任意集合，證明下列條件相互等價(jià)：A匸B; (2)AuB=B; (3)A=AnB.證明例2?2?4基本集合恒等式關(guān)于集合的運(yùn)算，有下列基本規(guī)律：交換律(Commutativelaws)：AuB=BuA,AnB=BnA；結(jié)合律(Associativelaws):(AuB)uC=Au(BuC),(AnB)nC=Ac(BcC);分配律(Distributivelaws):(AuB)nC=(AnC)u(BnC),(AnB)uC=(AuC)c(BuC);同一律(Identitylaws)：A①=A-①=AcU=A;零一律(Dominationlaws)Ac①=①,AU=U;有補(bǔ)律(Complementlaws)：排中律Aua，=U；矛盾律：Aca，=①；等冪律(Idempotentlaws)：AuA=AcA=A；雙否律(Complementationlaw)：(A，)，=A；吸收律(Absorptionlaws)：A屮acb)=ac(aub)=A；德摩根律(DeMorgan'slaws):(AcB):=a、b'/(AuB):=a，cb'例2.2.5(1)設(shè)A,B,C都是集合，且AcB=AcC,AuB=AuC,則B=C；對(duì)任意集合A,B,證明：A-B=①。A匸B.證明例2?2?5定義2?2?3TheCartesianproduct(叉積，笛卡爾積)ofthesetsAandB,denotedbyAxB,istheset{(a,b):aGAandbGB}.Theobject(a,b)iscalledanorderedpair(有序?qū)?withfirstcomponent(第一成員)aandsecondcomponent(第二成員)b.例2.2.6LetA={1,2,3}andB={r,s}.ThenAxB={(1,r),(1,s),(2,r),(2,s),(3,r),(3,s)}.BxA={(r；1),(r,2),(r,3),(s,1),(s,2),(s,3)}.Foranytwofinite,nonemptysetsAandB,|AxB|=|A||B|.ASSIGNMENTS：PP44-45：12，14，16，18，26，28，34，50，52，54VennDiagramsAusefultoolforrepresentingandobservinghowtheoperationsworkistheVenndiagrams.InaVenndiagram,setsarerepresentedasinteriorsofcircles,andtheuniversalsetisrepresentedasarectangular.文氏圖法(Venndiagrams)：用于描述集合間的關(guān)系及其運(yùn)算，其特點(diǎn)是直觀、形象、信息量大且富有啟發(fā)性■一般用矩形表示全集U,用圓表示U的子集A，B，C等等.ASSIGNMENTS：PP47-48：2，4，6，8，24，28，30BooleanAlgebrasThecircuitsincomputersandotherelectronicdeviceshaveinputs,eachofwhichiseithera0ora1,andproduceoutputsthatarealso0sand1s.Circuitscanbeconstructedusinganybasicelementthathastwodifferentstates.Suchelementsincludeswitchesthatcanbeineithertheonortheoffpositionandopticaldevicesthatcanbelitorunlit.1n1938ClaudeShannonshowedhowthebasicrulesoflogic,firstgivenbyGeorgeBoolein1854inhisThelawsofthought,couldbeusedtodesigncircuits.TheserulesformthebasisforBooleanalgebra.定義2.4.1(二元運(yùn)算)Anoperatoronasetisbinaryifitcombinesoroperatesontwoelementsofasettoproduceanotherelementoftheset.定義2.4.2(一元運(yùn)算)Anoperatoronasetisunaryifitoperatesononeelementofasettoproduceanotherelementoftheset.定義2.4.3(布爾代數(shù))ABooleanalgebraisasetBcontainingspecialelements1and0togetherwithbinaryoperators,+and?andaunaryoperator'onB,whichsatisfythefollowingaxiomsforallx,y,andzinB:CommutativeLaws:x?y=y?xx+y=y+xAssociativeLaws:x?(y?z)=(x?y)?zx+(y+z)=(x+y)+zDistributiveLaws:x?(y+z)=(x?y)+(x?z)x+(y?z)=(x+y)?(x+z)IdentityLaws:x+0=xx?1=xComplementLaws:x?x'=0x+x'=1Theelement1iscalledunity(么(單位)元),theelement0iscalledzero(零元),andx‘iscalledthecomplement(補(bǔ)元)ofx.Thebinaryoperation■isoftenomittedsox?yiswrittensimplyasxy.(設(shè)B是一個(gè)非空集合，?和+是B上的二元運(yùn)算，'是B上的一元運(yùn)算，0和1是B中兩個(gè)特殊元素.若它們滿足：(a)交換律:x?y=y?xx+y=y+x結(jié)合律:x?(y?z)=(x?y)?zx+(y+z)=(x+y)+z分配律:x?(y+z)=(x?y)+(x?z)x+(y?z)=(x+y)?(x+z)(d)同一律:x+0=xx?1=x(e)互補(bǔ)律:x?x'=0x+x'=1則(B,?+,，,0,1)是一個(gè)布爾代數(shù).)定理2.4.1ForallelementsxandyofaBooleanalgebra:IdempotentLaws(等冪律):x?x=xx+x=xNullLaws(零律):x?0=0x+1=1AbsorptionLaws(吸收律):x?(x+y)=xx+(x?y)=x證明定理2?4?1定理2.4.2(補(bǔ)元的唯一性)ThecomplementofanelementxofaBooleanalgebraisuniquelydefinedbyitsproperties;thatis,iX+x'=1,x?x'=0,x+x*=1andx?x*=0,thenx'=x*■證明定理2?4?2定理2.4.3ForallelementsxandyofaBooleanalgebra:InvolutionLaws(對(duì)合律):(x,),=xComplementofIdentitiesLaws:O'=11'=0DeMorgan'sLaws(德摩根律):(x+y)'=x?yr(x?y)'=x，+y‘定理2?4?4InaBooleanalgebra,x+y=yifandonlyifx?y=x.證明定理2?4?4定理2.4.5（對(duì)偶原理） InaBooleanalgebra,eachaxiomconsistsofapairofequationsthataredual（對(duì)彳禺式）inthesensethatifreplace+by?,?by+,0by1,and1by0inoneequation,wegettheotherequation.ASSIGNMENTS：PP53：2，6，8，10，12，14Relations關(guān)系是一種被廣泛使用的概念，如日常生活中的父子關(guān)系、朋友關(guān)系、債主與債戶關(guān)系，自然科學(xué)中的函數(shù)關(guān)系、相似關(guān)系、對(duì)稱關(guān)系.在計(jì)算機(jī)科學(xué)理論中關(guān)系理論的應(yīng)用更為普遍：如關(guān)系數(shù)據(jù)庫(kù)中數(shù)據(jù)特性關(guān)系、程序的輸入與輸出關(guān)系、計(jì)算機(jī)語(yǔ)言的字符關(guān)系、OOP編程中的類繼承關(guān)系、結(jié)構(gòu)化程序設(shè)計(jì)中的函數(shù)或子程序調(diào)用關(guān)系、程序的串行與并行運(yùn)算關(guān)系.從前我們介紹集合時(shí)，并不關(guān)心集合的成員之間有什么關(guān)系.而事實(shí)上客觀世界是由各種各樣的事物組成的，事物之間存在著一定的相互作用、相互聯(lián)系和相互制約的關(guān)系.集合的元素并不是烏合之眾.因此我們既有必要研究集合元素的個(gè)性、共性，更有必要研究元素之間的關(guān)系.關(guān)系描述了某一集合中兩個(gè)元素之間的一種特征.關(guān)系理論與集合論、數(shù)理邏輯以及組合學(xué)、圖論有很密切的聯(lián)系.Relationshipsbetweenelementsofsetsoccurinmanycontexts.Everydaywedealwithvariousrelationships.Relationshipsbetweenelementsofsetsarerepresentedusingthestructurecalledabinaryrelation.Relationscanbeusedtosolveproblemssuchasdeterminingwhichpairsofcitiesarelinkedbyairlineflightsinanetwork,findingaviableorderforthedifferentphasesofacomplicatedproject,orproducingausefulwaytostoreinformationincomputerdatabases.定義2.5.1LetAandBbenonemptysets.ArelationRbetweenAandB(A到B的關(guān)系)isasubsetofAxB.If(a,b)GR,wesaythataisrelatedtobbymeansofRandwewriteaRb.(A<B的子集R稱為A到B的一個(gè)二元關(guān)系■若(a,b)eR,則稱元素a,b有關(guān)系R或a與b相關(guān)，記為aRb.若(a,b)纟R,則稱元素a與b不相關(guān))特別地，當(dāng)A=B時(shí)，稱R匸AxA是A上的關(guān)系(arelationonA).例2.5.1LetA={1,2,3}andB={r,s}.ThenR={(1,r),(2,s),(3,r)}isarelationbetweenAandB.例2.5.2LetA={1,2,3,4,5}.DefinethefollowingrelationR(<,lessthan)onA:aRbifandonlyifa<b.ThenR={(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}.例2.5.3LetA=Z+.DefinethefollowingrelationR(|,division)onA:aRbifandonlyifadividesb.Then4R12,but5R7.例2.5.4LetAbethesetofallpossibleinputstoagivencomputerprogram,andBthesetofallpossibleoutputsfromthesameprogram.DefinethefollowingrelationRfromAtoB:aRbifandonlyifbistheoutputproducedbytheprogramwheninputaisused.若R=O，則稱之為空關(guān)系；若R=AxB，則稱R為全域關(guān)系■任一關(guān)系是笛卡爾積AxB的子集.A上的二元關(guān)系{(x,x)|xGA}稱為A上的恒等關(guān)系，記為I.定義2?5?2LetR匸AxB.ThedomainofR(定義域),denotedbyDom(R),isthesetofelementsinAthatarerelatedtosomeelementsinB.TherangeofR(值域)，denotedbyRan(R),isthesetofelementsinBthatarerelatedtosomeelementsinA.Dom(R)={a|aGAA(3b)(bGBA(a,b)GR)}Ran(R)={b|bGBa(3a)(aGAa(a,b)GR)}例2?5?5設(shè)A={1,2,3,4}，R匸AxA定義為：(a,b)GR。2|(a-b)，求R，R的定義域和值域.例2?5?6LetRbetherelationgivenin[例2.5.1].ThenDom(R)=A,Ran(R)=B.例2?5?7LetRbetherelationgivenin[例2.5.2].ThenDom(R)=(1,2,3,4),Ran(R)={2,3,4,5}.定義2?5?3LetR匸AxB.TherelationR-1匸BxA(theinverseofR,R的逆關(guān)系)isdefinedbybR-1aifandonlyifaRb.(設(shè)A,B均是集合，R匸AxB,則稱下列集合R-i={(y,x)|(x,y)eR}匸BxA為R的逆關(guān)系)Itisclearfromthedefinitionthat(R-1)-1=R,Dom(R-1)=Ran(R),andRan(R-1)=Dom(R).例2?5?8(1)R上的“S〃與“n〃互為逆關(guān)系Z上的“=〃與它本身互為逆關(guān)系；任一集合A上的恒等關(guān)系I的逆關(guān)系是它本身；Z+上的''整除〃與''倍數(shù)〃關(guān)系互為逆關(guān)系A(chǔ)={1,2,3},B={a,b,c},R={(1,a),(2,b),(3,a)},R-1={(a,1),(b,2),(a,3)}.定義2?5?4LetR匸AxB,S匸BxC.Thecomposite(復(fù)合)ofSandRistherelationT匸AxCdefinedby(a,c)GTifandonlyifthereisanelementbofBsuchthat(a,b)GRand(b,c)GS.WedenoteTbyS。R.特別地，若A=B=C,R=S，則記R2=R。R，R3=R。R。R， 例2?5?9設(shè)A=B=C={1,2,3}，R={(1,3),(2,3)},S={(3,1)},求R。S，SoR.定理2?5?1Compositionofrelationsisassociative;thatis,ifR匸AxB,S匸BxC,andT匸CxD,thenTo(S。R)=(T。S)。R.證明定理2?5?1定義2.5.4LetRbearelationonasetA.IfaRaforallainA,thenwesaythatRisreflexive.(若對(duì)va,,有aRa，則稱R是自反的)IfaRaforallainA,thenwesaythatRisantireflexive?(若對(duì)vaGA,有(a,a)纟R,則稱R是反自反的)IfwheneveraRb,thenbRa,thenwesaythatRissymmetric.(對(duì)va,bGA,只要aRb,則必有bRa，則稱R在A中是對(duì)稱的)IfwheneveraRbandbRa,thena=b(orifa豐b,thenaRborbRa).WesaythatRisantisymmetric.(對(duì)va,bGA,只要aRb,bRa，則必有a=b.則稱R在A中是反對(duì)稱的)IfwheneveraRbandbRc,thenaRc.WesaythatRistransitive.(對(duì)va,b,cGA,只要aRb,bRc,則必有aRc.則稱R在A中是傳遞的)例2?5?10(1)I,therelationofequalityonthesetA(A上的恒等關(guān)系或相等關(guān)系)isreflexive.LetR={(a,b)|a^b,a,bGA}(therelationofinequalityonthesetA,A上的不相等關(guān)系).ThenRisantireflexive.LetA={1,2,3}andR={(1,1),(2,1)}.ThenRisnotreflexiveandantireflexive.LetAbeanonemptyset.LetR=①(TheemptyrelationonA,A上的空關(guān)系).ThenRisantireflexivebutnotreflexive.RisreflexiveifandonlyI匸R.RisantireflexiveifandonlyifIcR=①?IfRisreflexiveonasetA,thenDom(R)=Ran(R)=A.例2.5.11 (1)LetA=ZandR={(a,b)|a<b},therelationlessthan(<).ThenRisantisymmetricbutnotsymmetric;LetA={1,2,3,4}andR={(1,2),(2,2),(3,4),(4,1)}.ThenRisnotsymmetric.Butitisantisymmetric.LetA=Z+,andR={(a,b)|adividesb}.ThenRisreflexiveandantisymmetric,butnotantireflexiveandsymmetric.定義2?5?5LetRbearelationonasetA.Thereflexiveclosure（自反閉包）ofRisthesmallestreflexiverelationonAcontainingRassaubset.Thesymmetricclosure（對(duì)稱閉包）ofRisthesmallestsymmetricrelationonAcontainingRasasubset.Thetransitiveclosure（傳遞閉包）ofRisthesmallesttransitiverelationonAcontainingRasasubset.定理2.5.2LetRbearelationonasetA.（a） ThereflexiveclosureofRisRuI.（b） ThesymmetricclosureofRisRuR-1.（c） If|A|=n,thenthetransitiveclosureofRistherelationRuR2u???uRnwh 2=ROR,…,Rk+1=RORk.證明定理2?5?2Representationofafiniteantireflexivesymmetricrelation定義2?5?6Agraph（無(wú)向圖）isafinitesetVcalledthevertexset（頂點(diǎn)集）,anantireflexivesymmetricrelationRonVandacollectionEoftwo-elementsubsetsofVdefinedby{a,b}GEifandonlyif（a,b）GR.ThesetEiscalledtheedgeset（邊集）.AnelementofEiscalledanedge（邊）.AgraphisdenotedbyG（托）■If{a,b}GE,thenwesayaandbarejoinedorconnected（連接）bytheedge{a,b}.定義2?5?7Adirectedgraph（有向圖）ordigraph，denotedbyG（V,E），consistsofasetofvertices,togetherwitharelationEonVcalledthesetofdirectededge.AnelementofEiscalledadirectededge（有向邊）.If（a,b）GE,thenaiscalledtheinitialvertex（起點(diǎn)）of（a,b）andbiscalledtheterminalvertex（終點(diǎn)）.ASSIGNMENTS：PP58-61：4，18，20，28，30，38，40，42，64，82，96PartiallyOrderedSets定義2?6?1ArelationRonAisapartialordering(偏序)ifitisreflexive,antisymmetric,andtransitive.IftherelationRonAisapartialordering,then(A,R)isapartiallyorderedsetorposet(偏序集)withorderingR.例2?6?1(1)Z,R上的、y〃、“n〃，Z+上的整除和倍數(shù)關(guān)系是偏序關(guān)系；設(shè)A為任一集合，則(P(A),匸)為一偏序集；但Z，R上的“〈”、“〉〃不是偏序關(guān)系.注：由于集合中的偏序關(guān)系是Z，R上的、y〃、“n〃的推廣，故常用“S〃表示一般的偏序關(guān)系，偏序集用(A,S)表示，用>表示偏序關(guān)系<的對(duì)偶偏序關(guān)系.Notethatthesymbol<isbeingusedtodenotethedistinetpartialorders具體理解時(shí)，我們應(yīng)該從具體定義或上下文中了解這些偏序關(guān)系的意義.定義2.6.2Twoelementsaandboftheposet(S,<)arecomparable(可比的)ifeithera<borb<a.Ifeverytwoelementsofaposet(S,<)arecomparable,thenposet(S,<)isatotalorderingorachain(全序，鏈，線序).例2.6.2(1)LetTbethesetofallpositivedivisorsof30andtherelationonTbethedivisibility|.Thentheintegers5and15arecomparablebut5and6arenotcomparable.(2)LetSbethepowersetof{a,b,c}andtherelationonSbetheinclusion匸.Then(S,匸)isaposetbutnotachain,because{a,b}and{a,c}arenotcomparable.NowwewillsimplifythedigraphofapartialorderonafinitesetA.Indeed,sinceapartialorderisreflexive,everyvertexinthedigraphofthepartialorderhasaloop.Soweshalldeleteallsuchloopsfromthedigraphtosimplifythematte.rWeshallalsoeliminatealledgesthatareimpliedbythetransitiveproperty.定義2?6?3設(shè)(A,<)是一個(gè)偏序集.若bGA滿足a<b且b豐a;若xGA使得a<x,x<b,則必有x=a或x=b.則稱b是a關(guān)于<的覆蓋(overlay).例2?6?3 (1)在偏序集(R,<)中，任意實(shí)數(shù)均無(wú)覆蓋在(Z,<)中，任意自然數(shù)均有唯一的覆蓋，即它的后繼在({1,2,3,4,5},丨)中，1的覆蓋為2和3,2的覆蓋為4,而3、4和5無(wú)覆蓋.對(duì)一個(gè)偏序集：(1)由于它的自反性,故對(duì)應(yīng)的關(guān)系圖的每個(gè)頂點(diǎn)都有自回路，因此可以省略.每個(gè)頂點(diǎn)用點(diǎn)(dot)表示.通過(guò)適當(dāng)安排頂點(diǎn)的位置使各有向邊的箭頭方向向上，從而有向邊可以簡(jiǎn)化為無(wú)向邊；(2)若a<b但b不是a的覆蓋，則省略a到b的有向邊.經(jīng)過(guò)這樣處理得到的圖稱為偏序關(guān)系V的哈斯(Hasse)圖?任一個(gè)偏序關(guān)系都有一個(gè)哈斯圖(Hassediagram).例2?6?4(1)設(shè)A={a,b},求(P(A),匸)的哈斯圖；設(shè)A={a,b,c},求(P(A),匸)的哈斯圖；設(shè)A={1,2,3,...,12},求(A,|)的哈斯圖.解例2?6?4例2?6?5給定偏序關(guān)系R的哈斯圖，也可求R的表達(dá)式.解例2?6?5ASSIGNMENTS：PP63-64：4,8,10,12,18,22,44,46EquivalenceRelations定義2.7.1ArelationRonasetAiscalledanequivalencerelation(等價(jià)關(guān)系)ifitisreflexive,symmetricandtransitive■(設(shè)A為集合，R匸AxA,若R是自反的、對(duì)稱的和傳遞的，則稱R是A上的等價(jià)關(guān)系■且若xRy，則稱x與y等價(jià))平面上直線之間的平行關(guān)系；三角形之間的全等(congruenttriangles)和相似關(guān)系，R上的“=〃關(guān)系，矩陣之間的''等價(jià)〃、''相似〃關(guān)系；而R上的二＜，＜，＞及正整數(shù)集上的整除和倍數(shù)關(guān)系都不是等價(jià)關(guān)系.例2.7.1LetA=Z,m＞1andR={(a,b)|aandbyieldthesameremainderwhentheyaredividedbym}.Wecallmthemodulus(模)andwritea三b(modm),read“aiscongruenttobmodm(a和b模m同余).Congruencemodmisanequivalentrelation(Z上的模m同余關(guān)系(m＞2)(congruentrelationmodm)是等價(jià)關(guān)系).AnequivalencerelationRonAseparatestheelementsofAintosubsetswheretheelementsinagivensubsetareallrelatedtoeachotherthroughtherelationR.(等價(jià)關(guān)系的作用是將A中的元素劃分成互不相交的若干類，每一類的元素有若干共同的性質(zhì)：如模m同余的整數(shù)關(guān)于m有相同的余數(shù)，全等三角形有相等的邊與角.)定義2.7.2LetaGAandRbeanequivaleneerelationonA.Let[a]denotetheset{x:xRa},calledtheequivalenceclass(等價(jià)類)containinga.[A]RdenotesthesetofallequivalenceclassesofAfortheequivalencerelationR.(若R為A上的等價(jià)關(guān)系，aeA，稱下列集合={y:yeAAaRy}為a關(guān)于R的等價(jià)類(記為a/R或[a])(equivaleneeclassofR),稱a為等價(jià)類[a]的一個(gè)代表.稱集合{[a]:aGA}為A關(guān)于等價(jià)關(guān)系R的商集(A/R).)例2?7?2由Z上的模m同余關(guān)系(m>2)得到的等價(jià)類就是模m同余類[0],[1],…，[m-1].例2.7.3LetA={1,2,3,4}andconsidertheequivalencerelationR={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}.Then[A]R={{1,2,3},{4}}.定義2?7?3LetAandIbesetsandletvA>={AiGI},withInonemptybeasetofnonemptysubsetsofA.Theset<A>iscalledapartition(劃分,分割)ofAifbothofthefollowingaresatisfied:AicAj=ofori豐j.A=A.iiGI定理2.7.1AnonemptysetofsubsetsvA>ofasetAisapartitionofAifandonlyifvA>=[A]forsomeequivalencerelationR.R證明定理2?7?1ASSIGNMENTS：PP68-69：2,4,8,10,22,24,30,32,34,36,38FunctionsAfunction,aspecialtypeofrelation,playsanimportantroleinmathematics,computerscience,andmanyapplications.定義2?8?1ArelationfonAxBisafunction(函數(shù)，映射)fromAtoB,denotedbyf:A—BforeveryaGA,thereisoneandonlyonebGBsothat(a,b)Gf.Iff:A—Bisafunctionand(a,b)Gf,wesaythatb=f(a).Aiscalledthedomain(定義域)offandBiscalledthecodomain(陪域).If A,thenf(E)={b:f(a)forsomeanE}iscalledtheimage(像)ofE.TheimageofAitselfiscalledtherange(值域)off.IfF匸B,thenf1(F)={a:f(a)eF}iscalledthepreimage(原像)ofF設(shè)A,B是非空集合.一個(gè)從A到B的函數(shù)f:A—B是一個(gè)滿足下列條件的從A到B的關(guān)系：對(duì)每一個(gè)aGA,存在唯 個(gè)B滿足(a,b)Gf.如果(a,b)Gf,則我們一般表示成f(a)=b，a稱為函數(shù)f的自變量(argument),b稱為a在函數(shù)f下的像(image)或值(value).函數(shù)也叫做映射(mapping)或變換(transformation).例2.8.1LetA={-2,-1,0,1,2}andB={0,1,2,3,4,5}.DefinetherelationfAxBasf={(-2,5),(-1,2),(0,1),(1,2),(2,5)}.TherelationfisafunctionfromAtoB.例2.8.2LetA={-2,-1,0,1,2}andB={0,1,2,3,4,5}.Letf:A—Bbedefinedbyf(x)=x2+1.IFE={1,2},thenf(E)={2,5}.IFF={0,2,3,4,5},thenf-1(F)={-1,1,-2,2}.f(A)={1,2,5}.定理2.8.1Letg:A—Bandf:B—CbefunctionsfromAtoBandfromBtoCrespectively.Then(a)Thecompositionf。gisafunctionfromAtoC,denotedbyf。g:A—CIfaGA,then(f。g)(a)=f(g(a)).定理2.8.2Thecompositionoffunctionsisassociative.例2.8.3設(shè)A=B=Z,C=所有偶數(shù)組成的集合.函數(shù)f和g定義為：g(a)=a+1f(b)=2b則(fog)(a)=f(g(a))=2g(a)=2(a+1).定義2?8?2Afunctionf:A—Bisone-to-oneorinjective(單射)iff(a)=f(b)impliesthata=b.Afunctionf:—Bisontoorsurjective(滿射，到上)ifforeveryyEBthereexistsanaGAsothatf(a)=b.Afunctionthatisbothone-to-oneandontoisone-to-onecorrespondence(一一對(duì)應(yīng))orbijection(雙射).IfA=Bandf:A—Bisabijection,thenfiscalledtobeapermutation(置換，排列)ofA.例2.8.4LetA={a,b,c},B={d,e,f},C={j,k},andD={o,m,n,p}.Considerthefollowingfunctions,fromAtoB,AtoD,andDtoCrespectively:f1={(a,e),(b,f),(c,d)}.f2={(a,m),(b,o),(c,p)}.f3={(d,k),(e,k),(f,j)}.Determinewhethereachfunctionisonetoone,ontoorbijection.定理2.8.3Ifafunctionf:A—Bisabijection,thentheinverserelationf-1isafunctionfromBtoAthatisalsoabijection.Conversely,forf:A—B,iff-1isafunctionfromBintoA,thenfisabijection.證明定理2?8?3定義2.8.3LetI:A—AbedefinedbyI(a)=aforallaGA.ThefunctionIiscalledtheidentityfunctiononA(A上的單位函數(shù)).定理2.8.4Iff:A—Bisabijection,then(a)f(f-1(b))=bforeachainB.(b)f-1(f(a))=aforeachainA.定理2?8?5Iff:A—AandIistheidentityfunctiononA,thenI。f=f。I=f.Iffhasaninversefunction(bijection),thenf。f-i=f-i。f=i.定理2.8.6Letg:A—Bandf:B—C;thenIfgandfareontoBandC,respectively,thenf。gisontoC.Ifgandfarebothone-to-one,thenf。gisone-to-one.Ifgandfarebothbijection,thenf。gisbijectiontooand(f。g)-1=g-1。f-1?ASSIGNMENTS：PP68-69：12，16，22，24，28，30，34，36，44定理證明及例題解答定理2?2?1aeA-B。(aGA)A(a電B)o(aeA)a(aeB')oae(AcB')定理2?2?2ae(AuB))oa電ABo(a電A)a(a電B)o(aeA')a(aeB')oae(AB')例2?2?4-(2)由定義顯然有B匸AuB.下證AuB匸B.vaeAuB,則aeA或aeB.因?yàn)锳B,所以aeB■即AuBB.-(3)由定義顯然有AcB匸A.下證A匚AnB.vaeA,則aeAuB.因?yàn)锳uB=B，所以aeB.即aeAcB，故AAcB.-(1)vaeA,因?yàn)锳cB=A，所以aeAnB,即aeB■故AB.例2?2?5B=Bu(AcB)=Bu(AcC)=(BuA)c(BuC)=(CuA)c(BuC)=(CuA)c(CuB)=Cu(AcB)=Cu(AcC)=C.u顯然；-用反證法證明.若A不是B的子集.則3aeA,但a纟B,即aeA-B.aha+xn?tha?(I+XT1:?>+>?XH>+>?xha+xnXH>?XXH>?XnXH>+X)-XH>?Xn>H>+X5N刪殽?*XJX女?><H*XX+OJX?*x+x?*xHcx+X)?*xHI?*xH*x*x?><H*X?><+0H*xx+xXH(*X+X)?><"TXJXXHI?XHS+I)?XH(A?X)+(I?XT>?x)+x(0)fx+xhcx?d+xhcx+x)?(T+xrT?(T+xrT+x(q)XHO+XHOX?X)+XH(X+X)?(x+xTl:?(X+XTX+X(e)Tqzwl眠?哽氏eHCQ—<<nJ叩H心Molls-=MOMMON?#joo」nsopo>4一sueho￡oq心4O-Is(3SO1Mp、e)nle(po)<#ose(ve)nCLUJ(PO)<su(Yq)<#UJ(q、e))oUJoEn(#￡q、e)<scp、q))g^qEnw(sol-,(p、e)#o(sol-,(p、e)nscp、q)<#,q、e)ncl￡po)<s出Qq)<#,q、e))CQ出qmn(le(po)<#os出Qe)oJEn(#os)。一出(p、e)TSNwl蝦First,weshowthatRR2u…uRn匸Rbymathematicalinduction.Forn=1,wehaveR匸R.AssumethatRuR2u Rk匸R.WewillshowthatRuR2u???uRkuRk+1匸R,thatisRk+1匸R.Let(a,c)ERk+1.Thenther