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

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

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

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

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

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

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

設 a0＝1，a1＝1，

ai+1＝ai

+ai-1（i1）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

沒有元素的集合稱為空集,用表示。空集可表示為：Φ={x|xx}定義3.5

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

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計算機科學與工程學院§3.2集合的運算定義3.6

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

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

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

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

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

|xA∧xB}

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

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

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

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

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

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

BA∪Ｂ

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

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

定義3.11

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

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

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

2）對于空集，有：

2＝{}

2{}＝{,{}}

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

1）如BA，則2B2A

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

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