離散數學(集合論)課后總結

1、第三章集合論基礎1、設a=a,a,a,b,a,b,c判斷下面命題的真值。awat(3) ceafaua t(7)a,bca tcca,b,c t(2) -.(a)ca)faca,b,cfa,bwa,b,ct(8)他b口 a,b,cf(10) (cca)->(ae(d)t2、證明空集是唯一的。(性質1：對于任何集合a,都有eya。)證明：假設有兩個空集ei、02，則因為1是空集，則由性質1得1匸2 o因為2是空集，則由性質1得2匸1。所以4>1=0>2 o3、設a= o ,b=p(p(a).問：(這道題要求知道幕集合的概念)a) 是否6gb?是否cb?b) 是否岸b?是否

2、74;gb?c) 是否oeb?是否<dub?解:設 a=0,b=p(p(a) p(a)=0>，在求p(p(a)時，一些同學対集合,難理解，實際上你就將，中的元素分別看 成=a ,=b,于是 e,=a,bb=p(p(a)=p(a,b) =bo, bl , b2 , b3 =b()(), bo1,b1o ,b11=，b, a, a,b 然后再將 a,b 代回即可 b=p(p(a)=p(o, )=, , 以后熟悉后就可以直接寫出。a) w bqbb) cwb 0 cbc) ®wbuba) 、b)、c)中命題均為真。4、證明aqboacb二a成立。證明：a a b=a <=

3、> vx(x e a n b <xe a) ovx(xwaqb txwa)/(xwat xwaqb) <=>vx(x apb vx a)a(xavx a a b) <=>vx(-i(xeaaxeb)vxea)a(xav(xeaaxeb) <=>vx(xavxb)vxea)a (xav(xeaaxeb) <=>vx(ta(ta (xav xb)ovx(xea/ xwb)ovx(xgatxwb)oaub5、(a-b)-c=(a-c)-(b-c) 證明：任取 xe(a-c)-(b-c) oxw(a-c)/xe(b-c)<=>(x

4、 aaxc)a-i(xb axc) o(xwa/xgc)/ (xgbvxwc)<=>(xaaxcaxb)v(xaaxca xgc)<=>x aaxcaxb<=>x a axb axco(x w a/xb)axgcox g a-b a x ecox g (a-b)-c 所以(a-b)-c=(a-c)-(b-c)6、a-(buc)=(a-b)n(a-c)證明：任取xga(buc)<=>xe aax(buc)«xeaa->(xebvxec)oxg a/(xgb/xgc)u>(x w a/xb)/(x 丘 a/xc )<=&g

5、t;xea-baxea-c<=>xe(a-b)n(a-c)所以 a-(b u c)=(a-b) a (a-c)7、(acb)=aub(aub)=adb這兩個公式稱之為底摩根定律。證明：任取xw(aqb)xe (aqb)oxgaqbykxwa/xxwe) o(xgavxgb)oxw avxw b<=>xe aub (arib)=aub8、acb o bya證明： acb <=>vx(x g atx e b)ovx(xbtx a)ovx(x w btx w a)obqa9、a=b 當且僅當 aub=e 且 anb=o證明：aub=eaaab=oo vx(x ea

6、u box ee)a(potop)vx(xeaabexe )(pofop)ovx(x w a u b<->t) avx(xeaa bof)ovx(x eauba-i(xeaab)o vx(x eavxeb)a-.(xeaaxeb)<>vx(x avxb)a(xavxb)ovx(x$atx w b)/(x w btxa)ovx(x e atx gb)a(xe btx e a)u>vx(x c a<>x 丘 b)oa=b關于對稱差a、b是集合，由屬于a而不屬于b,或者屬于b而不屬于a的元索構成的集合,稱之為a與 b 的對稱差，記作 ab。例如 a= 1,2

7、,3 b=2,3,4ab二1,4謂詞定義：ab=(a-b)u(b-a)=xl(xeaaxb)v(xebaxa)a b=(a u b)-(a a b)10、門對可分配 an(bec)=(anb)e(anc)證明：(anb)®(anc)=(a ab)u(an c)-(a ab)n(ap c)= (aa(buc)-(anbnc)=an(b uc)-(b ac)(n對分配)= aa(b c)但是u對不可分配，舉反例：a u (a b)=a u b ,而(a u a)©(a u b)=a (a u b)= (a u b)-aa u (ab)h(a u a)(a u b)般地,有n個有

8、限集合al, a2,. an,貝ij11、某個研究所有170名職工，其中120人會英語，80人會法語，60人會日語，50人會英 語和法語，25人會英語和日語，30人會法語和日語，10人會英語、日語和法語。問有多少 人不會這三種語言？解:令u為全集，e、f、j分別為會英語、法語和口語人的集合。iui=170iei=120 ifi=80 iji=60 ie a fi=50ienj 1=25 ifnj 1=30ieafaj|=10ieufu ji=iei+ifi+iji-ie a fi-ie a ji-if a ji+ie afaji=120+80+60-50-25-30+10=165iu-(euf

9、uj)|=170-165=5 即冇5人不會這三種語言。12、求1到1000 z間不能被5、6、8整除的數的個數。 解.設全集e=xlx是1到1000的整數 iei =1000a5、a6、a8是e的了集并分別表示可被5、6、8整除的數的集合。lx表示小于或 等于x的最人整數。lcm(x,y):表示x,y兩個數的最小公倍數。(least common multiple)| 人 i二=16610001000lcm (5,6,8)120i 力5| 人6)力8 1=81人5皿1二1000 _ _lcm (5,8)一頁100025i aod as 1=1000lcm (6,8)1000ta不能被5、6、8

10、整除的數的集合為(a5ua6ua8)i(a5 u a6u a8)i=iei 一 ia5 u a6u a8i=iei 一 (ia5i+ia6i+ia8i 一 ia5 cl a6i 一 ia5 a a8i 一 ia6 a a8l+ia5na6aa8l)=1000一 (200+166+125-33-25-41+8) = 60013、對24名科技人員掌握外語的情況進行調査結果如下：英、日、德、法四種外語中，每 個人至少會一種；會英、日、德、法語的人數分別是13、5、10、9人；同時會英、日語 的有2人；同時會英、法語的有4人；同時會德、法語的有4人；同時會英、德語的有 4人；會日語的人不會德語，也不會

11、法語；問這24人中，只會一種外語的人各是多少人？同時會英、法、德三種語言的人有多少人？ 解：設全集為u, e,f,g,j分別表示會英、法、德、口語人的集合。iui = 24 ienfi=igafi=iengi=4乂設ieqfggi=x只會英、法、徳、日-種外語的人分別是yl, y2, y3, y4。于是可以畫出文氏圖及方程如f：yl +2(4-x)+x+2=13y2 +2(4-x)+x=9y3 +2(4-x)+x=10y4+2=5yl+ y2+ y3 +y4 +3(4-x)+x+2=24解得：yl =4,y2=2,y3=3,y4=3 x=l14、a,b 是有限集合,p(a)表示 a 的塞集，已

12、知iai=3,ip(b)i=64,ip(aub)i=256,則ibi=(), iaabi=( ),ia-bi=( ),ia bl=( )解:由ip(b)i=64=26,得 ibi=6由ip(aub)i=256=28,得iaubi=8由包含排斥原理得iaubhai+ibi-iaabi得 8 = 3+6ia cl bl ,所以 iaabi=1ia-bi=iai-|aabi=3-1=2ia bi=ia u bi-ia cl bl=8-1=715、設f表示一年級大學生的集合,s表示二年級大學生的集合,m表示數學專業(yè)學生的集 合,c表示計算機專業(yè)學生的集合,d表示聽離散數學課學生的集合,g表示星期六晩上

13、參加音 樂會的學生的集合,h表示星期六晚上很晚才睡覺的學生集合，則將下面各個句子所對應的集 合表達式分別寫在句子后面的括號內：(1) 所有計算機專業(yè)二年級的學生在學離散數學課。(cqs匸d )(2) 這些h只冇這些學離散數學課的學生或者星期六晚上去聽音樂會的學生在星期六晩上很 晚才睡覺。(d ug=h)(3) 星期六晚上的音樂會只有大學-一、二年級的學生參加。(gqfus)除去數學專業(yè)和計算機專業(yè)以外的二年級的學生都去參加星期六晩上的音樂會。(mu c) a seg)16、一個班有50人，第一次考試得a的人數等于第二次考試得a的人數，僅僅在一次考 試中得a的學生總數是40,有4個學生兩次考試都

14、沒有得到a,問有多少學生僅在第一次 考試中取得a?問有多少學生僅在第二次考試中取得a?問有多少學生兩次考試中都取得 a?解.設al、a2分別表示在笫一次和笫二次得a的人的集合。根據題意得：iei = 50, ia1i = ia2i,(ia1i-ia1a a2i) + (ia2i-ia1a a2i) = 40,即 ia1i + ia2i - ia1 a a2i - ia1 a a2 i = 40 , 2ia1i-2ia1qa2i =40,.(1)ia1i -ia1a a2i = ia2i -ia1aa2i = 20 ,(僅一次得 a)又 iei-ia1u a2i = 4, ia1u a2i =

15、50 - 4 = 46即 ia1i + ia2i -iaina2l = 2iall-iain a2i = 46,.(2)(1)得：ia1qa2i = 6。(兩次得a為6人)17、在什么條件下，下面命題為真？a) (a-b)u(a-c) = a解(ab)u(a-c) = (a a b)u (a a c) = a a(b uc)二 a q (b gc)二 a-(b ac)= a所以滿足此式的充耍條件是：aabnc=b) (a-b)u(a-c)=解.(a-b) u (a-c) = a-(b a c)=所以滿足此式的充要條件是：aebpcc) (a-b)a(a-c)=o解.(a-b) a (a-c)

16、= (ah b) q (a q c)二 a q (b p c)= a cl (b u c) = a-(b u c)二所以滿足此式的充要條件是：aobucd) (a-b)©(a-c) = c解.因為當且僅當a = b ,才有ab二所以滿足此式的充要條件是：a-b = a-c18、計算 00(0=000 = 00>,的一 二和,0>-0 = <1>0,0-0 = 019、證明各式彼此等價。c)a u b=e, ayb, ba 證明.aub=e ovx(xgaub>xge)ovx(xwaub) (因 xwe 為 t) (potop)ovx(xwa/xwb)ov

17、x(xga>xwb) ovx(x w atx wb) <=> agb同理 aub=eo .o vx(xeavxeb)ovx(x$btx w a) o/x(xw btx w a) <=> bya所以 a u b=e o aqb o bca.2()證明(acb)uc 二 ac(buc) iff cca.證明：充分性已知cqa(aab)uc = (auc)a(buc)= aa(buc) (v cca auc=a)必耍性 己知(a nb)uc=aa(buc)任取 xec=>xe(aab)uc<=>xean(buc)=>xea 所以cya.21、證明(a-b)-c=(a-c)-b方法l任取xe(a-b)-co xg(a-b)/xgc o(x丘 a/xgb)/xgc u>(xw a/xc)/xgb u> x(a-c)axb o x w (a-c)-b所以(a-b)-c = (a-c)-b方法 2 (a-b)-c = (aa b) g c = (a cl c)