浙02324#離散數學試題第3頁共3頁全國2004年7月高等教育自學考試離散數學試題課程代碼：02324一、單項選擇題(在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內。每小題1分，共14分)1.下列語句不是命題的是()。A.黃金是非金屬。B.要是他不上場，我們就不會輸。C.他跑100米只用了10秒鐘，你說他是不是運動健將呢?D.他跑100米只用了10秒鐘，他是一個真正的運動健將。2.關于命題變元P和Q的大項M01表示()。A.┐P∧Q B.┐P∨QC.P∨┐Q D.P∧┐Q3.公式(x)(y)(P(x,z)→Q(y))S(x,y)中的(x)的轄域是()。A.(y)(P(x,z)→Q(y)) B.P(x,z)→Q(y)C.P(x,z) D.S(x,z)4.下列等價式不成立的是()。A.┐(x)A(x)(x)┐A(x)B.┐(x)A(x)(x)┐A(x)C.(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D.(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)5.公式(x)(y)(P(x,y)∧Q(z))→R(x)中的x()。A.只是約束變元B.只是自由變元C.既是約束變元又是自由變元D.既非約束變元又非自由變元6.設A={a,{a}}，則下列各式正確的是()。A.{a}∈p(A)(A的冪集) B.{a}p(A)C.{{a}}p(A) D.{a,{a}}p(A)7.集合的以下運算律不成立的是()。A.A∩B=B∩A B.A∪B=B∪AC.AB=BA D.A-B=B-A8.設N是自然數集，R是實數集，函數f：Ｎ→R，f(n)=lgn是()。A.入射 B.滿射C.雙射 D.非以上三種的一般函數9.設實數集R上的二元運算o為：xoy=x+y-2xy,則o不滿足()。A.交換律 B.結合律C.有冪等元 D.有零元10.若(A，*)是一個代數系統，且滿足結合律，則(A，*)必為()。A.半群 B.獨異點C.群 D.可結合代數11.設S是自然數集，則下列運算中不滿足交換律的是()。A.a*b=|a-b| B.a*b=abC.a*b=max{a,b} D.a*b=min{a,b}12.設圖G′=<V′，E′>是圖的生成子圖，則必須()。A.V′=V B.V′≠V但E′=EC.E′=E D.E′≠E且V′≠V13.設有向圖G有5個結點，4條邊，且有一條有向路經過每個結點一次，則圖G滿足的最大連通性是()。A.不連通 B.弱連通C.單側連通 D.強連通14.一個連通圖G具有以下何種條件時，能一筆畫出：即從某結點出發，經過圖中每邊僅一次回到該結點。()。A.G沒有奇數度結點 B.G有1個奇數度結點C.G有2個奇數度結點 D.G沒有或有2個奇數度結點二、填空題(每小題2分，共30分)1.設P：a2+b2=a2,Q:b=0,則PQ意思是說______.2.合式公式┐(Q→P)∧P是永______式.3.合式公式(PQ)∧(QR)與PR的關系是______.(等價或蘊含選一)4.命題“所有的貓都是動物”的謂詞表達式為__________.5.公式(x)A(x)→B(y)的前束范式為______.6.設個體域為D={-2,3,6},F(x):x3,G(x):x>5.則在此解釋下公式(x)(F(x)∧G(x))的真值為______.7.設R是有限集A中的關系，若其關系矩陣MR的主對角線上的元素全為0，則R至少是______關系.8.設A={a,b,c}中的關系R={<a,b>,<b,c>}，則R的對稱閉包為S(R)=______.9.設X={1,2,3},Y={a,b}，則從X到Y的不同的函數共有______個.10.設A={0,1,2,3}，A中的序關系“”定義為：aba整除b，則a的最小元是，最大元是______.11.只有兩個元素的群有且只有______個子群.12.一個格稱為布爾代數，如果它是______格和______格.13.設圖G的鄰接矩陣為M=，則G的可達性矩陣為______.14.設一個平面圖有v個結點，e條邊，r個面，則它們的數量關系是______.15.一個無向樹中有6條邊，則它有______個結點.三、計算題(每小題6分，共24分)1.求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式和主合取范式.2.設集合A={a,b,c},A中的關系R={<a,a>,<a,c>,<b,c>,<c,c>}.利用矩陣方法求R的傳遞閉包t(R).3.設(S，*)是代數系統，其中S={a,b,c}，*的運算表為*abcaabcbbaaccaa討論(S，*)是否構成獨異點，并驗證你的結論.4.已知一算式的根樹(如圖)，試分別寫出按中序行遍法、前序行遍法和后序行遍法的算式.四、證明題(每小題8分，共32分)1.利用CP規則證明A→(B→C)，(C∧D)→E,┐D∨E→H├