離散數(shù)學(xué)第6章-集合代數(shù)課件

主要內(nèi)容集合的基本概念屬于、包含冪集、空集文氏圖等集合的基本運(yùn)算并、交、補(bǔ)、差等集合恒等式集合運(yùn)算的算律、恒等式的證明方法第二部分集合論第六章集合代數(shù)1主要內(nèi)容第二部分集合論第六章集合代數(shù)16.1集合的基本概念1.集合定義集合沒有精確的數(shù)學(xué)定義理解：由離散個體構(gòu)成的整體稱為集合，稱這些個體為集合的元素常見的數(shù)集：N,Z,Q,R,C等分別表示自然數(shù)、整數(shù)、有理數(shù)、實數(shù)、復(fù)數(shù)集合2.集合表示法

枚舉法----通過列出全體元素來表示集合

謂詞表示法----通過謂詞概括集合元素的性質(zhì)實例：枚舉法自然數(shù)集合N={0,1,2,3,…}謂詞法S={x|x是實數(shù)，x21=0}26.1集合的基本概念1.集合定義2.集合表示法2元素與集合1.集合的元素具有的性質(zhì)無序性：元素列出的順序無關(guān)相異性：集合的每個元素只計數(shù)一次確定性：對任何元素和集合都能確定這個元素是否為該集合的元素任意性：集合的元素也可以是集合2．元素與集合的關(guān)系隸屬關(guān)系：或者3．集合的樹型層次結(jié)構(gòu)dA,aA3元素與集合1.集合的元素具有的性質(zhì)dA,aA集合與集合集合與集合之間的關(guān)系：,=,?,,,定義6.1A

B

x(xAxB)定義6.2A=B

A

B

B

A定義6.3A

B

A

B

A

B

A

?

B

x(xAxB)思考：和的定義注意和是不同層次的問題4集合與集合集合與集合之間的關(guān)系：,=,?,,,空集、全集和冪集1．定義6.4

空集：不含有任何元素的集合實例：{x|xRx2+1=0}定理6.1空集是任何集合的子集。證對于任意集合A，

A

x(xxA)T(恒真命題)

推論

是惟一的3.定義6.6

全集E：包含了所有集合的集合全集具有相對性：與問題有關(guān)，不存在絕對的全集2.定義6.5

冪集：P(A)={x|xA}實例：P()={},P({})={,{}}計數(shù)：如果|A|=n，則|P(A)|=2n.5空集、全集和冪集1．定義6.4空集：不含有任何元素6.2集合的運(yùn)算初級運(yùn)算集合的基本運(yùn)算有定義6.7

并

AB={x|xA

xB}

交

AB={x|xA

xB}

相對補(bǔ)

AB={x|xA

xB}定義6.8

對稱差

AB=(AB)(BA)定義6.9

絕對補(bǔ)

A=EA

66.2集合的運(yùn)算初級運(yùn)算6文氏圖集合運(yùn)算的表示ABABABABABABABA–BAB~A7文氏圖集合運(yùn)算的表示ABABABABABABABA–BA幾點(diǎn)說明并和交運(yùn)算可以推廣到有窮個集合上，即A1A2…An

={x|xA1xA2…xAn}A1A2…An

={x|xA1xA2…xAn}A

B

AB=

AB=

AB=A8幾點(diǎn)說明并和交運(yùn)算可以推廣到有窮個集合上，即8廣義運(yùn)算1.

集合的廣義并與廣義交

定義6.10廣義并A={x|z(zA

xz)}廣義交

A={x|z(zAxz)}實例{{1},{1,2},{1,2,3}}={1,2,3}

{{1},{1,2},{1,2,3}}={1}

{{a}}={a}，{{a}}={a}

{a}=a，{a}=a9廣義運(yùn)算1.集合的廣義并與廣義交9關(guān)于廣義運(yùn)算的說明2.廣義運(yùn)算的性質(zhì)(1)=，無意義(2)單元集{x}的廣義并和廣義交都等于x

(3)廣義運(yùn)算減少集合的層次（括弧減少一層）(4)廣義運(yùn)算的計算：一般情況下可以轉(zhuǎn)變成初級運(yùn)算{A1,A2,…,An}=A1A2…An{A1,A2,…,An}=A1A2…An

3.引入廣義運(yùn)算的意義可以表示無數(shù)個集合的并、交運(yùn)算，例如{{x}|xR}=R這里的R代表實數(shù)集合.10關(guān)于廣義運(yùn)算的說明2.廣義運(yùn)算的性質(zhì)10運(yùn)算的優(yōu)先權(quán)規(guī)定1類運(yùn)算：初級運(yùn)算,,,，優(yōu)先順序由括號確定2類運(yùn)算：廣義運(yùn)算和運(yùn)算，運(yùn)算由右向左進(jìn)行混合運(yùn)算：2類運(yùn)算優(yōu)先于1類運(yùn)算例1

A={{a},{a,b}}，計算A(AA).解：A(AA)={a,b}({a,b}{a})=(ab)((ab)a)=(ab)(ba)=b11運(yùn)算的優(yōu)先權(quán)規(guī)定1類運(yùn)算：初級運(yùn)算,,,，例有窮集合元素的計數(shù)1.文氏圖法2.包含排斥原理定理6.2設(shè)集合S上定義了n條性質(zhì)，其中具有第i條性質(zhì)的元素構(gòu)成子集Ai,那么集合中不具有任何性質(zhì)的元素數(shù)為

推論

S中至少具有一條性質(zhì)的元素數(shù)為12有窮集合元素的計數(shù)1.文氏圖法推論S中至少具有一條性實例例2求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個？解方法一：文氏圖定義以下集合：

S={x|xZ1x1000}A={x|xSx可被5整除}B={x|xSx可被6整除}C={x|xSx可被8整除}

畫出文氏圖，然后填入相應(yīng)的數(shù)字，解得N=1000－(200+100+33+67)=60013實例例2求1到1000之間（包含1和1000在內(nèi)）既不實例方法二|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/33=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8

=1000(200+166+125)+(33+25+41)8=60014實例方法二146.3集合恒等式集合算律1．只涉及一個運(yùn)算的算律：交換律、結(jié)合律、冪等律交換AB=BAAB=BAAB=BA結(jié)合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)冪等AA=AAA=A156.3集合恒等式集合算律交換AB=BAAB=集合算律2．涉及兩個不同運(yùn)算的算律：分配律、吸收律

與與分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A16集合算律2．涉及兩個不同運(yùn)算的算律：與與分配A(集合算律3．涉及補(bǔ)運(yùn)算的算律：DM律，雙重否定律

D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC雙重否定A=A17集合算律3．涉及補(bǔ)運(yùn)算的算律：D.M律A(BC)=(集合算律4．涉及全集和空集的算律：

補(bǔ)元律、零律、同一律、否定律E補(bǔ)元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=18集合算律4．涉及全集和空集的算律：E補(bǔ)元律AA=A集合證明題證明方法：命題演算法、等式置換法命題演算證明法的書寫規(guī)范(以下的X和Y代表集合公式)(1)證XY任取x，xX…

xY

(2)證X=Y方法一分別證明XY和YX方法二任取x，xX…

xY注意：在使用方法二的格式時，必須保證每步推理都是充分必要的19集合證明題證明方法：命題演算法、等式置換法19集合等式的證明方法一：命題演算法例3證明A(AB)=A（吸收律）證任取x,xA(AB)

xAxAB

xA(xAxB)

xA

因此得A(AB)=A.例4證明AB=AB證任取x,x

AB

xAxB

xAxB

xAB

因此得AB=AB20集合等式的證明方法一：命題演算法例4證明AB=等式代入法方法二：等式置換法例5假設(shè)交換律、分配律、同一律、零律已經(jīng)成立，證明吸收律.證A(AB)=(AE)(AB)（同一律）=A(EB)（分配律）=A(BE)（交換律）=AE（零律）

=A（同一律）21等式代入法方法二：等式置換法21包含等價條件的證明例6證明AB

AB=B

AB=A

AB=

①②③④證明思路：確定問題中含有的命題：本題含有命題①,②,③,④確定命題間的關(guān)系（哪些命題是已知條件、哪些命題是要證明的結(jié)論）：本題中每個命題都可以作為已知條件，每個命題都是要證明的結(jié)論確定證明順序：①②，②③，③④，④①按照順序依次完成每個證明（證明集合相等或者包含）22包含等價條件的證明例6證明ABAB=B證明證明AB

AB=B

AB=A

AB=

①②③④證①②顯然BAB，下面證明AB=B.任取x，

xAB

xAxB

xBxB

xB因此有ABB.綜合上述②得證.②③A=A(AB)

A=AB(由②知AB=B，將AB用B代入)23證明證明ABAB=BAB=AAB=③④假設(shè)AB,即xAB，那么知道xA且xB.而xB

xAB

從而與AB=A矛盾.④①假設(shè)AB不成立，那么x(xAxB)

xAB

AB與條件④矛盾.證明24③④證明24第六章習(xí)題課主要內(nèi)容集合的兩種表示法集合與元素之間的隸屬關(guān)系、集合之間的包含關(guān)系的區(qū)別與聯(lián)系特殊集合：空集、全集、冪集文氏圖及有窮集合的計數(shù)集合的,,,,等運(yùn)算以及廣義,運(yùn)算集合運(yùn)算的算律及其應(yīng)用25第六章習(xí)題課主要內(nèi)容25基本要求熟練掌握集合的兩種表示法能夠判別元素是否屬于給定的集合能夠判別兩個集合之間是否存在包含、相等、真包含等關(guān)系熟練掌握集合的基本運(yùn)算（普通運(yùn)算和廣義運(yùn)算）掌握證明集合等式或者包含關(guān)系的基本方法26基本要求熟練掌握集合的兩種表示法26練習(xí)11．判斷下列命題是否為真(1)(2)(3){}(4){}(5){a,b}{a,b,c,{a,b,c}}(6){a,b}{a,b,c,{a,b}}(7){a,b}{a,b,{{a,b}}}(8){a,b}{a,b,{{a,b}}}解(1)、(3)、(4)、(5)、(6)、(7)為真，其余為假.27練習(xí)11．判斷下列命題是否為真解(1)、(3)、(4方法分析(1)判斷元素a與集合A的隸屬關(guān)系是否成立基本方法：把a(bǔ)作為整體檢查它在A中是否出現(xiàn)，注意這里的a可能是集合表達(dá)式.(2)判斷AB的四種方法若A,B是用枚舉方式定義的，依次檢查A的每個元素是否在B中出現(xiàn).若A,B是謂詞法定義的，且A,B中元素性質(zhì)分別為P和Q,那么“若P則Q”意味AB，“P當(dāng)且僅當(dāng)Q”意味Ａ=Ｂ．通過集合運(yùn)算判斷AB，即AB=B,AB=A,AB=三個等式中有一個為真.通過文氏圖判斷集合的包含（注意這里是判斷，而不是證明28方法分析(1)判斷元素a與集合A的隸屬關(guān)系是否成立基本方法練習(xí)22．設(shè)S1={1,2,…,8,9}，S2={2,4,6,8}

S3={1,3,5,7,9}S4={3,4,5}

S5={3,5}確定在以下條件下X是否與S1,…,S5中某個集合相等？如果是，又與哪個集合相等？（1）若XS5=（2）若XS4但XS2=（3）若XS1且X

?S3（4）若XS3=（5）若XS3且X?S129練習(xí)22．設(shè)29解答解(1)和S5不交的子集不含有3和5，因此X=S2.(2)S4的子集只能是S4和S5.由于與S2不交，不能含有偶數(shù)，因此X=S5.(3)S1,S2,S3,S4和S5都是S1的子集，不包含在S3的子集含有偶數(shù)，因此X=S1,S2或S4.(4)XS3=意味著X是S3的子集，因此X=S3或S5.(5)由于S3是S1的子集，因此這樣的X不存在.30解答解30練習(xí)33.判斷以下命題的真假，并說明理由.（1）AB=A

B=（2）A(BC)=(AB)(AC)（3）AA=A（4）如果AB=B，則A=E.（5）A={x}x，則xA且x

A.31練習(xí)33.判斷以下命題的真假，并說明理由.31解題思路先將等式化簡或恒等變形.查找集合運(yùn)算的相關(guān)的算律，如果與算律相符，結(jié)果為真.注意以下兩個重要的充要條件AB=A

AB=

AB=

AB

AB=BAB=A如果與條件相符，則命題為真.如果不符合算律，也不符合上述條件，可以用文氏圖表示集合，看看命題是否成立.如果成立，再給出證明.試著舉出反例，證明命題為假.32解題思路先將等式化簡或恒等變形.32解答解(1)B=是AB=A的充分條件，但不是必要條件.當(dāng)B不空但是與A不交時也有AB=A.(2)這是DM律，命題為真.(3)不符合算律，反例如下：

A={1}，AA=，但是A.(4)命題不為真.AB=B的充分必要條件是BA，不是A=E.(5)命題為真，因為x既是A的元素，也是A的子集33解答解33練習(xí)44．證明AB=AC

AB=AC

B=C解題思路分析命題：含有3個命題：

AB=AC,AB=AC,

B=C①②③證明要求前提：命題①和②結(jié)論：命題③證明方法：恒等式代入反證法利用已知等式通過運(yùn)算得到新的等式34練習(xí)44．證明AB=ACAB=AC解答