離散數(shù)學(xué)期末考試試題有幾套帶答案

1、離散試卷及答案 離散試卷及答案第 1 頁(yè) 共 22 頁(yè)離散數(shù)學(xué)試題(A 卷及答案）一、證明題（ 一、證明題（10 10 分） 分）1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R證明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R)?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R?(?(P∨Q)∨(P∨Q))∧R?T∧R(置換)?R2)?x(A(x)?B(x)

2、)? ?xA(x)??xB(x)證明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)??xB(x)二、求命題公式 二、求命題公式(P (P∨(Q (Q∧R)) R))?(P (P∧Q∧R) R)的主析取范式和主合取范式（ 的主析取范式和主合取范式（10 10分） 分）證明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))?（?

3、P∧(?Q∨?R)）∨(P∧Q∧R)?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R)?m0∨m1∨m2∨m7?M3∨M4∨M5∨M6三、推理證明題（ 三、推理證明題（10 10 分） 分）1） C∨D, D, (C (C∨D) D)? ?E, E, ?E?(A (A∧?B), B), (A (A∧?B) B)?(R (R∨S) S

4、)?R∨S證明：(1) (C∨D)??E (2) ?E?(A∧?B) (3) (C∨D)?(A∧?B)(4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D (7) R∨S離散試卷及答案 離散試卷及答案第 3 頁(yè) 共 22 頁(yè)（gf）-1：C→A。同理可推 f-1g-1：C→A 是雙射。因?yàn)椤蔲-1g-1?存在 z（∈g-1?∈f-1）?存在 z（∈f?∈g）?∈gf?∈（gf）-1,所以（gf）-1=f-1

5、g-1。R {1,2}={,}，S[{1,2}]={1,4}。八、 八、 （15 15 分） 分）設(shè) *>是半群，對(duì) 是半群，對(duì) A 中任意元 中任意元 a 和 b，如 ，如 a≠b 必有 必有 a*b≠b*a，證明： ，證明：(1) (1)對(duì) A 中每個(gè)元 中每個(gè)元 a，有 ，有 a*a＝a。(2) (2)對(duì) A 中任意元 中任意元 a 和 b，有 ，有 a*b*a＝a。(3) (3)對(duì) A 中任意元 中任意元 a、b 和 c，

6、有 ，有 a*b*c＝a*c。證明 由題意可知，若 a*b＝b*a，則必有 a＝b。(1)由(a*a)*a＝a*(a*a)，所以 a*a＝a。(2)由 a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有 a*b*c＝a*c。

7、九、 九、給定簡(jiǎn)單無(wú)向圖 給定簡(jiǎn)單無(wú)向圖 G＝，且 ，且|V|＝m，|E|＝n。試證：若 。試證：若 n≥ 21 ? m C＋2，則 ，則 G 是哈密爾頓圖 是哈密爾頓圖 證明 證明 若 n≥ ＋2，則 2n≥m2－3m＋6 （1） 。 21 ? m C若存在兩個(gè)不相鄰結(jié)點(diǎn) 、 使得 d( )＋d( )＜m，則有 2n＝ ＜m＋ u v u v ??V ww d ) ((m－2)(m－3)＋m＝m2－3m＋6，與（1）矛盾。所以，對(duì)