離散數(shù)學(xué)第1章 集合論

離散數(shù)學(xué)

關(guān)于離散數(shù)學(xué)我們在說離散數(shù)學(xué)的時候，我們在說什么？2023/2/17現(xiàn)實世界計算機世界50－22023/2/17關(guān)于離散數(shù)學(xué)一切計算機學(xué)科的基礎(chǔ)！哲學(xué)數(shù)學(xué)語言學(xué)。。。離散算法網(wǎng)絡(luò)。。。。。。Wearehere!50－32023/2/17關(guān)于成績

出勤（10-15%）考試+態(tài)度70%-80%作業(yè)（10-15%）

50－42023/2/17第一篇預(yù)備知識第一章集合論50－52023/2/171.0內(nèi)容提要集合的概念1集合的表示方法2集合間的關(guān)系3集合的運算4無限集合5集合的概念1集合的表示方法2特殊集合550－62023/2/171.1本章學(xué)習(xí)要求重點掌握一般掌握了解11集合的概念及集合間關(guān)系2集合的表示3集合運算及定律4冪集P(A)

31集合的遞歸指定法表示2了解無限集的基本概念21集合的歸納法表示2集合的對稱差運算50－72023/2/171.2集合一、集合的概念集合（SET）由指定范圍內(nèi)的某些特定對象聚集在一起構(gòu)成。指定范圍內(nèi)的每一個對象稱為這個集合的元素(element)中國所有真皮沙發(fā)的聚集指定范圍特定對象50－82023/2/17二、集合的記法通常用帶(不帶)標號的大寫字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用帶（不帶）標號的小寫字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。50－92023/2/17固定的符號0,1,2,…自然數(shù)集合N…,-2,-1,0,1,2,…

整數(shù)集合

Zp/q,p,q是整數(shù)，且q≠0

有理數(shù)集合

Q

實數(shù)集合

R復(fù)數(shù)集合

C50－102023/2/171.2.1集合的表示方法集合是由它包含的元素完全確定的，為了表示一個集合，通常有：

枚舉法隱式法（敘述法）歸納法遞歸指定文氏圖50－112023/2/171、枚舉法（顯示法）--列出集合中全部元素或部分元素的方法叫枚舉法例1.2.1

（1）A＝{a，b，c，d}

（2）B={0,1,4,9,16,…,n2,…}適用場景：一個集合僅含有限個元素一個集合的元素之間有明顯關(guān)系

50－122023/2/17枚舉法的優(yōu)缺點是一種顯式表示法優(yōu)點：具有透明性缺點：在表示具有某種特性的集合或集合中元素過多時受到了一定的局限，而且，從計算機的角度看，顯式法是一種“靜態(tài)”表示法，如果一下子將這么多的“數(shù)據(jù)”輸入到計算機中去，那將占據(jù)大量的“內(nèi)存”。50－132023/2/172、隱式法（敘述法）通過刻畫集合中元素所具備的某種特性來表示集合的方法稱為敘述法（隱式法）一般表示方法：P＝{x|P(x)}適用場景：一個集合含有很多或無窮多個元素；一個集合的元素之間有容易刻畫的共同特征其突出優(yōu)點是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性。代表元X所具有的性質(zhì)p50－142023/2/17例1.2.2（1）A={x|x是“discretemathematics”中的所有字母}；（2）Z={x|x是一個整數(shù)}；（3）S={x|x是整數(shù)，并且x2＋1=0}；（4）Q+={x|x是一個正有理數(shù)}。50－152023/2/173、歸納法

歸納法是通過歸納定義集合，主要由三部分組成：第一部分：基礎(chǔ)。指出某些最基本的元素屬于某集合；第二部分：歸納。指出由基本元素造出新元素的方法；第三部分：極小性。指出該集合的界限。注意：第一部分和第二部分指出一個集合至少包括的元素，第三部分指出一個集合至多要包含的元素50－162023/2/17例1.2.3集合A按如下方式定義：（1）0和1都是A中的元素；（2）如果a,b是A中的元素，則ab,ba也是A中的元素；（3）有限次使用(1)、(2)后所得到的字符串都是A中的元素。試指出其定義方式。并舉出集合A中的3個元素50－172023/2/174、遞歸指定集合通過計算規(guī)則定義集合中的元素例1.2.4

設(shè)a0＝1，

ai+1＝2ai（i0）定義S＝{a0，a1，a2，...}

＝{ak|k0}，試寫出集合S中的所有元素。

50－182023/2/175、文氏圖解法

文氏圖解法是一種利用平面上點的集合作成的對集合的圖解。一般用平面上的圓形或方形表示一個集合。AA50－192023/2/171.2.2集合與元素的關(guān)系元素與集合之間的“屬于關(guān)系”是“明確”的。對某個集合A和元素a來說，a屬于集合A，記為aA或者a不屬于集合A，記為aA兩者必居其一且僅居其一。例如，對元素2和N，就有2屬于N，即2N，對元素-2和N，就有-2不屬于N，即-2N。50－202023/2/17羅素悖論例

在一個很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰給這位理發(fā)師刮臉？解：設(shè)C＝{x|x是不給自己刮臉的人}b是這位理發(fā)師

如bC，則bC； 如bC，則bC。50－212023/2/171.2.3集合與集合的關(guān)系1、互異性－集合中的元素都是不同的，凡是相同的元素，均視為同一個元素；{1,1,2}={1,2}2、確定性－能夠明確加以“區(qū)分的”對象；3、無序性－集合中的元素是沒有順序的。

{2,1}={1,2}一、集合的三大特征50－222023/2/17例1.2.5

設(shè)E={x|(x-1)(x-2)(x-3)=0},x∈R}F={x|(x∈Z+)且(x2＜12)}。試指出集合E和F中的元素。解集合E={1,2,3}，F(xiàn)={1,2,3}。

顯然，集合E,F中的元素完全相同，我們稱這樣的兩個集合相等

二、外延性原理A＝B當且僅當A與B具有相同的元素，否則，AB。50－232023/2/17例1.2.6

設(shè)A={BASIC,PASCAL,ADA}，B={ADA,BASIC,PASCAL}，請判斷A和B的關(guān)系。解根據(jù)集合元素的無序性和外延性原理可得，A=B。因為集合A=B，所以B中的每個元素都是A中的元素，我們稱集合A包含集合B。50－242023/2/17上述包含定義的數(shù)學(xué)語言描述為：

BA對任意x，如xB，則xA。三、包含和真包含關(guān)系定義1.2.1

設(shè)A,B是任意兩個集合，如果

B的每個元素都是A的元素，則稱B是A的子集合，簡稱子集(Subset)，這時也稱A包含B，或B被A包含，記作AB或BA，稱“”或“”為包含關(guān)系(InclusionRelation)。如果B不被A所包含，則記作BA。顯然，對任意集合A，都有AA。50－252023/2/17例1.2.7設(shè)A={BASIC,PASCAL,ADA}，B={ADA,BASIC,PASCAL}，請判斷A和B之間的包含關(guān)系。解根據(jù)集合間包含關(guān)系的定義知，AB且AB。又從例1.2.6知，集合A=B，于是我們有：定理1.2.2

設(shè)A、B是任意兩個集合，則AB，BAA=B50－262023/2/17真包含關(guān)系定義1.2.2

設(shè)A,B是任意兩個集合，如果

BA并且A≠B則稱B是A的真子集(ProperSubset)，記作BA，稱“”為真包含關(guān)系(ProperlyInclusionRelation)。如果B不是A的真子集，則記作BA。上述真子集的數(shù)學(xué)語言描述為：BA對任意x，如xB，則xA,并且，yA，但是yB50－272023/2/17判斷下列集合之間是否具有真包含關(guān)系。（1）{a,b}和{a,b,c,d}；（2）{a,b,c,d}和{a,b,c,d}。解根據(jù)真子集的定義，有（1）{a,b}{a,b,c,d}；（2）因為{a,b,c,d}＝{a,b,c,d}，所以{a,b,c,d}不是{a,b,c,d}的真子集。例1.2.850－282023/2/17例1.2.9設(shè)A={a}是一個集合，B={{a},{{a}}}，試問{A}∈B和{A}B同時成立嗎？

∵

{A}={{a}}，{{a}}∈B∴{A}∈B成立；

∵

{A}={{a}}，{a}∈B∴{A}B成立。解{A}∈B和AB同時成立。分析50－292023/2/17

1.2.4幾個特殊集合定義1.2.3

不含任何元素的集合叫做空集(EmptySet)，記作Φ?？占梢苑柣癁棣?{x|x≠x}空集是客觀存在的。

1、空集例1.2.10

設(shè)A={x|(x∈R)且(x2<0)}，試列舉集合A中的所有元素。解A=Φ。定理1.2.3（1）空集是一切集合的子集；（2）空集是絕對唯一的。50－302023/2/17定理1.2.3（2）的證明

對“唯一性”的證明通常采用反證法。即假設(shè)“不唯一”，得出矛盾，從而說明結(jié)論正確假設(shè)Φ1和Φ2是兩個空集，且Φ1≠Φ2，再證明Φ1＝Φ2，出現(xiàn)矛盾，從而說明結(jié)論成立。那么怎么證明Φ1＝Φ2？分析根據(jù)定理1.2.3（1）空集是一切集合的子集∴Φ1Φ2，Φ2

Φ1，根據(jù)定理1.2.2，Φ1＝Φ2

Φ1Φ2，Φ2Φ1與Φ1≠Φ2矛盾50－312023/2/17定義1.2.4

在一個相對固定的范圍內(nèi)，包含此范圍內(nèi)所有元素的集合，稱為全集或論集(UniversalSet)，用U或E表示。用文氏圖描述如下:U2、全集50－322023/2/17例1.2.12（1）在立體幾何中，全集是由空間的全體點組成；（2）在我國的人口普查中，全集是由我國所有人組成。定理1.2.5

全集是相對唯一的.50－332023/2/17集合A中元素的數(shù)目稱為集合A的基數(shù)（basenumber)，記為|A|。如|A|是有限的，則稱集合A為有限集，如|A|是無限的，則稱集合A為無限集。例1.2.13

求下列集合的基數(shù)。（1）A=Φ

；（2）B={Φ}；（3）C={a,b,c}；（4）D={a,{b,c}}。解

|A|=0，|B|=1，|C|=3，|D|=2。有限集和無限集50－342023/2/17m元子集定義1.2.6

如果一個集合A含有n個元素，則稱集合A為n元集，稱A的含有m個(0≤m≤n)元素的子集為A的m元子集。任給一個n元集，怎樣求出它的全部m元子集？例1.2.14

設(shè)A={1,2}，求出A的全部m元子集?！遪=|A|=2，m≤n∴m=0,1,2?！喈攎=0時，得到0元子集：Φ；當m=1時，得到1元子集：{1},{2}；當m=2時，得到2元子集：{1,2}。解

A的全部m元子集是Φ、{1}、{2}和{1,2}。分析50－352023/2/17子集總數(shù)一般來說，對于n元集A，它的m（0mn）元子集有個，所以不同的子集總數(shù)有：

＝(1+1)n＝2n所以，n元集共有2n個子集。50－362023/2/17冪集定義1.2.7

設(shè)A為任意集合，把A的所有不同子集構(gòu)成的集合叫做A的冪集(powerset)，記為P(A)或2A。其符號化表示為P(A)＝{x|一切xA}該集合又稱為集族(familyofset)。

對集族的研究在數(shù)學(xué)方面、知識庫和表處理語言以及人工智能等方面都有十分重要的意義。50－372023/2/17例1.2.15計算下列冪集（1）P(Φ)；（2）P({Φ})；（3）P({a,{b,c}})。解

（1）P(Φ)={Φ}；（2）P({Φ})={Φ,{Φ}}；（3）P({a,{b,c}})={Φ,{a},{{b,c}},{a,{b,c}}}。顯然，若集合Ａ有ｎ個元素，則集合Ａ共有2|A|個子集，即：|P(A)|＝2|A|。50－382023/2/171.2.5集合的運算定義1.2.8

設(shè)A、B是兩個集合，(1)并集AB={x|xA或xB}(2)交集AB={x|xA且xB}(3)差集A-B={x|xA且xB}(4)補集=U-A={x|xU且xA}(Ａ′,～Ａ,AC)(5)對稱差集AB={x|(xA)且(xB)或(xB)且(xA)}UAB并集UAB差集ABU對稱差集UAB交集UA補集50－392023/2/17推廣A1∪A2∪A3∪……∪An={x|(xA1)或(xA2)或……或(xAn)}＝A1∩A2∩A3∩……∩An＝{x|(xA1)且(xA2)且……且(xAn)}當n無限增大時，可以記為：＝A1∪A2∪A3∪…＝A1∩A2∩A3∩…50－402023/2/17定理1.2.51.等冪律:Ａ∪Ａ=Ａ；Ａ∩Ａ=Ａ；2.交換律:Ａ∪Ｂ=Ｂ∪Ａ;Ａ∩Ｂ=Ｂ∩Ａ3.結(jié)合律:Ａ∪(Ｂ∪Ｃ)=(Ａ∪Ｂ)∪Ｃ； Ａ∩(Ｂ∩Ｃ)=(Ａ∩Ｂ)∩Ｃ；4.恒等律:Ａ∪Φ=Ａ； Ａ∩Ｕ=Ａ；5.零律:Ａ∪Ｕ=Ｕ； Ａ∩Φ=Φ；6.分配律:Ａ∩(Ｂ∪Ｃ)=(Ａ∩Ｂ)∪(Ａ∩Ｃ)

Ａ∪(Ｂ∩Ｃ)=(Ａ∪Ｂ)∩(Ａ∪Ｃ)7.吸收律:A∩(A∪B)=A; A∪(A∩B)=A；

50－412023/2/17定理1.2.5(續(xù)）8.A-A=Φ；9.A-B=A-(A∩B)；10.(A-B)-C=A-(B∪C)；11.A∪(B-A)=A∪B；12.A-B=A∩；13.否定律：；14.DeMorgan律：；15.矛盾律：

A∩＝Φ；16.排中律：A∪＝U。50－422023/2/17證明：DeMorgan律：分析定理1.2.2

設(shè)A、B是任意兩個集合，則AB，BAA=B

50－432023/2/17證明（a）：由①、②知，①②50－442023/2/17證明（b）：（b）在中，用和分別取代A和B，則有50－452023/2/171.3無限集質(zhì)變無限集合無法用確切的個數(shù)來描述，因此，無限集合有許多有限集合所沒有的一些特征，而有限集合的一些特征也不能任意推廣到無限集合中去，即使有的能推廣，也要做某些意義上的修改。有限集無限集量變50－462023/2/171.3.1可數(shù)集合和不可數(shù)集合

二十世紀初，集合成為數(shù)學(xué)的基本概念之后，由馮?諾依曼（VonNeumann，J.）用集合的方式來定義自然數(shù)取得了成功，提出了用序列Φ，{Φ}，{Φ,{Φ}}，{Φ,{Φ},{Φ,