离散数学期末试题

第一篇：离散数学期末试题

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

一、（10分）求(PQ)(P∧(Q∨R))的主析取范式 解：(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

二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？

解 设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：P∧Q 乙：Q∧P 丙：Q∧R

王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：

((P∧Q)∧((Q∧R)∨(Q∧R)))∨((Q∧P)∧(Q∧R))(P∧Q∧Q∧R)∨(P∧Q∧Q∧R)∨(Q∧P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)P∧Q∧R T 因此，王教授是上海人。

三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。

证明 设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。

若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)R。则 ''sr(R)s(R)＝R，进而有tsr(R)t(R)＝R。

综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。

四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{，，，，，，，，，，，，，}，(1)写出R的关系矩阵。

(2)判断R是不是偏序关系，为什么？ 解(1)R的关系矩阵为： ''''10M(R)000111111010101

00110001(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：

10M(R2)000由以上矩阵可知R是传递的。

111111010101M(R)

00110001

五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。证明：因为

∈(A－B)×Cx∈(A－B)∧y∈C

(x∈A∧xB)∧y∈C

(x∈A∧y∈C∧xB)∨(x∈A∧y∈C∧yC)(x∈A∧y∈C)∧(xB∨yC)(x∈A∧y∈C)∧(x∈B∧y∈C)∈(A×C)∧(B×C)∈(A×C)－(B×C)所以，(A－B)×C＝(A×C－B×C)。

六、（10分）设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。

解 因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

七、（15分）设是一代数系统，运算*满足交换律和结合律，且a*x＝a*yx＝y，证明：若G有限，则G是一群。

证明 因G有限，不妨设G＝{a1，a2，…，an}。由a*x＝a*yx＝y得，若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。令e∈G使得a*e＝a。对任意的b∈G，令c*a＝b，则b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由运算*满足交换律得e*b＝b，所以e是关于运算*的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由运算*满足交换律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。

八、（20分）（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（2）给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥Cm1＋2，则G是哈密尔顿图。

2证明 若n≥Cm。1＋2，则2n≥m－3m＋6（1）

2若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝

wVd(w)＜m＋(m－2)(m－3)＋m＝m－

23m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。离散数考试试题（B卷及答案）

一、（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反自反的；由于矩阵不对称，R不是对称的；

经过计算可得

1011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，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wuw，y＝，则f()＝<＋，－22222uw>＝，所以f是满射。2(3)f()＝<－1－1uwuw，>。22－1

－1(4)ff()＝f(f())＝f()＝<

xyxyxy(xy)，>＝

444

55ff()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）给定群，若对G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，3试证是Abel群。

证明 对G中任意元a和b。

因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同理，由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。

由于(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＝是不连通的例子。解 下图满足条件但不连通。

12344

333334

34333

4333

133

113

122244 6

第二篇：《离散数学》期末复习

《离散数学》期末复习

内容：第一章~第七章 题型：

一、选择题（20%，每题2分）二．填空题（20%，每题2分）

三、计算题（20%，每题5分）

四、证明题（20%，每题5分）

五、判断题（20%，每题2分）

第1章 数学语言与证明方法

1.1 常用的数学符号

1.计算常用的数学符号式子 1.2 集合及其表示法

1.用列举法和描述法表示集合

2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集

5.求集合的运算：并、交、相对补、对称差、绝对补

6.用文氏图表示集合的运算 7.证明集合包含或相等

方法一： 根据定义, 通过逻辑等值演算证明

方法二： 利用已知集合等式或包含式, 通过集合演算证明

1.3 证明方法概述

1、用如下各式方法对命题进行证明。 直接证明法：AB为真

 间接证明法：“AB为真”  “ ¬B ¬A为真”  归谬法(反证法)： A¬B0为真

 穷举法： A1B, A2B,…, AkB 均为真

 构造证明法：在A为真的条件下, 构造出具有这种性质的客体B  空证明法：“A恒为假”  “AB为真” 平凡证明法：“B恒为真”  “AB为真”  数学归纳法： 第2章 命题逻辑

2.1 命题逻辑基本概念

1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, , , , )

2、判断命题公式的类型

赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算

1、用真值表判断两个命题公式是否等值

2、用等值演算证明两个命题公式是否等值

3、证明联结词集合是否为联结词完备集 2.3 范式

1、求命题公式的析取范式与合取范式

2、求命题公式的主析取范式与主合取范式（两种主范式的转换）

3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论

1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑

3.1 一阶逻辑基本概念

1、用谓词公式符号命题（正确使用量词）

2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算

1、证明谓词公式的等值式

2、求谓词公式的前束范式 第4章 关系

4.1 关系的定义及其表示

1、计算有序对、笛卡儿积

2、计算给定关系的集合

3、用关系图和关系矩阵表示关系 4.2 关系的运算

1、计算关系的定义域、关系的值域

2、计算关系的逆关系、复合关系和幂关系

3、证明关系运算满足的式子 4.3 关系的性质

1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系

3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系

1、判断关系是否为等价关系

2、计算等价关系的等价类和商集

3、计算集合的划分

4、判断关系是否为偏序关系

5、画出偏序集的哈期图

6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界

7、求偏序集的拓扑排序 第5章 函数

1.判断关系是否为函数 2.求函数的像和完全原像

3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数

6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图

1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度

2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根据握手定理顶点数、边数等

4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图

6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性

1.求图中给定顶点通路、回路的距离

2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示

1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵

5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图

1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树

1.判断一个无向图是否为树

2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用

1.判断一个有向图是否为根树

2.求根树的树根、树叶、内点、树高 3.求最优树

4.判断一个符号串集合是否为前缀码 5.求最佳前缀码

6.用三种方法遍历根树

第三篇：离散数学期末复习试题及答案(二)

第二章 二元关系

1.设A={1,2,3,4},A上二元关系

R={(a,b)|a=b+2}，S={(x,y)|y=x+1 or y=

x2} 求RS,SR,SRS,S2,S

3,SRc。

RS={(3,2),(4,3),(4,1)} SR={(2,1),(3,2)} SRS={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} SRc={(1,4),(2,3),(4,4)}

2．A={a,b,c,d,e,f,g,h}，给定A上关系R的 关系图如下：

图3－14 求最小正整数ｍ，ｎ，ｍ＜ｎ，使Ｒm＝Ｒn。

Ｒ1＝Ｒ16

这是因为R15是8个顶点以及8个自回路，相 当于左图的点各走了5圈，左图的点各走了3圈，R16就成了原来的R．

３．证明：

(1)(InA)IA(a,a)I2nA,aA,(a,a)IA,...,(a,a)IA, (b,b)InA,bA,(b,b)IA.(2)IARRIAR(a,b)R,a,bA,(a,a)IA,(b,b)IA,(a,b)IAR,(a,b)RIA,即RI

AR,RRIA;(a,b)IAR,若(a,b)R,则(a,b)IAR,矛盾,得IARR;同理,RIAR.事实上，当|A|有限时，R与IA复合，相当于矩阵与 单位矩阵相乘，不会变化。

(3)(RIn2nA)IARR...Rn1(RIA)IAR;设(RIk2A)IARR...Rk

(RIk1(I2A)...RkARR)(RIA)(RR2...Rk1)(I2ARR...Rk)IR2...RkRk1AR

４．判断下列等式是否成立（Ｒ,Ｒ1,Ｒ2均是Ａ到Ｂ的 二元关系）

(1)(Rccc1R2)R1R2对,(a,b)(Rc1R2)(b,a)R1R2(b,a)R

1or(b,a)R2(a,b)Rc1or(a,b)Rc2(a,b)Rcc1R2

(2)(Rcc1R2)R1Rc2对(a,b)(Rc1R2)(b,a)R1R2(b,a)R

1and(b,a)R2(a,b)Rcc1and(a,b)R2(a,b)Rcc1R2

(3)(R1R2)R1R2对cccc(a,b)(R1R2)(R1R2)c(b,a)R1R2(b,a)R1,(b,a)R2

(a,b)Rc1,(a,b)Rc2(a,b)Rcccc1R2R1R2(4)(AB)cAB否,例:A{1,2},B{3,4},AB{(1,3),(2,3),(1,4),(2,4)}

(AB)c{(3,1),(3,2),(4,1),(4,2)}(5)c否,c

与的定义域,值域对换了一下.(6)(R)c(Rc)对,(a,b)(R)c(b,a)R(b,a)R(a,b)Rc(a,b)Rc(7)(Rcc1R2)R2Rc1否,R2的定义域不一定与R1的值域相同(8)如果Rcc1R2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2.(9)如果R1Rcc2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2，R1R2,(c,d)R2,(c,d)R1,(d,c)Rc2,而(d,c)Rc1..

(10)R1R2R2R1否,R

2的定义域不一定与R1的值域相同.5.设R1,R2是集合A上的二元关系，如果R2R1，其中r,s,t分别是自反闭包，对称闭包，传递闭包的 记号。试证明:(1)r(R2)r(R1)R2R1,IAIA, R2IAR1IA

(2)s(R2)s(R1)R2Rcc1,R2R1

Rcc2R2R1R1

(3)t(R2)t(R1)R222R1(R2)1(R1)1(即R2R2R1R1)(a,b)R(a,b)(R2R1(R1)1b)R22)1(a,2,cA,(a,c),(c,b)R2R1,(a,b)R21,(a,b)(R1)1(a,b)t(R2),k,使(a,b)(R2)k(R1)kt(R1).6.设R1,R2,R3,R4分别是A到B，B到C，B到C，Ｃ到D的二元关系，证明

(1)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2or(z,y)R3z,(x,z)R1,(z,y)R2or(x,z)R

1,(z,y)R3(x,y)R1R2or(x,y)R1R3(x,y)R1R2R1R3

(2)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2and(z,y)R3z,(x,z)R

1,(z,y)R2and(x,z)R1,(z,y)R3(x,y)R1R2and(x,y)R1R3(x,y)R1R2R1R3(3)(4)类(1)(2)证明。

7.设R是A上的二元关系，证明对任意自然数m,n，(1)RmRnRmn(2)(Rm)nRmn

由归

(1)1)n1,Rm1RmR2)假定RmRnRmn{(a,b)|cA,(a,c)Rm,(c,b)Rn}n1RmR{(a,b)|cA,(a,c)Rm,(c,b)Rn1}其中,Rn1{(c,b)|dA,(c,d)Rn,(d,b)R}RmRn1{(a,b)|c,dA,(a,c)Rm,(c,d)Rn,(d,b)R}{(a,b)|dA,(a,d)Rmn,(d,b)R}RmnRR(mn)1Rm(n1)

(2)1)n1,RmRm2)假定(Rm)nRmn(Rm)n1(Rm)nRmRmnRm

由(1)RmnmRm(n1)8.设R是A上的二元关系，｜A｜＝n，证明存在 自然数s,t，使RsRt,且0st2n2，其中定义

R0{(a,a)|aA}。

0(ai,aj)R证:R(rij)nn,rij1(ai,aj)R至多有2n2个不同的Rk(kN)出现,

0k2n2,由鸽洞原理,(2n21)个Rk中必存在s,t,0st2n2,RsRt.9.R1，R2是Ａ上的二元关系，判别下列命题正确与否

(1)如果R1，R2自反，则R1R2也自反。

对,aA,(a,a)R1,(a,a)R2,(a,a)R

1R2

(2)如果R1，R2反自反，则R1R2也反自反。

否,若(a,b)R1,(b,a)R2,(a,a)R1R2

(3)如果R1，R2对称，则R1R2也对称。

否,例:A{1,2,3},R1{(1,2),(2,1)},R2{(2,3),(3,2)},(1,2)R

1,(2,3)R2,(1,3)R1R2,而(3,1)R1R2

(4)如果R1，R2反对称，则R1R2也反对称。

否,例:A{1,2,3},R1{(1,2),(3,2)},R2{(2,3),(2,1)},(1,2)R,3)R，1,(22,(1,3)R1R2(3,2)R1,(2,1)R2,(3,1)R1R2

(5)如果R1，R2传递，则R1R2也传递。

否,例:A{1,2,3,4},R1{(1,1),(2,3)},R2{(1,2),(3,3)},(1,1)R1,(1,2)R2,(1,2)R1R2，(2,3)R1,(3,3)R2,(2,3)R1R2,但(1,3)R1R2

10.设A={a,b,c}，以下分别给出一个P(A)上的二元 关系，确定它们哪些是自反的，反自反的，对称的，反对称的，传递的。

P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（１）ｘ是ｙ的一个真子集

R1{(x,y)|xy,x,yP(A)}

反自反，不对称，反对称，传递（２）ｘ与ｙ不相交

R2{(x,y)|xy,x,yP(A)}

不自反，也不反自反()，对称，不传递（３）xyA

R3{(x,y)|xyA,x,yP(A)}

不自反，也不反自反{a,b,c}{a,b,c}A，对称，不传递。

11.设R是A上二元关系，证明R是传递的当且仅当

R2R。

任(a,b)∈R2,C,(a,c)(c,b)∈R ,由R传递(a,b)∈R , 即R2  R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2 R , 所以R传递。

12.R是A上反对称的二元关系，问t(R)总是反对称 的吗？

010111否, 例： R001,t(R)111

100111

13．设R是A上的一个自反关系，证明当且仅当(a,b)和(a,c)属于R推出(b,c)属于R时，R是一个等价 关系。

若(a,b)∈R，又自反(a,a)∈R, 推出(b,a)∈R, 所以对称；

若(a,b)(b,c)∈R , 由对称(b,a)(b,c)∈R , 推出(a,c)∈R ,所以传递。若R等价,(a,b)(a,c)∈R , 由对称性(b,a)(a,c)∈R , 由传递性 ,(b,c)∈R。

14.设R是A上的一个对称和传递的关系，证明如果对A中的每个a，在A中存在b，使得(a,b)∈R，则R是一个等价关系。 aA,bA,(a,b)R,由对称性,(b,a)R,又由传递性,(a,a)R.15.设R是A上的一个传递和自反的关系，设T是 A上的一个二元关系，使得当且仅当(a,b)和(b,a)同时 属于R时，(a,b)∈T，证明T是一个等价关系。 a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R

=>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R

=>(a,c)∈R,(c,a)∈R

=>(a,c)∈T

16.设R是A上一个二元关系，设

S={(a,b)｜对某个C，(a,c)∈R且(c,b)∈R｝

证明如果R是等价关系，则Ｓ也是等价关系。

a,(a,a)∈R,(a,a)∈R

=>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R对称,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S

存在d,e

(a,d)(d,b)(b,e)(e,c)∈R

由R传递(a,b)(b,c)∈R 所以(a,c)∈S

17.设R是A上的二元关系，对所有的xi,xj,xk∈A，如果xiRxj∧xjRxkxkRxi，则称R为循环关系，试证明当且仅当R是等价关系时，R才是自反的和循环的。（其中aRb表示(a,b)∈Ｒ）。

R等价, 当然自反，如果xiRxj且xjRxk则由传递性，xiRxk, 由对称性xkRxi，R是自反, 循环的；

若(a,b)∈R, 由R自反 a,(a,a)∈R, 又(a,b)∈R, 由循环(b,a)∈R，对称，若(a,b)(b,c)∈R，由循环(c,a)∈R, 由对称(a,c)∈R，传递。

18．设R1，R2是A上二元关系，证明(1)r(R1R2)r(R1)r(R2)(2)s(R1R2)s(R1)s(R2)(3)t(R1R2)t(R1)t(R2)(1)r(R1R2)(R1R2)IAR1IAR2R1(IAIA)R2(R1IA)(IAR2)(R1IA)(R2IA)r(R1)r(R2)(2)s(Rc1R2)(R1R2)(R1R2)Rcc1R2R1R2

(Rcc1R1)(R2R2)s(R1)s(R2)(3)(R1R2)2{(a,b)|c,(a,c)R1orR2,(c,b)R1orR2}R221R2R1R2R2R1 29 R2221R2(R1R2)用归纳法可证RnRnn12(R1R2)

n,可得t(R1)t(R2)t(R1R2)

19.设A={a,b,c,d},A上二元关系

R={(a,b),(b,a),(b,c),(c,d)}

（１）用矩阵算法和作图法求r(R),s(R),t(R)。（２）用Warshall算法求t(R)。

110001001111 r(R)=1110101011110011 s(R)= 0101 t(R)=0001000100100000

010010011101010i10110i211100001100010001

0000j20000j1,20000i3111111111111110i311111i41111j20001000100010000j20000j1,2,30000

20.讨论正实数集上二元关系Ｒ的几何意义。（１）Ｒ是自反的（２）Ｒ是对称的（３）Ｒ是传递的

（提示：以第一象限的点讨论）

(1)第一象限角平分线

(2)关于对角平分线对称的点对集合

(3)若有P1(x1,y1)、P2(x2,y2), 若x2=y1，必有第三个点P3(x1,y2)

第四篇：离散数学期末复习试题及答案(一)

离散数学习题参考答案

第一章 集合

１．分别用穷举法，描述法写出下列集合（１）偶数集合

（２）36的正因子集合（３）自然数中3的倍数（４）大于１的正奇数

(1)E={，-6，-4，-2，0，2，4，6，}

={2 i | i I }

(2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }

(3)N3= { 3, 6, 9, ```} = { 3n | nN }

(4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }

２．确定下列结论正确与否（１）φφ

×（２）φ｛φ｝√（３）φφ√（４）φ｛φ｝√（５）φ｛ａ｝×（６）φ｛ａ｝√

（７）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√

３．写出下列集合的幂集（１）｛｛ａ｝｝

{φ, {{ a }}}

(2)φ

{φ}（３）｛φ，｛φ｝｝

{φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝

{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ））

{φ, {φ}, {{φ}}, {φ,{φ}} }

４．对任意集合Ａ，Ｂ，Ｃ，确定下列结论的正确与否（１）若ＡＢ，且ＢＣ，则ＡＣ√（２）若ＡＢ，且ＢＣ，则ＡＣ×（３）若ＡＢ，且ＢＣ，则ＡＣ×（４）若ＡＢ，且ＢＣ，则ＡＣ ×

５．对任意集合Ａ，Ｂ，Ｃ，证明

(1)A(BC)(AB)(AC)左差A(BC)差A(BC)D.MA(BC)

分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC)差(AB)(AC)右

2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC)幂等(AA)(BC)

结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)

分配,结合((AB)(BB))(A(B)B))

互补((AB)U)(A)

零一

(AB)(AB)右(5)(AB)CA(BC)左差(AB)C结合A(BC)

D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B

差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC))分配A((CB)(CC))互补A((CB)U)

零一A(CB)交换A(BC)(5)(AB)C左

６．问在什么条件下，集合Ａ，Ｂ，Ｃ满足下列等式

(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC)，CA时等式成立

(2)ABA左右是显然的,AABAB,AB，AB时等式成立

(3)ABBABB,BB,B,代入原式得A，AB时等式成立

(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立

(5)ABAB,若B,bB，当bA,bABA矛盾;当bA,bABA矛盾

(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立

(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A

ABC时等式成立

(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC),AB,AC时等式成立

(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC)时等式成立

(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)

由(6)知,(AB)(AC),ABAC,ABAC时等式成立

(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B

AB时等式成立

７．设Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ

８．在下列条件下，一定有Ｂ＝Ｃ吗？（１）ABAC

否，例：A={1，2，3}，B={4}，C={3,4}, ABAC{1,2,3,4},而BC。

（２）ABAC

否，例：A={1，2，3}，B={2，3}，C={2，3，4} ABAC{2,3},而BC。

（３）ABAC

对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC;若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾（４）ABAC且ABAC

bB,若bA,bABAC,bC,若bA,bABAC,bC，BC,同理,CB,BC

9.(1)(AB)(BC)AB

证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB

(2)若A(BC)且B(AC),则B。

若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾

10．化简

((ABC)(AB))((A(BC))A)(AB)A(AB)A

(AA)(BA)(BA)BA11.设A={2，3，4}，B={1，2}，C={4，5，6}，求（１）AB{1, 3, 4} （２）ABC{1,3,5,6}（３）(AB)(BC){2,3,5,6}

12.设A={1，2，3，4}，B={1，2，5}，求

(1)P(A)P(B){φ,{1},{2},{1,2}}

(2)P(A)P(B)

{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }

(3)P(A)P(B)

{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} }

(4)P(A)P(B)

{{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} }

第五篇：山东大学离散数学期末试题答案

数学建模作业

姓名：

王士彬 学院：

计算机科学与技术

班级：

2014级计科2班 学号：

201400130070

1.在区域x[-2,2],y[-2,3]内绘制函数z=exp^(-x2-y2)曲面图及等值线图。解：

曲面图如下：

>> x=-2:0.5:2;>> y=-2:0.5:3;>> [X,Y]=meshgrid(x,y);

>> Z=exp(-X.^2-``Y.^2);>> mesh(X,Y,Z)>>

等值线图如下：

>> x=-2:0.5:2;>> y=-2:0.5:3;>> [X,Y]=meshgrid(x,y);

>> Z=exp(-X.^2-Y.^2);>> mesh(X,Y,Z)>> surf(X,Y,Z)>> surf(X,Y,Z)>> contour(X,Y,Z)>>

2.已知一组观测数据，如表1所示.(1)试用差值方法绘制出x[-2,4.9]区间内的光滑曲线，并比较各种差值算法的优劣.(2)试用最小二乘多项式拟合的方法拟合表中的数据，选择一个能较好拟合数据点的多项式的阶次，给出相应多项式的系数和偏差平方和.(3)若表中数据满足正态分布函数y(x)221e(x)/2.试用最小二乘非线性拟合2的方法求出分布参数,值，并利用锁求参数值绘制拟合曲线，观察拟合效果.解：(1)分别用最领近插值，分段线性插值（缺省值），分段三次样条插值，保形分段三次插值方法绘制在x[-2,4.9]的光滑曲线，图形如下：

样条插值效果最好，其次线性插值，最近点插值效果最差，在这里效果好像不太明显。最近点插值优点就是速度快，线性插值速度稍微慢一点，但效果好不少。所以线性插值是个不错的折中方法。样条插值，它的目的是试图让插值的曲线显得更平滑，为了这个目的，它们不得不利用到周围若干范围内的点，不过计算显然要比前两种大许多。MATLAB文件如下： >> x0=-2:0.3:4.9;>> y0=[0.10289 0.11741 0.13158 0.14483 0.15656 0.16622 0.17332 0.17750 0.17853...0.17635 0.17109 0.16302 0.15255 0.1402 0.12655 0.11219 0.09768 0.08353...0.07015 0.05876 0.04687 0.03729 0.02914 0.02236];>> cx=-2:0.3:4.9;>> y1=interp1(cx,y0,cx,'nearest');>> y2=interp1(cx,y0,cx,'linear');>> y3=interp1(cx,y0,cx,'spline');>> y4=interp1(cx,y0,cx,'cubic');>> subplot(2,2,1),plot(cx,y0,'o',cx,y1,'-r'),title('Nearest Interpolant');

>> subplot(2,2,2),plot(cx,y0,'o',cx,y1,'-k'),title('Linear

Interpolant');>> subplot(2,2,3),plot(cx,y0,'o',cx,y1,'-b'),title('Spline Interpolant');>> subplot(2,2,4),plot(cx,y0,'o',cx,y1,'-k'),title('Cubic Interpolant');>> subplot(2,2,1),plot(cx,y0,'o',cx,y1,'-r'),title('Nearest Interpolant');(2),从图形可以看出曲线函数遵从幂函数的形式，设幂函数形式为：yx可化为lnylnlnx.即把非线性函数转化为线性函数，原线性函数形式为p(x)a1xa0

由此我们可以得出p(x)等价于lny;x等价于lnx;a1，lna0 我们可以先求出a1,a0。

求一个线性多项式p(x)a1xa0使之在最小二乘准则下拟合这些观测值，问题即化为

m求a0,a1使E(a0,a1)=min[yi(a1xia0)]利用多元函数极值原理可知，若目标函数a0,a1i12E(a0,a1)的极小值存在，一定有结果。>> log(x0);>> log(y0);>> x0=log(x0);>> y0=log(y0);>> n=length(x0);>> a=sum(x0);>> b=sum(y0);>> c=sum(x0.*y0);>> d=sum(x0.^2);>> a0=(d*b-c*a)*(n*d-a^2);>> a1=(n*c-a*b)/(n*d-a^2);>> a0,a1 a0 =-2.5891e+050.3558i 即系数a0为

-2.5891e+050.3558i 其相应多项式的系数和偏差平方和.我们可以求出E=-7.2019e+13 + 2.1767e+13i 其MATLAB文件如下： >> Y=a1*x0+a0;>> e=Y-y0;>> E=sum(e.^2)E =

-7.2019e+13 + 2.1767e+13i

即其相应多项式的系数和偏差平方和.为

-7.2019e+13 + 2.1767e+13i(3)？

3.将某物体放置在空气中，在t=0时刻测得其温度u0=150度，10min后测得温度u1=87度，假设空气的温度为24度。试建立数学模型给出物体的温度u与时间t的关系，并计算20min后物体的温度。

解：为了解决上述问题，我们首先需要了解有关热力学的一些基本规律：比如：热量总是从温度高的物体向温度低的物体传导的；在一定的温度范围（其中包括了上述问题的温度在内），一个物体的温度与这物体的温度和其所在介质的温度的差值成正比例。这是已为实验证明了的牛顿冷却定律。

设空气的温度为ua ,物体在时刻t的温度为uu(t)，则温度的变化速度du。注意热量总是从温度高的物体向温度低的物体传导的，因而初始温dt度大于空气温度，即（u0>ua），所以温差u-ua恒正；又因为物体的温度将随

du时间而逐渐冷却，故温度变化速度恒负。因此，由牛顿冷却定律得到

dtduK(uua)............(1)dt这里的K>0是比例常数。此（1）方程就是冷却过程的数学模型。

为了确定温度u与时间t的关系，我们需要从上面（1）的方程中解出u。又因为ua是常数，并且u-ua>0,所以我们可以将上述式子改写成

d(uua)Kdt

将此式积分可得到如下式子

uua为ln(uua)Ktc1

uuae^(Ktc1)ce^(Kt)即u=ua+ce^(-Kt)根据初始条件：t=0时，u=u0代入上式得 c=u0-ua 于是u=u0+(u0-ua)e^(-Kt)

又根据条件，当t=10时，u=u1代入上式得

u1=ua+(u0-ua)e^(-10K)

1Kln[(u0-ua)/(u1-ua)] 10根据题意我们可知u0=150，u1=87,ua=24,代入得到

1150241K=ln=ln2=0.069 10872410从而u=24+126e^(-0.069t)这就是物体冷却时温度u随着时间t的变化规律。用t=20代入得u=55.7度

4.假设在某商场中，某种商品在t时刻的价格为P(t)，若假定其变化率与商品的需求量D和供给量S之差成正比(比例系数为k),若

DabP,ScdP

其中a,b,c,d均为正常数，若已知初始价格为Po,求任意时刻t时该商品的价格。

解：一般情况下，某种商品的价格主要服从市场供求关系，由题意我们可知商品需求量D是价格P的单调递减函数，商品供给量S是价格P的单调递增函数，即

DabP,ScdP----(1)其中a,b,c,d均为常数，且b>0,d>0.当需求量与供给量相等时，由(1)可得供求平衡时的价格Pe=

ac，并称Pe

bd为均衡价格。

由题意得：

dpk[D(p)S(p)] dt其中比例系数k>0，用来反应价格的调整进度。将(1)式代入方程可得

其中常数=k(b+d)>0，所以此方程的通解为 P(t)=Pe+Ce^(-t)

由于初始价格P(0)=P0代入上式，得C=P0-Pe于是我们可以求出任意时刻价格P与时刻t之间的函数为：

P(t)=Pe+(P0-Pe)^(-t)，并且我们可以得出，因为>0知，t时P(t)Pe，说明随着时间的不断推延，实际价格P(t)将逐渐趋近均衡价格Pe。

5.农场种植计划问题

某农场根据土地的肥沃程度，把耕地分为I II III三等，相应的耕地面积分别为100、300和200km2,计划种植水稻、大豆和玉米.要求三种作物的最低收获量分别为190、130和350吨(t).I、II、III等耕地种植三种作物的单产如表所示.若三种作物的售价分别为水稻1.2元/kg,大豆1.50元/kg，玉米0.80元/kg.那么

(1)如何制订种植计划，才能使总产量最大？(2)如何制订种植计划，才能使总产值最大？

解：

(1):问题分析：

确定种植最佳土地分配，即每种等级耕地分别种植水稻、大豆、玉米的面积

模型建立：

1，决策变量：令x1,x2,x3分别为I II III三等耕地上种植的水稻面积，令x4,x5,x6分别为I II III三等耕地上种植的大豆面积，令x7,x8,x9分别为I II III三等耕地上种植的玉米面积。且令为xi（1<=i<=9）面积的耕地上的产量为ci.2,目标函数：总产量最大，即max=i1cixi

3,约束条件：

最低产量限制：最低水稻产量190吨，最低大豆产量130吨，最低玉米产量350吨

11x1+9.5x2+9x3≧190

8x4+6.8x5+6x6≧130

14x7+12x8+10x9≧350

耕地面积恒定：x1 +x4+x7=100

x2+x5+x8=300

x3+x6+x9=200

非负条件：x1，x2，x3，x4，x5，x6，x7，x8，x9≧0

数学模型：

max=11x1+9.5x2+9x3+8x4+6.8x5+6x6+14x7+12x8+10x9-11x1-9.5x2-9x3190-8x4-6.8x5-6x6130-14x7-12x8-10x9350x1 +x4+x7=100 x2+x5+x8=300x3+x6+x9=200，x2，x3，x4，x5，x6，x7，x8，x90x1 用MATLAB求解，用命令格式III，文件如下：

>>c=[11 9.5 9 8 6.8 6 14 12 10];>> A=[-11-9.5-9 0 0 0 0 0 0 0 0 0-8-6.8-6 0 0 0 0 0 0 0 0 0-14-12-10];>> b=[-190;-130;-350];>> Aeq=[1 0 0 1 0 0 1 0 0

0 1 0 0 1 0 0 1 0

0 0 1 0 0 1 0 0 1];>> beq=[100;300;200];>> vlb=[0;0;0;0;0;0;0;0;0];>> vub=[];>> [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)Optimization terminated.x =

17.2727

0.0000

0.0000

82.7273

300.0000

165.0000

0.0000

0.0000

35.0000 fval =

4.2318e+03

即，模型的最优解为(17.2727 0.0 0.0 82.7273 300.0 165.0

0.0 0.0 35.0)T,目标函数最优值为4.231103

即：x1，x2，x3，x4，x5，x6，x7，x8，x9值分别为17.2727 0.0 0.0 82.7273 300.0 165.0

0.0 0.0 35.0，此时才能使总产量最大。(2)问题分析：

根据题(1),当要求得产值最大时,目标函数只需变成Max

=1.2(11x1+9.5x2+9x3)+1.5(8x4+6.8x5+6x6)+0.8(14x7+12x8+10x9)

=13.2x1+11.4x2+10.8x3+12x4+10.2x5+9x6+11.2x7+9.6x8+8x9 MATLAB求解，部分文件如下：

>> c=[13.2 11.4 10.8 12 10.2 9 11.2 9.6 8];>> [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)Optimization terminated.x =

17.2727

0.0000

0.0000

0.0000

19.1176

0.0000

82.7273

280.8824

200.0000 fval =

5.6460e+03

即，模型的最优解(17.2727 0.0 0.0 0.0 19.1176 0.0 82.7273 280.8824 200.0)T目标函数最优值5.646103

即：x1，x2，x3，x4，x5，x6，x7，x8，x9值分别为17.2727 0.0 0.0 0.0 19.1176 0.0 82.7273 280.8824 200.0，此时才能使总产值最大。