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

第二章集合（set)

集合的概念在現(xiàn)代數(shù)學(xué)中是一個(gè)非常重要的概念。本節(jié)主要介紹集合及其表示、集合的運(yùn)算，序偶，集合的笛卡爾乘積。2023/2/41Zhengjin,CSU個(gè)體和集合之間的關(guān)系集合不能精確定義，只能直觀描述：一個(gè)集合就是若干事物的全體。組成集合的每個(gè)事物叫做這個(gè)集合的元素。小寫拉丁字母表示個(gè)體：a、b、c、d…大寫拉丁字母表示集合：A、B、C、D…2023/2/42Zhengjin,CSU個(gè)體與集合之間的關(guān)系：屬于關(guān)系。

對于某個(gè)個(gè)體a和某個(gè)集合A而言，a只有兩種可能1）a屬于A，記為aA，同時(shí)稱a是A中的元素。2）a不屬于A，記為aA，稱a不是A中的元素。個(gè)體a屬于A或者a不屬于A，二者居其一且只居其一。

2023/2/43Zhengjin,CSU集合的表示法

(1)文字表示法用文字表示集合的元素，兩端加上花括號。{在座的同學(xué)}{高等數(shù)學(xué)中的積分公式}

(2)元素列舉法將集合中的元素逐一列出，兩端加上花括號。{1，2，3，4，5}，{風(fēng)，馬，牛}{2，4，6，8，10，…}

2023/2/44Zhengjin,CSU(3)謂詞表示法

{x︱p(x)}p表示x所滿足的性質(zhì)例如：{x︱x2=1}={1，-1}{y︱y是開區(qū)間(a，b)上的連續(xù)函數(shù)}2023/2/45Zhengjin,CSU（4）歸納定義法

用歸納法定義一個(gè)非空集合A時(shí)，包括以下三步：1)基本項(xiàng)（保證A不空)

已知某些元素屬于A2)歸納項(xiàng)（生成規(guī)則）

給出一組規(guī)則，從A中的元素出發(fā)，依據(jù)這些規(guī)則所獲得的元素，仍然都是A中的元素。（這是構(gòu)造A的關(guān)鍵步驟）3）極小化（通常省略）如果集合S也滿足（1）和（2），且SA，則S=A。這一點(diǎn)保證集合A的唯一性。

2023/2/46Zhengjin,CSU例1如果論域是整數(shù)集I，那么能被3整除的正整數(shù)集合S用歸納法可定義如下：（1）（基礎(chǔ)）3S，（2）（歸納）如果xS和yS，則x+yS

2023/2/47Zhengjin,CSU集合的特殊情況1、不含任何元素的集合稱為空集，記為φ2、含討論問題所需全部元素的集合稱為全集，記為∪

3、稱含有有限個(gè)元素的集合為有限集合4、含有無限個(gè)元素的的集合稱為無限集合或無限集5、集合A中元素的個(gè)數(shù)（或基數(shù)或集合的勢）記為:|A|

提醒:一個(gè)集合也可以是別的集合的元素，如：{a，b，{a，b}}{a，b，φ，{{a，b}}}

2023/2/48Zhengjin,CSU集合與集合之間的關(guān)系

設(shè)A，B是兩個(gè)集合1）若對于A中的每個(gè)元素x，都有x屬于B，則稱A包含在B中，記為:A

B。同時(shí)稱A是B的子集。2）若A中的每個(gè)元素都屬于B，且B中的每個(gè)元素都屬于A，則稱A等于B，記為A=B。

(A=B當(dāng)且僅當(dāng)AB且BA）

3)集合的包含關(guān)系具有傳遞性:即

若AB且BC，則AC2023/2/49Zhengjin,CSU子集的兩種特殊情況（平凡子集）：1）空集是任一集合的子集。2）任何集合都是它自己的子集。2023/2/410Zhengjin,CSU例1：確定下列各命題的真假：(a)

(b)(c){}(d){}(e){a，b}{a，b，c，{a，b，c}}(f){a，b}{a，b，c，{a，b，c}}(g){a，b}{a，b，c，{a，b}}(h){a，b}{a，b，c，{a，b}}例2求出下列集合的全部子集：（a){，{}}

(b)

{{a，b}，{a，a，b}，{b，a，b}}2023/2/411Zhengjin,CSU集合上的運(yùn)算定義2設(shè)A，B是兩個(gè)集合1）A∩B={x︱xA∧xB}，稱A∩B為A與B的交集，稱∩為集合交運(yùn)算。2）A∪B={x︱xA∨xB}，稱A∪B為A與B的并集，稱∪為集合并運(yùn)算。3)A–B={x︱xA∧xB}，稱A–B為A與B的差集例1設(shè)A={1，2，3，4，5}，B={2，5，7}，則A∪

B={1，2，3，4，5，7}A∩

B={2，5}A–B={1，3，4}2023/2/412Zhengjin,CSU

定理1

設(shè)U是全集，A，B，C是U的三個(gè)子集1）A∩A=A，A∪A=A2）A∩U=A，A∪U=U3）A∩=，A∪=A4）A∩B=B∩A，A∪B=B∪A5）(A∩B)∩C=A∩(B∩C)，(A∪B)∪C=A∪(B∪C)6）A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)

2023/2/413Zhengjin,CSU定理2設(shè)A，B，C為三個(gè)集合，則1）AA∪B，A∩BA；2）若AC且BC，則A∪BC；3）若CA且CB，則CA∩B。4)A-BA5)A-=A6)A∩(B-C)=(A∩B)-(A∩C)；定理3

設(shè)A，B為兩個(gè)集合，則下面三式等價(jià)。1）AB2）A∪B=B3)A∩B=A圖形表示：2023/2/414Zhengjin,CSU集合上的補(bǔ)運(yùn)算(一元運(yùn)算）

設(shè)U是全

集，A是U的子集。

~A={xxU∧xA}=U-A稱~A是A關(guān)于U的補(bǔ)集，稱~為補(bǔ)運(yùn)算。例2設(shè)U={a，b，c，d，e}，A={c，d}，則~A=定理4

設(shè)U是全

集，A，B是U的子集。則1~(~

A)=A；2）若AB，則~

B~

A；3）若A=

B，則~

A=

~

B；4）~U=，~

=U。5)A∪~A=U，A∩~A=2023/2/415Zhengjin,CSU定理5

設(shè)A，B為兩個(gè)集合，則1）~(A∪B)=~

A∩~B2）~(A∩B)=~A∪~B2023/2/416Zhengjin,CSU集合的環(huán)和（對稱差）運(yùn)算定義：設(shè)A，B是兩個(gè)集合，

AB=(A-B)∪(B-A)

={x︱(xA∧xB)∨(xB∧xA)}稱AB為A和B的環(huán)和，稱為集合環(huán)和運(yùn)算。由環(huán)和運(yùn)算和并、差運(yùn)算的定義知

AB=(A∪B)–(AB)例：設(shè)A={a，b，c，d，e}，B={a，b，c，f，g}，則

2023/2/417Zhengjin,CSU冪集定義：設(shè)A是集合，A的所有子集組成的集合稱為A的冪集，記為：2A或p(A)。2A={xxA}

例1：如果A={a，b}，則2A={，{a}，，{a，b}}例2：設(shè)A={，{}}，則2A={，{}，{{}}，{，{}}}

定理1設(shè)集合A是有限集合，A

=n，則2A=2A

定理2設(shè)A，B是兩個(gè)集合。那么，A=B當(dāng)且僅當(dāng)2A=2B。2023/2/418Zhengjin,CSU有限集的計(jì)數(shù)原理設(shè)A和B都是有限集合，則以下公式成立:|A∪B|=|A|+|B|-|A

B||A

B|<=min(|A|，|B|)|

AB|=|A|+|B|-2|A

B||A-B|>=|A|-|B||A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1A2|-|A2A3|-|A1A3|+|A1A2A3|2023/2/419Zhengjin,CSU有限集計(jì)數(shù)原理P682023/2/420Zhengjin,CSU集合的廣義并和廣義交

定義6：如果集合C中的成員本身又都是集合，則集合C稱為集類(或稱為搜集)。

設(shè)C={A1，A2，A3，…An}(1)C的成員的并，記為：∪C，稱為C的廣義并∪C=A1∪A2∪…∪An（2）C的成員的交，記為：∩C，稱為C的廣義交∩C=A1∩A2∩…∩An例：設(shè)A={{1，2，4}，{3，4，5}，{4，6}}則A廣義交：∩A={1，2，4}∩{3，4，5}∩{4，6}=ΦA(chǔ)的廣義并：∪A={1，2，4}∪{3，4，5}∪{4，6}={1，2，3，4，5，6}2023/2/421Zhengjin,CSU數(shù)學(xué)歸納法對于以自然數(shù)為論域的xP(x)形式的歸納證明過程如下:第一數(shù)學(xué)歸納法(1)（基礎(chǔ)）先證明P(0)是真。(2)（歸納)再證明n(P(n)

→P(n+1))是真即先假設(shè)“P(n)對任意取定的自然數(shù)n是真，再由此推出P(n+1)也真，一旦證明了P(n)

→P(n+1)對任意n是真，則用全稱推廣規(guī)則得n(P(n)

→P(n+1))再根據(jù)數(shù)學(xué)歸納法第一原理得出xP(x)。2023/2/422Zhengjin,CSU第二數(shù)學(xué)歸納法原理n[k[k<n

→P(k)]

→P(n)]

∴xP(x)證明過程:(1)首先證明P(0)為真。(2)證明:對任意n>0，如果P(k)對一切k<n成立，那么P(n)成立。數(shù)學(xué)歸納法2023/2/423Zhengjin,CSU集合的笛卡爾乘積

由任意兩個(gè)元素x和y組成的集合{x，y}為偶集。因?yàn)閧x，y}={y，x}，所以這種偶集只能叫無序偶集，簡稱無序偶。

有序偶:它不僅與含有的元素x，y有關(guān)，還與x，y出現(xiàn)的次序有關(guān)。這樣的偶集稱為有序偶，并記為：<x,y>

例如，用<x，y>表示平面直角坐標(biāo)系下的橫坐標(biāo)為x且縱坐標(biāo)為y的點(diǎn)時(shí)，則<x，y>和<y，x>在xy時(shí)就代表不同的點(diǎn)，因而就不相同。

2023/2/424Zhengjin,CSU定義1有序偶的集合定義：若x，y為任意兩個(gè)元素，令<x，y>={{x}，{x，y}}稱<x，y>為由x，y組成的二元序偶，簡稱有序偶或序偶。

提醒：此種定義顯然體現(xiàn)了二元元素的有序性。但有序偶的定義不只一種，還有別的定義方法，只要能體現(xiàn)有序性就可以了用集合定義有序偶2023/2/425Zhengjin,CSU定理1<x，y>=<u，v>當(dāng)且僅當(dāng)x=u且y=v（根據(jù)序偶的定義即可得出。）定義2

設(shè)n是正整數(shù)，x1，x2，…，xn是任意的元素。若n=1，則令<x1>=x1

若n=2，則令<x1,x2>={{x1},{x1，x2}}

若n>2，則令

<x1,x2,…，xn>=<<x1,x2,…,xn-1>,xn>我們稱<x1，x2，…，xn>為由x1，x2，…，xn

組成的n元序偶，并稱每個(gè)xi為它的第i個(gè)分量。（這樣就定義了n元序偶）2023/2/426Zhengjin,CSU定義3設(shè)n是正整數(shù)，A1，A2，…，An為n個(gè)任意集合。A1×A2×…×An={<x1，x2，…，xn>若1≤i≤n，則xi∈Ai}稱A1×A2×…×An為A1，A2，…，An的n維笛卡爾乘積。

定義4設(shè)A，B是兩個(gè)非空集合

A×B={<a，b>｜aA∧bB}(即所有第一元素在A中，第二元素在B中的序偶的集合)稱A×B是A與B的叉積（笛卡兒積）集合。記:A×A=A2

2023/2/427Zhengjin,CSU（1）在A×B中，A稱為前集，B稱為后集。前集與后集可以相同，也可以不同。若前集與后集相同，則記為A×A=A2。（2）規(guī)定A×Φ=Φ=Φ×B。若偶對的第一分量或第二分量不存在就沒有偶對存在，故規(guī)定它們的叉積集合為空集。（3）由于偶對中的元素是有序的，因此一般地說A×B≠B×A。(除非A=B，或者A、B中至少有一個(gè)為空集)

2023/2/428Zhengjin,CSU例1

A={a，b，c}，B={0，1}A×B={<a，0>，<a，1>，<b，0>，<b，1>，<c，0>，<c，1>}B×A={<0，a>，<0，b>，<0，c>，<1，a>，<1，b>，<1，c>}A2={<a，a>，<a，b>，<a，c>，<b，a>，<b，b>，<b，c>，<c，a>，<c，b>，<c，c>}2023/2/429Zhengjin,CSU定理2：設(shè)A，B是兩集合，則AB=A*B(即AB中元素的個(gè)數(shù)等于A中元素個(gè)數(shù)乘以B中元素個(gè)數(shù))。定理3

設(shè)A，B，C，D是四個(gè)非空集合，那么A×B=C×D當(dāng)且僅當(dāng)A=C且B=D。20