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

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

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

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

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

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

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

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

ai+1＝ai

+ai-1（i1）

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

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

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

例4：在PASCAL語言中，標(biāo)識(shí)符集定義如下：

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

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

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

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

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

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

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

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

上述包含定義又可形象地?cái)⑹鰹椋?/p>

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

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

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

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

A＝B當(dāng)且僅當(dāng)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計(jì)算機(jī)科學(xué)與工程學(xué)院§3.2集合的運(yùn)算定義3.6

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

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

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

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

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

|xA∧xB}

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

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

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

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

仍是一個(gè)集合，稱它為Ａ與Ｂ的對(duì)稱差集，稱“－”為對(duì)稱差運(yùn)算。用文氏圖可表示如下：ABU

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

BA∪Ｂ

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

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

定義3.11

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

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

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

2）對(duì)于空集，有：

2＝{}

2{}＝{,{}}

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

1）如BA，則2B2A

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

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