第一篇：離散數(shù)學(xué)期末考試

一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）

1、設(shè)集合M={a，?}，N ={{a}，?}則M?N=（）。A、? B、{?} C、{a} D、{{a}，?，a}

2、設(shè)關(guān)系F={<1，a >，<2，2>，}，G={，，<1，2>}則 F?G=（）。

A、{<1，b>，<1，c>，}

B、{，，<1，b>} C、{，<1，2>}

D、{，<2，2>，<1，b>}

3、設(shè)集合H={1，2，3，4}，則H上的關(guān)系R={

。x +y是偶數(shù)}具有（）A、自反性、反對(duì)稱性和傳遞性

B、反自反性、反對(duì)稱性和傳遞性

C、反自反性、對(duì)稱性和傳遞性

D、自反性、對(duì)稱性和傳遞性

4、設(shè)T是一棵完全二叉樹(shù)，則T的每個(gè)結(jié)點(diǎn)都（）。

A、至少有兩個(gè)子結(jié)點(diǎn)

B、至多有兩個(gè)子結(jié)點(diǎn)

C、恰有兩個(gè)子結(jié)點(diǎn)

D、可以有任意多個(gè)子結(jié)點(diǎn)

5、設(shè)R是實(shí)數(shù)集，“+，—，A、

?>是群

B、是群

? >是半群

D、是獨(dú)異點(diǎn)

6、下面關(guān)系中，函數(shù)關(guān)系是（）。

A、{，，}

B、{，，<1，x>} C、{<1，y>，<1，x>，}

D、{，，}

7、設(shè)是一個(gè)代數(shù)系統(tǒng)，若多任意的x，y?S，都有x?y=y?x，則稱運(yùn)算?在S上滿足（）。

A、結(jié)合律

B、交換律

C、分配律

D、冪等律

8、設(shè)Z是整數(shù)集，“—”是整數(shù)減法，則下列說(shuō)法正確的是（）。A、不是代數(shù)系統(tǒng)

B、的單位元是0

C、是代數(shù)系統(tǒng)

D、的單位元是1

9、設(shè)L是無(wú)向圖G中的一條通路，L中的頂點(diǎn)各不相同，則L是一條（）。A、簡(jiǎn)單通路

B、初級(jí)通路

C、簡(jiǎn)單回路

D、初級(jí)回路

10、設(shè)G有6個(gè)3度點(diǎn)，2個(gè)4度點(diǎn)，其余頂點(diǎn)的度數(shù)均為0，則G的邊數(shù)是（）。A、10

B、13

C、11

D、6

二、填空題(本大題共8題，共10個(gè)空，每空2分，共20分)

1、設(shè)關(guān)系R={，<2，1>，<2，b>}，則R逆關(guān)系R?1=_______________________________。

2、在代數(shù)系統(tǒng)（Q是有理數(shù)集，“+”是有理數(shù)加法）中，單位元是______，2的逆元是___________。

3、設(shè)集合M={1，2，3，5}，則M的冪集P（M）包含___________個(gè)元素。

4、設(shè)T是一棵有n(n?2)個(gè)頂點(diǎn)的樹(shù)，則T有_____________條邊。

5、設(shè)是一個(gè)代數(shù)系統(tǒng)，?是S上的二元運(yùn)算，若存在??S，對(duì)任意x?S，有??x=x??=?，則稱?是的_______________。

6、設(shè)是一個(gè)代數(shù)系統(tǒng)，若?滿足結(jié)合律且中有單位元，則稱為一個(gè)___________________。

7、設(shè)D是有向圖，若D的基圖是連通圖，則稱D是_________________圖

8、既不含________________也不含____________________的無(wú)向圖稱為簡(jiǎn)單圖。

三、計(jì)算題(本大題共3小題，每小題10分，共30分)

1、用等值演算法求公式A=(p??q)?(p?r)的主析取范式。

2、求公式?x(Q(x)?G(x，s))?(?yP(y)??zH(y，z))的前束范式。

3、設(shè)集合A={1，2，3，4，5}，關(guān)系R={（1）列出R的所有元素；（2）寫出R的關(guān)系矩陣Mx，y? A且x整除y}，要求：

R；

（3）求偏序集的極大元、極小元和最小元。

四、應(yīng)用題(本大題共2小題，每小題5分，共10分)

1、用命題公式將下列命題符號(hào)化： 2和5是偶數(shù)，當(dāng)且僅當(dāng)5>2。

2、用謂詞公式將下列命題符號(hào)化：

每個(gè)計(jì)算機(jī)專業(yè)的學(xué)生都要學(xué)《編譯原理》，但有些計(jì)算機(jī)專業(yè)的學(xué)生不學(xué)《經(jīng)濟(jì)學(xué)》。

五、證明題（本大題共2小題，每小題10分，共20分）

1、在命題邏輯系統(tǒng)中用歸結(jié)法證明下列推理是有效的： 前提：?s?q，p??q，s 結(jié)論：?p

2、在謂詞邏輯系統(tǒng)中寫出下列推理的（形式）證明：

前提：?x(M(x)?P(x))，?x(M(x)?G(x))，?x(?G(x))結(jié)論：?xP(x)

計(jì)算題

6.設(shè)命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。

7.(9分)設(shè)一階邏輯公式：G =(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.9.設(shè)R是集合A = {a, b, c, d}.R是A上的二元關(guān)系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)畫出r(R), s(R), t(R)的關(guān)系圖.11.通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：

(1)G =(P∧Q)∨(?P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(?P∧R))13.設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝

{(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關(guān)系矩陣；(2)計(jì)算R?S, R∪S, R1, S1?R1.－

－

－證明題

1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。2.設(shè)A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D。4.(本題10分)A, B為兩個(gè)任意集合，求證：

A－(A∩B)=(A∪B)－B.答案：

1-5

BADBB 6-10 BBABB

1.{<1，a>，<1，2>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱連通 8.平行邊

環(huán) 三．

??(p??q)?(p?r)?(?p?q)?(p?r)1.?(?p?q?r)?(?p?q??r)?(p?q?r)?(p??q?r)?m011?m010?m111?m1012.??x(Q(x)?G(x,s))??y?z(P(y)?H(y,z))

??y?z?x((Q(x)?G(x,s))?(P(y)?H(y,z))3.(1)R?{?1,1?,?2,2?,?3,3?,?4,4?,?5,5?,?1,2?,?1,3?,?1,4?,?1,5?,?2,4?}

??1??2(2)MR???3?4???512345?11111??01010??

（3）最小元=1 極小元=1 極大元=5 00100?00010??00001??四

1.令p表示2是偶數(shù)；令q表示5是偶數(shù)；r表示5>2；

(p?q)?r

2.S（x）：x是計(jì)算機(jī)專業(yè)的學(xué)生；G（x）：x要學(xué)《編譯原理》； F（x）：x學(xué)經(jīng)濟(jì)學(xué)；

?x(S(x)?G(x))??x(S(x)??F(x))

五 1，（1）

s

前提引入（2）

?s?q

前提引入（3）

q??s

置換規(guī)則

（4）

q

1,3析取三段論（5）

p??q

前提引入（6）

?p

4,5拒取

（1）

?x(M(x)?G(x))

前提引入（2）

M（x）v G（x）

EI規(guī)則（3）

?x(?G(x))

前提引入（4）

?G(x)（5）

M(x)

AI規(guī)則

2,4析取三段論

（6）

?x(M(x)?P(x))

前提引入（7）

M(x)→P（x）

AI規(guī)則（8）

P（x）

5,7假言推理（9）

?xP(x)

EG規(guī)則

6.G = ?(P→Q)∨(Q∧(?P→R))

= ?(?P∨Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧P)∨(Q∧R)=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = ?(3, 4, 5, 6, 7).7.G =(?xP(x)∨?yQ(y))→?xR(x)

= ?(?xP(x)∨?yQ(y))∨?xR(x)=(??xP(x)∧??yQ(y))∨?xR(x)=(?x?P(x)∧?y?Q(y))∨?zR(z)= ?x?y?z((?P(x)∧?Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)

關(guān)系圖: abr(R)dcabs(R)dabt(R)dc c

11.G＝(P∧Q)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)＝m6∨m7∨m3 ＝?(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(?P∧R))＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝?(3, 6, 7)G,H的主析取范式相同，所以G = H.?1?013.(1)MR???0??0000011000??0?00??

MS??1??0??0??0100001000?1?? 0??1?(2)R?S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1?R1＝{(b, a),(d, c)}.－－四 證明題

1.證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S

(1)P∨R

(2)?R→P(3)P→Q(4)?R→Q(5)?Q→R(6)R→S

P Q(1)P Q(2)(3)Q(4)P

(7)?Q→S(8)Q∨S Q(5)(6)Q(7)2.證明：(A-B)-C =(A∩~B)∩~C

3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D(1)A D(附加)P(2)?A∨B(3)B Q(1)(2)P Q(4)(4)?C→?B(5)B→C(6)C

Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D

所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D.1.證明：A－(A∩B)

= A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝?∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪? = A－B 所以：A－(A∩B)=(A∪B)－B.

第二篇：離散數(shù)學(xué) 期末考試試卷答案

離散數(shù)學(xué)試題(B卷答案1）

一、證明題（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(置換)?R 2)?x(A(x)?B(x))? ?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∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式（10分）。

證明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))?（?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分）

1）C∨D，(C∨D)? ?E，?E?(A∧?B)，(A∧?B)?(R∨S)?R∨S 證明：(1)(C∨D)??E(2)?E?(A∧?B)

P P

P(3)(C∨D)?(A∧?B)T(1)(2)，I(4)(A∧?B)?(R∨S)(5)(C∨D)?(R∨S)(6)C∨D

T(3)(4)，I P(7)R∨S T(5)，I 2)?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))證明(1)?xP(x)P

(2)P(a)T(1)，ES(3)?x(P(x)?Q(y)∧R(x))P(4)P(a)?Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)?x(P(x)∧R(x))T(8)，EG(10)Q(y)∧?x(P(x)∧R(x))T(6)(9)，I

四、某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)（10分）。

解：A，B，C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。

先求|A∩B|。

∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。

于是|A∪B∪C|=12+6+14-6-5-3+2=20。不會(huì)打這三種球的人數(shù)25-20=5。

五、已知A、B、C是三個(gè)集合，證明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）

六、已知R、S是N上的關(guān)系，其定義如下：R={| x，y?N∧y=x}，S={| x，y?N∧y=x+1}。求R、R*S、S*R、R{1，2}、S[{1，2}]（10分）。

解：R={| x，y?N∧y=x} R*S={| x，y?N∧y=x+1} S*R={| x，y?N∧y=（x+1）}，R{1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。

七、設(shè)R={，，}，求r(R)、s(R)和t(R)（15分）。

解：r(R)={，，，，，}

12-1

2s(R)={，，，，，} R= R={，，} R={，，} R={，，} t(R)={，，，，，，，，}

八、證明整數(shù)集I上的模m同余關(guān)系R={|x?y(mod m)}是等價(jià)關(guān)系。其中，x?y(mod m)的含義是x-y可以被m整除（15分）。

證明：1）?x∈I，因?yàn)椋▁-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）=fg（10分）。

1-1-14325證明：因?yàn)閒、g是雙射，所以gf：A→C是雙射，所以gf有逆函數(shù)（gf）：C→A。同理可推fg：C→A是雙射。

因?yàn)?x，y>∈fg?存在z（∈g?∈f）?存在z（∈f?∈g）?∈gf?∈（gf），所以（gf）=fg。

1-1

-1-1-1-1

-1-1-1

-1離散數(shù)學(xué)試題(B卷答案2）

一、證明題（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 ?m0∨m2∨m3

三、推理證明題（10分）

1)(P?(Q?S))∧(?R∨P)∧Q?R?S 證明：(1)R(2)?R∨P(3)P(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

四、只要今天天氣不好，就一定有考生不能提前進(jìn)入考場(chǎng)，當(dāng)且僅當(dāng)所有考生提前進(jìn)入考場(chǎng)，考試才能準(zhǔn)時(shí)進(jìn)行。所以，如果考試準(zhǔn)時(shí)進(jìn)行，那么天氣就好（15分）。

解 設(shè)P：今天天氣好，Q：考試準(zhǔn)時(shí)進(jìn)行，A(e)：e提前進(jìn)入考場(chǎng)，個(gè)體域：考生 的集合，則命題可符號(hào)化為：?P??x?A(x)，?xA(x)?QQ?P。

(1)?P??x?A(x)P(2)?P???xA(x)T(1)，E(3)?xA(x)?P T(2)，E(4)?xA(x)?Q P(5)(?xA(x)?Q)∧(Q??xA(x))T(4)，E(6)Q??xA(x)T(5)，I(7)Q?P T(6)(3)，I

五、已知A、B、C是三個(gè)集合，證明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={,,}，求其關(guān)系矩陣及關(guān)系圖（10分）。

七、設(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>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}

八、設(shè)R1是A上的等價(jià)關(guān)系，R2是B上的等價(jià)關(guān)系，A≠?且B≠?。關(guān)系R滿足：<，>∈R?∈R1且∈R2，證明R是A×B上的等價(jià)關(guān)系（10分）。

證明 對(duì)任意的∈A×B，由R1是A上的等價(jià)關(guān)系可得∈R1，由R2是B上的等價(jià)關(guān)系可得∈R2。再由R的定義，有<，>∈R，所以R是自反的。

對(duì)任意的、∈A×B，若R，則∈R1且∈R2。由R1對(duì)稱得∈R1，由R2對(duì)稱得∈R2。再由R的定義，有<，> 432

5∈R，即R，所以R是對(duì)稱的。

對(duì)任意的、、∈A×B，若R且R，則∈R1且∈R2，∈R1且∈R2。由∈R1、∈R1及R1的傳遞性得∈R1，由∈R2、∈R2及R2的傳遞性得∈R1。再由R的定義，有<，>∈R，即R，所以R是傳遞的。

綜上可得，R是A×B上的等價(jià)關(guān)系。

九、設(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、g和h（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＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。－

1－1

－1－1－1

－1離散數(shù)學(xué)試題(B卷答案3）

一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？(寫過(guò)程)1)P?(P∨Q∨R)2)?((Q?P)∨?P)∧(P∨R)3)((?P∨Q)?R)?((P∧Q)∨R)解：1)重言式；2)矛盾式；3)可滿足式

二、（10分）求命題公式（P∨(Q∧R))?(P∨Q∨R)的主析取范式，并求成真賦值。

解：（P∨(Q∧R))?(P∨Q∨R)??(P∨(Q∧R))∨P∨Q∨R ??P∧(?Q∨?R)∨P∨Q∨R ?(?P∧?Q)∨(?P∧?R)∨(P∨Q)∨R ?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R ?1∨((?P∧?R)∨R)?1 ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 該式為重言式，全部賦值都是成真賦值。

三、（10分）證明((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(A∧(P?Q))?C 證明：((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(?(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 ?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))?C ?((P∧Q∧A)∨(A∧?P∧?Q))?C ?(A∧((P∧Q)∨(?P∧?Q)))?C ?(A∧((P∨?Q)∧(?P∨Q)))?C ?(A∧((Q?P)∧(P?Q)))?C ?(A∧(P?Q))?C

四、（10分）個(gè)體域?yàn)閧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+2=4））?（0∨0）∧（0∨1）?0∧1?0

五、（10分）對(duì)于任意集合A，B，試證明：P(A)∩P(B)=P(A∩B)解：?x?P(A)∩P(B)，x?P(A)且x?P(B)，有x?A且x?B，從而x?A∩B，x?P(A∩B)，由于上述過(guò)程可逆，故P(A)∩P(B)=P(A∩B)

六、（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分）設(shè)函數(shù)f：R×R?R×R，R為實(shí)數(shù)集，f定義為：f()=。1)證明f是雙射。

解：1）?，∈R×R，若f()=f()，即=，則x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2從而f是單射。

2）?

∈R×R，由f()=

，通過(guò)計(jì)算可得x=(p+q)/2；y=(p-q)/2；從而

的原象存在，f是滿射。

八、（10分）是個(gè)群，u∈G，定義G中的運(yùn)算“?”為a?b=a*u*b，對(duì)任意a，b∈G，求證：也是個(gè)群。

證明：1）?a，b∈G，a?b=a*u*b∈G，運(yùn)算是封閉的。

2）?a，b，c∈G，（a?b）?c=（a*u*b）*u*c=a*u*（b*u*c）=a?（b?c），運(yùn)算是可結(jié)合的。

3）?a∈G，設(shè)E為?的單位元，則a?E=a*u*E=a，得E=u，存在單位元u。4）?a∈G，a?x=a*u*x=E，x=u*a*u，則x?a=u*a*u*u*a=u=E，每個(gè)元素都有逆元。

所以也是個(gè)群。

九、（10分）已知：D=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的鄰接距陣A和可達(dá)距陣P。

解：1）D的鄰接距陣A和可達(dá)距陣P如下：

A= 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1-

1-1

P= 1 1 1 1

十、（10分）求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹(shù)及其權(quán)。

解：最優(yōu)二叉樹(shù)為

權(quán)＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148

離散數(shù)學(xué)試題(B卷答案4）

一、證明題（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(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x))證明：?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x))

二、求命題公式(?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?m0∨m2∨m3

三、推理證明題（10分）

1)(P?(Q?S))∧(?R∨P)∧Q?R?S 證明：（1）R 附加前提(2)?R∨P P(3)P T(1)(2),I(4)P?(Q?S)P(5)Q?S T(3)(4),I(6)Q P(7)S T(5)(6),I(8)R?S CP 2)?x(P(x)∨Q(x))，?x?P(x)??x Q(x)證明：(1)?x?P(x)P(2)?P(c)T(1),US(3)?x(P(x)∨Q(x))P(4)P(c)∨Q(c)T(3),US(5)Q(c)T(2)(4),I(6)?x Q(x)T(5),EG

四、例5在邊長(zhǎng)為1的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形（可能是退化的）面積不超過(guò)1/8（10分）。

證明：把邊長(zhǎng)為1的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形（可能是退化的）面積不超過(guò)小正方形的一半，即1/8。

五、已知A、B、C是三個(gè)集合，證明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）

六、?={A1，A2，?，An}是集合A的一個(gè)劃分，定義R={|a、b∈Ai，I=1，2，?，n}，則R是A上的等價(jià)關(guān)系（15分）。

證明：?a∈A必有i使得a∈Ai，由定義知aRa，故R自反。?a,b∈A，若aRb，則a,b∈Ai，即b,a∈Ai，所以bRa，故R對(duì)稱。

?a,b,c∈A，若aRb 且bRc，則a,b∈Ai及b,c∈Aj。因?yàn)閕≠j時(shí)Ai∩Aj=?，故i=j，即a,b,c∈Ai，所以aRc，故R傳遞。

總之R是A上的等價(jià)關(guān)系。

七、若f:A→B是雙射，則f:B→A是雙射（15分）。

證明:對(duì)任意的x∈A，因?yàn)閒是從A到B的函數(shù)，故存在y∈B，使∈f，∈f。所以,f是滿射。

對(duì)任意的x∈A，若存在y1,y2∈B，使得∈f且∈f,則有∈f且∈f。因?yàn)閒是函數(shù)，則y1=y2。所以，f是單射。

因此f是雙射。

八、設(shè)是群，和是的子群，證明：若A∪B＝G，則A＝G或B＝G（10分）。

證明 假設(shè)A≠G且B≠G，則存在a?A，a?B，且存在b?B，b?A（否則對(duì)任意的a?A，a?B，從而A?B，即A∪B＝B，得B＝G，矛盾。）

對(duì)于元素a*b?G，若a*b?A，因A是子群，a?A，從而a *(a*b)＝b ?A，所以矛盾，故a*b?A。同理可證a*b?B，綜合有a*b?A∪B＝G。綜上所述，假設(shè)不成立，得證A＝G或B＝G。

九、若無(wú)向圖G是不連通的，證明G的補(bǔ)圖G是連通的（10分）。

證明 設(shè)無(wú)向圖G是不連通的，其k個(gè)連通分支為G1、G2、?、Gk。任取結(jié)點(diǎn)u、v∈G，若u和v不在圖G的同一個(gè)連通分支中，則[u，v]不是圖G的邊，因而[u，v]

1-1-1

-1-1-1-1是圖G的邊；若u和v在圖G的同一個(gè)連通分支中，不妨設(shè)其在連通分支Gi（1≤i≤k）中，在不同于Gi的另一連通分支上取一結(jié)點(diǎn)w，則[u，w]和[w，v]都不是圖G的邊，因而[u，w]和[w，v]都是G的邊。綜上可知，不管那種情況，u和v都是可達(dá)的。由u和v的任意性可知，G是連通的。

離散數(shù)學(xué)試題（B卷答案5）

一、（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分）敘述并證明蘇格拉底三段論

解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號(hào)化：F（x）：x是一個(gè)人。G（x）：x要死的。A：蘇格拉底。命題符號(hào)化為?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是三個(gè)集合，證明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上的等價(jià)關(guān)系，試證：1）R∩S是A上的等價(jià)關(guān)系；2）對(duì)a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因?yàn)镽和S是自反關(guān)系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因?yàn)镽和S是對(duì)稱關(guān)系，所以因∈R、∈S，因而∈R∩S，故R∩S是對(duì)稱的。

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

總之R∩S是等價(jià)關(guān)系。

2）因?yàn)閤∈[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分)設(shè)A＝{a，b，c，d}，R是A上的二元關(guān)系，且R＝{，，，}，求r(R)、s(R)和t(R)。

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

t(R)＝?R＝{，，，，，，，

4232-1d>，}

六、(15分)設(shè)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，因?yàn)閒是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)，因?yàn)閒是A到B的雙射，g是C

到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。

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

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

證明：? ?a,b∈H有b∈H，所以a*b∈H。??a∈H，則e=a*a∈H a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H?G且H≠?,∴*在H上滿足結(jié)合律 ∴是的子群。

八、（10分）設(shè)G=是簡(jiǎn)單的無(wú)向平面圖，證明G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。

解：設(shè)G的每個(gè)結(jié)點(diǎn)的度數(shù)都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡(jiǎn)單無(wú)向平面圖的|E|≤3|V|-6矛盾，所以G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。九.G=,A={a,b,c},*的運(yùn)算表為：(寫過(guò)程，7分)-

1-1

-1-1-1-1-1

-1-1（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）因?yàn)閍*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a（3）因?yàn)閍*a=a 所以G的冪等元是a（4）因?yàn)閎*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹(shù)及其權(quán)。

解：最優(yōu)二叉樹(shù)為

權(quán)＝148 離散數(shù)學(xué)試題（B卷答案6）

一、（20分）用公式法判斷下列公式的類型：(1)(?P∨?Q)?(P??Q)(2)(P?Q)?(P∧?(Q∨?R))解：（1）因?yàn)??P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q)

?(P∧Q)∨(P∧?Q)∨(?P∧Q)?m1∨m2∨m3 ?M0

所以，公式(?P∨?Q)?(P??Q)為可滿足式。

（2）因?yàn)?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

所以，公式(P?Q)?(P∧?(Q∨?R))為可滿足式。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)科學(xué)家都是勤奮的，每個(gè)勤奮

又身體健康的人在事業(yè)中都會(huì)獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。

解：論域：所有人的集合。Q(x)：x是勤奮的；H(x)：x是身體健康的；S(x)：x是科學(xué)家；C(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為：

?x(S(x)?H(x))Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧?x(C(x)∨F(x))下面給出證明：

(1)?x(S(x)∧H(x))

P(2)S(a)∧H(a)

T(1)，ES(3)?x(S(x)?Q(x))

P(4)S(a)?Q(a)

T(1)，US(5)S(a)

T(2)，I(6)Q(a)

T(4)(5)，I(7)H(a)

T(2)，I(8)Q(a)∧H(a)

T(6)(7)，I(9)?x(Q(x)∧H(x)?C(x))

P(10)Q(a)∧H(a)?C(a)

T(9)，Us(11)C(a)

T(8)(10)，I(12)?xC(x)

T(11)，EG(13)?x(C(x)∨F(x))

T(12)，I

三、（10分）設(shè)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分）設(shè)R和S是集合A上的任意關(guān)系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對(duì)稱的，則R*S也是對(duì)稱的。

(4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則R∩S是自反的。(6)若R和S是傳遞的，則R∪S是傳遞的。

解

(1)成立。對(duì)任意的a∈A，因?yàn)镽和S是自反的，則∈R，∈S，于是∈R*S，故R*S也是自反的。

(2)不成立。例如，令A(yù)＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，則R和S是反自反的，但R*S＝{<1，1>}不是反自反的。

(3)不成立。例如，令A(yù)＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，則R和S是對(duì)稱的，但R*S＝{<1，3>，<3，2>}不是對(duì)稱的。

(4)不成立。例如，令A(yù)＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，則R和S是傳遞的，但R*S＝{<1，3>，<1，1>，<2，1>}不是傳遞的。

(5)成立。對(duì)任意的a∈A，因?yàn)镽和S是自反的，則∈R，∈S，于是∈R∩S，所以R∩S是自反的。

五、（15分）令X＝{x1，x2，?，xm}，Y＝{y1，y2，?，yn}。問(wèn)(1)有多少個(gè)不同的由X到Y(jié)的函數(shù)？

(2)當(dāng)n、m滿足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？(3)當(dāng)n、m滿足什么條件時(shí)，存在雙射，且有多少個(gè)不同的雙射？

解

(1)由于對(duì)X中每個(gè)元素可以取Y中任一元素與其對(duì)應(yīng)，每個(gè)元素有n種取法，所以不同的函數(shù)共nm個(gè)。

(2)顯然當(dāng)|m|≤|n|時(shí)，存在單射。由于在Y中任選m個(gè)元素的任一全排列都形成X到

mY的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個(gè)。

(3)顯然當(dāng)|m|＝|n|時(shí)，才存在雙射。此時(shí)Y中元素的任一不同的全排列都形成X到Y(jié)的不同的雙射，故不同的雙射有m!個(gè)。

六、（5分）集合X上有m個(gè)元素，集合Y上有n個(gè)元素，問(wèn)X到Y(jié)的二元關(guān)系總共有多少個(gè)？

解

X到Y(jié)的不同的二元關(guān)系對(duì)應(yīng)X×Y的不同的子集，而X×Y的不同的子集共有個(gè)2mn，所以X到Y(jié)的二元關(guān)系總共有2mn個(gè)。

七、（10分）若是群，則對(duì)于任意的a、b∈G，必有惟一的x∈G使得a*x＝

b。

證明 設(shè)e是群的幺元。令x＝a1*b，則a*x＝a*(a1*b)＝(a*a1)*b＝e*b＝b。

－

－

－所以，x＝a1*b是a*x＝b的解。－若x?∈G也是a*x＝b的解，則x?＝e*x?＝(a1*a)*x?＝a1*(a*x?)＝a1*b＝x。所以，x

－

－

－＝a1*b是a*x＝b的惟一解。－

八、（10分）給定連通簡(jiǎn)單平面圖G＝，且|V|＝6，|E|＝12。證明：對(duì)任意f∈F，d(f)＝3。

證明

由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝

f?F24。若存在f∈F，使得d(f)＞3，則3|F|＜2|E|＝24，于是|F|＜8，與|F|＝8矛盾。故對(duì)任意f∈F，d(f)＝3。

離散數(shù)學(xué)試題（B卷答案7）

一、（15分）設(shè)計(jì)一盞電燈的開(kāi)關(guān)電路，要求受3個(gè)開(kāi)關(guān)A、B、C的控制：當(dāng)且僅當(dāng)A和C同時(shí)關(guān)閉或B和C同時(shí)關(guān)閉時(shí)燈亮。設(shè)F表示燈亮。

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

解

(1)設(shè)A：開(kāi)關(guān)A關(guān)閉；B：開(kāi)關(guān)B關(guān)閉；C：開(kāi)關(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è)論域?yàn)閧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，問(wèn)(1)偏序集是否有最大元？(2)偏序集是否有最小元？

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

偏序集不存在最大元和最小元，因?yàn)閚＞2。

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

相比，恰好缺少第0層和第n層。因此的極小元就是X的所有單元集，即{x}，x∈X；而極大元恰好是比X少一個(gè)元素，即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，i?1?1>，<5，4>，<5，5>}。

五、（10分）設(shè)函數(shù)g：A→B，f：B→C，(1)若f?g是滿射，則f是滿射。(2)若f?g是單射，則g是單射。

證明

因?yàn)間：A→B，f：B→C，由定理5.5知，f?g為A到C的函數(shù)。

(1)對(duì)任意的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)對(duì)任意的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è)是一個(gè)有幺元且滿足消去律的有限半群，要證是群，只需證明G的任一元素a可逆。

考慮a，a2，?，ak，?。因?yàn)镚只有有限個(gè)元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。

于是，當(dāng)m＝1時(shí)，a＝e，而e是可逆的；當(dāng)m＞1時(shí)，a*am-1＝am-1*a＝e。從而a是可逆的，其逆元是am-1?？傊?，a是可逆的。

七、（20分）有向圖G如圖所示，試求：(1)求G的鄰接矩陣A。

(2)求出A2、A3和A4，v1到v4長(zhǎng)度為1、2、3和4的路有多少？

(3)求出ATA和AAT，說(shuō)明ATA和AAT中的第(2，2)元素和第(2，3)元素的意義。(4)求出可達(dá)矩陣P。(5)求出強(qiáng)分圖。

解

(1)求G的鄰接矩陣為：

?0??0A??0??0?101??011?

101??100??(2)由于

?0??02A??0??0?111??02??201?3?0A??02111????02011???12??03??22??044A?

?0312????0101???23??13? 23??22??所以v1到v4長(zhǎng)度為1、2、3和4的路的個(gè)數(shù)分別為1、1、2、3。(3)由于

?0??0ATA??0??0?000??21??312??12TAA?

?21011????10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素為3，表明那些邊以v2為終結(jié)點(diǎn)且具有不同始結(jié)點(diǎn)的數(shù)目為3，其第(2，3)元素為0，表明那些邊既以v2為終結(jié)點(diǎn)又以v3為終結(jié)點(diǎn)，并且具有相同始結(jié)點(diǎn)的數(shù)目為0。AAT中的第(2，2)元素為2，表明那些邊以v2為始結(jié)點(diǎn)且具有不同終結(jié)點(diǎn)的數(shù)目為2，其第(2，3)元素為1，表明那些邊既以v2為始結(jié)點(diǎn)又以v3為始結(jié)點(diǎn)，并且具有相同終結(jié)點(diǎn)的數(shù)目為1。

(4)?0??0B4?A?A2?A3?A4??0??0??0??0所以求可達(dá)矩陣為P??0??0??0??0(5)因?yàn)镻?PT??0??0?101??0??011??0+101??0???100???0111??111?。

111??111??111??0??111??1∧?1111????1111???000??0??111??0＝?0111????0111???000??111?，所以{v1}，{v2，v3，v4}

111??111??因

111??0

??

201??0

+

111??0

???011???0

212??03??122??04+

212??03???201???0123??13??23??22???0

??0?0??0?

為

741?

?

747?，747?

?

434??構(gòu)成G的強(qiáng)分圖。

離散數(shù)學(xué)試題（B卷答案8）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明

因?yàn)镾∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。(1)?R

附加前提(2)P?R

P(3)?P

T(1)(2)，I(4)P∨Q

P(5)Q

T(3)(4)，I(6)Q?S

P(7)S

T(5)(6)，I(8)?R?S

CP(9)S∨R

T(8)，E

二、（15分）根據(jù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。

(1)??x(P(x)?Q(x))

P(2)??x(?P(x)∨Q(x))

T(1)，E(3)?x(P(x)∧?Q(x))

T(2)，E(4)P(a)∧?Q(a)

T(3)，ES(5)P(a)

T(4)，I(6)?Q(a)

T(4)，I(7)?x(P(x)?(A(x)∨B(x))

P(8)P(a)?(A(a)∨B(a))

T(7)，US(9)A(a)∨B(a)

T(8)(5)，I(10)?x(A(x)?Q(x))

P

(11)A(a)?Q(a)

T(10)，US(12)?A(a)

T(11)(6)，I

(13)B(a)

T(12)(9)，I(14)P(a)∧B(a)

T(5)(13)，I(15)?x(P(x)∧B(x))

T(14)，EG

三、（10分）某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。

解

設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不會(huì)打這三種球的共5人。

四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱

i?13為由A1、A2和A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。

證明

小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)s1、s2、…、sr(r≤8)。

對(duì)任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個(gè)成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。

i?1i?1i?1i?1i?13rrrr任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。

綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。

五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。

證明

(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對(duì)任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。

證明

對(duì)G的邊數(shù)m作歸納法。

當(dāng)m＝0時(shí)，由于G是連通圖，所以G為平凡圖，此時(shí)n＝1，r＝1，結(jié)論自然成立。假設(shè)對(duì)邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對(duì)e分為下列情況來(lái)討論：

若e為割邊，則G?有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學(xué)歸納法知，結(jié)論成立。

七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：(1)f?g是A到C的函數(shù)；

(2)對(duì)任意的x∈A，有f?g(x)＝f(g(x))。

證明

(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對(duì)于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對(duì)任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。

綜上可知，f?g是A到C的函數(shù)。

(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函數(shù)，則可寫為f?g(x)＝f(g(x))。

八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a1*b∈H}，－則R是G中的一個(gè)等價(jià)關(guān)系，且[a]R＝aH。

證明

對(duì)于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。

－

－

若∈R，則a1*b∈H。因?yàn)镠是G的子群，故(a1*b)1＝b1*a∈H。所以

－

－

－a>∈R。

若∈R，∈R，則a1*b∈H，b1*c∈H。因?yàn)镠是G的子群，所以(a

－

－

－1*b)*(b1*c)＝a1*c∈H，故∈R。－－綜上可得，R是G中的一個(gè)等價(jià)關(guān)系。

對(duì)于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，－

－于是b∈aH，[a]R?aH。對(duì)任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R＝aH。

離散數(shù)學(xué)試題（B卷答案9）

一、（10分）證明(P∧Q∧A?C)∧(A?P∨Q∨C)?(A∧(P?Q))?C。證明：(P∧Q∧A?C)∧(A?P∨Q∨C)?(?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。

二、（10分）舉例說(shuō)明下面推理不正確：?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))。

解：設(shè)論域?yàn)閧1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。則： ?x?y(P(x)?Q(y))??x((P(x)?Q(1))∨(P(x)?Q(2)))

?((P(1)?Q(1))∨(P(1)?Q(2)))∧((P(2)?Q(1))∨(P(2)?Q(2)))?((T?T)∨(T?T))∧((T?T)∨(T?T))?T ?y?z(R(y)?Q(z))??y((R(y)?Q(1))∨(R(y)?Q(2)))

?((R(1)?Q(1))∨(R(1)?Q(2)))∧((R(2)?Q(1))∨(R(2)?Q(2)))

?((F?T)∨(F?T))∧((F?T)∨(F?T))

?T

但

?x?z(P(x)?R(z))??x((P(x)?R(1))∧(P(x)?R(2)))?((P(1)?R(1))∧(P(1)?R(2)))∨((P(2)?R(1))∧(P(2)?R(2)))?((T?F)∧(T?F))∨((T?F)∧(T?F))?F 所以，?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))不正確。

三、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：所有牛都有角，有些動(dòng)物是牛，所以，有些動(dòng)物有角。

解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是動(dòng)物；則推理化形式為：

?x(P(x)?Q(x))，?x(P(x)∧R(x))?x(Q(x)∧R(x))下面給出證明：

(1)?x(P(x)∧R(x))

P(2)P(a)∧R(a)

T(1)，ES(3)?x(P(x)?Q(x))

P(4)P(a)?Q(a)

T(3)，US(5)P(a)

T(2)，I(6)Q(a)

T(4)(5)，I(7)R(a)

T(2)，I(8)Q(a)∧R(a)

T(6)(7)，I(9)?x(Q(x)∧R(x))

T(8)，EG

四、（10分）證明(A∩B)×(C∩D)＝(A×C)∩(B×D)。

證明：因?yàn)?x，y>∈(A∩B)×(C∩D)?x∈(A∩B)∧y∈(C∩D)?x∈A∧x∈B∧y∈C∧y∈D?(x∈A∧y∈C)∧(x∈B∧y∈D)?∈A×C∧∈B×D?∈(A×C)∩(B×D)，所以(A∩B)×(C∩D)＝(A×C)∩(B×D)。

五、（15分）設(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，i?1?1>，<5，4>，<5，5>}。

六、（10分）若函數(shù)f：A→B是雙射，則對(duì)任意x∈A，有f1(f(x))＝x。

－證明

對(duì)任意的x∈A，因?yàn)閒：A→B是函數(shù)，則∈f，于是

－由f－1是B到A的函數(shù)，于是可寫為f1(f(x))＝x。

－

七、（10分）若G為有限群，則|G|＝|H|·[G:H]。

證明

設(shè)[G:H]＝k，a1、a2、…、ak分別為H的k個(gè)左陪集的代表元，由定理8.38得

G??[ai]R??aiH

i?1i?1kk又因?yàn)閷?duì)H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|＝…＝|akH|＝|H|。因此

|G|?|?aiH|?i?1k?|aH|?k|H|＝|H|·[G:H]。

ii?1k

八、（20分）（1）畫出3階2條邊的所有非同構(gòu)有向簡(jiǎn)單圖。

解：由握手定理可知，所畫的有向簡(jiǎn)單圖各結(jié)點(diǎn)度數(shù)之和為4，且最大出度和最大入度均小于或等于2。度數(shù)列與入度列、出度列為： 1、2、1：入度列為0、1、1或0、2、0或1、0、1；出度列為1、1、0或1、0、1或0、2、0 2、2、0：入度列為1、1、0；出度列為1、1、0 四個(gè)所求有向簡(jiǎn)單圖如圖所示。

（2）設(shè)G是n(n≥4)階極大平面圖，則G的最小度?≥3。

證明

設(shè)v是極大平面圖G的任一結(jié)點(diǎn)，則v在平面圖G－{v}的某個(gè)面f內(nèi)。由于G－{v}是一個(gè)平面簡(jiǎn)單圖且其結(jié)點(diǎn)數(shù)大于等于3，所以d(f)≥3。由G的極大平面性，v與f上的結(jié)點(diǎn)之間都有邊，因此d(v)≥3。由v的任意性可得，G的最小度?≥3。

離散數(shù)學(xué)試題（B卷答案10）

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

證明：因?yàn)?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不愉快。

解 設(shè)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分）設(shè)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分）設(shè)X＝{1，2，3，4}，R是X上的二元關(guān)系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。

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

?1??0M(R)??1??1?101110110??0? 0??0??(3)對(duì)于R的關(guān)系矩陣，由于對(duì)角線上不全為1，R不是自反的；由于對(duì)角線上存在非0元，R不是反自反的；由于矩陣不對(duì)稱，R不是對(duì)稱的；

經(jīng)過(guò)計(jì)算可得

?1??0M(R2)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0??

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

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

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

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

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

－1

()＝<

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

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

證明 對(duì)G中任意元a和b。

因?yàn)閍*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同33

333

2255

?13

?1?1?1理，由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。

3333334

344433555444

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

八、（15分）（1）證明在n個(gè)結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。

證明 不妨設(shè)G是無(wú)向連通圖（若G為有向圖，可略去邊的方向討論對(duì)應(yīng)的無(wú)向圖）。設(shè)G中結(jié)點(diǎn)為v1、v2、?、vn。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號(hào)），連接v1和v2，得邊e1，還是由連通性，在v3、v4、?、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、?、vn?1中的某個(gè)結(jié)點(diǎn)相鄰，得新邊en?1，由此可見(jiàn)G中至少有n－1條邊。

（2）試給出|V|＝n，|E|＝(n－1)(n－2)的簡(jiǎn)單無(wú)向圖G＝是不連通的例子。

解 下圖滿足條件但不連通。

12344333

第三篇：2012離散數(shù)學(xué)期末考試真題A

《毛概

（二）》復(fù)習(xí)提綱

1、中國(guó)改革開(kāi)放的依據(jù)、性質(zhì)、特點(diǎn)、意義、成敗評(píng)價(jià)標(biāo)準(zhǔn)，及改革發(fā)展穩(wěn)定三者的關(guān)系及處理原則。依據(jù)：也就是改革開(kāi)放的背景：國(guó)內(nèi)：a“文化大革命”使整個(gè)政治局面處于混亂狀態(tài)

b經(jīng)濟(jì)上處于緩慢發(fā)展和停滯狀態(tài)，國(guó)民經(jīng)濟(jì)到了崩潰邊緣國(guó)際：時(shí)代主題的改變，我國(guó)經(jīng)濟(jì)科技實(shí)力與國(guó)際先進(jìn)水平差距拉大

性質(zhì)：改革開(kāi)放是黨在新的時(shí)代條件下帶領(lǐng)人民進(jìn)行的新的偉大革命，它不是對(duì)原有經(jīng)濟(jì)體制細(xì)枝末節(jié)的修補(bǔ)，而是對(duì)其進(jìn)行根本性的變革；改革開(kāi)放是決定當(dāng)代中國(guó)命運(yùn)的關(guān)鍵抉擇。

特點(diǎn)：我國(guó)改革開(kāi)放 有以下七大特點(diǎn)：在改革的性質(zhì)上，堅(jiān)持社會(huì)主義制度的自我完善和發(fā)展在改革的方向上，堅(jiān)持市場(chǎng)取向在改革的目標(biāo)模式上，選擇建立社會(huì)主義市場(chǎng)經(jīng)濟(jì)體制在改革的方法上，堅(jiān)持先易后難、逐步深化、漸進(jìn)式推進(jìn)在改革的總體部署上，堅(jiān)持統(tǒng)籌兼顧，處理好若干重要關(guān)系在改革的動(dòng)力上，既依靠黨和政府的領(lǐng)導(dǎo)，又尊重人民的首創(chuàng)精神在對(duì)改革措施、手段和成果的評(píng)價(jià)上，堅(jiān)持“三個(gè)有利于”標(biāo)準(zhǔn)

意義：1 改革開(kāi)放是決定當(dāng)代中國(guó)命運(yùn)的關(guān)鍵抉擇，是發(fā)展中國(guó)特色社會(huì)主義，實(shí)現(xiàn)中華民族偉大復(fù)興的必由之路只有社會(huì)主義才能救中國(guó)，只有改革開(kāi)放才能發(fā)展中國(guó)，發(fā)展社會(huì)主義，發(fā)展馬克思主義3 改革開(kāi)放符合當(dāng)心民心，順應(yīng)時(shí)代潮流，方向和道路完全是正確的，成效和功績(jī)不容否定，停頓和倒退沒(méi)有出路

改革成敗得失的評(píng)價(jià)標(biāo)準(zhǔn)：1992年，在南方談話中，鄧小平明確地提出了“三個(gè)有利于”標(biāo)準(zhǔn)，即要以是否有利于發(fā)展社會(huì)主義社會(huì)的生產(chǎn)力、是否有利于增強(qiáng)社會(huì)主義國(guó)家的綜合國(guó)力、是否有利于提高人民生活水平作為判斷改革得失成敗的標(biāo)準(zhǔn)。

改革發(fā)展穩(wěn)定三者關(guān)系：

改革是動(dòng)力，發(fā)展是目的，穩(wěn)定是前提。只有堅(jiān)定不移地推進(jìn)發(fā)展，才能不斷增強(qiáng)綜合國(guó)力和國(guó)際競(jìng)爭(zhēng)力，更好地解決前進(jìn)中的矛盾和問(wèn)題。只有堅(jiān)定不移地推進(jìn)改革，才能為經(jīng)濟(jì)和社會(huì)的發(fā)展提供強(qiáng)大的動(dòng)力。只有堅(jiān)定不移地維護(hù)穩(wěn)定，才能不斷為改革發(fā)展創(chuàng)造有利的條件。實(shí)踐表明，改革，發(fā)展，穩(wěn)定三者關(guān)系處理得當(dāng)，就能總攬全局，保證經(jīng)濟(jì)社會(huì)的順利發(fā)展，處理不當(dāng)，就會(huì)吃苦頭，付出代價(jià)。

處理原則：1 保持改革，發(fā)展，穩(wěn)定在動(dòng)態(tài)中的相互協(xié)調(diào)和相互促進(jìn)。把改革的力度，發(fā)展的速度和社會(huì)可以承受的程度統(tǒng)一起來(lái)。把不斷改善人民生活作為處理改革，發(fā)展，穩(wěn)定關(guān)系的重要結(jié)合點(diǎn)。（每點(diǎn)的具體解釋在書(shū)本169頁(yè)）

2、中國(guó)對(duì)外開(kāi)放的依據(jù)、特點(diǎn)與格局

依據(jù)：

1、歷史依據(jù)：近代中國(guó)落后挨打的主要原因是閉關(guān)鎖國(guó)，在社會(huì)主義建設(shè)初期遇到挫折的原因也是 因?yàn)楸黄忍幱诜忾]和半封閉狀態(tài)。

2、時(shí)代依據(jù)： 實(shí)行對(duì)外開(kāi)放是社會(huì)化大生產(chǎn)和經(jīng)濟(jì)生活國(guó)際化的客觀要求。

3現(xiàn)實(shí)依據(jù)： 實(shí)行對(duì)外開(kāi)放是總結(jié)國(guó)內(nèi)外歷史經(jīng)驗(yàn)的必然結(jié)果。

特點(diǎn)：全方位，多層次，寬領(lǐng)域

格局：全方位、多層次、寬領(lǐng)域的對(duì)外開(kāi)放格局

A 全方位： 我國(guó)的對(duì)外開(kāi)放是對(duì)世界所有類型的國(guó)家開(kāi)放，不僅對(duì)發(fā)達(dá)國(guó)家，而且也對(duì)發(fā)展中國(guó)家，對(duì)原蘇聯(lián)東歐地區(qū)的國(guó)家開(kāi)放。但我們對(duì)外開(kāi)放的重點(diǎn)還是發(fā)達(dá)國(guó)家。

B 多層次： 我國(guó)的對(duì)外開(kāi)放經(jīng)歷了由東到西、由點(diǎn)到線、由線到面，由沿海到內(nèi)地逐步推進(jìn)的過(guò)程，形成了全國(guó)性的對(duì)外開(kāi)放格局。

C 多渠道、寬領(lǐng)域： 就是向世界市場(chǎng)開(kāi)放，包括商品市場(chǎng)、資本市場(chǎng)、技術(shù)市場(chǎng)、勞務(wù)市場(chǎng)等。

3、商品經(jīng)濟(jì)、市場(chǎng)經(jīng)濟(jì)、社會(huì)主義經(jīng)濟(jì)、社會(huì)主義市場(chǎng)經(jīng)濟(jì)的特點(diǎn)、聯(lián)系和區(qū)別。

商品經(jīng)濟(jì)的產(chǎn)生和存在需要兩個(gè)基本經(jīng)濟(jì)條件，第一個(gè)是社會(huì)分工的產(chǎn)生和存在，第二個(gè)是生產(chǎn)資料和勞動(dòng)分工屬于不同的所有者。商品經(jīng)濟(jì)的特點(diǎn)有:市場(chǎng)性；自發(fā)性；競(jìng)爭(zhēng)性；商品的使用價(jià)值；商品的價(jià)值；具有具體勞動(dòng)和抽象勞動(dòng)。

市場(chǎng)經(jīng)濟(jì)的特點(diǎn)：1.企業(yè)是獨(dú)立的經(jīng)濟(jì)單位

2.生產(chǎn)要素可以自由流動(dòng)

3.通過(guò)價(jià)格調(diào)節(jié)經(jīng)濟(jì)

社會(huì)主義經(jīng)濟(jì):

社會(huì)主義市場(chǎng)經(jīng)濟(jì)的特點(diǎn)：堅(jiān)持以公有制為主體，堅(jiān)持以按勞分配為主體，堅(jiān)持以實(shí)現(xiàn)共同富裕為目標(biāo)。社會(huì)主義市場(chǎng)經(jīng)濟(jì)體制是社會(huì)主義基本制度與市場(chǎng)經(jīng)濟(jì)的結(jié)合。一是在所有制結(jié)構(gòu)上，以公有制為主體，多種所有制經(jīng)濟(jì)共同發(fā)展，一切符合“三個(gè)有利于”標(biāo)準(zhǔn)的所有制形式都可以而且應(yīng)該用來(lái)為社會(huì)主義服務(wù)。二是在宏觀調(diào)控上，以實(shí)現(xiàn)最廣大勞動(dòng)人民利益為出發(fā)點(diǎn)和歸宿，社會(huì)主義國(guó)家能夠把人民的當(dāng)前利益與長(zhǎng)遠(yuǎn)利益，局部利益與整體利益結(jié)合起來(lái)，使市場(chǎng)在社會(huì)主義國(guó)家宏觀調(diào)控下對(duì)資源配置起基礎(chǔ)性作用，更好的發(fā)揮計(jì)劃和市場(chǎng)兩種手段的長(zhǎng)處。

聯(lián)系和區(qū)別:社會(huì)主義市場(chǎng)經(jīng)濟(jì)體制是社會(huì)主義基本制度與市場(chǎng)經(jīng)濟(jì)的結(jié)合。一方面，它必然體現(xiàn)社會(huì)主義的制度特征，另一方面，它又具有市場(chǎng)經(jīng)濟(jì)的一般特征。市場(chǎng)經(jīng)濟(jì)與社會(huì)主義制度結(jié)合。就要堅(jiān)持以公有制為主體，堅(jiān)持以按勞分配為主體，堅(jiān)持以實(shí)現(xiàn)共同富裕為目標(biāo)。市場(chǎng)經(jīng)濟(jì)是一種以市場(chǎng)手段為主的資源配置方式，不屬于社會(huì)經(jīng)濟(jì)制度的范疇。與社會(huì)主義基本制度相結(jié)合而形成的社會(huì)主義市場(chǎng)經(jīng)濟(jì)體制，在所有制結(jié)構(gòu)，分配制度和宏觀調(diào)控上具有自身的特征。

4、社會(huì)主義初級(jí)階段的基本經(jīng)濟(jì)制度，公有制經(jīng)濟(jì)成分、主體地位、實(shí)現(xiàn)形式。

基本經(jīng)濟(jì)制度：以公有制為主體，多種所有制經(jīng)濟(jì)共同發(fā)展是我國(guó)社會(huì)主義初級(jí)階段的一項(xiàng)基本經(jīng)濟(jì)制度。經(jīng)濟(jì)成分：國(guó)有經(jīng)濟(jì)和集體經(jīng)濟(jì)，混合所有制經(jīng)濟(jì)中的國(guó)有成分和集體成分。

主體地位：主體地位主要體現(xiàn)在：一是公有資產(chǎn)在社會(huì)總資產(chǎn)中占優(yōu)勢(shì)；二是國(guó)有經(jīng)濟(jì)控制國(guó)民經(jīng)濟(jì)命脈，對(duì)經(jīng)濟(jì)發(fā)展起主導(dǎo)作用。國(guó)有經(jīng)濟(jì)起主導(dǎo)作用，主要體現(xiàn)在控制力上。

實(shí)現(xiàn)形式：公有制的實(shí)現(xiàn)形式可以而且應(yīng)當(dāng)多樣化，一切反應(yīng)社會(huì)化生產(chǎn)規(guī)律的經(jīng)營(yíng)方式和組織形式都可以大膽利用。要大力發(fā)展國(guó)有資本，集體資本和非公有資本等參股的混合所有制經(jīng)濟(jì)，實(shí)現(xiàn)投資主體的多元化，使股份制成為公有制的主要實(shí)現(xiàn)形式。

5、社會(huì)主義初級(jí)階段的基本分配制度。

社會(huì)主義初級(jí)階段的基本分配制度是按勞分配為主體、多種分配方式并存的分配制度

6、建設(shè)創(chuàng)新型國(guó)家，科技是關(guān)鍵，人才是核心，教育是基礎(chǔ)。206頁(yè)

科技人才是提高自主創(chuàng)新能力的關(guān)鍵所在。我們要進(jìn)一步營(yíng)造鼓勵(lì)創(chuàng)新的環(huán)境，努力造就世界一流科學(xué)家和科技領(lǐng)軍人才，注重培養(yǎng)一線的創(chuàng)新人才，使全社會(huì)創(chuàng)新智慧迸發(fā)、各方面創(chuàng)新人才大量涌現(xiàn)，形成強(qiáng)大的自主創(chuàng)新能力，支持我國(guó)經(jīng)濟(jì)社會(huì)發(fā)展，實(shí)現(xiàn)2020年進(jìn)入創(chuàng)新型國(guó)家行列的目標(biāo)。

7、中國(guó)特色新型工業(yè)化道路，新在哪里？207頁(yè)

新型工業(yè)化道路的“新”，就在于它同信息化等現(xiàn)代高科技發(fā)展緊密結(jié)合；注重經(jīng)濟(jì)發(fā)展同資源環(huán)境相協(xié)調(diào)；堅(jiān)持城鄉(xiāng)協(xié)調(diào)發(fā)展；實(shí)現(xiàn)資金技術(shù)密集型產(chǎn)業(yè)同勞動(dòng)密集型相結(jié)合。

8、“三農(nóng)”問(wèn)題與建設(shè)社會(huì)主義新農(nóng)村的總要求。211頁(yè)

建設(shè)社會(huì)主義新農(nóng)村的總要求是生產(chǎn)發(fā)展、生活寬裕、鄉(xiāng)風(fēng)文明、村容整潔、管理民主。

生產(chǎn)發(fā)展，是新農(nóng)村建設(shè)的中心環(huán)節(jié)，是實(shí)現(xiàn)其他目標(biāo)的物質(zhì)基礎(chǔ)。生活寬裕，是新農(nóng)村建設(shè)的目的，也是衡量我們工作的基本尺度。鄉(xiāng)風(fēng)文明，是農(nóng)民素質(zhì)的反應(yīng)，體現(xiàn)農(nóng)村精神文明建設(shè)的要求。村容整潔，是展現(xiàn)農(nóng)村新貌的窗口，是實(shí)現(xiàn)人與環(huán)境和諧發(fā)展的必然要求。管理民主，是新農(nóng)村建設(shè)的政治保證，顯示了對(duì)農(nóng)民群眾政治權(quán)利的尊重和維護(hù)。

9、社會(huì)主義民主政治的本質(zhì)，中國(guó)的國(guó)體與政體。

社會(huì)主義民主政治的本質(zhì)：： 解放生產(chǎn)力，發(fā)展生產(chǎn)力，消滅剝削，消除兩極分化，最終達(dá)到共同富裕。中國(guó)國(guó)體與政體：工人階級(jí)領(lǐng)導(dǎo)的、以工農(nóng)聯(lián)盟為基礎(chǔ)的人民民主專政，政體是人民代表大會(huì)制度。

10、中國(guó)的基本政黨制度的特點(diǎn)和特色

特點(diǎn)和特色：共產(chǎn)黨執(zhí)政，多黨派參政，共產(chǎn)黨領(lǐng)導(dǎo)，多黨派合作

附：中國(guó)基本政黨制度：中國(guó)共產(chǎn)黨領(lǐng)導(dǎo)下的多黨合作和政治協(xié)商制度。

基本內(nèi)容：第一，中國(guó)共產(chǎn)黨是執(zhí)政黨，中國(guó)共產(chǎn)黨和各民主黨派是親密友黨。第二，中國(guó)共產(chǎn)黨和各民主黨派合作的政治基礎(chǔ)是堅(jiān)持中國(guó)共產(chǎn)黨的領(lǐng)導(dǎo)和堅(jiān)持四項(xiàng)基本原則。第三，中國(guó)共產(chǎn)黨和各民主黨派合作的基本方針是“長(zhǎng)期共存、互相監(jiān)督、肝膽相照、榮辱與共”。第四，中國(guó)共產(chǎn)黨和各民主黨派以憲法和法律為根本活動(dòng)準(zhǔn)則。

11、我國(guó)的民族區(qū)域制度和處理民族關(guān)系問(wèn)題的基本原則。

堅(jiān)持實(shí)行各民族平等、團(tuán)結(jié)、合作和共同繁榮的原則（書(shū)上）平等團(tuán)結(jié)互助和諧（網(wǎng)上）

12、中國(guó)基層民主制度及其三大基本類型和特點(diǎn)。

農(nóng)村基層民主政治

城市社區(qū)民主政治建設(shè)

職工代表大會(huì)制度建設(shè)

特點(diǎn)自我管理 自我教育 自我服務(wù)

不知道正確與否你看看吧

13、社會(huì)主義法制建設(shè)的基本要求（16字概括）。

答：有法可依，有法必依，執(zhí)法必嚴(yán)，違法必究（P238）

14、結(jié)合實(shí)際，如何認(rèn)識(shí)社會(huì)主義社會(huì)的民主、自由和人權(quán)？

答：1：“民主”，由“人民”和“權(quán)力”兩詞合成，意為“人民的政權(quán)”，是人民當(dāng)家作主的意思?！懊裰鳌笔钦?quán)的一種構(gòu)成形式。

2：“自由”通常是講政治自由，主要是指公民在法律范圍內(nèi)參與國(guó)家政治生活的一種權(quán)利，“自由”是政權(quán)給予公民的政治權(quán)利。

3：“人權(quán)“泛指人身自由和其他民主權(quán)利，主要包括生存權(quán)，發(fā)展權(quán)，經(jīng)濟(jì)權(quán)，文化權(quán)等。公民在政治上應(yīng)該享有的自由和民主權(quán)利，一般被稱作“人權(quán)”。（P242）

15、中國(guó)特色社會(huì)主義文化建設(shè)的根本任務(wù)和基本方針。

答：根本任務(wù)：就是以馬克思列寧主義，毛澤東思想，鄧小平理論和“三個(gè)代表”重要思想為指導(dǎo)，全面貫徹科學(xué)發(fā)展觀，著力培育有理想，有道德，有文化，有紀(jì)律的公民，切實(shí)提高全民族的思想道德素質(zhì)和科學(xué)文化素質(zhì)。（P251）

基本方針：1：堅(jiān)持以馬克思主義為指導(dǎo)，為人民服務(wù)，為社會(huì)主義服務(wù)。

2：堅(jiān)持百花齊放，百家爭(zhēng)鳴的方針。

3堅(jiān)持貼近實(shí)際，貼近生活，貼近群眾，不斷推進(jìn)文化創(chuàng)新。

4：堅(jiān)持立足當(dāng)代又繼承民族優(yōu)秀文化傳統(tǒng)，立足本國(guó)又充分吸收世界優(yōu)秀文化成果。

5：堅(jiān)持一手抓繁榮，一手抓管理。(P253)

16、社會(huì)主義核心價(jià)值體系及其基本內(nèi)容。

社會(huì)主義核價(jià)值體系是社會(huì)主義制度在價(jià)值層面的本質(zhì)規(guī)定，是全黨全國(guó)各族人民團(tuán)結(jié)奮斗的共同思想基礎(chǔ)，是實(shí)現(xiàn)科學(xué)發(fā)展觀、社會(huì)和諧的推動(dòng)力量，是國(guó)家文化軟實(shí)力的核心內(nèi)容，反映了我國(guó)社會(huì)主義基本制度的本質(zhì)要求。建設(shè)社會(huì)主義核心價(jià)值體系，是黨在思想文化建設(shè)上的一個(gè)重大理論創(chuàng)新和重大戰(zhàn)略任務(wù)。對(duì)于建設(shè)社會(huì)主義精神文明，為發(fā)展中國(guó)特色社會(huì)主義提供強(qiáng)大精神動(dòng)力和思想保證，具有重大意義。推動(dòng)社會(huì)主義文化大發(fā)展大繁榮，必須把建設(shè)社會(huì)主義核心價(jià)值體系作為第一位的任務(wù)，努力在全社會(huì)形成統(tǒng)一的指導(dǎo)思想，共同的理想信念，強(qiáng)大的精神支柱和基本的道德規(guī)范，增強(qiáng)社會(huì)主義意識(shí)形態(tài)的吸引力和凝聚力。

基本內(nèi)容：包括馬克思主義指導(dǎo)思想、中國(guó)特色社會(huì)主義共同理想、以愛(ài)國(guó)主義為核心的民族精神和以改革創(chuàng)新為核心時(shí)代精神、社會(huì)主義榮辱觀。

17、社會(huì)主義和諧社會(huì)的6大特征（或基本要求）及建設(shè)方針和舉措。

我們所要建設(shè)的社會(huì)主義和諧社會(huì)，應(yīng)該是民主法治、公平正義、誠(chéng)信有愛(ài)、充滿活力、安定有序、人與自然和諧相處的社會(huì)。

民主法治，就是社會(huì)主義民主得到充分發(fā)揚(yáng)，依法治國(guó)基本方略得到切實(shí)落實(shí)，在各方面積極因素得到廣泛調(diào)動(dòng)。

公平正義，就是社會(huì)各個(gè)方面的利益關(guān)系得到妥善協(xié)調(diào)，人民內(nèi)部矛盾和其他社會(huì)矛盾得到正確處理，社會(huì)公平和正義得到切實(shí)維護(hù)和實(shí)現(xiàn)。

誠(chéng)信友愛(ài)，就是全社會(huì)互幫互助、誠(chéng)實(shí)守信、全體人民平等友愛(ài)、融洽相處。

充滿活力，就是能夠使一切有利于社會(huì)進(jìn)步的創(chuàng)造愿望得到尊重，創(chuàng)造活動(dòng)得到支持，創(chuàng)造才能得到發(fā)揮，創(chuàng)造成果得到肯定。

安定有序，就是社會(huì)組織機(jī)制健全，社會(huì)管理完善，社會(huì)秩序良好，人民群眾安居樂(lè)業(yè)，社會(huì)保持安定團(tuán)結(jié)。

人與自然和諧相處，就是生產(chǎn)發(fā)展，生活富裕，生態(tài)良好。

建設(shè)方針和舉措：1.必須堅(jiān)持以馬克思列寧主義，毛澤東思想，鄧小平理論和“三個(gè)代表”重要思想為指導(dǎo)；2.必須堅(jiān)持以人為本；3，堅(jiān)持科學(xué)發(fā)展；4.堅(jiān)持改革開(kāi)放；5.堅(jiān)持民主法治；6。堅(jiān)持正確處理改革發(fā)展穩(wěn)定的關(guān)系；7.堅(jiān)持在黨的領(lǐng)帶下全社會(huì)共同建設(shè)；

18、1949年來(lái)，我國(guó)大陸對(duì)臺(tái)灣問(wèn)題解決的基本政策方針演變的幾個(gè)階段和特點(diǎn)。

1、武力解決

2、和平解決

3、一國(guó)兩制的提出

武力解決的特點(diǎn)：有堅(jiān)決解放臺(tái)灣的決心；受到美國(guó)軍事干涉和占領(lǐng)臺(tái)灣的威脅；人民解放軍炮擊金門，向國(guó)際社會(huì)，特別是向美國(guó)表明中國(guó)人民解放臺(tái)灣的決心和立場(chǎng)；中國(guó)人民解放軍發(fā)到渡海戰(zhàn)役。解放了一江山島和大陳島

和平解決的特點(diǎn)：國(guó)際形勢(shì)緩和，亞太地區(qū)國(guó)家希望和平的呼聲高漲；國(guó)內(nèi)正在進(jìn)行社會(huì)主義改造和第一個(gè)五年計(jì)劃的經(jīng)濟(jì)建設(shè)，需要一個(gè)和平的國(guó)際環(huán)境，開(kāi)展社會(huì)主義建設(shè)；臺(tái)灣局勢(shì)發(fā)生變化。美蔣在合作中出現(xiàn)矛盾；我們黨對(duì)解決臺(tái)灣問(wèn)題又提出了許多重要原則，促進(jìn)對(duì)臺(tái)灣的和平解決

一國(guó)兩制的特點(diǎn)：一個(gè)中國(guó)；兩制并存；高度自治；盡最大努力爭(zhēng)取和平統(tǒng)一，但不承諾放棄使用武力；解決臺(tái)灣問(wèn)題，實(shí)現(xiàn)祖國(guó)的完全統(tǒng)一，寄希望于臺(tái)灣人民；積極促談，爭(zhēng)取通過(guò)談判實(shí)現(xiàn)統(tǒng)一；積極促進(jìn)兩岸“三通”和各項(xiàng)交流，增進(jìn)兩岸同胞的相互了解和感情，密切兩岸經(jīng)濟(jì)，文化關(guān)系，為實(shí)現(xiàn)和平統(tǒng)一創(chuàng)造條件；堅(jiān)決反對(duì)任何“臺(tái)灣獨(dú)立”的言行；堅(jiān)決反對(duì)外國(guó)勢(shì)力插手和干涉臺(tái)灣問(wèn)題；集中力量搞好經(jīng)濟(jì)建設(shè)，是解決國(guó)際國(guó)內(nèi)問(wèn)題的基礎(chǔ)，也是實(shí)現(xiàn)國(guó)家統(tǒng)一的基礎(chǔ)。

19、“和平統(tǒng)一、一國(guó)兩制”構(gòu)想的內(nèi)涵及其基本內(nèi)容。

基本內(nèi)容：（1）一個(gè)中國(guó)（2）兩制并存（3）高度自治（4）盡最大努力爭(zhēng)取和平統(tǒng)一，但不承諾放棄武力。

（5）解決臺(tái)灣問(wèn)題，實(shí)現(xiàn)祖國(guó)的完全統(tǒng)一，寄希望于臺(tái)灣人民。（6）積極促談，爭(zhēng)取通過(guò)談判實(shí)現(xiàn)統(tǒng)一。

（7）積極促進(jìn)兩岸“三通”和各項(xiàng)交流，增進(jìn)兩岸同胞的相互了解和感情，密切兩岸經(jīng)濟(jì)、文化關(guān)系，為實(shí)現(xiàn)和平統(tǒng)一創(chuàng)造條件。（8）堅(jiān)決反對(duì)任何“臺(tái)灣獨(dú)立”的言行。（9）堅(jiān)決反對(duì)任何外國(guó)勢(shì)力插手和干涉臺(tái)灣問(wèn)題。（10）集中力量搞好經(jīng)濟(jì)建設(shè)，是解決國(guó)際國(guó)內(nèi)問(wèn)題的基礎(chǔ)，也是實(shí)現(xiàn)國(guó)家統(tǒng)一的基礎(chǔ)。內(nèi)涵：“和平統(tǒng)一、一國(guó)兩制”構(gòu)想是充分尊重歷史和現(xiàn)實(shí)、照顧各方面利益、維護(hù)民族團(tuán)結(jié)、實(shí)現(xiàn)祖國(guó)完

全統(tǒng)一和民族偉大復(fù)興的科學(xué)構(gòu)想。“一國(guó)兩制”是中華民族對(duì)人類政治文明的獨(dú)特貢獻(xiàn)。“和平統(tǒng)一、一國(guó)兩制”構(gòu)想豐富了馬克思主義，具有重大意義。

第一，“和平統(tǒng)一、一國(guó)兩制”構(gòu)想創(chuàng)造性地把和平共處原則用之于解決一個(gè)國(guó)家的統(tǒng)一問(wèn)題。

第二，“和平統(tǒng)一、一國(guó)兩制”構(gòu)想創(chuàng)造性地發(fā)展了馬克思主義的國(guó)家學(xué)說(shuō)。

第三，“和平統(tǒng)一、一國(guó)兩制”構(gòu)想體現(xiàn)了既堅(jiān)持祖國(guó)統(tǒng)一、維護(hù)國(guó)家主權(quán)的原則堅(jiān)定性，也體現(xiàn)了照

顧歷史實(shí)際和現(xiàn)實(shí)可能的策略靈活性，可以避免武力統(tǒng)一會(huì)造成的不良后果。

第四，“和平統(tǒng)一、一國(guó)兩制”構(gòu)想有利于爭(zhēng)取社會(huì)主義現(xiàn)代化建設(shè)事業(yè)所需要的和平的國(guó)際環(huán)境與國(guó)

內(nèi)環(huán)境。

第五，“和平統(tǒng)一、一國(guó)兩制”構(gòu)想為解決國(guó)際爭(zhēng)端和歷史遺留問(wèn)題提供了新的思路。（P302-305）

20、當(dāng)今世界時(shí)代主題和總體特征。

時(shí)代主題：和平與發(fā)展

總體特征:(1)世界多極化在曲折中發(fā)展(2)經(jīng)濟(jì)全球化趨勢(shì)深入發(fā)展

21、新中國(guó)成立以來(lái)，我國(guó)獨(dú)立自主和平外交政策的演變階段及其特點(diǎn)。

新中國(guó)成立初期：毛澤東提出“另起爐灶”、“打掃干凈屋子再請(qǐng)客”、“一邊倒”三大外交方針。特點(diǎn)：

這三大方針，符合中國(guó)人民實(shí)現(xiàn)國(guó)家安全、獨(dú)立和維護(hù)世界和平的根本利益，為獨(dú)立自主的新中國(guó)外交關(guān)系奠定了基礎(chǔ)。

1955年萬(wàn)隆會(huì)議：周恩來(lái)提出來(lái)互相尊重主權(quán)和領(lǐng)土完整、互不侵犯、互不干涉內(nèi)政、平等互利、和平

共處這五項(xiàng)基本原則。特點(diǎn)：和平共處五項(xiàng)原則成為我國(guó)處理對(duì)外關(guān)系的基本準(zhǔn)則。

20世紀(jì)60年代：我國(guó)外交政策重心由“一邊倒”調(diào)整為同時(shí)反對(duì)美蘇兩個(gè)超級(jí)大國(guó)到處侵略擴(kuò)張、肆

意干涉別國(guó)內(nèi)政的霸權(quán)主義政策。特點(diǎn)：積極支持民族解放運(yùn)動(dòng)，堅(jiān)持睦鄰友好，維護(hù)中國(guó)的主權(quán)和領(lǐng)土完整，維護(hù)世界的進(jìn)步與和平。

20世紀(jì)70年代：毛澤東提出“一條線”的外交戰(zhàn)略。特點(diǎn)：這是我國(guó)外交的一次重大戰(zhàn)略調(diào)整，對(duì)緩

解和我國(guó)面臨的緊張局勢(shì)，維護(hù)世界和平與穩(wěn)定，保障中國(guó)人民和世界人民的根本利益發(fā)揮了重要作用。20世紀(jì)80年代：堅(jiān)持獨(dú)立自主，主張一切從中國(guó)人民和世界人民的根本利益出發(fā)，在國(guó)際上保持自己的獨(dú)立地位，不與任何大國(guó)和國(guó)家集團(tuán)結(jié)盟，奉行真正的不結(jié)盟政策。特點(diǎn)：是我國(guó)對(duì)外政策和外交政策的重大調(diào)整，在新時(shí)期繼承和發(fā)展了毛澤東的外交思想。

冷戰(zhàn)結(jié)束后：江澤民繼承和發(fā)展了鄧小平外交思想，繼續(xù)開(kāi)創(chuàng)我國(guó)外交工作新局面。

黨的十六大以來(lái)：高舉和平、發(fā)展、合作的旗幟，堅(jiān)持獨(dú)立自主的外交政策。特點(diǎn)：中國(guó)主張國(guó)際關(guān)

系民主化和發(fā)展模式多樣化，積極推動(dòng)經(jīng)濟(jì)全球化朝著有利于實(shí)現(xiàn)共同繁榮的方向發(fā)展，推動(dòng)國(guó)際秩序向公正合理的方向發(fā)展，為推動(dòng)建設(shè)持久和平、共同繁榮的世界作出貢獻(xiàn)，（P327-330）

22、我國(guó)外交政策的原則和宗旨。

基本原則：第一，堅(jiān)持獨(dú)立自主地處理一切國(guó)際事務(wù)的原則。

第二，堅(jiān)持和平共處五項(xiàng)基本原則為指導(dǎo)國(guó)家間關(guān)系的基本準(zhǔn)則。

第三，堅(jiān)持同發(fā)展中國(guó)家加強(qiáng)團(tuán)結(jié)與合作的原則。

第四，堅(jiān)持愛(ài)國(guó)主義與履行國(guó)際義務(wù)相統(tǒng)一的原則。

宗旨：維護(hù)世界和平，促進(jìn)共同發(fā)展。（P330-332）

23、中國(guó)特色社會(huì)主義事業(yè)的依靠力量包括哪些？出現(xiàn)什么新變化和特點(diǎn)？

工人階級(jí)是國(guó)家的領(lǐng)導(dǎo)階級(jí)，是中國(guó)特色社會(huì)主義事業(yè)的領(lǐng)導(dǎo)力量；

農(nóng)民階級(jí)是人數(shù)最多的基本依靠力量，農(nóng)業(yè)、農(nóng)村、農(nóng)民問(wèn)題的重要性決定了農(nóng)民階級(jí)的重要地位； 知識(shí)分子是中國(guó)工人階級(jí)的一部分?？茖W(xué)技術(shù)的作用決定了知識(shí)分子的重要地位；

中國(guó)人民解放軍是建設(shè)中國(guó)特色社會(huì)主義的重要力量；

新變化和特點(diǎn)：改革開(kāi)放以來(lái)，我國(guó)工人階級(jí)隊(duì)伍發(fā)生了明顯變化，一是隊(duì)伍迅速壯大；二是內(nèi)部結(jié)構(gòu)發(fā)生重大變化；三是崗位流動(dòng)加快。改革開(kāi)放以來(lái)，我國(guó)出現(xiàn)了一些新的社會(huì)階層，主要有：民營(yíng)科技企業(yè)的創(chuàng)業(yè)人員和技術(shù)人員，個(gè)體戶，私營(yíng)企業(yè)主，自由職業(yè)人員等。在黨的領(lǐng)導(dǎo)下，廣大農(nóng)民表現(xiàn)出了可貴的創(chuàng)業(yè)革新精神，實(shí)行了以家庭聯(lián)產(chǎn)承包為主要內(nèi)容的責(zé)任制，農(nóng)民改革和建設(shè)取得巨大成就，帶動(dòng)了整個(gè)國(guó)家的改革和建設(shè)事業(yè)。改革開(kāi)放和現(xiàn)代化建設(shè)符合廣大農(nóng)民的根本利益，他們衷心擁護(hù)建設(shè)中國(guó)特色社會(huì)主義的路線，方針和政策，成為改革開(kāi)放和現(xiàn)代化建設(shè)的一支重要依靠力量。

24、如何認(rèn)識(shí)新時(shí)期愛(ài)國(guó)統(tǒng)一戰(zhàn)線的性質(zhì)、特點(diǎn)、構(gòu)成、基本任務(wù)及領(lǐng)導(dǎo)權(quán)問(wèn)題。

新時(shí)期愛(ài)國(guó)統(tǒng)一戰(zhàn)線的性質(zhì)是建立在社會(huì)主義和愛(ài)國(guó)主義基礎(chǔ)上的，是社會(huì)主義性質(zhì)的統(tǒng)一戰(zhàn)線； 特點(diǎn)是：具有空前的廣泛性，是最廣泛的愛(ài)國(guó)統(tǒng)一戰(zhàn)線；

構(gòu)成是：一個(gè)是大陸范圍內(nèi)，以愛(ài)國(guó)主義和社會(huì)主義為政治基礎(chǔ)的團(tuán)結(jié)全體勞動(dòng)者、建設(shè)者和愛(ài)國(guó)者的聯(lián)盟，這是統(tǒng)一戰(zhàn)線的主體和基礎(chǔ)；一個(gè)是大陸范圍以外的，以愛(ài)國(guó)和擁護(hù)祖國(guó)統(tǒng)一為政治基礎(chǔ)的團(tuán)結(jié)臺(tái)灣同胞、港澳同胞和海外僑胞的聯(lián)盟，這是統(tǒng)一戰(zhàn)線的重要組成部分；

基本任務(wù)：高舉愛(ài)國(guó)主義、社會(huì)主義旗幟，團(tuán)結(jié)一切可以團(tuán)結(jié)的力量，調(diào)動(dòng)一切積極因素，化消極因素為積極因素，為促進(jìn)社會(huì)主義經(jīng)濟(jì)建設(shè)、政治建設(shè)、文化建設(shè)、社會(huì)建設(shè)服務(wù)，為促進(jìn)香港、澳門長(zhǎng)期繁榮穩(wěn)定和祖國(guó)和平統(tǒng)一服務(wù)，為維護(hù)世界和平、促進(jìn)共同發(fā)展服務(wù)。

堅(jiān)持黨對(duì)統(tǒng)一戰(zhàn)線的領(lǐng)導(dǎo)權(quán)是鞏固與發(fā)展統(tǒng)一戰(zhàn)線的根本保證。

25、結(jié)合當(dāng)前中國(guó)海疆主權(quán)維護(hù)，談一談對(duì)中國(guó)加強(qiáng)國(guó)防和軍隊(duì)建設(shè)的認(rèn)識(shí)。

中國(guó)維護(hù)海洋權(quán)益的形勢(shì)依然嚴(yán)峻。當(dāng)前中國(guó)海洋安全形勢(shì)處于相對(duì)和平態(tài)勢(shì)，但不確定的因素仍然存在，各國(guó)之間力量的角逐日趨激烈。中國(guó)大陸周邊海洋形勢(shì)相對(duì)平穩(wěn)，黃海形勢(shì)穩(wěn)中有憂，東海形勢(shì)突破與挑戰(zhàn)并存，南海形勢(shì)復(fù)雜多變。在南海，目前南沙群島的安全問(wèn)題尤為突出，中國(guó)與東南亞國(guó)家的南海之爭(zhēng)，表面上看是島礁之爭(zhēng)，實(shí)質(zhì)是資源之爭(zhēng)。在東南亞地區(qū)，南沙群島爭(zhēng)端解決沒(méi)有實(shí)質(zhì)性進(jìn)展，中國(guó)“島礁被侵占、海域被瓜分、資源被掠奪”的狀況沒(méi)有改觀。

加強(qiáng)國(guó)防和軍隊(duì)建設(shè)，是發(fā)展中國(guó)特色社會(huì)主義的戰(zhàn)略任務(wù)，是維護(hù)我國(guó)主權(quán)和領(lǐng)土完整的保證，是我國(guó)和平共處原則外交政策的體現(xiàn)，必須統(tǒng)籌經(jīng)濟(jì)建設(shè)和國(guó)防建設(shè)，在推進(jìn)現(xiàn)代化事業(yè)進(jìn)程中實(shí)現(xiàn)富國(guó)和強(qiáng)軍的統(tǒng)一。要堅(jiān)持以毛澤東軍事思想、鄧小平新時(shí)期軍隊(duì)建設(shè)思想、江澤民國(guó)防和軍隊(duì)建設(shè)思想為指導(dǎo)，認(rèn)真落實(shí)胡錦濤同志關(guān)于新形勢(shì)下國(guó)防和軍隊(duì)建設(shè)重要論述，把科學(xué)發(fā)展觀作為國(guó)防和軍隊(duì)建設(shè)的重要指導(dǎo)方針。著眼全面履行新世紀(jì)新階段軍隊(duì)歷史使命，提高軍隊(duì)?wèi)?yīng)對(duì)多種安全威脅、完成多樣化軍事任務(wù)的能力，堅(jiān)決維護(hù)國(guó)家主權(quán)、安全和領(lǐng)土完整，為全面建設(shè)小康社會(huì)提供強(qiáng)有力的保障。加強(qiáng)人民武裝警察部隊(duì)建設(shè)，提高執(zhí)勤、處置突發(fā)事件、反恐維穩(wěn)的能力。加強(qiáng)國(guó)防教育，增強(qiáng)全民國(guó)防觀念。完善國(guó)防動(dòng)員體系。鞏固軍政軍民團(tuán)結(jié)。

26、如何正確認(rèn)識(shí)中國(guó)共產(chǎn)黨的性質(zhì)和宗旨？

.中國(guó)共產(chǎn)黨是中國(guó)工人階級(jí)的先鋒隊(duì)，同時(shí)是中國(guó)人民和中華民族的先鋒隊(duì)，是中國(guó)特色社會(huì)主義事業(yè)的領(lǐng)導(dǎo)核心，代表中國(guó)先進(jìn)生產(chǎn)力的發(fā)展要求，代表中國(guó)先進(jìn)文化的前進(jìn)方向，代表中國(guó)最廣大人民的根本利益。黨的最高理想和最終目標(biāo)是實(shí)現(xiàn)共產(chǎn)主義。

中國(guó)共產(chǎn)黨的性質(zhì)決定了一切從人民的利益出發(fā)，全心全意為人民服務(wù)是它的唯一宗旨。黨的階級(jí)性和先進(jìn)性，決定我們黨必須為工人階級(jí)和人民群眾謀利益。無(wú)產(chǎn)階級(jí)革命就是要消滅一切剝削制度和產(chǎn)生剝削的根源，解放全人類。作為工人階級(jí)先鋒隊(duì)的中國(guó)共產(chǎn)黨從它誕生之日起，就是中國(guó)各族人民的忠實(shí)代表，就把全心全意為人民服務(wù)看作是根本宗旨。黨在任何時(shí)候都把群眾利益放在第一位，在工作中實(shí)行群眾路線，一切為了群眾，一切依靠群眾，從群眾中來(lái)，到群眾中去，堅(jiān)持不懈地反對(duì)腐敗，加強(qiáng)黨風(fēng)建設(shè)和廉政建設(shè)。

27、如何全面推進(jìn)和加強(qiáng)黨的建設(shè)？

黨的建設(shè)偉大工程同黨領(lǐng)導(dǎo)的偉大事業(yè)緊密地聯(lián)系在一起。在新世紀(jì)新階段，要把全體人民的意志和力量凝聚起來(lái)，全面建設(shè)小康社會(huì)，加快推進(jìn)社會(huì)主義現(xiàn)代化，必須以加強(qiáng)黨的執(zhí)政能力建設(shè)和黨的先進(jìn)性建設(shè)為主線，以改革創(chuàng)新精神全面推進(jìn)黨的建設(shè)新的偉大工程。堅(jiān)持立黨為公，執(zhí)政為民，保持黨同人民群眾的血肉聯(lián)系。

28、如何看待和預(yù)防中國(guó)共產(chǎn)黨內(nèi)出現(xiàn)的腐敗現(xiàn)象？

是由于個(gè)別干部脫離群眾，濫用權(quán)力為謀小集團(tuán)或個(gè)人的私利，中國(guó)共產(chǎn)黨堅(jiān)決預(yù)防和反腐敗。

注重制度建設(shè)，從源頭上防腐。嚴(yán)格執(zhí)行黨風(fēng)廉政建設(shè)責(zé)任制。堅(jiān)持深化改革和創(chuàng)新體制，加強(qiáng)廉政文化建設(shè)，形成拒腐防變教育長(zhǎng)效機(jī)制，反腐倡廉制度體系，權(quán)力運(yùn)行監(jiān)控機(jī)制。健全紀(jì)檢監(jiān)察派駐機(jī)構(gòu)統(tǒng)一管理，完善巡視制度。加強(qiáng)領(lǐng)導(dǎo)干部廉潔自律工作，提高黨員干部拒腐防變能力。

第四篇：《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)

《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)

期末考試僅限于期中考試以后的內(nèi)容：Chapter 7 Trees;Chapter 8 Topics in

graph theory.考試題型：計(jì)算題；簡(jiǎn)答題；證明題；構(gòu)造圖形（構(gòu)造滿足一定條件的圖，如：

6個(gè)頂點(diǎn)，11條邊且無(wú)Hamiltonian circuit）。題目共計(jì)6題，無(wú)選擇題和填空題。

考試難度：基本與期中考試相同，有一定數(shù)量的題直接來(lái)自于習(xí)題，最后一題較

難（構(gòu)造圖形）。

復(fù)習(xí)要點(diǎn)：基本概念及定義：

rooted tree;binary tree;labeled tree;positional tree;tree

searching;undirected tree;weighted graph;minimal spanning tree;(undirected)graph;degree;Euler path and Euler circuit;Hamiltonian path and Hamiltonian circuit;matching function;coloring graph;chromatic number;chromatic polynomial;planar graph;

基本內(nèi)容：

tree searching;the prefix(Polish form)and infix form of the

algebraic expression;minimal spanning tree;the sufficient-necessary condition for a graph G to have Euler circuit(or path);coloring graph;chromatic number;chromatic polynomial;construct a graph(directed or undirected)subject to some given conditions.不要求的內(nèi)容：

Computer representation of binary positional tree;searching general tree;algorithms.復(fù)習(xí)中如遇困難請(qǐng)聯(lián)系：錢建國(guó)***，jgqian@jingxian.xmu.edu.cn徐偉***

陳美潤(rùn)***

祝大家取得好成績(jī)！

第五篇：離散數(shù)學(xué)期末考試試題及答案

離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。下面是小編整理的離散數(shù)學(xué)期末考試試題及答案，歡迎閱讀參考！

一、【單項(xiàng)選擇題】

(本大題共15小題，每小題3分，共45分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在答題卷相應(yīng)題號(hào)處。

1、在由3個(gè)元素組成的集合上，可以有()種不同的關(guān)系。

[A] 3 [B] 8 [C]9 [D]272、設(shè)A1,2,3,5,8,B1,2,5,7,則AB()。

[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，則一定有()。

[A]X不屬于Y [B]X∈Y

[C]X真包含于 Y [D]X∩Y=X4、下列關(guān)系中是等價(jià)關(guān)系的是()。

[A]不等關(guān)系 [B]空關(guān)系

[C]全關(guān)系 [D]偏序關(guān)系

5、對(duì)于一個(gè)從集合A到集合B的映射，下列表述中錯(cuò)誤的是()。

[A]對(duì)A的每個(gè)元素都要有象 [B] 對(duì)A的每個(gè)元素都只有一個(gè)象

[C]對(duì)B的每個(gè)元素都有原象 [D] 對(duì)B的元素可以有不止一個(gè)原象

6、設(shè)p:小李努力學(xué)習(xí)，q:小李取得好成績(jī)，命題“除非小李努力學(xué)習(xí)，否則他不能取得好成績(jī)”的符號(hào)化形式為()。

[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、設(shè)A={a,b,c},則A到A的雙射共有()。

[A]3個(gè) [B]6個(gè) [C]8個(gè) [D]9個(gè)

8、一個(gè)連通G具有以下何種條件時(shí)，能一筆畫出：即從某結(jié)點(diǎn)出發(fā)，經(jīng)過(guò)中每邊僅一次回到該結(jié)點(diǎn)()。

[A] G沒(méi)有奇數(shù)度結(jié)點(diǎn) [B] G有1個(gè)奇數(shù)度結(jié)點(diǎn)

[C] G有2個(gè)奇數(shù)度結(jié)點(diǎn) [D] G沒(méi)有或有2個(gè)奇數(shù)度結(jié)點(diǎn)

9、設(shè)〈G,*〉是群，且|G|>1，則下列命題不成立的是()。

[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外無(wú)其他冪等元

10、令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為()

[A] p→┐q [B] p∨┐q

[C] p∧q [D] p∧┐q11、設(shè)G=的結(jié)點(diǎn)集為V={v1,v2,v3},邊集為E={,}.則G的割(點(diǎn))集是()。

[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}

12、下面4個(gè)推理定律中，不正確的為()。

[A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段論)

[C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式)

13、在右邊中過(guò)v1,v2的初級(jí)回路有多少條()

[A] 1 [B] 2 [C] 3 [D]

414、若R，是環(huán)，且R中乘法適合消去律，則R是()。

[A]無(wú)零因子環(huán)

[C]整環(huán) [B]除環(huán) [D]域

15、無(wú)向G中有16條邊，且每個(gè)結(jié)點(diǎn)的度數(shù)均為2，則結(jié)點(diǎn)數(shù)是()。

[A]8 [B]16 [C]4 [D]

32二、【判斷題】

(本大題共8小題，每小題3分，共24分)正確的填T，錯(cuò)誤的填F，填在答題卷相應(yīng)題號(hào)處。

16、是空集。()

17、設(shè)S,T為任意集合，如果S—T=，則S=T。()

18、在命題邏輯中，任何命題公式的主合取范式都是存在的，并且是唯一的。()

19、關(guān)系的復(fù)合運(yùn)算滿足交換律。()

20、集合A上任一運(yùn)算對(duì)A是封閉的。()

21、0,1,2,3,4,max,min是格。()

22、強(qiáng)連通有向一定是單向連通的。()

23、設(shè)都是命題公式，則(PQ)QP。()

三、【解答題】

(本大題共3小題，24、25每小題10分，26小題11分，共31分)請(qǐng)將答案填寫在答題卷相應(yīng)題號(hào)處。

24、設(shè)集合A={a, b, c}，B={b, d, e}，求

(1)BA;(2)AB;(3)A-B;(4)BA.25、設(shè)非空集合A，驗(yàn)證(P(A)，,~，A)是布爾代數(shù)

26、如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過(guò)DELPHI語(yǔ)言而且學(xué)過(guò)C++語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)言或者C++語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。

離散數(shù)學(xué)試題答案

一、【單項(xiàng)選擇題】(本大題共15小題，每小題3分，共45分)

BDDCCCBABDADCBB

二、【判斷題】(本大題共8小題，每小題3分，共24分)

FFTFTTTF

三、【解答題】(本大題共3小題，24、25每小題10分，26小題11分，共31分)

24、設(shè)集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.標(biāo)準(zhǔn)答案：(1)BA={a, b, c}{b, d, e}={ b }

(2)AB={a, b, c}{b, d, e}={a, b, c, d, e }

(3)A-B={a, b, c}-{b, d, e}={a, c}

(4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e }

復(fù)習(xí)范圍或考核目標(biāo)：考察集合的基本運(yùn)算，包括交集，并集,見(jiàn)課件第一章第二節(jié),集合的運(yùn)算。

25、設(shè)非空集合A，驗(yàn)證(P(A)，,~，A)是布爾代數(shù)

標(biāo)準(zhǔn)答案：證明 因?yàn)榧螦非空，故P(A)至少有兩個(gè)元素，顯然，是P(A)上的二元運(yùn)算.由定理10，任給B,C,DP(A), H1 BD=DC CD=DC

H2 B(CD)=(BC)(BD)B(CD)=(BC)(BD)

H3 P(A)存在和A，BP(A), 有B=B，BA=B

H4，BP(A), BA，存在A~B，有

BA~B)= A B(A～B)=

所以(P(A)，,~，A)是布爾代數(shù).復(fù)習(xí)范圍或考核目標(biāo)：考察布爾代數(shù)的基本概念，集合的運(yùn)算，見(jiàn)課件代數(shù)系統(tǒng)中布爾代數(shù)小節(jié)。

26、如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過(guò)DELPHI語(yǔ)言而且學(xué)過(guò)C++語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)言或者C++語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。

標(biāo)準(zhǔn)答案：令p：他是計(jì)算機(jī)系本科生

q：他是計(jì)算機(jī)系研究生 r：他學(xué)過(guò)DELPHI語(yǔ)言

s:他學(xué)過(guò)C++語(yǔ)言

t:他會(huì)編程序

前提：(p∨q)→(r∧s),(r∨s)→t

結(jié)論：p→t

證①p P(附加前提)

②p∨q T①I

③(p∨q)→(r∧s)P(前提引入)

④r∧s T②③I

⑤r T④I

⑥r(nóng)∨s T⑤I

⑦(r∨s)→t P(前提引入)

⑧t T⑤⑥I