第一章集合-new.ppt

1、離散數(shù)學(xué),侯 愛 民東莞理工學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,前言,離散數(shù)學(xué)是計(jì)算機(jī)學(xué)科的基礎(chǔ)理論的核心課程。是學(xué)好數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、形式語言、并行處理、人工智能等知識(shí)的理論基礎(chǔ)。 離散數(shù)學(xué)的特點(diǎn)內(nèi)容廣泛，抽象理論多。 離散數(shù)學(xué)的貢獻(xiàn)提高學(xué)生的抽象思維、邏輯思維和創(chuàng)新思維。 離散數(shù)學(xué)的學(xué)習(xí)方法類似高等數(shù)學(xué)：清楚概念，多做習(xí)題。,第一章 集 合,學(xué)習(xí)重點(diǎn)： 1、集合、子集、空集、全集、補(bǔ)集、冪集等概念。 2、集合的基本運(yùn)算：并、交、差、對(duì)稱差。 3、集合代數(shù)的有關(guān)公式及證明。 4、在組合計(jì)數(shù)中廣泛使用的包含排斥原理。,第1.1節(jié) 集合的基本概念,第1.1.1節(jié) 集合概念及表示方法 第1.1.2節(jié)

2、 子集和空集 第1.1.3節(jié) 全集和補(bǔ)集 第1.1.4節(jié) 冪集,第1.1.1節(jié) 集合概念及表示方法,集合的概念：只能給出說明性的描述。 集合就是具有某種特點(diǎn)的研究對(duì)象的聚合。 其中每一個(gè)研究對(duì)象稱為這個(gè)集合的元素。 通常用大寫字母表示集合，小寫字母表示元素。 若a是集合A中的元素，則記為aA。稱元素a屬于集合A。 若a不 是集合A中的元素，則記為aA。稱元素a不屬于集合A。,第1.1.1節(jié) 集合概念及表示方法,列舉法（也稱枚舉法） 是把集合中的所有元素置于花括號(hào)內(nèi)，元素之間用逗號(hào)隔開。 即在集合中列舉出所有的元素。 很顯然，這種方法只能表示有窮集合。 例1：集合A含5個(gè)元素，它們分別是2,3,

3、5,7,13。用列舉法可把A表示成： A= 2,3,5,7,13 顯然，2A，而 4A。,第1.1.1節(jié) 集合概念及表示方法,特征法（也稱謂詞法） 是以某個(gè)小寫的英文字母來統(tǒng)一表示該集合的元素，并指出這類元素的共同特征。 例2： B= x|x是素?cái)?shù)，x15 花括號(hào)內(nèi)的符號(hào)“|”讀作“系指”，逗號(hào)讀作“并且”。因此，集合B是由小于15的素?cái)?shù)組成。集合B的元素就是2,3,5,7,13?？梢娂螧和列舉法提到的集合A的元素完全相同。,第1.1.2節(jié) 子集和空集,定義1.1.1： 設(shè)A，B是集合，如果A中每一個(gè)元素又都是B中的元素，則稱A是B的子集，也稱B包含A或A包含于B中，記作 B A 或 A B

4、 說明： 1.如果A不是B的子集，即A中至少有一個(gè)元素不屬于B，則稱B不包含A或A不包含于B中，記作 B A 或 A B,第1.1.2節(jié) 子集和空集,2.如果A是B的子集，但A和B不相等，即在B中總有一些元素不屬于A，則稱A為B的真子集，記作 B A 或 A B 3.當(dāng)兩個(gè)集合X和Y的元素相同時(shí)，稱這兩個(gè)集合相等，記作X=Y。 定理1.1.1： 集合A和B相等的充分必要條件是： AB 且 AB。,第1.1.2節(jié) 子集和空集,說明： 1.不含有任何元素的集合稱為空集，記作或。 2.空集是任何集合的子集。 3.集合中的元素也可以是另一個(gè)集合。 4.一般，屬于關(guān)系“”是元素和集合之間的關(guān)系；包含關(guān)系

5、“ ”是集合和集合之間的關(guān)系。但集合也可以屬于（）另一個(gè)集合。,第1.1.2節(jié) 子集和空集,例3：設(shè)A=a，b，B=a，b，a，b。 則：aA，bA。 aB，bB，a，bB。 A B，AB。,第1.1.3節(jié) 全集和補(bǔ)集,研究對(duì)象的全體稱為全集，記作。 設(shè)A是集合，由屬于全集但不屬于集合A的元素構(gòu)成的集合稱為A的補(bǔ)集，記作A（或A）。,第1.1.3節(jié) 全集和補(bǔ)集,說明： 例1：全集是全體正整數(shù)構(gòu)成的集合。 若集合A=x|x是正偶數(shù)。 則A的補(bǔ)集A=x|x是正奇數(shù)。 例2：全集=1,2,3,4,5,6,7,8,9,10。 若集合A=1,2,3,4 。 則A的補(bǔ)集A=5,6,7,8,9,10 。,第

6、1.1.4節(jié) 冪集,定義1.1.2： 設(shè)A是集合，由A的所有子集作為元素構(gòu)成的集合稱為A的冪集，記作(A)。 例1：設(shè)A=a，b，則 A的子集: ,a,b,a,b。 A的冪集：(A)=,a,b,a,b 當(dāng)一個(gè)集合的元素個(gè)數(shù)為有限時(shí)，稱該集合為有限集，集合中的元素個(gè)數(shù)為無限時(shí)，稱該集合為無限集。有限集A中元素的個(gè)數(shù)稱為有限集A的基。記作|A|。,第1.1.4節(jié) 冪集,定理1.1.2： 設(shè)A是有限集，且|A|=n，則|(A)|= 2n。 證明：由排列組合的知識(shí)可知 |(A)|= C0n+ C1n + C2n + + Cn-1n + Cnn 又由二項(xiàng)式定理可知 (a+b)n= C0n an+C1n

7、an-1b+C2n an-2b2+ Cn-1n a1bn-1 + Cnnbn 若取a=b=1,則有: (1+1)n= C0n+ C1n + Cnn 由此證得 |(A)|= 2n。,第1.1.4節(jié) 冪集,例2：A=a，b，c，其冪集(A)=？,第1.2節(jié) 集合的基本運(yùn)算,第1.2.1節(jié) 并 第1.2.2節(jié) 交 第1.2.3節(jié) 差 第1.2.4節(jié) 對(duì)稱差,第1.2.1節(jié) 并,定義1.2.1：設(shè)A和B是集合，由屬于集合A或者屬于集合B的所有元素構(gòu)成的集合，稱為A和B的并，記作AB，也即 AB=x | xA或xB 例1：A=1，3，5，B=2，3，4，則： AB=1，2，3，4，5。 例2：A=a，b

8、，c，B=b，c，d，e，則： AB=a，b，c，d，e。,第1.2.1節(jié) 并,“并”運(yùn)算的文氏圖：,第1.2.1節(jié) 并,“并”運(yùn)算的性質(zhì)：1、AB= BA2、A(BC)= (AB)C3、AA= A4、A= A5、AU= U,第1.2.2節(jié) 交,定義1.2.2：設(shè)A和B是集合，由屬于A，B兩集合的所有共同元素構(gòu)成的集合，稱為A和B的交，記作AB，也即 AB=x | xA且xB 例1：A=1，3，5，B=2，3，4，則： AB=3。 例2：A=a，b，c，B=b，c，d，e，則： AB=b，c。,第1.2.2節(jié) 交,“交”運(yùn)算的文氏圖：,第1.2.2節(jié) 交,“交”運(yùn)算的性質(zhì)：1、AB= BA2、

9、A(BC)= (AB)C3、AA= A4、A = 5、AU= A,第1.2.2節(jié) 交,集合的并、交運(yùn)算規(guī)律： 設(shè)A,B,C為任意集合,則: 冪等律 AA=A , AA=A 交換律 AB=BA , AB=BA 結(jié)合律 (AB)C = A(BC) (AB)C = A(BC) 同一律 A=A , AU =A 零律 AU=U , A= ,第1.2.2節(jié) 交,并和交運(yùn)算有著密切聯(lián)系分配律： 定理1.2.1：設(shè)A，B，C是集合，則下列分配律成立 A(BC) = (AB)(AC) A(BC) = (AB)(AC) 證明：只證第一等式，第二等式的證明方法相同。（在黑板上演算）,第1.2.2節(jié) 交,并和交運(yùn)算有

10、著密切聯(lián)系吸收律： 定理1.2.2： 設(shè)A，B是集合，則下列吸收律成立 A(AB) = A A(AB) = A 證明：只證第一等式，第二等式的證明方法相同。（在黑板上演算）,第1.2.2節(jié) 交,并和交運(yùn)算有著密切聯(lián)系迪摩根律： 定理1.2.3： 設(shè)A，B是集合，則下列迪摩根律成立 (AB)=AB (AB)=AB 證明：只證第一等式，第二等式的證明方法相同。（在黑板上演算）,第1.2.2節(jié) 交,迪摩根律的推廣應(yīng)用： 對(duì)于3個(gè)集合A，B，C，則有： (ABC)=ABC (ABC)=ABC 對(duì)于n個(gè)集合A1，A2，An，則有： (A1A2An)=A1A2An (A1A2An)=A1A2An,第1.2

11、.2節(jié) 交,以上的運(yùn)算規(guī)律在證明其它等式中可直接引用,使得集合等式的運(yùn)算可用代數(shù)的方式進(jìn)行。 例3：設(shè)A，B是集合，證明下列等式。 （1） A(AB) =AB （2） (AB)(BA)(AB)=(AB) （3） (AB)(AB)=(AB)(AB) (在黑板上演算第(2)等式的證明過程）,第1.2.3節(jié) 差,定義1.2.3: 設(shè)A和B是集合，由所有屬于A但不屬于B的元素構(gòu)成的集合，稱為A減B的差，記作A-B，即AB =x | xA且xB 例1：對(duì)于下列集合 A=1，2，3，4，B=3，4，5，則： 差集 A-B=1，2，B-A=5 例2：A=1，2，3，B=4，5，6，則： 差集 A-B=1，2

12、，3,第1.2.3節(jié) 差,“差”運(yùn)算的文氏圖：,第1.2.3節(jié) 差,定理1.2.4: 設(shè)A，B是集合，則A-B=AB。 證明：（在黑板上演算） 例3：設(shè)A、B、C是集合，證明 (1) A-(BC) = (A-B)(A-C) (2)(A-B)(B-C)(C-A)=(ABC) (ABC) （在黑板上演算）,第1.2.4節(jié) 對(duì)稱差,定義1.2.4: 設(shè)A，B是集合，由所有屬于A但不屬于B或者屬于B但不屬于A的元素構(gòu)成的集合，稱為A和B的對(duì)稱差，記作A B，也即 AB = (AB) (BA) 例1：A=1，2，3，4，B=3，4，5，6， 則： AB=1，2，5，6， BA=1，2，5，6。,第1.2

13、.4節(jié) 對(duì)稱差,“對(duì)稱差”運(yùn)算的文氏圖：,第1.2.4節(jié) 對(duì)稱差,“對(duì)稱差”運(yùn)算的性質(zhì)： 1）AB = BA 2）(AB)C = A(BC) 3）AA = 4）A = A 5）AU = A,第1.2.4節(jié) 對(duì)稱差,定理1.2.5: 設(shè)A，B是集合，則: AB = (AB) (AB)。 證明：（在黑板上演算） 例2：(1)證明A(BC)=(AB)(AC) (2)設(shè)A，B是集合，若AB=，證明A=B。 （在黑板上演算）,集合運(yùn)算性質(zhì)的一些重要結(jié)果：,1）AA=A，AA=A。等冪律 2）AB=BA，AB=BA， AB=BA。交換律 3）(AB)C =A(BC)，(AB)C = A(BC)，(AB)C

14、 =A(BC)。結(jié)合律 4）A(BC) =(AB)(AC) A(BC) =(AB)(AC)。分配律 5）AB=AB，AB=AB。迪摩根律 6）A=A。,集合運(yùn)算性質(zhì)的一些重要結(jié)果：,7）AA=U，AA=。補(bǔ)余律 8）A=A，AU=A。同一律 9）AU=U，A=。零一律 10）A-B=AB。 11）AB=(A-B)(B-A)=(AB)-(AB)。 12）AA= 。 13） = U。 14）U = 。,第1.3節(jié) 包含排斥原理,定理1.3.1:(容斥原理)設(shè)A，B為有限集合，則 |AB|=|A|+|B|-|AB| 證明: （用文氏圖理解） a)當(dāng)A和B不相交，即AB=，則： |AB|=|A|+|B

15、|,第1.3節(jié) 包含排斥原理,證明: b)當(dāng)A和B相交不空，即AB，則： 由，AB=A(B-A)，且A和(B-A)不相交， 所以：|AB|=|A|+|B-A|。 由，B=(B-A)(AB)，且B-A和AB不相交， 所以：|B|=|(B-A)(AB)| =|(B-A)|+|(AB)|。 于是有：|(B-A)|=|B|-|(AB)|。 所以： |AB|=|A|+ |B|-|(AB)|。,第1.3節(jié) 包含排斥原理,三個(gè)有限集合A、B、C的包含排斥原理： |ABC|=|A|+|B|+|C|-|AB|-|AC| -|BC|+|ABC| 四個(gè)有限集合A、B、C、D的包含排斥原理： |ABCD|=|A|+|

16、B|+|C|+|D|-|AB| -|AC|-|AD|-|BC|-|BD|-|CD| +|ABC|+|ABD|+|ACD| +|BCD|-|ABCD|,第1.3節(jié) 包含排斥原理,例1：某班有學(xué)生38人，其中有20人參加合唱隊(duì)，有16人參加話劇隊(duì)，有8人既參加合唱隊(duì)又參加話劇隊(duì)。問有多少人既不參加合唱隊(duì)也不參加話劇隊(duì)？ 解：設(shè)A表示參加合唱隊(duì)的學(xué)生的集合， B表示參加話劇隊(duì)的學(xué)生的集合。 則：|A|=20，|B|=16，|AB|=8 所以，|AB|=|A|+|B|-|AB|=20+16-8=28 所以，參加了活動(dòng)（指合唱隊(duì)或話劇隊(duì)）的學(xué)生人數(shù)為28人，剩下者=38-28=10,第1.3節(jié) 包含排斥

17、原理,例2：某班有72人，其中選學(xué)PASCAL語言的有30人，選學(xué)C語言的有36人，選學(xué)FORTRAN語言的有29人；選學(xué)PASCAL和C語言的有12人；3門語言都選學(xué)的有5人；僅僅選學(xué)FORTRAN語言的有7人，試求： （1）僅選學(xué)兩門語言的人數(shù)。 （2）這3門語言都不選學(xué)的人數(shù)。 解： (黑板上演算),第1.3節(jié) 包含排斥原理,例3：求1250間能被2，3，5，7中任一個(gè)數(shù)整除的整數(shù)的個(gè)數(shù)。 解:設(shè)A表示1250間能被2整除的整數(shù)的集合， B表示1250間能被3整除的整數(shù)的集合， C表示1250間能被5整除的整數(shù)的集合， D表示1250間能被7整除的整數(shù)的集合。 用符號(hào)x表示對(duì)數(shù)x做取整運(yùn)

18、算，如3.7=3 (黑板上演算),小 結(jié),1.掌握集合、子集、空集、全集、補(bǔ)集等概念，熟悉常用的表示集合的方法以及用文氏圖來表示集合的方法，能判定元素與集合之間的關(guān)系。懂得兩集合間相等關(guān)系和包含關(guān)系的定義和性質(zhì)，能夠利用定義證明兩個(gè)集合相等。 2.掌握集合的四種基本運(yùn)算：并、交、差和對(duì)稱差的定義并熟記集合運(yùn)算的基本等式，能夠利用他們來證明更復(fù)雜的集合等式。 3.掌握冪集的定義及計(jì)算有限集的冪集所含元素個(gè)數(shù)所使用的方法和思想。 4.熟記簡(jiǎn)單情形的包含排斥原理并進(jìn)行計(jì)算。,補(bǔ)充內(nèi)容,第1.4節(jié) 抽象公理和羅素悖論 第1.5節(jié) 外延公理和子集公理 第1.6節(jié) 偶集公理和聯(lián)集公理 第1.7節(jié) 正則公理

19、和極小元 第1.8節(jié) 無窮公理和自然數(shù) 第1.9節(jié) 冪集公理,第1.4節(jié) 抽象公理和羅素悖論,抽象公理：任給一個(gè)性質(zhì)，都有一個(gè)滿足該性質(zhì)的客體所組成的集合。 (y)(x)(xy (x) 其中，(x)是不以y為自由變?cè)墓健?羅素悖論：“由不為自身的成員這一性質(zhì)的所有客體組成的集合”，會(huì)導(dǎo)出矛盾。 在抽象公理中，令(x)= (xx) (y)(x)(xy (xx) 取x=y，則(y)(yy (yy) 而 AB (AB)(AB),第1.4節(jié) 抽象公理和羅素悖論,對(duì)羅素悖論的理解：通過構(gòu)造一個(gè)性質(zhì)，使得根據(jù)“抽象公理”構(gòu)造的集合，存在問題。因此，抽象公理是不完備的。 從另一個(gè)角度看，“由不為自身的成

20、員”這一性質(zhì)所決定的客體是不存在的，所以對(duì)應(yīng)的集合應(yīng)該是空集。這樣理解“抽象公理”，就沒有問題了。 對(duì)于(x)= (xx)來說， 若x僅是元素，則xx無意義 若x是集合，則xx為假命題(aa?) (x)= (xx)本身就存在問題,第1.4節(jié) 抽象公理和羅素悖論,定義3.1.3：xy := (xy) 這里，“xy”表示“x不屬于y”，或“x屬于y為假”。 定義3.1.4：y為集合 := (x)(xyy=) 這里，“(xyy=)”表示“集合y具有成員”，或“集合y是空集”。,第1.5節(jié) 外延公理和子集公理,外延公理：如果兩個(gè)集合中各個(gè)元素都是相同的，則它們相等。 (x)(xA xB) = A=B

21、定義3.2.1：若A、B是任何兩個(gè)集合，當(dāng)且僅當(dāng)A、B兩個(gè)集合恰有相同的各成員時(shí)，則稱A、B是相等的兩個(gè)集合，記為A=B。 A=B (x)(xA xB),第1.5節(jié) 外延公理和子集公理,子集公理：對(duì)于任給一個(gè)集合A和集合的每一種性質(zhì)，存在一個(gè)集合B，它的成員恰是A中那些具有性質(zhì)的成員。 (B)(x)(xB xA (x) 其中，B不可在(x)中出現(xiàn)。 定義3.2.2：集合B是集合A的一個(gè)子集，當(dāng)且僅當(dāng)B的每個(gè)成員也是A的一個(gè)成員，記為BA。 BA := (x)(xB xA),第1.5節(jié) 外延公理和子集公理,定理3.2.1：x。 定理3.2.2：(x)(xA) A=。 定理3.2.3：AA。 AB

22、 BA = A=B。 AB BC = AC。 定理3.2.4：(AA)。 AB = (BA)。 AB BC = AC。,第1.6節(jié) 偶集公理和聯(lián)集公理,偶集公理：對(duì)于給定的任何兩個(gè)集合A、B，存在一個(gè)集合C，其成員恰是A和B。 (C)(x)(xC x=A x=B) 即： C=A，B 定義3.4.1：設(shè)集合A，B是一個(gè)偶集（即二元集），當(dāng)且僅當(dāng)A、B是集合。 A，B=y (x)(xy x=A x=B),第1.6節(jié) 偶集公理和聯(lián)集公理,聯(lián)集公理：對(duì)于任何一個(gè)集合A，存在一個(gè)集合C，C的成員恰是A的成員的成員。 (C)(x)(xC (B)(BA xB) 定義3.4.2：集合C是集合A的一個(gè)聯(lián)集，當(dāng)且

23、僅當(dāng)(x)(xC (B)(BA xB) 定義3.4.3：A := x|(B)(BA xB) 定義3.4.4：AB := x|xA xB 定義3.4.5：A := x|(B)(BA xB) 定義3.4.6：AB := x|xA xB,第1.6節(jié) 偶集公理和聯(lián)集公理,定理3.4.1：xA (B)(BAxB) xAB xA xB = = A=A (AB)=(A)(B) AB = AB AB = AB (A)(ABAC) = BC,第1.6節(jié) 偶集公理和聯(lián)集公理,定理3.4.2：AA=A AB=BA A(BC)=(AB)C A=A AAB AB = ACBC AC BC ABC AB AB=B,第1.

24、6節(jié) 偶集公理和聯(lián)集公理,定理3.4.3：xA (B)(BAxB)(B)(BA) = = A=A A,B=AB AB (C)(CA) = BA AB = BA,第1.6節(jié) 偶集公理和聯(lián)集公理,定理3.4.3：ABAC = BC (C)(CA)(D)(DB) = (AB)=(A)(B) AA (AB)C = (AC)(BC) (AB)C = (AC)(BC),第1.6節(jié) 偶集公理和聯(lián)集公理,定理3.4.4：xA-B xAxB A-A= A-(AB)=A-B A(A-B)=A-B (A-B)B=AB (AB)-B=A-B (AB)-B= (A-B)B= A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C),第1.7