第一篇：離散數學考試試題(A、B卷及答案)test7

離散數學考試試題（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個人參加圍棋優勝比賽。關于誰參加競賽，下列4種判斷都是正確的：

(1)甲和乙只有一人參加；(2)丙參加，丁必參加；(3)乙或丁至多參加一人；(4)丁不參加，甲也不會參加。請推出哪兩個人參加了圍棋比賽。

解

符號化命題，設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

但依據題意條件，有且僅有兩人參加競賽，故?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規則，只能將x換成某個個體常元c，而不能將其改為自由變元。所以應將(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分）設A＝{a，b，c}，試給出A上的一個二元關系R，使其同時不滿足自反性、反自反性、對稱性、反對稱性和傳遞性。

解

設R＝{，，，}，則 因為?R，R不自反； 因為∈R，R不反自反；

因為∈R，?R，R不對稱； 因為∈R，∈R，R不反對稱；

因為∈R，∈R，但?R，R不傳遞。

五、（15分）設函數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的函數。

(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(x1)≠g(x2)。所以，g是單射。

六、（15分）設R是集合A上的一個具有傳遞和自反性質的關系，T是A上的關系，使得?T??R且?R，證明T是一個等價關系。

證明

因R自反，任意a∈A，有∈R，由T的定義，有∈T，故T自反。

若∈T，即∈R且∈R，也就是∈R且∈R，從而∈T，故T對稱。若∈T，∈T，即∈R且∈R，∈R且∈R，因R傳遞，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T傳遞。

所以，T是A上的等價關系。

七、（15分）若是群，H是G的非空子集，則是的子群?對任意的a、b∈H有a*b1∈H。－證明

必要性：對任意的a、b∈H，由是的子群，必有b1∈H，從而a*b1∈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上滿足結合律。綜上可知，是的子群。

八、（15分）(1)若無向圖G中只有兩個奇數度結點，則這兩個結點一定是連通的。(2)若有向圖G中只有兩個奇數度結點，它們一個可達另一個結點或互相可達嗎？

證明

(1)設無向圖G中只有兩個奇數度結點u和v。從u開始構造一條回路，即從u出發經關聯結點u的邊e1到達結點u1，若d(u1)為偶數，則必可由u1再經關聯u1的邊e2到達結點u2，如此繼續下去，每條邊只取一次，直到另一個奇數度結點為止，由于圖G中只有兩個奇數度結點，故該結點或是u或是v。如果是v，那么從u到v的一條路就構造好了。如果仍是u，該回路上每個結點都關聯偶數條邊，而d(u)是奇數，所以至少還有一條邊關聯結點u的邊不在該回路上。繼續從u出發，沿著該邊到達另一個結點u1?，依次下去直到另一個奇數度結點停下。這樣經過有限次后必可到達結點v，這就是一條從u到v的路。

(2)若有向圖G中只有兩個奇數度結點，它們一個可達另一個結點或互相可達不一定成立。下面有向圖中，只有兩個奇數度結點u和v，u和v之間都不可達。

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

一、（15分）設計一盞電燈的開關電路，要求受3個開關A、B、C的控制：當且僅當A和C同時關閉或B和C同時關閉時燈亮。設F表示燈亮。

(1)寫出F在全功能聯結詞組{?}中的命題公式。(2)寫出F的主析取范式與主合取范式。

解

(1)設A：開關A關閉；B：開關B關閉；C：開關C關閉；F＝(A∧C)∨(B∧C)。在全功能聯結詞組{?}中：

?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)設論域為{1，2}，令A(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分）設X為集合，A＝P(X)－{?}－{X}且A≠?，若|X|＝n，問(1)偏序集是否有最大元？(2)偏序集是否有最小元？

(3)偏序集中極大元和極小元的一般形式是什么？并說明理由。解

偏序集不存在最大元和最小元，因為n＞2。

考察P(X)的哈斯圖，最底層的頂點是空集，記作第0層，由底向上，第一層是單元集，第二層是二元集，…，由|X|＝n，則第n－1層是X的n－1元子集，第n層是X。偏序集與偏序集

相比，恰好缺少第0層和第n層。因此的極小元就是X的所有單元集，即{x}，x∈X；而極大元恰好是比X少一個元素，即X－{x}，x∈X。

四、（10分）設A＝{1，2，3，4，5}，R是A上的二元關系，且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分）設函數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的函數。

(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(x1)≠g(x2)。所以，g是單射。

六、（10分）有幺元且滿足消去律的有限半群一定是群。

證明

設是一個有幺元且滿足消去律的有限半群，要證是群，只需證明G的任一元素a可逆。

考慮a，a2，…，ak，…。因為G只有有限個元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。

于是，當m＝1時，a＝e，而e是可逆的；當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的路的個數分別為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為終結點且具有不同始結點的數目為3，其第(2，3)元素為0，表明那些邊既以v2為終結點又以v3為終結點，并且具有相同始結點的數目為0。AAT中的第(2，2)元素為2，表明那些邊以v2為始結點且具有不同終結點的數目為2，其第(2，3)元素為1，表明那些邊既以v2為始結點又以v3為始結點，并且具有相同終結點的數目為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的強分圖。

111??111?? 6

第二篇：離散數學考試試題(A、B卷及答案)test2

離散數學考試試題(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))的主析取范式與主合取范式，并寫出其相應的成真賦值和成假賦值（15分）。

主析取范式與析取范式的區別：主析取范式里每個括號里都必須有全部的變元。主析取范式可由析取范式經等值演算法算得。

證明：

公式法：因為(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))為可滿足式，其相應的成真賦值為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)。

八、證明整數集I上的模m同余關系R={|x?y(mod m)}是等價關系。其中，x?y(mod m)的含義是x-y可以被m整除（15分）。X(modm)=y(modm)證明：1）?x∈I，因為（x-x）/m=0，所以x?x(mod m)，即xRx。

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有逆函數（gf）：C→A。同理可推f-1g-1：C→A是雙射。

因為∈f-1g-1?存在z（∈g-1?∈f-1）?存在z（∈f?∈g）?∈gf?∈（gf）-1,所以（gf）-1=f-1g-1。

1離散數學考試試題(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

四、只要今天天氣不好，就一定有考生不能提前進入考場，當且僅當所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好（15分）。

解 ：

設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={,,}，求其關系矩陣及關系圖（10分）。有就是1，沒就是0

七、設R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它們及R的關系圖（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>}（傳遞

閉包）

九、設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恒等函數，由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－1＝h?g；由f?h?g＝IB，得g－1＝f?h；由g?f?h＝IC，得h－1＝g?f。

第三篇：離散數學考試試題(A卷及答案)

離散數學考試試題（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的二元關系數是多少？A到B的函數數是多少？

解：因為|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元關系有2mn個。因為|BA|=|B||A|=mn，所以A到B的函數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個兒童到公園游樂場，他們在那里可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次的費用是0.5元，公園游樂場總共收入70元，求有多少兒童沒有乘坐過其中任何一種。

解 設A、B、C分別表示騎旋轉木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|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上的等價關系，試證：1）R∩S是A上的等價關系；2）對a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因為R和S是自反關系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因為R和S是對稱關系，所以因∈R、∈S，因而∈R∩S，故R∩S是對稱的。?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因為R和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。

總之R∩S是等價關系。

2）因為x∈[a]R∩S?∈R∩S?∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七（10分）設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()＝。證明h是雙射。

證明：1）先證h是滿射。

?∈B×D，則b∈B，d∈D，因為f是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是滿射。

2）再證h是單射。

?、∈A×C，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因為f是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。綜合1）和2），h是雙射。

八、（12分）是個群，u∈G，定義G中的運算“?”為a?b=a*u-1*b，對任意a,b∈G，求證：也是個群。

證明：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），運算是可結合的。3）?a∈G，設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=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的鄰接距陣A和可達距陣P。

解：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分）求葉的權分別為2、4、6、8、10、12、14的最優二叉樹及其權。

解：最優二叉樹為

權＝148

離散數學考試試題（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（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上的等價關系，試證：1）R∩S是A上的等價關系；2）對a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因為R和S是自反關系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因為R和S是對稱關系，所以因∈R、∈S，因而∈R∩S，故R∩S是對稱的。

?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因為R和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。

總之R∩S是等價關系。

2）因為x∈[a]R∩S?∈R∩S?

∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)設A＝{a，b，c，d}，R是A上的二元關系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，} s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝?R＝{，，，，，，，，} i?1?i

4232-

1六、(15分)設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()＝。證明h是雙射。

證明：1）先證h是滿射。

?∈B×D，則b∈B，d∈D，因為f是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是滿射。

2）再證h是單射。

?、∈A×C，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因為f是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。

綜合1）和2），h是雙射。

七、(12分)設是群，H是G的非空子集，證明是的子群的充要條件是若a，b?H，則有a*b?H。

證明：? ?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上滿足結合律 ∴是的子群。

八、（10分）設G=是簡單的無向平面圖，證明G至少有一個結點的度數小于等于5。

解：設G的每個結點的度數都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一個結點的度數小于等于5。九.G=,A={a,b,c},*的運算表為：(寫過程，7分)

（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分)求葉的權分別為2、4、6、8、10、12、14的最優二叉樹及其權。

解：最優二叉樹為

權＝148 5

第四篇：離散數學考試范圍

第一部分 簡單命題符號化，求主析取范式，判斷公式類型（重言式，矛盾式，可滿足式）量詞消去規則。命題邏輯推理規則

帶全稱量詞和存在量詞的命題邏輯推理的構造和證明 第二部分

集合基本運算，文氏圖 有序對的基本知識，笛卡兒積，特征函數

函數的性質（單射，滿射，雙射）

集合的基本概念（交集，并集，冪集，定義域，值域）

給出關系圖，畫出r(R)，s(R)，t(R)等價關系及等價劃分 集合相等證明

從A到B的函數的性質

關系的性質（自反，對稱，傳遞）偏序關系和哈斯圖

A卷

1、選擇10題（2*10=20分）

2、填空8題（1*15=15分）

3、綜合題（6題，39分）（1）前束范式

（2）偏序關系和哈斯圖（3）文氏圖（4）關系的閉包

（5）用真值表判斷公式的成真賦值（6）量詞消去

4、證明題（3題，共26分）自然推理系統證明（第三章）集合相等證明

命題邏輯推理證明（第五章）B卷

1、填空10題（2*10=20分）

2、選擇10題（1*10=10分）

3、綜合題（6題，44分）（1）主析取范式判斷公式類型（2）量詞消去，求公式真值（3）集合計算（4）量詞消去（5）前束范式

（6）偏序關系和哈斯圖

4、推理填空題（8分）

5、證明題（18分）集合相等證明 命題邏輯推理證明

第五篇：離散數學考試大綱

武漢理工大學2011年博士入學考試《離散數學》考試大綱

一、考試要求共濟

要求考生系統地掌握離散數學的基本概念、基本定理和方法，具有較強的邏輯思維和抽象思維能力，能夠靈活運用所學的內容和方法解決實際問題。考

二、考試內容濟

1、數理邏輯濟

1)命題和聯結詞，謂詞與量詞，合適公式，賦值，解釋與指派，范式共

2)命題形式化，等價式與對偶式，蘊含式，推理與證明

3)證明方法3

4)數學歸納法

2、集合論院

1)集合代數，笛卡爾乘積，關系與函數，關系的性質與運算

2)等價關系，劃分共濟

3)偏序關系與偏序集，格輔導

3、計數336260 37

1)排列與組合，容斥原理，鴿巢原理共

2)離散概率正門

3)函數的增長與遞推關系院

4、圖論 共濟網

1)歐拉圖與哈密頓圖，平面圖與對偶圖，二部圖與匹配，圖的著色021-

2)樹，樹的遍歷，最小生成樹正門

3)最短路經，最大流量

5、形式語言與自動機 院

1)語言與文法，正則表達式與正則集

2)有限狀態自動機，自動機與正則語言

6、代數系統

1)二元運算，群與半群，積群與商群，同態與同構

2)群與編碼

3)格與布爾代數，環與域

三、試卷結構

1、考試時間為3小時，滿分100分。

2、題目類型：計算題、簡答題和證明題。

參考書

1．離散數學，胡新啟，武漢大學出版社，2007年。

2．離散數學，尹寶林、何自強、許光漢、檀鳳琴等，高等教育出版社，1998年。

3．離散數學及其應用，Kenneth H.Rosen，機械工業出版社，2002年。