離散數(shù)學(xué)-耿素云PPT(第5版).ppt
《離散數(shù)學(xué)-耿素云PPT(第5版).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-耿素云PPT(第5版).ppt（43頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
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注意：對(duì)于任何集合A和元素x(可以是集合)，x?A和x?A兩者成立其一，且僅成立其一.,7,隸屬關(guān)系的層次結(jié)構(gòu),例3.1A={a,{b,c},d,{kgo22gs}}{b,c}?Ab?A{ewgqumk}?Awkgk4cy?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思考：?和?的定義注意?和?是不同層次的問(wèn)題,9,空集與全集,空集?不含任何元素的集合實(shí)例{x|x2+1=0?x?R}就是空集定理空集是任何集合的子集??A??x(x???x?A)?T推論空集是惟一的.證假設(shè)存在?1和?2，則?1??2且?1??2，因此?1=?2全集E相對(duì)性在給定問(wèn)題中，全集包含任何集合，即?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}相對(duì)補(bǔ)A?B={x|x?A?x?B}對(duì)稱差A(yù)?B=(A?B)?(B?A)=(A?B)?(A?B)絕對(duì)補(bǔ)?A=E?A,13,文氏圖表示,14,關(guān)于運(yùn)算的說(shuō)明,運(yùn)算順序：?和冪集優(yōu)先，其他由括號(hào)確定并和交運(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,只有一、二年級(jí)的學(xué)生才愛好體育運(yùn)動(dòng),F:一年級(jí)大學(xué)生的集合S：二年級(jí)大學(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ī)系二年級(jí)學(xué)生外都不選修離散數(shù)學(xué),例1,所有計(jì)算機(jī)系二年級(jí)學(xué)生都選修離散數(shù)學(xué),數(shù)學(xué)系一年級(jí)的學(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,由已知包含式通過(guò)運(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)行代入化簡(jiǎ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,由已知等式通過(guò)運(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無(wú)窮集的實(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下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁(yè)未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 離散數(shù)學(xué) 耿素云 PPT
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://m.jqnhouse.com/p-3494407.html