《離散數學課件》1-2集合的基本概念

1

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

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

10/69第一次數學危機:發(fā)現了“無理數”

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

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

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

N代表自然數集,{0,1,2,…}

Z代表整數集,{…,-2,-1,0,1,2,…}

Q代表有理數集

R代表實數集

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

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

隸屬關系的層次結構例A={a,{b,c},d,{kcko8ys}}{b,c}

Ab,c

A{psrcfet}As2hqsqgAd

A

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

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

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

a?

S當且僅當a具有性質ξ

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

S不是自己的元素，二者居其一且只居其一。容易說明我們假定S是集合是錯誤的。如果S?S，那么與性質矛盾；如果S?S，那么S滿足性質，矛盾。20/69定義1：A,B是二個集合，對于任意的x，假設x?A，那么x?B，我們說集合A是集合B的子集，也說集合B包含集合A，記為A?B。假設A不是B的子集,記為A?B。也說B不包含A。三、集合的包含關系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空集?設K是一個集合，K={x?R│x2+1=0}

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

①A?A

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

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

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

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

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

{a,b,c}

是相等的兩個集合?；ギ愋?9/69集合的特點集合中的元素沒有任何方式的順序。例如：

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

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

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

{a,{a},?}

都是兩個確定的集合。確定性集合的表示方法集合的特性集合與元素的關系集合與集合的關系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例設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例設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集合運算性質定理：設A、B、C是三個任意集合，那么：冪等律A∪A=AA∩A=A交換律A∪B=B∪AA∩B=B∩A結合律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，假設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)假設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在何條件下成立？

解：根據分析當且僅當A∩(B∩C)=?時,等式成立。首先，假假設(A-B)∪(A-C)=A,要證明A∩(B∩C)=?。用反證法。假設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再證，假設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,假設x?B，那么有x?A-B,進而x?(A-B)；假設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 所以結論得證： (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的所有子集為元素構成的集合，稱它為集合A的冪集合，記為ρ(A)

，也記為P(A)、2A

。即ρ(A)

={x|x

A}例設A={0,1}，那么ρ(A)={?,{0},{1},{0,1}}設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}}}計數如果|A|=n，那么|P(A)|=2n51/69四、有限并與交設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)設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}集合的運算小結54/696.3全集和集合的補6.3.1全集、集合的補集6.3.2根本運算定理55/69

一、全集定義:

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

二、補運算：ā、

A

定義：設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結論成立。 “”設A∪B=U且A∩B=?，那么B=B∩U=B∩(A∪ā)=(B∩A)∪(B∩ā)=?∪(B∩ā)=(A∩ā)∪(B∩ā)=(A∪B)∩ā=U∩ā=ā任一集合的補集合是唯一的。60/69推論：設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