離散數(shù)學(xué)之集合論.ppt

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

2、合,1. 集合的元素具有的性質(zhì) 無序性：元素列出的順序無關(guān) 相異性：集合的每個(gè)元素只計(jì) 數(shù)一次 確定性：對(duì)任何元素和集合都 能確定這個(gè)元素是否 為該集合的元素 任意性：集合的元素也可以是 集合 2元素與集合的關(guān)系 隸屬關(guān)系：或者 3集合的樹型層次結(jié)構(gòu),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 A B x ( xA xB ) 思考： 和 的定義 注意 和 是不同層次的問題,5,空集、全集和冪集,1定義6.4 空集 ：不含有任何元素的集合 實(shí)

3、例： x | xR x2+1=0 定理6.1 空集是任何集合的子集。 證 對(duì)于任意集合A， A x (xxA) T (恒真命題) 推論 是惟一的,3. 定義6.6 全集 E：包含了所有集合的集合 全集具有相對(duì)性：與問題有關(guān)，不存在絕對(duì)的全集,2. 定義6.5 冪集：P(A)= x | x A 實(shí)例：P()=, P()=, 計(jì)數(shù)：如果 |A|=n，則 |P(A)|=2n.,6,6.2 集合的運(yùn)算,初級(jí)運(yùn)算 集合的基本運(yùn)算有 定義6.7 并 AB = x | xA xB 交 AB = x | xA xB 相對(duì)補(bǔ) AB = x | xA xB 定義6.8 對(duì)稱差 AB = (AB)(BA) 定義6.

4、9 絕對(duì)補(bǔ) A = EA,7,文氏圖,集合運(yùn)算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,8,幾點(diǎn)說明,并和交運(yùn)算可以推廣到有窮個(gè)集合上，即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAn A B AB = AB = AB = A,9,廣義運(yùn)算,1. 集合的廣義并與廣義交 定義6.10 廣義并 A = x | z ( zA xz ) 廣義交 A= x | z ( zA xz ) 實(shí)例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a,10,關(guān)于廣

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

6、 A(AA) = a,b(a,ba) = (ab)(ab)a) = (ab)(ba) = b,12,有窮集合元素的計(jì)數(shù),1. 文氏圖法 2. 包含排斥原理 定理6.2 設(shè)集合S上定義了n條性質(zhì)，其中具有第 i 條性質(zhì)的 元素構(gòu)成子集Ai, 那么集合中不具有任何性質(zhì)的元素?cái)?shù)為,推論 S中至少具有一條性質(zhì)的元素?cái)?shù)為,13,實(shí)例,例2 求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整 除，也不能被8整除的數(shù)有多少個(gè)？,解 方法一：文氏圖 定義以下集合： S= x | xZ 1x1000 A= x | xS x可被5整除 B= x | xS x可被6整除 C= x | xS x可被8整除 畫

7、出文氏圖，然后填入相應(yīng)的數(shù)字，解得 N=1000(200+100+33+67) =600,14,實(shí)例,方法二 |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(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,15

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

9、 例3 證明A(AB) = A （吸收律） 證 任取x, xA(AB) xAxAB xA(xAxB) xA 因此得 A(AB) = A.,例4 證明 AB = AB 證 任取x, x AB xAxB xAxB xAB 因此得 AB = AB,21,等式代入法,方法二：等式置換法 例5 假設(shè)交換律、分配律、同一律、零律已經(jīng)成立，證明吸 收律. 證 A(AB) = (AE)(AB) （同一律） = A(EB) （分配律） = A(BE) （交換律） = AE （零律） = A （同一律）,22,包含等價(jià)條件的證明,例6 證明AB AB=B AB=A AB= 證明思路： 確定問題中含有的命題：本題含

10、有命題 , , , 確定命題間的關(guān)系（哪些命題是已知條件、哪些命題是要證明的結(jié)論）：本題中每個(gè)命題都可以作為已知條件，每個(gè)命題都是要證明的結(jié)論 確定證明順序：， 按照順序依次完成每個(gè)證明（證明集合相等或者包含）,23,證明,證明AB AB=B AB=A AB= 證 顯然BAB，下面證明ABB. 任取x， xAB xAxB xBxB xB 因此有ABB. 綜合上述得證. A=A(AB) A=AB (由知AB=B，將AB用B代入),24, 假設(shè)AB, 即xAB，那么知道xA且xB. 而 xB xAB 從而與AB=A矛盾. 假設(shè)AB不成立，那么 x(xAxB) xAB AB 與條件矛盾.,證明,25

11、,第六章 習(xí)題課,主要內(nèi)容 集合的兩種表示法 集合與元素之間的隸屬關(guān)系、集合之間的包含關(guān)系的區(qū)別與聯(lián)系 特殊集合：空集、全集、冪集 文氏圖及有窮集合的計(jì)數(shù) 集合的, , , , 等運(yùn)算以及廣義, 運(yùn)算 集合運(yùn)算的算律及其應(yīng)用,26,基本要求,熟練掌握集合的兩種表示法 能夠判別元素是否屬于給定的集合 能夠判別兩個(gè)集合之間是否存在包含、相等、真包含等關(guān)系 熟練掌握集合的基本運(yùn)算（普通運(yùn)算和廣義運(yùn)算） 掌握證明集合等式或者包含關(guān)系的基本方法,27,練習(xí)1,1判斷下列命題是否為真 (1) (2) (3) (4) (5) a, b a, b, c, a, b, c (6) a, b a, b, c, a

12、, b (7) a, b a, b, a, b (8) a, b a, b, a,b,解 (1)、(3)、(4)、(5)、(6)、(7)為真，其余為假.,28,方法分析,(1) 判斷元素a與集合A的隸屬關(guān)系是否成立基本方法： 把 a 作為整體檢查它在A中是否出現(xiàn)，注意這里的 a 可 能是集合表達(dá)式. (2) 判斷AB的四種方法 若A,B是用枚舉方式定義的，依次檢查A的每個(gè)元素是否在B中出現(xiàn). 若A,B是謂詞法定義的，且A, B中元素性質(zhì)分別為P和Q, 那么“若P則Q”意味 AB，“P當(dāng)且僅當(dāng)Q”意味= 通過集合運(yùn)算判斷AB，即AB = B, AB = A, AB = 三個(gè)等式中有一個(gè)為真. 通

13、過文氏圖判斷集合的包含（注意這里是判斷，而不是證明,29,練習(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中某個(gè)集合相等？如果是，又與哪個(gè)集合相等？ （1）若 XS5= （2）若 XS4但 XS2= （3）若 XS1且 X S3 （4）若 XS3= （5）若 XS3 且 X S1,30,解答,解 (1) 和S5不交的子集不含有3和5，因此 X=S2. (2) S4的子集只能是S4和S5. 由于與S2不交，不能含有偶數(shù)， 因此 X=S5. (3) S1, S2,

14、S3, S4和S5都是S1的子集，不包含在S3的子集含有 偶數(shù)，因此 X=S1, S2或S4. (4) XS3=意味著 X是S3的子集，因此 X=S3或 S5. (5) 由于S3是S1的子集，因此這樣的X不存在.,31,練習(xí)3,3. 判斷以下命題的真假，并說明理由. （1）AB = A B= （2）A(BC) = (AB)(AC) （3）AA = A （4）如果AB = B，則A = E. （5）A = xx，則 xA且x A.,32,解題思路,先將等式化簡或恒等變形. 查找集合運(yùn)算的相關(guān)的算律，如果與算律相符，結(jié)果為真. 注意以下兩個(gè)重要的充要條件 AB = A AB = AB = AB A

15、B = B AB = A 如果與條件相符，則命題為真. 如果不符合算律，也不符合上述條件，可以用文氏圖表示集合，看看命題是否成立.如果成立，再給出證明. 試著舉出反例，證明命題為假.,33,解答,解 (1) B=是AB=A的充分條件，但不是必要條件. 當(dāng)B不空但 是與A不交時(shí)也有AB=A. (2) 這是DM律，命題為真. (3) 不符合算律，反例如下： A=1，AA=，但是A. (4) 命題不為真. AB=B的充分必要條件是 BA，不是A=E. (5) 命題為真，因?yàn)?x 既是 A 的元素，也是 A 的子集,34,練習(xí)4,4證明 AB = AC AB = AC B = C,解題思路 分析命題：

16、含有3個(gè)命題： AB = AC , AB = AC, B = C 證明要求 前提：命題和 結(jié)論：命題 證明方法： 恒等式代入 反證法 利用已知等式通過運(yùn)算得到新的等式,35,解答,方法一：恒等變形法 B = B(BA) = B(AB) = B(AC) = (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，也與已知矛盾.,36,解答,方法三：利用已知等式通過運(yùn)算得

17、到新的等式. 由已知等式和可以得到 (AB) (AB) = (AC) (AC) 即 AB = AC 從而有 A(AB) =A(AC) 根據(jù)結(jié)合律得 (AA)B = (AA) C 由于AA = , 化簡上式得B = C.,37,練習(xí)5,5設(shè)A,B為集合，試確定下列各式成立的充分必要條件： (1) AB=B (2) AB=BA (3) AB=AB (4) AB=A,38,分析,解題思路: 求解集合等式成立的充分必要條件可能用到集合的算律、不同集合之間的包含關(guān)系、以及文氏圖等. 具體求解過程說明如下： (1) 化簡給定的集合等式 (2) 求解方法如下： 利用已知的算律或者充分必要條件進(jìn)行判斷 先求必要條件，然后驗(yàn)證充分性 利用文氏圖的直觀性找出相關(guān)的條件，再利用集合論的證明方法加以驗(yàn)證,39,解答,解 (1) AB=B A=B=. 求解過程如下： 由AB=B得 (AB)B = BB 化簡得B=. 再將這個(gè)結(jié)果代入原來的等式得A= . 從 而得到必要條件A=B=. 再驗(yàn)證充分性. 如果A=B=成立，則A