離散數(shù)學(xué)屈婉玲第六章.ppt

《離散數(shù)學(xué)屈婉玲第六章.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)屈婉玲第六章.ppt（44頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1,主要內(nèi)容 集合的基本概念 屬于、包含 冪集、空集 文氏圖等 集合的基本運算 并、交、補、差等 集合恒等式 集合運算的算律、恒等式的證明方法,第二部分 集合論,第六章 集合代數(shù),2,6.1 集合的基本概念,1. 集合定義 集合沒有精確的數(shù)學(xué)定義 理解：由離散個體構(gòu)成的整體稱為集合，稱這些個體為集 合的元素 常見的數(shù)集：N, Z, Q, R, C 等分別表示自然數(shù)、整數(shù)、有 理數(shù)、實數(shù)、復(fù)數(shù)集合,2. 集合表示法 枚舉法----通過列出全體元素來表示集合 謂詞表示法----通過謂詞概括集合元素的性質(zhì) 實例： 枚舉法 自然數(shù)集合 N=0,1,2,3,

2、 謂詞法 S= x | x是實數(shù)，x21=0,3,元素與集合,1. 集合的元素具有的性質(zhì) 無序性：元素列出的順序無關(guān) 相異性：集合的每個元素只計 數(shù)一次 確定性：對任何元素和集合都 能確定這個元素是否 為該集合的元素 任意性：集合的元素也可以是 集合 2元素與集合的關(guān)系 隸屬關(guān)系：或者 3集合的樹型層次結(jié)構(gòu) A= a, b, b, d ,d A , a A,4,集合與集合,集合與集合之間的關(guān)系：, =, , , , 定義6.1 A B x ( xA xB ) 定義6.2 A = B A B B A 定義6.3 A B A B A B

3、A B x ( xA xB ) 思考： 和 的定義 注意 和 是不同層次的問題,5,空集、全集和冪集,1定義6.4 空集 ：不含有任何元素的集合 實例： x | xR x2+1=0 定理6.1 空集是任何集合的子集。 證 對于任意集合A， A x (xxA) T (恒真命題) 推論 是惟一的,3. 定義6.6 全集 E：包含了所有集合的集合 全集具有相對性：與問題有關(guān)，不存在絕對的全集,2. 定義6.5 冪集：P(A)= x | x A 實例：P()=, P()=, 計數(shù)：如果 |A|=n，則 |P(A)|=2n.,6,6.2 集合的運算,初級運算 集合的基本運算有 定

4、義6.7 并 AB = x | xA xB 交 AB = x | xA xB 相對補 AB = x | xA xB 定義6.8 對稱差 AB = (AB)(BA) 定義6.9 絕對補 A = EA 并和交運算可以推廣到有窮個集合上，即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAn,7,廣義運算,1. 集合的廣義并與廣義交 定義6.10 廣義并 A = x | z ( zA xz ) 定義6.11 廣義交 A= x | z ( zA xz ) 實例 1, 1,2, 1,2,3=1,2,3

5、 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a,8,關(guān)于廣義運算的說明,2. 廣義運算的性質(zhì) (1) =，無意義 (2) 單元集x的廣義并和廣義交都等于x (3) 廣義運算減少集合的層次（括弧減少一層） (4) 廣義運算的計算：一般情況下可以轉(zhuǎn)變成初級運算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An 3. 引入廣義運算的意義 可以表示無數(shù)個集合的并、交運算，例如 x | xR=R 這里的 R 代表實數(shù)集合.,9,運算的優(yōu)先權(quán)規(guī)定,1 類運算：初級運算, , , ， 優(yōu)先順序由

6、括號確定 2 類運算：廣義運算和運算， 運算由右向左進(jìn)行 混合運算：2 類運算優(yōu)先于1 類運算,例1 A=a,a,b，計算A(AA). 解： A(AA) = a,b(a,ba) = (ab)((ab)a) = (ab)(ba) = b,10,文氏圖,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,6.3 有窮集合元素的計數(shù),11,方法一：文氏圖,例2 求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整 除，也不能被8整除的數(shù)有多少個？,解 定義以下集合： S= x | xZ 1x1000 A= x | xS x可被

7、5整除 B= x | xS x可被6整除 C= x | xS x可被8整除 畫出文氏圖，填入相應(yīng)數(shù)字，得 N=1000(200+100+33+67) =600,12,方法二：包含排斥原理,定理6.2 設(shè)集合S上定義了n條性質(zhì)，其中具有第 i 條性質(zhì)的 元素構(gòu)成子集Ai, 那么集合中不具有任何性質(zhì)的元素數(shù)為,推論 S中至少具有一條性質(zhì)的元素數(shù)為,13,實例,方法二 |S| = 1000 |A|=1000/5=200, |B|=1000/6=166, |C|=1000/8=125 |AB| = 1000/lcm(5,6) = 1000/33 = 33 |AC| = 1000/lcm(

8、5,8) = 1000/40 = 25 |BC| = 1000/lcm(6,8) = 1000/24 = 41 |ABC| = 1000/lcm(5,6,8) = 1000/120 = 8 = 1000(200+166+125)+(33+25+41)8 = 600,歐拉函數(shù),例3 求歐拉函數(shù)的值. 歐拉函數(shù)(n)表示0,1,,n1中與n互素的數(shù)的個數(shù). (12)=4，與12互素的數(shù)有1, 5, 7, 11. (1)=1. 給定正整數(shù)n， 為n的素因子分解式，令 Ai= x | 0 x

9、正整數(shù)有16個：1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59.,15,,,實例：,錯位排列計數(shù),例4 錯位排列：排列 i1 i2 in，滿足 ij j, j = 1, 2, , n. 錯位排列數(shù) S為1, 2, , n排列的集合，Pi是 i 處在排列 第i 位的性質(zhì)， Ai是S中具有性質(zhì)Pi的排列的集合，i=1, 2, , n. |S|=n!， |Ai|=(n1)! i=1,2,,n |AiAj|=(n2)! 1i

10、6.4 集合恒等式,集合算律 1只涉及一個運算的算律： 交換律、結(jié)合律、冪等律,18,集合算律,2涉及兩個不同運算的算律： 分配律、吸收律,19,集合算律,3涉及補運算的算律： DM律，雙重否定律,20,集合算律,4涉及全集和空集的算律： 補元律、零律、同一律、否定律,21,集合證明題,證明方法：命題演算法、等式置換法 命題演算證明法的書寫規(guī)范 (以下的X和Y代表集合公式) (1) 證XY 任取x， xX xY (2) 證X=Y 方法一 分別證明 XY 和 YX 方法二 任取x，xX xY 注意：在使用方法二的格式時，必須保證每步推理都是充 分必要的,22,集

11、合等式的證明,方法一：命題演算法 例5 證明A(AB) = A （吸收律） 證 任取x, xA(AB) xAxAB xA(xAxB) xA 因此得 A(AB) = A.,例6 證明 AB = AB 證 任取x, x AB xAxB xAxB xAB 因此得 AB = AB,23,等式代入法,方法二：等式置換法 例7 假設(shè)交換律、分配律、同一律、零律已經(jīng)成立，證明吸 收律. 證 A(AB) = (AE)(AB) （同一律） = A(EB) （分配律） = A(BE) （交換律） = AE

12、 （零律） = A （同一律）,24,包含等價條件的證明,例8 證明AB AB=B AB=A AB= 證明思路： 確定問題中含有的命題：本題含有命題 , , , 確定命題間的關(guān)系（哪些命題是已知條件、哪些命題是要證明的結(jié)論）：本題中每個命題都可以作為已知條件，每個命題都是要證明的結(jié)論 確定證明順序：，，， 按照順序依次完成每個證明（證明集合相等或者包含）,25,證明,證明AB AB=B AB=A AB= 證 顯然BAB，下面證明ABB. 任取x， xAB xAxB xBxB xB 因此有ABB. 綜合上

13、述得證. A=A(AB) A=AB (由知AB=B，將AB用B代入),26, 假設(shè)AB, 即xAB，那么知道xA且xB. 而 xB xAB 從而與AB=A矛盾. 假設(shè)AB不成立，那么 x(xAxB) xAB AB 與條件矛盾.,證明,27,第六章 習(xí)題課,主要內(nèi)容 集合的兩種表示法 集合與元素之間的隸屬關(guān)系、集合之間的包含關(guān)系的區(qū)別與聯(lián)系 特殊集合：空集、全集、冪集 文氏圖及有窮集合的計數(shù) 集合的, , , , 等運算以及廣義, 運算 集合運算的算律及其應(yīng)用,28,基本要求,熟練掌握集合的兩種表示法 能夠判別元素是否屬于給定的集合 能夠判別兩個集合之間是否存在包含、相等、真包含

14、等關(guān)系 熟練掌握集合的基本運算（普通運算和廣義運算） 掌握有窮集合的計數(shù)方法和包含排斥原理 掌握證明集合等式或者包含關(guān)系的基本方法,29,練習(xí)1,1判斷下列命題是否為真 (1) (2) (3) (4) (5) a, b a, b, c, a, b, c (6) a, b a, b, c, a, b (7) a, b a, b, a, b (8) a, b a, b, a,b,解 (1)、(3)、(4)、(5)、(6)、(7)為真，其余為假.,30,方法分析,(1) 判斷元素a與集合A的隸屬關(guān)系是否成立基本方法： 把 a 作為整體檢查它在A中是否出現(xiàn)，注意這里的 a 可 能是集合表達(dá)式

15、. (2) 判斷AB的四種方法 若A,B是用枚舉方式定義的，依次檢查A的每個元素是否在B中出現(xiàn). 若A,B是謂詞法定義的，且A, B中元素性質(zhì)分別為P和Q, 那么“若P則Q”意味 AB，“P當(dāng)且僅當(dāng)Q”意味= 通過集合運算判斷AB，即AB = B, AB = A, AB = 三個等式中有一個為真. 通過文氏圖判斷集合的包含（注意這里是判斷，而不是證明,31,練習(xí)2,2設(shè) S1=1, 2, , 8, 9， S2=2, 4, 6, 8 S3=1, 3, 5, 7, 9 S4=3, 4, 5 S5=3, 5 確定在以下條件下X是否與S1,,S5中某個集合相等？如果是，

16、又與哪個集合相等？ （1）若 XS5= （2）若 XS4但 XS2= （3）若 XS1且 X S3 （4）若 XS3= （5）若 XS3 且 X S1,32,解答,解 (1) 和S5不交的子集不含有3和5，因此 X=S2. (2) S4的子集只能是S4和S5. 由于與S2不交，不能含有偶數(shù)， 因此 X=S5. (3) S1, S2, S3, S4和S5都是S1的子集，不包含在S3的子集含有 偶數(shù)，因此 X=S1, S2或S4. (4) XS3=意味著 X是S3的子集，因此 X=S3或 S5. (5) 由于S3是S1的子集，因此這樣的X不存在.,練習(xí)3,3. 一個班50個學(xué)生，在第

17、一次考試中有26人得5分，在第二次考試中有21人得5分. 如果兩次考試中都沒有得5分的有17人，那么兩次考試都得5分的有多少人？ 求解 方法一：文氏圖填圖法 第一次得5分學(xué)生：集合A 第二次得5分學(xué)生：集合B 全班學(xué)生：全集 E (26x)+x+(21x)+17=50 x=14.,33,文氏圖,求解,方法二：使用包含排斥原理. A、B和全集E設(shè)定同上. 那么有 |E|=50, |A|=26, |B|=21 根據(jù)包含排斥原理有 代入得：,34,,,35,練習(xí)4,4. 判斷以下命題的真假，并說明理由. （1）AB = A B= （2）A(BC) = (AB)(AC)

18、（3）AA = A （4）如果AB = B，則A = E. （5）A = xx，則 xA且x A.,36,解題思路,先將等式化簡或恒等變形. 查找集合運算的相關(guān)的算律，如果與算律相符，結(jié)果為真. 注意以下兩個重要的充要條件 AB = A AB = AB = AB AB = B AB = A 如果與條件相符，則命題為真. 如果不符合算律，也不符合上述條件，可以用文氏圖表示集合，看看命題是否成立.如果成立，再給出證明. 試著舉出反例，證明命題為假.,37,解答,解 (1) B=是AB=A的充分條件，但不是必要條件. 當(dāng)B不空但 是與A不交時也有AB=A. (2) 這是DM律，命題為真.

19、 (3) 不符合算律，反例如下： A=1，AA=，但是A. (4) 命題不為真. AB=B的充分必要條件是 BA，不是A=E. (5) 命題為真，因為 x 既是 A 的元素，也是 A 的子集,38,練習(xí)5,5證明 AB = AC AB = AC B = C,解題思路 分析命題：含有3個命題： AB = AC , AB = AC, B = C 證明要求 前提：命題和 結(jié)論：命題 證明方法： 恒等式代入 反證法 利用已知等式通過運算得到新的等式,39,解答,方法一：恒等變形法 B = B(BA) = B(AB) = B(AC)

20、 = (BA)(BC) = (AC)(BC) = (AB)C = (AC)C = C,方法二：反證法. 假設(shè) B C，則存在 x (xB且xC), 或存在 x (xC且xB). 不妨設(shè)為前者. 若x屬于A，則x屬于AB 但x不屬于AC，與已知矛盾； 若x不屬于A，則x屬于AB但x不屬于AC，也與已知矛盾.,40,解答,方法三：利用已知等式通過運算得到新的等式. 由已知等式和可以得到 (AB) (AB) = (AC) (AC) 即 AB = AC 從而有 A(AB) =A(AC) 根據(jù)結(jié)合律得 (AA)B = (AA) C 由于AA =

21、, 化簡上式得B = C.,41,練習(xí)6,6設(shè)A,B為集合，試確定下列各式成立的充分必要條件： (1) AB=B (2) AB=BA (3) AB=AB (4) AB=A,42,分析,解題思路: 求解集合等式成立的充分必要條件可能用到集合的算律、不同集合之間的包含關(guān)系、以及文氏圖等. 具體求解過程說明如下： (1) 化簡給定的集合等式 (2) 求解方法如下： 利用已知的算律或者充分必要條件進(jìn)行判斷 先求必要條件，然后驗證充分性 利用文氏圖的直觀性找出相關(guān)的條件，再利用集合論的證明方法加以驗證,43,解答,解 (1) AB=B A=B=. 求解過程如下： 由AB=B得 (AB)B

22、= BB 化簡得B=. 再將這個結(jié)果代入原來的等式得A= . 從 而得到必要條件A=B=. 再驗證充分性. 如果A=B=成立，則AB==B也成立.,(2) AB=BA A=B. 求解過程如下： 充分性是顯然的，下面驗證必要性. 由AB=BA得 (AB)A=(BA)A 從而有A=AB, 即AB. 同理可證BA.,44,解答,(3) AB=AB A=B. 求解過程如下： 充分性是顯然的，下面驗證必要性. 由AB=AB得 A(AB) = A(AB) 化簡得A =AB，從而有AB. 類似可以證明BA.,(4) AB=A B=. 求解過程如下： 充分性是顯然的，下面驗證必要性. 由AB = A得 A(AB) = AA 根據(jù)結(jié)合律有 (AA)B = AA 即 B = , 就是B = .,