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