第一篇：離散數(shù)學(xué)考試試題(A、B卷及答案)test7
離散數(shù)學(xué)考試試題（A卷及答案）
一、（10分）證明?(A∨B)??(P∨Q)，P，(B?A)∨?PA。
證明：(1)?(A∨B)??(P∨Q)
P(2)(P∨Q)?(A∨B)
T(1)，E(3)P
P(4)A∨B
T(2)(3)，I(5)(B?A)∨?P
P(6)B?A
T(3)(5)，I(7)A∨?B
T(6)，E(8)(A∨B)∧(A∨?B)
T(4)(7)，I(9)A∧(B∨?B)
T(8)，E(10)A
T(9)，E
二、（10分）甲、乙、丙、丁4個人有且僅有2個人參加圍棋優(yōu)勝比賽。關(guān)于誰參加競賽，下列4種判斷都是正確的：
(1)甲和乙只有一人參加；(2)丙參加，丁必參加；(3)乙或丁至多參加一人；(4)丁不參加，甲也不會參加。請推出哪兩個人參加了圍棋比賽。
解
符號化命題，設(shè)A：甲參加了比賽；B：乙參加了比賽；C：丙參加了比賽；D：丁參加了比賽。依題意有，(1)甲和乙只有一人參加，符號化為A?B?(?A∧B)∨(A∧?B)；(2)丙參加，丁必參加，符號化為C?D；(3)乙或丁至多參加一人，符號化為?(B∧D)；(4)丁不參加，甲也不會參加，符號化為?D??A。所以原命題為：(A?B)∧(C?D)∧(?(B∧D))∧(?D??A)?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A)?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A))?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T
但依據(jù)題意條件，有且僅有兩人參加競賽，故?A∧B∧?C∧?D為F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁參加了圍棋比賽。
三、（10分）指出下列推理中，在哪些步驟上有錯誤？為什么？給出正確的推理形式。(1)?x(P(x)?Q(x))
P(2)P(y)?Q(y)
T(1)，US(3)?xP(x)
P(4)P(y)
T(3)，ES(5)Q(y)
T(2)(4)，I(6)?xQ(x)
T(5)，EG 解
(4)中ES錯，因為對存在量詞限制的變元x引用ES規(guī)則，只能將x換成某個個體常元c，而不能將其改為自由變元。所以應(yīng)將(4)中P(y)改為P(c)，c為個體常元。
正確的推理過程為：
(1)?xP(x)
P(2)P(c)
T(1)，ES
(3)?x(P(x)?Q(x))
P(4)P(c)?Q(c)
T(3)，US(5)Q(c)
T(2)(4)，I(6)?xQ(x)
T(5)，EG
四、（10分）設(shè)A＝{a，b，c}，試給出A上的一個二元關(guān)系R，使其同時不滿足自反性、反自反性、對稱性、反對稱性和傳遞性。
解
設(shè)R＝{，，，}，則 因為?R，R不自反； 因為∈R，R不反自反；
因為∈R，
因為∈R，∈R，但?R，R不傳遞。
五、（15分）設(shè)函數(shù)g：A→B，f：B→C，(1)若f?g是滿射，則f是滿射。(2)若f?g是單射，則g是單射。
證明
因為g：A→B，f：B→C，由定理5.5知，f?g為A到C的函數(shù)。
(1)對任意的z∈C，因f?g是滿射，則存在x∈A使f?g(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是滿射。
(2)對任意的x1、x2∈A，若x1≠x2，則由f?g是單射得f?g(x1)≠f?g(x2)，于是f(g(x1))≠f(g(x2))，必有g(shù)(x1)≠g(x2)。所以，g是單射。
六、（15分）設(shè)R是集合A上的一個具有傳遞和自反性質(zhì)的關(guān)系，T是A上的關(guān)系，使得?T??R且?R，證明T是一個等價關(guān)系。
證明
因R自反，任意a∈A，有
若∈T，即∈R且
所以，T是A上的等價關(guān)系。
七、（15分）若
必要性：對任意的a、b∈H，由
－
－充分性：由H非空，必存在a∈H。于是e＝a*a1∈H。
－任取a∈H，由e、a∈H得a1＝e*a1∈H。
－
－對于任意的a、b∈H，有a*b＝a*(b1)1∈H，即a*b∈H。
－
－又因為H是G非空子集，所以*在H上滿足結(jié)合律。綜上可知，
八、（15分）(1)若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定是連通的。(2)若有向圖G中只有兩個奇數(shù)度結(jié)點，它們一個可達另一個結(jié)點或互相可達嗎？
證明
(1)設(shè)無向圖G中只有兩個奇數(shù)度結(jié)點u和v。從u開始構(gòu)造一條回路，即從u出發(fā)經(jīng)關(guān)聯(lián)結(jié)點u的邊e1到達結(jié)點u1，若d(u1)為偶數(shù)，則必可由u1再經(jīng)關(guān)聯(lián)u1的邊e2到達結(jié)點u2，如此繼續(xù)下去，每條邊只取一次，直到另一個奇數(shù)度結(jié)點為止，由于圖G中只有兩個奇數(shù)度結(jié)點，故該結(jié)點或是u或是v。如果是v，那么從u到v的一條路就構(gòu)造好了。如果仍是u，該回路上每個結(jié)點都關(guān)聯(lián)偶數(shù)條邊，而d(u)是奇數(shù)，所以至少還有一條邊關(guān)聯(lián)結(jié)點u的邊不在該回路上。繼續(xù)從u出發(fā)，沿著該邊到達另一個結(jié)點u1?，依次下去直到另一個奇數(shù)度結(jié)點停下。這樣經(jīng)過有限次后必可到達結(jié)點v，這就是一條從u到v的路。
(2)若有向圖G中只有兩個奇數(shù)度結(jié)點，它們一個可達另一個結(jié)點或互相可達不一定成立。下面有向圖中，只有兩個奇數(shù)度結(jié)點u和v，u和v之間都不可達。
uwv離散數(shù)學(xué)考試試題（B卷及答案）
一、（15分）設(shè)計一盞電燈的開關(guān)電路，要求受3個開關(guān)A、B、C的控制：當(dāng)且僅當(dāng)A和C同時關(guān)閉或B和C同時關(guān)閉時燈亮。設(shè)F表示燈亮。
(1)寫出F在全功能聯(lián)結(jié)詞組{?}中的命題公式。(2)寫出F的主析取范式與主合取范式。
解
(1)設(shè)A：開關(guān)A關(guān)閉；B：開關(guān)B關(guān)閉；C：開關(guān)C關(guān)閉；F＝(A∧C)∨(B∧C)。在全功能聯(lián)結(jié)詞組{?}中：
?A??(A∧A)?A?A A∧C???(A∧C)??(A?C)?(A?C)?(A?C)
A∨B??(?A∧?B)??((A?A)∧(B?B))?(A?A)?(B?B)所以
F?((A?C)?(A?C))∨((B?C)?(B?C))?(((A?C)?(A?C))?((A?C)?(A?C)))?(((B?C)?(B?C))?((B?C)?(B?C)))(2)F?(A∧C)∨(B∧C)
?(A∧(B∨?B)∧C)∨((A∨?A)∧B∧C)?(A∧B∧C)∨(A∧?B∧C)∨(A∧B∧C)∨(?A∧B∧C)?m3∨m5∨m7
主析取范式 ?M0∧M1∧M2∧M4∧M6
主合取范式
二、（10分）判斷下列公式是否是永真式？(1)(?xA(x)??xB(x))??x(A(x)?B(x))。(2)(?xA(x)??xB(x))??x(A(x)?B(x)))。解
(1)(?xA(x)??xB(x))??x(A(x)?B(x))?(??xA(x)∨?xB(x))??x(A(x)?B(x))??(??xA(x)∨?xB(x))∨?x(?A(x)∨B(x))?(?xA(x)∧??xB(x))∨?x?A(x)∨?xB(x)?(?xA(x)∨?x?A(x)∨?xB(x))∧(??xB(x)∨?x?A(x)∨?xB(x))??x(A(x)∨?A(x))∨?xB(x)?T
所以，(?xA(x)??xB(x))??x(A(x)?B(x))為永真式。
(2)設(shè)論域為{1，2}，令A(yù)(1)＝T；A(2)＝F；B(1)＝F；B(2)＝T。
則?xA(x)為假，?xB(x)也為假，從而?xA(x)??xB(x)為真；而由于A(1)?B(1)為假，所以?x(A(x)?B(x))也為假，因此公式(?xA(x)??xB(x))??x(A(x)?B(x))為假。該公式不是永真式。
三、（15分）設(shè)X為集合，A＝P(X)－{?}－{X}且A≠?，若|X|＝n，問(1)偏序集是否有最大元？(2)偏序集是否有最小元？
(3)偏序集中極大元和極小元的一般形式是什么？并說明理由。解
偏序集
考察P(X)的哈斯圖，最底層的頂點是空集，記作第0層，由底向上，第一層是單元集，第二層是二元集，…，由|X|＝n，則第n－1層是X的n－1元子集，第n層是X。偏序集與偏序集 相比，恰好缺少第0層和第n層。因此的極小元就是X的所有單元集，即{x}，x∈X；而極大元恰好是比X少一個元素，即X－{x}，x∈X。 四、（10分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} －R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，i?1?<5，5>}。 五、（10分）設(shè)函數(shù)g：A→B，f：B→C，(1)若f?g是滿射，則f是滿射。(2)若f?g是單射，則g是單射。 證明 因為g：A→B，f：B→C，由定理5.5知，f?g為A到C的函數(shù)。 (1)對任意的z∈C，因f?g是滿射，則存在x∈A使f?g(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是滿射。 (2)對任意的x1、x2∈A，若x1≠x2，則由f?g是單射得f?g(x1)≠f?g(x2)，于是f(g(x1))≠f(g(x2))，必有g(shù)(x1)≠g(x2)。所以，g是單射。 六、（10分）有幺元且滿足消去律的有限半群一定是群。 證明 設(shè) 考慮a，a2，…，ak，…。因為G只有有限個元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。 于是，當(dāng)m＝1時，a＝e，而e是可逆的；當(dāng)m＞1時，a*am-1＝am-1*a＝e。從而a是可逆的，其逆元是am-1。總之，a是可逆的。 七、（20分）有向圖G如圖所示，試求：(1)求G的鄰接矩陣A。(2)求出A2、A3和A4，v1到v4長度為1、2、3和4的路有多少？ (3)求出ATA和AAT，說明ATA和AAT中的第(2，2)元素和第(2，3)元素的意義。(4)求出可達矩陣P。(5)求出強分圖。 解 (1)求G的鄰接矩陣為： ?0??0A??0??0?101??011? 101??100??(2)由于 ?0??0A2??0??0?111??02??201??0A3???02111???02011???12??03??22??0A4???1203???0101???23??13? 23??22??所以v1到v4長度為1、2、3和4的路的個數(shù)分別為1、1、2、3。(3)由于 ?0??0TAA??0??0?000??21??312??12TAA? ?21011????10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素為3，表明那些邊以v2為終結(jié)點且具有不同始結(jié)點的數(shù)目為3，其第(2，3)元素為0，表明那些邊既以v2為終結(jié)點又以v3為終結(jié)點，并且具有相同始結(jié)點的數(shù)目為0。AAT中的第(2，2)元素為2，表明那些邊以v2為始結(jié)點且具有不同終結(jié)點的數(shù)目為2，其第(2，3)元素為1，表明那些邊既以v2為始結(jié)點又以v3為始結(jié)點，并且具有相同終結(jié)點的數(shù)目為1。 ?0??0(4)因為B4?A?A2?A3?A4??0??0??0??0以求可達矩陣為P??0??0?111??111?。 111??111??101??0??011??0+ 101??0???100???0111??0 ?? 201??0 + 111??0 ?? ?011???0212??03??122??04+ 212??03???201???0123??13??23??22???0 ??0?0??0?741? ? 747?，所 747? ? 434???0??0(5)因為P?PT??0??0?111??0??111??1∧?1111????1111???000??0??111??0＝?0111????0111???000??111?，所以{v1}，{v2，v3，v4}構(gòu)成G的強分圖。 111??111?? 6 離散數(shù)學(xué)考試試題(A卷及答案） 一、證明題（10分） 1)(P∧Q∧A?C)∧(A?P∨Q∨C)?(A∧(P?Q))?C。P<->Q=(p->Q)合取（Q->p）證明:(P∧Q∧A?C)∧(A?P∨Q∨C) ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律 ??((P∧Q∧A)∨(A∧?P∧?Q))∨C ??(A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??(A∧(P?Q))∨C ?(A∧(P?Q))?C 2)?(P?Q)? ?P??Q。 證明：?(P?Q)??(?(P∧Q))??(?P∨?Q))??P??Q。 二、分別用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式與主合取范式，并寫出其相應(yīng)的成真賦值和成假賦值（15分）。 主析取范式與析取范式的區(qū)別：主析取范式里每個括號里都必須有全部的變元。主析取范式可由析取范式經(jīng)等值演算法算得。 證明： 公式法：因為(P?(Q∨R))∧(?P∨(Q?R)) ?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R)) ?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律 ?(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P∨R∨?R) ?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) ?M4∧M5∧M6使（非P析取Q析取R）為0所賦真值，即100，二進制 為 4?m0∨m1∨m2∨m3∨m7 所以，公式(P?(Q∨R))∧(?P∨(Q?R))為可滿足式，其相應(yīng)的成真賦值為000、001、010、011、111：成假賦值為：100、101、110。 真值表法： 為000、001、010、011、111：成假賦值為：100、101、110。 三、推理證明題（10分） 1）?P∨Q，?Q∨R，R?SP?S。 證明： (1)P附加前提(2)?P∨QP (3)QT(1)(2)，I（析取三段論）(4)?Q∨RP (5)RT(3)(4)，I（析取三段論）(6)R?SP (7)ST(5)(6)，I（假言推理）(8)P?SCP 2)?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 證明（1）?xP(x)(2)P(a) (3)?x(P(x)?Q(y)∧R(x))(4)P(a)?Q(y)∧R(a)(5)Q(y)∧R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)∧R(a)(10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 五、已知A、B、C是三個集合，證明(A∪B)－C＝(A－C)∪(B－C)（10分） 證明：因為 x∈(A∪B)－C?x∈(A∪B)－C ?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C ?(x∈A∧x?C)∨(x∈B∧x?C)?x∈(A－C)∨x∈(B－C)?x∈(A－C)∪(B－C) 所以，(A∪B)－C＝(A－C)∪(B－C)。 八、證明整數(shù)集I上的模m同余關(guān)系R={ 2）?x,y∈I，若xRy，則x?y(mod m)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以y?x(mod m)，即yRx。 3）?x,y,z∈I，若xRy，yRz，則（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。 九、若f:A→B和g:B→C是雙射，則（gf）-1=f-1g-1（10分）。 證明： 因為f、g是雙射，所以gf：A→C是雙射，所以gf有逆函數(shù)（gf）：C→A。同理可推f-1g-1：C→A是雙射。 因為 1離散數(shù)學(xué)考試試題(B卷及答案） 一、證明題（10分） 1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T 證明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ?((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ?((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(等冪律)?T(代入) 2)?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)) 二、求命題公式(?P?Q)?(P∨?Q)的主析取范式和主合取范式（10分） 解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q) ??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q)?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q) ?M1析取要使之為假，即賦真值001，即M1 ?m0∨m2∨m3使之為真 三、推理證明題（10分） 1)(P?(Q?S))∧(?R∨P)∧Q?R?S 證明：(1)R(2)?R∨P(3)P p T（1）（2）析取三段論 p T（3）（4）I假言推理 P T（5）（6）I假言推理 CP (4)P?(Q?S)(5)Q?S(6)Q(7)S (8)R?S 2)?x(A(x)??yB(y))，?x(B(x)??yC(y))?xA(x)??yC(y)。 證明：(1)?x(A(x)??yB(y))P(2)A(a)??yB(y)T(1)ES(3)?x(B(x)??yC(y))P (4)?x(B(x)?C(c))T(3)ES(5)B(b)?C(c)T(4）US(6)A(a)?B(b)T(2)US (7)A(a)?C(c)T(5)(6)I假言三段論(8)?xA(x)?C(c)T(7)UG(9)?xA(x)??yC(y)T(8)EG 四、只要今天天氣不好，就一定有考生不能提前進入考場，當(dāng)且僅當(dāng)所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好（15分）。 解 ： 設(shè)P：今天天氣好，Q：考試準時進行，A(e)：e提前進入考場，個體域：考生的集 合，則命題可符號化為：?P??x?A(x)，?xA(x)?QQ?P。(1)?P??x?A(x)P(2)?P???xA(x)T(1)E(3)?xA(x)?PT(2)E(4)?xA(x)?QP(5)(?xA(x)?Q)∧(Q??xA(x))T(4)E(6)Q??xA(x)T(5)I(7)Q?PT(6)(3)I 五、已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C)（10分） 證明： ∵ x? A∩（B∪C）? x? A∧x?（B∪C）? x? A∧（x?B∨x?C）?（x? A∧ x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C? x?（A∩B）∪（A∩C）∴A ∩（B∪C）=（A∩B）∪（A∩C） 六、A={ x1,x2,x3 }，B={ y1,y2}，R={ 七、設(shè)R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它們及R的關(guān)系圖（15分）。 r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3><5,5>}（自反閉包） s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}（對稱閉包）t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}（傳遞 閉包） 九、設(shè)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－ 1、g－1和h－1（10分）。 解因IA恒等函數(shù)，由h?g?f＝IA可得f是單射，h是滿射；因IB恒等函數(shù)，由f?h?g＝IB可得g是單射，f是滿射；因IC恒等函數(shù)，由g?f?h＝IC可得h是單射，g是滿射。從而f、g、h均為雙射。 由h?g?f＝IA，得f－1＝h?g；由f?h?g＝IB，得g－1＝f?h；由g?f?h＝IC，得h－1＝g?f。 離散數(shù)學(xué)考試試題（A卷及答案） 一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？ 1)((P?Q)∧Q)?((Q∨R)∧Q)2)?((Q?P)∨?P)∧(P∨R)3)((?P∨Q)?R)?((P∧Q)∨R)解：1)永真式；2）永假式；3)可滿足式。 二、（8分）個體域為{1，2}，求?x?y（x+y=4）的真值。 解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4）） ?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））?（0∨0）∧（0∨1）?1∧1?0 三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元關(guān)系數(shù)是多少？A到B的函數(shù)數(shù)是多少？ 解：因為|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元關(guān)系有2mn個。因為|BA|=|B||A|=mn，所以A到B的函數(shù)mn個。 四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。 解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>} 五、(10分)75個兒童到公園游樂場，他們在那里可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次的費用是0.5元，公園游樂場總共收入70元，求有多少兒童沒有乘坐過其中任何一種。 解 設(shè)A、B、C分別表示騎旋轉(zhuǎn)木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。 由容斥原理，得 |A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以 |A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 沒有乘坐過其中任何一種的兒童共10人。 六、（12分）已知R和S是非空集合A上的等價關(guān)系，試證：1）R∩S是A上的等價關(guān)系；2）對a∈A，[a]R∩S=[a]R∩[a]S。 解：?x∈A，因為R和S是自反關(guān)系，所以 ?x、y∈A，若 總之R∩S是等價關(guān)系。 2）因為x∈[a]R∩S? 七（10分）設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且? 證明：1）先證h是滿射。 ? 2）再證h是單射。 ? 八、（12分） 證明：1）?a,b∈G，a?b=a*u-1*b∈G，運算是封閉的。 2）?a,b,c∈G，（a?b）?c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a?（b?c），運算是可結(jié)合的。3）?a∈G，設(shè)E為?的單位元，則a?E=a*u-1*E=a，得E=u，存在單位元。 4）?a∈G，a?x=a*u-1*x=E，x=u*a-1*u，則x?a=u*a-1*u*u-1*a=u=E，每個元素都有逆元。所以 九、（10分）已知：D= 解：D的鄰接距陣A和可達距陣P如下： A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 十、（10分）求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹及其權(quán)。 解：最優(yōu)二叉樹為 權(quán)＝148 離散數(shù)學(xué)考試試題（B卷及答案） 一、（10分）求命題公式?(P∧Q)??(?P?R)的主合取范式。 解：?(P∧Q)??(?P?R)?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(P∧Q)）?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)）?(P∧Q)∨(?P∧?R)?(P∨?R)∧（Q∨?P）∧（Q∨?R） ?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R）?M1∧M3∧M4∧M5 二、（8分）敘述并證明蘇格拉底三段論 解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：F（x）：x是一個人。G（x）：x要死的。A：蘇格拉底。命題符號化為?x（F（x）?G（x）），F(xiàn)（a）?G（a）證明： （1）?x(F(x)?G(x))P（2）F(a)?G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I 三、（8分）已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C)證明：∵x? A∩（B∪C）? x? A∧x?（B∪C） ? x? A∧（x?B∨x?C） ?（x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C ? x?（A∩B）∪（A∩C） ∴A∩（B∪C）=（A∩B）∪（A∩C） 四、（10分）已知R和S是非空集合A上的等價關(guān)系，試證：1）R∩S是A上的等價關(guān)系；2）對a∈A，[a]R∩S=[a]R∩[a]S。 解：?x∈A，因為R和S是自反關(guān)系，所以 ?x、y∈A，若 ?x、y、z∈A，若 總之R∩S是等價關(guān)系。 2）因為x∈[a]R∩S? 五、(10分)設(shè)A＝{a，b，c，d}，R是A上的二元關(guān)系，且R＝{ 解 r(R)＝R∪IA＝{ t(R)＝?R＝{ 4232- 1六、(15分)設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且? 證明：1）先證h是滿射。 ? 2）再證h是單射。 ? 綜合1）和2），h是雙射。 七、(12分)設(shè) 證明：? ?a,b∈H有b∈H，所以a*b∈H。??a∈H，則e=a*a∈H-1- 1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H?G且H≠?,∴*在H上滿足結(jié)合律 ∴ 八、（10分）設(shè)G= 解：設(shè)G的每個結(jié)點的度數(shù)都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖- 1-1 -1-1-1的|E|≤3|V|-6矛盾，所以G至少有一個結(jié)點的度數(shù)小于等于5。九.G= （1）G是否為阿貝爾群？ （2）找出G的單位元；（3）找出G的冪等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿貝爾群 （2）因為a*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a（3）因為a*a=a 所以G的冪等元是a（4）因為b*c=c*b=a，所以b的逆元是c且c的逆元是b 十、(10分)求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹及其權(quán)。 解：最優(yōu)二叉樹為 權(quán)＝148 5 第一部分 簡單命題符號化，求主析取范式，判斷公式類型（重言式，矛盾式，可滿足式）量詞消去規(guī)則。命題邏輯推理規(guī)則 帶全稱量詞和存在量詞的命題邏輯推理的構(gòu)造和證明 第二部分 集合基本運算，文氏圖 有序?qū)Φ幕局R，笛卡兒積，特征函數(shù) 函數(shù)的性質(zhì)（單射，滿射，雙射） 集合的基本概念（交集，并集，冪集，定義域，值域） 給出關(guān)系圖，畫出r(R)，s(R)，t(R)等價關(guān)系及等價劃分 集合相等證明 從A到B的函數(shù)的性質(zhì) 關(guān)系的性質(zhì)（自反，對稱，傳遞）偏序關(guān)系和哈斯圖 A卷 1、選擇10題（2*10=20分） 2、填空8題（1*15=15分） 3、綜合題（6題，39分）（1）前束范式 （2）偏序關(guān)系和哈斯圖（3）文氏圖（4）關(guān)系的閉包 （5）用真值表判斷公式的成真賦值（6）量詞消去 4、證明題（3題，共26分）自然推理系統(tǒng)證明（第三章）集合相等證明 命題邏輯推理證明（第五章）B卷 1、填空10題（2*10=20分） 2、選擇10題（1*10=10分） 3、綜合題（6題，44分）（1）主析取范式判斷公式類型（2）量詞消去，求公式真值（3）集合計算（4）量詞消去（5）前束范式 （6）偏序關(guān)系和哈斯圖 4、推理填空題（8分） 5、證明題（18分）集合相等證明 命題邏輯推理證明 武漢理工大學(xué)2011年博士入學(xué)考試《離散數(shù)學(xué)》考試大綱 一、考試要求共濟 要求考生系統(tǒng)地掌握離散數(shù)學(xué)的基本概念、基本定理和方法，具有較強的邏輯思維和抽象思維能力，能夠靈活運用所學(xué)的內(nèi)容和方法解決實際問題。考 二、考試內(nèi)容濟 1、數(shù)理邏輯濟 1)命題和聯(lián)結(jié)詞，謂詞與量詞，合適公式，賦值，解釋與指派，范式共 2)命題形式化，等價式與對偶式，蘊含式，推理與證明 3)證明方法3 4)數(shù)學(xué)歸納法 2、集合論院 1)集合代數(shù)，笛卡爾乘積，關(guān)系與函數(shù)，關(guān)系的性質(zhì)與運算 2)等價關(guān)系，劃分共濟 3)偏序關(guān)系與偏序集，格輔導(dǎo) 3、計數(shù)336260 37 1)排列與組合，容斥原理，鴿巢原理共 2)離散概率正門 3)函數(shù)的增長與遞推關(guān)系院 4、圖論 共濟網(wǎng) 1)歐拉圖與哈密頓圖，平面圖與對偶圖，二部圖與匹配，圖的著色021- 2)樹，樹的遍歷，最小生成樹正門 3)最短路經(jīng)，最大流量 5、形式語言與自動機 院 1)語言與文法，正則表達式與正則集 2)有限狀態(tài)自動機，自動機與正則語言 6、代數(shù)系統(tǒng) 1)二元運算，群與半群，積群與商群，同態(tài)與同構(gòu) 2)群與編碼 3)格與布爾代數(shù)，環(huán)與域 三、試卷結(jié)構(gòu) 1、考試時間為3小時，滿分100分。 2、題目類型：計算題、簡答題和證明題。 參考書 1．離散數(shù)學(xué)，胡新啟，武漢大學(xué)出版社，2007年。 2．離散數(shù)學(xué)，尹寶林、何自強、許光漢、檀鳳琴等，高等教育出版社，1998年。 3．離散數(shù)學(xué)及其應(yīng)用，Kenneth H.Rosen，機械工業(yè)出版社，2002年。第二篇：離散數(shù)學(xué)考試試題(A、B卷及答案)test2
第三篇：離散數(shù)學(xué)考試試題(A卷及答案)
第四篇：離散數(shù)學(xué)考試范圍
第五篇：離散數(shù)學(xué)考試大綱
點擊咨詢 