离散数学期末试题

2024-08-19

离散数学期末试题（精选8篇）

离散数学期末试题第1篇

离散数学考试试题（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为有向图，可略去边的方向讨论对应的无向图）。

（2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝是不连通的例子。解下图满足条件但不连通。

12344

333334

34333

4333

133

113

122244 6

离散数学期末试题第2篇

第一章集合

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

（２）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篇

关键词：图,出度,入度,关联矩阵,邻接矩阵

离散数学是研究离散量的结构及其相互关系的数学学科, 是现代数学的一个重要分支。它在各学科领域, 特别在计算机科学技术领域有着广泛的应用, 同时离散数学也是计算机专业的许多专业课程, 如程序设计、数据结构操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习, 不但可以掌握处理离散结构的描述工具和方法, 为后续课程的学习创造条件, 而且可以提高抽象思维和严格的逻辑推理能力, 为将来参与创新性的研究和开发工作打下坚实的基础。

高等教育出版社出版的离散数学教材, 是面向21世纪课程教材, 是普通高等教育“十一五”国家级规划教材。该教材相比其修订版及其他教材具有明显优点:语言组织简练易懂, 内容中心突出, 知识体系清晰, 知识点分布更加合理等。

下面是笔者在教学过程中发现的一个小问题, 在这里提出来和大家一起探讨。本书第五部分图论中第275页有如下定义:

定义14.4:设G=为无向图, ∀ν∈V, 称ν作为边的端点的次数之和为ν的度数, 简称为度, 记作dG (ν) 。在不发生混淆时, 略去下标G, 简记为d (ν) 。设D=为有向图, ∀ν∈V, 称ν作为边的始点的次数之和为ν的出度, 记作dD- (ν) , 简记为d- (ν) 。称ν作为边的终点的次数之和为ν的人度, 记作dD+ (ν) , 简记为dD+ (ν) 。称d- (ν) +d+ (ν) 为ν的度数, 记作dD (ν) , 简记作d (ν) 。

而在第288-289页图的矩阵表示中有如下定义:

定义14.24:设有向图D=中无环, V={ν1, ν2, …, νn}, E={e1, e2, …, en}, 令:

则称 (mij) n×m为D的关联矩阵, 记作M (D) 。

作为例题, 书中给出了图:

的关联矩阵:

并得到矩阵M (D) 具有如下的性质:

1) 每一列恰好有一个+1和一个-1。

2) -1的个数等于+1个数, 都等于边数m, 这正是有向图握手定理的内容。

3) 第i行中, +1的个数等于d+ (νi) , -1的个数等于dD- (νi) 。

4) 平行边所对应的列相同。

由定义14.4和定义14.24, 我们发现结论和定义出现了矛盾。如结论3为:+1的个数等于d+ (νi) , -1的个数等于dD- (νi) 。按照定义14.24中1和-1的定义, 该结论可解释为:νi作为边ei的始点的次数之和等于d+ (νi) , νi作为边ei的终点的次数之和等于d- (νi) 。而这与定义14.4中, 称ν作为边的始点的次数之和为的出度, 简记为d- (ν) 。称ν作为边的终点的次数之和为ν的人度, 简记为d+ (ν) 相矛盾。另外, 我们再看如下定义:

定义14.25:有向图D=, V={ν1, ν2, …, νn}, 令aij[1]为顶点νi邻接到顶点νj边的条数, 记作A (D) , 或简记为A。

作为例题, 书中给出了图:

邻接矩阵:

并且得到矩阵A具有如下的性质:

于是, , 即A (D) 中所有元素之和等于边数, 这也正是有向图握手定理的内容。

事实上, 因为a[1]ij为顶点νi邻接到顶点νj边的条数, 则有表示顶点νi作为边的始点的个数, 即顶点νi的出度, 由定义14.4, 即为d- (ν) , 因此 (1) 矛盾。类似的, 定义14.4也与 (2) 矛盾。

修改的方法很多, 比如:我们可以修改定义14.4, 但这不是很明智的。该文的修改主要是针对定义14.24中mij的取法以及上述两个例题及相关结论的修改。

定义14.24:设有向图D=中无环, V={ν1, ν2, …, νn}, E={e1, e2, …, en}, 令:

则称 (mij) n×m为D的关联矩阵, 记作M (D) 。

则图的关联矩阵改为:

此时其性质3仍然可以保持不变。

对于定义14.25:我们只需将性质 (1) 和 (2) 作如下修改:

这样一来, 我们的定义14.4、14, 24、14.25和相应的例题及结论则能保持一直, 既增加了本书的可读性, 同时, 读者在理解时也能轻松许多。

参考文献

[1]屈婉玲, 耿素云, 张立昂.离散数学[M].北京:高等教育出版社, 2008.

[2]左孝凌, 李为鑑, 刘永才.离散数学[M].上海:上海科学技术文献出版社, 1982.

七年级数学期末测试题(A) 第4篇

1．下列各图形中，具有稳定性的是（）.

2．已知三角形的三边长分别是3、8、x，则x的取值范围是（）.

A. x>5B. x<11

C. 5

3．有一幅美丽的平面镶嵌图案，在某个重合的顶点周围有四个边长相等的正多边形，其中三个分别为正三角形、正方形、正六边形，则另一个为（）.

A．正三角形 B．正方形

C．正五边形D．正六边形

4．如图1，直线a∥b，则∠A的大小是（）.

A. 28°B. 31°

C. 39° D. 42°

5．在某个频数分布直方图中有11个小长方形，各组组距都相同，若中间的小长方形的面积等于其他10个小长方形面积之和的，且样本容量为160，则中间一组的频数为（）.

A． 0.2B． 32

C． 0.25 D． 40

6．在平面直角坐标系中，点P（-3，4）到x轴的距离为（）.

A. 3B.-3

C. 4 D.-4

7．如果一个多边形的每个内角都相等，且内角和为1 800°，那么这个多边形的一个外角等于（）.

A． 30°B． 36°

C． 60° D． 72°

8．二元一次方程2x+3y=8的正整数解有（）.

A． 1组B． 2组

C． 3组 D．无穷多组

二、填空题（每小题4分，共28分）

9. 为了改进银行的服务质量，随机抽查了30名顾客在窗口办理业务所用的时间（单位：min）．图2是这次调查得到的统计图．请你根据图中的信息判断：办理业务所用时间为11min的顾客有人.

10．根据图3所给信息，可求出每只小猫和小狗的价格分别为.

11．若等腰三角形的两边长分别为6 cm和2 cm，则它的周长为cm.

12．将一副三角板（分别含30°角和45°角）按图4所示的方法摆放，则∠1的大小是．

13．如图5，已知AB∥CD，直线MN分别交AB、CD于点E、F，∠MFD=50°，EG平分∠MEB，那么∠MEG的大小是.

14．不等式组2x-7<5-2x，

x+1>

的整数解是.

15．在平面直角坐标系中，已知点P（3-m，2m-4）在第一象限，则m的取值范围是.

三、解答题（共68分）

16．（6分）某社区要调查社区内居民双休日学习的情况，采用下列调查方式：①从一幢高层住宅楼中选取200名居民；②从不同住宅楼中随机选取200名居民；③选取社区内200名在校学生．

（1）上述调查方式最合理的是；

（2）采用最合理的调查方式得到数据并制成扇形统计图（如图6）．在这次调查中，200名居民中双休日在家学习的有多少人？

17．（6分）解方程组3x+7y=9，

4x-7y=5.

18．（8分）解不等式组3-x>0，

，并把解集在图7所示的数轴上表示出来．

19．（8分）如图8，在平面直角坐标系中，四边形ABCD各个顶点的坐标分别是A（0，0），B（3，6），C（10，8），D（13，0），请计算这个四边形的面积.

20．（8分）如图9，已知∠1 =∠2，∠B =∠C，试说明AB∥CD.

21．（10分）对于有理数x、y，规定新运算x※y=ax+by+xy，其中a、b是常数.已知2※1=7，（-3）※3=3，求a、b的值.

22.（10分）阅读与思考（用求差法比较大小）.

制作某产品有两种用料方案，方案1用4张A型钢板，8张B型钢板；方案2用3张A型钢板，9张B型钢板.A型钢板的面积比B型钢板的大.从省料角度考虑，应选哪种方案？

设A型钢板和B型钢板的面积分别为x和y.于是，两种方案用料面积分别为4x+8y和3x+9y.现在需要比较这两个数量的大小.

这两个数量的大小可以通过它们的差来比较.

如果两个数a和b比较大小，那么当a>b时，一定有a-b>0；当a=b时，一定有a-b=0；当a

反过来也成立，即当a-b>0时，一定有a>b；当a-b=0时，一定有a=b；当a-b<0时，一定有a

因此，我们经常把两个要比较的对象先数量化，再求它们的差，根据差的正负判断对象的大小.

用求差的方法，你能解答前面的用料问题吗？

23．（12分）已知某工厂现有M种布料70 m，N种布料52 m.现计划用这两种布料生产A、B两种型号的时装共80套，做一套A型号的时装与做一套B型号的时装所需的布料如表1所示.利用现有原料，工厂能否完成任务？若能，有几种生产方案？请你设计出来.

表1

【责任编辑：穆林彬】

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

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(前提引入)

离散数学期末试卷第6篇

《离散数学》（A）

学号姓名：成绩

一、单项选择题（每题2分，共18分）

1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D）．

A．P→Q

C．P∧Q B．P∨Q D．P∧Q

p→q，蕴涵式，表示假设、条件、“如果，就”。

“→”与此题无关

2.关于命题变元P和Q的极大项M1表示(C)。书P15-P20，此题换作p、q更容易理解

A.┐P∧QB.┐P∨Qp∨┐q----01----1-----M

1C.P∨┐QD.P∧┐Q

3.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D）

4.在论域D={a,b}中与公式（x）A（x）等价的不含存在量词的公式是（B）

A.A(a)A(b)

C.A(a)A(b)

5．下列命题公式为重言式的是（C）

A．Q→（P∧Q）

C．（P∧Q）→PB．P→（P∧Q）D．（P∨Q）→QB.A(a)A(b)D.A(b)A(a)

牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况

6.设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是(A)

A.R=｛<1,a>,<2,a>,<3,a>｝

B.R=｛<1,a>,<2,b>｝

C.R=｛<1,a>,<1,b>,<2,a>,<3,a>｝

D.R=｛<1,b>,<2,a>,<3,b>,<1,a>｝

-第 1页

7.偏序关系具有性质（D）背

A.自反、对称、传递

B.自反、反对称

C.反自反、对称、传递

D.自反、反对称、传递

8.设R为实数集合，映射:RR,(x)x22x1,则 是(D).(A)单射而非满射(C)双射(B)满射而非单射(D)既不是单射也不是满射.书P96.设函数f：A→B

（1）若ranf=B，则f是满射的【即值域为B的全集，在本题中为R，该二次函数有最高点，不满足】

（2）若对于任何的x1,x2∈A , x1≠x2,都有f(x1)≠f(x2)，则称f是单射的【即x,y真正一一对应，甚至不存在一个y对应多个x。显然，本题为二次函数，不满足】

（3）若f既是满射的，又是单射的，则称f是双射的【本题中两个都不满足，既不是单射也不是满射】

二、填空题（每空2分，共22分）

１.设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，,∈S,*=, 则*运算的幺元是_____<1,0>_____。∈S, 若a≠0，则的逆元是______<1/a,-b>______。书P123定义

２.在个体域D中，公式xG(x)的真值为假当且仅当__某个G(x)的真值为假__，公式xG(x)的真值为假，当且仅当__所有G(x)的真值都为假__。

３.给定个体域为整数域，若F（x）：表示x是偶数，G（x）：表示x是奇数；那么，(x)F(x)(x)G(x)是一个(x)(F(x)G(x))是一个

４.设Aa,b,c　,A上的二元关系Ra,b,b,c,则r(R)

{,,,,,} 。

书P89、P85.自反闭包：r(R)= R U R0

={,} U {,,,} ={,,,,,}对称闭包：s(R)= R U R-1 = {,} U {,} = {,,,}-第 2页

传递闭包：t(R)= RUR2 UR3U……

５.设X={1,2,3},Y={a,b}，则从X到Y的不同的函数共有___8___个.书P96，B上A的概念：

设Ａ、Ｂ为集合，所有从Ａ到Ｂ的函数构成集合ＢA，读作“B上A”

如果|A| = m，|B| = n，m、n不全是0，则|BA| = nm

即，若题中给出集合A有m个元素，B有n个元素，可直接用nm 计算出A到B的函数个数。本题中为23 = 8

６.设，a,bG，则（a-1）-1，（ab）-1b-1 * a-1。

书P139公式

7.设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，则fg=__{<1,3>,<2,1>,<3,1>}___，gf=__{<1,3>,<2,3>,<3,2>}__。书P82-8

3合成：FG = {|xGz∧zFy}

需要说明的是，这里的合成FG是左复合，即G先作用，然后将F复合到G上。之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样的定义就可以了。总之，在咱们的离散里牢记左复合。

三、计算题（每题9分，共36分）

1.设集合A＝{1, 2, 3,4,5}，A上的关系R＝{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3,3>,<3,5>,<4,4>,<5,5>}

(1)画出R的关系图；

(2)问R具有关系的哪几种性质(自反、对称、传递、反对称).自反性、传递性

书P87表格，根据关系图可直接判断性质……

(3)给出R的传递闭包。

R={<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>,<3,5>,<4,4>,<5,5>}

-第 3页

R2 = RR = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}R3 = R2R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}……

所以，t(R)= {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

2.集合S={a,b,c,d,e}上的二元运算*的运算表如下，求出它的幺元，零元，及逆

元。*abcde

abaccc

babcde

cccccc

dedcba

edecdb

幺元：b

零元：c

逆元：a-1 =a,b-1 =b, d-1 =d,e-1 =e

书P123定义

3．求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式及成真赋值。

A = P→((┐P∨Q)∧(Q∧P))

= P→((┐P∨Q)∧(Q∧P))

= P→((┐P ∧Q∧P)∨(Q∧Q∧P))

= P→(Q∧P)

= ┐P∨(Q∧P)

=(┐P∧(Q∨┐Q))∨(Q∧P)

=(cP∧Q)∨(┐P∧┐Q)∨(P∧Q)

=(┐P∧┐Q)∨(┐P∧Q)∨(P∧Q)

= m0∨m1∨m

3成真赋值为00，01，1

14．求在1到1000000之间有多少个整数既不是完全立方数，也不是完全平方数？-第 4页

完全平方数的个数：1000=1000000，所以有1000个（即1到1000）

完全立方数的个数：1003 =1000000，所以有100个（即1到100）

既是完全平方数又是完全立方数的重复部分：106 =1000000，所以有10个（即16到106）所以既不是完全立方数，也不是完全平方数的整数有：1000000-(1000+100-10)= 998910

2四、证明题（每题8分，共24分）

1．若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止？（给出相应推理的证明过程）

2．给出关系不满足对称性的条件并证明。

∃∈R∧∉R

⇔∃∈R∧∉R

⇔┐∀(∈R∧∈R)

3．如果关系R和S为X上的等价关系，证明：R∩S也是X上的等价关系。

(1)自反

设x∈X【推∈R∩S】

∵R和S为X上的等价关系

∴R和S均为X上的自反关系

∵x∈X

∴∈R, ∈S

∴∈R∩S

∴R∩S在X上是自反的(2)对称

设∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵R和S为X上的等价关系

∴R和S均为X上的对称关系

∴∈R,∈S

∴∈R∩S

-第 5页

∵此时∈R∩S

∴R∩S在X上是对称的【∈R∩S时，必有∈R∩S】

(3)传递

设∈R∩S，∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵∈R∩S

∴∈R,∈S

∵R和S为X上的等价关系

∴R和S均为X上的传递关系

∴∈R,∈S

∴∈R∩S

∵此时∈R∩S，∈R∩S

∴R∩S在X上是传递的【∈R∩S，∈R∩S时，必有∈R∩S】

综上所述，R∩S在X上是自反、对称、传递的∴R∩S为X上的等价关系

书P90

等价关系：自反、对称、传递

偏序关系：自反、反对称、传递

因此要证明某关系在非空集合上是等价关系或偏序关系，一般需分为三个性质分别证明，同时，题目条件中若给出等价关系或偏序关系，也可分为三部分选择使用。这类题条件较多（自己设的、题目推的），一定要思路清晰，否则容易写乱自己绕不出来„„

这道题三部分每个部分所设的条件都是该性质定义里的“若”，想要推出定义里的“则”，即用定义证明。这就是思路很重要的一部分。

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

一、证明题（10分）

1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R)((P∧Q)∧R))∨((Q∨P)∧R)((P∨Q)∧R)∨((Q∨P)∧R)((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2)x(A(x)B(x)) xA(x)xB(x)证明：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)

二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式（10分）。

证明：(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R))（P∧(Q∨R)）∨(P∧Q∧R)(P∧Q)∨(P∧R))∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R)m0∨m1∨m2∨m7 M3∨M4∨M5∨M6

三、推理证明题（10分）

1）C∨D，(C∨D) E，E(A∧B)，(A∧B)(R∨S)R∨S 证明：(1)(C∨D)E(2)E(A∧B)

P P

P(3)(C∨D)(A∧B)T(1)(2)，I(4)(A∧B)(R∨S)(5)(C∨D)(R∨S)(6)C∨D

T(3)(4)，I P(7)R∨S T(5)，I 2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x)P

(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)，I

四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。

解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。

先求|A∩B|。

∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。

于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。

五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)（10分）。

证明：∵x A-（B∪C） x A∧x（B∪C）

 x A∧（xB∧xC）

（x A∧xB）∧（x A∧xC） x（A-B）∧x（A-C） x（A-B）∩（A-C）

∴A-（B∪C）=（A-B）∩（A-C）

六、已知R、S是N上的关系，其定义如下：R={| x，yN∧y=x}，S={| x，yN∧y=x+1}。求R、R*S、S*R、R{1，2}、S[{1，2}]（10分）。

解：R={| x，yN∧y=x} R*S={| x，yN∧y=x+1} S*R={| x，yN∧y=（x+1）}，R{1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。

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

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

12-1

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

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

证明：1）x∈I，因为（x-x）/m=0，所以xx(mod m)，即xRx。

2）x，y∈I，若xRy，则xy(mod m)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以yx(mod m)，即yRx。

3）x，y，z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。

九、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。

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

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

1-1

-1-1-1-1

-1-1-1

-1离散数学试题(B卷答案2）

一、证明题（10分）

1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T 证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律)((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律)((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(等幂律)T(代入)2)xy(P(x)Q(y)) (xP(x)yQ(y))证明：xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))

二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分）

解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1 m0∨m2∨m3

三、推理证明题（10分）

1)(P(QS))∧(R∨P)∧QRS 证明：(1)R(2)R∨P(3)P(4)P(QS)(5)QS(6)Q(7)S(8)RS 2)x(A(x)yB(y))，x(B(x)yC(y))xA(x)yC(y)。

证明：(1)x(A(x)yB(y))P(2)A(a)yB(y)T(1)，ES(3)x(B(x)yC(y))P(4)x(B(x)C(c))T(3)，ES(5)B(b)C(c)T(4)，US(6)A(a)B(b)T(2)，US(7)A(a)C(c)T(5)(6)，I(8)xA(x)C(c)T(7)，UG(9)xA(x)yC(y)T(8)，EG

四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。

解设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：PxA(x)，xA(x)QQP。

(1)PxA(x)P(2)PxA(x)T(1)，E(3)xA(x)P T(2)，E(4)xA(x)Q P(5)(xA(x)Q)∧(QxA(x))T(4)，E(6)QxA(x)T(5)，I(7)QP T(6)(3)，I

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

证明：∵x A∩（B∪C） x A∧x（B∪C） x A∧（xB∨xC）（x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C x（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）

六、A={ x1,x2,x3 }，B={ y1,y2}，R={,,}，求其关系矩阵及关系图（10分）。

七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。

解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>, <3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}

八、设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠。关系R满足：<，>∈R∈R1且∈R2，证明R是A×B上的等价关系（10分）。

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

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

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

对任意的、、∈A×B，若R且R，则∈R1且∈R2，∈R1且∈R2。由∈R1、∈R1及R1的传递性得∈R1，由∈R2、∈R2及R2的传递性得∈R1。再由R的定义，有<，>∈R，即R，所以R是传递的。

综上可得，R是A×B上的等价关系。

九、设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h（10分）。

由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。－

1－1

－1－1－1

－1离散数学试题(B卷答案3）

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

二、（10分）求命题公式（P∨(Q∧R))(P∨Q∨R)的主析取范式，并求成真赋值。

解：（P∨(Q∧R))(P∨Q∨R)(P∨(Q∧R))∨P∨Q∨R P∧(Q∨R)∨P∨Q∨R (P∧Q)∨(P∧R)∨(P∨Q)∨R ((P∨Q)∨(P∨Q))∨(P∧R)∨R 1∨((P∧R)∨R)1 m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 该式为重言式，全部赋值都是成真赋值。

三、（10分）证明((P∧Q∧A)C)∧(A(P∨Q∨C))(A∧(PQ))C 证明：((P∧Q∧A)C)∧(A(P∨Q∨C))((P∧Q∧A)∨C)∧(A∨(P∨Q∨C))((P∨Q∨A)∨C)∧((A∨P∨Q)∨C)

((P∨Q∨A)∧(A∨P∨Q))∨C ((P∨Q∨A)∧(A∨P∨Q))C ((P∨Q∨A)∨(A∨P∨Q))C ((P∧Q∧A)∨(A∧P∧Q))C (A∧((P∧Q)∨(P∧Q)))C (A∧((P∨Q)∧(P∨Q)))C (A∧((QP)∧(PQ)))C (A∧(PQ))C

四、（10分）个体域为{1，2}，求xy（x+y=4）的真值。

解：xy（x+y=4）x（（x+1=4）∨（x+2=4））

（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））（0∨0）∧（0∨1）0∧10

五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B)解：xP(A)∩P(B)，xP(A)且xP(B)，有xA且xB，从而xA∩B，xP(A∩B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B)

六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}

七、（10分）设函数f：R×RR×R，R为实数集，f定义为：f()=。1)证明f是双射。

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

2）

∈R×R，由f()=

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

的原象存在，f是满射。

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

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

2）a，b，c∈G，（ab）c=（a*u*b）*u*c=a*u*（b*u*c）=a（bc），运算是可结合的。

3）a∈G，设E为的单位元，则aE=a*u*E=a，得E=u，存在单位元u。4）a∈G，ax=a*u*x=E，x=u*a*u，则xa=u*a*u*u*a=u=E，每个元素都有逆元。

所以也是个群。

九、（10分）已知：D=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的邻接距阵A和可达距阵P。

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

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

1-1

P= 1 1 1 1

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

解：最优二叉树为

权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148

离散数学试题(B卷答案4）

一、证明题（10分）

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

证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律)((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律)((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(等幂律)T(代入)2)x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))证明：x(P(x)Q(x))∧xP(x)x((P(x)Q(x)∧P(x))x((P(x)∨Q(x)∧P(x))x(P(x)∧Q(x))xP(x)∧xQ(x)x(P(x)∧Q(x))

二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分）

解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m3

三、推理证明题（10分）

1)(P(QS))∧(R∨P)∧QRS 证明：（1）R 附加前提(2)R∨P P(3)P T(1)(2),I(4)P(QS)P(5)QS T(3)(4),I(6)Q P(7)S T(5)(6),I(8)RS CP 2)x(P(x)∨Q(x))，xP(x)x Q(x)证明：(1)xP(x)P(2)P(c)T(1),US(3)x(P(x)∨Q(x))P(4)P(c)∨Q(c)T(3),US(5)Q(c)T(2)(4),I(6)x Q(x)T(5),EG

四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。

证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。

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

六、={A1，A2，„，An}是集合A的一个划分，定义R={|a、b∈Ai，I=1，2，„，n}，则R是A上的等价关系（15分）。

证明：a∈A必有i使得a∈Ai，由定义知aRa，故R自反。a,b∈A，若aRb，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。

a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=，故i=j，即a,b,c∈Ai，所以aRc，故R传递。

总之R是A上的等价关系。

七、若f:A→B是双射，则f:B→A是双射（15分）。

证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使∈f，∈f。所以,f是满射。

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

因此f是双射。

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

证明假设A≠G且B≠G，则存在aA，aB，且存在bB，bA（否则对任意的aA，aB，从而AB，即A∪B＝B，得B＝G，矛盾。）

对于元素a*bG，若a*bA，因A是子群，aA，从而a *(a*b)＝b A，所以矛盾，故a*bA。同理可证a*bB，综合有a*bA∪B＝G。综上所述，假设不成立，得证A＝G或B＝G。

九、若无向图G是不连通的，证明G的补图G是连通的（10分）。

证明设无向图G是不连通的，其k个连通分支为G1、G2、„、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]

1-1-1

-1-1-1-1是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。

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

一、（10分）求命题公式(P∧Q)(PR)的主合取范式。

解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R）

(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5

二、（8分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为x（F（x）G（x）），F（a）G（a）证明：

（1）x(F(x)G(x))P（2）F(a)G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I

三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)证明：∵x A∩（B∪C） x A∧x（B∪C）

 x A∧（xB∨xC）

（x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C  x（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S∈R∩S

∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)设A＝{a，b，c，d}，R是A上的二元关系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，} s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝R＝{，，，，，，，

4232-1d>，}

六、(15分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()＝。证明h是双射。

证明：1）先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。

2）再证h是单射。

、∈A×C，若h()＝h()，则＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C

到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。

综合1）和2），h是双射。

七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则有a*bH。

证明： a,b∈H有b∈H，所以a*b∈H。a∈H，则e=a*a∈H a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵HG且H≠,∴*在H上满足结合律 ∴是的子群。

八、（10分）设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为：(写过程，7分)-

1-1

-1-1-1-1-1

-1-1（1）G是否为阿贝尔群？

（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿贝尔群

（2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a（3）因为a*a=a 所以G的幂等元是a（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b

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

解：最优二叉树为

权＝148 离散数学试题（B卷答案6）

一、（20分）用公式法判断下列公式的类型：(1)(P∨Q)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)

(P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3 M0

所以，公式(P∨Q)(PQ)为可满足式。

（2）因为(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R))

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

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

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

m2∨m3∨m4∨m5∨m6∨m7

所以，公式(PQ)(P∧(Q∨R))为可满足式。

二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋

又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。

解：论域：所有人的集合。Q(x)：x是勤奋的；H(x)：x是身体健康的；S(x)：x是科学家；C(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为：

x(S(x)H(x))Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧x(C(x)∨F(x))下面给出证明：

(1)x(S(x)∧H(x))

P(2)S(a)∧H(a)

T(1)，ES(3)x(S(x)Q(x))

P(4)S(a)Q(a)

T(1)，US(5)S(a)

T(2)，I(6)Q(a)

T(4)(5)，I(7)H(a)

T(2)，I(8)Q(a)∧H(a)

T(6)(7)，I(9)x(Q(x)∧H(x)C(x))

P(10)Q(a)∧H(a)C(a)

T(9)，Us(11)C(a)

T(8)(10)，I(12)xC(x)

T(11)，EG(13)x(C(x)∨F(x))

T(12)，I

三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解

P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}}

四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。

(4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则R∩S是自反的。(6)若R和S是传递的，则R∪S是传递的。

解

(1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。

(2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。

(3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。

(4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。

(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。

五、（15分）令X＝{x1，x2，„，xm}，Y＝{y1，y2，„，yn}。问(1)有多少个不同的由X到Y的函数？

(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？

解

(1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。

(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到

mY的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。

(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。

六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？

解

X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。

七、（10分）若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x＝

b。

证明设e是群的幺元。令x＝a1*b，则a*x＝a*(a1*b)＝(a*a1)*b＝e*b＝b。

－

－所以，x＝a1*b是a*x＝b的解。－若x∈G也是a*x＝b的解，则x＝e*x＝(a1*a)*x＝a1*(a*x)＝a1*b＝x。所以，x

－

－＝a1*b是a*x＝b的惟一解。－

八、（10分）给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。

证明

由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝

fF24。若存在f∈F，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。

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

一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。

(1)写出F在全功能联结词组{}中的命题公式。(2)写出F的主析取范式与主合取范式。

解

(1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F＝(A∧C)∨(B∧C)。在全功能联结词组{}中：

A(A∧A)AA A∧C(A∧C)(AC)(AC)(AC)

A∨B(A∧B)((AA)∧(BB))(AA)(BB)所以

F((AC)(AC))∨((BC)(BC))(((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC)))(2)F(A∧C)∨(B∧C)

(A∧(B∨B)∧C)∨((A∨A)∧B∧C)(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)m3∨m5∨m7

主析取范式 M0∧M1∧M2∧M4∧M6

主合取范式

二、（10分）判断下列公式是否是永真式？(1)(xA(x)xB(x))x(A(x)B(x))。(2)(xA(x)xB(x))x(A(x)B(x)))。解

(1)(xA(x)xB(x))x(A(x)B(x))(xA(x)∨xB(x))x(A(x)B(x))(xA(x)∨xB(x))∨x(A(x)∨B(x))(xA(x)∧xB(x))∨xA(x)∨xB(x)(xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(x)∨xB(x))x(A(x)∨A(x))∨xB(x)T

所以，(xA(x)xB(x))x(A(x)B(x))为永真式。

(2)设论域为{1，2}，令A(1)＝T；A(2)＝F；B(1)＝F；B(2)＝T。

则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真；而由于A(1)B(1)为假，所以x(A(x)B(x))也为假，因此公式(xA(x)xB(x))x(A(x)B(x))为假。该公式不是永真式。

三、（15分）设X为集合，A＝P(X)－{}－{X}且A≠，若|X|＝n，问(1)偏序集是否有最大元？(2)偏序集是否有最小元？

(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。解

偏序集不存在最大元和最小元，因为n＞2。

考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X。偏序集与偏序集

相比，恰好缺少第0层和第n层。因此的极小元就是X的所有单元集，即{x}，x∈X；而极大元恰好是比X少一个元素，即X－{x}，x∈X。

四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解

r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，－

<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i11>，<5，4>，<5，5>}。

五、（10分）设函数g：A→B，f：B→C，(1)若fg是满射，则f是满射。(2)若fg是单射，则g是单射。

证明

因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。

(1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是满射。

(2)对任意的x1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。

六、（10分）有幺元且满足消去律的有限半群一定是群。

证明

设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。

考虑a，a2，„，ak，„。因为G只有有限个元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。

于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*am-1＝am-1*a＝e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。

七、（20分）有向图G如图所示，试求：(1)求G的邻接矩阵A。

(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？

(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。(4)求出可达矩阵P。(5)求出强分图。

解

(1)求G的邻接矩阵为：

00A00101011

101100(2)由于

002A001110220130A0211102011120322044A

031201012313 2322所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于

00ATA000002131212TAA

21011102132110 2121再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。

(4)00B4AA2A3A40000所以求可达矩阵为P0000(5)因为PPT0010100110+10101000111111。

11111111101111∧1111111100001110＝01110111000111，所以{v1}，{v2，v3，v4}

111111因

1110



2010

1110

0110

2120312204+

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

000

为

741



747，747



434构成G的强分图。

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

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明

因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。(1)R

附加前提(2)PR

P(3)P

T(1)(2)，I(4)P∨Q

P(5)Q

T(3)(4)，I(6)QS

P(7)S

T(5)(6)，I(8)RS

CP(9)S∨R

T(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))

P(2)x(P(x)∨Q(x))

T(1)，E(3)x(P(x)∧Q(x))

T(2)，E(4)P(a)∧Q(a)

T(3)，ES(5)P(a)

T(4)，I(6)Q(a)

T(4)，I(7)x(P(x)(A(x)∨B(x))

P(8)P(a)(A(a)∨B(a))

T(7)，US(9)A(a)∨B(a)

T(8)(5)，I(10)x(A(x)Q(x))

(11)A(a)Q(a)

T(10)，US(12)A(a)

T(11)(6)，I

(13)B(a)

T(12)(9)，I(14)P(a)∧B(a)

T(5)(13)，I(15)x(P(x)∧B(x))

T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解

设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称

i13为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明

小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1i13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。

综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明

(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

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

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。

证明

对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明

(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

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

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

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

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

证明

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

－

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

－

－a>∈R。

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

－

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

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

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

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

一、（10分）证明(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。证明：(P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨Q∨C)

(P∨Q∨A∨C)∧(A∨P∨Q∨C)((P∨Q∨A)∧(A∨P∨Q))∨C ((P∧Q∧A)∨(A∧P∧Q))∨C (A∧((P∧Q)∨(P∧Q)))∨C (A∧(PQ))∨C (A∧(PQ))C。

二、（10分）举例说明下面推理不正确：xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))。

解：设论域为{1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。则： xy(P(x)Q(y))x((P(x)Q(1))∨(P(x)Q(2)))

((P(1)Q(1))∨(P(1)Q(2)))∧((P(2)Q(1))∨(P(2)Q(2)))((TT)∨(TT))∧((TT)∨(TT))T yz(R(y)Q(z))y((R(y)Q(1))∨(R(y)Q(2)))

((R(1)Q(1))∨(R(1)Q(2)))∧((R(2)Q(1))∨(R(2)Q(2)))

((FT)∨(FT))∧((FT)∨(FT))

T

但

xz(P(x)R(z))x((P(x)R(1))∧(P(x)R(2)))((P(1)R(1))∧(P(1)R(2)))∨((P(2)R(1))∧(P(2)R(2)))((TF)∧(TF))∨((TF)∧(TF))F 所以，xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))不正确。

三、（15分）在谓词逻辑中构造下面推理的证明：所有牛都有角，有些动物是牛，所以，有些动物有角。

解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是动物；则推理化形式为：

x(P(x)Q(x))，x(P(x)∧R(x))x(Q(x)∧R(x))下面给出证明：

(1)x(P(x)∧R(x))

P(2)P(a)∧R(a)

T(1)，ES(3)x(P(x)Q(x))

P(4)P(a)Q(a)

T(3)，US(5)P(a)

T(2)，I(6)Q(a)

T(4)(5)，I(7)R(a)

T(2)，I(8)Q(a)∧R(a)

T(6)(7)，I(9)x(Q(x)∧R(x))

T(8)，EG

四、（10分）证明(A∩B)×(C∩D)＝(A×C)∩(B×D)。

证明：因为∈(A∩B)×(C∩D)x∈(A∩B)∧y∈(C∩D)x∈A∧x∈B∧y∈C∧y∈D(x∈A∧y∈C)∧(x∈B∧y∈D)∈A×C∧∈B×D∈(A×C)∩(B×D)，所以(A∩B)×(C∩D)＝(A×C)∩(B×D)。

五、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解

六、（10分）若函数f：A→B是双射，则对任意x∈A，有f1(f(x))＝x。

－证明

对任意的x∈A，因为f：A→B是函数，则∈f，于是

－由f－1是B到A的函数，于是可写为f1(f(x))＝x。

－

七、（10分）若G为有限群，则|G|＝|H|·[G:H]。

证明

设[G:H]＝k，a1、a2、…、ak分别为H的k个左陪集的代表元，由定理8.38得

G[ai]RaiH

i1i1kk又因为对H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|＝…＝|akH|＝|H|。因此

|G||aiH|i1k|aH|k|H|＝|H|·[G:H]。

ii1k

八、（20分）（1）画出3阶2条边的所有非同构有向简单图。

解：由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。度数列与入度列、出度列为： 1、2、1：入度列为0、1、1或0、2、0或1、0、1；出度列为1、1、0或1、0、1或0、2、0 2、2、0：入度列为1、1、0；出度列为1、1、0 四个所求有向简单图如图所示。

（2）设G是n(n≥4)阶极大平面图，则G的最小度≥3。

证明

设v是极大平面图G的任一结点，则v在平面图G－{v}的某个面f内。由于G－{v}是一个平面简单图且其结点数大于等于3，所以d(f)≥3。由G的极大平面性，v与f上的结点之间都有边，因此d(v)≥3。由v的任意性可得，G的最小度≥3。

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

一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。

证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)

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

(P∧Q)∨(P∧(Q∨Q))(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。

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

(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为：

10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；

经过计算可得

10M(R2)111011101100M(R)，所以R是传递的。00

六、（15分）设函数f：R×RR×R，f定义为：f()＝。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f。

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

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

(2)对任意的∈R×R，令x＝－1－

1uwuwuwuw，y＝，则f()＝<＋，2222uwuw－>＝，所以f是满射。22(3)f()＝<－1－1uwuw，>。22－1(4)ff()＝f(f())＝f

－1

()＝<

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

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

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

因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同33

333

2255

13

111理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。

于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。

3333334

344433555444

由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。

八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。

证明不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为v1、v2、„、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、„、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、„、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。

（2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝是不连通的例子。

解下图满足条件但不连通。

离散数学简介及应用第8篇

离散数学是现代数学的一个重要分支,是计算机类专业的重要课程。它以研究离散量的结构及相互间的关系为主要目标,研究对象一般是有限个或可数个元素,因此离散数学可以充分描述计算机学科离散性的特点。它是传统的逻辑学、集合论(包括函数)、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数,计算模型(语言与自动机)等汇集起来的一门综合学科。该课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论及方法大量地应用于数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中;同时,该课程提供的训练有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高,有利于学生严谨、完整、规范的科学态度的培养。

2.离散数学在其他学科的应用

2.1数理逻辑在人工智能中的应用

人工智能是计算机学科一个非常重要的方向。离散数学在人工智能中的应用,主要是数理逻辑部分在人工智能中的应用,包括命题逻辑和谓词逻辑。命题逻辑就是研究以命题为单位进行前提与结论之间的推理, 而谓词逻辑就是研究句子内在的联系。人工智能共有两个流派:连接主义流派和符号主义流派。在符号主义流派里,他们认为现实世界的各种事物可以用符号的形式表示出来, 其中最主要的就是人类的自然语言可以用符号进行表示。语言的符号化就是数理逻辑研究的基本内容, 计算机智能化的前提就是将人类的语言符号化成机器可以识别的符号,这样计算机才能进行推理,才能具有智能。由此可见,数理逻辑中重要的思想、方法及内容贯穿人工智能的整个学科。

2.2图论在数据结构中的应用

离散数学在数据结构中的应用,主要是图论部分在数据结构中的应用,其中树在图论中占着重要的地位。树是一种非线性数据结构, 在现实生活中可以用树来表示某一家族的家谱或某公司的组织结构, 也可以用它来表示计算机中文件的组织结构,树中二叉树在计算机科学中有着重要的应用。二叉树中三种遍历方法:前序遍历法、中序遍历法和后序遍历法,均与离散数学中的图论有密不可分的关系。

2.3离散数学在生物信息学中的应用

生物信息学是现代计算机科学一个崭新的分支, 是计算机科学与生物学相结合的产物。目前,美国有一个国家实验室Sandia国家实验室 , 主要进行组合编码理论和密码学的研究 ,该机构在美国和国际学术界有很高的地位。另外,由于DNA是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人Rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且IBM公司将成立一个生物信息学研究中心。在1994年, 美国计算机科学家阿德勒曼公布了DNA计算机的理论, 并成功地运用DNA计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大反响,同时引起了国内学者的关注。DNA计算机的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的DNA序列反应,作为实现运算的过程;这样,以反应前DNA序列作为输入的数据, 反应后的DNA序列作为运算的结果,DNA计算机几乎能够解决所有的NP完全问题。

2.4离散数学在门电路设计中的应用

在数字电路中,离散数学的应用主要体现在数理逻辑部分的使用。在数字电路中, 广于使用的逻辑代数即为布尔代数。逻辑代数中的逻辑运算与、或、非、异或与离散数学中的合取,析取、否定、异或(排斥或)相对应。数字电路的学习重点在于掌握电路设计技术,在设计门电路时,要求设计者根据给出的具体逻辑问题,求出实现这一逻辑功能的逻辑电路。

总之,离散数学无处不在,它的主要应用就是在各种复杂关系中找出最优的方案。离散数学完全可以看成是一门量化的关系学,一门量化了的运筹学,一门量化了的管理学。现在我国每一所大学的计算机专业都开设离散数学课程, 正是由于离散数学在计算机科学中的重要应用, 因此可以说没有离散数学就没有计算机理论,也就没有计算机科学。所以应努力学习离散数学,推动离散数学的研究,使它在计算机中有着更广泛的应用。

摘要：离散数学是现代数学的一个重要分支,在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时是计算机专业的许多专业课程,如程序设计语言、数据结构、算法设计与分析等课程必不可少的先行课程。通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【离散数学期末试题】相关文章：

离散数学教学06-15