1、20042005 學年第1 學期試卷離散數(shù)學課程課程類別：必、限、任 閉卷、開卷(范圍)：一、判斷題：（10 分，在括號內(nèi)劃“”或“”）（）1“如果從西邊出來，則 2+2=4”，此命題值為假。）2(1,3,3,3)可以成為無向簡單圖的度數(shù)序列。）3有一個函數(shù) f：XY，若 f 具有反函數(shù)，則 f 一定是單射。）4（PQ）（PQ）是永真式。（）5在某集合上二元運算中，若某元素存在左右（，則該元素唯一。（）6命題公式的主析取范式為 0，則其主合取范式為 1。（）7有向圖的關(guān)聯(lián)矩陣中所有元）8初級回路一定是簡單回路。和為該圖度之和 。（）9若關(guān)系 R 具有自反性，則一定不具有反自反性。）10 x(A

2、(x) yH(x,y)在具體的解釋中其值是確定的。（二、填空（共 30 分）1 設(shè)A=1，2，P(A)表示 A 的冪集，,則 P(A) A =。在一階邏輯中符號化命題:“所有的人都是要死的”（只能用存在量詞）：。P(x) y R(x,y)的前束范式是：。n 階有向完全圖中所有頂點的度數(shù)之和為5.已知從 A 到 A/R 的函數(shù) g：AA/R 為自然g(1)=。6. 設(shè)函數(shù) f(x)=2x + 1,g(x)= x2-2,則 f o g =。7. Klein 四元群的運算表如下，其有個子群。，A=1,2,3 ，R=EA,則、。，承的承諾嚴擔：重由我此將引嚴起格的遵一守切考場紀律，并知道專業(yè)班級學號

3、學生簽名：題號一二三四五六七十總分分數(shù)評卷人e ea ab bc ce a b ca b ce c bc e ab a e8.R，+為代數(shù)系統(tǒng)，給定 bZ，令函數(shù) f：RR，且 f(x)bx，當 b滿足 時， f 是R，+的自同構(gòu)。9若|P(AB)|=256，|P(A)|=64，| B |=3，則|AB|=。10下圖為無向圖，并且是平面圖，畫出它的一種平面嵌入。三、（6 分）設(shè) A、B、C 為任意集合，證明：(ABC)(AB) (A(BC)A) = BA四、（8 分）求（pq） r 的主合取范式、主析取范式以及成假賦值。五、（8 分）設(shè)Z 為整數(shù),在Z 上定義二元運算，對任意的x,yZ，定義：

4、 xy=x+y+10證明： Z, 是群。六、（8 分）在一階邏輯自然推理系統(tǒng)中，構(gòu)造下面推理的證明。集合。域是人的“每個喜歡步行的人都不喜歡坐汽車，每個人或者喜歡坐汽車或者喜歡騎自行車，有的人不喜歡騎自行車。因而有的人不喜歡步行。”七、（10 分）設(shè)集合 A= 1,2,3,4上的二元關(guān)系 R1 與 R2 定義如下：R1=,，R2=,，1)2)3)寫出 R1 的關(guān)系矩陣，并判斷 R1 具有哪些性質(zhì)？求出 R1R2畫出 t(R2)的關(guān)系圖。V4V3V5V2V6V1八、（10 分）已知 A 和 A 上的偏序關(guān)系 R，設(shè) A = a,b,c,d,e,f ，R = ,IA 。1)2)3)畫出此偏序集的哈斯圖。找出最大元與最小元。A, 是否為分配格？是否為代數(shù)？說明理由。九、（10 分）若D 是具有結(jié)點 v1,v2,v3,v4 的有向圖，它的鄰接矩陣表示如下：10001)2)3)4)2000