離散數(shù)學考試大綱-資料下載頁
2024-10-25 02:13本頁面
【正文】 。（A∩B）∨x206。 A∩C 219。 x206。（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）四、（10分）已知R和S是非空集合A上的等價關系，試證：1）R∩S是A上的等價關系；2）對a∈A，[a]R∩S=[a]R∩[a]S。解：x∈A，因為R和S是自反關系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。x、y∈A，若∈R∩S，則∈R、∈S，因為R和S是對稱關系，所以因∈R、∈S，因而∈R∩S，故R∩S是對稱的。x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因為R和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的?？傊甊∩S是等價關系。2）因為x∈[a]R∩S219?！蔙∩S219?！蔙∧∈S219。 x∈[a]R∧x∈[a]S219。 x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。五、(10分)設A＝{a，b，c，d}，R是A上的二元關系，且R＝{，，}，求r(R)、s(R)和t(R)。解 r(R)＝R∪IA＝{，，，，} s(R)＝R∪R＝{，，，} R＝{，，} R＝{，，} R＝{，，}＝Rt(R)＝UR＝{，，，，} i=1165。i42321六、(15分)設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：AC174。BD且∈AC，h()＝。證明h是雙射。證明：1）先證h是滿射?！蔅D，則b∈B，d∈D，因為f是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈AC，使得h()＝＝，所以h是滿射。2）再證h是單射。、∈AC，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因為f是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。綜合1）和2），h是雙射。七、(12分)設是群，H是G的非空子集，證明是的子群的充要條件是若a，b206。H，則有a*b206。H。證明：222。 a,b∈H有b∈H，所以a*b∈H。220。a∈H，則e=a*a∈H1111a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H205。G且H≠F,∴*在H上滿足結合律 ∴是的子群。八、（10分）設G=是簡單的無向平面圖，證明G至少有一個結點的度數(shù)小于等于5。解：設G的每個結點的度數(shù)都大于等于6，則2|E|=Sd(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖11111的|E|≤3|V|6矛盾，所以G至少有一個結點的度數(shù)小于等于5。=,A={a,b,c},*的運算表為：(寫過程，7分)（1）G是否為阿貝爾群？（2）找出G的單位元；（3）找出G的冪等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿貝爾群（2）因為a*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a（3）因為a*a=a 所以G的冪等元是a（4）因為b*c=c*b=a，所以b的逆元是c且c的逆元是b十、(10分)求葉的權分別為114的最優(yōu)二叉樹及其權。解：最優(yōu)二叉樹為權＝148 5
環(huán)評公示相關推薦
鄂ICP備17016276號-1