离散数学试卷答案（精选6篇）
篇1：离散数学试卷答案
离散数学试题(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、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，使 对任意的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且∈A×C，h()＝ 证明：1）先证h是满射。 2）再证h是单射。 、∈A×C，若h()＝h()，则 到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。 综合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=,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)(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是自反的，则∈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分）若 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)偏序集是否有最大元？(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，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，所以∈R。 － － 若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以 － － －a>∈R。 若∈R， － － －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]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R＝aH。 离散数学试题（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小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条（）A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（）A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是（）A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是（）A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有（）A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是（）A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，〉，Z是整数集，定义为xxy=xy,x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉〈,a,c〉}，则关系R的对称闭包S(R)是（）A.R∪IA B.R C.R∪{〈c,a〉} D.R∩IA 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取（）A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是（）A.∈ B. C.{} D.{}∈ 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 专注于收集各类历年试卷和答案 D.(x)(y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于（）A.(x)A(x)→B B.(x)A(x)→B C.A(x)→B D.(x)A(x)→(x)B 13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x（）A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元 14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为（）A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命题公式中，为永假式的是（）A.p→(p∨q∨r) B.(p→┐p)→┐p C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元；若〈s,*〉有零元，则|s|=______。19.设A为集合，P(A)为A的幂集，则〈P(A)，是格，若x,y∈P(A),则x,y最大下界是______，〉最小上界是______。 20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ranf=Y，则称f是______函数。 21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则 〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。 22.使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。24.若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是相容的，若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是不相容的。 25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。 三、计算题(共30分)26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。 27.(5)设A={a,b},P(A)是A的幂集，是对称差运算，可以验证 是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系 R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA; 专注于收集各类历年试卷和答案 (1)作出偏序关系R的哈斯图 (2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。 30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。 31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。 四、证明题(共20分)32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。 33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。 证明：〈F, 〉是群。 34.(6分)在个体域D={a1,a2,„，an}中证明等价式： (x)(A(x)→B(x))(x)A(x)→(x)B(x) 五、应用题(共15分)35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。 36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么? 参考答案 一、单项选择题(本大题共15小题，每小题1分，共15分) 1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C 二、填空题 16.0 17.1 0 18.单位元 19.x∩y x∪y 20.入射 满射 21.［x］R=［y］R 22.A(x) B(y)23.(M(x)→D(x)) M(x)→D(x) 专注于收集各类历年试卷和答案 24.可满足式 永假式(或矛盾式)25.陈述句 真值 三、计算题 1100101026.M= 1011001122M=21110111 121011M2ij18,ij6 M2i1i1j144 G中长度为2的路总数为18，长度为2的回路总数为6。 27.当n是偶数时，x∈P(A),xn= 当n是奇数时，x∈P(A),xn=x 于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n =(｛a｝-1)n｛b｝n｛a｝n= 当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝= 28.(1)偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4，下确界4； 上界：无，上确界：无 29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q)) ((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q)) (┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q)) (┐(P∧┐Q)∨(P∧┐Q)) (P∧Q)∨(P∧┐Q) P∧(Q∨┐Q) P∨(Q∧┐Q) (P∨Q)∧(P∨┐Q) 命题为真的赋值是P=1,Q=0和P=1,Q=1 专注于收集各类历年试卷和答案 30.令e1=(v1,v3)，e2=(v4,v6) e3=(v2,v5)，e4=(v3,v6) e5=(v2,v3)，e6=(v1,v2) e7=(v1,v4)，e8=(v4,v3) e9=(v3,v5)，e10=(v5,v6) 令ai为ei上的权，则 a1 取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=15 31.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2) (换名) ┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2) x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2) x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2) 四、证明题 32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的 xy d(vi)=2(x+y-1)。 i又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是 xy d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1 从而2(x+y-1)≥x+2y+2k-4 x≥2k-2 33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空 (1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。 (2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。 (3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元 (4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元 由此上知〈F，〉是群 34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x)) 专注于收集各类历年试卷和答案 (┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an))) (┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an)) ┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an)) ┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x) 五、应用题 35.令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 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。 根据：构造无向简单图G= Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。 关键词：离散数学,教学方法 离散数学是现代数学的一个重要分支, 是以研究离散量的结构和相互间关系为主要目标的一门计算机专业核心基础课程.它不仅是计算机科学的理论基础, 也是培养学生缜密思维、提高学生数学素养的主要课程.因此, 研究如何提高离散数学课程的教学水平和教学质量具有非常重要的意义. 一、激发学生学习兴趣 爱因斯坦说过:“兴趣和爱好是最大的动力.”兴趣是最好的老师, 学生只有对离散数学产生了兴趣, 才会主动去学习, 探究.因此在教学过程中, 教师应特别注重学生学习兴趣的培养, 充分调动学生的积极性, 使学生学得轻松愉快, 才能充分发挥学生的主观能动性. 对于任何一门课程来说, 第一次课都是很重要的, 往往决定了学生能否对这门课程产生兴趣.在离散数学的第一次课上, 教师应该介绍离散数学的组成部分和发展过程, 而集合论作为离散数学的基础和重要组成部分, 我们可以首先讲述下面这个小故事. 这是《堂吉诃德》中的一个故事:堂吉诃德的仆人桑乔·潘萨跑到一个小岛上, 成了这个岛的国王.他颁布了一条奇怪的法律:每一个到达这个岛的人都必须回答一个问题:“你到这里来做什么?”如果回答对了, 就允许他在岛上游玩, 而如果答错了, 就要把他绞死.对于每一个到岛上来的人, 或者是尽兴地玩, 或者是被吊上绞架.有多少人敢冒死到这岛上去玩呢?一天, 有一个胆大包天的人来了, 他照例被问了这个问题, 而这个人的回答是:“我到这里来是要被绞死的.”请问桑乔·潘萨是让他在岛上玩, 还是把他绞死呢?如果应该让他在岛上游玩, 那就与他说“要被绞死”的话不相符合, 这就是说, 他说“要被绞死”是错话, 既然他说错了, 就应该被处绞刑.但如果桑乔·潘萨要把他绞死呢?这时他说的“要被绞死”就与事实相符, 从而就是对的, 既然他答对了, 就不该被绞死, 而应该让他在岛上玩.小岛的国王发现, 他的法律无法执行, 因为不管怎么执行, 都使法律受到破坏.他思索再三, 最后让卫兵把他放了, 并且宣布这条法律作废. 通过这个故事不但可以让学生们了解什么是朴素集合论中的悖论, 而且让学生们知道离散数学所讲述的不仅仅是枯燥的定义和定理, 还和我们现实生活中的事物息息相关的, 从而让学生在第一堂课就对离散数学产生浓厚的兴趣. 二、适当选择教学内容 《离散数学》是一门相对于“连续数学”而命名的数学分支, 它包括多个彼此独立的数学分支, 主要有数理逻辑、集合论、代数系统和图论几大部分, 这些知识点具有或多或少的联系, 但是又自成体系, 每一部分都可作为一个相对独立的分支来进行教学.近年来所出版的一些教材又加入了离散概率等内容, 而与之相矛盾的是各学校在不断地缩减离散数学课程的学时数.如何在有限的学时内选择合理的教学内容成为该课程教学中面临的重要问题. 首先在内容的深度和广度上应进行更新, 修正有些教材的知识面过大、难度过深的教学安排, 以便更适合我们的教学对象, 收效较好;其次添加实际应用教学, 在教学中添加若干上机编程题、设计题和学科论文等训练内容, 使学生加深对离散数学的理解和认识;最后在教学内容上要强调基本方法和技能, 要求学生掌握重要定理的证明和一些常用的解题方法, 如数理逻辑中的命题逻辑、谓词逻辑推理方法、关系论中的几种关系、函数映射中的方法, 等等. 三、科学运用教学方法 《离散数学》课程具有抽象性强而且内容多的特点.在传统的教学模式下, 教师向学生传播知识, 一般通过板书向学生传授, 其输出量比较低, 常常会受到板面的限制和时间的限制, 在此过程中花费大量时间, 不利于讲解和提问互动, 学生会难以理解和记忆;多媒体教学传递的信息量大, 速度快, 课前制作的课件可以节省上课板书时间, 把概念之间的联系以结构图的形式给出, 知识点清晰, 框架清楚, 易于学生记忆, 但在解题时不利于展示数学思维的过程.因此, 在实际教学中, 要适当地把板书形式和多媒体形式教学结合起来, 对于概念定理、公式推导等叙述性内容, 采用多媒体演示;对于例题的演算等思维性内容, 采用传统的板书形式, 一步步推导, 展示数学思维的全过程.这种传统教学方式与现代教学手段相结合的教学方法, 保证了上课时间的充分利用, 增加了课堂信息量, 又不至于使学生陷入一种“看电影”的状态, 很受学生的欢迎. 另外, 在做好课堂教学的同时, 还要充分利用网络辅助教学平台.在条件允许的情况下, 建立离散数学教学网站, 网站将包括以下内容:课程介绍、教学大纲、授课计划、教师队伍、电子教案、学生自测系统、习题库、网上答疑、实验指导、参考文献目录、教学录像等.另外本着方便学生的目的, 网站还提供与本课程相关的外文资料和电子图书, 以及方便学生考研的模拟试题和各高校历年考题. 参考文献 [1]刘叙华, 虞恩蔚, 姜云飞.离散数学[M].北京:中国广播电视大学出版社, 1993. [2]屈婉玲, 耿素云, 张立昂.离散数学:第2版[M].北京:清华大学出版社, 2008. [3]何中胜.离散数学教学中的问题分析与对策研究[J].高等理科教育, 2007 (5) :107-109. [4]王伟静, 彭慧伶.离散数学课程教学问题分析与对策研究[J].科技创新导报, 2009 (18) :150. 摘要：为了激发学生的学习热情，培养其思维能力和应用能力，根据离散数学课程教学的特点，笔者结合课程教学经验，对离散数学教学进行了研究.文章提出一些教学方法和手段的改革，在实际教学中起到了一定的作用，提高了教学质量. 关键词： 离散数学，教学方法，教学手段 【中图分类号】O158-4 On the Teaching "Discrete Mathematics" in Chenxue Gang Zhou Jiquan （North China Electric Power University Mathematics， Beijing， 102206， China） Abstract： In order to stimulate students' enthusiasm for learning， develop their thinking skills and ability， according to the characteristics of Discrete Mathematics Instruction， author of Teaching experience， discrete mathematics teaching were studied. This paper presents some of the reform of teaching methods and means， in the actual teaching has played a certain role in enhancing the quality of teaching. Keywords： discrete mathematics， teaching methods， teaching means 《离散数学》是计算机科学中重要的基础理论课程之一，它不仅是许多计算机专业课的必备基础，而且对培养学生抽象思维能力和逻辑推理能力有着重要的作用.然而采用以往的教学方法，教学效果往往不够理想.一方面，离散数学知识的分散性令许多学生感到无从下手.另一方面，在传统的离散数学教学中，往往采用“纯数学”教学方法，学生不能很好地体会离散数学对计算机科学的重要意义，所以学习积极性不高.因此，通过教学方法和手段的改革来激发和增强学生的学习兴趣，从而培养学生的创新思维和综合能力，是离散数学教学中非常迫切的需求.本文结合作者近年来从事离散数学课程教学的经验，从教学内容、教学方法、教学手段等方面进行了一些初步探讨. 1精选教学内容 《离散数学》教学内容主要包括数理逻辑、集合论、代数结构及图论等几大分支.各分支均有悠久历史.如果这几部分的内容都要详细讲授，时间上来不及，所以在在教学过程中对讲授内容的选择应当有所侧重.比如简单介绍集合论的理论基础，重点是如何利用集台论的方法解决实际应用问题.在二元关系这部分，重点是二元关系的几个与性质相关问题的论证方法的训练.在数理逻辑上通过将一般命题公式和一阶逻辑公式化成范式，达到强化训练学生逻辑演算能力.图论部分重点放在基本概念的理解和实际问题的处理上，通过对相关定理及其证明思路的理解来体会图论的研究方法.代数系统这部分内容重点放在群论上，尤其要在代数系统、群、子群、循环群、变换群、正规子群的概念及相关问题的理解上下功夫. 2 教学方法探讨 2.1 增加讨论课 老师首先选定讨论的课题，学生分组准备查询相关的文献，并形成自己观点.在讨论课上大家共同交流探讨，从而加深对这门课程的认识.最后各小组完成论文的书写.该方法不仅可以提高学生对离散数学重要性的认识，还可以提高学生互相协作的能力以及书写论文的能力. 2.2 增加趣味性，激发学生的学习兴趣. “兴趣是 最好的老师”，只有激发起学生的学习兴趣，他们才有真正自主学习的欲望.在教学过程中，根据具体的知识点，介绍它的发展史或者引入趣味问题，增加了学生学习离散数学的兴趣，拓宽了学生们的知识面，提高了学生对离散数学课程学习的积极性与主动性. 2.3 注重归纳与小结 离散数学的内容虽然多且散，但通过归纳和小结，可以用一条主线贯穿始终.离散数学讨论的内容主要包含系统中涉及到的静态（基本概念）与动态（运算、操作、推理）.如集合论中是元素（静态）及其上的运算（动态）；代数系统中是集合（静态）及运算（动态）；数理逻辑中是公式（静态）和推理（动态）.通过归纳与小结，学生能够理清头绪，提高学习效率. 3 教学手段改革 3.1 教学网站建设 信息技术对提高教学质量具有重要的影响，必须予以高度重视.为了提高教学质量，我们建设了一个教学支撑网站，一方面大力推进信息技术在教学中的实际运用，促进教学手段和教学方法现代化；另一方面以此提高教与学的效率. 3.2 重视学生作业，定时测验 离散数学的知识不经过学生的独立思考和多做练习是无法牢固掌握的，因此一定要给学生留一定数量的课后习题.但大部分学生不可能把课本上的习题全部做完，教师也不可能完全批阅.这就要求教师布置作业要选其精华，选题必须要有一定的深度和广度，要覆盖所学的内容，尽量选有启发性质的习题.对于学生的作业，要认真仔细批改，将作业中暴露出来的普遍问题，要进行课堂讲评.通过讲评作业，帮助学生澄清模糊和错误的认识. 3.3 新的考核方式 传统的考核方法就是试卷考试，考察学生的基本知识和基本技能，以及解难题的能力.我们尝试做了一些考核方法的改革，把原来的试卷考试和平时的考核两部分，改成了三部分成绩的统一， 即添加了一个新的内容：写离散数学的论文.把它的评定结果作为成绩的一个重要部分.所写论文必须要求观点明确、主题鲜明和论述严谨，并且具有一定的创新. 4 结束语 总之，要把离散数学这一门课教好，教师就要不断研究新的教学方法和手段，认真掌握教学规律，借助于现代化教学手段，提倡“启发”式教学.教师只要具有扎实的理论功底，并具有对学生高度负责的精神，就一定能够达到良好的教学效果. 参考文献： [1]赵青杉，孟国艳.关于离散数学教学改革的思考[J].忻州師范学院学报，2005，21（5）：6 . [2]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2001. [3]翁梅，刘倩，冯志慧等.“离散数学”课程教学实践与探索[J].计算机教育，2004（12）：62—63. [4]钟敏，时念云.改革课程实验提高离散数学教学质量 [J].计算机教育，2008，18. [5] 张艳华，周雪琴，马新娟，王举辉，张立红. 基于卓越工程师的“离散数学”教学改革探索[J]. 当代教育理论与实践. 2013（12） 11、填充下面推理证明中没有写出的推理规则。前提：pq,qr,rs,p 结论：s 证明：① p 前提引入 ②pq 前提引入 ③ q （①②析取三段论）④qr 前提引入 ⑤ r （③④析取三段论）⑥rs 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。前提：p(qr),q(rs)结论：(pq)s 证明：①(pq) （附加前提）② p （①化简规则）③ q （①化简规则）④p(qr) 前提引入 ⑤qr （②④假言推理）⑥ r （③⑤假言推理）⑦q(rs) 前提引入 ⑧(rs) （③⑦假言推理）⑨ s （⑥⑧假言推理） 13、前提：(pq)q,pq,rs 结论1：r 结论2：s 结论3：rs （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。（2）证明从此前提出发，推任何结论的推理都是正确的。证明：（1）①(((pq)q)(pq)(rs))r ((pq)q)(pq)(rs))r1 ②(((pq)q)(pq)(rs))s ((pq)q)(pq)(rs))s1 ③(((pq)q)(pq)(rs))(rs) ((pq)q)(pq)(rs))rs1 即结论1，结论2，结论3的推理都是正确的。 （2）((pq)q)(pq)(rs) ((pq)q)(pq)(rs)(pqq)(pq)(rs)0(pq)(rs)0 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明：（1）前提：p(qr)，p,q 结论：rs 证明：①p(qr) 前提引入 ② p 前提引入 ③ (qr) ① ②假言推理 ④ q 前提引入 ⑤ r ③ ④假言推理 ⑥ rs ⑤ 附加律 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：p(qr)，sp,q 结论：sr 证明： ① s 附加前提引入 ② sp 前提引入 ③ p ① ②假言推理 ④ p(qr) 前提引入 ⑤ qr ③ ④假言推理 ⑥ q 前提引入 ⑦ r ⑤ ⑥假言推理 即根据附加前提证明法，推理正确。 16、在自然推理系统P中用归谬法证明下面的推理： 前提：pq，qr,qs 结论：rs 证明： ① (rs) 结论否定引入 ② pq 前提引入 ③ qr 前提引入 ④ qs 前提引入 ⑤ rs ② ③ ④构造性二难 ⑥ (rs)(rs) ① ⑤ 合取 因为⑥为矛盾式即推理正确 17、在自然推理系统P中构造下面推理的证明： 只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间，如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 答：令p: A到过受害者房间 q: A在11点以前离开 r: A是谋杀嫌犯 s: 看门人看见过A 前提：(pq)r,p,qs,s 结论：r 证明：① qs 前提引入 ② s 前提引入 ③ q ① ②拒取式 ④ p 前提引入 ⑤ pq ③ ④合取 ⑥(pq)r 前提引入 ⑦ r ⑤ ⑥假言推理 1114490009 一、填空题 1、设是偏序集,如果_________, 则称是(偏序)格.2、设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____,a∧a′=______.3、一个格称为布尔代数，如果它是______格和______格.4、设<>是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____.二、证明题 1、设 a∧cb∧d2、证明：在有补分配格中，每个元素的补元一定唯一。 3、设 R={ | ab=b}是S上的偏序关系 4、若是一个格，则对任意a、b、cA，有若a≤c且b≤c，则a∨b≤c。 5、若是一个格，则对于任意a，bA，证明以下两个公式等价； （1）a≤b （2）a∨b =b6、证明：如果格中交对并是分配的，那么并对交也是分配的，反之亦然。 7、如果是有界格，全上界和全下界分别是1和0，则对任意元素aA，证明： 【离散数学试卷答案】相关文章： 离散数学试卷及答案08-19 离散数学试卷及答案二01-16 离散数学试题答案07-09 离散数学期末试题答案01-16 离散数学最全课后答案01-16 离散数学屈婉玲答案05-20 屈婉玲版离散数学课后习题答案05-02 离散数学期末试卷05-01 离散数学期末考试07-09 离散数学集合周记07-09篇2：离散数学试卷答案
篇3：《离散数学》课程教学探讨
篇4：浅谈《离散数学》的教学
篇5：离散数学习题三 含答案
篇6：离散数学习题与参考答案