第一篇：2010年7月自考離散數(shù)學(xué)試題及答案

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

課程代碼：02324

一、單項選擇題（本大題共15小題，每小題1分，共15分）

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1．下列句子不是命題的是（D）．．A．中華人民共和國的首都是北京 C．雪是黑色的

B．張三是學(xué)生 D．太好了！

2．下列式子不是謂詞合式公式的是（B）．．A．（?x）P(x)→R(y)B．(?x)┐P（x）?(?x)(P(x)→Q(x))C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x)D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z)3．下列式子為重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)?(P→Q)4．在指定的解釋下，下列公式為真的是（）A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,論域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,論域: {1,2} C．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} 5．對于公式(?x)(?y)(P(x)∧Q(y))→(?x)R(x,y)，下列說法正確的是（）A．y是自由變元 C．(?x)的轄域是R(x, y)

B．y是約束變元

D．(?x)的轄域是(?y)(P(x)∧Q(y))→(?x)R(x,y)6．設(shè)論域為{1,2}，與公式(?x)A(x)等價的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．設(shè)Z+是正整數(shù)集，R是實數(shù)集，f:Z+→R, f(n)=log2n ,則f（）A．僅是入射 C．是雙射

B．僅是滿射 D．不是函數(shù)

8．下列關(guān)系矩陣所對應(yīng)的關(guān)系具有反對稱性的是（）

?1?A．?0??10101??1 ?0???1?B．?0??10100??1 ?1??

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

?0C．?0???10001??1 ?0???1D．?0???10101??0 ?0??9．設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系R1?R2的說法正確的是（）A．一定是等價關(guān)系 C．一定不是相容關(guān)系

10．下列運算不滿足交換律的是（）．．．A．a(chǎn)*b=a+2b C．a(chǎn)*b=|a-b|

B．a(chǎn)*b=min(a,b)D．a(chǎn)*b=2ab B．一定是相容關(guān)系

D．可能是也可能不是相容關(guān)系

11．設(shè)A是偶數(shù)集合，下列說法正確的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．設(shè)*是集合A上的二元運算，下列說法正確的是（）A．在A中有關(guān)于運算*的左幺元一定有右幺元 B．在A中有關(guān)于運算*的左右幺元一定有幺元 C．在A中有關(guān)于運算*的左右幺元，它們不一定相同 D．在A中有關(guān)于運算*的幺元不一定有左右幺元 13．題13圖的最大出度是（）A．0 C．2 14．下列圖是歐拉圖的是（）

B．1 D．3

15．一棵樹的3個4度點，4個2度點，其它的都是1度，那么這棵樹的邊數(shù)是（）A．13 C．15

B．14 D．16

二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。

16．請寫出表示德摩根律的兩個命題公式等價定理___________，___________。

17．n個命題變元的___________稱為小項，其中每個變元與它的否定不能同時出現(xiàn)，但兩者必須___________。18．前提引入規(guī)則：在證明的任何步驟上都可以___________，簡稱___________規(guī)則。

19．自由變元代入規(guī)則是指對某___________出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且___________。20．設(shè)A=?,B={2,4}，則((A)=___________，A×B___________。

21．設(shè)A={1,2,3,4}, A上的二元關(guān)系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，則R2?S=___________，全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

(R)=___________。

22．設(shè)代數(shù)系統(tǒng)是環(huán)，則是___________，是___________。

23．在中，元素2的階為___________，它生成的子群為___________，其中?7為模7乘法。24．設(shè)是一個___________，如果A中任意兩個元素都有___________，則稱為格。25．若一條___________中，所有的___________均不相同，稱為跡。

三、計算題（本大題共6小題，每小題5分，共30分）

26．給定論域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在該賦值下，求式子?x(S(f(x))∧G(x, f(x)))的真值。

27．請通過等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．設(shè)A={1,2,3,4}，給定A上二元關(guān)系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的傳遞閉包。29．對題29圖所示格，找出它的所有的4元子格。

30．用矩陣的方法求題30圖中結(jié)點ui，u5之間長度為2的路徑的數(shù)目。

31．求題31圖的最小生成樹。

四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）32．用推理方法證明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．證明：設(shè)是一個群，則對于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．設(shè)圖G有n個結(jié)點，n+1條邊，證明：G中至少有一個結(jié)點度數(shù)≥3。

五、應(yīng)用題（本大題共2小題，第35小題9分，第36小題6分，共15分）

35．符合化下列命題，并構(gòu)造推理證明：三角函數(shù)都是周期函數(shù)，有些三角函數(shù)是連續(xù)函數(shù)，所以有些周期函數(shù)是連續(xù)函數(shù)。

36．兩個等價關(guān)系的并集不一定是等價關(guān)系，試舉例說明。-12

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

2010年7月全國自考離散數(shù)學(xué)試題參考答案

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

第二篇：2010年7月自考離散數(shù)學(xué)試題及答案

一、單項選擇題（本大題共15小題，每小題1分，共15分）

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1．下列句子不是命題的是（D）．．A．中華人民共和國的首都是北京 C．雪是黑色的

B．張三是學(xué)生 D．太好了！

2．下列式子不是謂詞合式公式的是（B）．．A．（?x）P(x)→R(y)B．(?x)┐P（x）?(?x)(P(x)→Q(x))C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x)D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z)3．下列式子為重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)?(P→Q)4．在指定的解釋下，下列公式為真的是（）A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,論域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,論域: {1,2} C．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} 5．對于公式(?x)(?y)(P(x)∧Q(y))→(?x)R(x,y)，下列說法正確的是（）A．y是自由變元 C．(?x)的轄域是R(x, y)

B．y是約束變元

D．(?x)的轄域是(?y)(P(x)∧Q(y))→(?x)R(x,y)6．設(shè)論域為{1,2}，與公式(?x)A(x)等價的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．設(shè)Z+是正整數(shù)集，R是實數(shù)集，f:Z+→R, f(n)=log2n ,則f（）A．僅是入射 C．是雙射

B．僅是滿射 D．不是函數(shù)

8．下列關(guān)系矩陣所對應(yīng)的關(guān)系具有反對稱性的是（）?101???A．?011?

??100???001???C．?001?

??100???100???B．?011?

??101???101???D．?010?

??100??9．設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系R1?R2的說法正確的是（）A．一定是等價關(guān)系

B．一定是相容關(guān)系

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

C．一定不是相容關(guān)系

10．下列運算不滿足交換律的是（）．．．A．a(chǎn)*b=a+2b C．a(chǎn)*b=|a-b|

D．可能是也可能不是相容關(guān)系

B．a(chǎn)*b=min(a,b)D．a(chǎn)*b=2ab

11．設(shè)A是偶數(shù)集合，下列說法正確的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．設(shè)*是集合A上的二元運算，下列說法正確的是（）A．在A中有關(guān)于運算*的左幺元一定有右幺元 B．在A中有關(guān)于運算*的左右幺元一定有幺元 C．在A中有關(guān)于運算*的左右幺元，它們不一定相同 D．在A中有關(guān)于運算*的幺元不一定有左右幺元 13．題13圖的最大出度是（）A．0 C．2 14．下列圖是歐拉圖的是（）

B．1 D．3

15．一棵樹的3個4度點，4個2度點，其它的都是1度，那么這棵樹的邊數(shù)是（）A．13 C．15

B．14 D．16

二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。

16．請寫出表示德摩根律的兩個命題公式等價定理___________，___________。

17．n個命題變元的___________稱為小項，其中每個變元與它的否定不能同時出現(xiàn)，但兩者必須___________。18．前提引入規(guī)則：在證明的任何步驟上都可以___________，簡稱___________規(guī)則。

19．自由變元代入規(guī)則是指對某___________出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且___________。

20．設(shè)A=?,B={2,4}，則((A)=___________，A×B___________。

21．設(shè)A={1,2,3,4}, A上的二元關(guān)系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，則R2?S=___________，(R-1)2=___________。

22．設(shè)代數(shù)系統(tǒng)是環(huán)，則是___________，是___________。

23．在中，元素2的階為___________，它生成的子群為___________，其中?7為模7乘法。24．設(shè)是一個___________，如果A中任意兩個元素都有___________，則稱為格。25．若一條___________中，所有的___________均不相同，稱為跡。

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

三、計算題（本大題共6小題，每小題5分，共30分）

26．給定論域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在該賦值下，求式子?x(S(f(x))∧G(x, f(x)))的真值。

27．請通過等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．設(shè)A={1,2,3,4}，給定A上二元關(guān)系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的傳遞閉包。29．對題29圖所示格，找出它的所有的4元子格。

30．用矩陣的方法求題30圖中結(jié)點ui，u5之間長度為2的路徑的數(shù)目。

31．求題31圖的最小生成樹。

四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）32．用推理方法證明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．證明：設(shè)是一個群，則對于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．設(shè)圖G有n個結(jié)點，n+1條邊，證明：G中至少有一個結(jié)點度數(shù)≥3。

五、應(yīng)用題（本大題共2小題，第35小題9分，第36小題6分，共15分）

35．符合化下列命題，并構(gòu)造推理證明：三角函數(shù)都是周期函數(shù)，有些三角函數(shù)是連續(xù)函數(shù)，所以有些周期函數(shù)是連續(xù)函數(shù)。

36．兩個等價關(guān)系的并集不一定是等價關(guān)系，試舉例說明。

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國2010年7月自學(xué)考試離散數(shù)學(xué)試題

第三篇：離散數(shù)學(xué)試題+答案

www.tmdps.cn 專注于收集各類歷年試卷和答案

一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1.一個連通的無向圖G，如果它的所有結(jié)點的度數(shù)都是偶數(shù)，那么它具有一條（）A.漢密爾頓回路

B.歐拉回路 C.漢密爾頓通路

D.初級回路

2.設(shè)G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是（）A.10

B.12

C.16

D.14 3.在布爾代數(shù)L中，表達式(a∧b)∨(a∧b∧c)∨(b∧c)的等價式是（）A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.設(shè)i是虛數(shù)，·是復(fù)數(shù)乘法運算，則G=<{1,-1,i,-i},·>是群，下列是G的子群是（）A.<{1},·>

B.〈{-1},·〉

C.〈{i},·〉

D.〈{-i},·〉

5.設(shè)Z為整數(shù)集，A為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運算，∩為集合的交運算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有（）A.〈Z，+，/〉

B.〈Z，/〉 C.〈Z，-，/〉

D.〈P(A)，∩〉 6.下列各代數(shù)系統(tǒng)中不含有零元素的是（）A.〈Q，*〉Q是全體有理數(shù)集，*是數(shù)的乘法運算

B.〈Mn(R),*〉,Mn(R)是全體n階實矩陣集合，*是矩陣乘法運算 C.〈Z，?〉，Z是整數(shù)集，?定義為x?xy=xy,?x,y∈Z D.〈Z，+〉，Z是整數(shù)集，+是數(shù)的加法運算

7.設(shè)A={1,2,3}，A上二元關(guān)系R的關(guān)系圖如下： R具有的性質(zhì)是 A.自反性 B.對稱性 C.傳遞性 D.反自反性

8.設(shè)A={a,b,c}，A上二元關(guān)系R={〈a,a〉，〈b,b〉〈,a,c〉}，則關(guān)系R的對稱閉包S(R)是（）A.R∪IA

B.R

C.R∪{〈c,a〉}

D.R∩IA 9.設(shè)X={a,b,c},Ix是X上恒等關(guān)系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價關(guān)系，R應(yīng)取（）A.｛〈c,a〉，〈a,c〉｝

B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉}

D.{〈a,c〉，〈c,b〉} 10.下列式子正確的是（）A.?∈?

B.???

C.{?}??

D.{?}∈?

11.設(shè)解釋R如下：論域D為實數(shù)集，a=0,f(x,y)=x-y,A(x,y):x

www.tmdps.cn 專注于收集各類歷年試卷和答案

D.(?x)(?y)(A(x,y)→A(f(x,a),a))12.設(shè)B是不含變元x的公式，謂詞公式(?x)(A(x)→B)等價于（）A.(?x)A(x)→B

B.(?x)A(x)→B C.A(x)→B

D.(?x)A(x)→(?x)B 13.謂詞公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中變元x（）A.是自由變元但不是約束變元 B.既不是自由變元又不是約束變元 C.既是自由變元又是約束變元 D.是約束變元但不是自由變元

14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為（）A.P∨Q

B.P∧┐Q

C.P→┐Q

D.P∨┐Q 15.以下命題公式中，為永假式的是（）A.p→(p∨q∨r)

B.(p→┐p)→┐p C.┐(q→q)∧p

D.┐(q∨┐p)→(p∧┐p)

二、填空題(每空1分，共20分)16.在一棵根樹中，僅有一個結(jié)點的入度為______，稱為樹根，其余結(jié)點的入度均為______。17.A={1,2,3,4}上二元關(guān)系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關(guān)系矩陣MR中m24=______,m34=______。18.設(shè)〈s,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。19.設(shè)A為集合，P(A)為A的冪集，則〈P(A)，是格，若x,y∈P(A),則x,y最大下界是______，?〉最小上界是______。

20.設(shè)函數(shù)f:X→Y,如果對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f是______函數(shù)，如果ranf=Y，則稱f是______函數(shù)。

21.設(shè)R為非空集合A上的等價關(guān)系，其等價類記為〔x〕R。?x,y∈A，若〈x,y〉∈R，則 〔x〕R與〔y〕R的關(guān)系是______，而若〈x,y〉?R，則〔x〕R∩〔y〕R=______。

22.使公式(?x)(?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的條件是______不含有y，______不含有x。23.設(shè)M(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號化為(?x)______,其中量詞(?x)的轄域是______。24.若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是相容的，若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是不相容的。

25.判斷一個語句是否為命題，首先要看它是否為，然后再看它是否具有唯一的。

三、計算題(共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。

27.(5)設(shè)A={a,b},P(A)是A的冪集，?是對稱差運算，可以驗證

是群。設(shè)n是正整數(shù)，求({a}-1{a})n?{a}-nn{a}n 28.(6分)設(shè)A={1,2,3,4,5},A上偏序關(guān)系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

www.tmdps.cn 專注于收集各類歷年試卷和答案

(1)作出偏序關(guān)系R的哈斯圖

(2)令B={1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并給出所有使命題為真的賦值。

30.(5分)設(shè)帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。

31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。

四、證明題(共20分)32.(6分)設(shè)T是非平凡的無向樹，T中度數(shù)最大的頂點有2個，它們的度數(shù)為k(k≥2),證明T中至少有2k-2片樹葉。

33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，?是函數(shù)復(fù)合運算。

證明：〈F, ?〉是群。

34.(6分)在個體域D={a1,a2,?，an}中證明等價式：

(?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)

五、應(yīng)用題(共15分)35.(9分)如果他是計算機系本科生或者是計算機系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。

36.(6分)一次學(xué)術(shù)會議的理事會共有20個人參加，他們之間有的相互認(rèn)識但有的相互不認(rèn)識。但對任意兩個人，他們各自認(rèn)識的人的數(shù)目之和不小于20。問能否把這20個人排在圓桌旁，使得任意一個人認(rèn)識其旁邊的兩個人?根據(jù)是什么?

參考答案

一、單項選擇題(本大題共15小題，每小題1分，共15分)

1.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空題 16.0 17.1

0 18.單位元

19.x∩y

x∪y 20.入射

滿射

21.［x］R=［y］R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)

www.tmdps.cn 專注于收集各類歷年試卷和答案

24.可滿足式

永假式(或矛盾式)25.陳述句

真值

三、計算題

?1100??1010???26.M=??

1011????0011???2?2?M=??2??1110?111???

121?011??M2ij?18,ij?6 ?M2i?1??i?1j?144

G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。

27.當(dāng)n是偶數(shù)時，?x∈P(A),xn=?

當(dāng)n是奇數(shù)時，?x∈P(A),xn=x

于是：當(dāng)n是偶數(shù)，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

=??(｛a｝-1)n｛b｝n｛a｝n=?????

當(dāng)n是奇數(shù)時，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝?(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝?｛a｝-1｛b｝｛a｝=? 28.(1)偏序關(guān)系R的哈斯圖為

(2)B的最大元：無，最小元：無；

極大元：2，5，極小元：1，3

下界：4，下確界4；

上界：無，上確界：無

29.原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命題為真的賦值是P=1,Q=0和P=1,Q=1

www.tmdps.cn 專注于收集各類歷年試卷和答案

30.令e1=(v1,v3)，e2=(v4,v6)

e3=(v2,v5)，e4=(v3,v6)

e5=(v2,v3)，e6=(v1,v2)

e7=(v1,v4)，e8=(v4,v3)

e9=(v3,v5)，e10=(v5,v6)

令ai為ei上的權(quán)，則

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=15 31.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2)

(換名)

?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2)

??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2)

??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、證明題

32.設(shè)T中有x片樹葉，y個分支點。于是T中有x+y個頂點，有x+y-1 條邊，由握手定理知T中所有頂點的度數(shù)之的

x?y

?d(vi)=2(x+y-1)。

i?又樹葉的度為1，任一分支點的度大于等于2

且度最大的頂點必是分支點，于是

x?y

?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i?1

從而2(x+y-1)≥x+2y+2k-4

x≥2k-2 33.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空

(1)?f,g∈F,因為f和g都是A到A的雙射函數(shù)，故f?g也是A到A的雙射函數(shù)，從而集合F關(guān)于運算?是封閉的。

(2)?f,g,h∈F,由函數(shù)復(fù)合運算的結(jié)合律有f?(g?h)=(f?g)?h故運算?是可結(jié)合的。

(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，?〉中的幺元

(4)?f∈F,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有f?f-1=f-1?f=IA,因此f-1是f的逆元

由此上知〈F，?〉是群

34.證明(?x)(A(x)→B(x))? ?x(┐A(x)∨B(x))

www.tmdps.cn 專注于收集各類歷年試卷和答案

?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨?∨(┐A(an)∨B(an)))

?(┐A(a1)∨A(a2)∨?∨┐A(an)∨(B(a1)∨B(a2)∨?∨(B(an))

?┐(A(a1)∧A(a2)∧?∧A(an))∨(┐B(a1)∨B(a2)∨?∨(B(an))

?┐(?x)A(x)∨(?x)B(x)?(?x)A(x)→(?x)B(x)

五、應(yīng)用題

35.令p：他是計算機系本科生

q：他是計算機系研究生

r：他學(xué)過DELPHI語言

s:他學(xué)過C++語言

t:他會編程序

前提：(p∨q)→(r∧s),(r∨s)→t

結(jié)論：p→t

證①p

P(附加前提)

②p∨q

T①I

③(p∨q)→(r∧s)

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r(nóng)∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

T⑤⑥I 36.可以把這20個人排在圓桌旁，使得任一人認(rèn)識其旁邊的兩個人。

根據(jù)：構(gòu)造無向簡單圖G=,其中V={v1,v2,?，V20}是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互認(rèn)識則在vi與vj之間連一條邊。

?Vi∈V,d(vi)是與vi相互認(rèn)識的人的數(shù)目，由題意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在漢密爾頓回路。

設(shè)C=Vi1Vi2?Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。

第四篇：2006年7月全國自考離散數(shù)學(xué)試題試卷真題及答案（精選）

www.tmdps.cn 專注于收集各類歷年試卷和答案

2006年7月全國自考離散數(shù)學(xué)試題試卷真題

一、單項選擇題（本大題共15小題，每小題1分，共15分）1．下列語句中不是命題的只有（）．A．雞毛也能飛上天？ C．不經(jīng)一事，不長一智。

B．或重于泰山，或輕于鴻毛。D．牙好，胃口就好。

2．從真值角度看，命題公式的全部類型是（）

A．永真式

B．永假式

C．永真式，永假式

D．永真式，永假式，可滿足式

3．設(shè)M（x）：x是人；F（x）：x要吃飯。用謂詞公式表達下述命題：所有的人都要吃飯，其中錯誤的表．．達式是（）A．(?x)(M(x)?F(x))C．(?x)(M(x)?F(x))

B．?(?x)(M(x)??F(x))D．(?x)(?M(x)?F(x))

4．下列公式是前束范式的是（）A．(?x)(?y)(?F(z,x)?G(y))B．(?(?x)F(x)?(?y)G(y))?H(z)C．(?x)F(x,y)?(?y)G(y)D．(?x)(F(x,y)?(?y)G(x,y))5．設(shè)論域為整數(shù)集，下列真值為真的公式是（）A．(?x)(?y)(x?y?0)

B．(?y)(?x)(x?y?0)C．(?x)(?y)(x?y?0)D．?(?x)?(?y)(x?y?0)

6．下列是謂詞演算中的合式公式的是（）

A．(?x)(p(x)??y)

B．(?x)F(x)?G(x,y)

C．(?x)P(x,y)Q(y,z)

D．(?x)?x?P(x,y)．（）A．B． C．D． ．（）

8．下列式子正確的是（）A．（A－B）-C=A-（B∪C）

（）

B．A－（B∪C）=（A－B）∪C C．~（A－B）=~（B－A）D．~（A∩B）?A 9．下列集合對所給的運算是封閉的只有（）

A．非零整數(shù)集合Z*上的除法運算

B．全體n×n實可逆矩陣集合Mn（R）上的矩陣加法和乘法運算 C．全體n×n實矩陣集合Mn（R）上的矩陣加法和乘法運算 D．A={1，2，?，10}，x*y=LCM（x，y），即x，y最小公倍數(shù)

+，*>是環(huán)，則下列說法不正確的是（）10．設(shè)是交換群 A．

B．是半群

+對*是可分配的 D．○11．下列四個格，是分配格的是（）

www.tmdps.cn 專注于收集各類歷年試卷和答案

12．下列各圖是無向完全圖的是（）

13．下列各有向圖是強連通圖的是（）

14．設(shè)Ｇ是具有n個結(jié)點的無向簡單圖，若在Ｇ中存在一條漢密爾頓路，則Ｇ中每一對結(jié)點的度數(shù)之和與n-1的關(guān)系為（）

A．大于

B．大于等于

C．等于

D．小于

15．設(shè)連通平面圖Ｇ，共有n個結(jié)點，e條邊，r個面，則歐拉證明成立的公式是（）A．e-n+r=2

B．n+r-e=2

C．n-r+e=2

D．n-e-r=2

二、填空題（本大題共10小題，每小題2分，共20分）

請在每小題的空格中填上正確答案。錯填、不填均無分。

16．所謂___是指不能再分解的命題，而復(fù)合命題是由一些____經(jīng)過聯(lián)結(jié)詞復(fù)合而成的命題。17．在命題演算中，兩個____的合取、析取、條件、雙條件均為____。

18．使公式(?x)(?y)(A(x)?B(y))?(?x)A(x)?(?y)B(y)成立的條件是____中不含y，____中不含x。19．設(shè)A={1，2，3，4}，R是A上的二元關(guān)系，R={|x/y是素數(shù)}，則domR=_____;ranR=____。20．設(shè)無向圖Ｇ有n個結(jié)點m條邊，每個結(jié)點的度數(shù)為k或k+1，記Nk為度數(shù)等于k的結(jié)點數(shù)，則Nk=_____。如果無向簡單圖C的結(jié)點的度數(shù)均為相同的偶數(shù)，且m=7，則n=____。

21．設(shè)X={1，3，5，9，15，45}，R是X上的整除關(guān)系，則R是X上的偏序，其最大元是___，極小元是____。

22．設(shè)是有界格，a,b?L,若a?b=0,則a=b=_____；若a?b=1,則a=b=____。

2-1-223．設(shè)e是群G上的幺元，若a?G且a=e,則a=____ ,a=__________。24．代數(shù)系統(tǒng)，其中A為命題公式集合。為析取運算?，則中零元素是____，幺元是____。25．樹是不包含_____的___圖。

三、計算題（本大題共6小題，第26、27題各4分，第28、29題各5分，第30、31題各6分，共30分）26．如果論域是集合{a,b,c}，試消去下面公式中的量詞：(?x)(?y)(x?y?0)27．求公式（p?q)?(q?r)的主析取范式。

28．設(shè)A={a,b,c},A上二元關(guān)系R={,,},用關(guān)系矩陣法求最小的自然數(shù)m,n,m

（2）奇數(shù)個頂點，奇數(shù)條邊

（3）偶數(shù)個頂點，奇數(shù)條邊

（4）奇數(shù)個頂點，偶數(shù)條邊

30．下列各整數(shù)集合對于整除關(guān)系“|”都構(gòu)成偏序集，判斷哪些偏序集能構(gòu)成格？并說明理由。1)L={1,2,3,4,5}

2)L={1,2,3,6,12}

www.tmdps.cn 專注于收集各類歷年試卷和答案

3)L={1,2,3,4,6,9,12,18,36}

4)L={1,2,2,2,?,2} 31．設(shè)A={2，3，5，12，19}，等價關(guān)系R={|x, y?A?x?y(mod 3)},寫出各元素的等價類，并求A/R。

四、證明題（本大題共3小題，第32、33題各6分，第34題8分，共20分）32．用等價變換法證明：(P?Q)?((R?Q)?((P?R)?Q))是永真式。

33．若無向圖G是歐拉圖，G中是否存在割邊？為什么？ 34．設(shè)A是一個集合，X=P（A），R是X上元素之間的包含關(guān)系，試證明是偏序集。（注：P（A）為A的冪集）

五、應(yīng)用題（本大題共2小題，第35題6分，第36題9分，共15分）35．設(shè)有n個村莊要修路，（1）若要使所有村莊之間都有通路，問需在兩村之間至少修幾條路？（2）若要使任意兩村莊之間有一條直接的路，則至少修幾個路？（3）若修一條連接所有村莊的環(huán)路，問有多少種修路方案？ 36．設(shè)有推理：

(a)沒有不守信用的人是可信賴的；

(b)有些可以信賴的人是受過教育的人；

(c)因此有些受過教育的人是守信用的。

試構(gòu)造推理的證明，要求把推理的前提，結(jié)論符號化為謂詞形式，并寫出推理過程。（個體域：人的集合）提示：設(shè)F（x）表示x是守信用的人；G（x）表示x是可信賴的人；H（x）表示x是受過教育的人。

23n 3

www.tmdps.cn 專注于收集各類歷年試卷和答案

www.tmdps.cn 專注于收集各類歷年試卷和答案

www.tmdps.cn 專注于收集各類歷年試卷和答案

第五篇：離散數(shù)學(xué)試題與答案

《離散數(shù)學(xué)》試題及答案

一、選擇題：本題共5小題，每小題3分，共15分，在每小題給出的四個選項中，只有一項是符合題目要求的。

1.命題公式(P?Q)?Q為()

(A)矛盾式(B)可滿足式(C)重言式(D)合取范式

2．設(shè)P表示“天下大雨”，Q表示“他在室內(nèi)運動”，則命題“除非天下大雨，否則他不在室內(nèi)運動”符號化為（）。

(A)． P?Q；(B)．P?Q；(C)．?P??Q；(D)．?P?Q．

3.設(shè)集合A={{1,2,3}, {4,5}, {6,7,8}}，則下式為真的是()

(A)1?A(B){1,2, 3}?A

(C){{4,5}}?A(D)??A

4.設(shè)A＝{1,2},B={a,b,c},C={c,d}, 則A×(B?C)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.設(shè)G如右圖：那么G不是().(A)哈密頓圖；(B)完全圖；

(C)歐拉圖；(D)平面圖.二、填空題：本大題共5小題，每小題4分，共20

6.設(shè)集合A={?,{a}}，則A的冪集P(A7.設(shè)集合A={1,2,3,4 }, B={6,8,12}, A到B的關(guān)系R＝{?x,y?y?2x,x?A,y?B},那么R1＝－

8.在“同學(xué)，老鄉(xiāng)，親戚，朋友”四個關(guān)系中_______是等價關(guān)系.9.寫出一個不含“?”的邏輯聯(lián)結(jié)詞的完備集.10.設(shè)X＝{a,b,c}，R是X上的二元關(guān)系，其關(guān)系矩陣為

?101??，那么R的關(guān)系圖為 MR＝?100????100??

三、證明題（共30分）

11.（10分）已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C)

12.（10分）構(gòu)造證明：(P?(Q?S))∧(?R∨P)∧Q?R?S

（0,1）13.（10分）證明與[0,1)，[0,1)與[0,1]等勢。

四、解答題(共35分)

14.（7分）構(gòu)造三階幻方（以1為首項的9個連續(xù)自然數(shù)正好布滿一個3?3方陣，且方陣中的每一行, 每一列及主、副對角線上的各數(shù)之和都相等.）

15.（8分）求命題公式(P?Q)?(?P??Q)的真值表.16.（10分）設(shè)R1是A1＝{1,2}到A2＝(a,b,c)的二元關(guān)系，R2是A2到A3＝{?,?}的二元關(guān)系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}

畢節(jié)學(xué)院《離散數(shù)學(xué) 》課程試卷

求R1?R2的集合表達式.17.（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？

三個條件：(1)若A去，則C和D中要去1個人；(2)B和C不能都去；

(3)若C去，則D留下。

一、單項選擇題(每小題3分，共15分)

1.B2.C3.C4.A5.B

二、填空題(每小題4分，共20分)

6.{?,{?},{{a}},{?,{a}}}

7.{<6,3>,<8,4> }8.老鄉(xiāng)

9.{?,?}或{?,?} 或 {?}或 {?}

10.見

f(0)?0??111?························································································ 10分 ,n?1,?A ·?f()?n?1n?n

??f(x)?x,x?[0,1)?A

14.85 1 2 7 6

填對每個格得1分。

15.表中最后一列的數(shù)中，每對1個數(shù)得2分.?110?16.MR1???,(2分)001??

MR2?01??(4分)??01????00??

?01??01???01?(6分)???00?????00???110? MR1?R2????001?

R1?R2?{?1,??}(10分)

17.解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時成立?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ?2分 因此(A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))

?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)

∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T ··································································································································· 8分

畢節(jié)學(xué)院《離散數(shù)學(xué) 》課程試卷

故有三種派法：B∧D，A∧C，A∧D。······································································· 10分

畢節(jié)學(xué)院《離散數(shù)學(xué) 》課程試卷