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

1、離散試卷及答案離散試卷及答案第1頁共22頁離散數(shù)學(xué)試題(A卷及答案）一、證明題（一、證明題（1010分）分）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))??xA(x)??xB

2、(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)的主析取范式和主合取范式（的主析取范式和主合取范式（1010分）分）證明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))?（?P∧(?Q∨?R)）∨(P∧Q∧R)?(?P∧

3、?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三、推理證明題（三、推理證明題（1010分）分）1）C∨DD(C(C∨D)D)??EE?E?(A(A∧?B)B)(A(A∧?B)B)?(R(R∨S)S)?R∨S證明：(1)(C∨D)??E(2)?E?(A∧?B)(3)(C∨D)?(A∧?B)(4)

4、(A∧?B)?(R∨S)(5)(C∨D)?(R∨S)(6)C∨D(7)R∨S離散試卷及答案離散試卷及答案第3頁共22頁（gf）1：C→A。同理可推f1g1：C→A是雙射。因?yàn)椤蔲1g1?存在z（∈g1?∈f1）?存在z（∈f?∈g）?∈gf?∈（gf）1所以（gf）1=f1g1。R12=，S[12]=14。八、八、（1515分）分）設(shè)是半群，對(duì)是半群，對(duì)A中任意元中任意元a和b，如，如a≠b必有必有ab≠ba，證明：，證明：(1)(1)

5、對(duì)A中每個(gè)元中每個(gè)元a，有，有aa＝a。(2)(2)對(duì)A中任意元中任意元a和b，有，有aba＝a。(3)(3)對(duì)A中任意元中任意元a、b和c，有，有abc＝ac。證明由題意可知，若ab＝ba，則必有a＝b。(1)由(aa)a＝a(aa)，所以aa＝a。(2)由a(aba)＝(aa)(ba)＝ab(aa)＝(aba)a，所以有aba＝a。(3)由(ac)(abc)＝(aca)(bc)＝a(bc)＝(ab)c＝(ab)(cac)＝(abc)

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