第一篇：2005-2006(1A)離散數(shù)學(xué)期末試卷答案

安徽大學(xué)2005-2006學(xué)年第一學(xué)期 《離散數(shù)學(xué)》期末考試試卷（A卷答案）

一、選擇題（2?10=20分）

C,B,C,B,D,D,D,B,A,A

二、填空題（每空2分，總2?15=30分）1．P?Q，P??Q，P?Q

2．??x(R(x)?Q(x))，?x(Q(x)?R(x)??Z(x))

3．{?,{?,{?}},{{?}},{?}} 4．{1}和{2}，{1,2}，?，無

5．2，5 6．{?1,1?,?2,2?,?1,2?,?2,1?,?3,3?,?4,4?,?3,4?,?4,3?} 7．f(f?19(B))?B，B?f?1(f(B))

三、計算題（每小題8分，總2?8=16分）

1.用等值演算法求命題公式?((P?Q)?R)??(P?Q)的主析取范式和主合取范式。解：

?((P?Q)?R)??(P?Q)?((P?Q)?R)??(?P?Q)?((P?Q)?R)?(P??Q)?(P?Q)?(P??Q)?R?(P?(Q??Q))?R?P?R4分

?(P?Q?R)?(P??Q?R)（主合取范式）??(0，2)??(1,3,4,5,6,7)?(?P??Q?R)?(?P?Q?R)?(P??Q??R)?(P??Q?R)?(P?Q??R)?(P?Q?R)（主析取范式）2．設(shè)A?3，解：因為

8分

?(B)?16，?(A?B)?64，試求B，A?B，A?B和A?B。

。于?(B)?16，所以B?4；因為?(A?B)?64，所以A?B?6（2分）是集合A,B的文氏圖如下：

所以，A?B?1（4分），A?B?2（6分），A?B?5（8分）。

四、證明題（1、2小題每小題9分，3、4小題每小題8分，總分34）1． 用CP規(guī)則證明?P?(?Q?R)，Q?(R?S)，P?Q?S。證： ①Q(mào) P（附加前提）1分 ②Q?(R?S)P 2分 ③R?S T①②I 3分 ④?P?(?Q?R)P 4分 ⑤P P 5分 ⑥?Q?R T④⑤I 6分 ⑦R T①⑥I 7分 ⑧S T③⑦I 8分 ⑨Q?S CP 9分 2． 設(shè)R1和R2是A上的關(guān)系，證明下列各式：（a）r(R1?R2)?r(R1)?r(R2)（b）s(R1?R2)?s(R1)?s(R2)

（c）t(R1?R2)?t(R1)?t(R2)證：

（a）r(R1?R2)?R1?R2?I?(R1?I)?(R2?I)?r(R1)?r(R2)

（這里I是A上的相等關(guān)系）3分

（b）s(R1?R2)?(R1?R2)?(R1?R2)?(R1?R2)?(R1?R2)

~~~~~?(R1?R)?(R2?R2)?s(R1)?s(R2)6分

（c）因為t(R1?R2)?R1，t(R1?R2)?R2且關(guān)系t(R1?R2)具有傳遞特性，根據(jù)傳遞閉包定義? t(R1?R2)?t(R1)，t(R1?R2)?t(R2)，所以t(R1?R2)?t(R1)?t(R2)。9分

3． 設(shè)函數(shù)f:R?R?R?R，f定義為：f(?x,y?)??x?y,x?y?。（1）證明f是單射；（2）證明f是滿射。證明：（1）??x1,y1?，?x2,y2??R?R，若f(?x1,y1?)?f(?x2,y2?)，即

?x1?y1?x2?y2則?，易得x1?x2，y1?y2，?x1?y1,x1?y1???x2?y2,x2?y2?，?x1?y1?x2?y2從而是單射。4分

（2）??p,q??R?R，由f(?x,y?)??p,q?，通過計算可得?而?p,q?的原象存在，f是滿射的。8分 4． 設(shè)A?N，B?(0,1)。證明A?B?c。證明：

定義一個從A?B到實數(shù)R的函數(shù)f：

?x?(p?q)/2，從

?y?(p?q)/2f:A?B?R，f(?n,x?)?n?x，其中n?N，x?(0,1)

因為f是單射且R?c，所以A?B?c。4分

此外，作映射g:(0,1)?A?B，g(x)??0,x?，其中x?(0,1)。因為g是單射，故c?A?B。

所以A?B?c。8分

第二篇：離散數(shù)學(xué)期末試卷

北京工業(yè)大學(xué)經(jīng)管學(xué)院期末試卷

《離散數(shù)學(xué)》（A）

學(xué)號姓名：成績

一、單項選擇題（每題2分，共18分）

1．令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（D）．

A．P→Q

C．P∧Q B．P∨Q D．P∧Q

p→q，蘊涵式，表示假設(shè)、條件、“如果，就”。

“→”與此題無關(guān)

2.關(guān)于命題變元P和Q的極大項M1表示(C)。書P15-P20，此題換作p、q更容易理解

A.┐P∧QB.┐P∨Qp∨┐q----01----1-----M

1C.P∨┐QD.P∧┐Q

3.設(shè)R（x）：x是實數(shù)；S（x,y）：x小于y。用謂詞表達下述命題：不存在最小的實數(shù)。其中錯誤的表達式是：（D）

4.在論域D={a,b}中與公式（?x）A（x）等價的不含存在量詞的公式是（B）

A.A(a)?A(b)

C.A(a)?A(b)

5．下列命題公式為重言式的是（C）

A．Q→（P∧Q）

C．（P∧Q）→PB．P→（P∧Q）D．（P∨Q）→QB.A(a)?A(b)D.A(b)?A(a)

牢記→真假條件，作為選擇題可直接代入0、1，使選項出現(xiàn)1→0，排除。熟練的可直接看出C不存在1→0的情況

6.設(shè)A=｛1，2，3｝，B=｛a,b｝，下列二元關(guān)系R為A到B的函數(shù)的是(A)

A.R=｛<1,a>,<2,a>,<3,a>｝

B.R=｛<1,a>,<2,b>｝

C.R=｛<1,a>,<1,b>,<2,a>,<3,a>｝

D.R=｛<1,b>,<2,a>,<3,b>,<1,a>｝

-第 1頁

7.偏序關(guān)系具有性質(zhì)（D）背

A.自反、對稱、傳遞

B.自反、反對稱

C.反自反、對稱、傳遞

D.自反、反對稱、傳遞

8.設(shè)R為實數(shù)集合，映射?:R?R,?(x)??x2?2x?1,則? 是(D).(A)單射而非滿射(C)雙射(B)滿射而非單射(D)既不是單射也不是滿射.書P96.設(shè)函數(shù)f：A→B

（1）若ranf=B，則f是滿射的【即值域為B的全集，在本題中為R，該二次函數(shù)有最高點，不滿足】

（2）若對于任何的x1,x2∈A , x1≠x2,都有f(x1)≠f(x2)，則稱f是單射的【即x,y真正一一對應(yīng)，甚至不存在一個y對應(yīng)多個x。顯然，本題為二次函數(shù)，不滿足】

（3）若f既是滿射的，又是單射的，則稱f是雙射的【本題中兩個都不滿足，既不是單射也不是滿射】

二、填空題（每空2分，共22分）

１.設(shè)Q為有理數(shù)集，笛卡爾集S=Q×Q，*是S上的二元運算，?,∈S,*=, 則*運算的幺元是_____<1,0>_____。?∈S, 若a≠0，則的逆元是______<1/a,-b>______。書P123定義

２.在個體域D中，公式?xG(x)的真值為假當(dāng)且僅當(dāng)__某個G(x)的真值為假__，公式?xG(x)的真值為假，當(dāng)且僅當(dāng)__所有G(x)的真值都為假__。

３.給定個體域為整數(shù)域，若F（x）：表示x是偶數(shù)，G（x）：表示x是奇數(shù)；那么，(?x)F(x)?(?x)G(x)是一個(?x)(F(x)?G(x))是一個

４.設(shè)A??a,b,c?　,A上的二元關(guān)系R?a,b,b,c,則r(R)?

{,,,,,} 。

書P89、P85.自反閉包：r(R)= R U R0

={,} U {,,,} ={,,,,,}對稱閉包：s(R)= R U R-1 = {,} U {,} = {,,,}-第 2頁

傳遞閉包：t(R)= RUR2 UR3U……

５.設(shè)X={1,2,3},Y={a,b}，則從X到Y(jié)的不同的函數(shù)共有___8___個.書P96，B上A的概念：

設(shè)Ａ、Ｂ為集合，所有從Ａ到Ｂ的函數(shù)構(gòu)成集合ＢA，讀作“B上A”

如果|A| = m，|B| = n，m、n不全是0，則|BA| = nm

即，若題中給出集合A有m個元素，B有n個元素，可直接用nm 計算出A到B的函數(shù)個數(shù)。本題中為23 = 8

６.設(shè)，a,b?G，則（a-1）-1，（a?b）-1b-1 * a-1。

書P139公式

7.設(shè)X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，則f?g=__{<1,3>,<2,1>,<3,1>}___，g?f=__{<1,3>,<2,3>,<3,2>}__。書P82-8

3合成：F?G = {|xGz∧zFy}

需要說明的是，這里的合成F?G是左復(fù)合，即G先作用，然后將F復(fù)合到G上。之前的答案“有誤”，因為采用了右復(fù)合。這兩種合成定義所計算的合成結(jié)果是不相等的，但兩個定義都是合理的，只要在體系內(nèi)部采用同樣的定義就可以了?？傊?，在咱們的離散里牢記左復(fù)合。

三、計算題（每題9分，共36分）

1.設(shè)集合A＝{1, 2, 3,4,5}，A上的關(guān)系R＝{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3,3>,<3,5>,<4,4>,<5,5>}

(1)畫出R的關(guān)系圖；

(2)問R具有關(guān)系的哪幾種性質(zhì)(自反、對稱、傳遞、反對稱).自反性、傳遞性

書P87表格，根據(jù)關(guān)系圖可直接判斷性質(zhì)……

(3)給出R的傳遞閉包。

R={<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>,<3,5>,<4,4>,<5,5>}

-第 3頁

R2 = R?R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}R3 = R2?R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}……

所以，t(R)= {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

2.集合S={a,b,c,d,e}上的二元運算*的運算表如下，求出它的幺元，零元，及逆

元。*abcde

abaccc

babcde

cccccc

dedcba

edecdb

幺元：b

零元：c

逆元：a-1 =a,b-1 =b, d-1 =d,e-1 =e

書P123定義

3．求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式及成真賦值。

A = P→((┐P∨Q)∧(Q∧P))

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

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

= P→(Q∧P)

= ┐P∨(Q∧P)

=(┐P∧(Q∨┐Q))∨(Q∧P)

=(cP∧Q)∨(┐P∧┐Q)∨(P∧Q)

=(┐P∧┐Q)∨(┐P∧Q)∨(P∧Q)

= m0∨m1∨m

3成真賦值為00，01，1

14．求在1到1000000之間有多少個整數(shù)既不是完全立方數(shù)，也不是完全平方數(shù)？-第 4頁

完全平方數(shù)的個數(shù)：1000=1000000，所以有1000個（即1到1000）

完全立方數(shù)的個數(shù)：1003 =1000000，所以有100個（即1到100）

既是完全平方數(shù)又是完全立方數(shù)的重復(fù)部分：106 =1000000，所以有10個（即16到106）所以既不是完全立方數(shù)，也不是完全平方數(shù)的整數(shù)有：1000000-(1000+100-10)= 998910

2四、證明題（每題8分，共24分）

1．若公司拒絕增加工資，則罷工不會停止，除非罷工超過三個月且公司經(jīng)理辭職。公司拒絕增加工資，罷工又剛剛開始。罷工是否能停止？（給出相應(yīng)推理的證明過程）

2．給出關(guān)系不滿足對稱性的條件并證明。

?∈R∧?R

??∈R∧?R

?┐?(∈R∧∈R)

3．如果關(guān)系R和S為X上的等價關(guān)系，證明：R∩S也是X上的等價關(guān)系。

(1)自反

設(shè)?x∈X【推∈R∩S】

∵R和S為X上的等價關(guān)系

∴R和S均為X上的自反關(guān)系

∵x∈X

∴∈R, ∈S

∴∈R∩S

∴R∩S在X上是自反的(2)對稱

設(shè)?∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵R和S為X上的等價關(guān)系

∴R和S均為X上的對稱關(guān)系

∴∈R,∈S

∴∈R∩S

-第 5頁

∵此時∈R∩S

∴R∩S在X上是對稱的【∈R∩S時，必有∈R∩S】

(3)傳遞

設(shè)?∈R∩S，?∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵∈R∩S

∴∈R,∈S

∵R和S為X上的等價關(guān)系

∴R和S均為X上的傳遞關(guān)系

∴∈R,∈S

∴∈R∩S

∵此時∈R∩S，∈R∩S

∴R∩S在X上是傳遞的【∈R∩S，∈R∩S時，必有∈R∩S】

綜上所述，R∩S在X上是自反、對稱、傳遞的∴R∩S為X上的等價關(guān)系

書P90

等價關(guān)系：自反、對稱、傳遞

偏序關(guān)系：自反、反對稱、傳遞

因此要證明某關(guān)系在非空集合上是等價關(guān)系或偏序關(guān)系，一般需分為三個性質(zhì)分別證明，同時，題目條件中若給出等價關(guān)系或偏序關(guān)系，也可分為三部分選擇使用。這類題條件較多（自己設(shè)的、題目推的），一定要思路清晰，否則容易寫亂自己繞不出來??

這道題三部分每個部分所設(shè)的條件都是該性質(zhì)定義里的“若”，想要推出定義里的“則”，即用定義證明。這就是思路很重要的一部分。

-第 6頁

第三篇：離散數(shù)學(xué)浙師大2008期末試卷

浙江師范大學(xué)《離散數(shù)學(xué)》考試卷

考試形式閉卷使用學(xué)生 計(非師范): 02班

考試時間120 分鐘出卷時間 2008 年5月28日

說明：考生應(yīng)將全部答案都寫在答題紙上，否則作無效處理。

一。選擇題（每題2分，共20分）：

1．命題公式p?(q?p)為（）。

A．重言式B．可滿足式C．矛盾式D．等值式

2．設(shè)集合A = {1，a}，則P(A)=（）。

A．{{1}，{a}}B．{?，{1}，{a}}

C．{?，{1}，{a}，{1，a}}D．{{1}，{a}，{1，a}}

3．下列命題中正確的結(jié)論是：（）

A．集合上A的關(guān)系如果不是自反的，就一定是反自反的；

B．若關(guān)系R,S都是反自反的，那么R?S必也為反自反的；

C．若關(guān)系R,S都是自反的，那么R?S必也為自反的；

D．每一個全序集必為良序集.4．下列結(jié)論中不正確的結(jié)論是：（）

A．三個命題變元的布爾小項?p?q??r的編碼是m010；

B．三個命題變元的布爾大項?p?q??r的編碼是M101；

C．任意兩個不同的布爾小項的合取式必為永假式；

D．任意兩個不同的布爾大項的合取式必為永假式.5．設(shè)集合A和二元運算*，可交換的代數(shù)運算是（）。

A．設(shè)A?P({x,y}),?a,b?A,a?b?a?b

B．設(shè)A?{1,?1,2,3,4,?5},?a,b?A,a?b?|b|

C．設(shè)A?Mn(R)，運算?是矩陣的乘法

D．設(shè)A?Z,?a,b?A,a?b?a?2b

6．以下命題中不正確的結(jié)論是（）

A．素數(shù)階群必為循環(huán)群；B．Abel群必為循環(huán)群；

C．循環(huán)群必為Abel群D．4階群必為Abel群.7．設(shè)代數(shù)系統(tǒng)(K1,?)和(K2,?)，存在映射f:K1?K2，如果?a,b?K1，都有（），稱K1與K2同態(tài)。

A．f(a?b)?f(a)?f(b)B．f(a?b)?f(a)?f(b)

C．f(a?b)?f(a)?f(b)D．f(a?b)?f(a)?f(b)

8．圖G有21條邊，3個4度結(jié)點，其余均為3度結(jié)點，則G有（）個結(jié)點。A．13B．15C．17D．19

9．以下命題中正確的結(jié)論是（）

A．n?2k時，完全圖Kn必為歐拉圖

B．如果一個連通圖的奇結(jié)點的個數(shù)大于2，那么它可能是一個Euler圖；

C．一棵樹必是連通圖，且其中沒有回路；

D．圖的鄰接矩陣必為對稱陣.10．若連通圖G??V,E?，其中|V|?n,|E|?m，則要刪去G中（）條邊，才能確定G的一棵生成樹。

A．n?m?1B．n?m?1C．m?n?1D．m?n?

1二．填空題（每題2分，共20分）

11．在有界格中命題a?0?0的對偶命題為

12．設(shè)G是有限群,H是G的子群，則H在G中的右陪集數(shù)為。

13．設(shè)集合A = {a,b,c,d}，A上的二元關(guān)系R = {,,,}，那么Dom(R)= Ran(R)=。

?110???14．設(shè)集合B = {a,b,c}上的二元關(guān)系R的關(guān)系矩陣MR??001?，則R具有的性質(zhì)

?000???

是，且它的對稱閉包S(R)＝。

15．設(shè)集合A = {a,b}，B = {1,2}，則從A到B的所有函數(shù)是，其中雙射的函數(shù)

16．設(shè)無向圖G??V,E?是哈密頓圖，對于任意的V1?V且V1??均有 其中，p(G?V1)為G?V1的連通分支數(shù)。

17．公式(a?(b?c)?d?e?f)?(g?(h?i)?j)的前綴符號法表示為。

18．已知下圖，它的點連通度?(G)為，邊連通度?(G)為

20．若二部圖Km,n為完全二部圖，則其邊數(shù)為

三．計算題(一)（每小題5分，共30分）

21．符號化下述兩個語句，并說明其區(qū)別：

（1）如果天不下雨，我們就去旅游；（2）只有不下雨，我們才去旅游。

22．將下命題化為主析取范式和主合取范式：(p?(q?r))?(p?q?r).23．設(shè)R={<0,1>,<1,0>,<0,2>,<2,0>}，求：⑴ R*R；⑵ R*R-1； ⑶R[{0}]

24．設(shè)集合Ａ＝｛１，２，３，４｝，Ａ上的二元關(guān)系Ｒ，其中Ｒ＝｛<1,1>,<1,4>,<2,2>, <2,3>,<3,2>,<3,3>,<4,1>,<4,4>｝，說明Ｒ是否Ａ上的等價關(guān)系。

25．設(shè)A?{1,2,?,12}，?為整除關(guān)系，B?{2,3,4}，(1)畫出偏序集?A,??的哈斯圖；

（2）找出A的極大元、極小元、最大元、最小元；（3）在?A,??中求B的上界、下界、最小上界、最大下界.26．設(shè)代數(shù)系統(tǒng)(Z,?),其中Z是整數(shù)集，二元運算定義為

?a,b?Z,a?b?a?b?2。?a?Z,求a的逆元.三．計算題(二)（每小題7分，共14分）

27．設(shè)G??a?是15階循環(huán)群.(1)求出G的所有生成元；（2）求出G的所有子群.28．求下圖D的鄰接矩陣A(D)，并算出其可達矩陣P(D)

五．證明題（每小題8分，共16分）

29．在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：

每個喜歡步行的人都不喜歡騎自行車。每個人或者喜歡騎自行車或者喜歡乘汽車。有的人不喜歡乘汽車，所有的人不喜歡步行。（個體域為人類集合）

30．證明：設(shè)?S,?,??是具有兩個二元運算的代數(shù)系統(tǒng)，且對于?和?運算適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義S中的偏序?，使得?S,??構(gòu)成一個格，且?a,b?S，有a?b?a?b，a?b?a?b.

第四篇：蘇州大學(xué)離散數(shù)學(xué)期末試卷

蘇州大學(xué)2011—2012年上學(xué)期離散數(shù)學(xué)期末試卷

一、名詞解釋

1、等勢：

2、阿貝爾群：

3、偏序關(guān)系：

4、命題：

5、平面圖：

二、求(p∧r)∨(p←→q)的主析取和主合取范式。

三、符號化下面的命題并推證其結(jié)論。

任何人如果他喜歡音樂，他就不喜歡美術(shù)，每個人或者喜歡美術(shù)或者喜歡體育，有的人不喜歡體育。所以存在有人不喜歡音樂。

四、證明：

1）A∩（A∪B）＝A 2）若關(guān)系R是對稱和傳遞的，試證明R°R=R。

五、已知映射f和g，f和g都是雙射，試證明f°g也為雙射。

六、證明：[0,1]是不可數(shù)的。

七、設(shè)是一個分配格，那么，對于任意的a，b，c∈A,如果有：

a∧b＝a∧c，a∨b＝a∨c 成立，則必有b＝c。

八、有關(guān)獨異點的證明，證明某一代數(shù)系統(tǒng)是可交換的獨異點。

九、簡單無向圖G，有N個結(jié)點，N+1條邊，證明G中至少有一個結(jié)點的次數(shù)大于等于3。

十、簡述歐拉定理，并證明該定理成立。

注：該份試題是參加完離散考試后整理出來的，除第八大題記不清具體題目外，其他都是原題。希望對學(xué)弟學(xué)妹的離散數(shù)學(xué)期末復(fù)習(xí)有所幫助。另外說明該份試卷是馬小虎老師班上考的，徐汀榮老師班上不知道是不是和該份試卷一樣。

第五篇：離散數(shù)學(xué)期末試卷06-07

安徽大學(xué)2006—2007學(xué)年

A.4，20 ； B.4，22 ； C.5，22 ； D.5，24。

圖1-8

9．設(shè)G是具有w個連通分支的平面圖，若G中有n個結(jié)點，m條邊，k個面，則必有（）A.n?m?k?2 ； B.n?m?k?w ； C.n?m?k?w?1 ； D.n?m?k?w?1。

10．設(shè)G=(V,E)為(n,m)連通圖，則要確定G的一顆生成樹必刪去G中邊數(shù)為（）A．n-m-1 ； B． n-m+1 ； C．m-n+1 ； D．m-n-1。

二、填空題（每空2分，共22分）

1．設(shè)G={1,5,7,11}，為群，其中*為模12乘法，則5的階（即周期）為__________，有__________個真子群。

2．令A(yù)={a,b,c}，是群，a是單位元，則b2=__________，c的階（即周期）為__________。3．設(shè)H?{0,4,8}，?H,?12?是群?N12,?12?的子群，其中N12?{0,1,2,...,11}，?12是模12加法，則?N12,?12?有__________個真子群，H的左培集3H?__________，4H?__________。4．若連通平面圖G有4個結(jié)點，3個面，則G有__________條邊。

5．設(shè)T是無向樹，它有40個1度點，20個2度點，31個3度點，且沒有6度或6度以上的頂點。則T中有__________個4度點，有__________個5度點。

6．無向圖G是有k（k?2）棵樹組成的森林，至少要添加_______條邊才能使G成為一棵樹。

三、綜合題（每小題6分，共18分）

1．Q為有理數(shù)集，Q上定義運算*為：a*b?a?b?ab。（共6分）

（1）求的幺元；（2分）

（2）求中元素a的逆元（若存在逆元）；（2分）

（3）求2*（-5）；7*12。（2分）

2．圖3-2是格L所對應(yīng)的哈斯圖。（共6分）

《

離散數(shù)學(xué)

》試卷

（1）若a,b,d,0的補元存在，寫出它們的補元；（2分）（2）L是否是有補格？說明理由；（2分）（3）L是否是分配格？說明理由。（2分）a d b e c 0 圖3-2 3．畫出所有具有6個頂點的無向樹。（6分）

四、證明題（每小題8分，共40分）

1．設(shè)?G,*?是一個群，證明：對于G中任意的a,b,c,d,a1,b1,c1,d1，如果a*c?a1*c1，a*d?a1*d1，b*c?b1*c1。則有b*d?b1*d1。

2．設(shè)G是交換群，證明G中一切有限階元素所成集合H是G的一個子群。

《

離散數(shù)學(xué)

》試卷

3．設(shè)?L,??為一個格，試證明：?L,??為分配格的充要條件是對于任意的a,b,c?L，有(a?b)*c?a?(b*c)。

4．證明在無向完全圖Kn中（n?3）任意刪去n-3條邊后，所得到的圖是哈密爾頓圖。

5．設(shè)簡單平面圖G中結(jié)點數(shù)n?7，邊數(shù)m?15，證明：G是連通的。

《

離散數(shù)學(xué)

》試卷

安徽大學(xué)2006—2007學(xué)年

圖3.3（注，直接畫出以上六個圖形得6分，寫出分析過程并正確可得3分。）

四、證明題（每小題8分，共40分）

1．證明：因為?G,*?是一個群，則?x,y?G，有(x*y)?1?y?1*x?1，x*x?1?e（1分）。所以，（2分）

=(b*c)*(c?1*a?1)*(a*d)（3分）b*d?b*(c*c?1)*(a?1*a)*d =(b1*c1)*(a*c)?1*(a1*d1)（4分）=(b1*c1)*(a1*c1)?1*(a1*d1)（5分）=(b1*c1)*(c1*a1)*(a1*d1)（6分）

=b1*(c1*c1)*(a1*a1)*d1（7分）

=b1*d1（8分）

2．證明：

(1)e?H，所以H??；（2分）

(2)對任x,y?H，存在m,n?Z?，使xm?e，yn?e，?G是交換群，?(x,y)mn?xm?n?ym?n?e，即xy也是有限階元素，所以xy?H；（6分）(3)對任x?H，存在m?Z?，使xm?e，所以(x?1)m?(xm)?1?e?1?e，所以x?1?H。（8分）

3．證明：

設(shè)?L,??是分配格。由a*c?a，(b*c)?(b*c)，可得

(a*c)?(b*c)?a?(b*c)，而(a?b)*c?(a*c)?(b*c)所以(a?b)*c?a?(b*c)。（2分）

反之，若對于任意的a,b,c?L，有(a?b)*c?a?(b*c)，則可得

(a?b)*c?((b?a)*c)*c

《

離散數(shù)學(xué)

》試卷

?1?1?1?1?(b?(a*c))*c 由已知條件 ?((a*c)?b)*c

?(a*c)?(b*c)由已知條件（6

分）

又由a*c?(a?b)*c和b*c?(a?b)*c，可得

(a*c)?(b*c)?(a?b)*c

于是有(a?b)*c?(a*c)?(b*c)（8分）

4．證明：

我們已經(jīng)知道，一個n階無向簡單圖是哈密爾頓圖的充分條件是：圖中任意不同兩點的度數(shù)之和大于等于n。（2分）

現(xiàn)證在無向完全圖Kn中任意刪去n-3條邊后所得的圖G，其不同兩點的度數(shù)之和大于等于n。用反證法。

設(shè)圖G中存在兩點vi和vj，其度數(shù)之和不大于等于n，即

deg(vi)+deg(vj)?n-1 刪去這兩個點后，至多刪去圖G中的n-1條邊，由題設(shè)條件可知，圖G的邊數(shù)

m?(n?1)? ?n(n?1)22

?(n?3)?(n?1)

?1（6(n?2)(n?3)分）

(n?2)(n?3)2(n?2)(n?3)2?1由此可知，在圖G中刪去點vi和vj后，余下的圖為具有n-2個點，且至少有但這樣的簡單無向圖是不存在的。因為具有n-2個點的簡單無向圖最多有

條邊，條邊。所以圖G中任意不同的兩點的度數(shù)之和大于等于n，圖G為哈密爾頓圖。（8分）

5．證明：

設(shè)G為非連通的，具有??2個連通分支G1,G2,...,G?。設(shè)Gi的結(jié)點數(shù)為ni，邊數(shù)為mi，i?1,2,...,?。

若存在nj?1，則?必為2，因為只有此時G為一個平凡圖并上一個K6才能使其邊數(shù)為15，可是K6不是平面圖，這矛盾于G為平面圖這個事實，所以不存在nj?1。（2分）

若存在nj?2，Gj中至多有一條邊（簡單圖），另外5個結(jié)點構(gòu)成K5時邊數(shù)最多，但其值也僅為10條邊，這與G有15條邊矛盾。（4分）

綜上所述，ni必大于等于3，i?1,2,...,?。由簡單平面圖可得：

mi?3ni?6，i?1,2,...,?

求和得：m?3n?6?。（6分）將n?7，m?15代入得：15?21?6????1。這與??2矛盾。故G必為連通圖。（8分）

《

離散數(shù)學(xué)

》試卷