离散数学考试试题(A卷及答案)

第一篇：离散数学考试试题(A卷及答案)

离散数学考试试题（A卷及答案）

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((PQ)∧Q)((Q∨R)∧Q)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)永真式；2）永假式；3)可满足式。

二、（8分）个体域为{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+1=4））（0∨0）∧（0∨1）1∧10

三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？

解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。

四、（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分)75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。

由容斥原理，得

|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以

|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。

六、（12分）已知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、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分）是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：也是个群。

证明：1）a,b∈G，ab=a*u-1*b∈G，运算是封闭的。

2）a,b,c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。

4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*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。

解：D的邻接距阵A和可达距阵P如下：

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

0 0 1 0 0

P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝148

离散数学考试试题（B卷及答案）

一、（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＝{，，，，，，，，} i1i

4232-

1六、(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-1-

1-1-1a=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|，与简单无向平面图-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为：(写过程，7分)

（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 5

第二篇：离散数学考试试题(A、B卷及答案)test2

离散数学考试试题(A卷及答案）

一、证明题（10分）

1)(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。P<->Q=(p->Q)合取（Q->p）证明:(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

2)(PQ) PQ。

证明：(PQ)((P∧Q))(P∨Q))PQ。

二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(QR))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。

证明：

公式法：因为(P(Q∨R))∧(P∨(QR))

(P∨Q∨R)∧(P∨(Q∧R)∨(Q∧R))

(P∨Q∨R)∧(((P∨Q)∧(P∨R))∨(Q∧R))分配律

(P∨Q∨R)∧(P∨Q∨Q)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

M4∧M5∧M6使（非P析取Q析取R）为0所赋真值，即100，二进制

为

4m0∨m1∨m2∨m3∨m7

所以，公式(P(Q∨R))∧(P∨(QR))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

真值表法：

为000、001、010、011、111：成假赋值为：100、101、110。

三、推理证明题（10分）

1）P∨Q，Q∨R，RSPS。

证明：

(1)P附加前提(2)P∨QP

(3)QT(1)(2)，I（析取三段论）(4)Q∨RP

(5)RT(3)(4)，I（析取三段论）(6)RSP

(7)ST(5)(6)，I（假言推理）(8)PSCP

2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))

证明（1）xP(x)(2)P(a)

(3)x(P(x)Q(y)∧R(x))(4)P(a)Q(y)∧R(a)(5)Q(y)∧R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)∧R(a)(10)x(P(x)∧R(x))

(11)Q(y)∧x(P(x)∧R(x))

五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C)（10分）

证明：因为

x∈(A∪B)－Cx∈(A∪B)－C

x∈(A∪B)∧xC (x∈A∨x∈B)∧xC

(x∈A∧xC)∨(x∈B∧xC)x∈(A－C)∨x∈(B－C)x∈(A－C)∪(B－C)

所以，(A∪B)－C＝(A－C)∪(B－C)。

八、证明整数集I上的模m同余关系R={|xy(mod m)}是等价关系。其中，xy(mod m)的含义是x-y可以被m整除（15分）。X(modm)=y(modm)证明：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）-1=f-1g-1（10分）。

证明：

因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推f-1g-1：C→A是双射。

因为∈f-1g-1存在z（∈g-1∈f-1）存在z（∈f∈g）∈gf∈（gf）-1,所以（gf）-1=f-1g-1。

1离散数学考试试题(B卷及答案）

一、证明题（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析取要使之为假，即赋真值001，即M1 m0∨m2∨m3使之为真

三、推理证明题（10分）

1)(P(QS))∧(R∨P)∧QRS

证明：(1)R(2)R∨P(3)P

p

T（1）（2）析取三段论 p

T（3）（4）I假言推理 P

T（5）（6）I假言推理 CP

(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)PT(2)E(4)xA(x)QP(5)(xA(x)Q)∧(QxA(x))T(4)E(6)QxA(x)T(5)I(7)QPT(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分）。有就是1，没就是0

七、设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><5,5>}（自反闭包）

s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}（对称闭包）t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}（传递

闭包）

九、设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－

1、g－1和h－1（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－1＝hg；由fhg＝IB，得g－1＝fh；由gfh＝IC，得h－1＝gf。

第三篇：离散数学考试试题(A、B卷及答案)test7

离散数学考试试题（A卷及答案）

一、（10分）证明(A∨B)(P∨Q)，P，(BA)∨PA。

证明：(1)(A∨B)(P∨Q)

P(2)(P∨Q)(A∨B)

T(1)，E(3)P

P(4)A∨B

T(2)(3)，I(5)(BA)∨P

P(6)BA

T(3)(5)，I(7)A∨B

T(6)，E(8)(A∨B)∧(A∨B)

T(4)(7)，I(9)A∧(B∨B)

T(8)，E(10)A

T(9)，E

二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：

(1)甲和乙只有一人参加；(2)丙参加，丁必参加；(3)乙或丁至多参加一人；(4)丁不参加，甲也不会参加。请推出哪两个人参加了围棋比赛。

解

符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。依题意有，(1)甲和乙只有一人参加，符号化为AB(A∧B)∨(A∧B)；(2)丙参加，丁必参加，符号化为CD；(3)乙或丁至多参加一人，符号化为(B∧D)；(4)丁不参加，甲也不会参加，符号化为DA。所以原命题为：(AB)∧(CD)∧((B∧D))∧(DA)((A∧B)∨(A∧B))∧(C∨D)∧(B∨D)∧(D∨A)((A∧B∧C)∨(A∧B∧C)∨(A∧B∧D)∨(A∧B∧D))∧((B∧D)∨(B∧A)∨(D∧A))(A∧B∧C∧D)∨(A∧B∧D)∨(A∧B∧C∧D)T

但依据题意条件，有且仅有两人参加竞赛，故A∧B∧C∧D为F。所以只有：(A∧B∧C∧D)∨(A∧B∧D)T，即甲、丁参加了围棋比赛。

三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。(1)x(P(x)Q(x))

P(2)P(y)Q(y)

T(1)，US(3)xP(x)

P(4)P(y)

T(3)，ES(5)Q(y)

T(2)(4)，I(6)xQ(x)

T(5)，EG 解

(4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。

正确的推理过程为：

(1)xP(x)

P(2)P(c)

T(1)，ES

(3)x(P(x)Q(x))

P(4)P(c)Q(c)

T(3)，US(5)Q(c)

T(2)(4)，I(6)xQ(x)

T(5)，EG

四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。

解

设R＝{，，，}，则 因为R，R不自反； 因为∈R，R不反自反；

因为∈R，R，R不对称； 因为∈R，∈R，R不反对称；

因为∈R，∈R，但R，R不传递。

五、（15分）设函数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是单射。

六、（15分）设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得TR且R，证明T是一个等价关系。

证明

因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。

若∈T，即∈R且∈R，也就是∈R且∈R，从而∈T，故T对称。若∈T，∈T，即∈R且∈R，∈R且∈R，因R传递，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T传递。

所以，T是A上的等价关系。

七、（15分）若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b1∈H。－证明

必要性：对任意的a、b∈H，由是的子群，必有b1∈H，从而a*b1∈H。

－

－充分性：由H非空，必存在a∈H。于是e＝a*a1∈H。

－任取a∈H，由e、a∈H得a1＝e*a1∈H。

－

－对于任意的a、b∈H，有a*b＝a*(b1)1∈H，即a*b∈H。

－

－又因为H是G非空子集，所以*在H上满足结合律。综上可知，是的子群。

八、（15分）(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？

证明

(1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。

(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。

uwv离散数学考试试题（B卷及答案）

一、（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，1>，<5，4>，i1<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0A200111022010A302111020111203220A4120301012313 2322所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于

00TAA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。

00(4)因为B4AA2A3A40000以求可达矩阵为P00111111。

11111110100110+

101010001110



2010

+

1110



01102120312204+

2120320101231323220

000741



747，所

747



43400(5)因为PPT0011101111∧1111111100001110＝01110111000111，所以{v1}，{v2，v3，v4}构成G的强分图。

111111 6

第四篇：离散数学考试范围

第一部分 简单命题符号化，求主析取范式，判断公式类型（重言式，矛盾式，可满足式）量词消去规则。命题逻辑推理规则

带全称量词和存在量词的命题逻辑推理的构造和证明 第二部分

集合基本运算，文氏图 有序对的基本知识，笛卡儿积，特征函数

函数的性质（单射，满射，双射）

集合的基本概念（交集，并集，幂集，定义域，值域）

给出关系图，画出r(R)，s(R)，t(R)等价关系及等价划分 集合相等证明

从A到B的函数的性质

关系的性质（自反，对称，传递）偏序关系和哈斯图

A卷

1、选择10题（2*10=20分）

2、填空8题（1*15=15分）

3、综合题（6题，39分）（1）前束范式

（2）偏序关系和哈斯图（3）文氏图（4）关系的闭包

（5）用真值表判断公式的成真赋值（6）量词消去

4、证明题（3题，共26分）自然推理系统证明（第三章）集合相等证明

命题逻辑推理证明（第五章）B卷

1、填空10题（2*10=20分）

2、选择10题（1*10=10分）

3、综合题（6题，44分）（1）主析取范式判断公式类型（2）量词消去，求公式真值（3）集合计算（4）量词消去（5）前束范式

（6）偏序关系和哈斯图

4、推理填空题（8分）

5、证明题（18分）集合相等证明 命题逻辑推理证明

第五篇：离散数学考试大纲

武汉理工大学2011年博士入学考试《离散数学》考试大纲

一、考试要求共济

要求考生系统地掌握离散数学的基本概念、基本定理和方法，具有较强的逻辑思维和抽象思维能力，能够灵活运用所学的内容和方法解决实际问题。考

二、考试内容济

1、数理逻辑济

1)命题和联结词，谓词与量词，合适公式，赋值，解释与指派，范式共

2)命题形式化，等价式与对偶式，蕴含式，推理与证明

3)证明方法3

4)数学归纳法

2、集合论院

1)集合代数，笛卡尔乘积，关系与函数，关系的性质与运算

2)等价关系，划分共济

3)偏序关系与偏序集，格辅导

3、计数336260 37

1)排列与组合，容斥原理，鸽巢原理共

2)离散概率正门

3)函数的增长与递推关系院

4、图论 共济网

1)欧拉图与哈密顿图，平面图与对偶图，二部图与匹配，图的着色021-

2)树，树的遍历，最小生成树正门

3)最短路经，最大流量

5、形式语言与自动机 院

1)语言与文法，正则表达式与正则集

2)有限状态自动机，自动机与正则语言

6、代数系统

1)二元运算，群与半群，积群与商群，同态与同构

2)群与编码

3)格与布尔代数，环与域

三、试卷结构

1、考试时间为3小时，满分100分。

2、题目类型：计算题、简答题和证明题。

参考书

1．离散数学，胡新启，武汉大学出版社，2007年。

2．离散数学，尹宝林、何自强、许光汉、檀凤琴等，高等教育出版社，1998年。

3．离散数学及其应用，Kenneth H.Rosen，机械工业出版社，2002年。