離散數(shù)學(xué)-耿素云PPT(第5版).ppt

1,集合論,2,集合論部分,第3章集合的基本概念和運(yùn)算第4章二元關(guān)系和函數(shù),3,第3章集合的基本概念和運(yùn)算,3.1集合的基本概念3.2集合的基本運(yùn)算3.3集合中元素的計(jì)數(shù),4,3.1集合的基本概念,集合的定義與表示集合與元素集合之間的關(guān)系空集全集冪集,5,集合定義與表示,集合沒有精確的數(shù)學(xué)定義理解：一些離散個(gè)體組成的全體組成集合的個(gè)體稱為它的元素或成員集合的表示列元素法A={a,b,c,d}謂詞表示法B={x|P(x)}B由使得P(x)為真的x構(gòu)成常用數(shù)集N,Z,Q,R,C分別表示自然數(shù)、整數(shù)、有理數(shù)、實(shí)數(shù)和復(fù)數(shù)集合，注意0是自然數(shù).,6,集合與元素,元素與集合的關(guān)系：隸屬關(guān)系屬于?，不屬于?實(shí)例A={x|x?R?x2-1=0},A={-1,1}1?A,2?A注意：對于任何集合A和元素x(可以是集合)，x?A和x?A兩者成立其一，且僅成立其一.,7,隸屬關(guān)系的層次結(jié)構(gòu),例3.1A={a,{b,c},d,{eykeu2c}}{b,c}?Ab?A{s0ou6cw}?Awi0cmue?Ad?A,8,集合之間的關(guān)系,包含（子集）A?B??x(x?A?x?B)不包含A?B??x(x?A?x?B)相等A=B?A?B?B?A不相等A?B真包含A?B?A?B?A?B不真包含A?B思考：?和?的定義注意?和?是不同層次的問題,9,空集與全集,空集?不含任何元素的集合實(shí)例{x|x2+1=0?x?R}就是空集定理空集是任何集合的子集??A??x(x???x?A)?T推論空集是惟一的.證假設(shè)存在?1和?2，則?1??2且?1??2，因此?1=?2全集E相對性在給定問題中，全集包含任何集合，即?A(A?E),10,冪集,定義P(A)={x|x?A}實(shí)例P(?)={?}，P({?})={?,{?}}P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}}計(jì)數(shù)如果|A|=n，則|P(A)|=2n,11,3.2集合的基本運(yùn)算,集合基本運(yùn)算的定義?????文氏圖（JohnVenn）例題集合運(yùn)算的算律集合包含或恒等式的證明,12,集合基本運(yùn)算的定義,并A?B={x|x?A?x?B}交A?B={x|x?A?x?B}相對補(bǔ)A?B={x|x?A?x?B}對稱差A(yù)?B=(A?B)?(B?A)=(A?B)?(A?B)絕對補(bǔ)?A=E?A,13,文氏圖表示,14,關(guān)于運(yùn)算的說明,運(yùn)算順序：?和冪集優(yōu)先，其他由括號確定并和交運(yùn)算可以推廣到有窮個(gè)集合上，即A1?A2?…An={x|x?A1?x?A2?…?x?An}A1?A2?…An={x|x?A1?x?A2?…?x?An}某些重要結(jié)果??A?B?AA?B?A?B=?（后面證明）A?B=??A?B=A,15,只有一、二年級的學(xué)生才愛好體育運(yùn)動(dòng),F:一年級大學(xué)生的集合S：二年級大學(xué)生的集合R：計(jì)算機(jī)系學(xué)生的集合M：數(shù)學(xué)系學(xué)生的集合T：選修離散數(shù)學(xué)的學(xué)生的集合L：愛好文學(xué)學(xué)生的集合P：愛好體育運(yùn)動(dòng)學(xué)生的集合,T?(M?R)?S,R?S?T,(M?F)?T=?,M?L?P,P?F?S,S?(M?R)?P,除去數(shù)學(xué)和計(jì)算機(jī)系二年級學(xué)生外都不選修離散數(shù)學(xué),例1,所有計(jì)算機(jī)系二年級學(xué)生都選修離散數(shù)學(xué),數(shù)學(xué)系一年級的學(xué)生都沒有選修離散數(shù)學(xué),數(shù)學(xué)系學(xué)生或愛好文學(xué)或愛好體育運(yùn)動(dòng),,,,,,16,例2,=S2,=S5,=S1,S2,S4,=S3,S5,與S1,...,S5都不等,17,集合運(yùn)算的算律,吸收律的前提：?、?可交換,18,集合運(yùn)算的算律（續(xù)）,19,集合包含或相等的證明方法,證明X?Y命題演算法包含傳遞法等價(jià)條件法反證法并交運(yùn)算法,證明X=Y命題演算法等式代入法反證法運(yùn)算法,以上的X,Y代表集合公式,20,任取x，x?X?…?x?Y,命題演算法證X?Y,例3證明A?B?P(A)?P(B)任取xx?P(A)?x?A?x?B?x?P(B)任取xx?A?{x}?A?{x}?P(A)?{x}?P(B)?{x}?B?x?B,21,,包含傳遞法證X?Y,找到集合T滿足X?T且T?Y，從而有X?Y例4A?B?A?B證A?B?AA?A?B所以A?B?A?B,22,,利用包含的等價(jià)條件證X?Y,例5A?C?B?C?A?B?C證A?C?A?C=CB?C?B?C=C(A?B)?C=A?(B?C)=A?C=C(A?B)?C=C?A?B?C命題得證,23,反證法證X?Y,欲證X?Y,假設(shè)命題不成立，必存在x使得x?X且x?Y.然后推出矛盾.例6證明A?C?B?C?A?B?C證假設(shè)A?B?C不成立，則?x(x?A?B?x?C)因此x?A或x?B，且x?C若x?A,則與A?C矛盾；若x?B,則與B?C矛盾.,24,利用已知包含式并交運(yùn)算,例7證明A?C?B?C?A?C?B?C?A?B證A?C?B?C，A?C?B?C上式兩邊求并，得(A?C)?(A?C)?(B?C)?(B?C)?(A?C)?(A??C)?(B?C)?(B??C)?A?(C??C)?B?(C??C)?A?E?B?E?A?B,由已知包含式通過運(yùn)算產(chǎn)生新的包含式X?Y?X?Z?Y?Z,X?Z?Y?Z,25,例8證明A?(A?B)=A（吸收律）證任取x,x?A?(A?B)?x?A?x?A?B?x?A?(x?A?x?B)?x?A,命題演算法證明X=Y,任取x，x?X?…?x?Yx?Y?…?x?X或者x?X?…?x?Y,26,等式替換證明X=Y,例9證明A?(A?B)=A（吸收律）證(假設(shè)交換律、分配律、同一律、零律成立)A?(A?B)=(A?E)?(A?B)同一律=A?(E?B)分配律=A?(B?E)交換律=A?E零律=A同一律,不斷進(jìn)行代入化簡，最終得到兩邊相等,27,反證法證明X=Y,例10證明以下等價(jià)條件A?B?A?B=B?A?B=A?A?B=?(1)(2)(3)(4)證明順序：(1)?(2),(2)?(3),(3)?(4),(4)?(1),假設(shè)X=Y不成立，則存在x使得x?X且x?Y，或者存在x使得x?Y且x?X，然后推出矛盾.,28,(1)?(2)顯然B?A?B，下面證明A?B?B.任取x，x?A?B?x?A?x?B?x?B?x?B?x?B因此有A?B?B.綜合上述（2）得證.,(2)?(3)A=A?(A?B)?A=A?B（將A?B用B代入),29,(3)?(4)假設(shè)A?B??,即?x?A?B，那么x?A且x?B.而x?B?x?A?B.從而與A?B=A矛盾.,(4)?(1)假設(shè)A?B不成立，那么?x(x?A?x?B)?x?A?B?A?B??與條件（4）矛盾.,30,集合運(yùn)算法證明X=Y,例11證明A?C=B?C?A?C=B?C?A=B證由A?C=B?C和A?C=B?C得到(A?C)-(A?C)=(B?C)-(B?C)從而有A?C=B?C因此A?C=B?C?(A?C)?C=(B?C)?C?A?(C?C)=B?(C?C)?A??=B???A=B,由已知等式通過運(yùn)算產(chǎn)生新的等式X=Y?X?Z=Y?Z,X?Z=Y?Z，X-Z=Y-Z,31,集合的基數(shù)與有窮集合包含排斥原理有窮集的計(jì)數(shù),3.3集合中元素的計(jì)數(shù),32,集合A的基數(shù)：集合A中的元素?cái)?shù)，記作cardA有窮集A：cardA=|A|=n，n為自然數(shù).有窮集的實(shí)例：A={a,b,c},cardA=|A|=3；B={x|x2+1=0,x?R},cardB=|B|=0無窮集的實(shí)例：N,Z,Q,R,C等,集合的基數(shù)與有窮集合,33,包含排斥原理,定理設(shè)S為有窮集，P1,P2,…,Pm是m種性質(zhì)，Ai是S中具有性質(zhì)Pi的元素構(gòu)成的子集，i=1,2,…,m.則S中不具有性質(zhì)P1,P2,…,Pm的元素?cái)?shù)為,,,34,證明,證設(shè)x不具有性質(zhì)P1,P2,…,Pm,x?Ai,i=1,2,…,mx?Ai?Aj,1?i<j?m…x?A1?A2?…?Am,x對右邊計(jì)數(shù)貢獻(xiàn)為1?0+0?0+…+(?1)m0=1,證明要點(diǎn)：任何元素x，如果不具有任何性質(zhì)，則對等式右邊計(jì)數(shù)貢獻(xiàn)為１，否則為０,35,證明（續(xù)）,設(shè)x具有n條性質(zhì)，1?n?mx對|S|貢獻(xiàn)為1x對貢獻(xiàn)為x對貢獻(xiàn)為….x對|A1?A2?…?Am|貢獻(xiàn)為x對右邊計(jì)數(shù)貢獻(xiàn)為,36,S中至少具有一條性質(zhì)的元素?cái)?shù)為,推論,37,解：S={x|x?Z,1?x?1000},如下定義S的3個(gè)子集A,B,C：A={x|x?S,5|x}，B={x|x?S,6|x}，C={x|x?S,8|x},例1求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？,應(yīng)用,38,對上述子集計(jì)數(shù)：|S|=1000,|A|=?1000/5?=200,|B|=?1000/6?=133，|C|=?1000/8?=125,|A?B|=?1000/30?=33,|B?C|=?1000/40?=25,|B?C|=?1000/24?=41,|A?B?C|=?1000/120?=8,,代入公式N=1000?(200+133+125)+(33+25+41)?8=600,例1（續(xù)）,39,文氏圖法,求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？,40,例224名科技人員，每人至少會(huì)1門外語.英語：13；日語：5；德語：10；法語：9英日：2;英德：4；英法：4；法德：4會(huì)日語的不會(huì)法語、德語求：只會(huì)1種語言人數(shù)，會(huì)3種語言人數(shù),x+2(4-x)+y1+2=13x+2(4-x)+y2=10 x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1,y1=4,y2=3,y3=2,41,例3求歐拉函數(shù)的值,歐拉函數(shù)：?(n)表示{0,1,…,n?1}中與n互素的數(shù)的個(gè)數(shù).?(12)=4，與12互素的數(shù)有1,5,7,11.解：n的素因子分解式Ai={x|0?x<n?1且pi整除x},,,42,,,,,實(shí)例,與60互素的正整數(shù)有16個(gè)：1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59.,43,