離散數學-耿素云PPT(第5版).ppt
《離散數學-耿素云PPT(第5版).ppt》由會員分享，可在線閱讀，更多相關《離散數學-耿素云PPT(第5版).ppt（43頁珍藏版）》請在裝配圖網上搜索。
1,集合論,2,集合論部分,第3章集合的基本概念和運算第4章二元關系和函數,3,第3章集合的基本概念和運算,3.1集合的基本概念3.2集合的基本運算3.3集合中元素的計數,4,3.1集合的基本概念,集合的定義與表示集合與元素集合之間的關系空集全集冪集,5,集合定義與表示,集合沒有精確的數學定義理解：一些離散個體組成的全體組成集合的個體稱為它的元素或成員集合的表示列元素法A={a,b,c,d}謂詞表示法B={x|P(x)}B由使得P(x)為真的x構成常用數集N,Z,Q,R,C分別表示自然數、整數、有理數、實數和復數集合，注意0是自然數.,6,集合與元素,元素與集合的關系：隸屬關系屬于?，不屬于?實例A={x|x?R?x2-1=0},A={-1,1}1?A,2?A注意：對于任何集合A和元素x(可以是集合)，x?A和x?A兩者成立其一，且僅成立其一.,7,隸屬關系的層次結構,例3.1A={a,{b,c},d,{wm2ecso}}{b,c}?Ab?A{owwcsw2}?Aamuk4yo?Ad?A,8,集合之間的關系,包含（子集）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,空集與全集,空集?不含任何元素的集合實例{x|x2+1=0?x?R}就是空集定理空集是任何集合的子集??A??x(x???x?A)?T推論空集是惟一的.證假設存在?1和?2，則?1??2且?1??2，因此?1=?2全集E相對性在給定問題中，全集包含任何集合，即?A(A?E),10,冪集,定義P(A)={x|x?A}實例P(?)={?}，P({?})={?,{?}}P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}}計數如果|A|=n，則|P(A)|=2n,11,3.2集合的基本運算,集合基本運算的定義?????文氏圖（JohnVenn）例題集合運算的算律集合包含或恒等式的證明,12,集合基本運算的定義,并A?B={x|x?A?x?B}交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=E?A,13,文氏圖表示,14,關于運算的說明,運算順序：?和冪集優(yōu)先，其他由括號確定并和交運算可以推廣到有窮個集合上，即A1?A2?…An={x|x?A1?x?A2?…?x?An}A1?A2?…An={x|x?A1?x?A2?…?x?An}某些重要結果??A?B?AA?B?A?B=?（后面證明）A?B=??A?B=A,15,只有一、二年級的學生才愛好體育運動,F:一年級大學生的集合S：二年級大學生的集合R：計算機系學生的集合M：數學系學生的集合T：選修離散數學的學生的集合L：愛好文學學生的集合P：愛好體育運動學生的集合,T?(M?R)?S,R?S?T,(M?F)?T=?,M?L?P,P?F?S,S?(M?R)?P,除去數學和計算機系二年級學生外都不選修離散數學,例1,所有計算機系二年級學生都選修離散數學,數學系一年級的學生都沒有選修離散數學,數學系學生或愛好文學或愛好體育運動,,,,,,16,例2,=S2,=S5,=S1,S2,S4,=S3,S5,與S1,...,S5都不等,17,集合運算的算律,吸收律的前提：?、?可交換,18,集合運算的算律（續(xù)）,19,集合包含或相等的證明方法,證明X?Y命題演算法包含傳遞法等價條件法反證法并交運算法,證明X=Y命題演算法等式代入法反證法運算法,以上的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,,利用包含的等價條件證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,假設命題不成立，必存在x使得x?X且x?Y.然后推出矛盾.例6證明A?C?B?C?A?B?C證假設A?B?C不成立，則?x(x?A?B?x?C)因此x?A或x?B，且x?C若x?A,則與A?C矛盾；若x?B,則與B?C矛盾.,24,利用已知包含式并交運算,例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,由已知包含式通過運算產生新的包含式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（吸收律）證(假設交換律、分配律、同一律、零律成立)A?(A?B)=(A?E)?(A?B)同一律=A?(E?B)分配律=A?(B?E)交換律=A?E零律=A同一律,不斷進行代入化簡，最終得到兩邊相等,27,反證法證明X=Y,例10證明以下等價條件A?B?A?B=B?A?B=A?A?B=?(1)(2)(3)(4)證明順序：(1)?(2),(2)?(3),(3)?(4),(4)?(1),假設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)假設A?B??,即?x?A?B，那么x?A且x?B.而x?B?x?A?B.從而與A?B=A矛盾.,(4)?(1)假設A?B不成立，那么?x(x?A?x?B)?x?A?B?A?B??與條件（4）矛盾.,30,集合運算法證明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,由已知等式通過運算產生新的等式X=Y?X?Z=Y?Z,X?Z=Y?Z，X-Z=Y-Z,31,集合的基數與有窮集合包含排斥原理有窮集的計數,3.3集合中元素的計數,32,集合A的基數：集合A中的元素數，記作cardA有窮集A：cardA=|A|=n，n為自然數.有窮集的實例：A={a,b,c},cardA=|A|=3；B={x|x2+1=0,x?R},cardB=|B|=0無窮集的實例：N,Z,Q,R,C等,集合的基數與有窮集合,33,包含排斥原理,定理設S為有窮集，P1,P2,…,Pm是m種性質，Ai是S中具有性質Pi的元素構成的子集，i=1,2,…,m.則S中不具有性質P1,P2,…,Pm的元素數為,,,34,證明,證設x不具有性質P1,P2,…,Pm,x?Ai,i=1,2,…,mx?Ai?Aj,1?i
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞：
- 離散數學 耿素云 PPT
裝配圖網所有資源均是用戶自行上傳分享，僅供網友學習交流，未經上傳用戶書面授權，請勿作他用。
鏈接地址：http://m.jqnhouse.com/p-3494407.html