離散數(shù)學(xué) 第三章：集合的基本概念和運(yùn)算課件

第3章集合的基本概念和運(yùn)算

§3.1集合的基本概念§3.2集合的基本運(yùn)算§3.3集合中元素的計(jì)數(shù)關(guān)于集合的有趣的例子在一個(gè)僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么誰給這位理發(fā)師刮臉？分析設(shè)C={x|x是不給自己刮臉的人}，b是這位理發(fā)師.一方面,如果bC，則b是不給自己刮臉的人；另一方面，由題意知，這位理發(fā)師b只給集合C中的人刮臉。所以b要給b刮臉，即bC;另一方面,如果bC，則b是要給自己刮臉的人；另一方面，由題意知，理發(fā)師只給自己不刮臉的人刮臉。所以b是不給自己刮臉的人，即bC。無論如何，都有bC和bC同時(shí)成立。這種情況稱為羅素悖論。§3.1集合的基本概念1.集合的概念沒有精確的定義,但一般認(rèn)為一個(gè)集合指的是可確定的可分辨的事物構(gòu)成的整體。元素：集合里所含的個(gè)體稱為集合的元素。1）集合的三要素：確定性，無序性，互異性。2）集合的元素：可以是任意類型的事物，也可以為一個(gè)集合。例如：3）可以用樹形結(jié)構(gòu)把集合與元素之間的關(guān)系表示出來。在每層次上，把集合作為一個(gè)結(jié)點(diǎn)，它的元素則作為它的兒子。A{b,c}ad{ak04yai}bcaq6umqud注:3.集合全部子集

推論.空集是唯一的.證明:假設(shè)存在兩個(gè)空集則由定理1知且從而例1.求A的全部子集.解:將A的子集從小到大分類;0元子集:1個(gè),1元子集:個(gè),2元子集:個(gè),3元子集:個(gè),注:一般的,對(duì)于n元子集A,它的m元子集共有個(gè),所以不同的子集總數(shù)有:定義：A的所有子集構(gòu)成的集合叫做A的冪集，記作P（A）.4.冪集例:設(shè)A={a,b,c},則符號(hào)化為:注:若A為n元集,則P(A)=2n個(gè)元素.例3:計(jì)算以下冪集:3.2集合的運(yùn)算及性質(zhì)一、集合的運(yùn)算集合的運(yùn)算，就是以給定集合為對(duì)象，按照確定的規(guī)則得到另外一些集合。1.集合的交定義1

設(shè)A，B為任意兩集合，由集合A和B的所有共同元素組成的集合S,稱為A和B的交集，記作A∩B。

S=A∩B={x|x∈A∧x∈B}用文氏圖表示如下：EAB例：A={0,2,4,6,8},B={1,2,3,4,5,6},則:A∩B={2,4,6}2.集合的并定義2

設(shè)A，B為任意兩集合，所有屬于A或?qū)儆贐的元素組成的集合S,稱為A和B的并集，記作A∪B。

S=A∪B={x|x∈A∨x∈B}用文氏圖表示如下：ABE例：設(shè)A={1,2,3,4},B={2,4,5}.則

A∪B={1,2,3,4,5}.3.集合的補(bǔ)定義3

設(shè)A，B為任意兩集合，所有屬于A而不屬于B的一切元素組成的集合S,稱為B對(duì)于A的補(bǔ)集，或稱相對(duì)補(bǔ)，記作A-B。

S=A-B={x|x∈A∧xB}={x|x∈A∧

(xB)}A-B也稱為集合A和B的差。用文氏圖表示如下：EAB例：設(shè)A={2,5,6},B={1,2,4,7,9},則A-B={5,6}定義5

設(shè)A，B為任意兩個(gè)集合，A與B的對(duì)稱差為集合S,其元素或?qū)儆贏,或?qū)儆贐,但不能既屬于A又屬于B,記作A⊕B。

A⊕B=(A–B)∪(B-A)或A⊕B=(A∪B)-(A∩B)用文氏圖表示如下：EAB例：設(shè)A={a,b,e},B={a,c,d},則A-B={b,e},B-A={c,d}A⊕B={b,e,c,d}4.集合的對(duì)稱差(6)零律

A∪E＝E

A∩?=?

(7)排中律 A∪~A=E(8)矛盾律

A∩~A=?(9)吸收律

A∪(A∩B)=A A∩(A∪B)=A(10)德摩根律

A-(B∪C)=(A-B)∩(A-C)

A-(B∩C)=(A-B)∪(A-C)

~(B∪C)=~B∩~C ~(B∩C)=~B∪~C ~?=E ~E=?(11)雙重否定律

~~A=A(4)補(bǔ)差轉(zhuǎn)換律A-B=A∩~B(6)對(duì)稱差運(yùn)算定律①交換律②結(jié)合律③∩對(duì)⊕滿足分配律④⑤⑥(消去律)其它的結(jié)果:設(shè)A1、A2為集合公式，欲證A1=A2，只須證A1

A2∧A2

A1，也即證對(duì)任意的x,有

x∈A1

x∈A2和x∈A2x∈A1

成立，把這兩個(gè)式子合到一起就是

x∈A1

x∈A2恒等式證明的兩種思路：（1）根據(jù)定義進(jìn)行證明（2）利用已有的集合恒等式證明新的恒等式總體上還是采用命題邏輯中的等值式，在敘述上采用半形式化的方法，其中?表示當(dāng)且僅當(dāng)，意即“等價(jià)”。例:證明德摩根律 證明~(B∪C)=~B∩~C證明：~(B∪C)={x|x~(B∪C)}={x|x(B∪C)}={x|x(B∪C)}={x|(xB∨xC)}={x|xB∧xC}={x|x~B∧x~C}=~B∩~C 練1：證明(A∪B)-C=(A-C)∪(B-C).證明:對(duì)于xx∈(A∪B)-C

?x∈(A∪B)

∧xC

?(

x∈A∨x∈B)∧xC

?(

x∈A∧xC)∨(x∈B∧xC)?x∈A-C∨x∈B-C

?x∈(A-B)∪(A-C)∴(A∪B)-C=(A-C)∪(B-C)3.3集合中元素的計(jì)數(shù)定義3.3.1

如果存在nN,使得集合A與集合{x|xN∧x<n}={0,1,2,…,n-1}的元素個(gè)數(shù)相同，就說集合A的基數(shù)是n,記作cardA=n或|A|=n.所謂基數(shù)，是表示集合中所含元素多少的量。顯然空集?的基數(shù)是0。定義3.3.2

設(shè)A為集合，如果存在自然數(shù)n（0也是自然數(shù)）,使得cardA=n，則稱集合A為有窮集，否則稱A為無窮集。例{a,b,c,d}為有窮集，而N,Z,Q,R為無窮集。對(duì)有限集合A，P(A)=2|A|.例設(shè)某校有運(yùn)動(dòng)員總數(shù)為70人，其中足球隊(duì)員38人，籃球隊(duì)員35人，排球隊(duì)員32人，其中有8人同時(shí)參加三個(gè)隊(duì)，試求僅同時(shí)參加兩個(gè)隊(duì)的隊(duì)員人數(shù)是幾人？

則又

在文氏圖中用A、B、C分別表示足球隊(duì)員、籃球隊(duì)員和排球隊(duì)員的集合

解答案：僅同時(shí)參加兩個(gè)隊(duì)的隊(duì)員人數(shù)是19人.

A38C32B35xyz8足球籃球排球包含排斥原理|A1∪A2|=|A1|+|A2|-|A1∩A2|推廣2:A1A2E|A∪

B∪

C|=|A|+|B|+|C||A∩

B||B∩

C||A∩

C|+|A∩

B∩

C|，例:一個(gè)班20人，都至少會(huì)排球、網(wǎng)球和籃球中的一種，其中會(huì)打排球的有12人、會(huì)打網(wǎng)球的有6人、會(huì)打籃球的有14人，既會(huì)打排球又會(huì)打籃球的有6人，既會(huì)打網(wǎng)球又會(huì)打籃球的有5人，三種都會(huì)的有2人，問同時(shí)會(huì)排球和網(wǎng)球的人有幾個(gè)？解：設(shè)幾個(gè)集合：A=會(huì)打排球的人,B=會(huì)打網(wǎng)球的人,C=會(huì)打籃球的人，