離散數(shù)學(xué)第2章VIP

離散數(shù)學(xué)(DiscreteMathematics),離散數(shù)學(xué)(DiscreteMathematics)計(jì)算機(jī)科學(xué)與工程系TianjinUniversityofTechnologyDepartmentofComputerScience,用小寫(xiě)字母a,b,c,代表元素。,1)如果a是集合A的一個(gè)元素,則記為,aA,讀做“a屬于A”,或“a在集合A中”。,2)如果a不是集合A的一個(gè)元素,則記為,讀做“a不屬于A”,或“a不在集合A中”。,任一元素,對(duì)某一集合而言,或?qū)儆谠摷?或不屬于該集合,二者必居其一,且只居其一。,注：,二、集合的表示法,1、符號(hào)表示法,絕不容許界限不分明或含糊不清的情況存在。,注：,離散數(shù)學(xué)中，只討論界限清楚、無(wú)二義性的描述，,不清晰的對(duì)象構(gòu)成的集合,屬于模糊論的研究范疇。,著名理發(fā)師問(wèn)題就屬于模糊論的研究范疇。,二、集合的表示法,2、描述集合中元素的方法1)列舉法a、全部列舉法：,以任意順序?qū)懗黾系乃性?隔開(kāi)，,元素間用逗號(hào),并將其放在花括號(hào)內(nèi)。,例如“所有小于5的正整數(shù)”，,這個(gè)集合的元素為,1,2,3,4,再?zèng)]有別的元素了。,如果把這個(gè)集合命名為A,A=1,2,3,4,就可記為,二、集合的表示法,2、描述集合中元素的方法1)列舉法b、部分列舉法：,列舉集合的部分元素，,素,其他元素可從列舉的元,用省略號(hào)代替。,例如A表示“全體小寫(xiě)英文字母”的集合，,A=a,b,y,z,則,歸納出來(lái)，,列舉法僅適用于描述元素個(gè)數(shù)有限的集合,注：,或,元素具有明顯排列規(guī)律的集合。,二、集合的表示法,2、描述集合中元素的方法2)描述法,把集合元素的共同屬性描述出來(lái)。,集合中元素的屬性。,P(x)表示任何謂詞，,則,A=x|P(x),即用謂詞概括,表示所有使謂詞P(x)成立的元素x所組成的集合。,例：x|x2-3x+2=0、,x|x=2n-1nN,如果P(a)為真，,則aA，,否則,(謂詞表示法),集合的元素,集合的元素必須滿足的條件,二、集合的表示法,1、有些集合可以用兩種方法表示，,注：,但是有些,集合不可以用列元素法表示，,如實(shí)數(shù)集合。,2、集合的元素是彼此不同的，,如果同一個(gè)元,素在集合中多次出現(xiàn),應(yīng)該認(rèn)為是一個(gè)元素。,如:3,4,4,4,5、,3,4,5、,5,4,3,是同一個(gè)集合。,3、集合的元素是無(wú)序的。,4、集合的元素可以是一個(gè)集合，,但不允許以,集合自身為其元素。,如:S=a,b,S=a,b,S,aS，,A，,三、元素和集合之間的關(guān)系,元素和集合之間的關(guān)系,是隸屬關(guān)系，,即屬于,或不屬于，,屬于記作，,不屬于記作。,例如：A=1，1，2，3，3,1,1，2,3,A，,A，,3,A，,2,3,A，,A。,可以用一種樹(shù)形圖表示集合與元素的隸屬關(guān)系。,A,2,1，2，,AB,(),四、集合間的包含關(guān)系,1、子集,如果集合A中每個(gè)元素,都是集合B中的元素，,則稱(chēng)A是B的,或A包含于B，,子集，,或者B包含A，,記作AB,如果A不是B的子集，,或BA。,AB,(x),x,A,x,B,則在A中至少有一個(gè)元素,不屬于B時(shí)，,稱(chēng)B不包含A，,記作,或BA。,注：,1)AA，,2)AB，,BC，,則AC。,B,(),四、集合間的包含關(guān)系,2、集合相等1)定義,兩個(gè)集合相等,當(dāng)且僅當(dāng),它們有相同的元素。,若A和B相等，,記作,A=B,(x),x,A,x,(外延性原理),A=B。,兩個(gè)集合不相等，,記作AB。,四、集合間的包含關(guān)系,2、集合相等2)判斷,A與B互為,子集。,定理若A和B相等,當(dāng)且僅當(dāng),AB,且,BA。,即,A,(),(),四、集合間的包含關(guān)系,3、真子集,如果集合A中每個(gè)元素,都屬于集合B，,但B中,不屬于A，,則稱(chēng)A是B的,記作AB,或BA。,AB,(x),x,A,x,B,至少有一個(gè)元素,真子集。,(x),x,B,x,AB,AB,例A=a，b,B=a，b,不是,的子集。,（真）,四、集合間的包含關(guān)系,3、真子集,可以用文氏圖了表示集合間的包含關(guān)系。,文氏(Venn)圖是一種利用平面上的點(diǎn)構(gòu)成的圖形來(lái)形象展示集合的一種方法。,集合用矩形、園面,如果AB，,或一封閉曲線來(lái)表示。,則表示A的圓面,一般完全落在,表示B,的圓面內(nèi)。,A,B,B,A,AB,四、集合間的包含關(guān)系,4、隸屬和包含關(guān)系的區(qū)別,例A=a，a，B=a,BA，,BA，,B是A的元素，,B的元素a,是A的元素，,B是A的子集。,隸屬是,元素,和,集合,的關(guān)系，,包含是,集合,和,集合,的關(guān)系，,某些集合可以同時(shí)成立這兩種關(guān)系。,是個(gè)體與整體的關(guān)系，,是部分與整體的關(guān)系。,五、特殊集合,1、空集定義,不含任何元素的集合,空集，,稱(chēng)為,記作,。,例兩條平行線交點(diǎn)的集合,為。,例x|x0x0xR,=。,注：,1)與的區(qū)別。,是集合，沒(méi)有元素,有1個(gè)元素的集合,2)，,五、特殊集合,1、空集定理,空集是任一集合A的子集，,即A。,下列命題是否為真。,練習(xí),1);2);3);4)。,五、特殊集合,1、空集推理,空集是唯一的。,設(shè)1，2是兩個(gè)空集,則12，,且21，,得1=2，,所以空集是唯一的。,證明：,證明唯一性一般采用反證法,(絕對(duì)唯一),證畢。,五、特殊集合,1、空集,2)證明一個(gè)集合是空集，或證明集合的唯一性，,常采用反證方法，,即假設(shè)該集合不是空集，,或不唯一，,導(dǎo)致與已知條件的矛盾或?qū)е挛ㄒ弧?注：,1)任何非空集合A，,至少有子集：,兩個(gè),、,和A。,只有子集,一個(gè),。,五、特殊集合,2、全集定義,在一定范圍內(nèi)，如果所有集合都是某一集合的子集，,則稱(chēng)此集合為,全集,記作,U。,注：,1)全集是相對(duì)的，不同的問(wèn)題有不同的全集，,即使是同一個(gè)問(wèn)題也可以取不同的全集。,2)一般地說(shuō)，全集取得小一些，問(wèn)題的描述和處理會(huì)簡(jiǎn)單些。,3)全集U用一個(gè)矩形的內(nèi)部表示，,U,五、特殊集合,3、冪集定義,由集合A的所有子集為元素所組成的集合,稱(chēng)為A的,冪集,記作,注：,1)冪集的元素都是,集合。,或P(A),或2A。,2)任一集合的冪集,都非空。,3)在A的所有子集中，,A,和,又叫平凡子集。,(A),、,a,五、特殊集合,3、冪集例的冪集：,=,A=a的冪集：,=,、,a,A=a，b的冪集：,=,b,a、b,有個(gè)元素,1,有個(gè)元素,2,有個(gè)元素,4,20,21,22,(A),五、特殊集合,3、冪集一般地，,集合A=a1、a2、an，,則,有個(gè)元素。,2n,它的m(0mn)元子集有個(gè)，,不同的子集共有,+,=(1+1)n,=2n個(gè)。,A=x|，,理發(fā)師問(wèn)題,在一個(gè)很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專(zhuān)給那些并且只給那些自己不刮臉的人刮臉。那么，誰(shuí)給這位理發(fā)師刮臉？,解：,設(shè),不給自己刮臉的人,x是,b是這位理發(fā)師。,1)若bA，,則b是不給自己刮臉的人，,而由題意，,b只給集合A中的人刮臉。,b要給b刮臉，,即bA。,理發(fā)師問(wèn)題,在一個(gè)很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專(zhuān)給那些并且只給那些自己不刮臉的人刮臉。那么，誰(shuí)給這位理發(fā)師刮臉？,解：,則b是要給自己刮臉的人，,而由題意，,理發(fā)師只給自己不刮臉的人刮臉。,b是不給自己刮臉的人，,即bA。,無(wú)論1)和2)，,都有,bA,同時(shí)成立。,這種情況稱(chēng)為羅索悖論，,是模糊論的范疇。,第二節(jié)集合的運(yùn)算,一集合的交,二集合的并,三集合的補(bǔ),四集合的對(duì)稱(chēng)差,五集合恒等式,六小結(jié),一、集合的交,1、定義2、文氏圖,任意兩個(gè)集合A和B，,由A和B的,所有共同元素,組成的集合，,稱(chēng)為A和B的,交集，,記為,AB。,AB=x|xAxB,即,(Intersection),AB,A,B,一、集合的交,如果兩個(gè)集合沒(méi)有任何共同的元素，,(Intersection),例如，A=a,b,c,e,f，B=b,e,f,r,s，C=a,t,u,v,則,AB=,b,e,f,AC=,a,BC=,則稱(chēng)它們是,不相交,集合。,E,A,B,一、集合的交,三個(gè)或更多的集合的交集運(yùn)算：,(Intersection),ABC=,x|,xA,xB,xC,一、集合的交,3、性質(zhì),AA,1)冪等律,(Intersection),=A,A,2)零律,=,AE,3)同一律,=A,AB,4)交換律,=BA,A(BC),5)結(jié)合律,=(AB)C,(),B,一、集合的交,3、性質(zhì),(Intersection),若AB，,6),則AC,BC。,反之,不然。,證：,AB,(x),x,A,x,分析：,若xAC，,即,xA,xC,AB,xA,xB,則,xB,xC,xBC。,反之，,取C=，,A=a，,B=b，,則,AC,=,BC,=,證畢,一、集合的交,3、性質(zhì),(Intersection),AB,7),A,AB,B,（集合越交,越?。?注：,集合運(yùn)算的規(guī)律和命題演算的某些規(guī)律是一致的，所以命題演算的方法是證明集合恒等式的基本方法。,二、集合的并,1、定義2、文氏圖,任意兩個(gè)集合A和B，,由屬于A,或?qū)儆贐,組成的集合，,稱(chēng)為A和B的,并集，,記為,AB。,AB=x|xAxB,即,(Union),的元素,A,B,二、集合的并,三個(gè)或更多的集合的并集運(yùn)算：,(Union),E,A,B,ABC=,x|,xA,C,xB,xC,二、集合的并,3、性質(zhì),AA,1)冪等律,(Union),=A,AU,2)零律,=U,A,3)同一律,=A,AB,4)交換律,=BA,A(BC),5)結(jié)合律,=(AB)C,二、集合的并,3、性質(zhì)，,(Union),若AB，,6),則AC,BD。,反之,不然。,若xAC，,即,xA,xC,CD，,1)若xA，,則xB，,xBD，,2)若xC，,則xD，,xBD，,始終有xBD。,反之，,取C=D=E，,A=a，,B=b，,則,AC,E=,BD,=E,證：,證畢。,二、集合的并,3、性質(zhì),(Union),AB，,7),A,（集合越并,越大）,AB,B,xB,(),xB,xA,(),(),二、集合的并,4、和的關(guān)系,(Union),定理,對(duì)任意集合A、B和C有:,1)A(BC)=(AB)(AC);,2)A(BC)=(AB)(AC)。,即對(duì)可以分配,對(duì)可以分配。,1)A(BC),=x|,xA,xC,=x|,xA,xC,=(AB),(AC),=x|,xA,xB,xA,xC,x|,分配律,分配律,證：,xB,(),xA,二、集合的并,4、和的關(guān)系,(Union),定理,對(duì)任意集合A、B有:,1)A(AB)=A,2)A(AB)=A,證一：,1)A(AB),=x|,xA,=x|,xA,=A,吸收律,吸收律,命題邏輯中的吸收律,二、集合的并,4、和的關(guān)系吸收律,(Union),定理,對(duì)任意集合A、B有:,AB,AB=B,或,AB=A。,當(dāng)且僅當(dāng),AB，,BB，,AB,BB,=B,由性質(zhì)7),B,AB,AB,=B,反之，,由性質(zhì)7),A,AB,AB=B,AB,證：,證畢。,三、集合的補(bǔ),1、定義2、文氏圖,任意兩個(gè)集合A和B，,由屬于A,但不屬于B,組成的集合，,稱(chēng)為B對(duì)于A的,補(bǔ)集,記為,AB。,AB=x|xAxB,即,(RelativeComplement),所有元素,或相對(duì),的,補(bǔ),或A和B的差。,=x|xA(xB),B,A,三、集合的補(bǔ),3、絕對(duì)補(bǔ)集,全集U和集合A的差集,稱(chēng)為A的,絕對(duì)補(bǔ),記為,UA,A=,即,(RelativeComplement),或A的余集,或A的補(bǔ)集。,=x|xUxA,A,或A,UA,xA,xA,(AbsoluteComplement).,三、集合的補(bǔ),4、性質(zhì),(RelativeComplement),(A),1)雙重否定律,=A,U,2),=,3),=U,AA,4)排中律,=U,AA,5)矛盾律,=,三、集合的補(bǔ),4、性質(zhì),(RelativeComplement),(1)(AB),6)德摩根律,=AB,(2)(AB),=AB,(AB),=x|xU,(xAB),=x|xU,(xA,=x|xU,(xA),(xB),=x|(xU,(xA),(xB),(xU,=A,B,xB),證:(1),A,(),B,(),三、集合的補(bǔ),5、定理：,(RelativeComplement),2),利用(3)的結(jié)論。,A-(AB),=A,(AB),=A,A,(3)的結(jié)論,德摩根律,=A,A,B,(),=A-B,1)A-B,=AB,2)A-B,=A-(AB),分配律,三、集合的補(bǔ),5、定理,(RelativeComplement),4)A(B-C)=(AB)-(AC),三、集合的補(bǔ),5、定理,(RelativeComplement),4)a)ABBA,b)AB(B-A)A=B,證：a),若xA,則必有xB，,因此xB，,必有xA，,即xB,xA,BA,AB,由上述證明可知：,(A),BA,(B),A=,=B,ABBA,四、集合的對(duì)稱(chēng)差,1、定義,(SymmetricDifference),設(shè)A、B是兩個(gè)集合，,其元素,但,集合A和B的對(duì)稱(chēng)差(環(huán)和）是,集合，,記作AB,或?qū)儆贏，,或?qū)儆贐,不能既屬于A,又屬于B，,即：,AB=(A-B)(B-A),例如A=a,b,c,B=b,d,則AB,=,a,c,d,=x|(xAxB)(xBxA),四、集合的對(duì)稱(chēng)差,2、文氏圖,(SymmetricDifference),四、集合的對(duì)稱(chēng)差,3、性質(zhì),(SymmetricDifference),1)交換律,2)同一律,3)零律,AB=,4),AB,=BA,A,=A,AA,=,B),(A,(A,B),四、集合的對(duì)稱(chēng)差,3、性質(zhì),(SymmetricDifference),(AB)C=A(BC),5)結(jié)合律,定義2.2-6A、B兩集合的環(huán)積記為AB，是集合。,定理2.2-12(1)=AB，(2)AB=BA，(3)AA=U。,定理2.2-13,定理2.2-14,例1已知ABAC，是否必須BC？,解：,是。,AB=AC，,A(AB),=A(AC),(AA)B,=(AA)C,B,=,C,B=C。,例2已知AB=AC，是否必須B=C？,解：,否。,例：,設(shè)A=1、2，B=1，C=2,例3已知AB=AC，是否必須B=C？解：例：,設(shè)A=1，B=1、2，C=1、3,否。,2-5集合的笛卡爾積,1、序偶(有序2元組)：兩個(gè)具有固定次序的客體組成一個(gè)序偶(有序2元組)，記作，其中x是它的第一元素，y是它的第二元素。,一、有序n元組,例：平面直角坐標(biāo)系中的一個(gè)點(diǎn)的坐標(biāo)就構(gòu)成為一個(gè)有序序偶，我們可用表示。注：序偶是講究次序的。例和表示平面上兩個(gè)不同的點(diǎn)，這與集合不同，1，3和3，1是兩個(gè)相等的集合。2、定義：兩個(gè)序偶相等，=，當(dāng)且僅當(dāng)x=u且y=v。,一、有序n元組,3、有序元組：是一個(gè)序偶，其第一元素本身也是一個(gè)序偶，表示為，z或。4、有序n元組：有序n元組也是一個(gè)序偶，其第一元素是一個(gè)n-1元組。，xn，通常簡(jiǎn)記為：，其中xi稱(chēng)作它的第i坐標(biāo)，i=1，2，n。=的充要條件是xi=yi，i=