《離散數(shù)學(xué) 作業(yè) 3~4 答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué) 作業(yè) 3~4 答案（3頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、『離散數(shù)學(xué)』課程
作業(yè)3：
P64：3
某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人中有4人會(huì)打排球。求不會(huì)打球的人數(shù)。
解：直接使用容斥原理。我們做如下設(shè)定：
A：會(huì)打籃球的學(xué)生； B：會(huì)打排球的學(xué)生； C：會(huì)打網(wǎng)球的學(xué)生；
根據(jù)題意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|B∩C|=4，|A∩B∩C|=2
由容斥原理:
|A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|=14+12+6
2、-6-5-4+2=19
不會(huì)打球的人數(shù)=|E|-|A∪B∪C|=25-19=6
——————————————————————————————————————
但相當(dāng)一部分同學(xué)沒(méi)有直接使用容斥原理，
而是畫了文氏圖。
使用文氏圖的方法，會(huì)發(fā)現(xiàn)此題存在問(wèn)題：
= -1，
表示只會(huì)打網(wǎng)球的同學(xué)是-1人，
此種情況與實(shí)際不符。
這可能是作者的疏忽，該教材第一版中，
“已知6個(gè)會(huì)打網(wǎng)球的人中有4人會(huì)打排球?！?
一句是寫作
“已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球?！?
則用容斥原理或文氏圖，都可以得到5的結(jié)果。
A：會(huì)打籃球的學(xué)生； B：會(huì)打排球的學(xué)生； C：會(huì)打網(wǎng)球的學(xué)生；
3、
根據(jù)題意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|A∩B∩C|=2
因?yàn)椤皶?huì)打網(wǎng)球的人都會(huì)打籃球或排球?！?
所以C =（A∩C）∪（B∩C）
由容斥原理:
|C|=|（A∩C）∪（B∩C）|
= |（A∩C）|+|（B∩C）|-|（A∩C）∩（B∩C）|
可知|（B∩C）|= |C|-|（A∩C）|+|（A∩C）∩（B∩C）|
= 6-5+2=3
|A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|
=14+12+6-6-5-3+2=20
不會(huì)打球的人數(shù)=|E|-|A∪B∪C|=2
4、5-20=5
作業(yè)4：
P70：2
當(dāng)A=φ時(shí)， 若AB?AC，B?C不一定成立；
當(dāng)A≠φ時(shí)，若AB?AC，則B?C一定成立，反證如下：
若B?C不成立，則存在y∈B∧y?C；又因?yàn)棣铡貯，所以存在x∈A；可知序偶∈AB∧ ? AC ，與AB?AC矛盾。
P76：5
自反閉包r(R)= R∪{}
對(duì)稱閉包s(R)= R∪{,}
傳遞閉包t(R)= R∪{}
P80：2
A中各元素關(guān)于R的等價(jià)類：
[a]=[b]={a,b}
[c]=[d]={c,d}
相應(yīng)的劃分{{a,b}，{
5、c,d}}
當(dāng)堂測(cè)試：
1、判斷下程序段基本語(yǔ)句執(zhí)行次數(shù)的O(f(n))。
int n=10,x=n,y=0;
while(x>=(y+1)*(y+1))
y++;
解：
循環(huán)次數(shù)
1
2
3
…
k
y的值
1
2
3
…
k
第(k+1)此循環(huán)沒(méi)有執(zhí)行，說(shuō)明循環(huán)條件不滿足。
取臨界值，我們認(rèn)為x=n≈(y+1)*(y+1)=(k+1)2
k≈n1/2-1 時(shí)間復(fù)雜度T(n)= O(n1/2)
2、利用容斥原理作答：某班有50 位同學(xué)參加期末考試，結(jié)果英語(yǔ)不及格的有15 人，數(shù)學(xué)不及格的有19 人，英語(yǔ)和數(shù)學(xué)都及格的有21 人，求英
6、語(yǔ)和數(shù)學(xué)都不及格的有多少人？
解：A：英語(yǔ)及格的學(xué)生 B：數(shù)學(xué)及格的學(xué)生
|E|=50 |A|=50-15=35 |B|=50-19=31 |A∩B|=21
根據(jù)容斥原理：|A∪B|=|A|+|B|-|A∩B|=35+31-21=45
所求為=|E|-|A∪B|=50-45=5
3、 R和S都是A={1, 2, 3, 4}上的二元關(guān)系，R={<1, 1>, <1, 2>, <1, 3>, <2, 3>, <2, 4>, <4, 3>, <4, 4>}，S={<1, 2>, <1, 3>, <2, 3>, <2, 4>, <3, 1>, <4, 3>}，試用矩陣相乘的方法求
7、RS。
解：本題是拷給大家的PPT課件原題。
RS={<1,1>，<1,2>，<1,3>，<1,4>，<2,1>，<2,3>，<4,1>，<4,3>}
4、 設(shè)Ａ={a,b,c}，R={,,}，求r(R)，s(R)，t(R)。
5、判斷給出的關(guān)系是否是{1,2,3,4,5}上的等價(jià)關(guān)系。如果是，列出等價(jià)類。
（1）{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,3>,<3,1>,<3,4>,<4,3>}
不是等價(jià)關(guān)系，不滿足傳遞性 有<1,3>,<3,4>卻無(wú)<1,4>
（2）{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,5>,<5,1>,<3,5>,<5,3>,<1,3>,<3,1>}
是等價(jià)關(guān)系，等價(jià)類為：
[1]=[3]=[5]={1,3,5}
[2]={2} [4]={4}
對(duì)應(yīng)的劃分{{1,3,5}，{2}，{4}}
離散數(shù)學(xué) 作業(yè) 3~4 答案
