第六章集合代數(shù)

第六章集合代數(shù)第1頁，共45頁，2023年，2月20日，星期三6.1集合的基本概念方程x2-1=0的實數(shù)解集合,1和-1是該集合的元素;26個英文字母的集合,a,b,…,z是該集合的元素;坐標平面上所有點的集合;

<0,0>,<0,1>,<1,1>是該集合的元素;常用的集合名稱:N:自然數(shù)集合(本課程中認為0也是自然數(shù))Z:整數(shù)集合 Q:有理數(shù)集合R:實數(shù)集合 C:復數(shù)集合集合(Set)是一些個體匯集在一起所組成整體.通常把整體中的個體稱為集合的元素或成員.例如:集合是不能精確定義的基本概念。第2頁，共45頁，2023年，2月20日，星期三集合有三種表示方法:列元素法、謂詞表示法和圖示法.列元素法:列出集合中的所有元素,各元素之間用逗號隔開,并把它們用花括號括起來.例如A={a,b,c,…,z}Z={0,±1,±2,…}謂詞表示法:用謂詞來概括集合中元素的屬性.例如:B={x|x

R且x2-1=0}集合B表示方程x2-1=0的實數(shù)解集.許多集合可用兩種方法來表示,如:B={-1,1}.有些集合不能用列元素法表示,如:實數(shù)集合,不能列舉出所有集合中的所有元素.圖示法:用一個圓來表示,圓中的點表示集合中的元素.6.1集合的基本概念第3頁，共45頁，2023年，2月20日，星期三集合的元素是彼此不同的.若同一個元素在集合中多次出現(xiàn),則只認為其是一個元素;

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

{3,1,2}={1,2,3}本書規(guī)定:集合的元素都是集合.6.1集合的基本概念第4頁，共45頁，2023年，2月20日，星期三元素(Element)和集合之間的隸屬關(guān)系:“屬于”或“不屬于”.“屬于”關(guān)系記作,“不屬于”記作.例如:A={a,{b,c},d,{8p4cli6}}. aA,{b,c}A,dA,{u0v1hzh}A, bA,4aqs6w9A. b和puuv0vz是A元素的元素.為了體系的嚴謹性,規(guī)定:對任何集合A,都有:AA.A={a,{b,c},d,{hyiro0l}}的樹形圖表示.a{b,c}Ad{asqc4cm}bcjdclz7xd6.1集合的基本概念第5頁，共45頁，2023年，2月20日，星期三如果B不被A包含,則記作BA.包含的符號化表示為

BAx(xBxA)例如:NZQRC,但,ZN.顯然,對任何集合A,都有:AA.包含關(guān)系表示集合之間的關(guān)系;隸屬關(guān)系表示元素和集合之間的關(guān)系,但也可表示某些集合之間關(guān)系.如: {a}{a,{a}},{a}{a,{a}}定義6.1設A和B為集合,若B中的每個元素都是A的元素,則稱B是A的子集合,簡稱子集(Subset),也可稱B被A包含,或A包含B,記作BA.AB6.1集合的基本概念：等值的：蘊涵式第6頁，共45頁，2023年，2月20日，星期三定義6.2設A和B為集合,如果AB且BA,則稱A與B相等,記作:A=B.若A與B不相等,則記作:A

B.相等的符號化表示為 A=B

AB∧BA

x(xAxB)∧x(xBxA)定義6.3設A和B為集合,如果BA且B

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

A例如:NZQRC,但,NN.6.1集合的基本概念第7頁，共45頁，2023年，2月20日，星期三定義6.4不含任何元素的集合叫做空集,記作:.空集可以符號化表示為:={x|x

x}.例如:{x|xR∧x2+1=0}是方程x2+1=0的實數(shù)解集,因為該方程無實數(shù)解,所以,其解集是空集.定理6.1空集是一切集合的子集.任給一個集合A,由子集的定義可知:

Ax(xxA)由于蘊涵式(x

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

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

2,2

1.由集合相等的定義可知:1=2.推論空集是惟一的.證第8頁，共45頁，2023年，2月20日，星期三例6.1A={1,2,3},將A的子集分類:假設有一個含有n個元素的集合A（n元集）,若集合A1是其子集且|A1|=m,則稱子集A1為集合A的m元子集.對任給一個n元集合A,如何求出它的全部子集?0元子集,即空集,只有一個:;1元子集,即單元集:{1},{2},{3};2元子集:{1,2},{1,3},{2,3};3元子集:{1,2,3}.由上面的例子,我們不難歸納出:對n元集合A,有:0元子集有Cn0個1元子集有Cn1個…m元子集有Cnm個…n元子集有Cnn個子集總數(shù)為Cn0+Cn1+…+Cnn=2n個定義集合A中元素的個數(shù)n為集合的勢(Cardinality),記為|A|.6.1集合的基本概念第9頁，共45頁，2023年，2月20日，星期三全集是有相對性的,不同的問題有不同的全集,即使是同一個問題也可以取不同的全集.例如:在研究平面上直線的相互關(guān)系時,可把整個平面上所有點的集合看作全集,也可把整個空間上所有點的集合看作全集.一般地說,全集取得小一些,問題的描述和處理會簡單些.冪集的符號化表示為:P(A)={x|xA}.對于集合A={1,2,3},有:P(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.不難看出,若A是n元集,則P(A)有2n個元素.定義6.6在某具體問題中,若所涉及的集合都是某個集合的子集,則稱該集合為全集(UniversalSet),記作E.定義6.5設A為集合,把A的全體子集構(gòu)成的集合叫做A的冪集(PowerSet),記作P(A),PA,2A.6.1集合的基本概念第10頁，共45頁，2023年，2月20日，星期三集合的基本運算有并(Union),交(Intersection)和相對補(Relative

Complement).定義6.7設A和B為集合,A與B的并集A∪B,交集A∩B,B對A的相對補集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=若兩個集合的交集為,則稱這兩個集合是不相交的.如:B和C是不相交的.

6.2集合的運算第11頁，共45頁，2023年，2月20日，星期三n個集合的并和交:無窮多個集合的并和交:∪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集合的運算第12頁，共45頁，2023年，2月20日，星期三例如A={a,b,c},B={b,d},則:AB={a,c,d}對稱差運算的另一種定義是 AB=(A∪B)-(B∩A)在給定全集E以后,AE,A的絕對補集~A定義如下:集合的對稱差集(SymmetricDifference)和絕對補集(AbsoluteComplement).定義6.9~A=E–A={x|xE∧xA}因為E是全集,xE是真命題,所以,~A可以定義為~A={x|xA}.例如:E={a,b,c,d},A={a,b,c},則, ~A=nr7lr4d.定義6.8設A和B為集合,A與B的對稱差集AB定義為:

AB=(A-B)∪(B-A)6.2集合的運算第13頁，共45頁，2023年，2月20日，星期三6.2集合的運算以上定義的并和交運算稱為初級并和初級交.下面考慮推廣的并和交運算,即廣義并和廣義交.第14頁，共45頁，2023年，2月20日，星期三定義6.10設A為集合,A的元素的元素構(gòu)成的集合稱為A的廣義并,記為∪A.符號化表示為:

∪A={x|z(zA∧xz)}根據(jù)廣義并的定義不難得到:若A={A1,A2,…,An},則 ∪A=A1∪A2∪…∪An類似地可以定義集合的廣義交.例6.4設 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集合的運算第15頁，共45頁，2023年，2月20日，星期三例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設A為非空集合,A的所有元素的公共元素所構(gòu)成的集合稱為A的廣義交,記為∩A.符號化表示為 ∩A={x|z(zA

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

=;空集不可進行廣義交,因為∩不是集合;

在集合論中是沒有意義的;若A={A1,A2,…,An},則∩A=A1∩A2∩…∩An.6.2集合的運算第16頁，共45頁，2023年，2月20日，星期三稱廣義并,廣義交,冪集,絕對補運算為一類運算,并,交,相對補和對稱差運算為二類運算.下面的集合公式都是合理的公式:∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)一類運算優(yōu)先于二類運算一類運算之間由右向左順序進行二類運算之間由括號決定先后順序6.2集合的運算第17頁，共45頁，2023年，2月20日，星期三例6.5設A={{a},{a,b}},計算∪∪A,∩∩A,∪∩A,∩∪A.解 ∪A={a,b} ∩A={a} ∪∪A=a∪b ∩∩A=a ∩∪A=a∩b ∪∩A=a

6.2集合的運算第18頁，共45頁，2023年，2月20日，星期三例6.5（續(xù)）設A={{a},{a,b}},計算∩∪A∪(∪∪A-∪∩A)（練習）.解 ∪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集合的運算第19頁，共45頁，2023年，2月20日，星期三課后作業(yè)(1)習題六第5,6,8,9,11,14題（4小題（含）以上的題做奇數(shù)小題；否則全做。）（第96-98頁）.第20頁，共45頁，2023年，2月20日，星期三EEBEB文氏圖(VennDiagrams)EABA∩B=AA∩B=AEABA-BEABA∪BEABA∩BEA~AAABB(A∩B)-CAC6.3有窮集的計數(shù)第21頁，共45頁，2023年，2月20日，星期三有窮集的計數(shù)使用文氏圖可以很方便地解決有窮集的計數(shù)問題。首先根據(jù)已知條件把對應的文氏圖畫出來一般地說，每一條性質(zhì)決定一個集合。有多少條性質(zhì)，就有多少個集合。如果沒有特殊說明，任何兩個集合都畫成相交的。然后將已知集合的元素數(shù)填入表示該集合的區(qū)域內(nèi)通常從n個集合的交集填起，根據(jù)計算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設為x。根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所需要的結(jié)果。

第22頁，共45頁，2023年，2月20日，星期三例6.2對24名人員掌握外語情況的調(diào)查.其統(tǒng)計結(jié)果如下:解令A,B,C和D分別表示會英、法、德、日語的人的集合.設同時會三種語言的有x人,只會英、法或德語一種語言的分別為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會英、日、德、法分別為:13,5,10和9人;同時會英語和日語的有2人;會英、德和法語中任兩種語言的都是4人.已知會日語的人既不懂法語也不懂德語,分別求只會一種語言(英、德、法、日)的人數(shù)和會三種語言的人數(shù).6.3有窮集的計數(shù)第23頁，共45頁，2023年，2月20日，星期三41BAC例6.3求1到1000之間(包含1和1000在內(nèi)),既不能被5和6,也不能被8整除的數(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∩C6.3有窮集的計數(shù)第24頁，共45頁，2023年，2月20日，星期三定理6.2(包含排斥原理)設S為有窮集,P1,P2,…,Pm是m個性質(zhì).S中的任何元素x或者具有性質(zhì)Pi,或者不具有性質(zhì)Pi(i=1..m),兩種情況必居其一.

令Ai表示S中具有性質(zhì)Pi的元素構(gòu)成的子集,則S中不具有性質(zhì)P1,P2,…,Pm的元素數(shù)為:6.3有窮集的計數(shù)第25頁，共45頁，2023年，2月20日，星期三推論S中至少具有一條性質(zhì)的元素數(shù)為根據(jù)包含排斥原理,例6.3中所求的元素數(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=6006.3有窮集的計數(shù)第26頁，共45頁，2023年，2月20日，星期三歐拉函數(shù)歐拉函數(shù)Φ是數(shù)論中的一個重要函數(shù),設n是正整數(shù),Φ(n)表示{0,1,…,n-1}中與n互素的數(shù)的個數(shù).例如Φ(12)=4,因為與12互素的數(shù)有1,5,7,11.這里認為Φ(1)=1.利用包含排斥原理給出歐拉函數(shù)的計算公式.分析

(1)因式分解！(2)包含排斥原理。第27頁，共45頁，2023年，2月20日，星期三歐拉函數(shù)（續(xù)）(1)因式分解給定正整數(shù)n,n的因式分解式為,令則有(2)包含排斥原理首先計算由包含排斥原理得

第28頁，共45頁，2023年，2月20日，星期三冪等率–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集合恒等式第29頁，共45頁，2023年，2月20日，星期三同一率–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集合恒等式第30頁，共45頁，2023年，2月20日，星期三吸收率–

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集合恒等式第31頁，共45頁，2023年，2月20日，星期三6.4集合恒等式例6.6證明:A-(B∪C)=(A-B)∩(A-C) (式6.17)分析（證明思路）（1）定義（集合的基本概念）；（2）命題邏輯中的等值演算?；蛘撸?）根據(jù)前面的定理(集合恒等式)直接推導。第32頁，共45頁，2023年，2月20日，星期三例6.8證明:A-(B∪C)=(A-B)∩(A-C) (式6.17)證對任意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集合恒等式第33頁，共45頁，2023年，2月20日，星期三例6.9證明式6.10,即:A∩E=A.證對任意x,xA∩E

xA∧xE

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

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

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

就是xPxQ6.4集合恒等式第34頁，共45頁，2023年，2月20日，星期三證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假設已知等式6.1-6.14,試證等式6.15:

A∪(A∩B)=A.6.4集合恒等式第35頁，共45頁，2023年，2月20日，星期三6.4集合恒等式（練習）

證明:A-(B∩C)=(A-B)∪(A-C) (式6.18)第36頁，共45頁，2023年，2月20日，星期三還有一些關(guā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集合恒等式第37頁，共45頁，2023年，2月20日，星期三例6.11證明等式6.27,即A-B=A∩~B.證對于任意的x, xA-B xA∧xB xA∧x~B xA∩~B所以,A-B=A∩~B.等式6.27把相對補運算轉(zhuǎn)換成交運算.6.4集合恒等式第38頁，共45頁，2023年，2月20日，星期三例6.12證明:(A-B)∪B=A∪B.證 (A-B)∪B =(A∩~B)∪B =(A∪B)∩(~B∪B) =(A∪B)∩E =A∪B6.4集合恒等式第39頁，共45頁，2023年，2月20日，星期三例6.13證明命題6.28是真命題:

A∪B=B

AB

A∩B=A

A-B=.證

1).證A∪B=BAB對于任意的x,xA