第一篇：離散數學單元測試試題1

臨沂大學2015—2016學年度第1學期

離散數學單元測試試題一

(適用于2014級計算機科學與技術、軟件工程、網絡工程專業(yè)本科學生)

一、選擇題(共10題，每題3分，共30分)1.下列語句中為命題的是（D)。A.這朵花是誰的？ B.這朵花真美麗??！C.這朵花是你的嗎？ D.這朵花是他的。

2.若p：他聰明；q：他用功；則“他雖聰明，但不用功”，可符號化為(B)。A.p∨q

B.p∧┐q

C.p→┐q

D.p∨┐q 3.命題公式p∨q→q的公式類型為（D)。A.矛盾式 B.非重言可滿足式 C.重言式

D.條件式

4.若F(x)：x是有理數，G(x)：x能被2整除，則“有的有理數能被2整除”，可符號化為（A)。

A.?x(F(x)∧G(x))

B.F(x)∧G(x)

C.?xF(x)

D.?xG(x)5.設F(x)表示x是火車，G(x)表示y是汽車，H(x，y)表示x比y快，命題“某些汽車比所有火車慢”的符號化公式是（B)。

A.?y(G(y)→?x(F(x)∧H(x,y)))B.?y(G(y)∧?x(F(x)→H(x,y)))C.?x?y(G(y)→(F(x)∧H(x,y)))D.?y(G(y)→(?x)(F(x)→H(x,y)))6．設集合A={1,2,3},A上的關系R={<1,2>,<1,3>,<3,3>},則R具有(D)。A.自反性 B.傳遞性 C.對稱性 D.以上答案都不對

######7.謂詞公式?x(P(x)∨?yR(y))→Q(x)中的 x是(C)。A.自由變元 B.約束變元

C.既是自由變元又是約束變元 D.既不是自由變元又不是約束變元

8.設X、Y是兩個集合且|X|＝n，|Y|＝m，則從X到Y可產生(A)個二元關系。A.n ? m B.mn

C.2n m D.nm 9.下列關于集合的表示中正確的為(C)。A.{a}?{a,b,c} B.{a}?{a,b,c}

C.??{a,b,c} D.{a,b}?{a,b,c} 10．設集合A={1,2,3,4,5},下列哪些是集合A的劃分(D)。A.{{1,2},{3,5}}

B.{{1,2,3,4},5} C.{ ?,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}}

二、填空題(共10空，每空3分，共30分)1.設p：2＋2＝5，q：明天是陰天，則命題“只要2＋2＝5，那么明天是陰天”可符號化為 p->q，其真值是 1。

2.設p:你陪伴我，q:你代我叫車子，r:我出去，則“如果你不陪伴我或不代我叫車子,我就不出去?！钡姆柣问綖??p/?q->r。

3.設p: 天下雨，q: 天刮風，r: 我去書店，則“如果天不下雨并且不刮風，我就去書店”的符號化形式為。

4.設S(x)∶x是大學生；K(x)∶x是運動員。則“有些運動員不是大學生”的符號化為。

5.設P(x)：x非常聰明；Q(x):x非常能干；a：小李；則“小李非常聰明且能干”的符號化形式為。

6.設F(x): x是人，G(x): x用右手寫字，則“有的人并不用右手寫字”的符號化形式為。

7.設S(x)：x是學生；L(x)：x喜歡英語。則“有些學生喜歡英語”的符號化為：。8.在公式?x(P(z)→Q(x,z))∧?zR(x,z)中，?x的轄域是

，z的轄域是。

三、計算與證明(共2題，每題20分，共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。

2.在命題邏輯自然推理系統中，構造下面推理的證明。前提： p∨q, q→r, p→s, ┐s，結論：r ∧

(p∨q)。

第二篇：離散數學期末試題

離散數學考試試題（A卷及答案）

一、（10分）求(P?Q)?(P∧?(Q∨?R))的主析取范式 解：(P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R))

?(P∨Q)∨(P∧?Q∧R))

?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R)

?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1

?m2∨m3∨m4∨m5∨m6∨m7

二、（10分）在某次研討會的休息時間，3名與會者根據王教授的口音分別作出下述判斷： 甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教授既不是上海人，也不是杭州人。

王教授聽后說：你們3人中有一個全說對了，有一人全說錯了，還有一個人對錯各一半。試判斷王教授是哪里人？

解 設設P：王教授是蘇州人；Q：王教授是上海人；R：王教授是杭州人。則根據題意應有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R

王教授只可能是其中一個城市的人或者3個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因為，若甲全錯了，則有?Q∧P，因此，乙全對。同理，乙全錯則甲全對。所以丙必是一對一錯。故王教授的話符號化為：

((?P∧Q)∧((Q∧?R)∨(?Q∧R)))∨((?Q∧P)∧(?Q∧R))?(?P∧Q∧Q∧?R)∨(?P∧Q∧?Q∧R)∨(?Q∧P∧?Q∧R)?(?P∧Q∧?R)∨(P∧?Q∧R)??P∧Q∧?R ?T 因此，王教授是上海人。

三、（10分）證明tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關系。

證明 設R是非空集合A上的二元關系，則tsr(R)是包含R的且具有自反性、對稱性和傳遞性的關系。

若R是包含R的且具有自反性、對稱性和傳遞性的任意關系，則由閉包的定義知r(R)?R。則 ''sr(R)?s(R)＝R，進而有tsr(R)?t(R)＝R。

綜上可知，tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關系。

四、（15分）集合A＝{a，b，c，d，e}上的二元關系R為R＝{，，，，，，，，，，，，，}，(1)寫出R的關系矩陣。

(2)判斷R是不是偏序關系，為什么？ 解(1)R的關系矩陣為： ''''?1??0M(R)??0??0?0?1111??1101?0101?

?0011?0001??(2)由關系矩陣可知，對角線上所有元素全為1，故R是自反的；rij＋rji≤1，故R是反對稱的；可計算對應的關系矩陣為：

?1??0M(R2)??0??0?0?由以上矩陣可知R是傳遞的。

1111??1101?0101??M(R)

?0011?0001??

五、（10分）設A、B、C和D為任意集合，證明(A－B)×C＝(A×C)－(B×C)。證明：因為

∈(A－B)×C?x∈(A－B)∧y∈C

?(x∈A∧x?B)∧y∈C

?(x∈A∧y∈C∧x?B)∨(x∈A∧y∈C∧y?C)?(x∈A∧y∈C)∧(x?B∨y?C)?(x∈A∧y∈C)∧?(x∈B∧y∈C)?∈(A×C)∧?(B×C)?∈(A×C)－(B×C)所以，(A－B)×C＝(A×C－B×C)。

六、（10分）設f：A?B，g：B?C，h：C?A，證明：如果h?g?f＝IA，f?h?g＝IB，g?f?h＝IC，則f、g、h均為雙射，并求出f、g和h。

解 因IA恒等函數，由h?g?f＝IA可得f是單射，h是滿射；因IB恒等函數，由f?h?g＝IB可得g是單射，f是滿射；因IC恒等函數，由g?f?h＝IC可得h是單射，g是滿射。從而f、g、h均為雙射。

由h?g?f＝IA，得f＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。－

1－1

－1－1－1

－1

七、（15分）設是一代數系統，運算*滿足交換律和結合律，且a*x＝a*y?x＝y，證明：若G有限，則G是一群。

證明 因G有限，不妨設G＝{a1，a2，…，an}。由a*x＝a*y?x＝y得，若x≠y，則a*x≠a*y。于是可證，對任意的a∈G，有aG＝G。又因為運算*滿足交換律，所以aG＝G＝Ga。令e∈G使得a*e＝a。對任意的b∈G，令c*a＝b，則b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由運算*滿足交換律得e*b＝b，所以e是關于運算*的幺元。對任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由運算*滿足交換律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每個元素都存在逆元。故G是一群。

八、（20分）（1）證明在n個結點的連通圖G中，至少有n－1條邊。

證明 不妨設G是無向連通圖（若G為有向圖，可略去邊的方向討論對應的無向圖）。

設G中結點為v1、v2、…、vn。由連通性，必存在與v1相鄰的結點，不妨設它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結點，不妨設為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結點相鄰，得新邊en?1，由此可見G中至少有n－1條邊。

2（2）給定簡單無向圖G＝，且|V|＝m，|E|＝n。試證：若n≥Cm?1＋2，則G是哈密爾頓圖。

2證明 若n≥Cm。?1＋2，則2n≥m－3m＋6（1）

2若存在兩個不相鄰結點u、v使得d(u)＋d(v)＜m，則有2n＝

w?V?d(w)＜m＋(m－2)(m－3)＋m＝m－

23m＋6，與（1）矛盾。所以，對于G中任意兩個不相鄰結點u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密爾頓圖。離散數考試試題（B卷及答案）

一、（10分）使用將命題公式化為主范式的方法，證明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。證明：因為(P?Q)?(P∧Q)??(?P∨Q)∨(P∧Q)

?(P∧?Q)∨(P∧Q)(Q?P)∧(P∨Q)?(?Q∨P)∧(P∨Q)?(P∧?Q)∨(?Q∧Q)∨(P∧P)∨(P∧Q)?(P∧?Q)∨P

?(P∧?Q)∨(P∧(Q∨?Q))?(P∧?Q)∨(P∧Q)∨(P∧?Q)?(P∧?Q)∨(P∧Q)所以，(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。

二、（10分）證明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。

解 設A：A努力工作；B、C、D分別表示B、C、D愉快；則推理化形式為： A?B∨C，B??A，D??CA??D

(1)A 附加前提(2)A?B∨C P(3)B∨C T(1)(2)，I(4)B??A P(5)A??B

T(4)，E(6)?B T(1)(5)，I(7)C T(3)(6)，I(8)D??C P(9)?D T(7)(8)，I(10)A??D CP

三、（10分）證明?x?y(P(x)?Q(y))?(?xP(x)??yQ(y))。?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y))??x(?P(x)∨?yQ(y))??x?P(x)∨?yQ(y)???xP(x)∨?yQ(y)?(?xP(x)??yQ(y))

四、（10分）設A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}}

五、（15分）設X＝{1，2，3，4}，R是X上的二元關系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關系圖。(2)寫出R的關系矩陣。

(3)說明R是否是自反、反自反、對稱、傳遞的。解(1)R的關系圖如圖所示：(2)R的關系矩陣為：

?1??0M(R)??1??1?反自反的；由于矩陣不對稱，R不是對稱的；

經過計算可得

101110110??0? 0??0??(3)對于R的關系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是?1??0M(R2)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0??

六、（15分）設函數f：R×R?R×R，f定義為：f()＝。(1)證明f是單射。(2)證明f是滿射。(3)求逆函數f。

(4)求復合函數f?f和f?f。

證明(1)對任意的x，y，x1，y1∈R，若f()＝f()，則＝，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y1，故f是單射。

(2)對任意的∈R×R，令x＝－1－

1u?wu?wu?wu?wu?w，y＝，則f()＝<＋，－22222u?w>＝，所以f是滿射。2(3)f()＝<－1－1u?wu?w，>。22－1

－1(4)f?f()＝f(f())＝f()＝<

x?y?x?yx?y?(x?y)，>＝

444

55f?f()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）給定群，若對G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，3試證是Abel群。

證明 對G中任意元a和b。

因為a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。

于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。

由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。

八、（15分）（1）證明在n個結點的連通圖G中，至少有n－1條邊。

證明 不妨設G是無向連通圖（若G為有向圖，可略去邊的方向討論對應的無向圖）。

設G中結點為v1、v2、…、vn。由連通性，必存在與v1相鄰的結點，不妨設它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結點，不妨設為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結點相鄰，得新邊en?1，由此可見G中至少有n－1條邊。

（2）試給出|V|＝n，|E|＝(n－1)(n－2)的簡單無向圖G＝是不連通的例子。解 下圖滿足條件但不連通。

12344

333334

34333

4333

?133

?1?13

?122244 6

第三篇：離散數學復習題1

邏輯

1、給出的真值表

2、證明為永真式 謂詞量詞和推理

1、使用量詞和謂詞表達不存在這一事實

2、證明前提“在這個班上的某個學生沒有讀過書”和班上的每個學生都通過了第一門考試蘊含結論“通過考試的某個人沒有讀過書” 集合、函數、數列與求和

1、全集為，求集合A=的位串？它的補集的位串是什么？寫出集合A=的所有子集，寫出集合

2、從集合到集合能定義多少個函數？下面給出的函數其定義為：該函數是雙射嗎？是滿射嗎？該函數是否存在逆函數？如果存在請給出其逆函數。計數

1、計算機系統的美國用戶有一個6～8個字符構成的密碼，其中每個字符是一個大寫字母或數字，且每個密碼必須至少包含一個數字，問總共有多少個合適的密碼？

2、在30天的一個月里，某棒球隊一天至少打一場比賽，但最多打45場。證明一定有連續(xù)的若干天內這個球隊恰好打了14場比賽

3、證明n個元素的集合中允許重復的r組合數等于

4、按照字典順序生成整數1，2，3的所有排列（不允許重復），在362541后面按照字典順序的下一個最大排列是什么？找出在1000100111后面的下一個最大的二進制串。關系

1、求下面給出關系R的自反閉包、對稱閉包和傳遞閉包的0-1關系矩陣，其中

2、S是所有比特串的集合，關系定義為當s=t或者s和t的長度至少是3，且前3個比特相同時具有關系，例如0101，0011100101，但01010，0101101110。證明是S上的等價關系，由產生的S的等價類是那些集合？

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是極大的，那些元素是極小的？ 圖與樹

1、在下圖所示的圖中，從a 到d的長度為4的通路有幾條？該圖是否是Euler圖，是否是Hamilton圖，該圖的度序列是什么？該圖是否可平面，如果是請給出平面畫圖，該圖的點色數和邊色數等于多少？給出該圖的一個生成樹，2、求下面賦權圖從a到z的最短距離是多少？最短路徑是什么？（畫圖給出標號過程）

3、用哈夫曼編碼方法來編碼下列符號，這些符號具有下列頻率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,該編碼方法編碼一個字符的平均位數是多少？

4、下面樹的高度是多少？那些節(jié)點是內部節(jié)點，那些節(jié)點是葉子節(jié)點，該樹是否是3元正則樹？分別給出該樹節(jié)點的前序、中序、后序遍歷的節(jié)點訪問次序

第四篇：離散數學練習題1

1、下列句子是簡單命題的是（）

A)3是素數。B)2x+3<

5C)張三跟李四是同學嗎？D)我在說謊。

2、下列公式不是永真式的是（）．．

A)((p∧q))→p)∨rB)p→(p∨q∨r)

C)┓(q→r)∧rD)(p→q)→(┓q→┓p)

3、設命題公式G<=>┓(p→q)，H<=>p→(q →┓p)，則G與H的關系是()。

A)G<=>HB)H→GC)H => GD)G => H4、下列命題不為真的是（）．

A)Φ ? ΦB)Φ∈Φ

C){a,b}∈{a,b,c,{a,b}}}D){a,b}?{a,b,c,{a,b}}

5、1到300之間（包含1 和1000）不能被3、5和7整除的數有（）個。

13、下列運算在指定集合上不符合交換律的是（）。

A)復數C集合上的普通加法B)n階實矩陣上的乘法 C)集合S的冪集上的∪D)集合S的冪集上的?

14、下列集合對所給的二元運算封閉的是（）

A)正實數集合R+和。運算，其中。運算定義如下：?a,b∈R+，a。b=ab-a-b B)n∈Z+，nZ={nZ|z∈Z}，nZ關于普通的加法運算 C)S={2x-1|x∈Z+}關于普通的加法運算

D)S={x|x=2n, n∈Z+}，S關于普通的加法運算

15、設V=,其中*定義如下：?a，b∈Z, a*b=a+b-2 ,則能構成的代數系統是（）。

A)半群、獨異點、群B)半群、獨異點C)半群D)二元運算

上有○

A)138B)120C)68D)1246、設A, C, B, D為任意集合，以下命題一定為真的是（）

A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C

C)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得A ? A ×A7、設A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的關系，則R的性質是（）

A)既是對稱的也是反對稱的 B)既不是對稱的也不是反對稱的 C)是對稱的但不是反對稱的D)不是對稱的但是反對稱的8、設R是A上的關系，則R在A上是傳遞的當且僅當（）

則這4個運算中滿足冪等律的是（）

17、在上述四個運算中有單位元的是（）

18、在上述四個運算中有零元的是（）

19、與命題公式P?（Q?R）等值的公式是()

A)(P?Q)?RB)(P?Q)?RC)(P?Q)?RD)P?(Q?R)

20、下列集合都是N的子集，能夠構成代數系統V=的子代數的是（）

A)｛x| x∈N∧x與5互為素數｝B)｛x| x∈N∧x是30的因子｝ C){x| x∈N∧x是30的倍數}D){x|x=2k+1, k∈N }

二、填空題(1分/空，共20分。請將正確答案填在相應的橫線上。)

1、公式┓(p∨q)→p的成假賦值為00__,公式┓(q→p)∧p的成真賦值為。

2、設Ａ，Ｂ為任意命題公式，Ｃ為重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么Ａ<->Ｂ是重言式（重言式、矛盾式或可滿足式）。

3、f：N->N×N，f(x)=,A={5},B={<2,3>,<7,8>},則f(x)是A)IA ? RB)R=R-1C)R∩IA ?ΦD)R。R?R9、設A={1,2,3,4,5,6,7,8},R為A上的等價關系R={|x,y ∈ A ∧ x=y(mod 3)}

其中，x=y(mod 3)叫做x與y模3相等，即x除以3的余數與y除以3的余數相等。則1的等價類，即[1]，為（）

A){1,4,7}B){2,5,8}C){3,6}D){1,2,3,4,5,6,7,8}

10、當集合A=Φ且B≠Φ時，則BA結果為（）

A)ΦB){Φ} C){Φ, {Φ}}D)錯誤運算

11、函數f:R→R,f(x)= x2-2x+1,則f(x)是（）函數。

A)單射B)滿射C)雙射D)不是單射，也不是滿射

12、設X={a,b,c,d},Y={1,2,3}，f={,,}，則以下命題正確的是()

A)f是從X到Y的二元關系，但不是從X到Y的函數 B)f是從X到Y的函數，但不是滿射的，也不是單射的 C)f是從X到Y的滿射，但不是單射 D)f是從X到Y的雙射

雙射）函數，A在f下的像f(A)＝_{<5,6>}_，B在f下的完全原像f-1(B)=____。

4、已知公式A中含有3個命題變項p,q,r，并且它的成真賦值為000，011，110，則A的主合取范式為（用極大項表示）__M∧_M∧_M∧_M∧_M，主析取范式為（用極小項表示）

5、公式?x(F(x,y)→?yG(x,y,z))的前束范式為_

6、列出從集合A={1,2}到B={1}的所有二元關系。

7、設A為集合且∣A∣=n，則A共有nP(A)有n

8、設 f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 則復合函數

⑦ ?x(F(x)∧G(x)→H(x))前提引入 ⑧ F(a)∧G(a)→H(a)T ⑦UI⑨ F(a)∧G(a)T ③ ⑥合取(10)H(a)T ⑧ ⑨ 假言推理

f。g。h(x)=__，f。g。h(x)=_____。

9、含有n個命題變項的公式共有_____個不同的賦值，最多可以生成___個不同的真值表；n個命題變項共可產生___n_____個極小項（極大項）；含n個命題變項的所有有窮多個合式公式中，與它們等值的主析取范式（主合取范式）共有___2^2___種不同的情況。

10、已知集合A={?,{?}}，則A的冪集P(A)＝_____。

n

n

n

五、設A={1,2,3,4}，在A×A上定義二元關系R，?，∈A×A，R<=>u+y=x+v

(1)證明R是A×A上的等價關系

(2)確定由R引起的對A×A的劃分。(5分)

三、利用公式的主合取范式判斷下列公式是否等值。（5分）

p→(q→r)與?(p∧q)∨r p→(q→r)

<=>?p∨(?q∨r)<=>?p∨?q∨r <=>M6

?(p∧q)∨r

<=>(?p∨?q)∨r <=>?p∨?q)∨r <=>M6

(1)證明: ? ∈ A×A => x+y=y+x=> ∈ R∴R是自反的 ? ∈ A×A , R => x+v=y+u=> R∴R是對稱的 ? ,∈ A×A , R ∧ R=> x+v=y+u ∧ u+n=v+m

=> x+v+u+n=y+u+v+m => x+n=y+m => R ∧∴R是傳遞的(2)

解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}

四、符號化命題，并推理證明(給出每個符號的準確含義，及每一步推理的根據)。（5分）

每個科學工作者都是刻苦鉆研的。每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。華有為是科學工作者并且是聰明的，所以華有為在他的事業(yè)中將獲得成功。

六、A= {1,2,3,4,6,8,12}，R是A上的整除關系，請作出偏序集的哈斯圖，給出關系矩陣，并

求出A的極大元、極小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）

解:

首先符號化：M(x)：x是科學工作者；F(x)：x是刻苦鉆研的；G(x)：x是聰明的；H(x)：x

在事業(yè)中獲得成功；a：華有為。

前提： ?x(M(x)→F(x)），?x(F(x)∧G(x)→H(x)),M(a)∧ G(a)

結論：H(a)

證明：① M(a)∧ G(a)前提引入 ② M(a)T ①化簡規(guī)則 ③ G(a)T ①化簡規(guī)則 ④ ?x(M(x)→F(x)）前提引入 ⑤ M(a)→F(a)T ④

⑥ F(a)T ② ⑤ 假言推理

解:A的極大元為8、12,極小元為1，無最大元，最小元為1。

B的上界為12，下界為1，最小上界為12，最大下界為1。

七、在自然推理系統P中構造下面推理的證明。（5分）(1)前提：(p∨q)→(r∧s),(s∨t)→u

結論：p→u(2)前提：?x(F(x)→(G(a)∧ R(x)))，?x F(x).九、證明下列恒等式 A-(B∪C)=(A-B)∩(A-C)。（5分）證明：A-(B∪C)

結論： ?x(F(x)∧ R(x)).(1)證明：① p附加前提引入規(guī)則② p ∨ q①附加規(guī)則③(p ∨ q)→(r ∧ s)前提引入

④ r ∧ s②③ 假言推理⑤ s④化簡規(guī)則⑥ s ∨ t⑤附加規(guī)則⑦(s ∨ t)→ u前提引入

⑧ u⑥ ⑦假言推理

(2)證明：① ?x F(x)前提引入② F(b)① EI③ ?x(F(x)→(G(a)∧ R(x)))前提引入④ F(b)→(G(a)∧ R(b))③ UI

⑤ G(a)∧ R(b)② ④假言推理⑥ R(b)⑤化簡⑦ F(b)∧ R(b)②⑥合?、?x(F(x)∧ R(x))⑦EG

八、設有理數集合Q上的 * 運算定義如下：?a，b∈Q, a*b=a+b-ab。請指出該運算的性質，并求出其單位元、零元及所有可能的逆元。（5分）

解：(1)因為a*b=a+b-ab =b+a-ba=b*a，所以運算滿足交換律。

(2)因為(a*b)*c=(a+b-ab)*c= a+b-ab+c-(a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)= a+b+c-ab-bc-ac+abc故運算滿足結合律。

(3)任意x∈Q，因為x*x=x+x-xx=2x+x2≠x，故不滿足冪等律(4)因為對?a∈Q，有a*0=a+0-a0=a，所以0是單位元。(5)因為對?a∈Q，有a*1=a+1-a=1，所以1是零元。

(6)對?a∈Q，令a*x=a+x-ax=0，則有x=a/(a-1)。所以當a≠1時，其逆元為a=a/(a-1)，1沒有逆元。

1＝A∩～(B∪C)＝A∩～B∩～C = A∩A∩～B∩～C ＝(A∩～B)∩(A∩～C)=(A-B)∩(A-C)

十、設A,B為任意集合，證明：A?B<=>P(A)?P(B)。（5分）證明：先證明充分性（=>）

?X∈P(A)=> X?A=> X?B=> X∈P(B)再證明必要性（<=）

?x∈A=> {x}?A=> {x}∈P(A)=> {x}∈P(B)=> {x}?B=>x∈B 綜上所述，A?B<=>P(A)?P(B)

第五篇：大學離散數學復習試題

離散數學練習題目

一、選擇題

1．設A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是錯的。

A、??A； B、{6，7，8}?A； C、{{4，5}}?A； D、{1，2，3}?A。

2.已知集合A={a,b,c},B={b,c,e},則 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列語句中，不是命題的是____A_________ A.我說的這句話是真話； B.理發(fā)師說“我說的這句話是真話”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以這些煤不會燃燒；

4.下面___D______命題公式是重言式。

A.P?Q?R ； B.(P?R)?(P?Q)；C.(P?Q)?(Q?R)；

D、(P?(Q?R))?((P?Q)?(P?R))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．設L(x)：x是演員，J(x)：x是老師，A(x , y)：x欽佩y，命題“所有演員都欽佩某些老師”符號化為___D______。

A、?x(L(x)?A(x,y))； B、?x(L(x)??y(J(y)?A(x,y)))； C、?x?y(L(x)?J(y)?A(x,y))； D、?x?y(L(x)?J(y)?A(x,y))。7.關于謂詞公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯誤的是__B_____ A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）

B．z是該謂詞公式的約束變元

C．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變元 8． 設S?A?B，下列各式中____B___________是正確的。

A、domS?B ； B、domS?A； C、ranS?A； D、domS ? ranS = S。9．設集合X??，則空關系?X不具備的性質是____A________。

A、自反性； B、反自反性； C、對稱性； D、傳遞性。

10.集合A，R是A上的關系，如果R是等價關系，則R必須滿足的條件是__D___ A.R是自反的、對稱的 B.R是反自反的、對稱的、傳遞的 C.R是自反的、對稱的、不傳遞的 D.R是自反的，對稱的、傳遞的 11.集合A={a,b,c,d},B={1,2,3},則下列關系中__ACD______是函數

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} ????已知集合???????????? R?A,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},則頂點2的入度和出度分別是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.設完全圖Kn有n個結點(n≥2)，m條邊，當下面條件__C____滿足時，Kn中存在歐拉回路．

A．m為奇數 B．n為偶數 C．n為奇數 D．m為偶數 14.下面敘述正確的是____B______ A.二部圖K3,3是歐拉圖 B.二部圖是平面圖

K3,3是哈密爾頓圖

C.二部圖 K3,32

D.二部圖K3,3是既不是歐拉圖也不哈密爾頓圖

15.已知某平面圖的頂點數是12，邊數是14，則該平面圖有__D___個面 A.3 B.2 C.5 D.4 16．設G是n個結點、m條邊和r個面的連通平面圖，則m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面幾種代數結構中，不是群的是___D____ A. B. C. D.(這里Z，Q，R，N分別表示整數集、有理數集、實數集、自然數集，+普通加法)

二、問答題

1.在程序設計過程中，有如下形式的判斷語句： if(a>=0)if(b>1)if(c<0)cout<

請將這段程序化簡，并說明化簡的理由。解：簡化的程序：

if(a>=0 && b>1 && c<0)cout<

設置命題變量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))經過等值演算可得，A與下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①證明R是偏序關系。

②寫出偏序集（A，R）的極小元、極大元；最小元、最大元 ③寫出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根據整除性質可知，R滿足自反性，反對稱性，傳遞性。所以R是A上的偏序關系。

②偏序集（A，R）的極小元：1，極大元：5, 6，7，8，9 最小元：1； 最大元：無

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m個男孩子，n個女孩排成一排，任何兩個女孩不相鄰，有多少種排法？

(n<=m)插空問題

(2)如果排成一個園環(huán)，又有多少種排法？

解：(1)考慮5個男孩，5個女孩的情況

男孩的安排方法： _B_B_B_B_B_ 排列總數P(5,5)女孩的安排方法：6個位置安排5個女孩，排列中數 P(6,5)所以：總的排列方法數是 m!*p(m+1,n)

(2)考慮男孩的圓排列情況，結果是(m-1)!*p(m,n)

4.某商家有三種品牌的足球，每種品牌的足球庫存數量不少于10只，如果我想買5只足球，有多少種買法？如果每種品牌的足球最少買一只，有多少種買法？

解：①這是一個多重集的組合問題

類別數是k=3，選取的元素個數是 r=5 多重集組合數的計算公式是 N?所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由選取的球只有2個 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(r?k?1)!?C(k?r?1,r)

r!(k?1)!

5．某軟件公司將職工分為三種崗位。該公司65人，有些職工（例如項目管理人員、設計人員）可能從事不止一個崗位的工作。每個職工至少被分在一個崗位?，F在軟件設計崗位（崗位A）（包括需求分析、概要設計和詳細設計等工作）的人數是15人，代碼編寫崗位（崗位B）的人數是32人，軟件測試崗位（崗位C）的人數是28人，同時參加崗位A和崗位B的有12人, 同時參加崗位B和崗位C的有8人, 同時參加崗位A和崗位C組的有3人，問，三個崗位參加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 設S表示全班同學總人數，則 |S|=65 求：|A∩B∩C|=？

根據容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因為每個同學至少參加一個小組，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三個小組都參加的人數是13人

6.證明組合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

說明：也可以直接利用組合演算公式進行演算 7.求1228的個位數是多少? 解：1228的個位數就是1228 mod 10的余數1228mod10?(12mod10)28mod10?24*7mod10?(27mod10)4mod10?8mod10?64

8.已知圖G有10條邊, 4個3度頂點, 其余頂點的度數均小于2, 問G至少有多少個頂點?

解：由握手定理∑d(v)=2m=20，度數為3的頂點有3個占去12度，還有8度由其余頂點占有，而由題意，其余頂點的度數可為0，1，當均為1時所用頂點數最少，所以應有8個頂點占有此8度，即G中至少有8+4=12個頂點。

9刑偵人員審一件盜竊案時，已經掌握的線索如下：（1）甲或乙盜竊了電腦。

（2）若甲盜竊了電腦，則作案時間不能發(fā)生在午夜前。（3）若乙證詞正確，則在午夜時屋里燈光未滅。（4）若乙證詞不正確，則作案時間發(fā)生在午夜前。（5）午夜時屋里燈光滅了。

請通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細的推理步驟）解 設p： 甲盜竊了電腦，q： 乙盜竊了電腦，r： 作案時間發(fā)生在午夜前，s： 乙證詞正確，t：午夜時屋里燈光滅了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的時間T與數據規(guī)模n的遞推關系如下，求出T與n的顯示關系表達式

?T(n)?T(n?1)?n?1 ??T(1)?0

解：

??T(n)?T(n?1)?n?1 ??T(n?2)?n?2?n?1???T(n?3)?n?3?n?2?n?1 ?????T(n?k)?n?k???n?2?n?1??T(n?k)?kn-(1?2??k)??k(k?1)??T(n?k)?kn?2?令n-k=1，那么 k=n-1，所以：

n(n?1)n(n?1)n(n?1)? T(n)?T(1)??0???222?答：T與n的顯示關系是：T(n)?

11.解下列一階同余方程組

n(n?1)2x?1(mod 3)x?2(mod 4)x?3(mod 5)解：已知a1?1,a2?2,a3?3;m1?3,m2?4,m3?5 方程組的齊次通解是：x?k?Lcm(1,2,3)?6k 60k 根據中國剩余定理，特解是：

x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)M1?m2m3?20,M2?m1m3?15,M3?m1m2?12 ?1?1?1M1mod m1是下列同余方程的解

3)，解得：x=2，即M1?2 M1x?1(mod m1)即20x?1(mod?1?1同理可解得：M2?3，M3?3 ?1?1 7

x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)mod m?（1?20?2?2?15?3?3?12?3）mod 60?1?1?1所以：?(40?90?108)mod 60?238mod 6058

同余方程組的解是 x?x?x0?6k?58 60k

12.假設需要加密的明文數據是a=8,選取兩個素數p=7,q=19,使用RSA算法： ① 計算出密鑰參數

② 利用加密算法計算出密文c ③ 利用解密算法根據密文c反求出明文a 解：① 取 p=7,q=19;計算 n=p*q=7*19=133 計算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 選取較小的數w,使w與108互質, 5是最小的,于是w=5 計算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余數為1, 于是算出d=65 至此加密、解密參數計算完成：

公鑰w=5,n=133.私鑰d=65,n=133.② 加密

c?mwmodn?85mod133?((82mod133)*(83mod133))mod133

?(64*113)mod133?50③ 解密

a?cdmodn?5065mod133

a?A0?A6 其中，A0?50, Ai?(Ai?1)2

根據上述遞推公式可以計算出：A1?502mod133?106,A2?1062mod133?64

A3?642mod133?106，??, A6?1062mod133?64 a?A0?A6?(50*64)mod133?8

解密后的明文與原來的明文是相等的，所以算法正確。

13.設A={1，2，3，4，6，9，12，24},R定義為R?{(a,b)|a?b(mod 3)}，（1）證明R是一個等價關系；（2）寫出A的商集；

14.基于字典序的組合生成算法

問題說明：假設我們需要從5個元素中選取3個的所有組合，已知組合個數為 C（５，３）＝１０，按字典序，其具體組合為： 123,124,125,134,135,145,234,235,245,345 所謂按字典序生成組合，就是已知當前的組合（例如135），求下一個組合（例如，145）。下面給出算法的函數頭：

//數組s[]:函數運行前，保存當前的組合，函數結束后，是新生成的下一個組合 //n,r:表示從n個元素中選取r個元素的組合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某單位要從A,B,C三人選派若干人出國考察, 需滿足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案? 9