第二篇集合與關系

集合論是現(xiàn)代各科數(shù)學的基礎，它是德國數(shù)學家康托（GeogCantor,1845?1918）

于1874年創(chuàng)立的，1876?1883年康托一系列有關集合論的文章，對任意元的集合進行

了深入的探討，提出了關于基數(shù)、序數(shù)和良序集等理論，奠定了集合論深厚的基礎，19

世紀90年代后逐漸為數(shù)學家們采用，成為分析數(shù)學、代數(shù)和兒何的有力工具。

隨著集合論的發(fā)展，以及它與數(shù)學哲學密切聯(lián)系所作的討論，在1900年前后出現(xiàn)了

各種悖論，使集合的發(fā)展一度陷入僵滯的局面。1904~1908年，策墨羅（Zermelo）列

出了第一個集合論的公理系統(tǒng)，它的公理，使數(shù)學哲學中產(chǎn)生的一些矛盾基本上得到了

統(tǒng)一，在此基礎上以后就逐漸形成了公理化集合論和抽象集合論，使該學科成為在數(shù)學

中發(fā)展最為迅速的一個分支。

現(xiàn)在，集合論已經(jīng)成為內(nèi)容充實、實用廣泛的一門學科，在近代數(shù)學中占據(jù)重要地

位，它的觀點已滲透到古典分析、泛函、概率、函數(shù)論、信息論、排隊論等現(xiàn)代數(shù)學各

個分支，正在影響著整個數(shù)學科學。集合論在計算機科學中也具有十分廣泛的應用，計

算機科學領域中的大多數(shù)基本概念和理論幾乎均采用集合論的有關術語來描述和論證，

成為計算機科學工作者必不可少的基礎知識。集合論可作為數(shù)學學科的通用語言，一切

必要的數(shù)據(jù)結構都可以利用集合這個原始數(shù)據(jù)結構而構造出來，計算機科學家或許也可

以利用這種方法。

本篇介紹集合論的基礎知識，主要內(nèi)容包括集合及其運算、性質(zhì)、序偶、關系、映

射、函數(shù)、基數(shù)等。

第2-1章集合及其運算

§2-1-1集合的概念及其表示

一、集合的概念

“集合”是集合論中的一個原始的概念，因此它不能被精確地定義出來。一般地說,

把具有某種共同性質(zhì)的許多事物，匯集成一個整體，就形成一個集合。構成這個集合的

每一個事物稱為這個集合的一個成員（或一個元素），構成集合的這些成員可以是具體

東西，也可以是抽象東西。例如：教室內(nèi)的桌椅；圖書館的藏書；全國的高等學校；自

然數(shù)的全體；程序設計語言C的基本字符的全體等均分別構成一個集合。通常用大寫的

英文字母表示集合的名稱；用小寫的英文字母表示元素。若元素。屬于集合/記作

aEA,讀作屬于Z"。否則，若a不屬于4,就記為。仁“，讀作"。不屬于工"。

一個集合，若其組成集合的元素個數(shù)是有限的，則稱作“有限集”，否則就稱作“無限

集”。

集合的表示方法有兩種：--種是列舉法乂稱窮舉法，它是將集合中的元素全部列出

來，元素之間用逗號“，”隔開，并用花括號“{}”在兩邊括起來，表示這些元素構成

整體。

例2-1-1.1A=(a,b,c,d};5={1,2,3,…}；

D=(桌子，臺燈，鋼筆，計算機，掃描儀，打印機};E={a,a2,a3.

集合的另一種表示方法叫做謂詞法又叫敘述法，它是利用一項規(guī)則，概括集合中元

素的屬性，以便決定某一事物是否屬于該集合的方法。設x為某類對象的?般表示，P(x)

為關于X的?個命題，我們用{x|P(X)}表示“使P(x)成立的對象X所組成的集合”，其

中豎線“I”前寫的是對象的一般表示，右邊寫出對象應滿足(具有)的屬性。

例2-1-1.2全體正奇數(shù)集合表示為={x|x是正奇數(shù)},

所有偶自然數(shù)集合可表示為￡={同2|相且加wN}其中2物表示2能整

除

［0』］上的所有連續(xù)函數(shù)集合表示為qo11］={/(x)|/(x)在［0,1］上連續(xù)}

集合的元素也可以是集合。例如S={a,{l,2},p,{q}},/

a{1,2}P⑷

................./\I

但必須注意：q&{q},而qeS,同理1e{1,2},{1,2}GS,12q

而1定S。

兩個集合相等是按下述原理定義的。外延性原理：兩個集合相等，當且僅當兩個集

合有相同的元素。兩個集合力，8相等，記作/=8,兩個集合不相等，記作力

集合中的元素是無次序的，集合中的元素也是彼此不相同的。

例如:{1,2,4}={1,4,2},{1,2,4}={1,2,2,4},

{{1,2},4}工{1,2,4},{1,3,5,…}={x|x是正奇數(shù)}。

集合中元素可以是任何事物(如例2-1-1.Do不含任何元素的集合稱為空集，記為

由。例如，方程/+1=0的實根的集合是空集。

二、集合與集合間的關系

“集合”、“元素”、元素與集合間的“屬于”關系是三個沒有精確定義的原始概念,

對它們僅給出了直觀的描述，以說明它們各自的含義?，F(xiàn)利用這三個概念定義集合間的

相等關系，集合的包含關系，集合的子集和基集等概念。

定義2-1-L1設力，8是任意兩個集合，如果/中的每一個元素都是8的元素，則

稱Z是8的子集，或Z包含于8內(nèi)，或8包含力。記作4=8,或8=/。

即AqB0Vx(xEAxGB)

可等價地表示為47BoVx(xe6—>x任4)。

例2?1?L3設N為自然數(shù)集合，Q為一切有理數(shù)組成的集合。R為全體實數(shù)集合，

C為全體復數(shù)集合，貝1JNJQJRJC,

{1}N,{1,1.2,9.9}c2，{6,哈qR。

如果/不是8的子集，則記為/<Z8(讀作N不包含在8內(nèi))，顯然，

AuBo3x((xGJ)A(x5))o

集合間的包含關系具有下述性質(zhì)：

2-1-1.自反性AQA；

2.傳遞性(Z18)A(3qC)nG4qC)。

證明：采用邏輯演繹的方法證明。

(1)A^BP

(2)Vx((xeZ)->(xeB))T(1)E

(3)(?eJ)->(<7eB)US(2)

(4)BjCp

⑸Vx((x￡8)f(X￡C))T(4)E

(6)(Q￡5)f(a￡C)US(5)

⑺(aEA)->(aEC)T(3)(6)I

(8)Vx((xGA)—>(xeC))UG(8)

⑼AQCT(8)E

定義2-1-1.2如果集合力的每一元素都屬于集合8,而集合6中至少有一元素不屬

于力,則稱/為8的真子集，記作

即AuBoVx((xe-?(xGB))A3X((Xe5)A(xg/))

例如：｛。，6｝是｛。4，。｝的真子集；N是Q的真子集，Q是R的真子集；R是C

的真子集。

注意符號“C”和“三”在概念上的區(qū)別，“￡”表示元素與集合間的“屬于”關系,

表示集合間的“包含”關系。

定理2-L1.1集合N=8的充分必要條件是：/三8且(外延性原則)

證明：必要性，即證：A=B=>(AqB)/\(BqA)

4=Bn(Vx((xw/)?(xwB)))A(VX((Xe8)f(xe/)))=(/c8)A(8")

充分性，即證：(AQB)A(Bc^)=>A=B

/*3=>3x((xwZ)△(xeB))。AUB(A<ZB)A(AQB)F

或4H8nHx((xe5)A(xgA))oBU4(5(ZA(5c^)<=>F#

定理2-1-1.2對于任一集合A,①且空集是唯一的。

證明：假設①之4為假，則至少存在一個元素X,使xe①且x定4,因為空集中不

包含任何元素，所以這是不可能的。

設①'與①都是空集，由上述可知，①'[①且①之①'，根據(jù)定理2-1-1.1知中'=①

所以，空集是唯一的。

注意：①H{①},<X>={X|P(X)A-1P(X)}P(X)是任一謂詞。

例2-1-1.4設A={2,3},6為方程一5x+6=0的根組成的集合，則A=

Bo

定理2-1-L1指出了一個重要原則：要證明兩個集合相等，即要證明每一個集合中的

任一元素均是另一集合的元素。這種證明是靠邏輯推理理論，而不是靠直觀。證明兩個

集合相等是應該掌握的方法。

定義2-1-L3在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全

集，記作E。對于任一xe/,因Z=所以xwE,

也即Vx(xeE)恒為真

故E-{x\P(X)V->P(X)},P(X)為任一謂詞。

注意：全集的概念相當于論域，只包含與討論有關的所有對象，并不一定包含一切

對象與事物。例如：在初等數(shù)論中，全體整數(shù)組成了全集；方程/+1=0的解集合，在

全集為實數(shù)集時為空集，而全集為復數(shù)集時解集合就不再是空集，此時解集合為

{/,-/,},/=1。

三、幕集

定義2-1-L4給定集合A,由集合A的所有子集為元素組成的集合，稱為集合A

的基集。記為集(A)(或記為2")。即(P(A)={X|XcA}o

例2-1-1.5A={0,1,2},則-(A)={中,{0},{1},{2},{0,1},{0,2},{1,

2},{0,1,2))；

軟⑷尸{①，㈤};

(P(0)={0}；<?({0})={0,{0}}o

定理2-L1.3設〃={/，％,…，4}，則|0(A)|=2"。

其中：|R(A)|表示集合O(A)中元素的個數(shù)。

證明：集合A的加(加=0,1,2,…，〃)個元素組成的子集個數(shù)為從〃個元素中取相

個元素的組合數(shù)，即C：,故O(A)的元素個數(shù)為：

匠(A)|=C；+《+...+&=￡c：

fn=0

根據(jù)二項式定理(X+W令x=y=l得2"=沙；

7M=0/W=0

故⑷(A)|=2"。

四、集合的數(shù)碼表示

在中學學習集合時，特別強調(diào)了集合中元素的無序性，但是，為了用計算機表示集

合及其基集，需要對集合中元素規(guī)定次序，即給集合中元素附上排列指標，以指明一個

元素關于集合中其他元素的位置。如A2={計算機，打印機}是二個元素的集合，令“計

算機”為集合A的第一個元素，“打印機”為集合A2的第二個元素。改記為A2={X1,

X2}，則以A2)的四個元素,可記為，①=Soo,{xl}=sio,{x2]=S0l,{xt,x2}=Sn,

其中S的下標，從左到右分別記為第一位，第二位，它們的取值是1還是0由第一個和

第二個元素是否在該子集中出現(xiàn)來決定，如果第7?個元素出現(xiàn)在該子集中，那么S下標

的第i位取值為1,否則取值為0(1=0,1)。即令1={00,01,10,11}={"，是二位

二進制數(shù)，00<i<11},則0(A2)={S,-|/GJ}o類似地，三個元素集合

A3={修，x2,X3}的界集?(A3)={S/|ZGJ,J={z|i二進制數(shù)，000WiW

111}),因此，

Soio={x2}，S|(H={X1,X3}。上述基集中元素表示法實際上是一種編碼，可以推廣到

〃個元素的集合A”的幕集上，?(A”)的2"個元素可以表示為

nn

S,,zGJ={z|i是二進制數(shù)，/六7b<iWfT±'}

)6

如果A6={X,,X2,X3,X4,X5,X6},fP(A6的2個元素記為So,5,S2<1,此時S

的下標是十進制整數(shù)，如何求出S,，￡是A6的那些元素組成的子集呢？將下標轉(zhuǎn)換為

二進制的整數(shù)，不足六位的在左邊補入需要個數(shù)的零，使之成為六位的二進制整數(shù)，由

排列的六位二進制整數(shù)推斷出，含有那些元素。凡第i位為0,表示X,不在此子集中，

凡第i位為1表示打在此子集中，故

B?=8山=5OOOII1={x4,x5,x6},Bl2=Bmi00={xy,xj。這種方法可以推廣到一般情況,

即將十進制整數(shù)轉(zhuǎn)換為二進制整數(shù)，在左邊補入需要個數(shù)的零使之成為〃位的二進制數(shù),

若第i位為0,表示X,不在此子集中，若第，位為1表示盯在此子集中。

子集的這種編碼法，不僅給出了一個子集含那些元素的判別方法，還可以用計算機

表示集合、存貯集合以供使用。

§2-1-2集合的基本運算

集合的運算，就是以集合為對象，按照確定的規(guī)則得到另外一些新集合的過程。給

定集合A,B,可以通過集合的并（U）、交（0）、相對補（一）、絕對補（一）和對稱

差（?）等運算產(chǎn)生新的集合。

一、集合并（U）運算

定義2-1-2.1設A，B為任意兩集合，所有屬于集合A或?qū)儆诩螧的元素組成

的集合，稱為集合A和B的并集。記作AUB

AuB={x|（xeJ）v（xe5）}

并集的文氏（英國數(shù)學家JohanWenn（1834?1883））圖

例2-1-2.1設A={1,2,3,4},B={2,4,5,6}

則AUB={1,2,3,4,5,6}o注意：集合是由互不相同元素組成的，在AUB中2,4

各寫一次，不能重寫。

由集合并運算的定義知，并運算具有如下性質(zhì):

定理2-1-2.1設A,B,C為任意三個集合，則

⑴基等律AUA=A；

(2)交換律AUB=BUA；

(3)結合律(AUB)UC=AU(BUC)；

(4)同一律AUO=A；

(5)零律AUE=E；

(6)AcAUB,BcAUB；

(7)AUB=B=AcBo

證明：性質(zhì)⑴，⑵，⑷，⑸，⑹由定義2-1-2.1立即可以得到。

⑶的證明

(AUB)UC={x|xe(AUB)UC}={x\(%eAUB)V(XGB)}

={x((xGA)V(xEB))V(xEB)}={(xEA)V((xGB)V(xEC))}

={x|(xeA)V(xGBUC)}={x|XEAU(BUC)}=AU(BUC)°

A3=B

⑺的證明：必要性證明\/x(x￡/)nVx(x￡/u3)u>Vx(xGB)所以AcBo

充分性證明由⑹知BqAUB,現(xiàn)證明AUBcB

A^B

Vx(xw/u8)=Vx(xeB)

所以有AUB=Bo

例2-1-2.2設AcB,C=D,則AUCcBUD

AqB,CcD

證明：A<JC={x\xeA^JC}={X|(xeJ)v(xeC)}=>{x|(xe5)v(xeD)}

={x|xeBu。}=即AUCqBUD成立。

同理可證AqBnAuCqBuC。

因為集合的并運算滿足結合律，對〃個集合A|,A2,…，A“的并集4。4口…

定義為至少屬于Ai,A2,…，A”之一的那些元素構成的集合?！ǔ？s

寫成。4。

/=1

X

4u…uZ,?…=U4,={x|加wN,xGZ,,}其中N是自然數(shù)集合。

M=l

一般地，U4R={X,X￡4}。

kel

集合的并運算，就是把給定集的那些元素放到一起合并成一個集合，在這個合并中

相同的元素只要一個。如設4={1,2,3},4={3,8},H={2,3,6}則

3

U4={1，2,3,6,8}。

/=1

二、集合的交(n)運算

定義2-122設任意兩個集合A和B,由集合A和B共

同元素組成的集合，稱為集合A和B的交集，記作AABo

Ar\B-{x\(xe/1)A(xe5)}o

交集的文圖

例2-1-2.3^,A={a,b,c,d,e},B={a,c,e,f}則Ar>B-{a,c,e}?

例2-1-2.4設A={X高等學校的本科學生},B={X高等學校計算機專業(yè)的學生},

則

AAB={X高等學校計算機專業(yè)的本科學生}

例2-1-2.5設A是所有能被k整除的整數(shù)集合，B是所有能被/整除的整數(shù)集合,

則ACB是所有能被左與/最小公倍數(shù)整除的整數(shù)集合。

由集合交運算的定義知，集合交運算具有如下性質(zhì)：

定理2-122設A,B,C是任意三個集合，則

(1)基等律APA=A；

(2)交換律AnB=BAA；

(3)結合律(AAB)nC=An(BAC)；

(4)零律①CA=①；

(5)同一律EPA=A；

(6)AnBcA,AABcB；

(7)AnB=AoA￡B。

證明：根據(jù)定義2-1-2.2,性質(zhì)(1),(2),(4),(5),(6)立即可以得到。

性質(zhì)(3)的證明：

(AAB)nC={x|xe(AAB)AC}={x|(xEAHB)A(xEC)}

={x\((xeA)A(xGB))A(xGC)}={x\(x￡A)A((x^B)A(%eC)}

={x\(xGA)A(x￡Bnc)}={%IXGAA(Bnc)}=An(BAC)

性質(zhì)(7)的證明：

AryB=A

必要性的證明：Vx(xw/)OVx(xGNc8)=Vx(xe8)即得ACB=A=>A=B

充分性得證明：由性質(zhì)(6)知AAB=A,現(xiàn)證AcAAB

采用邏輯演繹推理法

(1)Vx(xeA)p（附加前提）

(2)aeAUS(1)

(3)AqBp

(4)Vx((x￡4)f(X￡5))T(3)E

(5)(aeA)->(aEB)US(4)

(6)asBT(2,5)I

⑺(aeA)A(aGB)T(2,6)I

(8)Vx((xE4)△(X￡5))UG(7)

(9)Vx(x￡AcB)T(8)E

(10)AcAABCP

若集合A,B沒有共同的元素，則可記為AAB=①，這時稱A,B不相交。

由集合的交運算具有結合律，同樣可以定義〃個集合Ai,A2,…，A”的交集，也

可以定義集序列A-A2,…，A“,…的交集，分別記為

n

4c42c…c4,=p|4={x|ze{l,2,---,n},xe4}

i=l

oo

A2o---ryAnry-=^\An={x\〃e{1,2,,xe/“}

M=1

一般地，集合族{Ak}g中各集的交記成其定義為

ke/

0|4={x|X//e/,xe4}。

ke!

若序列，…任意兩集合豐不相交,則稱

A?,A2,A?Ai,Ay-(ij)

A|,A2,…，A”,…是兩兩不相交的集序列。

三、交運算與并運算之間的聯(lián)系

定理2-1-2.3(分配律)設A,B,C為任意三個集合，貝IJ

(1)交運算對并運算的分配律

/C(6DC)=(ZC8)D(4CC)

(2)并運算對交運算的分配律

NU(6CC)=(/U8)C(/UC)

證明：(1)AC(BUC)={xIxdAA(BUC)}={x|(xGA)A(xSBUC)}

={x|(xGA)A((xGB)V(xEC))}

={x\((xEA)A(xEB))V((xeA)A(xGC)))

={x|(xGAPB)V(xeAAC)}

={x|xE(AAB)U(AAC)}=(AAB)U(AAC)

當然可以仿照(1)的證明方法證明(2)的成立，現(xiàn)在采用(1)來證明(2),注意

至UACAUB,AACcA,由(1)可得

(AUB)n(AUC)=((AUB)AA)U((AUB)AC)=AU(Anc)u(BAC)=AU(BAC)。

同理可以利用(2)證得(1)成立(讀者自行完成)，于是(1)成立o(2)的成立。

定理2-1-2.4(吸收律)設A,B為任意兩集合，則

(1)AU(AAB)=A；

(2)An(AuB)=A；

證明：由分配律可得

（1）AU（AnB）=（AnE）U（AAB）=An（EUB）=AAE=A

（2）AA（AUB）=（AU中）A（AUB）=AU（中DB）=AUG=A#

四、集合的補運算

定義2-1-2.3設A,B為任意兩集合，由屬于A而不屬于B的一切元素構成的集合,

稱為A與B的差運算(又稱B對于A的補運算，或相對補)，記為A-B,A-B稱為A

與B的差集(或B對于A的補集)。

A-B={x\(xeA(xg5)}={x|(xe

若A=E,對任意集合B關于E的補集

E-B，稱為集合B的絕對補，記作豆o

B-E-B-{x\(xeE)/\(xB)}

例2-126設人={1,2,3,4,5},

B={1,2,4,7,9},則A-B={3,5}o

例2-1-2.7設A是素數(shù)集合，B是奇數(shù)集合，則A-B={2}。

例2-128設￡=強高校計算機專業(yè)學生},A={X高校校計算機專業(yè)本科學生},

則A={X高校計算機專業(yè)研究生}o

由集合補運算的定義知，補(差)集合有如下性質(zhì)

定理2-125設A,B,C為任意三集合，則

(1)對合律，=/；

(2)豆=①；

(3)不=￡；

(4)排中律NuZ=E；

(5)矛盾律

(6)(De.Morgan定理)

①AuB=AcB,②4cB=AuB；

(7)①A-B=AoB,②A-B=A-(AcB)；

(8)4c(8—C)=(/c8)—(ZcC)；

(9)若Z=當且僅當①BQA；②(B-4)uA=B。

證明：由補運算的定義立即可得性質(zhì)(1)?(5)o

(6)的證明：

0A<JB-{x^xA<JB}-{x\xA<JB}-{x\{xiA)/\{xB)}

-{x|(xeN)A(xe8)}={x|xGAcB}-AryB

②的證法與①類似，請讀者自行證明。

(7)的證明：

①A-B={x\(x&A)/\(xB)}={x|(xeJ)A(xe5)}={x|xeAryB}=Ar\B；

②A-(Ar^B)=Ar\Ar>B=Ar>(A<jB)=(AryA')<J(Ar^B)=Ar\B=A-B,,

(8)的證明：

(NcB)-(/cC)=(Zc8)cGn)=(/c8)c(1uG)

=(Zc8c/)u(/c8cC)=/c8cC=Jn(5-C)o

(9)的證明:

證明①

,__A^B___

必要性Vx(xe5)=>Vx(x任8)=>Vx(xA)=>Vx(xeA)即B=A；

充分性Vx(xGA)=>Vx(xeN)nVx(x史B)nVx(xGB)即4qB。

證明②

必要性(8-Z)U4=(6C1)UZ=(8UZ)C(1UZ)=8DZ=B；

充分性A^AU(B-A)=(B-A)VJA=BO#

五、集合的對稱差運算

定義2-1-2.4設A,B為任意兩集合，由“屬于A而不屬于

B”或“屬于B而不屬于A”的一切元素構成的集合，稱為A,B

的對稱差，記作A。B。

Z十8=(4-8)-N)={x[(x")▽(xe8)}={x|((x")v(xG8)凝密An5)}

對稱差運算的性質(zhì)

定理2-1-2.6設A,B,C為任意三集合，則

(1)/十8=8十Z；

(2)/十①=4；

(3)/十/=<!>；

(4)2十8=(/c豆)；

(5)(〃十8)十C=Z十(8十C)；

(6)交關于對稱差的分配律Ar>(B?C)=(Ar^B)?(AryC)；

(7)若Z十8=/十C,則B=Co

證明：

由對稱差的定義立即可得(1),(2),(3),(4)的證明。

(5)的證明

(/十8)十C=((/c豆)u(彳c8))十C

=((/c-)5、c8)nC)u(((Jc豆)u(1c5))nC)

=((Ju5)n(z4o5)nC)u(y4nSnC)u(JnBnC)

=(Jn5nC)u(7n5nC)u(y4nSnC)o(J4n5nC)

Z十(8十C)=Z十((8c^)口(豆cC))

=(Jn((5nC)u(5nC)))u(Jn((5nC)o(5nC)))

=(Jn(5uC)n(5uC))u((Jn5nC)u(In5nC))

=(Zc8cC)5/c8cC)u(4c8cC)u(ZDBCC)

所以(N十8)十C=/十(8十C)。

(6)的證明

(/c8)a(ZcC)=((/c8)c(/cC))5(/c8)c(/cC))

=((Zc8)c(Zu}))□((]u耳)c(/cC))

=(y4n5nC)u(y4n5nC)

=Jn((5nC)u(5nC))

=Jn(S?C)

(7)的證明

(〃十8)=(〃十C)nN十(，十8)=〃十(，十C)n(，十⑷十8=(N十⑷十C

n①十8=0)十。n8=C

從對稱差定義或文圖容易看出

Zu8=(/c巨)u(彳c8)u(Nc8)=(，十8)u(4c8),

4十B=(AuB)—(AcB).

§2-1-3集合中元素的計數(shù)

一、兩個基本原理

加法原理：若一個事件以m種方式出現(xiàn)（這些方式構成集合A）,另一個事件以n

種方式出現(xiàn)（這些方式構成集合B）,這兩個事件完成一?件即能達到目的（構成集合A

UB）,則達到目的的方式數(shù)為小+〃。

例2-1-3.1假設從城市A到城市B有鐵路兩條，公路三條，航線一條，那么按加

法原理，從城市A到城市B有2+3+1=6種走法。

乘法原理：若一個事件以m種方式出現(xiàn)（這些方式構成集合A）,另一個事件以〃

種方式出現(xiàn)（這些方式構成集合B）,這兩個事件同時完成才能達到目的（構成集合A

HB）,則達到目的的方式數(shù)為相〃。

例2-1-3.2一位學生想從圖書館借離散數(shù)學和C#語言書各一本，書架上有三種不

同作者的離散數(shù)學書，有兩種不同作者的C#語言書，那么這位學生共有3X2=6種不

同的選法。

二、排列、組合

中學里已學過的計數(shù)公式是排列組合公式。從n個元素的集合中每次取m個的排列

和組合的公式分別為：

*〃（〃_1）...（/_唐+1）=加,=生=——-一

（〃一加）！m\

對排列P"'：若加=〃時稱為全排列，m<n時稱為選排列。排列和組合的最基本恒

等式有：

P,；"=HC;，CH,c，=c：：+M

例2-1-3.3將的字母全部取出進行全排列，其中c不在第一位，r不在末

位，問共有多少種排法？

解：cow?曲〃er字母的全排列數(shù)為6=8!,其中c排在第一位的排法共有7!種，尸

排在末位的排法共有7!,除去這些不合要求的排法，還有8!-（7!+7!）=30240種,

然而這還不是答案，因為c在第一位的7!種排法中尸可能排至末位的7!中c可能排在

第一位，即c在第一位，r在末位的排法被減去了兩次，實際上應該只減一次，故把不

應該減的加回去才能得到正確的答案。所求的答案為：

一一2.+"=30960（種）。

這種分析問題的方法稱為“多退少補法”，這種思想在“包含排斥原理”中還要用到。

例2-1-3.4將1,2,3三個數(shù)字排成2行3列的矩陣，要求同行和同列上都沒有相

同的數(shù)字，問這樣的數(shù)字矩陣有多少？（實際上這就是集合｛1,2,3｝到自身上的一些雙

射或置換，這些雙射不允許一個元素以自身為像）

解：先排矩陣的第一行共有片=3!=6種排法，如果不管題目的要求，第二行也有

6種排法，由乘法原理，知共有6X6=36種矩陣。這些矩陣包含了有一列數(shù)字相同的情

況，有兩列因而就有三列數(shù)字相同的情況，按題目要求這些矩陣都應該除去，這些矩陣

的個數(shù)可如下計算：一列數(shù)字相同其余兩列數(shù)字不同的矩陣數(shù)有8種；有兩列數(shù)

字相同從而就有三列數(shù)字相同的矩陣數(shù)有3!=6個，因此所求的矩陣個數(shù)為

Hxg—℃"-6=12。

片"與c；是從〃個元素中任意取用個元素（不重復抽取）的排列與組合，但是有些

實際問題需要在n個元素中重復抽取若干個元素來排列，如用0,1,2,3,4,5,6,7,8,

9這十個數(shù)字來編制代碼，，每個號碼就可以重復使用某個數(shù)字。一般地，從〃個元素的

集合中抽取加個元素，允許重復的排列數(shù)為：〃“。實際上可以設想有機個位子，每個

位子都可以放上〃個元素中的任一個，允許

重復，由乘法原理即知有Ax〃x…種排法。

例2-1-3.5求電子計算機中的6位二進制數(shù)。

解：電子計算機中的數(shù)碼第一?位數(shù)不能為0,故首位必須為1,后面五位每位都可選0

或1,固有25=32種排法，因而6位二進制數(shù)有32個。

例2-1-3.6考試時有25個正確或錯誤的問題，學生也可能不作答，問有多少種不

同的考試結果？

解：對每一問題的回答有三種情況：正確、錯誤和不作答，因而考試結果共有325個。

關于重復組合數(shù)〃；的計算問題。先從一個實例來研究它的計算公式，從｛1,2,3｝

中每次取出兩個（允許重復抽?。┑慕M合按自然數(shù)順序?qū)懗鰜恚疵杜e）為：

11,12,13,22,23,33（a）

現(xiàn)將各種組合分別加上01，就得到

12,13,14,23,24,34（b）

3）中的6個組合恰好是從｛1,2,3,4｝中任取兩個元素不重復的組合情況。反之從（6）中

的組合中分別減去01即得（。），說明（。）與（b）存在1—1對應關系（雙射），因而從三個

相異元素中任取兩個的重復組合數(shù)可化為從四個相異元素中任取兩個不重復的組合數(shù)

來計算，即"；=。：（27=。：=6得到。一般地計算〃：仿上面的討論，即從｛1,2,…，

〃｝中任取加個允許重復的每一個組合，將其元素分別加上0,1,2,…，吁1即變成從｛1,

2,,?,?+1,…，〃+（m-1）｝中任取m個不重復的組合，故"；=o

例2-1-3.7求成自然序的四位數(shù)碼個數(shù)。

解：四位數(shù)碼是從｛0,1,2,3,4,5,6,7,8,9｝中選四個數(shù)字組成，數(shù)字可以重復

使用，由于規(guī)定自然順序，故只有一種排法，因而變?yōu)?0個相異元素中任取四個允許

重復的組合問題，所求個數(shù)為“[=C]（4T）=C2=715。

關于環(huán)狀排列問題，由于環(huán)狀排列旋轉(zhuǎn)后仍是同一種排列，故可以令其中任一個元

素固定位置，不讓它移動，其余〃-1個元素任意排列，因而〃個相異元素的環(huán)狀排列數(shù)

為（〃-1）!,它恰好為〃個相異元素的全排列數(shù)〃!被〃除的結果，這種想法可以推廣到

不盡相異元素的排列情形。

例2-1-3.88為朋友圍圓桌而坐，若座位不編號有多少種坐法？座位編號又有多少

種坐法？

座位不編號為環(huán)狀排列問題，有

7!=5040種坐法。

座位編號為非環(huán)狀排列問題，故有

8!=40320種坐法。

例2-1-3.95顆紅珠，3顆白珠穿在一個項鏈上，有多少種方法？

解：如果只穿在--條線上就是不盡相異元素的全排列問題。排列數(shù)為工=56。

5!3!

現(xiàn)在項鏈上是環(huán)狀排列問題，因而穿法為名=7種。

8

三、容斥原理

設集合A={0,42,…，。”}，它含有〃個元素，可以說集合A的基數(shù)是〃，記

作CardA=〃?；鶖?shù)是表示集合中所含元素多少的量。如果集合A的基數(shù)是〃,可記為

|A|=〃，這時稱A為有窮集，顯然空集的基數(shù)是0,即|①|(zhì)=0。如果A不是有窮集,

則稱A為無窮集。

容斥原理也稱包含與排斥原理或逐步淘汰原則，它也是“多退少補”計數(shù)思想的應

用。

定理2-1-3.1（容斥原理）設A,B為有限集合，則

|A^JB\=\A\+\B|-|AoB\.

證明：①當A,B不相交，即Nc8=<I）時，|A\JB|=||+|5|

②當NcB。①時

|^|=||+|AoB\,|5|=|BryA|+|AoB\

所以，|Z|+|8|=|Zc反|+||+2||

但是，反|+|Zc8|+|Zc6|=|/u8|

因此，|JuB|=|J|+|5|-|AoB\

定理2-132設A,B是有限集合，則?十M=|/|+冏-2|4門同。

證明：

H十同=|(Nu8)—(Nc5)|=|JuS|-|Jn5|=(|j|+|B|-|Jn5|)-|JnB\

=|j|+|5|-2|Jn5|

例2-1-3.10假設10名青年中有5名是工人，7名是學生，其中既是工人又是學生

的青年有3名，問既不是工人又不是學生的青年的有幾名？

解：設該10名青年組成集合Y,1Y|=10,其中工人集合設為W,|W|=5；學生集合

設為s,Is|=7。|wns|=3,又因為丫=(印uS)u(萬cS)

所以|Y\=\JKu5|+|^nS|=10

即|方|=10—|%uS|=10—(|%|+1S|—|"cS|)=10—(5+7—3)=1

因此，既不是工人又不是學生的青年有1人。

這個例子的計算過程用到了容斥原理。一般，令有限集A的元素具有m個不同的性

質(zhì)Pi,P2,…，P,?=A中具有性質(zhì)P,的元素組成子集記為A,z=1,2,,m；A,■

HA,(i差/)表示A中同時具有性質(zhì)Pj和P/的元素組成的子集；A/AAyAAtQi豐j豐k)

表示A中同時具有性質(zhì)P,，Pj,PA的元素組成的子集；…；AinA2n…AA,”表示

A中同時具有性質(zhì)Pi,P2,…，P,”的元素組成的子集。％表示A中不具有性質(zhì)P,的元

素組成的子集。那么包含排斥原理可以敘述為

定理2-L3.3(容斥原理的推廣)A中不具有性質(zhì)R,P2,…，Pm的元素數(shù)是，

14cHe…cZ,」=|n-￡|闋+Z|4c可

/=1

-XI4cAjc//+.?.+(-1)〃[4c&c??.c4」

l</<J<k<m

注意：上式右邊共1+C；?+C,；+---+C；=2,n項

證明：等式左邊是A中不具有性質(zhì)P1,P2,…，P,”的元素數(shù)。下面我們要證明：

對A中的任何元素a,如果它不具有這根條性質(zhì)，那么它對等式右邊的貢獻是1；如果

。至少具有這m條性質(zhì)中的一條，那么它對等式右邊的貢獻是0o

設。不具有性質(zhì)Pi,P2,…，P“”那么,z=1,2,???,mo對任何整數(shù)，和

j,1<z<j<m,都有a定4cN/。對任何整數(shù)i、j和k,1<f<j<k<tn,都有

a史4cN/C/*,…，2c…cN,.。但是“e/,所以在等式右邊的計數(shù)中

它的貢獻是：1-0+0-0+...+（-1）*0=10

設。具有這磨條性質(zhì)中的左條性質(zhì)，14%4%，則“對|A|的貢獻是1；對》⑷的

/=1

貢獻是C：=k；對的貢獻是C：；…；對|2c…c4/的貢獻是小,

j&m

所以“對等式右邊計數(shù)的總貢獻是：

l-C；+C^--+（-irC；'（k<m）

=c；-c：+c；-…+（-i）C=缶（-1）C=（1-1）"=o#

7=0

推論A中至少具有加個性質(zhì)之一的元素個數(shù)為

|/?……”/江⑷-Z|4c聞

/=11</<j<m

+El4cZ/C/J—…+（—i）a|4c/2c…c4j

1</<j<k<m

證明：因為4=〃_（4?！?。4,）=/_（4c/2c…c/,“）

所以

|4。45-U，」=回一|2c…門彳/二工卜卜

/=1i<j￡m

+4cZ/cN*|-…+（-l）"[acZ2c…c/Jo

1<i<j<k<m

例2-1-3.11試求不超過1000的自然數(shù)中能被2或3或5整除的數(shù)的個數(shù)。

解：設A={1,2,…，1000},這是研究對象的集合，在A上定義性質(zhì)PI,P2,P3。

對任意〃dA,若〃具有性質(zhì)Pi（P2,P3）當且僅當2|“（3]〃，5|〃）0令A,?為A中具

有性質(zhì)P,的數(shù)組成的子集，z=l,2,3,則

Ai={2,4,6,1000}={2%Ik=1,2,,500},

A2={3,6,9,,999}={364=1,2,

A3={5,10,15,1000}={5山=1,2,…,［隈叫)o

1000

工旦IIF1cnnA「1。。。1°”?.Ifl0001.

于是，IAAi|=------=500，AI=------=333，A|=------=2nn00。

22335

100Q-1000-

而A{r\A21={6左k=1,2)==166；

6,6.

4c4|=F1000'Fl000'

{10人左=1,2,…,)==100

1010

，2C/3|=10001000

{15左k=1,2)=二66；

1_15._15.

|4c42cz3|=1000

"30-

由定理2-1-3.3推論知

|A>UA2UA3I=(500+333+200)-(166+100+66)+33=1033-332+33=

734o

所以，不超過1000的自然數(shù)中，至少能被2,3,5之一整除的數(shù)共有734個。

例2-1-3.12某汽車工廠裝配了三十輛汽車，可供選擇的設備是收錄機，空調(diào)器，

防盜器，三十輛汽車中有15輛汽車裝有收錄機，8輛裝有空調(diào)器，8輛裝有防盜器，三

種設備都具有的汽車有3輛，問這三種設備都沒有的汽車有兒輛？

解：設Ai,A2,A3分別表示具有收錄機，空調(diào)器，防盜器的汽車的集合。由題設

知

|A||=15,|A2I=8,|A3I=8,|A|nA2nA3I=3o

由定理2-1-3.3推論知，

IA,UA2UA3