離散數(shù)學(xué)：3-3-1 集合的基本概念與運(yùn)算

復(fù)習(xí)思考題7A、B、C為任意集合，判斷下列等式或命題是否恒真，若不為恒真，請(qǐng)舉一反例.

ABB

=

A(B－A)(AB)－

(BC)=A－C

設(shè)A、B為任意集合，尋找下列等式成立的充要條件。

A－

B=B

A－B=

B－A

AB=AB

第3章集合的基本概念和運(yùn)算3.1集合的基本概念3.2集合的基本運(yùn)算3.3集合中元素的計(jì)數(shù)集合的基數(shù)與有窮集合集合A的基數(shù)——集合A中的元素?cái)?shù)，記作cardA有窮集

AcardA=|A|=n，n為自然數(shù).集合基本運(yùn)算的基數(shù)

|A

B|

≤|A|+

|B|

|AB|

≤

min(|A|,

|B|)

|A

─B|

≥|A|─

|B|

|A

B|

=|A|+

|B|─2|AB|3.3集合中元素的計(jì)數(shù)設(shè)論域?yàn)镾，則同時(shí)不屬于集合A，B和C的元素為：

=|S|－|AB

C

||AB

C

|=|A|+|B|+|C|

─|AB|─|AC|─|BC|+|AB

C

|

不屬于三個(gè)集合的元素的計(jì)數(shù)包含排斥原理定理

設(shè)S為有窮集，P1,P2,…,Pm

是m種性質(zhì)，Ai是S

中具有性質(zhì)Pi

的元素構(gòu)成的子集，i=1,2,…,m.則S

中不具有性質(zhì)P1,P2,…,Pm的元素?cái)?shù)為證：設(shè)x不具有性質(zhì)P1、P2、

…、

Pm,

xAi

,i=1,2,…,m

xAiAj

,1i<jm

…

xA1A2…Am

,x對(duì)右邊計(jì)數(shù)貢獻(xiàn)為

10+00+…+(1)m·0=1證明要點(diǎn)：任何元素

x，如果不具有任何性質(zhì)，則對(duì)等式右邊計(jì)數(shù)貢獻(xiàn)為１，否則為０。包含排斥原理的證明包含排斥原理的證明設(shè)x具有n條性質(zhì)，1nm

x

對(duì)|S|貢獻(xiàn)為1

x

對(duì)貢獻(xiàn)為

x

對(duì)貢獻(xiàn)為

….

x

對(duì)|A1A2…Am|貢獻(xiàn)為

x對(duì)右邊計(jì)數(shù)貢獻(xiàn)為包含排斥原理的推論S中至少具有一條性質(zhì)的元素?cái)?shù)為證明:

將定理1代入即可[P65例3.11]例題某班有25名學(xué)生，14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這3種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另一種球(指籃球或排球)，求不會(huì)打這3種球的人數(shù)。解：設(shè)A、B和C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合，則

|A|=12，|B|=6，|C|=14，

|S|=25，

|ABC|=2

|AC|=6，|BC|=5，=25-(12+6+14)+(6+5+3)-2=512614

243125|AB|=3排球網(wǎng)球籃球解：S={x|xZ,1x1000},

如下定義S

的3個(gè)子集A,B,C：

A={x|xS,5|x}，

B={x|xS,6|x}，

C={x|xS,8|x}

利用下面公式求例：求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？應(yīng)用舉例2

對(duì)上述子集計(jì)數(shù)：|S|=1000,|ABC|=1000/120=8,

|AB|=1000/30=33,|AC|=1000/40=25,|BC|=1000/24=41,|A|=1000/5=200,|B|=1000/6=166，

|C|=1000/8=125,

=1000(200+166+125)+(33+25+41)-8

=600例：求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個(gè)？[P68]例3.16——文氏圖法對(duì)24名科技人員掌握外語(yǔ)情況調(diào)查結(jié)果如下——每人至少會(huì)1門外語(yǔ).英語(yǔ)：13；日語(yǔ)：5；德語(yǔ)：10；法語(yǔ)：9英日：2;英德：4；英法：4；法德：4會(huì)日語(yǔ)的不會(huì)法語(yǔ)、德語(yǔ)求：只會(huì)1種語(yǔ)言人數(shù)，會(huì)3種語(yǔ)言人數(shù)

解：設(shè)同時(shí)會(huì)3種語(yǔ)言的有x人只會(huì)英、法或德語(yǔ)1種語(yǔ)言分別有y1、y2、y3人會(huì)英語(yǔ)的人數(shù):

x+2(4-x)+y1+2=13會(huì)法語(yǔ)的人數(shù):

x+2(4-x)+y2=9

會(huì)德語(yǔ)的人數(shù):

x+2(4-x)+y3=10總?cè)藬?shù)為:

x+3(4-x)+y1+y2+y3+5=24xy132y2y34-x4-x4-x英語(yǔ)日語(yǔ)法語(yǔ)德語(yǔ)[P68]例3.16——文氏圖法對(duì)24名科技人員掌握外語(yǔ)情況調(diào)查結(jié)果如下——每人至少會(huì)1門外語(yǔ).英語(yǔ)：13；日語(yǔ)：5；德語(yǔ)：10；法語(yǔ)：9英日：2;英德：4；英法：4；法德：4會(huì)日語(yǔ)的不會(huì)法語(yǔ)、德語(yǔ)求：只會(huì)1種語(yǔ)言人數(shù)，會(huì)3種語(yǔ)言人數(shù)x+2(4-x)+y1+2=13x+2(4-x)+y2=9x+2(4-x)+y3=10x+3(4-x)+y1+y2+y3+5=24x=1,y1=4,y2=2,y3=3

3x+6(4-x)+y1+y2+y3+2=32[P68]例3.16——包含排斥原理法解：(1)只會(huì)日語(yǔ)的人：5–2=3

|ABC|=24–3=21(2)由|A|=13，|B|=9，|C|=10

|AB|=|AC|=|BC|=4

和包含排斥原理的推論得：|ABC|=|A|+|B|+|C|

–(|AB|+|AC|+|BC|)+|ABC|

代入得：21=13+9+10–(4+4+4)+|ABC|

得會(huì)3種語(yǔ)言的人有：|ABC|=1對(duì)24名科技人員掌握外語(yǔ)情況調(diào)查結(jié)果如下——每人至少會(huì)1門外語(yǔ).英語(yǔ)：13；日語(yǔ)：5；德語(yǔ)：10；法語(yǔ)：9英日：2;英德：4；英法：4；法德：4會(huì)日語(yǔ)的不會(huì)法語(yǔ)、德語(yǔ)求：只會(huì)1種語(yǔ)言人數(shù)，會(huì)3種語(yǔ)言人數(shù)2英語(yǔ)A日語(yǔ)法語(yǔ)B德語(yǔ)C31[P68]例3.16——包含排斥原理法(3)只會(huì)英語(yǔ)的人：|A-BC|–2=|A|–(|AB|+|AC|)+|ABC|–2

=13-4-4+1–2=4(4)只會(huì)法語(yǔ)的人：|B-AC|=|B|-(|BA|+|BC|)+|ABC|=9-4-4+1=2(5)只會(huì)德語(yǔ)的人：|C-AB|=|C|-(|CA|+|CB|)+|ABC|=10-4-4+1=3對(duì)24名科技人員掌握外語(yǔ)情況調(diào)查結(jié)果如下——每人至少會(huì)1門外語(yǔ).英語(yǔ)：13；日語(yǔ)：5；德語(yǔ)：10；法語(yǔ)：9英日：2;英德：4；英法：4；法德：4會(huì)日語(yǔ)的不會(huì)法語(yǔ)、德語(yǔ)求：只會(huì)1種語(yǔ)言人數(shù)，會(huì)3種語(yǔ)言人數(shù)32英語(yǔ)A日語(yǔ)法語(yǔ)B德語(yǔ)C1[P66]例3.13——求歐拉函數(shù)的值歐拉函數(shù)：

(n)

表示{1,…,n1}中與n互素的數(shù)的個(gè)數(shù).規(guī)定：(1)=1例：(12)=4，與12互素的數(shù)有1,