第一篇：離散數學期末考試
一、單項選擇題（本大題共10小題，每小題2分，共20分）
1、設集合M={a，?}，N ={{a}，?}則M?N=（）。A、? B、{?} C、{a} D、{{a}，?，a}
2、設關系F={<1，a >，<2，2>，
A、{<1，b>，<1，c>，
B、{
D、{
3、設集合H={1，2，3，4}，則H上的關系R={
。x +y是偶數}具有（）A、自反性、反對稱性和傳遞性
B、反自反性、反對稱性和傳遞性
C、反自反性、對稱性和傳遞性
D、自反性、對稱性和傳遞性
4、設T是一棵完全二叉樹，則T的每個結點都（）。
A、至少有兩個子結點
B、至多有兩個子結點
C、恰有兩個子結點
D、可以有任意多個子結點
5、設R是實數集，“+，—，A、 ?>是群 B、 ? >是半群 D、 6、下面關系中，函數關系是（）。 A、{ B、{ D、{ 7、設 A、結合律 B、交換律 C、分配律 D、冪等律 8、設Z是整數集，“—”是整數減法，則下列說法正確的是（）。A、 B、 C、 D、 9、設L是無向圖G中的一條通路，L中的頂點各不相同，則L是一條（）。A、簡單通路 B、初級通路 C、簡單回路 D、初級回路 10、設G有6個3度點，2個4度點，其余頂點的度數均為0，則G的邊數是（）。A、10 B、13 C、11 D、6 二、填空題(本大題共8題，共10個空，每空2分，共20分) 1、設關系R={ 2、在代數系統 3、設集合M={1，2，3，5}，則M的冪集P（M）包含___________個元素。 4、設T是一棵有n(n?2)個頂點的樹，則T有_____________條邊。 5、設 6、設 7、設D是有向圖，若D的基圖是連通圖，則稱D是_________________圖 8、既不含________________也不含____________________的無向圖稱為簡單圖。 三、計算題(本大題共3小題，每小題10分，共30分) 1、用等值演算法求公式A=(p??q)?(p?r)的主析取范式。 2、求公式?x(Q(x)?G(x，s))?(?yP(y)??zH(y，z))的前束范式。 3、設集合A={1，2，3，4，5}，關系R={ R； （3）求偏序集 四、應用題(本大題共2小題，每小題5分，共10分) 1、用命題公式將下列命題符號化： 2和5是偶數，當且僅當5>2。 2、用謂詞公式將下列命題符號化： 每個計算機專業的學生都要學《編譯原理》，但有些計算機專業的學生不學《經濟學》。 五、證明題（本大題共2小題，每小題10分，共20分） 1、在命題邏輯系統中用歸結法證明下列推理是有效的： 前提：?s?q，p??q，s 結論：?p 2、在謂詞邏輯系統中寫出下列推理的（形式）證明： 前提：?x(M(x)?P(x))，?x(M(x)?G(x))，?x(?G(x))結論：?xP(x) 計算題 6.設命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。 7.(9分)設一階邏輯公式：G =(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.9.設R是集合A = {a, b, c, d}.R是A上的二元關系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)畫出r(R), s(R), t(R)的關系圖.11.通過求主析取范式判斷下列命題公式是否等價： (1)G =(P∧Q)∨(?P∧Q∧R) (2)H =(P∨(Q∧R))∧(Q∨(?P∧R))13.設R和S是集合A＝{a, b, c, d}上的關系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝ {(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關系矩陣；(2)計算R?S, R∪S, R1, S1?R1.－ － －證明題 1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊涵Q∨S。2.設A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊涵A→D。4.(本題10分)A, B為兩個任意集合，求證： A－(A∩B)=(A∪B)－B.答案： 1-5 BADBB 6-10 BBABB 1.{<1，a>，<1，2>， 環 三． ??(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是偶數；令q表示5是偶數；r表示5>2； (p?q)?r 2.S（x）：x是計算機專業的學生；G（x）：x要學《編譯原理》； F（x）：x學經濟學； ?x(S(x)?G(x))??x(S(x)??F(x)) 五 1，（1） s 前提引入（2） ?s?q 前提引入（3） q??s 置換規則 （4） q 1,3析取三段論（5） p??q 前提引入（6） ?p 4,5拒取 （1） ?x(M(x)?G(x)) 前提引入（2） M（x）v G（x） EI規則（3） ?x(?G(x)) 前提引入（4） ?G(x)（5） M(x) AI規則 2,4析取三段論 （6） ?x(M(x)?P(x)) 前提引入（7） M(x)→P（x） AI規則（8） P（x） 5,7假言推理（9） ?xP(x) EG規則 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) 關系圖: 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}蘊涵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}蘊涵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}蘊涵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. 離散數學試題(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名學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網球，還有2人會打這三種球。而6個會打網球的人都會打另外一種球，求不會打這三種球的人數（10分）。 解：A，B，C分別表示會打排球、網球和籃球的學生集合。則|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。不會打這三種球的人數25-20=5。 五、已知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） 六、已知R、S是N上的關系，其定義如下：R={ 解：R={ 七、設R={ 解：r(R)={ 12-1 2s(R)={ 八、證明整數集I上的模m同余關系R={ 證明：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）=fg（10分）。 1-1-14325證明：因為f、g是雙射，所以gf：A→C是雙射，所以gf有逆函數（gf）：C→A。同理可推fg：C→A是雙射。 因為 1-1 -1-1-1-1 -1-1-1 -1離散數學試題(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 四、只要今天天氣不好，就一定有考生不能提前進入考場，當且僅當所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好（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)?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是三個集合，證明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={ 七、設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>,<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>} 八、設R1是A上的等價關系，R2是B上的等價關系，A≠?且B≠?。關系R滿足：< 證明 對任意的 對任意的 5∈R，即 對任意的 綜上可得，R是A×B上的等價關系。 九、設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恒等函數，由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＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。－ 1－1 －1－1－1 －1離散數學試題(B卷答案3） 一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？(寫過程)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分）個體域為{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分）對于任意集合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)，由于上述過程可逆，故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分）設函數f：R×R?R×R，R為實數集，f定義為：f( 解：1）? 2）? ∈R×R，由f( ，通過計算可得x=(p+q)/2；y=(p-q)/2；從而 的原象存在，f是滿射。 八、（10分） 證明：1）?a，b∈G，a?b=a*u*b∈G，運算是封閉的。 2）?a，b，c∈G，（a?b）?c=（a*u*b）*u*c=a*u*（b*u*c）=a?（b?c），運算是可結合的。 3）?a∈G，設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，每個元素都有逆元。 所以 九、（10分）已知：D= 解：1）D的鄰接距陣A和可達距陣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分）求葉的權分別為2、4、6、8、10、12、14的最優二叉樹及其權。 解：最優二叉樹為 權＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148 離散數學試題(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在邊長為1的正方形內任意放置九個點，證明其中必存在三個點，使得由它們組成的三角形（可能是退化的）面積不超過1/8（10分）。 證明：把邊長為1的正方形分成四個全等的小正方形，則至少有一個小正方形內有三個點，它們組成的三角形（可能是退化的）面積不超過小正方形的一半，即1/8。 五、已知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） 六、?={A1，A2，?，An}是集合A的一個劃分，定義R={ 證明：?a∈A必有i使得a∈Ai，由定義知aRa，故R自反。?a,b∈A，若aRb，則a,b∈Ai，即b,a∈Ai，所以bRa，故R對稱。 ?a,b,c∈A，若aRb 且bRc，則a,b∈Ai及b,c∈Aj。因為i≠j時Ai∩Aj=?，故i=j，即a,b,c∈Ai，所以aRc，故R傳遞。 總之R是A上的等價關系。 七、若f:A→B是雙射，則f:B→A是雙射（15分）。 證明:對任意的x∈A，因為f是從A到B的函數，故存在y∈B，使 對任意的x∈A，若存在y1,y2∈B，使得 因此f是雙射。 八、設 證明 假設A≠G且B≠G，則存在a?A，a?B，且存在b?B，b?A（否則對任意的a?A，a?B，從而A?B，即A∪B＝B，得B＝G，矛盾。） 對于元素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。綜上所述，假設不成立，得證A＝G或B＝G。 九、若無向圖G是不連通的，證明G的補圖G是連通的（10分）。 證明 設無向圖G是不連通的，其k個連通分支為G1、G2、?、Gk。任取結點u、v∈G，若u和v不在圖G的同一個連通分支中，則[u，v]不是圖G的邊，因而[u，v] 1-1-1 -1-1-1-1是圖G的邊；若u和v在圖G的同一個連通分支中，不妨設其在連通分支Gi（1≤i≤k）中，在不同于Gi的另一連通分支上取一結點w，則[u，w]和[w，v]都不是圖G的邊，因而[u，w]和[w，v]都是G的邊。綜上可知，不管那種情況，u和v都是可達的。由u和v的任意性可知，G是連通的。 離散數學試題（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分）敘述并證明蘇格拉底三段論 解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：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是自反關系，所以 ?x、y∈A，若 ?x、y、z∈A，若 總之R∩S是等價關系。 2）因為x∈[a]R∩S? 五、(10分)設A＝{a，b，c，d}，R是A上的二元關系，且R＝{ 解 r(R)＝R∪IA＝{ t(R)＝?R＝{ 4232-1d>， 六、(15分)設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且? 證明：1）先證h是滿射。 ? 2）再證h是單射。 ? 到D的雙射，所以a1＝a2，c1＝c2，所以 綜合1）和2），h是雙射。 七、(12分)設 證明：? ?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上滿足結合律 ∴ 八、（10分）設G= 解：設G的每個結點的度數都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖的|E|≤3|V|-6矛盾，所以G至少有一個結點的度數小于等于5。九.G= 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）因為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 離散數學試題（B卷答案6） 一、（20分）用公式法判斷下列公式的類型：(1)(?P∨?Q)?(P??Q)(2)(P?Q)?(P∧?(Q∨?R))解：（1）因為(?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）因為(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分）在謂詞邏輯中構造下面推理的證明：每個科學家都是勤奮的，每個勤奮 又身體健康的人在事業中都會獲得成功。存在著身體健康的科學家。所以，存在著事業獲得成功的人或事業半途而廢的人。 解：論域：所有人的集合。Q(x)：x是勤奮的；H(x)：x是身體健康的；S(x)：x是科學家；C(x)：x是事業獲得成功的人；F(x)：x是事業半途而廢的人；則推理化形式為： ?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分）設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分）設R和S是集合A上的任意關系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對稱的，則R*S也是對稱的。 (4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則R∩S是自反的。(6)若R和S是傳遞的，則R∪S是傳遞的。 解 (1)成立。對任意的a∈A，因為R和S是自反的，則 (2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，則R和S是反自反的，但R*S＝{<1，1>}不是反自反的。 (3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，則R和S是對稱的，但R*S＝{<1，3>，<3，2>}不是對稱的。 (4)不成立。例如，令A＝{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)成立。對任意的a∈A，因為R和S是自反的，則 五、（15分）令X＝{x1，x2，?，xm}，Y＝{y1，y2，?，yn}。問(1)有多少個不同的由X到Y的函數？ (2)當n、m滿足什么條件時，存在單射，且有多少個不同的單射？(3)當n、m滿足什么條件時，存在雙射，且有多少個不同的雙射？ 解 (1)由于對X中每個元素可以取Y中任一元素與其對應，每個元素有n種取法，所以不同的函數共nm個。 (2)顯然當|m|≤|n|時，存在單射。由于在Y中任選m個元素的任一全排列都形成X到 mY的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個。 (3)顯然當|m|＝|n|時，才存在雙射。此時Y中元素的任一不同的全排列都形成X到Y的不同的雙射，故不同的雙射有m!個。 六、（5分）集合X上有m個元素，集合Y上有n個元素，問X到Y的二元關系總共有多少個？ 解 X到Y的不同的二元關系對應X×Y的不同的子集，而X×Y的不同的子集共有個2mn，所以X到Y的二元關系總共有2mn個。 七、（10分）若 b。 證明 設e是群 － － －所以，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分）給定連通簡單平面圖G＝ 證明 由偶拉公式得|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矛盾。故對任意f∈F，d(f)＝3。 離散數學試題（B卷答案7） 一、（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)偏序集 (3)偏序集 偏序集 考察P(X)的哈斯圖，最底層的頂點是空集，記作第0層，由底向上，第一層是單元集，第二層是二元集，…，由|X|＝n，則第n－1層是X的n－1元子集，第n層是X。偏序集 相比，恰好缺少第0層和第n層。因此 四、（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，i?1?1>，<5，4>，<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分）有幺元且滿足消去律的有限半群一定是群。 證明 設 考慮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??02A??0??0?111??02??201?3?0A??02111????02011???12??03??22??044A? ?0312????0101???23??13? 23??22??所以v1到v4長度為1、2、3和4的路的個數分別為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為終結點且具有不同始結點的數目為3，其第(2，3)元素為0，表明那些邊既以v2為終結點又以v3為終結點，并且具有相同始結點的數目為0。AAT中的第(2，2)元素為2，表明那些邊以v2為始結點且具有不同終結點的數目為2，其第(2，3)元素為1，表明那些邊既以v2為始結點又以v3為始結點，并且具有相同終結點的數目為1。 (4)?0??0B4?A?A2?A3?A4??0??0??0??0所以求可達矩陣為P??0??0??0??0(5)因為P?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的強分圖。 離散數學試題（B卷答案8） 一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R 證明 因為S∨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分）根據推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。 設P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為：?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名學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網球，還有2人會打這三種球。而6個會打網球的人都會打另外一種球，求不會打這三種球的人數。 解 設A、B、C分別表示會打排球、網球和籃球的學生集合。則： |A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因為|(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。故，不會打這三種球的共5人。 四、（10分）設A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱 i?13為由A1、A2和A3產生的小項。試證由A1、A2和A3所產生的所有非空小項的集合構成全集U的一個劃分。 證明 小項共8個，設有r個非空小項s1、s2、…、sr(r≤8)。 對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。 i?1i?1i?1i?1i?13rrrr任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現在sp和sq中，于是sp∩sq＝?。 綜上可知，{s1，s2，…，sr}是U的一個劃分。 五、（15分）設R是A上的二元關系，則：R是傳遞的?R*R?R。 證明 (5)若R是傳遞的，則 反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則 六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結點數、邊數和面數。 證明 對G的邊數m作歸納法。 當m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結論自然成立。假設對邊數小于m的連通平面圖結論成立。下面考慮連通平面圖G的邊數為m的情況。 設e是G的一條邊，從G中刪去e后得到的圖記為G?，并設其結點數、邊數和面數分別為n?、m?和r?。對e分為下列情況來討論： 若e為割邊，則G?有兩個連通分支G1和G2。Gi的結點數、邊數和面數分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設有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，由歸納假設有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。 由數學歸納法知，結論成立。 七、（10分）設函數g：A→B，f：B→C，則：(1)f?g是A到C的函數； (2)對任意的x∈A，有f?g(x)＝f(g(x))。 證明 (1)對任意的x∈A，因為g：A→B是函數，則存在y∈B使 對任意的x∈A，若存在y1、y2∈C，使得 綜上可知，f?g是A到C的函數。 (2)對任意的x∈A，由g：A→B是函數，有 八、（15分）設 證明 對于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以 － － 若 － － －a>∈R。 若 － － －1*b)*(b1*c)＝a1*c∈H，故 對于任意的b∈[a]R，有 －于是b∈aH，[a]R?aH。對任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H， 離散數學試題（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分）舉例說明下面推理不正確：?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))。 解：設論域為{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分）在謂詞邏輯中構造下面推理的證明：所有牛都有角，有些動物是牛，所以，有些動物有角。 解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是動物；則推理化形式為： ?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)。 證明：因為 五、（15分）設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，i?1?1>，<5，4>，<5，5>}。 六、（10分）若函數f：A→B是雙射，則對任意x∈A，有f1(f(x))＝x。 －證明 對任意的x∈A，因為f：A→B是函數，則 －由f－1是B到A的函數，于是可寫為f1(f(x))＝x。 － 七、（10分）若G為有限群，則|G|＝|H|·[G:H]。 證明 設[G:H]＝k，a1、a2、…、ak分別為H的k個左陪集的代表元，由定理8.38得 G??[ai]R??aiH i?1i?1kk又因為對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條邊的所有非同構有向簡單圖。 解：由握手定理可知，所畫的有向簡單圖各結點度數之和為4，且最大出度和最大入度均小于或等于2。度數列與入度列、出度列為： 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 四個所求有向簡單圖如圖所示。 （2）設G是n(n≥4)階極大平面圖，則G的最小度?≥3。 證明 設v是極大平面圖G的任一結點，則v在平面圖G－{v}的某個面f內。由于G－{v}是一個平面簡單圖且其結點數大于等于3，所以d(f)≥3。由G的極大平面性，v與f上的結點之間都有邊，因此d(v)≥3。由v的任意性可得，G的最小度?≥3。 離散數學試題（B卷答案10） 一、（10分）使用將命題公式化為主范式的方法，證明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。 證明：因為(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不愉快。 解 設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分）設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分）設X＝{1，2，3，4}，R是X上的二元關系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關系圖。(2)寫出R的關系矩陣。 (3)說明R是否是自反、反自反、對稱、傳遞的。解(1)R的關系圖如圖所示：(2)R的關系矩陣為： ?1??0M(R)??1??1?101110110??0? 0??0??(3)對于R的關系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的； 經過計算可得 ?1??0M(R2)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0?? 六、（15分）設函數f：R×R?R×R，f定義為：f( (4)求復合函數f?f和f?f。 證明(1)對任意的x，y，x1，y1∈R，若f( (2)對任意的 1u?wu?wu?wu?w，y＝，則f( －1 ( x?y?x?y，2x?y?(x?y)>＝ 七、（15分）給定群 證明 對G中任意元a和b。 因為a*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中，至少有n－1條邊。 證明 不妨設G是無向連通圖（若G為有向圖，可略去邊的方向討論對應的無向圖）。設G中結點為v1、v2、?、vn。由連通性，必存在與v1相鄰的結點，不妨設它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、?、vn中必存在與v1或v2相鄰的結點，不妨設為v3，將其連接得邊e2，續行此法，vn必與v1、v2、?、vn?1中的某個結點相鄰，得新邊en?1，由此可見G中至少有n－1條邊。 （2）試給出|V|＝n，|E|＝(n－1)(n－2)的簡單無向圖G＝ 解 下圖滿足條件但不連通。 12344333 《毛概 （二）》復習提綱 1、中國改革開放的依據、性質、特點、意義、成敗評價標準，及改革發展穩定三者的關系及處理原則。依據：也就是改革開放的背景：國內：a“文化大革命”使整個政治局面處于混亂狀態 b經濟上處于緩慢發展和停滯狀態，國民經濟到了崩潰邊緣國際：時代主題的改變，我國經濟科技實力與國際先進水平差距拉大 性質：改革開放是黨在新的時代條件下帶領人民進行的新的偉大革命，它不是對原有經濟體制細枝末節的修補，而是對其進行根本性的變革；改革開放是決定當代中國命運的關鍵抉擇。 特點：我國改革開放 有以下七大特點：在改革的性質上，堅持社會主義制度的自我完善和發展在改革的方向上，堅持市場取向在改革的目標模式上，選擇建立社會主義市場經濟體制在改革的方法上，堅持先易后難、逐步深化、漸進式推進在改革的總體部署上，堅持統籌兼顧，處理好若干重要關系在改革的動力上，既依靠黨和政府的領導，又尊重人民的首創精神在對改革措施、手段和成果的評價上，堅持“三個有利于”標準 意義：1 改革開放是決定當代中國命運的關鍵抉擇，是發展中國特色社會主義，實現中華民族偉大復興的必由之路只有社會主義才能救中國，只有改革開放才能發展中國，發展社會主義，發展馬克思主義3 改革開放符合當心民心，順應時代潮流，方向和道路完全是正確的，成效和功績不容否定，停頓和倒退沒有出路 改革成敗得失的評價標準：1992年，在南方談話中，鄧小平明確地提出了“三個有利于”標準，即要以是否有利于發展社會主義社會的生產力、是否有利于增強社會主義國家的綜合國力、是否有利于提高人民生活水平作為判斷改革得失成敗的標準。 改革發展穩定三者關系： 改革是動力，發展是目的，穩定是前提。只有堅定不移地推進發展，才能不斷增強綜合國力和國際競爭力，更好地解決前進中的矛盾和問題。只有堅定不移地推進改革，才能為經濟和社會的發展提供強大的動力。只有堅定不移地維護穩定，才能不斷為改革發展創造有利的條件。實踐表明，改革，發展，穩定三者關系處理得當，就能總攬全局，保證經濟社會的順利發展，處理不當，就會吃苦頭，付出代價。 處理原則：1 保持改革，發展，穩定在動態中的相互協調和相互促進。把改革的力度，發展的速度和社會可以承受的程度統一起來。把不斷改善人民生活作為處理改革，發展，穩定關系的重要結合點。（每點的具體解釋在書本169頁） 2、中國對外開放的依據、特點與格局 依據： 1、歷史依據：近代中國落后挨打的主要原因是閉關鎖國，在社會主義建設初期遇到挫折的原因也是 因為被迫處于封閉和半封閉狀態。 2、時代依據： 實行對外開放是社會化大生產和經濟生活國際化的客觀要求。 3現實依據： 實行對外開放是總結國內外歷史經驗的必然結果。 特點：全方位，多層次，寬領域 格局：全方位、多層次、寬領域的對外開放格局 A 全方位： 我國的對外開放是對世界所有類型的國家開放，不僅對發達國家，而且也對發展中國家，對原蘇聯東歐地區的國家開放。但我們對外開放的重點還是發達國家。 B 多層次： 我國的對外開放經歷了由東到西、由點到線、由線到面，由沿海到內地逐步推進的過程，形成了全國性的對外開放格局。 C 多渠道、寬領域： 就是向世界市場開放，包括商品市場、資本市場、技術市場、勞務市場等。 3、商品經濟、市場經濟、社會主義經濟、社會主義市場經濟的特點、聯系和區別。 商品經濟的產生和存在需要兩個基本經濟條件，第一個是社會分工的產生和存在，第二個是生產資料和勞動分工屬于不同的所有者。商品經濟的特點有:市場性；自發性；競爭性；商品的使用價值；商品的價值；具有具體勞動和抽象勞動。 市場經濟的特點：1.企業是獨立的經濟單位 2.生產要素可以自由流動 3.通過價格調節經濟 社會主義經濟: 社會主義市場經濟的特點：堅持以公有制為主體，堅持以按勞分配為主體，堅持以實現共同富裕為目標。社會主義市場經濟體制是社會主義基本制度與市場經濟的結合。一是在所有制結構上，以公有制為主體，多種所有制經濟共同發展，一切符合“三個有利于”標準的所有制形式都可以而且應該用來為社會主義服務。二是在宏觀調控上，以實現最廣大勞動人民利益為出發點和歸宿，社會主義國家能夠把人民的當前利益與長遠利益，局部利益與整體利益結合起來，使市場在社會主義國家宏觀調控下對資源配置起基礎性作用，更好的發揮計劃和市場兩種手段的長處。 聯系和區別:社會主義市場經濟體制是社會主義基本制度與市場經濟的結合。一方面，它必然體現社會主義的制度特征，另一方面，它又具有市場經濟的一般特征。市場經濟與社會主義制度結合。就要堅持以公有制為主體，堅持以按勞分配為主體，堅持以實現共同富裕為目標。市場經濟是一種以市場手段為主的資源配置方式，不屬于社會經濟制度的范疇。與社會主義基本制度相結合而形成的社會主義市場經濟體制，在所有制結構，分配制度和宏觀調控上具有自身的特征。 4、社會主義初級階段的基本經濟制度，公有制經濟成分、主體地位、實現形式。 基本經濟制度：以公有制為主體，多種所有制經濟共同發展是我國社會主義初級階段的一項基本經濟制度。經濟成分：國有經濟和集體經濟，混合所有制經濟中的國有成分和集體成分。 主體地位：主體地位主要體現在：一是公有資產在社會總資產中占優勢；二是國有經濟控制國民經濟命脈，對經濟發展起主導作用。國有經濟起主導作用，主要體現在控制力上。 實現形式：公有制的實現形式可以而且應當多樣化，一切反應社會化生產規律的經營方式和組織形式都可以大膽利用。要大力發展國有資本，集體資本和非公有資本等參股的混合所有制經濟，實現投資主體的多元化，使股份制成為公有制的主要實現形式。 5、社會主義初級階段的基本分配制度。 社會主義初級階段的基本分配制度是按勞分配為主體、多種分配方式并存的分配制度 6、建設創新型國家，科技是關鍵，人才是核心，教育是基礎。206頁 科技人才是提高自主創新能力的關鍵所在。我們要進一步營造鼓勵創新的環境，努力造就世界一流科學家和科技領軍人才，注重培養一線的創新人才，使全社會創新智慧迸發、各方面創新人才大量涌現，形成強大的自主創新能力，支持我國經濟社會發展，實現2020年進入創新型國家行列的目標。 7、中國特色新型工業化道路，新在哪里？207頁 新型工業化道路的“新”，就在于它同信息化等現代高科技發展緊密結合；注重經濟發展同資源環境相協調；堅持城鄉協調發展；實現資金技術密集型產業同勞動密集型相結合。 8、“三農”問題與建設社會主義新農村的總要求。211頁 建設社會主義新農村的總要求是生產發展、生活寬裕、鄉風文明、村容整潔、管理民主。 生產發展，是新農村建設的中心環節，是實現其他目標的物質基礎。生活寬裕，是新農村建設的目的，也是衡量我們工作的基本尺度。鄉風文明，是農民素質的反應，體現農村精神文明建設的要求。村容整潔，是展現農村新貌的窗口，是實現人與環境和諧發展的必然要求。管理民主，是新農村建設的政治保證，顯示了對農民群眾政治權利的尊重和維護。 9、社會主義民主政治的本質，中國的國體與政體。 社會主義民主政治的本質：： 解放生產力，發展生產力，消滅剝削，消除兩極分化，最終達到共同富裕。中國國體與政體：工人階級領導的、以工農聯盟為基礎的人民民主專政，政體是人民代表大會制度。 10、中國的基本政黨制度的特點和特色 特點和特色：共產黨執政，多黨派參政，共產黨領導，多黨派合作 附：中國基本政黨制度：中國共產黨領導下的多黨合作和政治協商制度。 基本內容：第一，中國共產黨是執政黨，中國共產黨和各民主黨派是親密友黨。第二，中國共產黨和各民主黨派合作的政治基礎是堅持中國共產黨的領導和堅持四項基本原則。第三，中國共產黨和各民主黨派合作的基本方針是“長期共存、互相監督、肝膽相照、榮辱與共”。第四，中國共產黨和各民主黨派以憲法和法律為根本活動準則。 11、我國的民族區域制度和處理民族關系問題的基本原則。 堅持實行各民族平等、團結、合作和共同繁榮的原則（書上）平等團結互助和諧（網上） 12、中國基層民主制度及其三大基本類型和特點。 農村基層民主政治 城市社區民主政治建設 職工代表大會制度建設 特點自我管理 自我教育 自我服務 不知道正確與否你看看吧 13、社會主義法制建設的基本要求（16字概括）。 答：有法可依，有法必依，執法必嚴，違法必究（P238） 14、結合實際，如何認識社會主義社會的民主、自由和人權？ 答：1：“民主”，由“人民”和“權力”兩詞合成，意為“人民的政權”，是人民當家作主的意思。“民主”是政權的一種構成形式。 2：“自由”通常是講政治自由，主要是指公民在法律范圍內參與國家政治生活的一種權利，“自由”是政權給予公民的政治權利。 3：“人權“泛指人身自由和其他民主權利，主要包括生存權，發展權，經濟權，文化權等。公民在政治上應該享有的自由和民主權利，一般被稱作“人權”。（P242） 15、中國特色社會主義文化建設的根本任務和基本方針。 答：根本任務：就是以馬克思列寧主義，毛澤東思想，鄧小平理論和“三個代表”重要思想為指導，全面貫徹科學發展觀，著力培育有理想，有道德，有文化，有紀律的公民，切實提高全民族的思想道德素質和科學文化素質。（P251） 基本方針：1：堅持以馬克思主義為指導，為人民服務，為社會主義服務。 2：堅持百花齊放，百家爭鳴的方針。 3堅持貼近實際，貼近生活，貼近群眾，不斷推進文化創新。 4：堅持立足當代又繼承民族優秀文化傳統，立足本國又充分吸收世界優秀文化成果。 5：堅持一手抓繁榮，一手抓管理。(P253) 16、社會主義核心價值體系及其基本內容。 社會主義核價值體系是社會主義制度在價值層面的本質規定，是全黨全國各族人民團結奮斗的共同思想基礎，是實現科學發展觀、社會和諧的推動力量，是國家文化軟實力的核心內容，反映了我國社會主義基本制度的本質要求。建設社會主義核心價值體系，是黨在思想文化建設上的一個重大理論創新和重大戰略任務。對于建設社會主義精神文明，為發展中國特色社會主義提供強大精神動力和思想保證，具有重大意義。推動社會主義文化大發展大繁榮，必須把建設社會主義核心價值體系作為第一位的任務，努力在全社會形成統一的指導思想，共同的理想信念，強大的精神支柱和基本的道德規范，增強社會主義意識形態的吸引力和凝聚力。 基本內容：包括馬克思主義指導思想、中國特色社會主義共同理想、以愛國主義為核心的民族精神和以改革創新為核心時代精神、社會主義榮辱觀。 17、社會主義和諧社會的6大特征（或基本要求）及建設方針和舉措。 我們所要建設的社會主義和諧社會，應該是民主法治、公平正義、誠信有愛、充滿活力、安定有序、人與自然和諧相處的社會。 民主法治，就是社會主義民主得到充分發揚，依法治國基本方略得到切實落實，在各方面積極因素得到廣泛調動。 公平正義，就是社會各個方面的利益關系得到妥善協調，人民內部矛盾和其他社會矛盾得到正確處理，社會公平和正義得到切實維護和實現。 誠信友愛，就是全社會互幫互助、誠實守信、全體人民平等友愛、融洽相處。 充滿活力，就是能夠使一切有利于社會進步的創造愿望得到尊重，創造活動得到支持，創造才能得到發揮，創造成果得到肯定。 安定有序，就是社會組織機制健全，社會管理完善，社會秩序良好，人民群眾安居樂業，社會保持安定團結。 人與自然和諧相處，就是生產發展，生活富裕，生態良好。 建設方針和舉措：1.必須堅持以馬克思列寧主義，毛澤東思想，鄧小平理論和“三個代表”重要思想為指導；2.必須堅持以人為本；3，堅持科學發展；4.堅持改革開放；5.堅持民主法治；6。堅持正確處理改革發展穩定的關系；7.堅持在黨的領帶下全社會共同建設； 18、1949年來，我國大陸對臺灣問題解決的基本政策方針演變的幾個階段和特點。 1、武力解決 2、和平解決 3、一國兩制的提出 武力解決的特點：有堅決解放臺灣的決心；受到美國軍事干涉和占領臺灣的威脅；人民解放軍炮擊金門，向國際社會，特別是向美國表明中國人民解放臺灣的決心和立場；中國人民解放軍發到渡海戰役。解放了一江山島和大陳島 和平解決的特點：國際形勢緩和，亞太地區國家希望和平的呼聲高漲；國內正在進行社會主義改造和第一個五年計劃的經濟建設，需要一個和平的國際環境，開展社會主義建設；臺灣局勢發生變化。美蔣在合作中出現矛盾；我們黨對解決臺灣問題又提出了許多重要原則，促進對臺灣的和平解決 一國兩制的特點：一個中國；兩制并存；高度自治；盡最大努力爭取和平統一，但不承諾放棄使用武力；解決臺灣問題，實現祖國的完全統一，寄希望于臺灣人民；積極促談，爭取通過談判實現統一；積極促進兩岸“三通”和各項交流，增進兩岸同胞的相互了解和感情，密切兩岸經濟，文化關系，為實現和平統一創造條件；堅決反對任何“臺灣獨立”的言行；堅決反對外國勢力插手和干涉臺灣問題；集中力量搞好經濟建設，是解決國際國內問題的基礎，也是實現國家統一的基礎。 19、“和平統一、一國兩制”構想的內涵及其基本內容。 基本內容：（1）一個中國（2）兩制并存（3）高度自治（4）盡最大努力爭取和平統一，但不承諾放棄武力。 （5）解決臺灣問題，實現祖國的完全統一，寄希望于臺灣人民。（6）積極促談，爭取通過談判實現統一。 （7）積極促進兩岸“三通”和各項交流，增進兩岸同胞的相互了解和感情，密切兩岸經濟、文化關系，為實現和平統一創造條件。（8）堅決反對任何“臺灣獨立”的言行。（9）堅決反對任何外國勢力插手和干涉臺灣問題。（10）集中力量搞好經濟建設，是解決國際國內問題的基礎，也是實現國家統一的基礎。內涵：“和平統一、一國兩制”構想是充分尊重歷史和現實、照顧各方面利益、維護民族團結、實現祖國完 全統一和民族偉大復興的科學構想。“一國兩制”是中華民族對人類政治文明的獨特貢獻。“和平統一、一國兩制”構想豐富了馬克思主義，具有重大意義。 第一，“和平統一、一國兩制”構想創造性地把和平共處原則用之于解決一個國家的統一問題。 第二，“和平統一、一國兩制”構想創造性地發展了馬克思主義的國家學說。 第三，“和平統一、一國兩制”構想體現了既堅持祖國統一、維護國家主權的原則堅定性，也體現了照 顧歷史實際和現實可能的策略靈活性，可以避免武力統一會造成的不良后果。 第四，“和平統一、一國兩制”構想有利于爭取社會主義現代化建設事業所需要的和平的國際環境與國 內環境。 第五，“和平統一、一國兩制”構想為解決國際爭端和歷史遺留問題提供了新的思路。（P302-305） 20、當今世界時代主題和總體特征。 時代主題：和平與發展 總體特征:(1)世界多極化在曲折中發展(2)經濟全球化趨勢深入發展 21、新中國成立以來，我國獨立自主和平外交政策的演變階段及其特點。 新中國成立初期：毛澤東提出“另起爐灶”、“打掃干凈屋子再請客”、“一邊倒”三大外交方針。特點： 這三大方針，符合中國人民實現國家安全、獨立和維護世界和平的根本利益，為獨立自主的新中國外交關系奠定了基礎。 1955年萬隆會議：周恩來提出來互相尊重主權和領土完整、互不侵犯、互不干涉內政、平等互利、和平 共處這五項基本原則。特點：和平共處五項原則成為我國處理對外關系的基本準則。 20世紀60年代：我國外交政策重心由“一邊倒”調整為同時反對美蘇兩個超級大國到處侵略擴張、肆 意干涉別國內政的霸權主義政策。特點：積極支持民族解放運動，堅持睦鄰友好，維護中國的主權和領土完整，維護世界的進步與和平。 20世紀70年代：毛澤東提出“一條線”的外交戰略。特點：這是我國外交的一次重大戰略調整，對緩 解和我國面臨的緊張局勢，維護世界和平與穩定，保障中國人民和世界人民的根本利益發揮了重要作用。20世紀80年代：堅持獨立自主，主張一切從中國人民和世界人民的根本利益出發，在國際上保持自己的獨立地位，不與任何大國和國家集團結盟，奉行真正的不結盟政策。特點：是我國對外政策和外交政策的重大調整，在新時期繼承和發展了毛澤東的外交思想。 冷戰結束后：江澤民繼承和發展了鄧小平外交思想，繼續開創我國外交工作新局面。 黨的十六大以來：高舉和平、發展、合作的旗幟，堅持獨立自主的外交政策。特點：中國主張國際關 系民主化和發展模式多樣化，積極推動經濟全球化朝著有利于實現共同繁榮的方向發展，推動國際秩序向公正合理的方向發展，為推動建設持久和平、共同繁榮的世界作出貢獻，（P327-330） 22、我國外交政策的原則和宗旨。 基本原則：第一，堅持獨立自主地處理一切國際事務的原則。 第二，堅持和平共處五項基本原則為指導國家間關系的基本準則。 第三，堅持同發展中國家加強團結與合作的原則。 第四，堅持愛國主義與履行國際義務相統一的原則。 宗旨：維護世界和平，促進共同發展。（P330-332） 23、中國特色社會主義事業的依靠力量包括哪些？出現什么新變化和特點？ 工人階級是國家的領導階級，是中國特色社會主義事業的領導力量； 農民階級是人數最多的基本依靠力量，農業、農村、農民問題的重要性決定了農民階級的重要地位； 知識分子是中國工人階級的一部分。科學技術的作用決定了知識分子的重要地位； 中國人民解放軍是建設中國特色社會主義的重要力量； 新變化和特點：改革開放以來，我國工人階級隊伍發生了明顯變化，一是隊伍迅速壯大；二是內部結構發生重大變化；三是崗位流動加快。改革開放以來，我國出現了一些新的社會階層，主要有：民營科技企業的創業人員和技術人員，個體戶，私營企業主，自由職業人員等。在黨的領導下，廣大農民表現出了可貴的創業革新精神，實行了以家庭聯產承包為主要內容的責任制，農民改革和建設取得巨大成就，帶動了整個國家的改革和建設事業。改革開放和現代化建設符合廣大農民的根本利益，他們衷心擁護建設中國特色社會主義的路線，方針和政策，成為改革開放和現代化建設的一支重要依靠力量。 24、如何認識新時期愛國統一戰線的性質、特點、構成、基本任務及領導權問題。 新時期愛國統一戰線的性質是建立在社會主義和愛國主義基礎上的，是社會主義性質的統一戰線； 特點是：具有空前的廣泛性，是最廣泛的愛國統一戰線； 構成是：一個是大陸范圍內，以愛國主義和社會主義為政治基礎的團結全體勞動者、建設者和愛國者的聯盟，這是統一戰線的主體和基礎；一個是大陸范圍以外的，以愛國和擁護祖國統一為政治基礎的團結臺灣同胞、港澳同胞和海外僑胞的聯盟，這是統一戰線的重要組成部分； 基本任務：高舉愛國主義、社會主義旗幟，團結一切可以團結的力量，調動一切積極因素，化消極因素為積極因素，為促進社會主義經濟建設、政治建設、文化建設、社會建設服務，為促進香港、澳門長期繁榮穩定和祖國和平統一服務，為維護世界和平、促進共同發展服務。 堅持黨對統一戰線的領導權是鞏固與發展統一戰線的根本保證。 25、結合當前中國海疆主權維護，談一談對中國加強國防和軍隊建設的認識。 中國維護海洋權益的形勢依然嚴峻。當前中國海洋安全形勢處于相對和平態勢，但不確定的因素仍然存在，各國之間力量的角逐日趨激烈。中國大陸周邊海洋形勢相對平穩，黃海形勢穩中有憂，東海形勢突破與挑戰并存，南海形勢復雜多變。在南海，目前南沙群島的安全問題尤為突出，中國與東南亞國家的南海之爭，表面上看是島礁之爭，實質是資源之爭。在東南亞地區，南沙群島爭端解決沒有實質性進展，中國“島礁被侵占、海域被瓜分、資源被掠奪”的狀況沒有改觀。 加強國防和軍隊建設，是發展中國特色社會主義的戰略任務，是維護我國主權和領土完整的保證，是我國和平共處原則外交政策的體現，必須統籌經濟建設和國防建設，在推進現代化事業進程中實現富國和強軍的統一。要堅持以毛澤東軍事思想、鄧小平新時期軍隊建設思想、江澤民國防和軍隊建設思想為指導，認真落實胡錦濤同志關于新形勢下國防和軍隊建設重要論述，把科學發展觀作為國防和軍隊建設的重要指導方針。著眼全面履行新世紀新階段軍隊歷史使命，提高軍隊應對多種安全威脅、完成多樣化軍事任務的能力，堅決維護國家主權、安全和領土完整，為全面建設小康社會提供強有力的保障。加強人民武裝警察部隊建設，提高執勤、處置突發事件、反恐維穩的能力。加強國防教育，增強全民國防觀念。完善國防動員體系。鞏固軍政軍民團結。 26、如何正確認識中國共產黨的性質和宗旨？ .中國共產黨是中國工人階級的先鋒隊，同時是中國人民和中華民族的先鋒隊，是中國特色社會主義事業的領導核心，代表中國先進生產力的發展要求，代表中國先進文化的前進方向，代表中國最廣大人民的根本利益。黨的最高理想和最終目標是實現共產主義。 中國共產黨的性質決定了一切從人民的利益出發，全心全意為人民服務是它的唯一宗旨。黨的階級性和先進性，決定我們黨必須為工人階級和人民群眾謀利益。無產階級革命就是要消滅一切剝削制度和產生剝削的根源，解放全人類。作為工人階級先鋒隊的中國共產黨從它誕生之日起，就是中國各族人民的忠實代表，就把全心全意為人民服務看作是根本宗旨。黨在任何時候都把群眾利益放在第一位，在工作中實行群眾路線，一切為了群眾，一切依靠群眾，從群眾中來，到群眾中去，堅持不懈地反對腐敗，加強黨風建設和廉政建設。 27、如何全面推進和加強黨的建設？ 黨的建設偉大工程同黨領導的偉大事業緊密地聯系在一起。在新世紀新階段，要把全體人民的意志和力量凝聚起來，全面建設小康社會，加快推進社會主義現代化，必須以加強黨的執政能力建設和黨的先進性建設為主線，以改革創新精神全面推進黨的建設新的偉大工程。堅持立黨為公，執政為民，保持黨同人民群眾的血肉聯系。 28、如何看待和預防中國共產黨內出現的腐敗現象？ 是由于個別干部脫離群眾，濫用權力為謀小集團或個人的私利，中國共產黨堅決預防和反腐敗。 注重制度建設，從源頭上防腐。嚴格執行黨風廉政建設責任制。堅持深化改革和創新體制，加強廉政文化建設，形成拒腐防變教育長效機制，反腐倡廉制度體系，權力運行監控機制。健全紀檢監察派駐機構統一管理，完善巡視制度。加強領導干部廉潔自律工作，提高黨員干部拒腐防變能力。 《離散數學》期末考試復習指導 期末考試僅限于期中考試以后的內容：Chapter 7 Trees;Chapter 8 Topics in graph theory.考試題型：計算題；簡答題；證明題；構造圖形（構造滿足一定條件的圖，如： 6個頂點，11條邊且無Hamiltonian circuit）。題目共計6題，無選擇題和填空題。 考試難度：基本與期中考試相同，有一定數量的題直接來自于習題，最后一題較 難（構造圖形）。 復習要點：基本概念及定義： 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; 基本內容： 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.不要求的內容： Computer representation of binary positional tree;searching general tree;algorithms.復習中如遇困難請聯系：錢建國***，jgqian@jingxian.xmu.edu.cn徐偉*** 陳美潤*** 祝大家取得好成績！ 離散數學是研究離散量的結構及其相互關系的數學學科，是現代數學的一個重要分支。下面是小編整理的離散數學期末考試試題及答案，歡迎閱讀參考！ 一、【單項選擇題】 (本大題共15小題，每小題3分，共45分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在答題卷相應題號處。 1、在由3個元素組成的集合上，可以有()種不同的關系。 [A] 3 [B] 8 [C]9 [D]272、設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、下列關系中是等價關系的是()。 [A]不等關系 [B]空關系 [C]全關系 [D]偏序關系 5、對于一個從集合A到集合B的映射，下列表述中錯誤的是()。 [A]對A的每個元素都要有象 [B] 對A的每個元素都只有一個象 [C]對B的每個元素都有原象 [D] 對B的元素可以有不止一個原象 6、設p:小李努力學習，q:小李取得好成績，命題“除非小李努力學習，否則他不能取得好成績”的符號化形式為()。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、設A={a,b,c},則A到A的雙射共有()。 [A]3個 [B]6個 [C]8個 [D]9個 8、一個連通G具有以下何種條件時，能一筆畫出：即從某結點出發，經過中每邊僅一次回到該結點()。 [A] G沒有奇數度結點 [B] G有1個奇數度結點 [C] G有2個奇數度結點 [D] G沒有或有2個奇數度結點 9、設〈G,*〉是群，且|G|>1，則下列命題不成立的是()。 [A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外無其他冪等元 10、令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為() [A] p→┐q [B] p∨┐q [C] p∧q [D] p∧┐q11、設G=的結點集為V={v1,v2,v3},邊集為E={,}.則G的割(點)集是()。 [A]{v1} [B]{v2} [C]{v3} [D]{v2,v3} 12、下面4個推理定律中，不正確的為()。 [A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段論) [C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式) 13、在右邊中過v1,v2的初級回路有多少條() [A] 1 [B] 2 [C] 3 [D] 414、若R，是環，且R中乘法適合消去律，則R是()。 [A]無零因子環 [C]整環 [B]除環 [D]域 15、無向G中有16條邊，且每個結點的度數均為2，則結點數是()。 [A]8 [B]16 [C]4 [D] 32二、【判斷題】 (本大題共8小題，每小題3分，共24分)正確的填T，錯誤的填F，填在答題卷相應題號處。 16、是空集。() 17、設S,T為任意集合，如果S—T=，則S=T。() 18、在命題邏輯中，任何命題公式的主合取范式都是存在的，并且是唯一的。() 19、關系的復合運算滿足交換律。() 20、集合A上任一運算對A是封閉的。() 21、0,1,2,3,4,max,min是格。() 22、強連通有向一定是單向連通的。() 23、設都是命題公式，則(PQ)QP。() 三、【解答題】 (本大題共3小題，24、25每小題10分，26小題11分，共31分)請將答案填寫在答題卷相應題號處。 24、設集合A={a, b, c}，B={b, d, e}，求 (1)BA;(2)AB;(3)A-B;(4)BA.25、設非空集合A，驗證(P(A)，,~，A)是布爾代數 26、如果他是計算機系本科生或者是計算機系研究生，那么他一定學過DELPHI語言而且學過C++語言。只要他學過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結論。 離散數學試題答案 一、【單項選擇題】(本大題共15小題，每小題3分，共45分) BDDCCCBABDADCBB 二、【判斷題】(本大題共8小題，每小題3分，共24分) FFTFTTTF 三、【解答題】(本大題共3小題，24、25每小題10分，26小題11分，共31分) 24、設集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.標準答案：(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 } 復習范圍或考核目標：考察集合的基本運算，包括交集，并集,見課件第一章第二節,集合的運算。 25、設非空集合A，驗證(P(A)，,~，A)是布爾代數 標準答案：證明 因為集合A非空，故P(A)至少有兩個元素，顯然，是P(A)上的二元運算.由定理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)是布爾代數.復習范圍或考核目標：考察布爾代數的基本概念，集合的運算，見課件代數系統中布爾代數小節。 26、如果他是計算機系本科生或者是計算機系研究生，那么他一定學過DELPHI語言而且學過C++語言。只要他學過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結論。 標準答案：令p：他是計算機系本科生 q：他是計算機系研究生 r：他學過DELPHI語言 s:他學過C++語言 t:他會編程序 前提：(p∨q)→(r∧s),(r∨s)→t 結論：p→t 證①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s)P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I ⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I第二篇：離散數學 期末考試試卷答案
第三篇：2012離散數學期末考試真題A
第四篇：《離散數學》期末考試復習指導
第五篇：離散數學期末考試試題及答案
點擊咨詢 