離散數(shù)學(xué)離散第1章集合論

1、廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院離散數(shù)學(xué)離散數(shù)學(xué)離離 散散 數(shù)數(shù) 學(xué)學(xué)蔡瑞初蔡瑞初20222022年年3 3月月11 11日星期五日星期五22022-3-112022-3-11關(guān)于我關(guān)于我蔡瑞初蔡瑞初研究方向：搜索引擎、數(shù)據(jù)挖掘、生物信息學(xué)研究方向：搜索引擎、數(shù)據(jù)挖掘、生物信息學(xué)實(shí)驗(yàn)室：實(shí)驗(yàn)室：321321實(shí)驗(yàn)室實(shí)驗(yàn)室EmailEmail：32022-3-112022-3-11關(guān)于你們關(guān)于你們態(tài)度決定一切！態(tài)度決定一切！精進(jìn)、持戒、忍辱、布施、禪定、智慧42022-3-112022-3-11關(guān)于離散數(shù)學(xué)關(guān)于離散數(shù)學(xué)一切計(jì)算機(jī)學(xué)科的基礎(chǔ)！一切計(jì)算機(jī)學(xué)科的基礎(chǔ)！哲學(xué)哲學(xué)數(shù)學(xué)數(shù)學(xué)語言學(xué)語

2、言學(xué)。離散離散算法算法網(wǎng)絡(luò)網(wǎng)絡(luò)。We are We are here!here!52022-3-112022-3-11關(guān)于成績關(guān)于成績 出勤（出勤（10-15%10-15%）考試考試 + + 態(tài)度態(tài)度70%-80% 70%-80% 作業(yè)（作業(yè)（10-15%10-15%） 62022-3-112022-3-11第一篇第一篇 預(yù)備知識預(yù)備知識第一章第一章 集合論集合論72022-3-112022-3-111.0 1.0 內(nèi)容提要內(nèi)容提要集合的概念集合的概念1集合的表示方法集合的表示方法2集合間的關(guān)系集合間的關(guān)系3集合的運(yùn)算集合的運(yùn)算4無限集合無限集合5集合的概念集合的概念1集合的表示方法集合的表示

3、方法2特殊集合特殊集合582022-3-112022-3-111.1 1.1 本章學(xué)習(xí)要求本章學(xué)習(xí)要求重點(diǎn)掌握重點(diǎn)掌握一般掌握一般掌握了解了解11 1 集合的概念集合的概念及集合間關(guān)系及集合間關(guān)系2 2 集合的表示集合的表示3 3 集合運(yùn)算及集合運(yùn)算及定律定律4 4 冪集冪集P(A)P(A) 31 1 集合的遞歸集合的遞歸指定法表示指定法表示2 2 了解無限集了解無限集的基本概念的基本概念21 1 集合的歸納集合的歸納法表示法表示2 2 集合的對稱集合的對稱差運(yùn)算差運(yùn)算 92022-3-112022-3-111.2 1.2 集合集合一、集合的概念一、集合的概念集合集合（SETSET）由指定范圍

4、內(nèi)的某些特定對象由指定范圍內(nèi)的某些特定對象聚集在一起構(gòu)成。聚集在一起構(gòu)成。指定范圍內(nèi)的每一個(gè)對象稱為這個(gè)指定范圍內(nèi)的每一個(gè)對象稱為這個(gè)集合的元素集合的元素(element)(element)中國中國所有真皮沙發(fā)所有真皮沙發(fā)的聚集的聚集指定指定范圍范圍特定對特定對象象102022-3-112022-3-11二、集合的記法二、集合的記法通常用帶通常用帶( (不帶不帶) )標(biāo)號的大寫字母標(biāo)號的大寫字母A A、B B、C C、.、A A1 1、 B B1 1 、C C1 1 、.、X X、Y Y、Z Z、.表示表示集合集合； 通常用帶（不帶）標(biāo)號的小寫字母通常用帶（不帶）標(biāo)號的小寫字母a a、b b、

5、c c、.、a a1 1、 b b1 1 、c c1 1 、.、x x、y y、z z、.表示表示元素元素。112022-3-112022-3-11固定的符號固定的符號0, 1, 2, 自然數(shù)集合自然數(shù)集合N, -2, -1, 0, 1, 2, 整數(shù)集合整數(shù)集合 Zp/q,p,q是整數(shù)，且是整數(shù)，且q0 有理數(shù)集合有理數(shù)集合 Q 實(shí)數(shù)集合實(shí)數(shù)集合 R復(fù)數(shù)集合復(fù)數(shù)集合 C122022-3-112022-3-111.2.1 1.2.1 集合的表示方法集合的表示方法 集合是由它包含的元素完全確定的，為了表示集合是由它包含的元素完全確定的，為了表示一個(gè)集合，通常有：一個(gè)集合，通常有： 枚舉法枚舉法 隱

6、式法（敘述法）隱式法（敘述法） 歸納法歸納法 遞歸指定遞歸指定文氏圖文氏圖132022-3-112022-3-111 1、枚舉法（顯示法）、枚舉法（顯示法）-列出集合中全部元素或部分元素的方法叫列出集合中全部元素或部分元素的方法叫枚舉法枚舉法例例1.2.11.2.1適用場景：適用場景：u一個(gè)集合僅含有限個(gè)元素一個(gè)集合僅含有限個(gè)元素u一個(gè)集合的元素之間有明顯關(guān)系一個(gè)集合的元素之間有明顯關(guān)系 142022-3-112022-3-11枚舉法的優(yōu)缺點(diǎn)枚舉法的優(yōu)缺點(diǎn)是一種是一種顯式表示法顯式表示法優(yōu)點(diǎn)優(yōu)點(diǎn)：具有：具有透明性透明性缺點(diǎn)缺點(diǎn)：在表示具有某種特性的集合或集合中元：在表示具有某種特性的集合或集合

7、中元素過多時(shí)受到了一定的素過多時(shí)受到了一定的局限局限，而且，從計(jì)算機(jī)，而且，從計(jì)算機(jī)的角度看，顯式法是一種的角度看，顯式法是一種“靜態(tài)靜態(tài)”表示法，如表示法，如果一下子將這么多的果一下子將這么多的“數(shù)據(jù)數(shù)據(jù)”輸入到計(jì)算機(jī)中輸入到計(jì)算機(jī)中去，那將占據(jù)大量的去，那將占據(jù)大量的“內(nèi)存內(nèi)存”。152022-3-112022-3-112 2、隱式法（敘述法）、隱式法（敘述法）通過刻畫集合中通過刻畫集合中元素所具備的某種特性元素所具備的某種特性來表示集來表示集合的方法稱為敘述法（隱式法）合的方法稱為敘述法（隱式法）一般表示方法：一般表示方法：P Px|x|P(x)P(x) 適用場景：適用場景：一個(gè)集合含有

8、很多或無窮多個(gè)元素；一個(gè)集合含有很多或無窮多個(gè)元素；一個(gè)集合的元素之間有容易刻畫的共同特征一個(gè)集合的元素之間有容易刻畫的共同特征其其突出優(yōu)點(diǎn)突出優(yōu)點(diǎn)是原則上不要求列出集合中全部元素，是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性。而只要給出該集合中元素的特性。代表元代表元X X所具有的所具有的性質(zhì)性質(zhì)p p162022-3-112022-3-11例例1.2.21.2.2（1 1）A = x|xA = x|x是是“discrete mathematicsdiscrete mathematics”中中的所有字母的所有字母 ；（2 2）Z = x|xZ = x|x是一個(gè)整數(shù)是一個(gè)整數(shù)

9、 ； （3 3）S = x|xS = x|x是整數(shù)，并且是整數(shù)，并且x x2 21 = 01 = 0； （4 4）Q Q+ + = x|x = x|x是一個(gè)正有理數(shù)是一個(gè)正有理數(shù) 。172022-3-112022-3-113 3、歸納法、歸納法歸納法是通過歸納定義集合，主要由三部分組成：歸納法是通過歸納定義集合，主要由三部分組成：第一部分：第一部分：基礎(chǔ)?；A(chǔ)。指出某些最基本的元素屬于某集指出某些最基本的元素屬于某集合；合；第二部分：第二部分：歸納。歸納。指出由基本元素造出新元素的方指出由基本元素造出新元素的方法；法；第三部分：第三部分：極小性。極小性。指出該集合的界限。指出該集合的界限。注意

10、：第一部分注意：第一部分和和第二部分第二部分指出一個(gè)集合指出一個(gè)集合至少包括至少包括的元素的元素，第三部分第三部分指出一個(gè)集合指出一個(gè)集合至多要包含的元素至多要包含的元素182022-3-112022-3-11例例1.2.31.2.3集合集合A A按如下方式定義：按如下方式定義：（1 1）0 0和和1 1都是都是A A中的元素；中的元素；（2 2）如果）如果a, ba, b是是A A中的元素，則中的元素，則ab, baab, ba也是也是A A中的中的元素；元素；（3 3）有限次使用）有限次使用(1)(1)、(2)(2)后所得到的字符串都是后所得到的字符串都是A A中的元素。中的元素。試指出其

11、定義方式。并舉出集合試指出其定義方式。并舉出集合A A中的中的3 3個(gè)元素個(gè)元素192022-3-112022-3-114 4、遞歸指定集合、遞歸指定集合通過通過計(jì)算規(guī)則計(jì)算規(guī)則定義集合中的元素定義集合中的元素例例1.2.41.2.4 設(shè)設(shè) a a0 0 1 1， a ai+1 i+1 2a2ai i （i i 0 0） 定義定義S Saa0 0 ，a a1 1 ，a a2 2 ，. aak k | k| k 0 0 ，試寫出集合試寫出集合S S中的所有元素。中的所有元素。 202022-3-112022-3-115 5、文氏圖解法、文氏圖解法 文氏圖解法文氏圖解法是一種利用平面上點(diǎn)的集合作成

12、的是一種利用平面上點(diǎn)的集合作成的對集合的圖解。一般用平面上的對集合的圖解。一般用平面上的圓形或方形圓形或方形表示表示一個(gè)集合。一個(gè)集合。 AA212022-3-112022-3-111.2.2 1.2.2 集合與元素的關(guān)系集合與元素的關(guān)系元素與集合之間的元素與集合之間的“屬于關(guān)系屬于關(guān)系”是是“明確明確”的。的。 對某個(gè)集合對某個(gè)集合A A和元素和元素a a來說，來說，a a屬于集合屬于集合A A，記為記為a a A A或者或者a a不屬于集合不屬于集合A A，記為記為a a A A 兩者必居其一且僅居其一兩者必居其一且僅居其一。例如，對元素例如，對元素2 2和和N N，就有，就有2 2屬于屬

13、于N N，即，即2 2 N N，對元素對元素-2-2和和N N，就有，就有-2-2不屬于不屬于N N，即，即- -2 2 N N。222022-3-112022-3-11羅素悖論羅素悖論例例 在一個(gè)很僻靜的孤島上，住著一些人家，島上在一個(gè)很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰給這位理發(fā)師刮臉？自己不刮臉的人刮臉。那么，誰給這位理發(fā)師刮臉？設(shè)設(shè)C Cx|xx|x是不給自己刮臉的人是不給自己刮臉的人 b b是這位理發(fā)師是這位理發(fā)師如如 b b C C，則，則 b b C C；如如 b b

14、 C C，則，則 b b C C。232022-3-112022-3-111.2.3 1.2.3 集合與集合的關(guān)系集合與集合的關(guān)系1 1、互異性互異性集合中的元素都是不同的，凡是相同的集合中的元素都是不同的，凡是相同的 元素，均視為同一個(gè)元素；元素，均視為同一個(gè)元素；1,1,2=1,21,1,2=1,22 2、確定性確定性能夠明確加以能夠明確加以“區(qū)分的區(qū)分的”對象；對象；3 3、無序性無序性集合中的元素是沒有順序的。集合中的元素是沒有順序的。 2,1=1,22,1=1,2一、集合的三大特征一、集合的三大特征242022-3-112022-3-11例例1.2.51.2.5設(shè)設(shè)E = x|(x

15、- 1)(x - 2)(x - 3) = 0, xRE = x|(x - 1)(x - 2)(x - 3) = 0, xR F = x|(x Z F = x|(x Z+ +) )且且(x(x2 212)12)。試指出集合試指出集合E E和和F F中的元素。中的元素。解解 集合集合E = 1, 2, 3E = 1, 2, 3，F(xiàn) = 1, 2, 3F = 1, 2, 3。顯然，集合顯然，集合E, FE, F中的中的元素完全相同元素完全相同，我們稱，我們稱這樣的這樣的兩個(gè)集合相等兩個(gè)集合相等 A AB B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A A與與B B具有相同的元素，否則，具有相同的元素，否則，A A B B。2

16、52022-3-112022-3-11例例1.2.61.2.6設(shè)設(shè)A = BASIC, PASCAL, ADAA = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL B = ADA, BASIC, PASCAL，請判斷請判斷A A和和B B的關(guān)系。的關(guān)系。解解 根據(jù)集合元素的根據(jù)集合元素的無序性和外延性原理無序性和外延性原理可得，可得， A = B A = B。 因?yàn)榧弦驗(yàn)榧螦 = BA = B，所以，所以B B中的每個(gè)元素都是中的每個(gè)元素都是A A中的元中的元素，我們稱素，我們稱集合集合A A包含包含集合集合B B。262022-3-112022-3

17、-11上述包含定義的數(shù)學(xué)語言描述為：上述包含定義的數(shù)學(xué)語言描述為： B B A A對任意對任意x x，如，如x x B B，則，則x x A A。三、包含和真包含關(guān)系三、包含和真包含關(guān)系定義定義1.2.11.2.1 設(shè)設(shè)A,BA,B是任意兩個(gè)集合，如果是任意兩個(gè)集合，如果 B B的每個(gè)元素都是的每個(gè)元素都是A A的元素，的元素，則稱則稱B B是是A A的子集合，簡稱的子集合，簡稱子集子集(Subset)(Subset)，這時(shí)也稱這時(shí)也稱A A包含包含B B，或，或B B被被A A包含包含，記作，記作A A B B 或或B B A A，稱稱“ ”或或“ ”為為包含關(guān)系包含關(guān)系(Inclusion

18、 Relation)(Inclusion Relation)。如果如果B B不被不被A A所包含，則記作所包含，則記作B B A A 。272022-3-112022-3-11例例1.2.71.2.7設(shè)設(shè)A = BASIC, PASCAL, ADAA = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL B = ADA, BASIC, PASCAL，請判斷請判斷A A和和B B之間的包含關(guān)系。之間的包含關(guān)系。解解 根據(jù)集合間根據(jù)集合間包含關(guān)系的定義包含關(guān)系的定義知，知，A A B B 且且A A B B 。 又從例又從例1.2.61.2.6知，集合知，集合A

19、 = BA = B，于是我們有：，于是我們有：定理定理1.2.21.2.2 設(shè)設(shè)A A、B B是任意兩個(gè)集合，則是任意兩個(gè)集合，則 A A B B，B B A A A=B A=B 282022-3-112022-3-11真包含關(guān)系真包含關(guān)系定義定義1.2.21.2.2 設(shè)設(shè)A,BA,B是任意兩個(gè)集合，如果是任意兩個(gè)集合，如果 B B A A并且并且ABAB則稱則稱B B是是A A的的真子集真子集(Proper Subset)(Proper Subset)，記作，記作B B A A，稱稱“ ”為為真包含關(guān)系真包含關(guān)系(Properly Inclusion (Properly Inclusion

20、Relation)Relation)。如果如果B B不是不是A A的真子集，則記作的真子集，則記作B AB A。上述真子集的數(shù)學(xué)語言描述為：上述真子集的數(shù)學(xué)語言描述為：B B A A對任意對任意x x，如，如x x B B，則，則x x A,A,并且，并且， y y A A，但是但是y y B B292022-3-112022-3-11判斷下列集合之間是否具有真包含關(guān)系。判斷下列集合之間是否具有真包含關(guān)系。（1 1）a, ba, b和和a, b, c, da, b, c, d；（2 2）a, b, c, da, b, c, d和和a, b, c, da, b, c, d。解解 根據(jù)根據(jù)真子集的

21、定義真子集的定義，有，有（1 1） a, b a, b a, b, c, da, b, c, d；（2 2）因?yàn)椋┮驗(yàn)閍, b, c, da, b, c, da, b, c, da, b, c, d，所以所以a, b, c, da, b, c, d不是不是a, b, c, da, b, c, d 的真子集。的真子集。例例1.2.81.2.8302022-3-112022-3-11例例1.2.91.2.9設(shè)設(shè)A = aA = a是一個(gè)集合，是一個(gè)集合，B = a, aB = a, a，試問，試問AABB和和AA B B同時(shí)成立嗎？同時(shí)成立嗎？ A = aA = a，aaBB AABB成立；成立；

22、 A = aA = a，aaBB AA B B成立。成立。解解 AABB和和A A B B同時(shí)成立。同時(shí)成立。分析分析312022-3-112022-3-11 1.2.4 1.2.4 幾個(gè)特殊集合幾個(gè)特殊集合定義定義1.2.31.2.3 不含任何元素的集合叫做空集不含任何元素的集合叫做空集(Empty Set)(Empty Set)，記作，記作?？占梢苑柣癁榭占梢苑柣癁?= x|xx = x|xx空集是客觀存在的?？占强陀^存在的。 1 1、空集、空集 設(shè)設(shè)A = x|(xR)A = x|(xR)且且(x(x2 20)0)，試列舉集合試列舉集合A A中的所有元素。中的所有元素。解解 A

23、 = A = 。定理定理1.2.3 1.2.3 （1 1）空集是一切集合的子集；）空集是一切集合的子集；（2 2）空集是絕對唯一的。）空集是絕對唯一的。322022-3-112022-3-11定理定理1.2.3 1.2.3 （2 2）的證明）的證明 對對“唯一性唯一性”的證明通常采用的證明通常采用反證法反證法。即假設(shè)即假設(shè)“不唯一不唯一”，得出矛盾，從而說明結(jié)論正，得出矛盾，從而說明結(jié)論正確確假設(shè)假設(shè)1 1和和2 2是兩個(gè)空集，且是兩個(gè)空集，且1 12 2，再證明再證明1 12 2，出現(xiàn)矛盾，從而說明結(jié)論成立。，出現(xiàn)矛盾，從而說明結(jié)論成立。那么怎么證明那么怎么證明1 12 2？分析分析根據(jù)定理

24、根據(jù)定理1.2.3 1.2.3 （1 1）空集是一切集合的子集）空集是一切集合的子集 1 1 2 2， 2 2 1 1，根據(jù)定理根據(jù)定理1.2.21.2.2， 1 12 2 1 1 2 2，2 2 1 1與與1 12 2矛盾矛盾332022-3-112022-3-11定義定義1.2.41.2.4 在一個(gè)在一個(gè)相對固定的范圍相對固定的范圍內(nèi)，內(nèi)，包含包含此范圍內(nèi)所有元素的集合此范圍內(nèi)所有元素的集合，稱為，稱為全集或論集全集或論集(Universal Set)(Universal Set)，用，用U U或或E E表示。表示。 用文氏圖描述如下用文氏圖描述如下: :U2 2、全集、全集342022-

25、3-112022-3-11例例1.2.121.2.12（1 1）在立體幾何中，全集是由空間的全體點(diǎn)組成；）在立體幾何中，全集是由空間的全體點(diǎn)組成；（2 2）在我國的人口普查中，全集是由我國所有人組成。）在我國的人口普查中，全集是由我國所有人組成。定理定理1.2.51.2.5 全集是相對唯一的全集是相對唯一的. .352022-3-112022-3-11集合集合A A中元素的數(shù)目稱為集合中元素的數(shù)目稱為集合A A的的基基數(shù)（數(shù)（base base number)number)，記為記為|A|A|。如如|A|A|是有限的，則稱集合是有限的，則稱集合A A為為有限集，有限集，如如|A|A|是無限的，

26、則稱集合是無限的，則稱集合A A為為無限集。無限集。例例1.2.13求下列集合的基數(shù)。求下列集合的基數(shù)。（1）A=；（2）B=；（3）C=a,b,c；（；（4）D=a,b,c。解解|A|=0，|B|=1，|C|=3，|D|=2。有限集和無限集有限集和無限集362022-3-112022-3-11m m元子集元子集定義定義1.2.61.2.6 如果一個(gè)集合如果一個(gè)集合A A含有含有n n個(gè)元素，則稱集合個(gè)元素，則稱集合A A為為n n元集元集，稱，稱A A的含有的含有m m個(gè)個(gè)(0mn)(0mn)元素的子集為元素的子集為A A的的m m元子集元子集。任給一個(gè)任給一個(gè)n n元集，怎樣求出它的全部元

27、集，怎樣求出它的全部m m元子集？元子集？例例1.2.141.2.14 設(shè)設(shè)A=1,2A=1,2，求出，求出A A的全部的全部m m元子集。元子集。 n=|A| = 2n=|A| = 2，mnmn m=0,1,2m=0,1,2。 當(dāng)當(dāng) m=0 m=0 時(shí)，得到時(shí)，得到0 0元子集：元子集：； 當(dāng)當(dāng) m=1 m=1 時(shí)，得到時(shí)，得到1 1元子集：元子集：1, 21, 2； 當(dāng)當(dāng) m=2 m=2 時(shí)，得到時(shí)，得到2 2元子集：元子集：1, 21, 2。解解 A A的全部的全部m m元子集是元子集是、11、22和和1, 21, 2。分析分析372022-3-112022-3-11子集總數(shù)子集總數(shù)一般

28、來說，對于一般來說，對于n n元集元集A A，它的，它的m m（0 0 m m n n）元子集有）元子集有 個(gè)，個(gè)，所以不同的子集總數(shù)有：所以不同的子集總數(shù)有：(1+1)(1+1)n n2 2n n所以，所以，n n元集共有元集共有2 2n n個(gè)子集。個(gè)子集。nn1n0nC.CC mnC382022-3-112022-3-11冪集冪集定義定義1.2.71.2.7 設(shè)設(shè)A A為任意集合，把為任意集合，把A A的的所有不同子集所有不同子集構(gòu)構(gòu)成的集合叫做成的集合叫做A A的的冪集冪集( (power set)power set)，記為，記為P P(A)(A)或或2 2A A 。其符號化表示為其符號

29、化表示為 P(A)P(A)x|x|一切一切x x AA該集合又稱為該集合又稱為集族集族(family of set)(family of set)。 對集族的研究在數(shù)學(xué)方面、知識庫和表處理語言對集族的研究在數(shù)學(xué)方面、知識庫和表處理語言以及人工智能等方面都有十分重要的意義。以及人工智能等方面都有十分重要的意義。 392022-3-112022-3-11例例1.2.15 1.2.15 計(jì)算下列冪集計(jì)算下列冪集（1 1）P()P()；（；（2 2）P()P()；（；（3 3）P(a,b,c)P(a,b,c)。解解（1 1）P() = P() = ；（2 2）P() = , P() = , ；（3 3

30、）P(a,b,c)=,a,b,c,a,b,cP(a,b,c)=,a,b,c,a,b,c。 顯然，若集合有個(gè)元素，則集合共有顯然，若集合有個(gè)元素，則集合共有2 2|A|A|個(gè)個(gè)子集，即：子集，即：| |P P(A)|(A)| 2 2|A|A|。402022-3-112022-3-111.2.5 1.2.5 集合的運(yùn)算集合的運(yùn)算定義定義1.2.81.2.8 設(shè)設(shè)A A、B B是兩個(gè)集合，是兩個(gè)集合，(1)(1)并集并集 A A B=x|xB=x|x A A或或x x BB(2)(2)交集交集 A A B=x|xB=x|x A A且且x x BB(3)(3)差集差集 A A- -B=x|xB=x|x

31、 A A且且x x BB(4)(4)補(bǔ)集補(bǔ)集 = =U-U-A=x|xA=x|x U U且且x x A(A(,A,AC C) )(5)(5)對稱差集對稱差集 A A B=x|(xB=x|(x A)A)且且(x(x B)B)或或(x(x B)B)且且(x(x A)A)AUA B并集并集UA B差集差集A BU對稱差集對稱差集UA B交集交集補(bǔ)補(bǔ)集集UA412022-3-112022-3-11推廣推廣A A1 1AA2 2AA3 3AAn n1niiAin,.,2, 1iin1iAA iZii1iAA iZii1iAA =x|(x=x|(x A A1 1) )或或(x(x A A2 2) )或或或

32、或(x(x A An n)A A1 1AA2 2AA3 3AAn nx|(xx|(x A A1 1) )且且(x(x A A2 2) )且且且且(x(x A An n)當(dāng)當(dāng)n n無限增大時(shí)，可以記為：無限增大時(shí)，可以記為：A A1 1AA2 2AA3 3 A A1 1AA2 2AA3 3422022-3-112022-3-11定理定理1.2.51.2.51.1.等冪律等冪律: := =；= =； 2.2.交換律交換律: := =; ;= =3.3.結(jié)合律結(jié)合律: :( ()=()=()； ( ()=()=()；4.4.恒等律恒等律: :=； = =； 5.5.零律零律: := =； =；6.6

33、.分配律分配律: :( ()=()=()()() )( ()=()=()()() )7.7.吸收律吸收律: :A(AB)=A;A(AB)=A;A(AB)=AA(AB)=A； 432022-3-112022-3-11定理定理1.2.5(1.2.5(續(xù)）續(xù)）8.8.A - A = A - A = ； 9.9.A - B = A - (AB)A - B = A - (AB)；10.10.(A - B) - C = A - (BC)(A - B) - C = A - (BC)；11.11.A(B-A) = ABA(B-A) = AB；12.12.A - B =A A - B =A ；13.13.否定律

34、：否定律： ；14.DeMorgan14.DeMorgan律：律： ；15.15.矛盾律：矛盾律： AA；16.16.排中律：排中律：A A U U。BAA BABABABA,AA442022-3-112022-3-11證明：證明：DeMorganDeMorgan律：律：BABABABA BABABABA)2() 1 (分析分析定理定理1.2.21.2.2 設(shè)設(shè)A A、B B是任意兩個(gè)集合，則是任意兩個(gè)集合，則 A A B B，B B A A A=B A=B 452022-3-112022-3-11證明（證明（a a）：）：由、知，由、知，BAxBABABAxBxAx且BAxBxAx且BAxB

35、xAx且BxAx且BAxBAxBABABABA462022-3-112022-3-11證明（證明（b b）：）：（b b）在在 中，用中，用 和和 分別取代分別取代A A和和B B，則有則有 BABABABABABABABABAAB472022-3-112022-3-111.3 1.3 無限集無限集 質(zhì)質(zhì) 變變無限集合無法用確切的個(gè)數(shù)來描述，無限集合無法用確切的個(gè)數(shù)來描述，因此，無因此，無限集合有許多有限集合所沒有的一些特征，而限集合有許多有限集合所沒有的一些特征，而有限集合的一些特征也不能任意推廣到無限集有限集合的一些特征也不能任意推廣到無限集合中去，即使有的能推廣，也要做某些意義上合中去，

36、即使有的能推廣，也要做某些意義上的修改。的修改。有限集有限集無限集無限集量量 變變482022-3-112022-3-111.3.1 1.3.1 可數(shù)集合和不可數(shù)集合可數(shù)集合和不可數(shù)集合 二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由馮馮 諾依曼諾依曼（Von NeumannVon Neumann，J.J.）用集合的方式來）用集合的方式來定義自然數(shù)取得了成功，提出了用序列定義自然數(shù)取得了成功，提出了用序列，,，,，來定義自然來定義自然數(shù)。數(shù)。 492022-3-112022-3-111.3.1 1.3.1 可數(shù)集合與不可數(shù)集合可數(shù)集合與不可數(shù)集合問題問題1

37、,2,3,1,2,3, 與與112 2,2,22 2,3,32 2, , 哪個(gè)集合的元素更多？哪個(gè)集合的元素更多？引入：引入：自然數(shù)集合自然數(shù)集合 二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由馮馮 諾依曼（諾依曼（Von NeumannVon Neumann，J.J.）用集合的方式來定義）用集合的方式來定義自然數(shù)取得了成功，提出了用序列自然數(shù)取得了成功，提出了用序列，,，,，來來定義自然數(shù)。定義自然數(shù)。 502022-3-112022-3-11自然數(shù)集合自然數(shù)集合N N的定義的定義 N N，若若n n N N，則，則n n: :n n nn N N。也即

38、：也即：0:0: ， 1:1: 00， 2:2: , 0,10,1 . . n: n:0,1,2,3,.n-10,1,2,3,.n-1 . .故故 N N0,1,2,3,.,n,.0,1,2,3,.,n,.512022-3-112022-3-11等勢的概念等勢的概念 定義定義1.3.11.3.1 設(shè)設(shè)A A，B B是兩個(gè)集合，若在是兩個(gè)集合，若在A A，B B之間之間存在存在1-11-1對應(yīng)對應(yīng)的關(guān)系：的關(guān)系：ABAB則稱則稱A A與與B B是是等勢的等勢的(equipotential)(equipotential)，記為：，記為：A A B B。也稱集合也稱集合A A與與B B等勢等勢(eq

39、uipotent)(equipotent)。 注意：注意：若若A AB B，則，則 A A B B。 若若A A B B，則，則 A AB B （）（）522022-3-112022-3-11可數(shù)集合可數(shù)集合( (可列集）可列集） 定義定義1.3.21.3.2 凡是與凡是與自然數(shù)集合自然數(shù)集合等勢的集合，統(tǒng)等勢的集合，統(tǒng)稱為稱為可數(shù)集合可數(shù)集合( (可列集可列集)(Countable Set )(Countable Set )。記為：記為：0 0 ( (讀作讀作阿列夫零阿列夫零) ) 。例例1.3.11.3.1 下列集合都是可數(shù)集合：下列集合都是可數(shù)集合： 1)O1)O+ +x|xx|x N

40、N，x x是奇數(shù)是奇數(shù); 2)P 2)Px|xx|x N N，x x是素?cái)?shù)是素?cái)?shù); 3) 3)有理數(shù)集合有理數(shù)集合Q.Q.532022-3-112022-3-11解：解：1 1）在在O O+ +與與N N之間建立之間建立1-11-1對應(yīng)的關(guān)系對應(yīng)的關(guān)系 f f：NONO+ + 如下：如下：N N . . . . . . O O+ + . 2n+1 . 2n+1 .所以，所以，O O+ +是可數(shù)集合。是可數(shù)集合。542022-3-112022-3-112 2）在在P P與與N N之間建立之間建立1-11-1對應(yīng)的關(guān)系對應(yīng)的關(guān)系f f：NPNP如下：如下：N N . . .P P 11 .11 .

41、 所以，所以，P P是可數(shù)集合。是可數(shù)集合。552022-3-112022-3-115 5）-3/1-3/118 18 -2/1-2/15 5 -1/1-1/14 4 0/10/100 1/11/11 1 2/1 2/11010 -3/1 -3/11111 -3/2-3/217 17 -2/2 -1/2-2/2 -1/23 3 0/2 1/20/2 1/222 2/2 2/2 3/23/21212 -3/3 -2/3 -3/3 -2/36 6 -1/3-1/37 7 0/3 1/30/3 1/388 2/3 2/399 3/3 3/3 -3/4 -3/41616 -2/4-2/4 -1/4-1

42、/415 15 0/40/4 1/41/414 14 2/4 3/42/4 3/41313所以，有理數(shù)集合必是可數(shù)集合。所以，有理數(shù)集合必是可數(shù)集合。 562022-3-112022-3-11定理定理1.3.11.3.1兩個(gè)有限集合等勢兩個(gè)有限集合等勢當(dāng)且僅當(dāng)它們有相同的元當(dāng)且僅當(dāng)它們有相同的元素個(gè)數(shù)；素個(gè)數(shù)；有限集合不和其任何真子集等勢；有限集合不和其任何真子集等勢；可數(shù)集合可以和其可數(shù)的真子集等勢?？蓴?shù)集合可以和其可數(shù)的真子集等勢。572022-3-112022-3-11不可數(shù)集合不可數(shù)集合定義定義1.3.31.3.3開區(qū)間開區(qū)間(0,1)(0,1)稱為稱為不可數(shù)集合不可數(shù)集合，其，其基數(shù)

43、設(shè)為基數(shù)設(shè)為( (讀讀作阿列夫作阿列夫) )；凡是與開區(qū)間凡是與開區(qū)間(0,1)(0,1)等勢的集合都是不可數(shù)集合。等勢的集合都是不可數(shù)集合。例例1.3.21.3.2 (1)(1)閉區(qū)間閉區(qū)間0,1 0,1 是不可數(shù)集合；是不可數(shù)集合； (2)(2)實(shí)數(shù)集合實(shí)數(shù)集合R R是不可數(shù)集合。是不可數(shù)集合。582022-3-112022-3-11例例1.3.2 1.3.2 解解（1 1）在閉區(qū)間在閉區(qū)間0, 10, 1和開區(qū)間和開區(qū)間(0, 1)(0, 1)之間建立之間建立如下對應(yīng)關(guān)系：如下對應(yīng)關(guān)系： 則上述對應(yīng)是則上述對應(yīng)是一一對應(yīng)一一對應(yīng)的關(guān)系。的關(guān)系。 所以所以00，11與與（0 0，1 1）一

44、定是等勢的，即）一定是等勢的，即00，11是不可數(shù)集合是不可數(shù)集合。nn201 / 4,11 / 2,R :11n1, 2,3,22nnn(0,1) .其 他592022-3-112022-3-11例例1.3.2 1.3.2 解（續(xù)）解（續(xù)）（2 2）在實(shí)數(shù)集和開區(qū)間在實(shí)數(shù)集和開區(qū)間(0,1)(0,1)之間建立如下對之間建立如下對應(yīng)關(guān)系：應(yīng)關(guān)系：顯然此對應(yīng)關(guān)系是顯然此對應(yīng)關(guān)系是一一對應(yīng)一一對應(yīng)關(guān)系，即（關(guān)系，即（0 0，1 1）與）與R R之間是等勢的，所以之間是等勢的，所以R R是一個(gè)不可數(shù)集合是一個(gè)不可數(shù)集合。2n1ntan2602022-3-112022-3-111.4 1.4 集合的應(yīng)

45、用集合的應(yīng)用例例1.4.11.4.1 用用H H代表硬幣正面，代表硬幣正面，T T代表硬幣反面。試寫代表硬幣反面。試寫出當(dāng)扔出三個(gè)硬幣時(shí)可能出現(xiàn)的結(jié)果所組成的集合。出當(dāng)扔出三個(gè)硬幣時(shí)可能出現(xiàn)的結(jié)果所組成的集合。解解: : 8 8種可能：種可能：HHHHHH，HHTHHT，HTHHTH，HTTHTT，THHTHH，THTTHT，TTHTTH，TTTTTT。但這三個(gè)硬幣沒有順序之分，即。但這三個(gè)硬幣沒有順序之分，即HHTHHT和和HTHHTH是同一個(gè)元素，所以是同一個(gè)元素，所以 A = HHHA = HHH，HHTHHT，HTTHTT，TTTTTT。612022-3-112022-3-11例例1.4.21.4.2一個(gè)正三角形被均分為三個(gè)小三角形，如圖一個(gè)正三角