离散数学 期末考试试卷答案

第一篇：离散数学 期末考试试卷答案

离散数学试题(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={| 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}。

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

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

12-1

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

八、证明整数集I上的模m同余关系R={|xy(mod m)}是等价关系。其中，xy(mod m)的含义是x-y可以被m整除（15分）。

证明：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是双射。

因为∈fg存在z（∈g∈f）存在z（∈f∈g）∈gf∈（gf），所以（gf）=fg。

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={,,}，求其关系矩阵及关系图（10分）。

七、设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满足：<，>∈R∈R1且∈R2，证明R是A×B上的等价关系（10分）。

证明 对任意的∈A×B，由R1是A上的等价关系可得∈R1，由R2是B上的等价关系可得∈R2。再由R的定义，有<，>∈R，所以R是自反的。

对任意的、∈A×B，若R，则∈R1且∈R2。由R1对称得∈R1，由R2对称得∈R2。再由R的定义，有<，> 432

5∈R，即R，所以R是对称的。

对任意的、、∈A×B，若R且R，则∈R1且∈R2，∈R1且∈R2。由∈R1、∈R1及R1的传递性得∈R1，由∈R2、∈R2及R2的传递性得∈R1。再由R的定义，有<，>∈R，即R，所以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)证明f是双射。

解：1），∈R×R，若f()=f()，即=，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。

2）

∈R×R，由f()=

，通过计算可得x=(p+q)/2；y=(p-q)/2；从而

的原象存在，f是满射。

八、（10分）是个群，u∈G，定义G中的运算“”为ab=a*u*b，对任意a，b∈G，求证：也是个群。

证明：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=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的邻接距阵A和可达距阵P。

解：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、b∈Ai，I=1，2，„，n}，则R是A上的等价关系（15分）。

证明：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，使∈f，∈f。所以,f是满射。

对任意的x∈A，若存在y1,y2∈B，使得∈f且∈f,则有∈f且∈f。因为f是函数，则y1=y2。所以，f是单射。

因此f是双射。

八、设是群，和是的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。

证明 假设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是自反关系，所以∈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＝{，，，，，，，

4232-1d>，}

六、(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 a=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|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为：(写过程，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）因为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是自反的，则∈R，∈S，于是∈R*S，故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是自反的，则∈R，∈S，于是∈R∩S，所以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分）若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x＝

b。

证明 设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分）给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意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矛盾。故对任意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)偏序集是否有最大元？(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，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分）有幺元且满足消去律的有限半群一定是群。

证明

设是一个有幺元且满足消去律的有限半群，要证是群，只需证明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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z(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（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使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，－则R是G中的一个等价关系，且[a]R＝aH。

证明

对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。

－

－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以

－

－

－a>∈R。

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a

－

－

－1*b)*(b1*c)＝a1*c∈H，故∈R。－－综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，－

－于是b∈aH，[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R＝aH。

离散数学试题（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)。

证明：因为∈(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分）设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，于是

－由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()＝。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f。

(4)求复合函数ff和ff。

证明(1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。

(2)对任意的∈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分）给定群，若对G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，试证是Abel群。

证明 对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

第二篇：离散数学期末考试

一、单项选择题（本大题共10小题，每小题2分，共20分）

1、设集合M={a，}，N ={{a}，}则MN=（）。A、 B、{} C、{a} D、{{a}，，a}

2、设关系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、设集合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、{，，<1，x>} C、{<1，y>，<1，x>，}

D、{，，}

7、设是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足（）。

A、结合律

B、交换律

C、分配律

D、幂等律

8、设Z是整数集，“—”是整数减法，则下列说法正确的是（）。A、不是代数系统

B、的单位元是0

C、是代数系统

D、的单位元是1

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，1>，<2，b>}，则R逆关系R1=_______________________________。

2、在代数系统（Q是有理数集，“+”是有理数加法）中，单位元是______，2的逆元是___________。

3、设集合M={1，2，3，5}，则M的幂集P（M）包含___________个元素。

4、设T是一棵有n(n2)个顶点的树，则T有_____________条边。

5、设是一个代数系统，是S上的二元运算，若存在S，对任意xS，有x=x=，则称是的_______________。

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={（1）列出R的所有元素；（2）写出R的关系矩阵Mx，y A且x整除y}，要求：

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>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱连通 8.平行边

环 三．

(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.

第三篇：离散数学期末考试试题及答案

离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！

一、【单项选择题】

(本大题共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

第四篇：离散数学期末考试_2013年春季_试卷A_答案及评分细则

电子科技大学2012-2013学年第 2学期期 末 考试 A 卷

答案及评分细则

课程名称： 离散数学 考试形式： 闭卷 考试日期：2013 年 月 日 考试时长：120分钟

I.Multiple Choice(15%, 10 questions, 1.5 points each)C, C, B, A, B, B, D, A, B, C II.True or False(10%, 10 questions, 1 point each)F, T, T, T, F, F, F, F, T, F

III.Fill in the Blanks(20%, 10 questions, 2 points each)27=128, [-1,1], (aa)(bb)(cc)(ab)(ba), (12)(23)(33)(42), Some tests are easy, gcd（45，12）=3=12  4  45 (1), 6!, 52, ∀x ∃y(xy <>0), {(a,b)2|ab}

IV.Answer the Questions(35%,7 questions, 5 points each)： 1．

(1 point for each row)

2.Ans:(a)0123

(3points)

(b)[612).(2points)113.Ans: 001110011100.(one entry 1 point)114.Ans:

(one point for each step)

5.Ans: Encrypted form: CTOA.(one character 1 point)6.Ans: 5  11k.(the inverse of 5 module 11 is 9, 3 points, the result 2 points)7.Ans: The graphs are isomorphic(2 points): A–7, B–4, C–3, D–6, E–5, F–2, G–1.(3 points)

V.(6%)

(a)R is reflexive:(a, b)and(a, b)lie on the same line through the origin, namely on the line y = bx/a(if a≠0), or else on the line x = 0(if a = 0).(1 point)

R is symmetric: if(a, b)and(c, d)lie on the same line through the origin, then(c, d)and(a, b)lie on the same line through the origin.(1 point)R is transitive: suppose(a, b)and(c, d)lie on the same line L through the origin and(c, d)and(e, f)lie on the same line M through the origin.Then L and M both contain the two distinct points(0, 0)and(c, d).Therefore L and M are the same line, and this line contains(a, b)and(e, f).Therefore(a, b)and(e, f)lie on the same line through the origin.(1 point)Note: The proof that R is an equivalence relation can be carried out using analytic geometry: if(a, b)and(c, d)lie on the same nonvertical line through the origin, then the slope must equal b/a because the line passes through(0, 0)and(a, b)and the slope must also equal d/c because the line passes through(0, 0)and(c, d);thus, b/a = d/c, or ad = bc.If(a, b)and(c, d)lie on the same vertical line through the origin, then the points must have the form(0, b)and(0, d), and again it must happen that ad = bc.Therefore,(a, b)R(c, d)means that ad = bc.This equation can be used to verify that R is reflexive, symmetric, and transitive.(b)Each equivalence class is the set of points of A on a line of the form y = mx or the vertical line x = 0.(2 points)(c)If A is replaced by the entire plane, R is not an equivalence relation.It fails to satisfy the transitive property;for example,(1, 2)R(0, 0)and(0, 0)R(2, 2), but(1, 2)R(2, 2)because the line passing through(1, 2)and(2, 2)does not pass through the origin.(1 point)

VI(7%)

Using the variables: p: Lynn works part time;f: Lynn works full time;t: Lynn plays on the team;b: Lynn is busy, the argument can be written in symbols:

(3 points)If p∨f;t →p;t → b;f Then b

(1 point)One method to find whether the argument is valid is to construct the truth table:

We need to examine all cases where the hypotheses(columns 5, 6, 7, 8)are all true.There is only one case in which all four hypotheses are true(row 5), and in this case the conclusion is also true.Therefore, the argument is valid.(3 points)Alternately, rules of logic can be used to give a proof that the argument is valid.We begin with the four hypotheses and show how to derive the conclusion, b.1.p∨f;premise 2.t →p premise 3.t → b premise 4.f premise 5.p disjunctive syllogism on(1)and(4)

(1 point)6.p → t contrapositive of(2)

7.t modus ponens on(5)and(6)

(1 point)8.b modus ponens on(7)and(3)

(1 point)

VI I(7%)

Ans: {a} {a, b} {a, b, c}

(2points){a, b, c, d} {a, b, c, d, e} {a, b, c, d, e, f}(2points)The shortest path is a-b-c-d-e-f with cost 13.(2points)

第五篇：2012离散数学期末考试真题A

《毛概

（二）》复习提纲

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、如何看待和预防中国共产党内出现的腐败现象？

是由于个别干部脱离群众，滥用权力为谋小集团或个人的私利，中国共产党坚决预防和反腐败。

注重制度建设，从源头上防腐。严格执行党风廉政建设责任制。坚持深化改革和创新体制，加强廉政文化建设，形成拒腐防变教育长效机制，反腐倡廉制度体系，权力运行监控机制。健全纪检监察派驻机构统一管理，完善巡视制度。加强领导干部廉洁自律工作，提高党员干部拒腐防变能力。