2006-2007-2學期離散數學期末考試（b卷）標準答案
一、單項選擇題：評分標準：對1個給1分
1. (2)
2. (1)
3. (3)
4. (4)
5. (2)
6. (2)
7. (2)
8. (2)
9. (2)
10. (3)
二、多項選擇題：評分標準：完全正確1個給1分，否則不給分
1. （1，2，3，4，5）
2. （2，3，4）
3. （1，2，4）
4. （2，4，5）
5. （1，3，4，5）
三、簡答題：評分標準：答對大意給2分
1、答：設a為集合，把a的全體子集構成的集合叫做a的冪集。
2、答：設r是集合a上的二元關係，對任意的x,y,z∈a，如果∈r且∈r，那麼∈r，則稱關係r是傳遞的，或稱r具有傳遞性。
3、答：連通而不含迴路的無向圖稱為無向樹，簡稱樹。
4、答：設和是兩個格，ψ是l到s的對映。如果對任意x,y∈l，都有
ψ(x∧y) = ψ(x)* ψ(y)，ψ(x∨y) = ψ(x)ψ(y)
則稱ψ為從格到格的格同態對映，簡稱格同態。
四、判斷分析改錯題：評分標準：判斷正確給3分，理由正確給2分。判斷錯誤則不給分。
1、答：不是。
例如：a＝，a上的關係r＝、s＝均反自反，但r s＝不反自反。
2、答：不成立。
例如： ① 個體域為d=；
② g(a)指定為：1，g(b)指定為：0
③ h(a)指定為：0，h(b)指定為：1
則（x）(g(x) h(x))為0，（x）g(x) （x）h(x)為1。故不等。
3、答：對。
假設無向簡單圖g中存在一條邊(u,v)不在任何乙個連通分支中。若u、v在同乙個連通分支p中，則p∪(u,v)是g的子圖且仍然是連通的，這與p是連通分支矛盾；若u、v不在同乙個連通分支中，設u在連通分支p中，v在連通分支q中，則p∪(u,v)∪q是g的子圖且然是連通的，這與p是連通分支矛盾。故無向簡單圖中的每條邊都必須在乙個連通分支中。
4、答：對。
假設a是g中非么元e的冪等元，即a*a = a，且a≠e。因此a*a = a*e，由消去律知a = e，矛盾。
五、計算題（4×8＝32分，每小題8分）
1 解 (x)p(x)(x)q(f(a),x)
=(p(1)∧p(0)) (q(f(a),1)∨(f(a),1)) ――（4分）
=(p(1)∧p(0))(q(f(0),1)∨q(f(0),1)) ――（1分）
=(1∧0)(q(1,1)∨q(1,1)) ――（1分）
=(0∧1)(1∨1) ――（1分）
=01＝1――（1分）
2 證明
(1) 對xa，有3|(x-x)，所以r，即r是自反的。――（1分）
(2) 對x,ya，若r，即3|(x-y)，所以3|(y-x)，所以，r，即r是對稱的1分）
(3) 對x,y,aa，若r且r，有3|(x-y)且3|(y-z)，所以由(x-z)=(x-y)+(y-z)得3|(x-z)，所以，r，即r是傳遞的。
――（2分）
由(1)、(2)、(3)知，r是a上的等價關係。
因為[1]r＝＝[4]r＝[7]r ――（1分）
[2]r=＝[5]r=[8]r1分）
[3]r==[6]r=[9]r1分）
所以商集a/r＝=，，} ――（1分）
3 解右圖的鄰接矩陣為：
2分)則
2分)――(2分)
從而，1分)
即右圖中長度為3的通路(含迴路)總數為48，其中10條為迴路。――(1分)
4 解 有麼元，可逆元，但沒有零元1分)
因為存在-2∈z，使得對任意a∈z，有
a*(-2)=a+(-2)+2=a， 2*a=(-2)+a+2=a.
故－2是的么元2分)
不存在x∈z，使得對任意a∈z，有
a*x=x*a=x.
故無零元2分)
對任意a∈z，存在4-a∈z，使得
a*(-4-a)=a+(-4-a)+2=-2， (-4-a)*a=-4-a+a+2=-2.
故a的逆元是-4-a
由a的任意性知，z中每個元素都有逆元3分)
六、證明題（共25分,第1題9分，第2，3題各8分）
1、解：設q(x)：x是有理數；r(x)：x是實數；n(x)：x是無理數；c(x)：x是虛數，則上述句子可符號為：
(x) (q(x)→r(x))，(x) (n(x)→r(x))，(x) (c(x)→┐r(x))
(x) (c(x)→┐q(x)∧┐n(x3分)
① (x) (q(x)→r(xp
q(x)→r(xus1分)
x) (n(x)→r(xp
n(x)→r(xus1分)
x) (c(x)→┐r(xp
c(x)→┐r(xus1分)
r(x)→┐c(xt，⑥，e0.5分)
q(x)→┐c(xt，②，⑦，i ――(0.5分)
n(x)→┐c(xt，④，⑦，i ――(0.5分)
q(x)→┐c(x))∧(q(x)→┐c(x)) t，⑧，⑨，e ――(0.5分)
11 (c(x)→┐q(x)∧┐n(xt，⑩，e0.5分)
12 (x) (c(x)→┐q(x)∧┐n(x)) ug，110.5分)
2、證明
（1）對任意cc, 由fg是滿射，所以存在aa，使得fg(a)=c, 即g(f(a))=c。
――(2分)
所以存在b=f(a) b，使得g(b)=c，由c的任意性，所以g是滿射。
――(2分)
（2）對任意a1,a2c (a1≠a2), 由fg是單射，有fg(a1)≠fg(a2),
即g(f(a1))≠g(f(a23分)
因g是函式，所以，f(a1)≠f(a2)。 所以f是單射1分)
3、證明設是有界分配格，並設a是所有有補元構成的集合。
――(1分)
由於0和1有補元，所以0, 1∈a，於是a非空1分)
又對任意的a, b∈a，設a, b的補元分別是和，因為
(a*b)*( )=(a*b*) (a*b*)=((a*)*b) (a*(b*))
=(0*b) (a*0)=0 0=01.5分)
(a*b) ()=(a)* (b)=((a))*((b))
=(1)*(1)=1*1=11.5分)
這表明a*b有補元。
又因為(ab)*( *)=(a**) (b**)=((a*)*) (*(b*))
=(0*) (*0)=0 0=01.5分)
(ab) (*)=( ab )* (ab )=((a)b)*(a(b))
=(1b)*(a1)=1*1=11.5分)
這表明ab有補元*。
綜上所述，是的子格。
離散數學期末複習指導
山東廣播電視大學計算機與通訊學院 2008年6月 離散數學是 電大計算機應用專業資訊管理方向開設的必修統設課。該課程使用新的教學大綱，在原有離散數學課程的基礎上削減了教學內容 主要是群與環 格與布林代數這兩章及圖論的後三節內容 使所學的知識達到必需 夠用，更加適合大學專科層次的教育。目前該課程沒有新...
離散數學期末複習指導
2 3 4 5 6 1，3，4 3，4，1 7 8 如果ab b，則a e。解析 此題涉及到集合中子集的概念，集合的包含關係，空集與集合的關係。解題時要注意區分兩個集合之間的關係以及集合中元素與集合之間的關係的不同。集合之間的關係分為包含關係 子集 真子集 相等關係 冪集等，判斷時要準確理解這些概念...
離散數學期末複習指導
瀏水浮芸qq632069015 山東廣播電視大學計算機與通訊學院 2008年6月 離散數學是 電大計算機應用專業資訊管理方向開設的必修統設課。該課程使用新的教學大綱，在原有離散數學課程的基礎上削減了教學內容 主要是群與環 格與布林代數這兩章及圖論的後三節內容 使所學的知識達到必需 夠用，更加適合大學...