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

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

ABB

=

A(B－A)(AB)－

(BC)=A－C

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

A－

B=B

A－B=

B－A

AB=AB

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

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

|A

B|

≤|A|+

|B|

|AB|

≤

min(|A|,

|B|)

|A

─B|

≥|A|─

|B|

|A

B|

=|A|+

|B|─2|AB|3.3集合中元素的計數(shù)設(shè)論域為S，則同時不屬于集合A，B和C的元素為：

=|S|－|AB

C

||AB

C

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

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

C

|

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

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

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

中具有性質(zhì)Pi

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

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

…、

Pm,

xAi

,i=1,2,…,m

xAiAj

,1i<jm

…

xA1A2…Am

,x對右邊計數(shù)貢獻為

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

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

x

對|S|貢獻為1

x

對貢獻為

x

對貢獻為

….

x

對|A1A2…Am|貢獻為

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

將定理1代入即可[P65例3.11]例題某班有25名學(xué)生，14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這3種球。而6個會打網(wǎng)球的人都會打另一種球(指籃球或排球)，求不會打這3種球的人數(shù)。解：設(shè)A、B和C分別表示會打排球、網(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個子集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ù)有多少個？應(yīng)用舉例2

對上述子集計數(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ù)有多少個？[P68]例3.16——文氏圖法對24名科技人員掌握外語情況調(diào)查結(jié)果如下——每人至少會1門外語.英語：13；日語：5；德語：10；法語：9英日：2;英德：4；英法：4；法德：4會日語的不會法語、德語求：只會1種語言人數(shù)，會3種語言人數(shù)

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

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

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

會德語的人數(shù):

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

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

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

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

(n)

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