第六章集合代數(shù)課件

6.1集合的基本概念方程x2-1=0的實(shí)數(shù)解集合,1和-1是該集合的元素;26個(gè)英文字母的集合,a,b,…,z是該集合的元素;坐標(biāo)平面上所有點(diǎn)的集合;

<0,0>,<0,1>,<1,1>是該集合的元素;常用的集合名稱:N:自然數(shù)集合(本課程中認(rèn)為0也是自然數(shù))Z:整數(shù)集合 Q:有理數(shù)集合R:實(shí)數(shù)集合 C:復(fù)數(shù)集合集合(Set)是一些個(gè)體匯集在一起所組成整體.通常把整體中的個(gè)體稱為集合的元素或成員.例如:集合是不能精確定義的基本概念。6.1集合的基本概念方程x2-1=0的實(shí)1集合有三種表示方法:列元素法、謂詞表示法和圖示法.列元素法:列出集合中的所有元素,各元素之間用逗號(hào)隔開,并把它們用花括號(hào)括起來(lái).例如

A={a,b,c,…,z}Z={0,±1,±2,…}謂詞表示法:用謂詞來(lái)概括集合中元素的屬性.例如:B={x|x

R且x2-1=0}集合B表示方程x2-1=0的實(shí)數(shù)解集.許多集合可用兩種方法來(lái)表示,如:B={-1,1}.有些集合不能用列元素法表示,如:實(shí)數(shù)集合,不能列舉出所有集合中的所有元素.圖示法:用一個(gè)圓來(lái)表示,圓中的點(diǎn)表示集合中的元素.

6.1集合的基本概念集合有三種表示方法:列元素法、謂詞表示法和圖示法.列元素法:2集合的元素是彼此不同的.若同一個(gè)元素在集合中多次出現(xiàn),則只認(rèn)為其是一個(gè)元素;

如:{1,1,2,2,3}={1,2,3}集合的元素是無(wú)序的,如:

{3,1,2}={1,2,3}本書規(guī)定:集合的元素都是集合.

6.1集合的基本概念集合的元素是彼此不同的.若同一個(gè)元素在集合中多次出現(xiàn),則只3元素(Element)和集合之間的隸屬關(guān)系:“屬于”或“不屬于”.“屬于”關(guān)系記作,“不屬于”記作.例如:A={a,{b,c},d,{6976xt1}}.

aA,{b,c}A,dA,{4rgtglg}A,

bA,rthbzesA.

b和scxlycv是A元素的元素.為了體系的嚴(yán)謹(jǐn)性,規(guī)定:對(duì)任何集合A,都有:AA.A={a,{b,c},d,{49xczoy}}的樹形圖表示.a{b,c}Ad{m139upd}bc148oknid

6.1集合的基本概念元素(Element)和集合之間的隸屬關(guān)系:“屬于”或“不4如果B不被A包含,則記作BA.包含的符號(hào)化表示為

BAx(xBxA)例如:NZQRC,但,ZN.顯然,對(duì)任何集合A,都有:AA.包含關(guān)系表示集合之間的關(guān)系;隸屬關(guān)系表示元素和集合之間的關(guān)系,但也可表示某些集合之間關(guān)系.如: {a}{a,{a}},{a}{a,{a}}定義6.1

設(shè)A和B為集合,若B中的每個(gè)元素都是A的元素,則稱B是A的子集合,簡(jiǎn)稱子集(Subset),也可稱B被A包含,或A包含B,記作BA.

AB

6.1集合的基本概念：等值的：蘊(yùn)涵式如果B不被A包含,則記作BA.定義6.1設(shè)A和B5定義6.2

設(shè)A和B為集合,如果AB且BA,則稱A與B相等,記作:A=B.若A與B不相等,則記作:A

B.相等的符號(hào)化表示為

A=B

AB∧BA

x(xAxB)∧x(xBxA)定義6.3

設(shè)A和B為集合,如果BA且B

A,則稱B是A的真子集(ProperSubset),記作BA.若B不是A的真子集,則記為:BA.真子集的符號(hào)化表示為:BABA∧B

A例如:NZQRC,但,NN.

6.1集合的基本概念定義6.2設(shè)A和B為集合,如果AB且BA,6定義6.4

不含任何元素的集合叫做空集,記作:.空集可以符號(hào)化表示為:={x|x

x}.例如:{x|xR∧x2+1=0}是方程x2+1=0的實(shí)數(shù)解集,因?yàn)樵摲匠虩o(wú)實(shí)數(shù)解,所以,其解集是空集.定理6.1

空集是一切集合的子集.任給一個(gè)集合A,由子集的定義可知:

Ax(xxA)由于蘊(yùn)涵式(x

xA)的前件為假而使其成為真命題,所以,

A.

6.1集合的基本概念證假設(shè):存在空集1和2.由定理6.1可知:1

2,2

1.由集合相等的定義可知:1=2.推論空集是惟一的.證定義6.4不含任何元素的集合叫做空集,記作:.空集可7例6.1A={1,2,3},將A的子集分類:假設(shè)有一個(gè)含有n個(gè)元素的集合A（n元集）,若集合A1是其子集且|A1|=m,則稱子集A1為集合A的m元子集.對(duì)任給一個(gè)n元集合A,如何求出它的全部子集?0元子集,即空集,只有一個(gè):;1元子集,即單元集:{1},{2},{3};2元子集:{1,2},{1,3},{2,3};3元子集:{1,2,3}.由上面的例子,我們不難歸納出:對(duì)n元集合A,有:0元子集有Cn0個(gè)1元子集有Cn1個(gè)…m元子集有Cnm個(gè)…n元子集有Cnn個(gè)子集總數(shù)為Cn0+Cn1+…+Cnn=2n個(gè)定義集合A中元素的個(gè)數(shù)n為集合的勢(shì)(Cardinality),記為|A|.

6.1集合的基本概念例6.1A={1,2,3},將A的子集分類:8全集是有相對(duì)性的,不同的問題有不同的全集,即使是同一個(gè)問題也可以取不同的全集.例如:在研究平面上直線的相互關(guān)系時(shí),可把整個(gè)平面上所有點(diǎn)的集合看作全集,也可把整個(gè)空間上所有點(diǎn)的集合看作全集.一般地說(shuō),全集取得小一些,問題的描述和處理會(huì)簡(jiǎn)單些.冪集的符號(hào)化表示為:P(A)={x|xA}.對(duì)于集合A={1,2,3},有:P(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.不難看出,若A是n元集,則P(A)有2n個(gè)元素.定義6.6在某具體問題中,若所涉及的集合都是某個(gè)集合的子集,則稱該集合為全集(UniversalSet),記作E.定義6.5

設(shè)A為集合,把A的全體子集構(gòu)成的集合叫做A的冪集(PowerSet),記作P(A),PA,2A.

6.1集合的基本概念全集是有相對(duì)性的,不同的問題有不同的全集,即使是同一個(gè)問9集合的基本運(yùn)算有并(Union),交(Intersection)和相對(duì)補(bǔ)(Relative

Complement).定義6.7設(shè)A和B為集合,A與B的并集A∪B,交集A∩B,B對(duì)A的相對(duì)補(bǔ)集A-B分別定義如下:A∪B={x|x

A∨x

B}A∩B={x|x

A∧x

B}A-B={x|x

A∧xB}由定義可知:A∪B是由A或B的元素構(gòu)成,A∩B由A和B的公共元素構(gòu)成,A-B由屬于A,但不屬于B的元素構(gòu)成.例如:A={a,b,c},B={a},C={b,d},則:

A∪B={a,b,c}

A∩B={a}

A-B={b,c}

B-A=,B∩C=若兩個(gè)集合的交集為,則稱這兩個(gè)集合是不相交的.如:B和C是不相交的.

6.2集合的運(yùn)算集合的基本運(yùn)算有并(Union),交(Intersecti10n個(gè)集合的并和交:無(wú)窮多個(gè)集合的并和交:∪i=1..∞Ai=A1∪A2∪…∩i=1..∞Ai=A1∩A2∩…∪i=1..nAi=A1∪A2∪…∪An={x|xA1∨…∨xAn)∩i=1..nAi=A1∩A2∩…∩An={x|xA1∧…∧xAn)

6.2集合的運(yùn)算n個(gè)集合的并和交:無(wú)窮多個(gè)集合的并和交:∪i=1..∞Ai11例如A={a,b,c},B={b,d},則:AB={a,c,d}對(duì)稱差運(yùn)算的另一種定義是

AB=(A∪B)-(B∩A)在給定全集E以后,AE,A的絕對(duì)補(bǔ)集~A定義如下:集合的對(duì)稱差集(SymmetricDifference)和絕對(duì)補(bǔ)集(AbsoluteComplement).定義6.9~A=E–A={x|xE∧xA}因?yàn)镋是全集,xE是真命題,所以,~A可以定義為~A={x|xA}.例如:E={a,b,c,d},A={a,b,c},則, ~A=9o6xixq.定義6.8

設(shè)A和B為集合,A與B的對(duì)稱差集AB定義為:

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

6.2集合的運(yùn)算例如A={a,b,c},B={b,d12

6.2集合的運(yùn)算以上定義的并和交運(yùn)算稱為初級(jí)并和初級(jí)交.

下面考慮推廣的并和交運(yùn)算,即廣義并和廣義交.6.2集合的運(yùn)算以上定義的并和交運(yùn)算稱為初級(jí)并和初13定義6.10

設(shè)A為集合,A的元素的元素構(gòu)成的集合稱為A的廣義并,記為∪A.符號(hào)化表示為:

∪A={x|z(zA∧xz)}根據(jù)廣義并的定義不難得到:若A={A1,A2,…,An},則 ∪A=A1∪A2∪…∪An類似地可以定義集合的廣義交.例6.4設(shè)

A={{a,b,c},{a,c,d},{a,e,f}} B={{a}} C={a,{c,d}}則 ∪A={a,b,c,d,e,f} ∪B={a} ∪C=a∪{c,d} ∪=

6.2集合的運(yùn)算定義6.10設(shè)A為集合,A的元素的元素構(gòu)成的集合稱為A14例6.4: A={{a,b,c},{a,c,d},{a,e,f}} B={{a}}C={a,{c,d}}有: ∩A={a},∩B={a},∩C=a∩{c,d}定義6.11

設(shè)A為非空集合,A的所有元素的公共元素所構(gòu)成的集合稱為A的廣義交,記為∩A.符號(hào)化表示為 ∩A={x|z(zA

xz)}定義6.11中,特別強(qiáng)調(diào)A是非空集合;對(duì)于空集可以進(jìn)行廣義并,即:∪

=;空集不可進(jìn)行廣義交,因?yàn)椤刹皇羌?

在集合論中是沒有意義的;若A={A1,A2,…,An},則∩A=A1∩A2∩…∩An.

6.2集合的運(yùn)算例6.4:定義6.11設(shè)A為非空集合,A的所有元素的公15稱廣義并,廣義交,冪集,絕對(duì)補(bǔ)運(yùn)算為一類運(yùn)算,并,交,相對(duì)補(bǔ)和對(duì)稱差運(yùn)算為二類運(yùn)算.下面的集合公式都是合理的公式:∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)一類運(yùn)算優(yōu)先于二類運(yùn)算一類運(yùn)算之間由右向左順序進(jìn)行二類運(yùn)算之間由括號(hào)決定先后順序

6.2集合的運(yùn)算稱廣義并,廣義交,冪集,絕對(duì)補(bǔ)運(yùn)算為一類運(yùn)算,并,16例6.5設(shè)A={{a},{a,b}},計(jì)算∪∪A,∩∩A,∪∩A,∩∪A.解 ∪A={a,b} ∩A={a} ∪∪A=a∪b ∩∩A=a ∩∪A=a∩b ∪∩A=a

6.2集合的運(yùn)算例6.5設(shè)A={{a},{a,b}17例6.5（續(xù)）設(shè)A={{a},{a,b}},計(jì)算∩∪A∪(∪∪A-∪∩A)（練習(xí)）.解 ∪A={a,b} ∩A={a} ∪∪A=a∪b ∩∩A=a ∩∪A=a∩b ∪∩A=a ∩∪A∪(∪∪A-∪∩A)

=(a∩b)∪((a∪b)-a)

=(a∩b)∪(b-a)

=b所以∪∪A=a∪b,∩∩A=a, ∩∪A∪(∪∪A-∪∩A)=b.

6.2集合的運(yùn)算例6.5（續(xù)）設(shè)A={{a},{a,b18課后作業(yè)(1)習(xí)題六第5,6,8,9,11,14題（4小題（含）以上的題做奇數(shù)小題；否則全做。）（第96-98頁(yè)）.課后作業(yè)(1)習(xí)題六19EEBEB文氏圖(VennDiagrams)EABA∩B=AA∩B=AEABA-BEABA∪BEABA∩BEA~AAABB(A∩B)-CAC

6.3有窮集的計(jì)數(shù)EEBEB文氏圖(VennDiagrams)EABA∩B20有窮集的計(jì)數(shù)使用文氏圖可以很方便地解決有窮集的計(jì)數(shù)問題。首先根據(jù)已知條件把對(duì)應(yīng)的文氏圖畫出來(lái)一般地說(shuō)，每一條性質(zhì)決定一個(gè)集合。有多少條性質(zhì)，就有多少個(gè)集合。如果沒有特殊說(shuō)明，任何兩個(gè)集合都畫成相交的。然后將已知集合的元素?cái)?shù)填入表示該集合的區(qū)域內(nèi)通常從n個(gè)集合的交集填起，根據(jù)計(jì)算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設(shè)為x。根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所需要的結(jié)果。

有窮集的計(jì)數(shù)使用文氏圖可以很方便地解決有窮集的計(jì)數(shù)問題。21例6.2對(duì)24名人員掌握外語(yǔ)情況的調(diào)查.其統(tǒng)計(jì)結(jié)果如下:解令A(yù),B,C和D分別表示會(huì)英、法、德、日語(yǔ)的人的集合.設(shè)同時(shí)會(huì)三種語(yǔ)言的有x人,只會(huì)英、法或德語(yǔ)一種語(yǔ)言的分別為y1,y2和y3.畫出的圖如右圖.列出下面方程組:y1+2(4-x)+x+2=13y2+2(4-x)+x=9y3+2(4-x)+x=10y1+y2+y3+3(4-x)+x=19解得:x=1,y1=4,y2=3,y3=3.y224-xy1x4-x4-xy35-2DACB會(huì)英、日、德、法分別為:13,5,10和9人;同時(shí)會(huì)英語(yǔ)和日語(yǔ)的有2人;會(huì)英、德和法語(yǔ)中任兩種語(yǔ)言的都是4人.已知會(huì)日語(yǔ)的人既不懂法語(yǔ)也不懂德語(yǔ),分別求只會(huì)一種語(yǔ)言(英、德、法、日)的人數(shù)和會(huì)三種語(yǔ)言的人數(shù).

6.3有窮集的計(jì)數(shù)例6.2對(duì)24名人員掌握外語(yǔ)情況的調(diào)查.其統(tǒng)計(jì)結(jié)果如下:2241BAC例6.3求1到1000之間(包含1和1000在內(nèi)),既不能被5和6,也不能被8整除的數(shù)有多少個(gè).解設(shè)S={x|xZ∧1

x

1000}A={x|xS∧x可被5整除}B={x|xS∧x可被6整除}C={x|xS∧x可被8整除}|A|=int(1000/5)=200|B|=int(1000/6)=166|C|=int(1000/8)=125|A∩B|=int(1000/lcm(5,6))=33|A∩C|=int(1000/lcm(5,8))=25|B∩C|=int(1000/lcm(6,8))=41|A∩B∩C|=int(1000/lcm(5,6,8))=81000-(200+100+33+67)=600171502581333320016612516733672510059+A∩B∩C

6.3有窮集的計(jì)數(shù)41BAC例6.3求1到1000之間(包含1和1000在內(nèi)23定理6.2(包含排斥原理)

設(shè)S為有窮集,P1,P2,…,Pm是m個(gè)性質(zhì).S中的任何元素x或者具有性質(zhì)Pi,或者不具有性質(zhì)Pi(i=1..m),兩種情況必居其一.

令A(yù)i表示S中具有性質(zhì)Pi的元素構(gòu)成的子集,則S中不具有性質(zhì)P1,P2,…,Pm的元素?cái)?shù)為:

6.3有窮集的計(jì)數(shù)定理6.2(包含排斥原理)設(shè)S為有窮集,P1,P2,24推論

S中至少具有一條性質(zhì)的元素?cái)?shù)為根據(jù)包含排斥原理,例6.3中所求的元素?cái)?shù)為:|A∩B∩C|=|S|-(|A|+|B|+|C|) +(|A∩B|+|A∩C|+|B∩C|)-|A∩B∩C| =1000-(200+166+125)+(33+25+41)-8=600

6.3有窮集的計(jì)數(shù)推論S中至少具有一條性質(zhì)的元素?cái)?shù)為根據(jù)包含排斥原理,例25歐拉函數(shù)歐拉函數(shù)Φ是數(shù)論中的一個(gè)重要函數(shù),設(shè)n是正整數(shù),Φ(n)表示{0,1,…,n-1}中與n互素的數(shù)的個(gè)數(shù).例如Φ(12)=4,因?yàn)榕c12互素的數(shù)有1,5,7,11.這里認(rèn)為Φ(1)=1.利用包含排斥原理給出歐拉函數(shù)的計(jì)算公式.分析

(1)因式分解！(2)包含排斥原理。歐拉函數(shù)歐拉函數(shù)Φ是數(shù)論中的一個(gè)重要函數(shù),設(shè)n是正整數(shù),Φ26歐拉函數(shù)（續(xù)）(1)因式分解給定正整數(shù)n,n的因式分解式為,

令則有(2)包含排斥原理首先計(jì)算由包含排斥原理得

歐拉函數(shù)（續(xù)）(1)因式分解27冪等率

–IdempotentLawsA∪A=A (6.1)A∩A=A (6.2)結(jié)合律

–AssociativeLaws(A∪B)∪C=A∪(B∪C) (6.3)(A∩B)∩C=A∩(B∩C) (6.4)交換律

–CommutativeLawsA∪B=B∪A (6.5)A∩B=B∩A (6.6)分配律

–DistributiveLawsA∪(B∩C)=(A∪B)∩(A∪C) (6.7)A∩(B∪C)=(A∩B)∪(A∩C) (6.8)

6.4集合恒等式冪等率–IdempotentLaws6.4集28同一率

–IdentityLaws

A∪=A (6.9)A∩E=A (6.10)零率–moreIdentitylaws

A∪E=E (6.11)A∩=

(6.12)排中率–ComplementationlawsA∪~A=E (6.13)A∩~A=

(6.14)

6.4集合恒等式同一率–IdentityLaws6.4集合恒29吸收率–

AbsorptionlawsA∪(A∩B)=A (6.15)A∩(A∪B)=A (6.16)德摩根律

–

DeMorganlawsA-(B∪C)=(A-B)∩(A-C) (6.17)A-(B∩C)=(A-B)∪(A-C) (6.18)~(B∪C)=~B∩~C (6.19)~(B∩C)=~B∪~C (6.20)~=E (6.21)~E=

(6.22)雙重否定率–

Double

Complementation~(~A)=A (6.23)

6.4集合恒等式吸收率–Absorptionlaws6.4集306.4集合恒等式例6.6證明:A-(B∪C)=(A-B)∩(A-C) (式6.17)分析（證明思路）（1）定義（集合的基本概念）；（2）命題邏輯中的等值演算。或者（3）根據(jù)前面的定理(集合恒等式)直接推導(dǎo)。6.4集合恒等式31例6.8證明:A-(B∪C)=(A-B)∩(A-C) (式6.17)證對(duì)任意x, x

A-(B∪C)

xA∧xB∪C

xA∧┐(xB∨xC)

xA∧(┐xB∧┐xC)

xA∧xB∧xC

(xA∧xB)∧(xA∧xC)

xA-B∧xA-C

x(A-B)∩(A-C)所以,A-(B∪C)=(A-B)∩(A-C)

6.4集合恒等式例6.8證明:A-(B∪C)=(A-B)∩32例6.9證明式6.10,即:A∩E=A.證對(duì)任意x,

xA∩E

xA∧xE

xA(因?yàn)閤E是恒真命題),所以,A∩E=A.以上證明的基本思想是:設(shè)P和Q為集合公式,欲證:

P=Q,即證PQ∧QP為真.要證對(duì)于任意的x有:

xPxQ和xQxP成立.對(duì)于某些恒等式,可將這兩個(gè)方向的推理合到一起,

就是xPxQ

6.4集合恒等式例6.9證明式6.10,即:A∩E=A.以上證明33證A∪(A∩B) =(A∩E)∪(A∩B) (6.10) =A∩(E∪B) (6.8) =A∩(B∪E) (6.5) =A∩E (6.11) =A (6.10)例6.10假設(shè)已知等式6.1-6.14,試證等式6.15:

A∪(A∩B)=A.

6.4集合恒等式證A∪(A∩B)例6.10假設(shè)已知等式6.1-6.34

6.4集合恒等式（練習(xí)）

證明:A-(B∩C)=(A-B)∪(A-C) (式6.18)6.4集合恒等式（練習(xí)）證明:A-35還有一些關(guān)于集合運(yùn)算性質(zhì)的重要結(jié)果.A∩B

A,A∩BB (6.24)AA∪B,BA∪B (6.25)A-BA (6.26)A-B=A∩~B (6.27)A∪B=B

AB

A∩B=A

A-B=

(6.28)AB=BA (6.29)(AB)C=A(BC) (6.30)A

=A (6.31)AA= (6.32)AB=ACB=C (6.33)

6.4集合恒等式還有一些關(guān)于集合運(yùn)算性質(zhì)的重要結(jié)果.A∩BA,A∩B36例6.11證明等式6.27,即A-B=A∩~B.證對(duì)于任意的x, xA-B

xA∧xB

xA∧x~B

xA∩~B所以,A-B=A∩~B.等式6.27把相對(duì)補(bǔ)運(yùn)算轉(zhuǎn)換成交運(yùn)算.

6.4集合恒等式例6.11證明等式6.27,即A-B=A∩~B37例6.12證明:(A-B)∪B=A∪B.證

(A-B)∪B

=(A∩~B)∪B

=(A∪B)∩(~B∪B)

=(A∪B)∩E

=A∪B

6.4集合恒等式例6.12證明:(A-B)∪B=A∪B.證38例6.13證明命題6.28是真命題:

A∪B=B

AB

A∩B=A

A-B=.證

1).證A∪B=B