第一篇：离散数学期末考试_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], (aa)(bb)(cc)(ab)(ba), (12)(23)(33)(42), Some tests are easy, gcd（45，12）=3=12 4 45 (1), 6!, 52, ∀x ∃y(xy <>0), {(a,b)2|ab}
IV.Answer the Questions(35%,7 questions, 5 points each)： 1．
(1 point for each row)
2.Ans:(a)0123
(3points)
(b)[612).(2points)113.Ans: 001110011100.(one entry 1 point)114.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)
第二篇：离散数学 期末考试试卷答案
离散数学试题(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))xA(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∧（xB∧xC）
（x A∧xB）∧（x A∧xC） 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，所以xx(mod m)，即xRx。
2）x，y∈I，若xRy，则xy(mod m)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以yx(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)xy(P(x)Q(y)) (xP(x)yQ(y))证明：xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))
二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分）
解：(PQ)(P∨Q)(PQ)∨(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(QS))∧(R∨P)∧QRS 证明：(1)R(2)R∨P(3)P(4)P(QS)(5)QS(6)Q(7)S(8)RS 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提前进入考场，个体域：考生 的集合，则命题可符号化为：PxA(x)，xA(x)QQP。
(1)PxA(x)P(2)PxA(x)T(1)，E(3)xA(x)P T(2)，E(4)xA(x)Q P(5)(xA(x)Q)∧(QxA(x))T(4)，E(6)QxA(x)T(5)，I(7)QP 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∧（xB∨xC）（x A∧xB）∨（x A∧xC） 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：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h（10分）。
解 因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。
由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。－
1－1
－1－1－1
－1离散数学试题(B卷答案3）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P(P∨Q∨R)2)((QP)∨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∧(PQ))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∧((QP)∧(PQ)))C (A∧(PQ))C
四、（10分）个体域为{1，2}，求xy（x+y=4）的真值。
解：xy（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∧10
五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B)解：xP(A)∩P(B)，xP(A)且xP(B)，有xA且xB，从而xA∩B，xP(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×RR×R，R为实数集，f定义为：f(
解：1）
2）
∈R×R，由f( ，通过计算可得x=(p+q)/2；y=(p-q)/2；从而 的原象存在，f是满射。 八、（10分） 证明：1）a，b∈G，ab=a*u*b∈G，运算是封闭的。 2）a，b，c∈G，（ab）c=（a*u*b）*u*c=a*u*（b*u*c）=a（bc），运算是可结合的。 3）a∈G，设E为的单位元，则aE=a*u*E=a，得E=u，存在单位元u。4）a∈G，ax=a*u*x=E，x=u*a*u，则xa=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)) 二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分） 解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m3 三、推理证明题（10分） 1)(P(QS))∧(R∨P)∧QRS 证明：（1）R 附加前提(2)R∨P P(3)P T(1)(2),I(4)P(QS)P(5)QS T(3)(4),I(6)Q P(7)S T(5)(6),I(8)RS CP 2)x(P(x)∨Q(x))，xP(x)x Q(x)证明：(1)xP(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∧（xB∨xC）（x A∧xB）∨（x A∧xC） 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，则存在aA，aB，且存在bB，bA（否则对任意的aA，aB，从而AB，即A∪B＝B，得B＝G，矛盾。） 对于元素a*bG，若a*bA，因A是子群，aA，从而a *(a*b)＝b A，所以矛盾，故a*bA。同理可证a*bB，综合有a*bA∪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)(PR)的主合取范式。 解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(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∧（xB∨xC） （x A∧xB）∨（x A∧xC） 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×CB×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 ∵HG且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)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3 M0 所以，公式(P∨Q)(PQ)为可满足式。 （2）因为(PQ)(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 所以，公式(PQ)(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|＝ fF24。若存在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)AA A∧C(A∧C)(AC)(AC)(AC) A∨B(A∧B)((AA)∧(BB))(AA)(BB)所以 F((AC)(AC))∨((BC)(BC))(((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC)))(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))∨xA(x)∨xB(x)(xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(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，i11>，<5，4>，<5，5>}。 五、（10分）设函数g：A→B，f：B→C，(1)若fg是满射，则f是满射。(2)若fg是单射，则g是单射。 证明 因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。 (1)对任意的z∈C，因fg是满射，则存在x∈A使fg(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，则由fg是单射得fg(x1)≠fg(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的邻接矩阵为： 00A00101011 101100(2)由于 002A001110220130A0211102011120322044A 031201012313 2322所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于 00ATA000002131212TAA 21011102132110 2121再由定理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)00B4AA2A3A40000所以求可达矩阵为P0000(5)因为PPT0010100110+10101000111111。 11111111101111∧1111111100001110＝01110111000111，所以{v1}，{v2，v3，v4} 111111因 1110 2010 + 1110 0110 2120312204+ 2120320101231323220 000 为 741 747，747 434构成G的强分图。 离散数学试题（B卷答案8） 一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R 证明 因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。(1)R 附加前提(2)PR P(3)P T(1)(2)，I(4)P∨Q P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS 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，|ABC|＝25－20＝5。故，不会打这三种球的共5人。 四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称 i13为由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，于是Usi。又显然有siU，所以U＝si。 i1i1i1i1i13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。 综上可知，{s1，s2，…，sr}是U的一个划分。 五、（15分）设R是A上的二元关系，则：R是传递的R*RR。 证明 (5)若R是传递的，则 反之，若R*RR，则对任意的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)fg是A到C的函数； (2)对任意的x∈A，有fg(x)＝f(g(x))。 证明 (1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使 对任意的x∈A，若存在y1、y2∈C，使得 综上可知，fg是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]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H， 离散数学试题（B卷答案9） 一、（10分）证明(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。证明：(P∧Q∧AC)∧(AP∨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∧(PQ))∨C (A∧(PQ))C。 二、（10分）举例说明下面推理不正确：xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))。 解：设论域为{1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。则： xy(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)))((TT)∨(TT))∧((TT)∨(TT))T yz(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))) ((FT)∨(FT))∧((FT)∨(FT)) T 但 xz(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)))((TF)∧(TF))∨((TF)∧(TF))F 所以，xy(P(x)Q(y))，yz(R(y)Q(z))xz(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，i11>，<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]RaiH i1i1kk又因为对H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|＝…＝|akH|＝|H|。因此 |G||aiH|i1k|aH|k|H|＝|H|·[G:H]。 ii1k 八、（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分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。 证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q) (P∧Q)∨(P∧Q)(QP)∧(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)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。 二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。 解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： AB∨C，BA，DCAD (1)A 附加前提(2)AB∨C P(3)B∨C T(1)(2)，I(4)BA P(5)AB T(4)，E(6)B T(1)(5)，I(7)C T(3)(6)，I (8)DC P(9)D T(7)(8)，I(10)AD CP 三、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(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的关系矩阵为： 10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的； 经过计算可得 10M(R2)111011101100M(R)，所以R是传递的。00 六、（15分）设函数f：R×RR×R，f定义为：f( (4)求复合函数ff和ff。 证明(1)对任意的x，y，x1，y1∈R，若f( (2)对任意的 1uwuwuwuw，y＝，则f( －1 ( xyxy，2xy(xy)>＝ 七、（15分）给定群 证明 对G中任意元a和b。 因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同33 333 2255 13 111理，由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、„、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。 （2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝ 解 下图满足条件但不连通。 12344333 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！ 一、【单项选择题】 (本大题共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 在半剖视图中半个视图与半个剖视图的分界线用（）。 （A）粗实线 (B)细实线 (C)细点画线 (D)波浪线 答案：（C） 局部放大图的标注中，若被放大的部分有几个，应用（）数字编号，并在局部放大图上方标注相应的数字和采用的比例。 （A）希腊 (B)阿拉伯 (C)罗马 (D)中国 答案：（C） 尺寸应该尽量标注在（D）上。 A、主视图 B、俯视图 C、左视图 D、特征视图 六个基本视图中最常用的是（）视图。 （A）主、右、仰 (B)主、俯、左 (C)后、右、仰 (D)主、左、仰 答案：（B）下图的A-A剖面图中，选出正确的断面图（）。 在下图中，选出正确的一组视图（）。 答案：C 下面右图用的是（）表示方法。 （A）全剖 （B）局部剖 （C）移出剖面 （D）重合剖面 答案：C 在下图中选出正确的剖视图。（） 答案：C 在下图中选出正确的局部剖视图。（） 答案：B 在下图中选出正确的剖视图。（） 答案：C 求作立体的相贯线。（12分） 一.标注尺寸（数值从视图中量取，比例1:1）（13分） 分析下列螺纹画法的错误,正确的打“√”, 错误的打“×”。（8分） (×)(√)(×)(×) 选择正确的移出剖面图（将正确的答案序号填入括号内）（6分）(b) 读齿轮轴零件图，在指定位置补画A-A断面图，并回答下列问题。（15分） 1．说明M12×1.5-6g含义：表示公称直径为12mm的细牙普通螺纹，M为螺纹代号，1.5为螺距,6g为中径和顶径的公差带代号。2．说明含义：⊥表示垂直度，0.03为垂直度公差，A为基准符号。 3．指出图中的工艺结构：它有 2 处倒角，其尺寸分别为 C2和C1.5，有 1 处退刀槽，其尺寸为 2×2。 模数其余218齿数压力角精度等级齿厚配对齿数8-7-7-3.142图号齿数齿 轮 轴制图校核比例数量材料 《物权法》期末考试试卷及答案 一、单选题 1.土地承包经营权属于()。 A.所有权 B.用益物权 C.担保物权 D准物权 2.相邻关系是不动产的相邻各方因不动产行使所有权或使用权而发生的权利义务关系，因此，相邻关系的客体是()。A.不动产 B.对不动产所有的权利 C.对不动产所负的义务 D.不动产权利人行使其所有权或者使用权过程中所体现的权益 3.根据《物权法》的规定，下列各项有关共有关系的表述中，不符合法律规定的是()。 A.按份共有人有权自由处分自己的共有份额，无需取得其他共有人的同意 B.共同共有人对共有财产的处分，必须征得全体共有人的同意 C.按份共有人将份额出让给共有人以外的第三人时，必须征得其他共有人的同意 D.共同共有关系终止，才能确定份额，分割共有财产 4.甲、乙、丙了人分别出资修建了一栋三层小楼。建楼前三人约定建成后甲、乙、丙分别住一 楼、二楼、三楼，但对楼房的所有权的归属未明确约定。楼房建成后，因对楼房的所有权归属发生争议，如果三人不能协商解决，该楼房的所有权()。 A.三人共同共有 B.三人按份共有 C.三人区分所有 D.甲拥有所有权，乙、丙拥有使用权 5.通过招标、拍卖、公开协商等方式承包()等农村土地，依照土地承包法等法律和国务院的有关规定。其土地承包经营权可以转让、入股、抵押或者以其他方式流转。 A.耕地 B.林地 C.荒地 D.草地 6.孙某有一辆汽车，估价20万元，6月1日向李某借款l0万元。订立了汽车抵押合同并于当天办理抵押登记。6月2日，向赵某借款10万元，又以该汽车抵押并办理了登记。后孙某不能还款，变卖汽车得款l6万元。关于抵押板，下列说法正确的是()。 A.赵某优先得到实现 B.他们处于同一顺序 C.李某优先得到实现 D.二者协商处理 7.甲公司向银行贷款，并以所持乙上市公司股份用于质押。根据《物权法》的规定：质押合同的生效时间是()。A.借款合同签订之日 B.质押合同签订之日 C.向证券登记机构申请办理出质登记之日 D.证券登记机构办理出质登记之日 8.甲遗失一部相机，乙拾得的后放在办公桌的抽屉内，并张贴了招领启事。丙盗走该相机，卖给了不知情的丁，丁出质于戊，对此下列说法不正确的是()。A.乙对相机的占有属于无权占有 B.丙对相机的占有属于他主占有 C.丁对相机的占有属于自主占有 D.戊对相机的占有属于直接占有 9.我国担保法规定的担保法规定的，担保物权包括：（）A.典权和抵押权 B.留置权、抵押权和质权 C.地上权和地役权 D.地役权、典权和质权 10.根据物权是否具有独立性不同，物权可以分为（）。 A.主物权和从物权 B.有期限物权和无期限物权 C.动产物权、不动产物权和权利物权 D．用益物权与担保物权 11.甲将自己所有的一套书卖给乙，但甲还想留阅一段时间，遂又与乙达成协议，借阅该书1个月，乙表示应允。乙取得该套书所有权的交付方法为（）。A.简易交付 B.占有改定 C.指示交付 D.拟制交付 12.所有人不明的埋藏物，所有权归（）。A.发现人 B.土地使用权人 C.国家 D．发现人和土地使用权人 13.下列财产所有权取得方法中，属于继受取得的是（）。 A．添附 B．生产 C．继承 D．拾得遗失物 14.下列财产中，不得抵押的是（）。 A.土地所有权 B.抵押人所有的房屋 C.抵押人所有的机器 D.在建工程 15.赵某孤身一人，因外出打工，将一祖传古董交由邻居钱某保管。钱某因结婚用钱，情急之下谎称该古董为自己所有，卖给了古董收藏商孙某，得款10000元。孙某因资金周转需要，向李某借款 20000 元，双方约定将该古董押给李某，如孙某到期不回赎，古董归李某所有。下列说法中正确的是：（）A．钱某与孙某之间的古董买卖合同无效 B．孙某取得该古董的所有权 C．李某对该古董的占有属于无权占有 D．赵某可以直接请求李某归还该古董 16.根据我国《物权法》规定，下列各项中，不属于物权的是：（）A．土地承包经营权 B． 建设用地使用权 C． 典权 D．海域使用 17.某小区拟解聘现有的物业管理机构，则下列关于业主表决情况的说法正确的是：（）A．应当经专有部分占建筑物总面积三分之二以上的业主或占总人数三分之二以上的业主同意 B．应当经专有部分占建筑物总面积三分之二以上的业主且占总人数三分之二以上的业主同 意 C．应当经专有部分占建筑物总面积过半数的业主且占总人数过半数的业主同意 D．应当经专有部分占建筑物总面积过半数的业主或占总人数过半数的业主同意 18.下列关于留置权的表述，正确的是（）。 A.留置权是用益物权 B.留置权是约定担保物权 C.留置权是自物权 D.留置权是法定担保物权 19.农民甲一家 4 口承包了本村 6 亩家庭承包地，并取得土地承包经营权证。后甲的女儿乙结婚嫁到外村，由于其夫家所在村农地紧张，致其在夫家始终未取得家庭承包地。甲所在村村委会依据自定的村规民约，抽回了乙 1.5 亩承包地，并作为家庭承包地补给本村村民丁经营管理。甲多次要求村委返还却遭拒绝。下列说法错误的是：（） A．村委会侵害了甲的土地承包经营权 B．女儿外嫁后收回承包地是村规民约，村委会并未侵权 C．甲可以请求丁返还该承包地 D．甲可以请求村委会赔偿其相应的损失 20.陈某向贺某借款20万元.借期2年，陈某以自己正在建造的房屋提供抵押担保并办理了登 记。下列说法中，符合《物权法》的是：()。A.贺某不享有抵押权。因为商品楼为在建工程，尚未完工 B.贺某不享有抵押权，只有以建成的房屋抵押，才符合《担保法》确定的抵押物范围 C.贺某享有抵押权，虽然商品楼正在建造中，但当事人办理了抵押物登记 D.贺某不享有抵押权，因为在建工程不属于《担保法》规定的抵押物范同 二、多选题 1.下列各项中，属于物权法上物的有哪些？（）A．无线电频谱 B．水流 C． 海域 D．空气 2.下列哪些权利可以作为权利质权的标的：（）A．汇票、本票、支票、债券、存款单、仓单、提单 B．依法可以转让的股份、股票、基金份额 C．商标专用权、专利权、著作权中的财产权 D．依法可以转让的债权 3.下列民事关系中，应按照相邻关系处理的是：（）A．甲在乙的房屋后挖菜窖，造成乙的房屋基础下沉，墙体裂缝引起纠纷 B．甲开发商购得一块土地的使用权，欲建一露天餐厅，其与该土地相邻的乙约定，乙不得再建露天餐厅，为此甲给予乙每年 3 万元的补偿 C．甲村在河流上游修建拦河坝，使乙村用水量剧减，引起纠纷 D．甲家与乙家相邻，甲家的猫闯入乙家，打碎乙家的花瓶，引起纠纷 4.在当事人对担保物权范围没有约定的情况下，下列各项中，属于担保物权担保范围的包括()。 A.主债权 B.主债权的利息 C.损害赔偿金 D.律师费 5.下列财产中，可以抵押的有（）。A.违章建筑物 B.机关法人的公益性财产 C.预购的房屋 D.抵押人所有的汽车 三、名词解释 1.善意取得 2.用益物权 3.占有改定 4.留置权 四、简答题 1.简述担保物权的特征。2.简述善意取得的构成要件。3.试述留置权取得的条件。 五、案例分析题 甲信用社、乙银行和丙公司在同一城市。丙与甲签订一金额为400万元的质权担保借款合同，质押财产为丙公司价值600万元的动产。合同签订后，丙即将质押财产转移给甲占有。嗣后，丙与乙签订一金额为280万元的借款、抵押合同，抵押物也为丙的上述动产，并办理了抵押权登记。合同到期后，丙无法向甲和乙偿还债务，甲和乙均要求以丙所提供的该担保财产优先清偿债务，从而引发纠纷。思考并回答下列问题： 1.质权设立的要件是什么？ 2.在同一财产之上既设立质权又设立抵押权，其效力如何？ 3.本案应如何处理？ 参考答案 一、单选题 1-5 BDCBC 6-10 CBBBA 11-15 BCCAB 16-20 CCDBC 二、多选题 1.ABC 2.ABCD 3.AC 4.ABC 5.CD 三、名词解释 1.善意取得亦称即时取得，是指无权处分他人财产的财产占有人，在不法将其占有的财产转让给第三人以后，如果受让人在取得该项财产时系出于善意，即依法取得该财产的所有权，原财产所有人不得要求受让人返还财产的制度。 2.用益物权，是指非所有权人对他人所有之物所享有的占有、使用和收益的他物权。其外延包括土地承包经营权、建设用地使用权、宅基地使用权、地役权等。 3.占有改定，是指在动产交易中出让人与受让人约定，由出让人继续直接占有动产，使受让人取得对于动产的间接占有，并取得动产的所有权。 4.留置权，是指债权人依债权占有属于债务人的动产，债务人未按照约定的期限履行债务时，债权人有权依法留置该财产，以该财产折价或者以拍卖、变卖该财产的价款优先受偿的担保物权。 四、简答题 1.担保物权的特征有： （1）担保物权以担保债权的实现为目的。（2分） （2）担保物权的标的是债务人或第三人所特有的特定动产、不动产或其他财产权利。（2分） （3）担保物权限制了担保人对担保标的物的处分权。（2分）（4）债权人享有对担保标的物的换价权。（2分）（5）担保物权能够担保其债权享有优先受偿权。（2分） 2、实行善意取得的结果，是物的原所有人丧失其所有权，善意受让人则取得所有权。其要件是： （1）受让人在受让时不知道或者不应当知道转让人无处分权，即善意。（3分） （2）以合理的价格有偿受让。（2分） （3）转让的财产依照法律规定应当登记的已经登记，不需要登记的已经交付给受让人。（3分） （4）转移占有的财产须是法律允许流通的动产和不动产。（2分） 3、留置权成立要件分为积极要件和消极要件 （一）留置权成立的积极要件，是留置权成立所应具备的事实，包括以下三项： （1）须债权人合法占有债务人的动产。（1分）（2）须债权的发生与该动产有牵连关系。（2分）（3）须债权已届清偿期且债务人未履行债务。（2分） （二）留置权成立的消极要件通常有以下五项：（1）须当事人事先无不得留置的约定。（1分） （2）须留置债务人的财产不违反公共秩序或善良风俗。（1分）（3）须留置财产与债权人的义务不相抵触。（1分） （4）须留置财产与对方交付财产前或交付财产时所为的指示不相抵触。（1分） （5）对动产的占有须非因侵权行为而取得。（1分） 五、案例分析题 1、在本案中，丙公司与甲信用社签订质权担保合同，（2分）质押财产已经转移占有，（2分）符合质权设立的要求，质权合同生效，甲信用社取得质权。（1分） 2、在同一财产之上既设立质权又设立抵押权的，其效力规则有：（1）在同一财产上，法定登记的抵押权与质权并存时，抵押权人优先于质权人受偿（3分） （2）对于无须办理登记即可成立的抵押权，仍然必须按照权利设定的前后并考虑其他因素加以判定：一是当动产上先设定抵押权后设定质权时，如果抵押权已经登记的，抵押权人优先于质权人受偿；二是先成立的抵押权未经登记，则其不能对抗善意第三人。（4分）（3）当动产上先设定质权后设定抵押权时，无论该抵押权是否办理登记，都不能对抗设定在先的质权。（3分） 3、本案属于先设定质权后设定抵押权，因此，该抵押权不能对抗设定在先的质权。法官审理这一案件，应当判决甲信用社优先受偿，就剩余部分，乙银行受偿。（5分）第三篇：离散数学期末考试试题及答案
第四篇：《机械制图》期末考试试卷答案
第五篇：《物权法》期末考试试卷及答案
点击咨询 