《離散數(shù)學(xué)課件》1-2集合的基本概念

1

集合論2集合論局部第6章集合第7章〔二元〕關(guān)系第8章函數(shù)3/69康托集合論——公理集合論德國數(shù)學(xué)家康托(G.Cantor)樸素集合論:十九世紀七十年代悖論公理集合論:在二十世紀初數(shù)學(xué)思想的最驚人的產(chǎn)物，在純粹理性的范疇中人類活動的最美的表現(xiàn)?？赡苁沁@個時代所能夸耀的最巨大的工作。4/69康托GeorgCantor，1845－19181845年3月3日生于彼得堡。1856年全家遷居法蘭克福。先后就學(xué)于蘇黎世大學(xué)、哥廷根大學(xué)、法蘭克福大學(xué)和柏林大學(xué)，主要學(xué)習(xí)哲學(xué)、數(shù)學(xué)和物理。在柏林大學(xué)，他受到著名分析學(xué)家魏爾斯特拉斯的影響，對純粹數(shù)學(xué)產(chǎn)生了興趣。1867年，他以求不定方程ax2+by2+cz2=0的整數(shù)解〔其中，a、b、c為任意整數(shù)〕的博士論文獲哲學(xué)博士學(xué)位。5/69羅素〔BertrandArthurWilliamRussell，1872-1970〕著名的英國數(shù)學(xué)家、邏輯學(xué)家。1890年劍撟大學(xué)學(xué)習(xí)數(shù)學(xué)和哲學(xué)。1901年開始與懷特海(Whitehead)合作，經(jīng)過10年的奮戰(zhàn)，寫成3卷本巨著《數(shù)學(xué)原理》。羅素還是2l世紀最有影響的哲學(xué)家之一。1920年應(yīng)邀來中國講學(xué)一年。1950年獲諾貝爾文學(xué)獎。1964年創(chuàng)設(shè)羅素和平基金會。6/69理發(fā)師難題西班牙的塞維利亞有一個理發(fā)師，這位理發(fā)師有一條極為特殊的規(guī)定：他只給那些“不給自己刮胡子”的人刮胡子。7/69羅素悖論與第三次數(shù)學(xué)危機“數(shù)學(xué)大廈的基石”竟然出現(xiàn)了明顯的“裂縫”，那么人類消耗數(shù)千年心血建立起來的“數(shù)學(xué)殿堂”，會不會倒塌呢？一時間，數(shù)學(xué)界眾說紛紜，這就是數(shù)學(xué)史上著名的“第三次數(shù)學(xué)危機”?！榜押场?希爾伯特……蔡梅羅:找到擺脫困境的方法8/69ZF公理系統(tǒng)數(shù)學(xué)家們創(chuàng)造了公理化集合論，明確提出形成集合的原那么，且規(guī)定只能按照這些確定的原那么形成集合，以防止的一些集合論的悖論。最著名的一個系統(tǒng)是由蔡梅羅(ErnstZermelo)1908年提出，后經(jīng)弗蘭克爾(AbrahamA.Fraenkel)等人改進而建立的。人們稱之為ZF系統(tǒng)。9/69第二次數(shù)學(xué)危機:關(guān)于微積分在牛頓和萊布尼茨發(fā)現(xiàn)了微積分的年代里,老是有那么幾個敵對分子跟他們作對,其中有一位愛爾蘭的大主教貝克萊就譏諷牛頓的“一剎那”是“已死量的幽靈”。還有一位意大利的數(shù)學(xué)教授格蘭蒂把

1/2=1-1+1-1+...=(1-1)+(1-1)+...=0這樣的式子看作是"從虛無創(chuàng)造萬有"等等不一而足.

10/69第一次數(shù)學(xué)危機:發(fā)現(xiàn)了“無理數(shù)”

畢達格拉斯的一個弟子發(fā)現(xiàn)邊長為1的正方形的對角線是不能用任何比例來表示的。對于畢氏學(xué)派來說,這是天大的罪過,結(jié)果被扔進海里喂了鯊魚。11/69第六章集合6.1集合的根本概念6.1.1集合的定義6.1.2集合的表示6.1.3集合的包含關(guān)系6.1.4集合的特點12/696.1集合的根本概念集合是最根本的數(shù)學(xué)概念之一，由于它太根本了，所以不能用更根本的概念來定義它。集合是不能精確定義的數(shù)學(xué)概念。但是，這并不影響我們?nèi)ダ斫馑驼莆账?3/69每一個人都知道許多集合邏輯值T,F可以組成一個集合,記為{T,F},真值集。數(shù)0，1可以組成一個集合,記為{0,1},真值集。

數(shù)0,1,2,3,4,5,6,7,8,9可以組成一個集合,阿拉伯數(shù)字集。數(shù)0，1,3,

4可以組成一個集合。二十六個英文字母可以組成一個集合,英文字母集例如：14/69一、集合與元素集合：某些確定的、能夠區(qū)分的對象的聚合。元素：組成一個集合的那些對象稱為這一集合的元素和成員。用大寫字母代表集合，用小寫英文字母代表集合的元素。15/69常用的集合

N代表自然數(shù)集,{0,1,2,…}

Z代表整數(shù)集,{…,-2,-1,0,1,2,…}

Q代表有理數(shù)集

R代表實數(shù)集

R+={x│x∈R,x>0}是表示非負的實數(shù)集R2={(x,y)│x,y∈R}是XOY坐標平面上點的集合。16/69集合與元素的關(guān)系如果a是集合A的一個元素，就叫做a屬于集合A，這時記為a?A

。如果a不是集合A中的一個元素，就叫做a不屬于A，這時記為a?A。對于任給的一個對象a和任給的一個集合A，或者a屬于A，或者a不屬于A，二者必居其一，不可得兼。

隸屬關(guān)系的層次結(jié)構(gòu)例A={a,{b,c},d,{g0ycimi}}{b,c}

Ab,c

A{q0cikg0}Amqss0c0Ad

A

18/69二、集合的表示(1)列舉出這個集合中的所有元素。 ?A={a,b,c}

?B={1,3,5}(2)利用元素所具有的性質(zhì)來表示。 ?D={x│x2-3x+2=0,x∈R}

?E={x│x是南京理工大學(xué)學(xué)生}一般地，S={a│a具有性質(zhì)ξ}表示

a?

S當且僅當a具有性質(zhì)ξ

。描述法枚舉法19/69羅素(B.Russell)悖論S={A│A是不以自身為元素的集合,即A?A}S是集合嗎？如果我們假定S是集合，那么S是自己的元素，

S不是自己的元素，二者居其一且只居其一。容易說明我們假定S是集合是錯誤的。如果S?S，那么與性質(zhì)矛盾；如果S?S，那么S滿足性質(zhì)，矛盾。20/69定義1：A,B是二個集合，對于任意的x，假設(shè)x?A，那么x?B，我們說集合A是集合B的子集，也說集合B包含集合A，記為A?B。假設(shè)A不是B的子集,記為A?B。也說B不包含A。三、集合的包含關(guān)系21/69例{1，2}?{1，2，3}{1，3}?{1，3，2，4}{1}?{1，2}1?{1，2}1∈{1，2}22/69例：是否存在這樣兩個集合，其中一個既是另一個的子集，又是它的元素？{1}∈{1，{1}}

{1}?{1，{1}}23/69空集?設(shè)K是一個集合，K={x?R│x2+1=0}

。我們都知道集合K中什么元素也沒有。這樣沒有一個元素的集合稱為空集。我們用?來表示空集合。24/69命題1(p76)A是任意集合，?是空集，那么

①A?A

②??A證明：①對于任意的x，假設(shè)x?A,那么顯然有x?A，所以A?A.用反證法：假設(shè)?不包含于A，那么存在x，x??，但x?A。顯然這與?是空集矛盾。故??A。25/69定義2(p76)A,B是兩個集合，假設(shè)A?B，且B?A,那么說A與B是相等的兩個集合，記為A=B。假設(shè)A?B且A≠B，說A是B的真子集，記為A?B。26/69命題2：空集是唯一的。證明：設(shè)?1，?2

是兩個空集合。由命題1，?1??2

且?2??1故?1=?2

27集合之間的關(guān)系包含〔子集〕ABx(xAxB)不包含A?Bx(xAxB)相等A=BABBA不相等AB真包含ABABAB不真包含AB注意和是不同層次的問題28/69四、集合的特點僅考慮集合所包含的不同的元素，也就是說集合中元素重復(fù)出現(xiàn)沒有意義。例如：

{a,a,b,c,c},

{a,b,c}

是相等的兩個集合。互異性29/69集合的特點集合中的元素沒有任何方式的順序。例如：

{a,b,c}{c,a,b}

是相等的兩個集合。無序性30/69集合的特點對集合中的元素沒有任何的限制，也就是一個集合中的元素之間彼此獨立，可以毫不相干；一個集合也可以是另一個集合的元素。例如：

{a,2,華盛頓,中國人}

{a,{a},?}

都是兩個確定的集合。確定性集合的表示方法集合的特性集合與元素的關(guān)系集合與集合的關(guān)系3132/696.2集合的根本運算6.2.1集合的并、交、差6.2.2集合的對稱差6.2.3文氏圖6.2.4集合的冪集合6.2.5多個集合的并與交33/69并運算：A∪BA∪B={x│x?A或x?B}其元素是所有的或者屬于集合A，或者屬于集合B的元素組成。

A∪B34/69交運算：A∩BA∩B={x│x?A且x?B}其元素是所有的既屬于集合A，又屬于集合B的元素組成。

A∩B35/69差運算：A–BA–B={x│x?A且x?B}其元素是所有的屬于集合A，但不屬于集合B的元素組成。

A–B36/69例設(shè)A、B是兩個任意集合，那么以下兩條件等價A∪B=AB?A證明：①②對于任意的x?B,有x?A∪B=A， 即x(xBxA) 于是B?A。②①顯然，A?A∪B。 對于任意的x?A∪B,那么x?A或x?B，由于B?A，故總有x?A，即證得A∪B?A。因此A∪B=A。37/69例設(shè)A、B是兩個任意集合，那么以下兩條件等價A∩B=BB?A證明：①②對于任意的x?B,有 x?B=A∩B， 于是x?A,因此證得B?A。②① 顯然，A∩B?B。 對于任意的x?B,那么由于B?A，故x?A，從而x?A∩B，即證得B?A∩B。因此A∩B=B。38/69集合運算性質(zhì)定理：設(shè)A、B、C是三個任意集合，那么：冪等律A∪A=AA∩A=A交換律A∪B=B∪AA∩B=B∩A結(jié)合律A∪〔B∪C〕=〔A∪B〕∪CA∩〔B∩C〕=〔A∩B〕∩C分配律A∪〔B∩C〕=〔A∪B〕∩〔A∪C〕A∩〔B∪C〕=〔A∩B〕∪〔A∩C〕39/69例試證：A∪(B∩C)=(A∪B)∩(A∪C)證明：1、對于任意的x，假設(shè)x?A∪(B∩C)，那么x?A，或x?B∩C。當x?A，那么 x?A∪B且x?A∪C， 于是 x?(A∪B)∩(A∪C)； 當x?B∩C，那么x?B且x?C，就有 x?A∪B,且x?A∪C， 于是 x?(A∪B)∩(A∪C)。 故A∪(B∩C)?(A∪B)∩(A∪C)2、再證明：(A∪B)∩(A∪C)?A∪(B∩C)假設(shè)x?(A∪B)∩(A∪C)，那么x?A∪B,且x?A∪C由x?A∪B得 x?A或x?B；〔1〕由x?A∪C得 x?A或x?C?！?〕于是，當x?A，有 x?A∪(B∩C)；當x?A，由(1)和(2)，x?B且x?C，有 x?B∩C，所以x?A∪(B∩C)。故(A∪B)∩(A∪C)?A∪(B∩C)綜上知，A∪〔B∩C〕=〔A∪B〕∩〔A∪C〕。41/69證明：對于任意的x，x?A∪(B∩C)，x?Ax?B∩Cx?A〔x?Bx?C〕〔x?Ax?B〕〔x?Ax?C〕x?A∪Bx?A∪Cx?〔A∪B∩x?A∪C〕

例試證：A∪(B∩C)=(A∪B)∩(A∪C)42/69例1(p78)(A-B)∪(A-C)=A在何條件下成立？

解：根據(jù)分析當且僅當A∩(B∩C)=?時,等式成立。首先，假假設(shè)(A-B)∪(A-C)=A,要證明A∩(B∩C)=?。用反證法。假設(shè)A∩B∩C≠?,那么?x?A∩B∩C,所以x?A，x?B，x?C。由x?A，x?B,有x?A-B,又由x?A，x?C,有x?A-C,所以有x?(A-B)∪(A-C)=A。矛盾說明A∩B∩C=?。分析：A的元素a既是B的元素、也是C的元素，那么等式不成立。43/69再證，假設(shè)A∩(B∩C)=?,那么(A-B)∪(A-C)=A成立。1、對于任意的x?(A-B)∪(A-C),那么有x?A-B或x?A-C,即有x?A且x?B,或x?A且x?C,于是有x?A,所以(A-B)∪(A-C)?A。2、對于任意的x?A,假設(shè)x?B，那么有x?A-B,進而x?(A-B)；假設(shè)x?B,那么x?A∩B，由于A∩(B∩C)=?,那么x?C,即有x?A-C,進而x?(A-B)∪(A-C)；所以有A?(A-B)∪(A-C)。綜合得到(A-B)∪(A-C)=A成立。44/69二、對稱差：A⊕B

A⊕B={x│x?A且x?B,或x?B且x?A}其元素是所有的或者屬于A不屬于B，或者屬于B不屬于A。

A⊕B由定義，不難知：A⊕B=(A–B)∪(B–A)A⊕A=?A⊕?=A45/69命題1(p79)A⊕B=(A∪B)–(A∩B)

證明：對于任何一個x,x?A⊕Bx?A–Bx?B–A?！瞲?Ax?B〕〔x?Bx?A〕〔x?Ax?B〕〔x?Ax?A〕〔x?Bx?B〕〔x?Bx?A〕〔x?Ax?B〕〔x?Bx?A〕〔x?Ax?B〕〔x?Bx?A〕〔x?A∪B〕〔x?A∩B〕〔x?A∪B〕x?A∩Bx?(A∪B)–(A∩B)46/69命題3(p79)〔A⊕B〕⊕C=A⊕〔B⊕C〕

47/69命題3(p79)〔A⊕B〕⊕C=A⊕〔B⊕C〕

證：記 P={x?A且x?B且x?C}, Q={x?B且x?A且x?C}, S={x?C且x?A且x?B}, T={x?A且x?B且x?C},那么容易驗證：(A⊕B)⊕C=P∪Q∪S∪T A⊕(B⊕C)=P∪Q∪S∪T 所以結(jié)論得證： (A⊕B)⊕C=A⊕(B⊕C)PQST48/69例2(p80)A⊕B=A⊕C，證明B=C。證明：因為A⊕B=A⊕C所以A⊕(A⊕B)=A⊕(A⊕C)從而有〔A⊕A〕⊕B=〔A⊕A〕⊕C即?⊕B=?⊕C故B=C49/69三、冪集定義3：A是一個集合，存在一個集合，它是由A的所有子集為元素構(gòu)成的集合，稱它為集合A的冪集合，記為ρ(A)

，也記為P(A)、2A

。即ρ(A)

={x|x

A}例設(shè)A={0,1}，那么ρ(A)={?,{0},{1},{0,1}}設(shè)B={a,b,c}，那么ρ(B)={?,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}50/69例P(

)={

}，

P({

})={

,{

}}

P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}計數(shù)如果|A|=n，那么|P(A)|=2n51/69四、有限并與交設(shè)Pi(1≤i≤k)是k個任意集合,A1

A2

…Ak=={x|x

A1

x

A2

…

x

Ak}A1

A2

…Ak=={x|x

A1

x

A2

…

x

Ak}52/69推論(p67)設(shè)A,Pi(1≤i≤k)是k+1個集合,那么〔分配率對有限并、有限交都成立。〕集合根本運算的定義并

A

B={x|x

A

x

B}交

A

B={x|x

A

x

B}相對補

A

B={x|x

A

x

B}對稱差

A

B=(A

B)

(B

A)=(A

B)(A

B)

53冪集ρ(A)

={x|x

A}集合的運算小結(jié)54/696.3全集和集合的補6.3.1全集、集合的補集6.3.2根本運算定理55/69

一、全集定義:

我們在研究某一個具體問題時，往往規(guī)定一個集合，使所涉及的集合都是它的子集合，稱這個集合為全集，記為U(或E)。全集是個有相對性的概念，不同的問題，可以規(guī)定不同的全集。56/69

二、補運算：ā、

A

定義：設(shè)A是一個集合,U是全集合，我們稱集合U–A為A的補集，記為ā或

A

，即有：

ā={x│x?A且x?U}UAā57/69定理1A是一個任意集合，那么

A∪?

=AA∩U=A58/69定理2A是一個任意集合，那么A∪ā=UA∩ā

=?59/69定理3ā=B當且僅當A∪B=U且A∩B=?證明： “”由定理1結(jié)論成立。 “”設(shè)A∪B=U且A∩B=?，那么B=B∩U=B∩(A∪ā)=(B∩A)∪(B∩ā)=?∪(B∩ā)=(A∩ā)∪(B∩ā)=(A∪B)∩ā=U∩ā=ā任一集合的補集合是唯一的。60/69推論：設(shè)A是任意一個集合，那么61/69定理4

德·摩根定律三、運算定律

(A

B)=A

B

(A

B)=A

B62證明：

(A∩B)=A∪

B對任意的x，x?(A∩B)x?Ux?A∩B。x?U〔x?Ax?B〕x?U〔x?Ax?B〕x?U