離散數(shù)學(xué)(第3章)陳瑜

陳瑜Email：chenyu.inbox@2/2/2023離散數(shù)學(xué)計算機學(xué)院2/2/20231計算機科學(xué)與工程學(xué)院第三章集合及其運算集合是數(shù)學(xué)中最基本的概念之一,是現(xiàn)代數(shù)學(xué)的重要基礎(chǔ),它已深入到各種科學(xué)和技術(shù)領(lǐng)域中。對計算機科學(xué)與技術(shù)的工作者來說,更是不可缺少的工具。本書各部分貫穿著集合論的思想。計算機科學(xué)的許多分支都大量用到集合的概念和知識,如數(shù)據(jù)結(jié)構(gòu),程序語言,數(shù)據(jù)庫,人工智能等。集合論的主要特點:研究問題的廣泛性,分析思考問題的抽象性,處理問題的統(tǒng)一性,特別便于描述和研究離散對象及其關(guān)系。2/2/20232計算機科學(xué)與工程學(xué)院§3.1集合論的基本概念我們對于“在一定范圍內(nèi)的討論的對象組成的整體”給予一個名字，叫集合（SET）,其中的對象稱為這個集合的“成員”或“元素”（ELEMENT）。通俗地講，所謂集合，就是某些客體的一個確定的表或匯總。（任意客體的聚集）通常用帶（不帶）標號的大寫字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用帶（不帶）標號的小寫字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。一、集合的概念2/2/20233計算機科學(xué)與工程學(xué)院二、集合的表示法：

集合是由它所包含的元素完全確定的，為了表示一個集合，通常有：枚舉法、隱式法（敘述法）、歸納法、遞歸指定、巴科斯范式BNF、文氏圖、特征函數(shù)等表示方法。

1、枚舉法：此方法就是將集合中的元素全部列出來（或者只列出一部分元素，而其余部分可以從前后關(guān)系中很明顯的知道）。

2/2/20234計算機科學(xué)與工程學(xué)院2、隱式法（敘述法）：用一集合之元素所具有的共同性質(zhì)來刻劃這個集合。一般表示方法：P＝{x|P(x)}1）“｜”前面的x代表集合P中的任意元素2）“｜”后面的P(x)表示x必須具有性質(zhì)P其突出優(yōu)點是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性例1：S1＝{x|x是正偶數(shù)}S2＝{x|（xZ）并且（x>0)}S3＝{x|x是四川大學(xué)的學(xué)生}S4＝{x|x是“l(fā)etter”中的字母}2/2/20235計算機科學(xué)與工程學(xué)院3、歸納法：歸納法是通過歸納定義集合，主要由三部分組成。第一部分：基礎(chǔ)。它指出某些最基本的元素屬于某集合；第二部分：歸納。指出由基本元素造出新元素的方法；第三部分：極小性。指出該集合的界限。第一部分和第二部分指出一個集合至少要包括的元素，第三部分指出一個集合至多要包含的元素。例2：集合M是按如下方式定義：

1）每一個英文字母都是M中的元素；

2）如果P、Q是M中的元素，則PQ、QP也是M中的元素；

3）有限次使用（1）、（2）后所得到的字符串都是M中的元素。2/2/20236計算機科學(xué)與工程學(xué)院4、遞歸指定集合通過計算規(guī)則定義集合中的元素例3：

設(shè) a0＝1，a1＝1，

ai+1＝ai

+ai-1（i1）

S＝{a0，a1，a2，...}＝{ak

|k0}2/2/20237計算機科學(xué)與工程學(xué)院5、巴科斯范式BNF表示法

BNF（BackusNormalForm）常常用來定義高級程序設(shè)計語言的標識符或表達式集合。

例4：在PASCAL語言中，標識符集定義如下：

<Letter>:＝<Letter>{<Letterordigit>}<Letterordigit>:＝<Letter>|<digit>2/2/20238計算機科學(xué)與工程學(xué)院6、文氏圖（Venn）

文氏圖解是一種利用平面上點的集合作成的對集合的圖解。一般用平面上的圓形或方形表示一個集合。AA2/2/20239計算機科學(xué)與工程學(xué)院7、特征函數(shù)表示法定義3.1

設(shè)A是集合,稱為A的特征函數(shù)。（它表明了集合與其成員的關(guān)系）對某個集合Ａ和元素ａ來說，ａ或者屬于集合Ａ，或者不屬于集合Ａ，兩者必居其一，且僅居其一。ａ是集合Ａ的元素或ａ屬于Ａ，記為：aAａ不是Ａ的元素或ａ不屬于Ａ，記為：aA2/2/202310計算機科學(xué)與工程學(xué)院羅素悖論例

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

如bC，則bC； 如bC，則bC。2/2/202311計算機科學(xué)與工程學(xué)院羅素悖論例

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

如bC，則bC； 如bC，則bC。此例說明：“集合”是一個無法精確定義的數(shù)學(xué)概念之一2/2/202312計算機科學(xué)與工程學(xué)院三、集合之間的關(guān)系與子集

定義3.2：設(shè)有集合A與B，若A中的每一個元素都是B中的元素，則稱A是B的子集或B包含A，記為：AB或BA

上述包含定義又可形象地敘述為：

BA對任意x，如xB，則xA。定義3.3：設(shè)A、B是任意兩個集合，如果AB且BA，則稱A與B相等，記為A=B。符號化表示為：

A=BAB且BA。如果A和B不相等，則記作AB。2/2/202313計算機科學(xué)與工程學(xué)院基數(shù)集合A中元素的數(shù)目稱為集合A的基數(shù)，記為|A|。如|A|是有限的，則稱A為有限集合如|A|是無限的，則稱A為無限集合定義3.4

沒有元素的集合稱為空集,用表示?？占杀硎緸椋害?{x|xx}定義3.5

全集用U或E表示,它表示在某個固定范圍內(nèi)的所有對象的全體。性質(zhì)1：全集只能是相對唯一的，而非絕對唯一的性質(zhì)1：空集是絕對唯一的。2/2/202314計算機科學(xué)與工程學(xué)院性質(zhì)3對任意一個集合A，都有：A對任意一個集合A，都有：AA(自反性）對任意集合A、B、C，如果AB并且BC，則AC(傳遞性）對任意集合A、B，A＝B當且僅當AB并且BA(反對稱性）2/2/202315計算機科學(xué)與工程學(xué)院外延性原理在集合中，凡是相同的元素，均認為是同一個元素，并可將相同的元素合并成一個元素，即是說，這里所談的“元素”都是“確定的”，能夠明確加以“區(qū)分的”對象。我們認為集合中的元素都是不同的并且是無序的。

A＝B當且僅當A與B具有相同的元素，否則，AB例1.8集合A＝{a，b，c，b}B＝{a，b，c}C＝{c，b，a}A=B=C例1.9E＝{x|（xZ）并且（x2-3x+2＝0）}F＝{1，2}G＝{1，2，2，1，6/3}E＝F＝G2/2/202316計算機科學(xué)與工程學(xué)院§3.2集合的運算定義3.6

設(shè)A、B是全集U的兩個子集合，則A∪B＝{xU|xA∨xB}

仍是一個集合，稱為集合A與B的并集，稱“∪”為并運算（UnionOperation）。用文氏圖表示如下：UAB2/2/202317計算機科學(xué)與工程學(xué)院交集定義3.7

設(shè)A，B是全集U的兩個子集合，則A∩B＝{xU|xA∧xB}

仍是一個集合，稱為集合A與B的交集，稱“∩”為交運算（IntersectionOperation）。用文氏圖可表示如下：UAB2/2/202318計算機科學(xué)與工程學(xué)院推廣=A1∪A2∪A3∪……∪An=A1∩A2∩A3∩……∩An當n無限增大時，可以記為：=A1∪A2∪A3∪……，=A1∩A2∩A3∩……。2/2/202319計算機科學(xué)與工程學(xué)院差集定義3.8

設(shè)A，B是全集U的兩個子集合，則A-B＝{xU

|xA∧xB}

仍是一個集合，稱為集合A與B的差集，稱“-”為差運算（SubtractionOperation)，Ａ-Ｂ又叫相對補集。用文氏圖可表示如下：UAB2/2/202320計算機科學(xué)與工程學(xué)院補集定義3.9

設(shè)U是全集，A是U的子集，則＝U-A＝{x|xU并且xA}

仍是一個集合，稱它為集合A的補集(也可記為Ａ＇，～Ａ，AC等），“￣”稱為補運算（ComplementOperation）。用文氏圖可表示如下：UA2/2/202321計算機科學(xué)與工程學(xué)院對稱差定義3.10：設(shè)A，B是兩個集合，則

AB={x|(xA)并且(xB)或(xB)并且(xA)}=(A-B)∪(B-A)

仍是一個集合，稱它為Ａ與Ｂ的對稱差集，稱“－”為對稱差運算。用文氏圖可表示如下：ABU

圖中的粉紅部分為AB。2/2/202322計算機科學(xué)與工程學(xué)院關(guān)于運算“差”和“補”的幾個性質(zhì)：1.AA∪Ｂ

BA∪Ｂ

；2.Ａ∩ＢＡＡ∩ＢB；3.AＢＡ∪Ｂ=Ｂ或Ａ∩Ｂ=Ａ；4．Ａ∪＝U；5．Ａ－Ｂ＝Ａ∩；6．ＡＢ=（Ａ∩）∪（Ｂ∩）2/2/202323計算機科學(xué)與工程學(xué)院定理3.1：1.冪等律：Ａ∪Ａ＝Ａ；Ａ∩Ａ＝Ａ；2．交換律：Ａ∪Ｂ＝Ｂ∪Ａ；Ａ∩Ｂ＝Ｂ∩Ａ；3．結(jié)合律：Ａ∪（Ｂ∪Ｃ）＝（Ａ∪Ｂ）∪Ｃ；Ａ∩（Ｂ∩Ｃ）＝（Ａ∩Ｂ）∩Ｃ；4．零一律：Ａ∪Ｕ＝Ｕ；Ａ∩Φ＝Φ；Ａ∪Φ＝Ａ；Ａ∩Ｕ＝Ａ；5．分配律：Ａ∩（Ｂ∪Ｃ）＝（Ａ∩Ｂ）∪（Ａ∩Ｃ）；Ａ∪（Ｂ∩Ｃ）＝（Ａ∪Ｂ）∩（Ａ∪Ｃ）。6．吸收律：A∩（A∪B）＝A；A∪（A∩B）=A；7．否定律：

2/2/202324計算機科學(xué)與工程學(xué)院8．DeMorgan律：9．矛盾律：A∩=Φ；A∪=U；2/2/202325計算機科學(xué)與工程學(xué)院§3.4集合的冪集和笛卡爾集★★一、冪集

定義3.11

由集合A的所有子集組成的集合稱為A的冪集，記為(A)或2A。2A=(A)＝{x|一切xA}

這種以集合為元素構(gòu)成的集合，常稱為集合的集合或集族（FamilyofSet）。對集族的研究在數(shù)學(xué)方面、知識庫和表處理語言以及人工智能等方面都有十分重要的意義。2/2/202326計算機科學(xué)與工程學(xué)院例10：設(shè)Ａ＝{ａ,ｂ}，則：

1）2A＝{,{ａ},{ｂ},{ａ,ｂ}}

2）對于空集，有：

2＝{}

2{}＝{,{}}

3）({1,{2,3}})={Φ,{1},{{2,3}},{1,{2,3}}}定理3.2：設(shè)A和B是兩個集合，

1）如BA，則2B2A

2）若集合Ａ有ｎ個元素，則集合Ａ共有2n個子集，即：|(A)|＝2n。2/2/202327計算機科學(xué)與工程學(xué)院二.笛卡爾積(直積)Descartes

定義3.12:設(shè)給定n≥1個集合A1,A2,…,An,稱A1×A2×…×An={<a1,a2,…,an>︱aiAi,1≤i≤n}