離散數(shù)學課件ch6集合論

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

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

3、次 確定性：對任何元素和集合都確定性：對任何元素和集合都 能確定這個元素是否能確定這個元素是否 為該集合的元素為該集合的元素 任意性：集合的元素也可以是任意性：集合的元素也可以是 集合集合2元素與集合的關系元素與集合的關系 隸屬關系：隸屬關系： 或者或者 3集合的樹型層次結(jié)構(gòu)集合的樹型層次結(jié)構(gòu)d A , a A 4集合與集合集合與集合集合與集合之間的關系：集合與集合之間的關系： , =, , , , 定義定義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 空集空集 ：不含有任何元素的集合：不含有任何元素的集合 實例：實例： x | x R x2+1=0 定理定理6.1 空集是任何集合的子集?？占侨魏渭系淖蛹?證證 對于任意集合對于任意集合A， A x (xx A) T (恒真命題恒真命題) 推論推論 是惟一的是惟一的3. 定義定義6.6 全集全集 E：包含了所有集合的集合：包含了所有集合的集合 全集具有相對性：與問題有關，不存在絕對的全集全集具有相對性：與問題有關，不存在絕對的全集2. 定義定義6.5 冪集冪集：P(A)= x |

5、x A 實例：實例：P()=, P()=, 6含有含有n個元素的集合簡稱個元素的集合簡稱n元集元集，它的含有，它的含有m(mn)個元素個元素的子集叫做它的的子集叫做它的m元子集元子集。例例 A1,2,3，將，將A的子集分類：的子集分類：0 0元子集（空集）元子集（空集）1 1元子集（單元集）元子集（單元集）11，22，332 2元子集元子集1,21,2，1,31,3，2,32,33 3元子集元子集1,2,31,2,3 7一般地說，對于一般地說，對于n元集元集A，它的，它的0元子集有元子集有 個，個，1元子集有元子集有 個，個，m元子集有元子集有 個，個，n元子集有元子集有 個。子集總數(shù)為個。子

6、集總數(shù)為n nn nn n2 2n n1 1n n0 0n n2 2C CC CC CC C0 0n nC C1 1n nC Cm mn nC Cn nn nC C若若A A是是n n元集，則元集，則P(A)P(A)有有 2 2n n 個元素。個元素。 86.2 集合的運算集合的運算初級運算初級運算集合的基本運算有集合的基本運算有定義定義6.7 并并 A B = x | x A x B 交交 A B = x | x A x B 相對補相對補 A B = x | x A x B定義定義6.8 對稱差對稱差 A B = (A B) (B A) 定義定義6.9 絕對補絕對補 A = E A 9文氏圖

7、文氏圖集合運算的表示集合運算的表示ABABABABABA BA BABA BA 10幾點說明幾點說明l 并和交運算可以推廣到有窮個集合上，即并和交運算可以推廣到有窮個集合上，即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 = A 11廣義運算廣義運算1. 集合的廣義并與廣義交集合的廣義并與廣義交 定義定義6.10 廣義并廣義并 A = x | z ( z A x z ) 廣義交廣義交 A= x | z ( z A x z ) 實例實例 1, 1,2, 1,2,3=1,2,3

8、1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a 12關于廣義運算的說明關于廣義運算的說明2. 廣義運算的性質(zhì)廣義運算的性質(zhì) (1) =，無意義無意義 (2) 單元集單元集x的廣義并和廣義交都等于的廣義并和廣義交都等于x (3) 廣義運算減少集合的層次（括弧減少一層）廣義運算減少集合的層次（括弧減少一層） (4) 廣義運算的計算：一般情況下可以轉(zhuǎn)變成初級運算廣義運算的計算：一般情況下可以轉(zhuǎn)變成初級運算 A1, A2, , An=A1 A2 An A1, A2, , An=A1 A2 An 3. 引入廣義運算的意義引入廣義運算的意義 可以表示無數(shù)個集合的并、交運算，例如可以表示

9、無數(shù)個集合的并、交運算，例如 x | x R=R 這里的這里的 R 代表實數(shù)集合代表實數(shù)集合. 13運算的優(yōu)先權(quán)規(guī)定運算的優(yōu)先權(quán)規(guī)定1 類運算：初級運算類運算：初級運算 , , , ， 優(yōu)先順序由括號確定優(yōu)先順序由括號確定2 類運算：廣義運算和類運算：廣義運算和 運算，運算， 運算由右向左進行運算由右向左進行混合運算：混合運算：2 類運算優(yōu)先于類運算優(yōu)先于1 類運算類運算例例1 A=a,a,b，計算，計算A (AA). 解：解： A (AA) = a,b ( a,ba) = (a b) (a b) a) = (a b) (b a) = b 14有窮集合元素的計數(shù)有窮集合元素的計數(shù)1. 文氏圖法

10、文氏圖法2. 包含排斥原理包含排斥原理定理定理6.2 設集合設集合S上定義了上定義了n條性質(zhì)，其中具有第條性質(zhì)，其中具有第 i 條性質(zhì)條性質(zhì)的的元素構(gòu)成子集元素構(gòu)成子集Ai, 那么集合中不具有任何性質(zhì)的元素數(shù)為那么集合中不具有任何性質(zhì)的元素數(shù)為 |.|) 1(.|.|2111121nnnkjikjnjijiniinAAAAAAAAASAAAi 推論推論 S中至少具有一條性質(zhì)的元素數(shù)為中至少具有一條性質(zhì)的元素數(shù)為|)1(|21111121nmnkjikjinjijiniinAAAAAAAAAAAA 15實例實例例例2 求求1到到1000之間（包含之間（包含1和和1000在內(nèi)）既不能被在內(nèi)）既不能

11、被5和和6整整除，也不能被除，也不能被8整除的數(shù)有多少個？整除的數(shù)有多少個？解解 方法一：文氏圖方法一：文氏圖 定義以下集合：定義以下集合： S= x | x Z 1 x 1000 A= x | x S x可被可被5整除整除 B= x | x S x可被可被6整除整除 C= x | x S x可被可被8整除整除 畫出文氏圖，然后填入相應的畫出文氏圖，然后填入相應的數(shù)字，解得數(shù)字，解得 N=1000(200+100+33+67) =600 16實例實例方法二方法二 |S| = 1000 |A|= 1000/5 =200, |B|= 1000/6 =166, |C|= 1000/8 =125 |A

12、 B| = 1000/lcm(5,6) = 1000/33 = 33 |A C| = 1000/lcm(5,8) = 1000/40 = 25 |B C| = 1000/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 176.3 集合恒等式集合恒等式集合算律集合算律1只涉及一個運算的算律：只涉及一個運算的算律： 交換律交換律、結(jié)合律結(jié)合律、冪等律冪等律 交換交換A B=B AA B=B AA B=B A結(jié)合結(jié)合(A B) C

13、=A (B C)(A B) C=A (B C)(A B) C=A (B C)冪等冪等A A=AA A=A 18集合算律集合算律 2涉及兩個不同運算的算律：涉及兩個不同運算的算律： 分配律、吸收律分配律、吸收律 與與 與與 分配分配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)=A 19集合算律集合算律3涉及補運算的算律：涉及補運算的算律： DM律律，雙重否定律雙重否定律 D.M律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B C)= BC (B C)

14、= BC雙重否定雙重否定A=A 20集合算律集合算律4涉及全集和空集的算律：涉及全集和空集的算律： 補元律補元律、零律零律、同一律同一律、否定律否定律E補元律補元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E= 21集合證明題集合證明題證明方法：命題演算法、等式置換法證明方法：命題演算法、等式置換法命題演算證明法的書寫規(guī)范命題演算證明法的書寫規(guī)范 (以下的以下的X和和Y代表集合公式代表集合公式)(1) 證證X Y 任取任取x， x X x Y (2) 證證X=Y 方法一方法一 分別證明分別證明 X Y 和和 Y X 方法二方法二 任取任取x，x X x Y注

15、意：在使用方法二的格式時，必須保證每步推理都是充注意：在使用方法二的格式時，必須保證每步推理都是充分必要的分必要的 22集合等式的證明集合等式的證明方法一：命題演算法方法一：命題演算法例例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 = AB 23等式代入法等式代入法方法二：等式置換法方法二：等式置換法例例5 假設交換律、分配

16、律、同一律、零律已經(jīng)成立，證明假設交換律、分配律、同一律、零律已經(jīng)成立，證明吸收律吸收律. 證證 A (A B) = (A E) (A B) （同一律）（同一律） = A (E B) （分配律）（分配律） = A (B E) （交換律）（交換律） = A E （零律）（零律） = A （同一律）（同一律） 24包含等價條件的證明包含等價條件的證明例例6 證明證明A B A B=B A B=A A B= 證明思路：證明思路：l 確定問題中含有的命題：本題含有命題確定問題中含有的命題：本題含有命題 , , , l 確定命題間的關系（哪些命題是已知條件、哪些命題是要確定命題間的關系（哪些命題是已知條

17、件、哪些命題是要證明的結(jié)論）：本題中每個命題都可以作為已知條件，每證明的結(jié)論）：本題中每個命題都可以作為已知條件，每個命題都是要證明的結(jié)論個命題都是要證明的結(jié)論l 確定證明順序：確定證明順序：， l 按照順序依次完成每個證明（證明集合相等或者包含）按照順序依次完成每個證明（證明集合相等或者包含） 25證明證明證明證明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

18、 B用用B代入代入) 26證明證明A B A B=B A B=A A B= 假設假設A B, 即即 x A B，那么知道，那么知道x A且且x B. 而而 x B x A B 從而與從而與A B=A矛盾矛盾.假設假設A B不成立，那么不成立，那么 x(x A x B) x A B A B與條件矛盾與條件矛盾. 證明證明 27第六章第六章 習題課習題課主要內(nèi)容主要內(nèi)容l 集合的兩種表示法集合的兩種表示法l 集合與元素之間的隸屬關系、集合之間的包含關系的區(qū)集合與元素之間的隸屬關系、集合之間的包含關系的區(qū)別與聯(lián)系別與聯(lián)系l 特殊集合：空集、全集、冪集特殊集合：空集、全集、冪集l 文氏圖及有窮集合的計

19、數(shù)文氏圖及有窮集合的計數(shù)l 集合的集合的 , , , , 等運算以及廣義等運算以及廣義 , 運算運算l 集合運算的算律及其應用集合運算的算律及其應用 28冪集冪集 ( power set ) 對于對于n元集元集A，它的，它的0元子集有元子集有 個，個，1元子集有元子集有 個，個，m元子集有元子集有 個，個，n元子集有元子集有 個。子集總數(shù)為個。子集總數(shù)為n nn nn n2 2n n1 1n n0 0n n2 2C CC CC CC C0 0n nC C1 1n nC Cm mn nC Cn nn nC C設設A A為集合，把為集合，把A A的全部子集構(gòu)成的集合叫做的全部子集構(gòu)成的集合叫做A

20、A的冪集，記作的冪集，記作P(A)(P(A)(或或PAPA，2 2A A) )。冪集的符號化表示為冪集的符號化表示為P(A)P(A)x | xx | x A A 若若A A是是n n元集，則元集，則P(A)P(A)有有 2 2n n 個元素。個元素。 29對稱差對稱差設設A，B為集合，為集合，A與與B的的對稱差集對稱差集 A B定義為：定義為：A B(AB)(BA) 對稱差運算的另一種定義是對稱差運算的另一種定義是A B(AB)(AB) 例如例如: Aa，b，c，Bb，d，則則 A Ba，c，d A BB A (A B) CA (B C)AA A AA BA C BC 30集合恒等式集合恒等式

21、 下面的恒等式給出了集合運算的主要算律，其中下面的恒等式給出了集合運算的主要算律，其中A，B，C代代表任意集合。表任意集合。冪等律冪等律 AAA (6.1) AAA (6.2)結(jié)合律結(jié)合律 (AB)CA(BC) (6.3) (AB)CA(BC) (6.4)交換律交換律 ABBA (6.5) ABBA (6.6)分配律分配律 A(BC)(AB)(AC) (6.7) A(BC)(AB)(AC) (6.8)同一律同一律 AA (6.9) AEA (6.10) 31集合恒等式集合恒等式零律零律 AEE (6.11) A (6.12)排中律排中律 AAE (6.13)矛盾律矛盾律 AA (6.14)吸收

22、律吸收律 A(AB)A (6.15) A(AB)A (6.16)德摩根律德摩根律 A(BC)(AB)(AC)(6.17) A(BC)(AB)(AC)(6.18)(BC)BC (6.19)(BC)BC (6.20)E (6.21)E (6.22)雙重否定律雙重否定律 (A)A (6.23) 32集合運算性質(zhì)的一些重要結(jié)果集合運算性質(zhì)的一些重要結(jié)果AB A，AB B(6.24)A AB，B AB (6.25)AB A(6.26)ABAB (6.27)ABB A B ABA AB (6.28) A BB A (6.29)(A B) CA (B C) (6.30)AA (6.31)A A (6.32)

23、A BA C BC (6.33) 33 已知已知 A BA C，證明，證明BC。證明證明 已知已知 A BA C，所以所以 A (A B)A (A C) (A A) B(A A) C (由式由式6.30) BC (由式由式6.32) BC (由式由式6.29) BC (由式由式6.31) 34對偶對偶(dual)原理原理對偶對偶(dual)式：式：一個集合表達式，如果只含有一個集合表達式，如果只含有、E、 、 ，那么同時把，那么同時把與與互換，把互換，把與與E互換，把互換，把 與與 互換互換，得到式子，得到式子稱為原式的對偶式。稱為原式的對偶式。對歐原理對歐原理：對偶式同真假?；蛘哒f，集合恒等

24、式：對偶式同真假?；蛘哒f，集合恒等式的對偶式還是恒等式。的對偶式還是恒等式。 35基本要求基本要求l 熟練掌握集合的兩種表示法熟練掌握集合的兩種表示法l 能夠判別元素是否屬于給定的集合能夠判別元素是否屬于給定的集合l 能夠判別兩個集合之間是否存在包含、相等、真包含等關能夠判別兩個集合之間是否存在包含、相等、真包含等關系系l 熟練掌握集合的基本運算（普通運算和廣義運算）熟練掌握集合的基本運算（普通運算和廣義運算）l 掌握證明集合等式或者包含關系的基本方法掌握證明集合等式或者包含關系的基本方法 36集合恒等式的證明方法集合恒等式的證明方法邏輯演算法邏輯演算法利用利用邏輯等值式邏輯等值式和和推理規(guī)則

25、推理規(guī)則集合演算法集合演算法利用利用集合恒等式集合恒等式和和已知結(jié)論已知結(jié)論 37邏輯演算法的格式邏輯演算法的格式題目：題目：AB證明：證明： x x， x xA x xB所以所以 AB或證或證 P Q Q P 題目：題目：A A B B證明：證明： x x， xAxA xBxB所以所以 A A B B 38集合演算法的格式集合演算法的格式題目：題目：AB證明：證明： A B所以所以 AB題目：題目：A A B B證明：證明：A A B B所以所以 A A B B 39練習練習1 1判斷下列命題是否為真判斷下列命題是否為真 (1) (2) (3) (4) (5) a, b a, b, c, a

26、, 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)為真，其余為假為真，其余為假. 40練習練習22設設 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中某個集合相等？如中某個集合相等？如果是，又與哪個集合相等？果是，又與哪個集合相等？ （1）若）若 X S5= （2）若）若 X S4但但 X S2= （3）若）若

27、X S1且且 X S3 （4）若）若 X S3= （5）若）若 X S3 且且 X S1 41解答解答解解(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=意味著意味著 X是是S3的子集，因此的子集，因此 X=S3或或 S5.(5) 由于由于S3是是S1的

28、子集，因此這樣的的子集，因此這樣的X不存在不存在. 42練習練習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. 43解題思路解題思路l 先將等式化簡或恒等變形先將等式化簡或恒等變形.l 查找集合運算的相關的算律，如果與算律相符，結(jié)果為真查找集合運算的相關的算律，如果與算律相符，結(jié)果為真.l 注意以下兩個重要的充要條件注意以下兩個重要的充要條件 A B = A A B =

29、A B = A B A B = B A B = A 如果與條件相符，則命題為真如果與條件相符，則命題為真.l 如果不符合算律，也不符合上述條件，可以用文氏圖表示如果不符合算律，也不符合上述條件，可以用文氏圖表示集合，看看命題是否成立集合，看看命題是否成立.如果成立，再給出證明如果成立，再給出證明.l 試著舉出反例，證明命題為假試著舉出反例，證明命題為假. 44解答解答解解(1)A B = A B=是假命題，是假命題， B=是是A B=A的充分條件，但不是必要條件的充分條件，但不是必要條件. 當當B不空但不空但 是與是與A不交時也有不交時也有A B=A. 如當如當A=1， A=2時。時。(2)

30、A (B C) = (A B) (A C)是是DM律，命題為真律，命題為真.(3) A A = A是假命題，反例如下：是假命題，反例如下： A=1，A A=，但是，但是A.(4)如果如果A B = B，則，則A = E是假命題是假命題. A B=B的充分必要條的充分必要條件是件是 B A，不是，不是A=E. (5) A = x x，則，則 x A且且x A命題為真，因為命題為真，因為 x 既是既是 A 的的元素，也是元素，也是 A 的子集的子集 45練習練習44證明證明 A B = A C A B = A C B = C解題思路解題思路l 分析命題：含有分析命題：含有3 3個命題：個命題： A

31、 B = A C , A B = A C, B = C l 證明要求證明要求 前提：命題和前提：命題和 結(jié)論：命題結(jié)論：命題 l 證明方法：證明方法： 恒等式代入恒等式代入 反證法反證法 利用已知等式通過運算得到新的等式利用已知等式通過運算得到新的等式 46解答解答方法一：恒等變形法方法一：恒等變形法 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 證明證明 A B = A C A B = A C B = C 47解答解答方法二：反證法方法二：反證法.假設假設 B C，則存在，則存在 x (x B且且x C), 或存在或存在 x (x C且且x B). 不妨設為前者不妨設為前者. 若若x屬于屬于A，則，則x屬于屬于A B 但但x不屬于不屬于A C，與已知矛盾；，與已知矛盾；若若x不屬于不屬于A，則，則x屬于屬于A B但但x不屬于不屬于A C，也與已知矛盾，也與已知矛盾. 證明證明 A B = A C A B = A C B = C 48解答解答A B = A C , A B = A C, B = C 方法三：利用已知等式通過運算得到新的等式方法三：利用已知等式通過運算得到新的等式.由已知等式和可以得到由已知等式和可以得到 (A B) (A B) = (A