1、離 散 數(shù) 學(xué),2020/9/8,第一篇 預(yù)備知識(shí),第一章 集合論,2020/9/8,1.0 內(nèi)容提要,2020/9/8,1.1 本章學(xué)習(xí)要求,2020/9/8,1.2 集合,一、集合的概念,集合（SET）由指定范圍內(nèi)的某些特定對(duì)象聚集在一起構(gòu)成。,指定范圍內(nèi)的每一個(gè)對(duì)象稱為這個(gè)集合的元素(element),中國所有大學(xué)生的聚集,指定范圍,特定對(duì)象,2020/9/8,二、集合的記法,通常用帶(不帶)標(biāo)號(hào)的大寫字母A、B、C、.、A1、 B1 、C1 、.、X、Y、Z、.表示集合； 通常用帶（不帶）標(biāo)號(hào)的小寫字母a、b、c、.、a1、 b1 、c1 、.、x、y、z、.表示元素。,2020/9/

2、8,固定的符號(hào),2020/9/8,1.2.1 集合的表示方法,集合是由它包含的元素完全確定的，為了表示一個(gè)集合，通常有： 枚舉法 隱式法（敘述法） 歸納法 遞歸指定 文氏圖,2020/9/8,1、枚舉法（顯示法）,-列出集合中全部元素或部分元素的方法叫枚舉法,例1.2.1 （1）Aa，b，c，d （2）B = 0, 1, 4, 9, 16, , n2, ,適用場(chǎng)景： 一個(gè)集合僅含有限個(gè)元素 一個(gè)集合的元素之間有明顯關(guān)系,2020/9/8,枚舉法的優(yōu)缺點(diǎn),是一種顯式表示法 優(yōu)點(diǎn)：具有透明性 缺點(diǎn)：在表示具有某種特性的集合或集合中元素過多時(shí)受到了一定的局限，而且，從計(jì)算機(jī)的角度看，顯式法是一種“靜

3、態(tài)”表示法，如果一下子將這么多的“數(shù)據(jù)”輸入到計(jì)算機(jī)中去，那將占據(jù)大量的“內(nèi)存”。,2020/9/8,2、隱式法（敘述法）,通過刻畫集合中元素所具備的某種特性來表示集合的方法稱為敘述法（隱式法） 一般表示方法：Px|P(x) 適用場(chǎng)景： 一個(gè)集合含有很多或無窮多個(gè)元素； 一個(gè)集合的元素之間有容易刻畫的共同特征 其突出優(yōu)點(diǎn)是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性。,代表元,X所具有的性質(zhì)p,2020/9/8,例1.2.2,（1）A = x|x是“discrete mathematics”中的所有字母； （2）Z = x|x是一個(gè)整數(shù)； （3）S = x|x是整數(shù)，并且x21

4、 = 0； （4）Q+ = x|x是一個(gè)正有理數(shù)。,2020/9/8,3、歸納法,歸納法是通過歸納定義集合，主要由三部分組成： 第一部分：基礎(chǔ)。指出某些最基本的元素屬于某集合； 第二部分：歸納。指出由基本元素造出新元素的方法； 第三部分：極小性。指出該集合的界限。,注意：第一部分和第二部分指出一個(gè)集合至少包括的元素，第三部分指出一個(gè)集合至多要包含的元素,2020/9/8,例1.2.3,集合A按如下方式定義： （1）0和1都是A中的元素； （2）如果a, b是A中的元素，則ab, ba也是A中的元素； （3）有限次使用(1)、(2)后所得到的字符串都是A中的元素。 試指出其定義方式。并舉出集合A

5、中的3個(gè)元素,2020/9/8,4、遞歸指定集合,通過計(jì)算規(guī)則定義集合中的元素,例1.2.4 設(shè) a0 1， ai+1 2ai （i0） 定義Sa0 ，a1 ，a2 ，. ak | k0， 試寫出集合S中的所有元素。,2020/9/8,5、文氏圖解法,文氏圖解法是一種利用平面上點(diǎn)的集合作成的對(duì)集合的圖解。一般用平面上的圓形或方形表示一個(gè)集合。,A,A,2020/9/8,1.2.2 集合與元素的關(guān)系,元素與集合之間的“屬于關(guān)系”是“明確”的。 對(duì)某個(gè)集合A和元素a來說， a屬于集合A，記為aA 或者 a不屬于集合A，記為aA 兩者必居其一且僅居其一。,例如，對(duì)元素2和N，就有2屬于N，即2N，

6、對(duì)元素-2和N，就有-2不屬于N，即-2N。,2020/9/8,羅素悖論,例 在一個(gè)很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰給這位理發(fā)師刮臉？,解：設(shè)Cx|x是不給自己刮臉的人 b是這位理發(fā)師 如 bC，則 bC； 如 bC，則 bC。,2020/9/8,1.2.3 集合與集合的關(guān)系,1、互異性集合中的元素都是不同的，凡是相同的 元素，均視為同一個(gè)元素； 1,1,2=1,2 2、確定性能夠明確加以“區(qū)分的”對(duì)象； 3、無序性集合中的元素是沒有順序的。 2,1=1,2,一、集合的三大特征,2020/9/8,例1.2.5,設(shè)E =

7、x|(x - 1)(x - 2)(x - 3) = 0, xR F = x|(x Z+)且(x212)。 試指出集合E和F中的元素。 解 集合E = 1, 2, 3，F(xiàn) = 1, 2, 3。,顯然，集合E, F中的元素完全相同，我們稱 這樣的兩個(gè)集合相等,二、外延性原理 AB當(dāng)且僅當(dāng)A與B具有相同的元素，否則，AB。,2020/9/8,例1.2.6,設(shè)A = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL， 請(qǐng)判斷A和B的關(guān)系。 解 根據(jù)集合元素的無序性和外延性原理可得， A = B。,因?yàn)榧螦 = B，所以B中的每個(gè)元素都是A中的元素，我們稱集合A包含

8、集合B。,2020/9/8,三、包含和真包含關(guān)系,定義1.2.1 設(shè)A,B是任意兩個(gè)集合，如果 B的每個(gè)元素都是A的元素， 則稱B是A的子集合，簡(jiǎn)稱子集(Subset)， 這時(shí)也稱A包含B，或B被A包含，記作AB 或BA， 稱“”或“”為包含關(guān)系(Inclusion Relation)。 如果B不被A所包含，則記作B A 。,上述包含定義的數(shù)學(xué)語言描述為： BA對(duì)任意x，如xB，則xA。,顯然，對(duì)任意集合A，都有AA。,2020/9/8,例1.2.7,設(shè)A = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL， 請(qǐng)判斷A和B之間的包含關(guān)系。 解 根據(jù)集合間包

9、含關(guān)系的定義知，AB 且AB 。,又從例1.2.6知，集合A = B，于是我們有：,定理1.2.2 設(shè)A、B是任意兩個(gè)集合，則 AB，BA A=B,2020/9/8,真包含關(guān)系,定義1.2.2 設(shè)A,B是任意兩個(gè)集合，如果 BA并且AB 則稱B是A的真子集(Proper Subset)，記作BA， 稱“”為真包含關(guān)系(Properly Inclusion Relation)。 如果B不是A的真子集，則記作B A。,上述真子集的數(shù)學(xué)語言描述為： BA對(duì)任意x，如xB，則xA,并且， yA，但是yB,2020/9/8,判斷下列集合之間是否具有真包含關(guān)系。 （1）a, b和a, b, c, d； （

10、2）a, b, c, d和a, b, c, d。,解 根據(jù)真子集的定義，有 （1） a, b a, b, c, d； （2）因?yàn)閍, b, c, da, b, c, d， 所以a, b, c, d不是a, b, c, d 的真子集。,例1.2.8,2020/9/8,例1.2.9,設(shè)A = a是一個(gè)集合，B = a, a，試問 AB和AB 同時(shí)成立嗎？ A = a，aB AB成立； A = a，aB AB成立。 解 AB和AB同時(shí)成立。,分析,2020/9/8,1.2.4 幾個(gè)特殊集合,定義1.2.3 不含任何元素的集合叫做空集(Empty Set)，記作。 空集可以符號(hào)化為 = x|xx 空集

11、是客觀存在的。,1、空集,例1.2.10 設(shè)A = x|(xR)且(x20)， 試列舉集合A中的所有元素。 解 A = 。,定理1.2.3 （1）空集是一切集合的子集； （2）空集是絕對(duì)唯一的。,2020/9/8,定理1.2.3 （2）的證明,對(duì)“唯一性”的證明通常采用反證法。 即假設(shè)“不唯一”，得出矛盾，從而說明結(jié)論正確 假設(shè)1和2是兩個(gè)空集，且12， 再證明12，出現(xiàn)矛盾，從而說明結(jié)論成立。,那么怎么證明12？,分析,根據(jù)定理1.2.3 （1）空集是一切集合的子集 1 2， 2 1，,根據(jù)定理1.2.2， 12 12，21,與12矛盾,2020/9/8,定義1.2.4 在一個(gè)相對(duì)固定的范圍

12、內(nèi)，包含此范圍內(nèi)所有元素的集合，稱為全集或論集(Universal Set)，用U或E表示。 用文氏圖描述如下:,U,2、全集,2020/9/8,例1.2.12,（1）在立體幾何中，全集是由空間的全體點(diǎn)組成； （2）在我國的人口普查中，全集是由我國所有人組成。,定理1.2.5 全集是相對(duì)唯一的.,2020/9/8,集合A中元素的數(shù)目稱為集合A的基數(shù)（base number)，記為|A|。 如|A|是有限的，則稱集合A為有限集， 如|A|是無限的，則稱集合A為無限集。,例1.2.13 求下列集合的基數(shù)。 （1）A =； （2）B = ； （3）C = a, b, c；（4）D = a, b, c

13、。 解 |A| = 0，|B| = 1，|C| = 3，|D| = 2。,有限集和無限集,2020/9/8,m元子集,定義1.2.6 如果一個(gè)集合A含有n個(gè)元素，則稱集合A為n元集，稱A的含有m個(gè)(0mn)元素的子集為A的m元子集。 任給一個(gè)n元集，怎樣求出它的全部m元子集？ 例1.2.14 設(shè)A=1,2，求出A的全部m元子集。 n=|A| = 2，mn m=0,1,2。 當(dāng) m=0 時(shí)，得到0元子集：； 當(dāng) m=1 時(shí)，得到1元子集：1, 2； 當(dāng) m=2 時(shí)，得到2元子集：1, 2。 解 A的全部m元子集是、1、2和1, 2。,分析,2020/9/8,子集總數(shù),一般來說，對(duì)于n元集A，它的

14、m（0mn）元子集有 個(gè)，所以不同的子集總數(shù)有： (1+1)n2n 所以，n元集共有2n個(gè)子集。,2020/9/8,冪集,定義1.2.7 設(shè)A為任意集合，把A的所有不同子集構(gòu) 成的集合叫做A的冪集(power set)，記為P(A)或2A 。 其符號(hào)化表示為 P(A)x|一切xA 該集合又稱為集族(family of set)。,對(duì)集族的研究在數(shù)學(xué)方面、知識(shí)庫和表處理語言以及人工智能等方面都有十分重要的意義。,2020/9/8,例1.2.15 計(jì)算下列冪集,（1）P()；（2）P()；（3）P(a,b,c)。 解 （1）P() = ； （2）P() = , ； （3）P(a,b,c)=,a,b

15、,c,a,b,c。,顯然，若集合有個(gè)元素，則集合共有2|A|個(gè)子集，即： |P(A)| 2|A|。,2020/9/8,1.2.5 集合的運(yùn)算,定義1.2.8 設(shè)A、B是兩個(gè)集合， (1)并集 AB=x|xA或xB (2)交集 AB=x|xA且xB (3)差集 A-B=x|xA且xB (4)補(bǔ)集 =U-A=x|xU且xA(,AC) (5)對(duì)稱差集 AB=x|(xA)且(xB)或(xB)且(xA),2020/9/8,推廣,A1A2A3An,=x|(xA1)或(xA2)或或(xAn),A1A2A3An,x|(xA1)且(xA2)且且(xAn),當(dāng)n無限增大時(shí)，可以記為：,A1A2A3, A1A2A3

16、,2020/9/8,定理1.2.5,1.等冪律:=；=； 2.交換律:=;= 3.結(jié)合律:()=()； ()=()； 4.恒等律:=；=； 5.零律:=；=； 6.分配律:()=()() ()=()() 7.吸收律:A(AB)=A;A(AB)=A；,2020/9/8,定理1.2.5(續(xù)）,8.A - A = ； 9.A - B = A - (AB)； 10.(A - B) - C = A - (BC)； 11.A(B-A) = AB；12.A - B =A ； 13.否定律： ； 14.DeMorgan律： ； 15.矛盾律： A； 16.排中律：A U。,2020/9/8,證明：,DeMor

17、gan律：,分析 定理1.2.2 設(shè)A、B是任意兩個(gè)集合，則 AB，BA A=B,2020/9/8,證明（a）：,由、知，,2020/9/8,證明（b）：,（b）在 中，用 和 分別取代A和B，則有,2020/9/8,1.3 無限集,質(zhì) 變,無限集合無法用確切的個(gè)數(shù)來描述，因此，無限集合有許多有限集合所沒有的一些特征，而有限集合的一些特征也不能任意推廣到無限集合中去，即使有的能推廣，也要做某些意義上的修改。,有限集,無限集,量 變,2020/9/8,1.3.1 可數(shù)集合和不可數(shù)集合,二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由馮諾依曼（Von Neumann，J.）用集合的方式來定義自然數(shù)取得了

18、成功，提出了用序列，,，,，來定義自然數(shù)。,2020/9/8,1.3.1 可數(shù)集合與不可數(shù)集合,問題1,2,3,與12,22,32,哪個(gè)集合的元素更多？ 引入：自然數(shù)集合 二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由馮諾依曼（Von Neumann，J.）用集合的方式來定義自然數(shù)取得了成功，提出了用序列，,，,，來定義自然數(shù)。,2020/9/8,自然數(shù)集合N的定義,N， 若nN，則n:nnN。 也即： 0:， 1:0， 2:,0,1 . n:0,1,2,3,.n-1 . 故 N0,1,2,3,.,n,.,2020/9/8,等勢(shì)的概念,定義1.3.1 設(shè)A，B是兩個(gè)集合，若在A，B之間存在1-1對(duì)

19、應(yīng)的關(guān)系： ：AB 則稱A與B是等勢(shì)的(equipotential)，記為：AB。 也稱集合A與B等勢(shì)(equipotent)。,注意：若AB，則 AB。,若AB，則 AB,（）,（）,2020/9/8,可數(shù)集合(可列集）,定義1.3.2 凡是與自然數(shù)集合等勢(shì)的集合，統(tǒng)稱為可數(shù)集合(可列集)(Countable Set )。 記為：0 (讀作阿列夫零) 。,例1.3.1 下列集合都是可數(shù)集合： 1)O+x|xN，x是奇數(shù); 2)Px|xN，x是素?cái)?shù); 3)有理數(shù)集合Q.,2020/9/8,解：1）,在O+與N之間建立1-1對(duì)應(yīng)的關(guān)系 f：NO+ 如下： N . . . . O+ . 2n+1

20、. 所以，O+是可數(shù)集合。,2020/9/8,2）,在P與N之間建立1-1對(duì)應(yīng)的關(guān)系 f：NP如下： N . . P 11 . 所以，P是可數(shù)集合。,2020/9/8,5）,-3/118 -2/15 -1/14 0/10 1/11 2/110 -3/111 -3/217 -2/2 -1/23 0/2 1/22 2/2 3/212 -3/3 -2/36 -1/37 0/3 1/38 2/39 3/3 -3/416 -2/4 -1/415 0/4 1/414 2/4 3/413 所以，有理數(shù)集合必是可數(shù)集合。,2020/9/8,定理1.3.1,兩個(gè)有限集合等勢(shì)當(dāng)且僅當(dāng)它們有相同的元素個(gè)數(shù)； 有限集

21、合不和其任何真子集等勢(shì)； 可數(shù)集合可以和其可數(shù)的真子集等勢(shì)。,2020/9/8,不可數(shù)集合,定義1.3.3 開區(qū)間(0,1)稱為不可數(shù)集合，其基數(shù)設(shè)為(讀作阿列夫)； 凡是與開區(qū)間(0,1)等勢(shì)的集合都是不可數(shù)集合。,例1.3.2 (1)閉區(qū)間0,1 是不可數(shù)集合； (2)實(shí)數(shù)集合R是不可數(shù)集合。,2020/9/8,例1.3.2 解,（1）在閉區(qū)間0, 1和開區(qū)間(0, 1)之間建立如下對(duì)應(yīng)關(guān)系： 則上述對(duì)應(yīng)是一一對(duì)應(yīng)的關(guān)系。 所以0，1與（0，1）一定是等勢(shì)的，即0，1是不可數(shù)集合。,2020/9/8,例1.3.2 解（續(xù)）,（2）在實(shí)數(shù)集和開區(qū)間(0,1)之間建立如下對(duì)應(yīng)關(guān)系： 顯然此對(duì)應(yīng)

22、關(guān)系是一一對(duì)應(yīng)關(guān)系，即（0，1）與R之間是等勢(shì)的，所以R是一個(gè)不可數(shù)集合。,2020/9/8,1.4 集合的應(yīng)用,例1.4.1 用H代表硬幣正面，T代表硬幣反面。試寫出當(dāng)扔出三個(gè)硬幣時(shí)可能出現(xiàn)的結(jié)果所組成的集合。 解: 8種可能：HHH，HHT，HTH，HTT，THH，THT，TTH，TTT。但這三個(gè)硬幣沒有順序之分，即HHT和HTH是同一個(gè)元素，所以 A = HHH，HHT，HTT，TTT。,2020/9/8,例1.4.2,一個(gè)正三角形被均分為三個(gè)小三角形，如圖1.4.1所示?，F(xiàn)用黑、白二色對(duì)其小三角形著色，假設(shè)經(jīng)旋轉(zhuǎn)能使之重合的圖像算一種。試寫出由不同圖像構(gòu)成的集合。,2020/9/8,例1.4.2 解,因?yàn)槊總€(gè)小三角形均可著色，三個(gè)小三角形共有222 = 8種著色方案，所以可得8種不