《離散數(shù)學(xué)》課件1第1章 集合

本章主要內(nèi)容：集合集合間的關(guān)系集合的運(yùn)算冪集與編碼集合恒等式的證明11.1集合1.1.1集合的概念集合是具有某種特定性質(zhì)的事物的全體。集合中的單個(gè)事物通常也稱為“個(gè)體”或“元素”。通常用英文大寫(xiě)字母來(lái)表示集合，如A、B、C等，用小寫(xiě)字母來(lái)表示集合中的元素，如a、b、c等，但不是絕對(duì)的，因?yàn)橐粋€(gè)集合也可以作為另一個(gè)集合的元素。如果元素a是集合A中的元素，用符號(hào)a∈A來(lái)表示，讀作“元素a屬于集合A”；反之，如果元素a不是集合A中的元素，用符號(hào)a

A來(lái)表示，讀作“元素a不屬于集合A”。集合、元素和屬于是集合論中的三個(gè)最基本的概念。2例1.1判斷下列各項(xiàng)是否是集合。（1）英文字母表中的26個(gè)字母；（2）所有的自然數(shù)；（3）一些自行車(chē)；（4）上海財(cái)經(jīng)大學(xué)全體學(xué)生的集合。3本書(shū)中常用的集合以及相應(yīng)的符號(hào)：N：全體自然數(shù)的集合；

Q：全體有理數(shù)的集合；

R：全體實(shí)數(shù)的集合；

C：全體復(fù)數(shù)的集合；

Z：全體整數(shù)的集合；

E：全體偶數(shù)的集合；

O：全體奇數(shù)的集合；

P：全體素?cái)?shù)的集合。41.1.2集合的特性互異性：互異性是指一個(gè)集合的各個(gè)元素是可以互相區(qū)分開(kāi)的，并且每個(gè)元素只能出現(xiàn)一次，如果某個(gè)元素在集合中出現(xiàn)多次，也只能看作是一個(gè)元素。如：集合{1,2,3,2}就是集合{1,2,3}。

無(wú)序性：無(wú)序性是指一個(gè)集合中所有元素之間的排列次序是任意的，即集合的表示形式是不唯一的。如集合{1,2,3}和集合{2,1,3}是同一個(gè)集合。確定性：任意一個(gè)元素是否屬于某一個(gè)集合回答是確定的。如給定元素a和集合A，元素a和集合A之間的關(guān)系是確定的，a∈A和a

A二者必有一個(gè)成立。5三大基本原理:1.外延公理:兩個(gè)集合和相等的充要條件是他們有相同的元素。(互異性和無(wú)序性)2.概括公理:純粹性—凡該集合中的元素都具有某種性質(zhì).完備性—凡具有某種性質(zhì)的元素都在該集合中.63.正則公理:不存在集合A,B,C,…,使得…CBA.(----消除了悖論)悖論：

所謂悖論是指：一個(gè)命題Q，如果從Q為真，可以推導(dǎo)出Q為假；又從Q為非真推導(dǎo)出Q為真，命題Q是一個(gè)悖論。7例1.2說(shuō)謊悖論：

“我正在說(shuō)謊.”問(wèn):這個(gè)人是在說(shuō)謊還是在講真話?解

如果他在說(shuō)謊，這表明他的斷言“我正在說(shuō)謊”是謊話，也就是說(shuō)他在講真話。即他說(shuō)謊，推出他是講真話（即沒(méi)有說(shuō)謊）。另一方面，如果他講真話，這表明他的斷言“我正在說(shuō)謊”是真話，也就是說(shuō)他正說(shuō)謊話，即他講真話，推出他在說(shuō)謊（即沒(méi)有講真話）。81）羅素將集合分成兩類：一類是集合A本身是A的一個(gè)元素，即A

A；另一類是集合A本身不是A的一個(gè)元素，即A

A；2）構(gòu)造一個(gè)集合S：S={A|A

A}}，即，S是由滿足條件A

A的那些A組成的一個(gè)新的集合。問(wèn)：S是不是它自己的一個(gè)元素?即S

S,還是S

S？例1.3羅素悖論：9解我們作如下分析：如果S

S,因?yàn)榧蟂由所有滿足條件A

A的集合組成,由于S

S,所以S滿足對(duì)于集合S中元素的定義，即S是集合S的元素，也就是說(shuō)S

S。如果S

S,因?yàn)镾中任一元素A都有A

A,又由于S

S,根據(jù)集合S的規(guī)定，知S不是集合S的元素,也就是說(shuō)S

S。既不是SS，也不是SS。

10羅素悖論的出現(xiàn),說(shuō)明樸素集合論有問(wèn)題,從而使數(shù)學(xué)的基礎(chǔ)發(fā)生了動(dòng)搖（第3次數(shù)學(xué)危機(jī)）,引起了一些著名數(shù)學(xué)家的極大重視。經(jīng)過(guò)長(zhǎng)期的努力，作出如下約定：先有成員才形成集合，一個(gè)正在形成的集合不能作為一個(gè)實(shí)體充當(dāng)本集合的成員，否則在概念上將產(chǎn)生循環(huán)，從而導(dǎo)致悖論。這正是正則公理的內(nèi)容，從而消除悖論。111.1.3集合的表示方法1.列舉法：所謂列舉法就是將集合中的元素用一對(duì)花括號(hào)括起來(lái)，這個(gè)集合可以是有限集，也可以是無(wú)限集。例1.4（1）A={1，2，3，4}（2）B={a，b，c，d，…，x，y，z}（3）C＝{桌子，椅子}（4）N={0，2，4，6，8，10，…}122.描述法：描述集合的方法是通過(guò)刻畫(huà)集合中元素所具備的某種特性來(lái)表示集合。我們通常用符號(hào)P(x)來(lái)表示不同對(duì)象x所具有的性質(zhì)P，由P(x)所定義的集合常記為：{x|P(x)}例1.5（1）A={x

0<x<2，x∈R}（2）B={x

x2-1=0，x∈R}（3）C={(x，y)

x2+y2≤4，x，y∈R}（4）D={x

x是動(dòng)物}說(shuō)明：描述法中A={x

0<x<2}與A={y

0<y<2}是表示同一個(gè)集合。133.文氏圖用平面上封閉曲線包圍點(diǎn)集的圖形來(lái)表示集合（見(jiàn)圖1.1）。文氏圖可以形象和直觀地描述集合之間的關(guān)系和集合之間的有關(guān)運(yùn)算。A圖1.1集合A144.BackusNaurForm(BNF)常用于定義高級(jí)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法集合。例1.6

在PASCAL語(yǔ)言中，標(biāo)識(shí)符集合定義如下：＜Letter＞::=＜Letter＞{＜Letter

or

Digit＞}{＜Letter

or

Digit＞}::=＜Letter＞|＜Digit＞155.遞規(guī)定義給定基礎(chǔ)元素，通過(guò)計(jì)算規(guī)則定義集合的其他元素。a0=1，a1=1，ai+1=2ai+ai-1(i≥1)，于是：S={a0，a1，…，an}={ak|k≥0}

161.2集合間的關(guān)系1.2.1包含關(guān)系定義1.1

包含設(shè)A和B是兩個(gè)集合,若A中的每一個(gè)元素都是B的元素,則稱A是B的子集,記作AB或BA.若AB且AB,則稱A是B的真子集,記作AB.B稱為A的超集.此外，若存在元素a

A,但a

B,則A不是B的子集.17例1.8N

I

Q

R與N

I

Q

R同時(shí)成立。例1.9

{1}

{1,2}與

{1}

{1,2}同時(shí)成立。例1.10N?N成立,但是N?N不成立。即一個(gè)集合可以是自身的子集,但不可以是自身的真子集。18集合間的包含關(guān)系具有下列性質(zhì)：自反性：A

A反對(duì)稱性：若A

B且B

A，則A=B

傳遞性：若A

B且B

C，則A

C191.2.2相等關(guān)系定義1.2

集合A和B的元素全相同，則稱A和B相等，A=B；否則稱A和B不相等，AB。由集合包含關(guān)系的定義，我們可以給出集合相等關(guān)系的另一種定義形式：定義1.3

設(shè)A和B是兩個(gè)集合，如果AB且BA,則稱A=B.20例1.11集合A={2,3}，B={x|x2-5x+6=0}，則有集合。例1.12集合A=

，B={x|x2+x+1=0,x∈R}，則有集合A=B。。21定理1.1設(shè)A和B是兩個(gè)集合，A=B的充要條件是：AB且BA，即兩個(gè)集合相等的充要條件是它們互為子集。

22定理1.1設(shè)A和B是兩個(gè)集合，A=B的充要條件是：AB且BA，即兩個(gè)集合相等的充要條件是它們互為子集。證明：必要性

A=B

AB并且BA。因?yàn)锳=B，由定義A中的每個(gè)元素是在B中，所以AB，同理B中的每個(gè)元素是在A中，所以BA。充分性

AB并且BA

A=B。反證法。如果A

B，則A中至少有一個(gè)元素不在B中，與AB矛盾；或者B中至少有一個(gè)元素不在A中，與BA矛盾。所以A

B不可能成立。所以A=B。23自反性:A=A對(duì)稱性:若A=B,則B=A傳遞性:若A=B且B=C,則A=C集合間相等關(guān)系的性質(zhì):24定義1.4

集合A中所包含的不同元素的個(gè)數(shù)，稱為集合A的基數(shù)，通常用|A|或Card(A)表示。例1.13計(jì)算下列集合的基數(shù)。(1)集合A={0,1,2}。(2)空集Φ。(3)集合B={x|x2-2x+1=0}。(4)自然數(shù)集N。(5)集合C={(x,y)|x2+y2≤4}。(6)集合D={Φ,{1},{2},{1,2}}。25定義1.5

設(shè)A是集合，如果A中有有限個(gè)不同的元素，則稱A為有限集，否則稱A為無(wú)限集。對(duì)有限集A，如果含有n個(gè)不同的元素，簡(jiǎn)稱A為n元集，它的基數(shù)為m（0

m

n）的子集稱為它的m元子集。26例1.14設(shè)集合A={a,b,c}，寫(xiě)出它的全部子集。解0元子集，有C30＝1個(gè)：

；

1元子集，有C31

＝3個(gè)：{a},,{c}；

2元子集，有C32

＝3個(gè)：{a,b},{a,c},{b,c}；

3元子集，有C33＝1個(gè)：{a,b,c}。共有C30＋C31＋C32＋C33

＝8個(gè)子集。27例1.15設(shè)集合A={a,b,c},寫(xiě)出它的全部子集。例1.16設(shè)集合A={Φ,{a},,{c}},寫(xiě)出它的全部子集。28一般地，對(duì)于n元子集，它的m（0

m

n）元子集有個(gè)，所以集合A的不同子集總數(shù)有Cn0＋Cn1＋…＋Cnn

＝2n個(gè)。定義1.6

對(duì)于每個(gè)非空集合S，至少有兩個(gè)不同的子集?和S，稱?和S是S的平凡子集。291.2.3特殊的集合定義1.7

不包含任何元素的集合稱為空集，用符號(hào)

或{}表示。定理1.2

是一切集合的子集.證明

反證法。設(shè)存在某一集合A，使得

不是集合A的子集，則存在x∈

且xA。這與

的定義相矛盾。因此定理成立。定理1.3空集是唯一的.證明假設(shè)有2個(gè)空集

1和

2，由定理1.2得出

1

2

，且

2

1

。再由集合相等的定義有

1=

2

。故空集是唯一的。例1.17：A={x

x2+x+2=0,x

R}，這是空集。

30定義1.8在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集。記作U。例如全體自然數(shù)組成了全集。全集的概念是相對(duì)的。不同的問(wèn)題有不同的全集，即使同一問(wèn)題也可以取不同的全集，全集的選取要看具體研究的問(wèn)題。如要研究2007年全國(guó)畢業(yè)大學(xué)生的就業(yè)情況，則將2007年畢業(yè)的所有的大學(xué)生全體作為全集；若只研究上海市2007年畢業(yè)的大學(xué)生就業(yè)情況時(shí)，只需將2007年上海市畢業(yè)的大學(xué)生全體作為全集。311.3集合的運(yùn)算定義1.9設(shè)A、B是兩個(gè)集合,由集合A和B中所有的元素組成的集合稱為集合A與B的并集,記作A∪B,讀作“A并B”。即A∪B是由屬于A或?qū)儆贐的元素所組成,用符號(hào)表示為A∪B={x|x∈A或x∈B}32例1.18設(shè)集合A={1,2,3},集合B={a,b}，則A∪B＝{1,2,3,a,b}。例1.19設(shè)集合A={1,2,3},集合B={a,b,1,2}，則A∪B＝{1,2,3,a,b}。例1.20設(shè)集合A={1,2,3},集合B={x|x2+x+2=0,x∈R},則A∪B={1,2,3}。33定義1.10

設(shè)A、B是兩個(gè)集合，由集合A和B中公共元素組成的集合稱為集合A與B的交集，記作A∩B，即A∩B是由既屬于A又屬于B的元素組成，用符號(hào)表示為：

A∩B＝{x|x∈A且x∈B}34例1.21設(shè)集合A={1,2,3},集合B={a,b}，則A∩B＝

。例1.22設(shè)集合A={1,2,3},集合B={a,b,1,2}，則A∩B＝{1,2}。例1.23設(shè)集合A={1,2,3},集合B={x|x2+x+2=0,x∈R},則A∩B=

。35兩個(gè)集合的并和交運(yùn)算可以推廣成n個(gè)集合的并和交，我們用公式表示如下：36定義1.11

設(shè)A、B是兩個(gè)集合，由在集合A中且不在集合B中的所有元素組成的集合，稱為集合B對(duì)A的相對(duì)補(bǔ)集，記作A-B，用符號(hào)表示為：

A－B＝{x|x∈A且x

B}37例1.24設(shè)集合A={1,2,3},集合B={a,b}，則A-B＝{1,2,3}。例1.25設(shè)集合A={1,2,3},集合B={a,b,1,2}，則A-B＝{3}。例1.26設(shè)集合A={1,2,3},集合B={x|x2+x+2=0,x∈R},則A-B=A。38定義1.12

集合的絕對(duì)補(bǔ)，是對(duì)于全集而言的，設(shè)U為全集，則集合A的絕對(duì)補(bǔ)集是由不在集合A中的所有的元素構(gòu)成的集合，稱為A的絕對(duì)補(bǔ)集，記作或A

表示，絕對(duì)補(bǔ)集也簡(jiǎn)稱為補(bǔ)集，用符號(hào)表示為：

A

=U-A={x|x

U且x

A}例1.27設(shè)集合U={1,2,3},求下列集合的補(bǔ)集。（1）集合A={1,2}。（2）集合A＝

。39定義1.13

集合A和B的對(duì)稱差定義如下式所示：

A

B=（A-B)∪(B-A)或用符號(hào)表示為：

A

B={x|x

A且x

B,或x

B且x

A}例1.28設(shè)集合A={1,2,3},集合B={a,b,1,2}，則A

B=(A-B)∪(B-A)={3}∪{a，b}={a，b，3}40集合運(yùn)算定律（1）雙重否定律(A

)

=A（2）交換律A∪B=B∪AA∩B=B∩AA

B=B

A（3）結(jié)合律A∪(B∪C)=(A∪B)∪CA∩(B∩C)=(A∩B)∩CA

(B

C)=(A

B)

C（4）分配律A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)A∩(B－C)

(A-B)∪(A-C)(A∪B)－(A∪C)

A∪(B－C)41集合運(yùn)算定律（5）同一律A∪=AA∩U=AA－=AA=A（6）互補(bǔ)律A∪A=U（7）矛盾律A∩A=（8）冪等律A∪A=AA∩A=A（9）零一律A∪U=UA∩=A－A=AA=（10）吸收律A∪(A∩B)=AA∩(A∪B)=A42集合運(yùn)算定律（11）德摩根律=UU=(A∪B)=A∩B(A∩B)=A∪BA－(B∪C)=(A－B)∩(A－C)A－(B∩C)=(A－B)∪(A－C)（12）功能完備律A－B=A∩B’AB=(A∪B)－(A∩B)=(A－B)∪(B－A)=(A∩B)∪(A∩B)431.3.2有限集合的計(jì)數(shù)有了集合的運(yùn)算定律，結(jié)合前面介紹的集合的基數(shù)的概念，可以求出任意一個(gè)有限集合中元素的個(gè)數(shù)，計(jì)算出有限集合中元素的個(gè)數(shù)通常有兩種方法：文氏圖法和排斥原理。下面分別來(lái)介紹這兩種方法：文氏圖法與排斥原理法。441.文氏圖法：每一條性質(zhì)定義為一個(gè)集合，用一個(gè)圓來(lái)表示，如無(wú)特殊說(shuō)明，任何兩個(gè)圓畫(huà)成相交的，然后將已知集合的元素填入表示該集合的區(qū)域內(nèi)。通常從n個(gè)集合的交集填起，根據(jù)計(jì)算的結(jié)果逐步將數(shù)字填入其它各空白區(qū)域。如果交集的值是未知的，可以設(shè)為x，根據(jù)題目的條件列出方程或方程組，求出所需結(jié)果。45例1.29對(duì)24名會(huì)外語(yǔ)的科技人員進(jìn)行掌握外語(yǔ)情況的調(diào)查。其統(tǒng)計(jì)結(jié)果如下：會(huì)英、日、德和法語(yǔ)的人分別為13，5，10和9人，其中同時(shí)會(huì)英語(yǔ)和日語(yǔ)的有2人，會(huì)英、德和法語(yǔ)中任兩種語(yǔ)言的都是4人。已知會(huì)日語(yǔ)的人既不懂法語(yǔ)也不懂德語(yǔ)，分別求只會(huì)一種語(yǔ)言(英、德、法、日)的人數(shù)和會(huì)三種語(yǔ)言的人數(shù)。462.排斥原理法：設(shè)U為全集,A1，A2，…，An為U的有限子集,則有如下3個(gè)公式。(1)兩個(gè)集合的排斥原理公式：|A1∪A2|=|A1|+|A2|-|A1∩A2|(2)三個(gè)集合的排斥原理公式：|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|-|A1∩A3|-|A2∩A3|+|A1∩A2∩A3|(3)個(gè)集合的排斥原理公式

47由排斥原理，我們很容易得到如下幾個(gè)結(jié)論成立：48例1.30在20名青年有10名是公司職員，12名是學(xué)生，其中5名既是職員又是學(xué)生，問(wèn)有幾名既不是職員，又不是學(xué)生。49例1.30在20名青年有10名是公司職員，12名是學(xué)生，其中5名既是職員又是學(xué)生，問(wèn)有幾名既不是職員，又不是學(xué)生。解設(shè)集合A是職員集合，集合B是學(xué)生集合，根據(jù)題意有：

A

=10，

B

=12，

A∩B

=5

A∪B

=

A

+

B

-

A∩B

=10+12-5=17則

(A∪B)

=

E

-

A∪B

=20-17=3因此，有3名既不是職員又不是學(xué)生。50例1.31某班有學(xué)生60人,其中38人學(xué)習(xí)pascal語(yǔ)言,有16人學(xué)習(xí)C語(yǔ)言,有21人學(xué)習(xí)Fortran語(yǔ)言,有3人這三種語(yǔ)言都學(xué)習(xí),有4人這三種語(yǔ)言都不學(xué)習(xí),問(wèn)僅學(xué)習(xí)兩門(mén)語(yǔ)言的學(xué)生數(shù)是多少?51解設(shè)A是學(xué)習(xí)pascal語(yǔ)言的學(xué)生集合，B是學(xué)習(xí)C語(yǔ)言的學(xué)生集合，C是學(xué)習(xí)Fortran語(yǔ)言的學(xué)生集合，根據(jù)題意有：|A|=38，|B|=16，|C|=21，|A∩B∩C|=3，|A∪B∪C|+4=60，即|A∪B∪C|=56因?yàn)閨A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|故|A∩B|+|A∩C|+|B∩C|=38+16+21+3-56=22所求僅學(xué)生兩門(mén)語(yǔ)言的學(xué)生人數(shù)應(yīng)為|(A∩B∩C’)∪(A∩B’∩C)∪(A’∩B∩C)|=|A∩B|+|A∩C|+|B∩C|-3|A∩B∩C|=22-3

3=13即僅學(xué)習(xí)兩門(mén)語(yǔ)言的學(xué)生數(shù)為13人。52例1.32某市舉行中學(xué)生數(shù)學(xué)、物理、化學(xué)三科競(jìng)賽，共有100人參加競(jìng)賽，結(jié)果數(shù)學(xué)優(yōu)秀者為41人，物理優(yōu)秀者為46人，化學(xué)優(yōu)秀者為39人，三門(mén)課全優(yōu)者為8人，僅兩門(mén)課為優(yōu)者26人，問(wèn)沒(méi)有得到優(yōu)秀的人數(shù)是多少？53解設(shè)A表示數(shù)學(xué)優(yōu)秀者的集合，B表示物理優(yōu)秀者的集合，C表示化學(xué)優(yōu)秀者的集合。由題意可得：

|A|=41，|B|=46，|C|=39，|A∩B∩C|=8僅兩門(mén)課為優(yōu)秀的人數(shù)為：|(A∩B∩C’)∪(A∩B’∩C)∪(A’∩B∩C)|=|A∩B|+|A∩C|+|B∩C|-3|A∩B∩C|即26=|A∩B|+|A∩C|+|B∩C|-3*8因此|A∩B|+|A∩C|+|B∩C|=50因此一門(mén)課為優(yōu)秀的人數(shù)為：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|=41+46+39-50+8=84因此沒(méi)有得到的優(yōu)秀的人數(shù)為100-84=16（人）54例1.33使用包含排斥原理求不超過(guò)120的素?cái)?shù)個(gè)數(shù)。解:因?yàn)?12=121,不超過(guò)120的合數(shù)(除了1和它自身還能被其他數(shù)整除的數(shù))至少有2,3,5或7這幾個(gè)素因子之一,首先考慮不能被2,3,5,7整除的整數(shù),設(shè)S={x|x∈Z,1≤x≤120}A1={x|x∈S,x是2的倍數(shù)}A2={x|x∈S,x是3的倍數(shù)}A3={x|x∈S,x是5的倍數(shù)}A4={x|x∈S,x是7的倍數(shù)}則上述集合的基數(shù)分別為|S|=120,|A1|=60,|A2|=40,|A3|=24,|A4|=17|A1∩A2|=20,|A1∩A3|=12,|A1∩A4|=8,|A2∩A3|=8,|A2∩A4|=5,|A3∩A4|=3|A1∩A2∩A3|=4,|A1∩A2∩A4|=2,|A1∩A3∩A4|=1,|A2∩A3∩A4|=1,|A1∩A2∩A3∩A4|=0根據(jù)包含排斥原理,不能被2,3,5,7整除的整數(shù)有|A'1∩A'2∩A'3∩A'4|=120-(60+40+24+17)+(20+12+8+8+5+3)-(4+2+1+1)+0=27因?yàn)?、3、5、7不滿足上述條件,但是它們都是素?cái)?shù)。另外,1滿足上述條件,但是1不是素?cái)?shù),因此,不超過(guò)120的素?cái)?shù)有27+4-1=30個(gè)。551.4冪集和編碼1.4.1冪集定義1.14

給定集合A，由集合A的所有子集為元素組成的集合，稱為集合A的冪集，記為P(A)或2A，即P(A)=2A={X|X

A}。561.4冪集和編碼例1.34設(shè)集合A＝{a，b，c}，則P(A)＝{

，{a}，，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}例1.35計(jì)算下列集合的冪集。(1)A=

。(2)B=P(

)。(3)C={

,P(

)}。57

定理1.4

如果有限集合A中有n個(gè)元素，則其冪集P(A)有2n個(gè)元素。證明由A的k個(gè)元素組成的子集的個(gè)數(shù)為Cnk，當(dāng)k從0取到n時(shí)就構(gòu)成了集合A的所有的子集，因此集合A的子集的個(gè)數(shù)為：

Cn0+Cn1+…+Cnn=2n

因此P(A)的元素個(gè)數(shù)是2n

。58定理1.5設(shè)A、B是任意兩個(gè)集合，則有如下結(jié)論成立：（1）當(dāng)AB當(dāng)且僅當(dāng)P(A)P(B)（2）P(A)∪P(B)P(A∪B)（3）P(A∩B)=P(A)∩P(B)（4）P(A’)(P(A))’59證明:(1)必要性:對(duì)

xP(A)xAxBxP(B)

因此P(A)P(B)

充分性:對(duì)

xA{x}P(A){x}P(B)xB

因此AB60(2)對(duì)xP(A)∪P(B)

xP(A)xP(B)

xAxB

xA∪B

xP(A∪B)P(A)∪P(B)P(A∪B)例:P(A)∪P(B)P(A∪B)A={1},B={2},A∪B={1,2}P(A)∪P(B)={,{1},{2}}P(A∪B)={,{1},{2},{1,2}}61(3)對(duì)xP(A∩B)

xA且xB

xP(A)且xP(B)

xP(A)∩P(B)(4)顯然成立，不用證明。621.4.2冪集元素與編碼現(xiàn)在引進(jìn)一種編碼，用來(lái)唯一地表示有限集冪集的元素。設(shè)集合A中有n個(gè)元素，確定下標(biāo)為n位的二進(jìn)制數(shù)，每一位對(duì)應(yīng)集合A中的一個(gè)元素。如果元素在某個(gè)子集中出現(xiàn)，則相應(yīng)的二進(jìn)制位為1，否則為0。以集合A={a,b,c}為例：是二進(jìn)制數(shù)且將P（A）中的各個(gè)元素詳細(xì)描述如下：

=A000，{a}=A100，=A010，{c}=A001，{a,b}=A110，{a,c}=A101，{b,c}=A011，{a,b,c}=A11163補(bǔ)集的編碼表示：設(shè)Ai1i2…in是集合A的子集，i1i2…in是Ai1i2…in的二進(jìn)制編碼表示，則Ai1i2…in

補(bǔ)集的二進(jìn)制編碼表示只需將每個(gè)1換成0，0換成1即可。如A001的補(bǔ)集為A110。

64兩個(gè)子集交的編碼表示：兩個(gè)子集交的編碼是兩個(gè)子集編碼對(duì)應(yīng)位置的布爾乘。布爾乘規(guī)則如下：1×1=1，1×0=0，0×1=0，0×0=0則A001與A101的交集為A001。兩個(gè)子集并的編碼表示：兩個(gè)子集并的編碼是兩個(gè)子集編碼對(duì)應(yīng)位置的布爾加法。布爾加規(guī)則如下：1+1=1，1+0=1，0+1=1，0+0=0則A001與A101的并集為A101。65例1.36:設(shè)S={a1,a2,…,a6}.由S15和S22所表示的S的子集是什么?如何表示子集{a3,a5}和{a2,a4,a6}?解：S15=S001111={a3,a4,a5,a6}S22=S010110={a2,a4,a5}{a3,a5}=S001010=S10{a2,a4,a6}=S010101=S21661.5集合恒等式證明通過(guò)對(duì)集合恒等式的證明的練習(xí)，既可以加深對(duì)集合性質(zhì)的理解與掌握，又可以為命題邏輯中公式的基本等價(jià)式的應(yīng)用打下良好的基礎(chǔ)。因此，集合恒等式的證明實(shí)際上是一種基本功訓(xùn)練。本節(jié)主要介紹三種方法來(lái)證明集合恒等式，分別是基本定義法、公式法和集合成員表的方法。67例1.38設(shè)A、B、C是任意集合，證明

A-(B∪C)=(A-B)∩(A-C)

。證明:對(duì)于?x∈A-(B∪C)?x∈A且x?(B∪C)?x∈A且(x?B且x?C)?(x∈A且x?B)且(x∈A且x?C)?x∈(A-B)且x∈(A-C)?x∈(A-B)∩(A-C)因此A-(B∪C)=(A-B)∩(A-C)。

681.5.2公式法所謂公式法就是利用已證明過(guò)的集合恒等式去證明新的集合恒等式。在用公式法證明集合恒等式的時(shí)候，要充分利用集合的運(yùn)算定律，同時(shí)注意以下幾個(gè)基本原則：(1)將集合運(yùn)算表達(dá)式中其他運(yùn)算符號(hào)轉(zhuǎn)換為∪和∩；(2)將補(bǔ)運(yùn)算作用到單一集合上；(3)左邊

右邊，右邊

左邊，左邊

中間式，右邊

中間式；(4)根據(jù)基本運(yùn)算符號(hào)的定義和運(yùn)算定律轉(zhuǎn)換。69例1.39設(shè)A、B、C是任意三個(gè)集合，證明A∩(B-C)=(A∩B)-(A∩C)證明A∩(B-C)=A∩(B∩C

)=A∩B∩C

又(A∩B)-(A∩C)=(A∩B)∩(A∩C)

=(A∩B)∩(A

∪C

)=(A∩B∩A

)∪(A∩B∩C

)=

∪(A∩B∩C’)=A∩B∩C

所以A∩(B-C)=(A∩B)-(A∩C)70例1.40設(shè)A、B、C是任意三個(gè)集合，證明A∪(B∩C)=(A∪B)∩(A∪C)證明(A∪B)∩(A∪C)=((A∪B)∩A)∪((A∪B)∩C)=(A∩(A∪B))∪(C∩(A∪B))=A∪(C∩(A∪B))=A∪((C∩A)∪(C∩B))=(A∪(A∩C))∪(B∩C)=A∪(B∩C)。所以A∪(B∩C)=(A∪B)∩(A∪C)71例1.41設(shè)A、B、C是任意三個(gè)集合，證明(A∩B)∪(A∩C)∪(B∩C)=(A∪B)∩(A∪C)∩(B∪C)證明(A∩B)∪(A∩C)∪(B∩C)=(A∪A∪B