離散考試原題青島理工大學(xué)

1、.教師試做時(shí)間70出題教師張楠取題時(shí)間審核教研室主任出題單位計(jì)算機(jī)使用班級計(jì)071075考試日期2008.12.26院（部）主任考試成績期望值70印刷份數(shù)規(guī)定完成時(shí)間110交教務(wù)科印刷日期 學(xué)號： 姓名： 班級： 。密。封。線。計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè) 2 年級 計(jì)算071075 班 20082009學(xué)年第 1 學(xué)期 離散數(shù)學(xué) 課試卷 試卷類型： A 卷題號一二三四五六七八九十總成績得分閱卷人 一、單項(xiàng)選擇題(每小題2分，共20分，答案寫于后面答題紙中。)1. 命題公式（pq）q為 ( )(A) 矛盾式 (B) 可滿足式 (C) 重言式 (D) 合取范式2. 設(shè)C(x): x是國家級運(yùn)動(dòng)員，G(

2、x): x是健壯的，則命題“沒有一個(gè)國家級運(yùn)動(dòng)員不是健壯的”可符號化為 ( ) 3.設(shè)集合A=1,2,3, 4,5, 6,7,8，則下式為真的是( )(A) 1A (B) 1,2, 3A(C) 4,5A (D) A4. 設(shè)A1,2,B=a,b,c,C=c,d, 則A(BC)= ( )(A) , (B) , (C) , (D) ,5.在布爾代數(shù)L中，表達(dá)式(ab)(abc) (bc)的等價(jià)式是（ ）（A）b(ac)（B）(ac) (ab)（C）(ab) (abc) (bc)（D）(bc) (ac)6.設(shè)i是虛數(shù)，是復(fù)數(shù)乘法運(yùn)算，則G=是群，下列是G的子群是（ ）（A） （B） （C） （D） 7

3、.設(shè)Z為整數(shù)集，A為集合，A的冪集為P（A），、/ 為數(shù)的加、減、除運(yùn)算，為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有（ ）（A） （B） （C） （D）。8.下列各代數(shù)系統(tǒng)不含有零元的是（ ）（A）,Q是全體有理數(shù)集，*是數(shù)的乘法運(yùn)算（B）, Mn(R)是全體n階實(shí)矩陣集合，*是矩陣乘法運(yùn)算（C）, Z是整數(shù)集，*定義為x*y=xy,x,yZ（D）, Z是整數(shù)集，+是數(shù)的加法運(yùn)算9.設(shè)G是連通簡單平面圖，G中有11個(gè)頂點(diǎn)5個(gè)面，則G中的邊是（ ）（A）10 （B）12 （C）16 （D）14 10. 下列圖形中為歐拉圖的是（ ）( A) ( B) (C) ( D) 二、填空題（每題2分，共20分

4、，答案寫于后面答題紙中。）1.令p:天下大雨，q:小王遲到。命題“除非天下大雨，否則小王不會(huì)遲到”的符號化形式為 。青島理工大學(xué)試卷紙 共 5 頁 第 1 頁試題要求: 1.試題后標(biāo)注本題得分;2.試卷應(yīng)附有評卷用標(biāo)準(zhǔn)答案,并有每題每步得分標(biāo)準(zhǔn);3.試卷必須提前一周送考試中心;4.考試前到指定地點(diǎn)領(lǐng)取試卷；5.考生不得拆散試卷，否則試卷無效。學(xué)號； 姓名： 班級： 。密。封。線。2.F(x):x是火車，G(y):y是汽車，H(x,y):x比y快。命題“說火車都比汽車快是不對的” 的符號化形式為 。3.R為A=1,2,3,4,5上的關(guān)系，則R導(dǎo)出的A的劃分是 。4.，P(A)= 。5. 如圖所示

5、哈斯圖中構(gòu)成分配格的有 。6.群G其中為集合的對稱差運(yùn)算，對于1,2P(1,2,3)的生成子群是 。7.， 。8.G為4階無向連通簡單圖，則G中至多有 棵非同構(gòu)的生成樹。9.若n階無向簡單圖G的，則G為 。10.無向圖G中有8條邊，1個(gè)1度頂點(diǎn)，2個(gè)2度頂點(diǎn)，1個(gè)5度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均為3，則G中3度頂點(diǎn)的個(gè)數(shù) 。三、計(jì)算或簡答題(共36分，答案寫于后面答題紙中。) 1.(6分)求下面公式的主析取范式和主合取范式并寫出成真賦值和成假賦值(pq)(rp)2. (6分) (3分)設(shè)個(gè)體域,消去下面公式的量詞 (3分)求下面公式的前束范式 3.(6分) R的關(guān)系圖如圖所示1234 說明R具有什么

6、性質(zhì)（指自反性、反自反性、對稱性、反對稱性、傳遞性） 求R2 求r(R),s(R),t(R) 4.(6分)設(shè)為偏序集，其中A1,2,3,4,6,9,24,54,R是A上的整除關(guān)系 畫出的哈斯圖 求A中的極大元，極小元，最大元，最小元 求B4,6,9的上界，上確界，下界，下確界5.（4分）設(shè)代數(shù)系統(tǒng)V=的運(yùn)算表如下表所列 *a b c d *a b c d *a b c da b c da b c db c b dc a b cd a c c 說明*運(yùn)算是否滿足交換律、結(jié)合律、冪等律 *運(yùn)算的單位元和零元（如果存在） 寫出所有可逆元素的逆元 青島理工大學(xué)試卷紙 共 5 頁 第 2 頁 學(xué)號； 姓

7、名： 班級： 。密。封。線。3410799712685136.(8分)(3分)求圖G的最小生成樹(5分)設(shè)有如下有向圖D= 1)求D的鄰接矩陣；2)D中v1到v4的長度為4 的通路有多少條？3) D中經(jīng)過v1的長度為3 的回路有多少條？4)D中長度不超過4 的通路有多少條？其中有多少條回路？V1V4V2V3 四、證明題（共18分，答案寫于后面答題紙中。）1.(6分)對任意集合A,B，證明：若AA=BB，則A=B。2.(6分)設(shè)u是群G中任意固定元素，如下定義新運(yùn)算：有abau1b證明：G關(guān)于運(yùn)算構(gòu)成群3.(6分)構(gòu)造下面的推理證明：每個(gè)喜歡步行的人都不喜歡騎自行車。每個(gè)人或者喜歡騎自行車或者喜

8、歡乘汽車。有的人不喜歡乘汽車，所以有的人不喜歡步行。五、應(yīng)用題（6分，答案寫于后面答題紙中。）某次國際會(huì)議有8人參加，已知每人至少與其余7人中的4人有共同語言，問服務(wù)員能否將他們安排在同一張圓桌周圍就坐，使每個(gè)人能與兩邊的人交談，請說明依據(jù)。青島理工大學(xué)試卷紙 共 5 頁 第 3 頁 學(xué)號； 姓名： 班級： 。密。封。線。 答題一、 選擇題(每題2分，共20分)1B 2D 3C 4A 5A 6A 7D 8D 9D 10C二、 填空題(每題2分，共20分)1、2、3、1,3,5, 2,44、5、L2 L36、7、(15634)(2)8、29、無向完全圖Kn10、2三、 計(jì)算題或簡答題（共36分）

9、1、（6分）(pq)(rp)(pq)(rP)（合取范式）(pq(rr)(p(qq)r)(pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)（主合取范式） (2分)m5m6m7或 (1分) M0M1M2M3M4（主析取范式）或 (0,1,2,3,4) (1分)所有成真賦值為：101，110，111 或m5 ，m6，m7，或M5 , M6 , M7 或p=1,q=0,r=1；p=1,q=1,r=0； p=1,q=1,r=1（1分）所有成假賦值為：000，001，010，011，100或m0 ，m1，m2，m3 ，m4，或M0 , M1 , M2，M3 , M4或p=0,q=0,

10、r=0；p=0,q=0,r=1； p=0,q=1,r=0 p=0,q=1,r=1；p=1,q=0,r=0（1分）2（6分）(3分)(3分)（答案不唯一）3.（6分） 不具有任何性質(zhì)（1分） R2(1分) 或r(R)= (1分)或s(R)= (1分)或t(R)= (2分)4（6分）123 669424546 的哈斯圖（2分） A中的極大元為24 54，極小元1，最大元 無，最小元1 （2分） B4,6,9的上界 無，上確界 無，下界1，下確界1 （2分）5.（4分）不滿足交換律、不滿足結(jié)合律、不滿足冪等律 （2分） *運(yùn)算的單位元 a 零元 無 （1分） a1a （1分）3477685 6. 圖

11、G的最小生成樹，如第6題答案圖. 首先選對邊(v1,v2)得1分，再選對每一條邊得2分. v1 v2 v5 v6 v8 v7 v4 v 1）A=，A2=A3=，A4=（2分）2）G中v1到v4的長度為4 的通路有4條；（1分）3）G中經(jīng)過v1的長度為3 的回路有3條；（1分）4）G中長度不超過4 的通路有72條，其中有19條回路。（1分）四、證明題（共18分）1.（6分）若B=，則BB=。從而AA =。故A=。從而B=A。（2分） 若B，則BB。從而AA。（1分）對, BB。因?yàn)锳A=BB，則A。從而xA。故BA。（2分）同理可證，AB。故B=A。（1分）2.（6分）（1）易見G關(guān)于運(yùn)算是封閉

12、的。（1分） （2）任取a，b，cG，有 （a b）c（au1b）c（au1b）u1cau1b u1c a（b c）a（b u1c）au1（b u1c）au1b u1c 結(jié)合律成立。（2分） （3）單位元是u 因?yàn)閍uau1ua uauu1aa（1分） （4）a的逆元為ua1u 因?yàn)閍（u a1u）au1u a1uu ，（u a1u）au a1u u1au （2分）3.設(shè)喜歡步行，喜歡騎自行車，喜歡乘汽車。前提： ， ，結(jié)論：（給出問題的謂詞表示得2分）證明：（1） 前提引入 （2） （1）UI規(guī)則 （3） 前提引入（4） （3）UI規(guī)則（1分）（5） （3）（4）析取三段論 （1分）（6） 前提引入 （7） (6) UI規(guī)則（8） （5）（7）拒取式 （1分）（9） （8）UG (1分)五、應(yīng)用題（6分）將每個(gè)人與會(huì)者對