離散數(shù)學(xué)_高等教育出版社配套PPT課件_屈婉玲_耿素云_張立昂-6

1、1主要內(nèi)容主要內(nèi)容l 集合的基本概念集合的基本概念 屬于、包含屬于、包含 冪集、空集冪集、空集 文氏圖等文氏圖等l 集合的基本運(yùn)算集合的基本運(yùn)算 并、交、補(bǔ)、差等并、交、補(bǔ)、差等l 集合恒等式集合恒等式 集合運(yùn)算的算律、恒等式的證明方法集合運(yùn)算的算律、恒等式的證明方法 第二部分第二部分 集合論集合論第六章第六章 集合代數(shù)集合代數(shù)26.1 集合的基本概念集合的基本概念1. 集合定義集合定義 集合沒有精確的數(shù)學(xué)定義集合沒有精確的數(shù)學(xué)定義 理解：由離散個(gè)體構(gòu)成的整體稱為理解：由離散個(gè)體構(gòu)成的整體稱為集合集合，稱這些個(gè)體為集，稱這些個(gè)體為集 合的合的元素元素 常見的數(shù)集：常見的數(shù)集：N, Z, Q,

2、R, C 等分別表示自然數(shù)、整數(shù)、有等分別表示自然數(shù)、整數(shù)、有 理數(shù)、實(shí)數(shù)、復(fù)數(shù)集合理數(shù)、實(shí)數(shù)、復(fù)數(shù)集合2. 集合表示法集合表示法 枚舉法枚舉法-通過列出全體元素來表示集合通過列出全體元素來表示集合 謂詞表示法謂詞表示法-通過謂詞概括集合元素的性質(zhì)通過謂詞概括集合元素的性質(zhì) 實(shí)例：實(shí)例： 枚舉法枚舉法 自然數(shù)集合自然數(shù)集合 N=0,1,2,3, 謂詞法謂詞法 S= x | x是實(shí)數(shù)，是實(shí)數(shù)，x2 1=0 3元素與集合元素與集合1. 集合的元素具有的性質(zhì)集合的元素具有的性質(zhì) 無序性：元素列出的順序無關(guān)無序性：元素列出的順序無關(guān) 相異性：集合的每個(gè)元素只計(jì)相異性：集合的每個(gè)元素只計(jì) 數(shù)一次數(shù)一次

3、確定性：對(duì)任何元素和集合都確定性：對(duì)任何元素和集合都 能確定這個(gè)元素是否能確定這個(gè)元素是否 為該集合的元素為該集合的元素 任意性：集合的元素也可以是任意性：集合的元素也可以是 集合集合2元素與集合的關(guān)系元素與集合的關(guān)系 隸屬關(guān)系：隸屬關(guān)系： 或者或者 3集合的樹型層次結(jié)構(gòu)集合的樹型層次結(jié)構(gòu)d A , a A4集合與集合集合與集合集合與集合之間的關(guān)系：集合與集合之間的關(guān)系： , =, , , , 定義定義6.1 A B x ( x A x B )定義定義6.2 A = B A B B A定義定義6.3 A B A B A B A B x ( x A x B ) 思考：思考： 和和 的定義的定義

4、注意注意 和和 是不同層次的問題是不同層次的問題5空集、全集和冪集空集、全集和冪集1定義定義6.4 空集空集 ：不含有任何元素的集合：不含有任何元素的集合 實(shí)例：實(shí)例： x | x R x2+1=0 定理定理6.1 空集是任何集合的子集?？占侨魏渭系淖蛹?。 證證 對(duì)于任意集合對(duì)于任意集合A， A x (xx A) T (恒真命題恒真命題) 推論推論 是惟一的是惟一的3. 定義定義6.6 全集全集 E：包含了所有集合的集合：包含了所有集合的集合 全集具有相對(duì)性：與問題有關(guān)，不存在絕對(duì)的全集全集具有相對(duì)性：與問題有關(guān)，不存在絕對(duì)的全集2. 定義定義6.5 冪集冪集：P(A)= x | x A

5、實(shí)例：實(shí)例：P()=, P()=, 計(jì)數(shù)：如果計(jì)數(shù)：如果 |A|=n，則，則 |P(A)|=2n.66.2 集合的運(yùn)算集合的運(yùn)算初級(jí)運(yùn)算初級(jí)運(yùn)算集合的基本運(yùn)算有集合的基本運(yùn)算有定義定義6.7 并并 A B = x | x A x B 交交 A B = x | x A x B 相對(duì)補(bǔ)相對(duì)補(bǔ) A B = x | x A x B定義定義6.8 對(duì)稱差對(duì)稱差 A B = (A B) (B A) 定義定義6.9 絕對(duì)補(bǔ)絕對(duì)補(bǔ) A = E A 7文氏圖文氏圖集合運(yùn)算的表示集合運(yùn)算的表示ABABABABABA BA BABA BA8幾點(diǎn)說明幾點(diǎn)說明l 并和交運(yùn)算可以推廣到有窮個(gè)集合上，即并和交運(yùn)算可以推廣到

6、有窮個(gè)集合上，即A1 A2 An = x | x A1 x A2 x An A1 A2 An = x | x A1 x A2 x Anl A B A B = l A B = A B = A9廣義運(yùn)算廣義運(yùn)算1. 集合的廣義并與廣義交集合的廣義并與廣義交 定義定義6.10 廣義并廣義并 A = x | z ( z A x z ) 廣義交廣義交 A= x | z ( z A x z ) 實(shí)例實(shí)例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a10關(guān)于廣義運(yùn)算的說明關(guān)于廣義運(yùn)算的說明2. 廣義運(yùn)算的性質(zhì)廣義運(yùn)算的性質(zhì) (1) =，無意義無意

7、義 (2) 單元集單元集x的廣義并和廣義交都等于的廣義并和廣義交都等于x (3) 廣義運(yùn)算減少集合的層次（括弧減少一層）廣義運(yùn)算減少集合的層次（括弧減少一層） (4) 廣義運(yùn)算的計(jì)算：一般情況下可以轉(zhuǎn)變成初級(jí)運(yùn)算廣義運(yùn)算的計(jì)算：一般情況下可以轉(zhuǎn)變成初級(jí)運(yùn)算 A1, A2, , An=A1 A2 An A1, A2, , An=A1 A2 An 3. 引入廣義運(yùn)算的意義引入廣義運(yùn)算的意義 可以表示無數(shù)個(gè)集合的并、交運(yùn)算，例如可以表示無數(shù)個(gè)集合的并、交運(yùn)算，例如 x | x R=R 這里的這里的 R 代表實(shí)數(shù)集合代表實(shí)數(shù)集合. 11運(yùn)算的優(yōu)先權(quán)規(guī)定運(yùn)算的優(yōu)先權(quán)規(guī)定1 類運(yùn)算：初級(jí)運(yùn)算類運(yùn)算：初級(jí)運(yùn)

8、算 , , , ， 優(yōu)先順序由括號(hào)確定優(yōu)先順序由括號(hào)確定2 類運(yùn)算：廣義運(yùn)算和類運(yùn)算：廣義運(yùn)算和 運(yùn)算，運(yùn)算， 運(yùn)算由右向左進(jìn)行運(yùn)算由右向左進(jìn)行混合運(yùn)算：混合運(yùn)算：2 類運(yùn)算優(yōu)先于類運(yùn)算優(yōu)先于1 類運(yùn)算類運(yùn)算例例1 A=a,a,b，計(jì)算，計(jì)算A (AA). 解：解： A (AA) = a,b ( a,ba) = (a b) (a b) a) = (a b) (b a) = b12有窮集合元素的計(jì)數(shù)有窮集合元素的計(jì)數(shù)1. 文氏圖法文氏圖法2. 包含排斥原理包含排斥原理定理定理6.2 設(shè)集合設(shè)集合S上定義了上定義了n條性質(zhì)，其中具有第條性質(zhì)，其中具有第 i 條性質(zhì)的條性質(zhì)的元素構(gòu)成子集元素構(gòu)成子集

9、Ai, 那么集合中不具有任何性質(zhì)的元素?cái)?shù)為那么集合中不具有任何性質(zhì)的元素?cái)?shù)為 |.|) 1(.|.|2111121nnnkjikjnjijiniinAAAAAAAAASAAAi 推論推論 S中至少具有一條性質(zhì)的元素?cái)?shù)為中至少具有一條性質(zhì)的元素?cái)?shù)為|)1(|21111121nmnkjikjinjijiniinAAAAAAAAAAAA 13實(shí)例實(shí)例例例2 求求1到到1000之間（包含之間（包含1和和1000在內(nèi)）既不能被在內(nèi)）既不能被5和和6整整除，也不能被除，也不能被8整除的數(shù)有多少個(gè)？整除的數(shù)有多少個(gè)？解解 方法一：文氏圖方法一：文氏圖 定義以下集合：定義以下集合： S= x | x Z 1

10、x 1000 A= x | x S x可被可被5整除整除 B= x | x S x可被可被6整除整除 C= x | x S x可被可被8整除整除 畫出文氏圖，然后填入相應(yīng)的畫出文氏圖，然后填入相應(yīng)的數(shù)字，解得數(shù)字，解得 N=1000(200+100+33+67) =60014實(shí)例實(shí)例方法二方法二 |S| = 1000 |A|= 1000/5 =200, |B|= 1000/6 =166, |C|= 1000/8 =125 |A B| = 1000/lcm(5,6) = 1000/33 = 33 |A C| = 1000/lcm(5,8) = 1000/40 = 25 |B C| = 1000/

11、lcm(6,8) = 1000/24 = 41 |A B C| = 1000/lcm(5,6,8) = 1000/120 = 8 = 1000 (200+166+125)+(33+25+41) 8 = 600 |CBA 156.3 集合恒等式集合恒等式集合算律集合算律1只涉及一個(gè)運(yùn)算的算律：只涉及一個(gè)運(yùn)算的算律： 交換律交換律、結(jié)合律結(jié)合律、冪等律冪等律 交換交換A B=B AA B=B AA B=B A結(jié)合結(jié)合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B C)冪等冪等A A=AA A=A16集合算律集合算律 2涉及兩個(gè)不同運(yùn)算的算律：涉及兩個(gè)不同運(yùn)算的

12、算律： 分配律、吸收律分配律、吸收律 與與 與與 分配分配A (B C)=(A B) (A C)A (B C)=(A B) (A C)A (B C)=(A B) (A C)吸收吸收A (A B)=AA (A B)=A17集合算律集合算律3涉及補(bǔ)運(yùn)算的算律：涉及補(bǔ)運(yùn)算的算律： DM律律，雙重否定律雙重否定律 D.M律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B C)= BC (B C)= BC雙重否定雙重否定A=A18集合算律集合算律4涉及全集和空集的算律：涉及全集和空集的算律： 補(bǔ)元律補(bǔ)元律、零律零律、同一律同一律、否定律否定律E補(bǔ)元律補(bǔ)元律AA=AA=

13、E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=19集合證明題集合證明題證明方法：命題演算法、等式置換法證明方法：命題演算法、等式置換法命題演算證明法的書寫規(guī)范命題演算證明法的書寫規(guī)范 (以下的以下的X和和Y代表集合公式代表集合公式)(1) 證證X Y 任取任取x， x X x Y (2) 證證X=Y 方法一方法一 分別證明分別證明 X Y 和和 Y X 方法二方法二 任取任取x，x X x Y注意：在使用方法二的格式時(shí)，必須保證每步推理都是充注意：在使用方法二的格式時(shí)，必須保證每步推理都是充分必要的分必要的20集合等式的證明集合等式的證明方法一：命題演算法方法一：命題演

14、算法例例3 證明證明A (A B) = A （吸收律）（吸收律）證證 任取任取x, x A (A B) x A x A B x A (x A x B) x A 因此得因此得 A (A B) = A.例例4 證明證明 A B = AB證證 任取任取x, x A B x A x B x A xB x AB 因此得因此得 A B = AB21等式代入法等式代入法方法二：等式置換法方法二：等式置換法例例5 假設(shè)交換律、分配律、同一律、零律已經(jīng)成立，證明吸假設(shè)交換律、分配律、同一律、零律已經(jīng)成立，證明吸 收律收律. 證證 A (A B) = (A E) (A B) （同一律）（同一律） = A (E B

15、) （分配律）（分配律） = A (B E) （交換律）（交換律） = A E （零律）（零律） = A （同一律）（同一律）22包含等價(jià)條件的證明包含等價(jià)條件的證明例例6 證明證明A B AB=B A B=A A B= 證明思路：證明思路：l 確定問題中含有的命題：本題含有命題確定問題中含有的命題：本題含有命題 , , , l 確定命題間的關(guān)系（哪些命題是已知條件、哪些命題是要確定命題間的關(guān)系（哪些命題是已知條件、哪些命題是要證明的結(jié)論）：本題中每個(gè)命題都可以作為已知條件，每證明的結(jié)論）：本題中每個(gè)命題都可以作為已知條件，每個(gè)命題都是要證明的結(jié)論個(gè)命題都是要證明的結(jié)論l 確定證明順序：確定證

16、明順序：， l 按照順序依次完成每個(gè)證明（證明集合相等或者包含）按照順序依次完成每個(gè)證明（證明集合相等或者包含） 23證明證明證明證明A B A B=B A B=A A B= 證證 顯然顯然B A B，下面證明，下面證明A B B. 任取任取x， x A B x A x B x B x B x B 因此有因此有A B B. 綜合上述綜合上述得證得證. A=A (A B) A=A B (由由知知A B=B，將，將A B用用B代代入入) 24假設(shè)假設(shè)A B, 即即 x A B，那么知道，那么知道x A且且x B. 而而 x B x A B 從而與從而與A B=A矛盾矛盾.假設(shè)假設(shè)A B不成立，那么

17、不成立，那么 x(x A x B) x A B A B與條件與條件矛盾矛盾. 證明證明25第六章第六章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 集合的兩種表示法集合的兩種表示法l 集合與元素之間的隸屬關(guān)系、集合之間的包含關(guān)系的區(qū)集合與元素之間的隸屬關(guān)系、集合之間的包含關(guān)系的區(qū)別與聯(lián)系別與聯(lián)系l 特殊集合：空集、全集、冪集特殊集合：空集、全集、冪集l 文氏圖及有窮集合的計(jì)數(shù)文氏圖及有窮集合的計(jì)數(shù)l 集合的集合的 , , , , 等運(yùn)算以及廣義等運(yùn)算以及廣義 , 運(yùn)算運(yùn)算l 集合運(yùn)算的算律及其應(yīng)用集合運(yùn)算的算律及其應(yīng)用26基本要求基本要求l 熟練掌握集合的兩種表示法熟練掌握集合的兩種表示法l 能夠判別元素

18、是否屬于給定的集合能夠判別元素是否屬于給定的集合l 能夠判別兩個(gè)集合之間是否存在包含、相等、真包含等關(guān)能夠判別兩個(gè)集合之間是否存在包含、相等、真包含等關(guān)系系l 熟練掌握集合的基本運(yùn)算（普通運(yùn)算和廣義運(yùn)算）熟練掌握集合的基本運(yùn)算（普通運(yùn)算和廣義運(yùn)算）l 掌握證明集合等式或者包含關(guān)系的基本方法掌握證明集合等式或者包含關(guān)系的基本方法27練習(xí)練習(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 解解

19、 (1)、(3)、(4)、(5)、(6)、(7)為真，其余為假為真，其余為假.28方法分析方法分析(1) 判斷元素判斷元素a與集合與集合A的隸屬關(guān)系是否成立基本方法：的隸屬關(guān)系是否成立基本方法： 把把 a 作為整體檢查它在作為整體檢查它在A中是否出現(xiàn)，注意這里的中是否出現(xiàn)，注意這里的 a 可可 能是集合表達(dá)式能是集合表達(dá)式. (2) 判斷判斷A B的四種方法的四種方法l 若若A,B是用枚舉方式定義的，依次檢查是用枚舉方式定義的，依次檢查A的每個(gè)元素是否的每個(gè)元素是否在在B中出現(xiàn)中出現(xiàn). l 若若A,B是謂詞法定義的，且是謂詞法定義的，且A, B中元素性質(zhì)分別為中元素性質(zhì)分別為P和和Q, 那么那

20、么“若若P則則Q”意味意味 A B，“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”意味意味=l 通過集合運(yùn)算判斷通過集合運(yùn)算判斷A B，即，即A B = B, A B = A, A B = 三個(gè)等式中有一個(gè)為真三個(gè)等式中有一個(gè)為真.l 通過文氏圖判斷集合的包含（注意這里是判斷，而不是通過文氏圖判斷集合的包含（注意這里是判斷，而不是證明證明29練習(xí)練習(xí)22設(shè)設(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è)集合相等？如果是，又與哪個(gè)集合相等？果是，又與

21、哪個(gè)集合相等？ （1）若）若 X S5= （2）若）若 X S4但但 X S2= （3）若）若 X S1且且 X S3 （4）若）若 X S3= （5）若）若 X S3 且且 X S130解答解答解解(1) 和和S5不交的子集不含有不交的子集不含有3和和5，因此，因此 X=S2. (2) S4的子集只能是的子集只能是S4和和S5. 由于與由于與S2不交，不能含有偶數(shù)，不交，不能含有偶數(shù)， 因此因此 X=S5.(3) S1, S2, S3, S4和和S5都是都是S1的子集，不包含在的子集，不包含在S3的子集含有的子集含有 偶數(shù)，因此偶數(shù)，因此 X=S1, S2或或S4. (4) X S3=意味著

22、意味著 X是是S3的子集，因此的子集，因此 X=S3或或 S5.(5) 由于由于S3是是S1的子集，因此這樣的的子集，因此這樣的X不存在不存在.31練習(xí)練習(xí)33. 判斷以下命題的真假，并說明理由判斷以下命題的真假，并說明理由. （1）A B = A B= （2）A (B C) = (A B) (A C) （3）A A = A （4）如果）如果A B = B，則，則A = E. （5）A = x x，則，則 x A且且x A. 32解題思路解題思路l 先將等式化簡或恒等變形先將等式化簡或恒等變形.l 查找集合運(yùn)算的相關(guān)的算律，如果與算律相符，結(jié)果為真查找集合運(yùn)算的相關(guān)的算律，如果與算律相符，結(jié)果

23、為真.l 注意以下兩個(gè)重要的充要條件注意以下兩個(gè)重要的充要條件 A B = A A B = A B = A B A B = B A B = A 如果與條件相符，則命題為真如果與條件相符，則命題為真.l 如果不符合算律，也不符合上述條件，可以用文氏圖表示如果不符合算律，也不符合上述條件，可以用文氏圖表示集合，看看命題是否成立集合，看看命題是否成立.如果成立，再給出證明如果成立，再給出證明.l 試著舉出反例，證明命題為假試著舉出反例，證明命題為假.33解答解答解解(1) B=是是A B=A的充分條件，但不是必要條件的充分條件，但不是必要條件. 當(dāng)當(dāng)B不空但不空但 是與是與A不交時(shí)也有不交時(shí)也有A

24、B=A. (2) 這是這是DM律，命題為真律，命題為真.(3) 不符合算律，反例如下：不符合算律，反例如下： A=1，A A=，但是，但是A.(4) 命題不為真命題不為真. A B=B的充分必要條件是的充分必要條件是 B A，不是，不是A=E. (5) 命題為真，因?yàn)槊}為真，因?yàn)?x 既是既是 A 的元素，也是的元素，也是 A 的子集的子集 34練習(xí)練習(xí)44證明證明 A B = A C A B = A C B = C解題思路解題思路l 分析命題：含有分析命題：含有3 3個(gè)命題：個(gè)命題： A B = A C , A B = A C, B = C l 證明要求證明要求 前提：命題前提：命題和和

25、結(jié)論：命題結(jié)論：命題 l 證明方法：證明方法： 恒等式代入恒等式代入 反證法反證法 利用已知等式通過運(yùn)算得到新的等式利用已知等式通過運(yùn)算得到新的等式35解答解答方法一：恒等變形法方法一：恒等變形法 B = B (B A) = B (A B) = B (A C) = (B A) (B C) = (A C) (B C) = (A B) C = (A C) C = C 方法二：反證法方法二：反證法.假設(shè)假設(shè) B C，則存在，則存在 x (x B且且x C), 或存在或存在 x (x C且且x B). 不妨設(shè)為前者不妨設(shè)為前者. 若若x屬于屬于A，則，則x屬于屬于A B 但但x不屬于不屬于A C，與已

26、知矛盾；，與已知矛盾；若若x不屬于不屬于A，則，則x屬于屬于A B但但x不屬于不屬于A C，也與已知矛盾，也與已知矛盾. 36解答解答方法三：利用已知等式通過運(yùn)算得到新的等式方法三：利用已知等式通過運(yùn)算得到新的等式.由已知等式由已知等式和和可以得到可以得到 (A B) (A B) = (A C) (A C)即即 A B = A C 從而有從而有 A (A B) =A (A C) 根據(jù)結(jié)合律得根據(jù)結(jié)合律得 (A A) B = (A A) C 由于由于A A = , 化簡上式得化簡上式得B = C. 37練習(xí)練習(xí)55設(shè)設(shè)A,B為集合，試確定下列各式成立的充分必要條件：為集合，試確定下列各式成立的充分必要條件：(1) A B=B(2) A B=B A(3) A B=A B(