离散数学单元测试试题1

第一篇：离散数学单元测试试题1

临沂大学2015—2016学年度第1学期

离散数学单元测试试题一

(适用于2014级计算机科学与技术、软件工程、网络工程专业本科学生)

一、选择题(共10题，每题3分，共30分)1.下列语句中为命题的是（D)。A.这朵花是谁的？ B.这朵花真美丽啊！C.这朵花是你的吗？ D.这朵花是他的。

2.若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为(B)。A.p∨q

B.p∧┐q

C.p→┐q

D.p∨┐q 3.命题公式p∨q→q的公式类型为（D)。A.矛盾式 B.非重言可满足式 C.重言式

D.条件式

4.若F(x)：x是有理数，G(x)：x能被2整除，则“有的有理数能被2整除”，可符号化为（A)。

A.x(F(x)∧G(x))

B.F(x)∧G(x)

C.xF(x)

D.xG(x)5.设F(x)表示x是火车，G(x)表示y是汽车，H(x，y)表示x比y快，命题“某些汽车比所有火车慢”的符号化公式是（B)。

A.y(G(y)→x(F(x)∧H(x,y)))B.y(G(y)∧x(F(x)→H(x,y)))C.xy(G(y)→(F(x)∧H(x,y)))D.y(G(y)→(x)(F(x)→H(x,y)))6．设集合A={1,2,3},A上的关系R={<1,2>,<1,3>,<3,3>},则R具有(D)。A.自反性 B.传递性 C.对称性 D.以上答案都不对

######7.谓词公式x(P(x)∨yR(y))→Q(x)中的 x是(C)。A.自由变元 B.约束变元

C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元

8.设X、Y是两个集合且|X|＝n，|Y|＝m，则从X到Y可产生(A)个二元关系。A.n  m B.mn

C.2n m D.nm 9.下列关于集合的表示中正确的为(C)。A.{a}{a,b,c} B.{a}{a,b,c}

C.{a,b,c} D.{a,b}{a,b,c} 10．设集合A={1,2,3,4,5},下列哪些是集合A的划分(D)。A.{{1,2},{3,5}}

B.{{1,2,3,4},5} C.{ ,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}}

二、填空题(共10空，每空3分，共30分)1.设p：2＋2＝5，q：明天是阴天，则命题“只要2＋2＝5，那么明天是阴天”可符号化为 p->q，其真值是 1。

2.设p:你陪伴我，q:你代我叫车子，r:我出去，则“如果你不陪伴我或不代我叫车子,我就不出去。”的符号化形式为 ¬p/¬q->r。

3.设p: 天下雨，q: 天刮风，r: 我去书店，则“如果天不下雨并且不刮风，我就去书店”的符号化形式为。

4.设S(x)∶x是大学生；K(x)∶x是运动员。则“有些运动员不是大学生”的符号化为。

5.设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则“小李非常聪明且能干”的符号化形式为。

6.设F(x): x是人，G(x): x用右手写字，则“有的人并不用右手写字”的符号化形式为。

7.设S(x)：x是学生；L(x)：x喜欢英语。则“有些学生喜欢英语”的符号化为：。8.在公式x(P(z)→Q(x,z))∧zR(x,z)中，x的辖域是

，z的辖域是。

三、计算与证明(共2题，每题20分，共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。

2.在命题逻辑自然推理系统中，构造下面推理的证明。前提： p∨q, q→r, p→s, ┐s，结论：r ∧

(p∨q)。

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

离散数学考试试题（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

第三篇：离散数学复习题1

逻辑

1、给出的真值表

2、证明为永真式 谓词量词和推理

1、使用量词和谓词表达不存在这一事实

2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和

1、全集为，求集合A=的位串？它的补集的位串是什么？写出集合A=的所有子集，写出集合

2、从集合到集合能定义多少个函数？下面给出的函数其定义为：该函数是双射吗？是满射吗？该函数是否存在逆函数？如果存在请给出其逆函数。计数

1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字，且每个密码必须至少包含一个数字，问总共有多少个合适的密码？

2、在30天的一个月里，某棒球队一天至少打一场比赛，但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛

3、证明n个元素的集合中允许重复的r组合数等于

4、按照字典顺序生成整数1，2，3的所有排列（不允许重复），在362541后面按照字典顺序的下一个最大排列是什么？找出在1000100111后面的下一个最大的二进制串。关系

1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵，其中

2、S是所有比特串的集合，关系定义为当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系，例如0101，0011100101，但01010，0101101110。证明是S上的等价关系，由产生的S的等价类是那些集合？

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的？ 图与树

1、在下图所示的图中，从a 到d的长度为4的通路有几条？该图是否是Euler图，是否是Hamilton图，该图的度序列是什么？该图是否可平面，如果是请给出平面画图，该图的点色数和边色数等于多少？给出该图的一个生成树，2、求下面赋权图从a到z的最短距离是多少？最短路径是什么？（画图给出标号过程）

3、用哈夫曼编码方法来编码下列符号，这些符号具有下列频率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少？

4、下面树的高度是多少？那些节点是内部节点，那些节点是叶子节点，该树是否是3元正则树？分别给出该树节点的前序、中序、后序遍历的节点访问次序

第四篇：离散数学练习题1

1、下列句子是简单命题的是（）

A)3是素数。B)2x+3<

5C)张三跟李四是同学吗？D)我在说谎。

2、下列公式不是永真式的是（）．．

A)((p∧q))→p)∨rB)p→(p∨q∨r)

C)┓(q→r)∧rD)(p→q)→(┓q→┓p)

3、设命题公式G<=>┓(p→q)，H<=>p→(q →┓p)，则G与H的关系是()。

A)G<=>HB)H→GC)H => GD)G => H4、下列命题不为真的是（）．

A)Φ  ΦB)Φ∈Φ

C){a,b}∈{a,b,c,{a,b}}}D){a,b}{a,b,c,{a,b}}

5、1到300之间（包含1 和1000）不能被3、5和7整除的数有（）个。

13、下列运算在指定集合上不符合交换律的是（）。

A)复数C集合上的普通加法B)n阶实矩阵上的乘法 C)集合S的幂集上的∪D)集合S的幂集上的

14、下列集合对所给的二元运算封闭的是（）

A)正实数集合R+和。运算，其中。运算定义如下：a,b∈R+，a。b=ab-a-b B)n∈Z+，nZ={nZ|z∈Z}，nZ关于普通的加法运算 C)S={2x-1|x∈Z+}关于普通的加法运算

D)S={x|x=2n, n∈Z+}，S关于普通的加法运算

15、设V=,其中*定义如下：a，b∈Z, a*b=a+b-2 ,则能构成的代数系统是（）。

A)半群、独异点、群B)半群、独异点C)半群D)二元运算

上有○

A)138B)120C)68D)1246、设A, C, B, D为任意集合，以下命题一定为真的是（）

A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C

C)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得A  A ×A7、设A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的关系，则R的性质是（）

A)既是对称的也是反对称的 B)既不是对称的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的8、设R是A上的关系，则R在A上是传递的当且仅当（）

则这4个运算中满足幂等律的是（）

17、在上述四个运算中有单位元的是（）

18、在上述四个运算中有零元的是（）

19、与命题公式P（QR）等值的公式是()

A)(PQ)RB)(PQ)RC)(PQ)RD)P(QR)

20、下列集合都是N的子集，能够构成代数系统V=的子代数的是（）

A)｛x| x∈N∧x与5互为素数｝B)｛x| x∈N∧x是30的因子｝ C){x| x∈N∧x是30的倍数}D){x|x=2k+1, k∈N }

二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)

1、公式┓(p∨q)→p的成假赋值为00__,公式┓(q→p)∧p的成真赋值为。

2、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么Ａ<->Ｂ是重言式（重言式、矛盾式或可满足式）。

3、f：N->N×N，f(x)=,A={5},B={<2,3>,<7,8>},则f(x)是A)IA  RB)R=R-1C)R∩IA ΦD)R。RR9、设A={1,2,3,4,5,6,7,8},R为A上的等价关系R={|x,y ∈ A ∧ x=y(mod 3)}

其中，x=y(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即[1]，为（）

A){1,4,7}B){2,5,8}C){3,6}D){1,2,3,4,5,6,7,8}

10、当集合A=Φ且B≠Φ时，则BA结果为（）

A)ΦB){Φ} C){Φ, {Φ}}D)错误运算

11、函数f:R→R,f(x)= x2-2x+1,则f(x)是（）函数。

A)单射B)满射C)双射D)不是单射，也不是满射

12、设X={a,b,c,d},Y={1,2,3}，f={,,}，则以下命题正确的是()

A)f是从X到Y的二元关系，但不是从X到Y的函数 B)f是从X到Y的函数，但不是满射的，也不是单射的 C)f是从X到Y的满射，但不是单射 D)f是从X到Y的双射

双射）函数，A在f下的像f(A)＝_{<5,6>}_，B在f下的完全原像f-1(B)=____。

4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（用极小项表示）

5、公式x(F(x,y)→yG(x,y,z))的前束范式为_

6、列出从集合A={1,2}到B={1}的所有二元关系。

7、设A为集合且∣A∣=n，则A共有nP(A)有n

8、设 f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数

⑦ x(F(x)∧G(x)→H(x))前提引入 ⑧ F(a)∧G(a)→H(a)T ⑦UI⑨ F(a)∧G(a)T ③ ⑥合取(10)H(a)T ⑧ ⑨ 假言推理

f。g。h(x)=__，f。g。h(x)=_____。

9、含有n个命题变项的公式共有_____个不同的赋值，最多可以生成___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2___种不同的情况。

10、已知集合A={,{}}，则A的幂集P(A)＝_____。

n

n

n

五、设A={1,2,3,4}，在A×A上定义二元关系R，，∈A×A，R<=>u+y=x+v

(1)证明R是A×A上的等价关系

(2)确定由R引起的对A×A的划分。(5分)

三、利用公式的主合取范式判断下列公式是否等值。（5分）

p→(q→r)与(p∧q)∨r p→(q→r)

<=>p∨(q∨r)<=>p∨q∨r <=>M6

(p∧q)∨r

<=>(p∨q)∨r <=>p∨q)∨r <=>M6

(1)证明:  ∈ A×A => x+y=y+x=> ∈ R∴R是自反的  ∈ A×A , R => x+v=y+u=> R∴R是对称的  ,∈ A×A , R ∧ R=> x+v=y+u ∧ u+n=v+m

=> x+v+u+n=y+u+v+m => x+n=y+m => R ∧∴R是传递的(2)

解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}

四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）

每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将获得成功。

六、A= {1,2,3,4,6,8,12}，R是A上的整除关系，请作出偏序集的哈斯图，给出关系矩阵，并

求出A的极大元、极小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）

解:

首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x

在事业中获得成功；a：华有为。

前提： x(M(x)→F(x)），x(F(x)∧G(x)→H(x)),M(a)∧ G(a)

结论：H(a)

证明：① M(a)∧ G(a)前提引入 ② M(a)T ①化简规则 ③ G(a)T ①化简规则 ④ x(M(x)→F(x)）前提引入 ⑤ M(a)→F(a)T ④

⑥ F(a)T ② ⑤ 假言推理

解:A的极大元为8、12,极小元为1，无最大元，最小元为1。

B的上界为12，下界为1，最小上界为12，最大下界为1。

七、在自然推理系统P中构造下面推理的证明。（5分）(1)前提：(p∨q)→(r∧s),(s∨t)→u

结论：p→u(2)前提：x(F(x)→(G(a)∧ R(x)))，x F(x).九、证明下列恒等式 A-(B∪C)=(A-B)∩(A-C)。（5分）证明：A-(B∪C)

结论： x(F(x)∧ R(x)).(1)证明：① p附加前提引入规则② p ∨ q①附加规则③(p ∨ q)→(r ∧ s)前提引入

④ r ∧ s②③ 假言推理⑤ s④化简规则⑥ s ∨ t⑤附加规则⑦(s ∨ t)→ u前提引入

⑧ u⑥ ⑦假言推理

(2)证明：① x F(x)前提引入② F(b)① EI③ x(F(x)→(G(a)∧ R(x)))前提引入④ F(b)→(G(a)∧ R(b))③ UI

⑤ G(a)∧ R(b)② ④假言推理⑥ R(b)⑤化简⑦ F(b)∧ R(b)②⑥合取⑧x(F(x)∧ R(x))⑦EG

八、设有理数集合Q上的 * 运算定义如下：a，b∈Q, a*b=a+b-ab。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）

解：(1)因为a*b=a+b-ab =b+a-ba=b*a，所以运算满足交换律。

(2)因为(a*b)*c=(a+b-ab)*c= a+b-ab+c-(a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)= a+b+c-ab-bc-ac+abc故运算满足结合律。

(3)任意x∈Q，因为x*x=x+x-xx=2x+x2≠x，故不满足幂等律(4)因为对a∈Q，有a*0=a+0-a0=a，所以0是单位元。(5)因为对a∈Q，有a*1=a+1-a=1，所以1是零元。

(6)对a∈Q，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a≠1时，其逆元为a=a/(a-1)，1没有逆元。

1＝A∩～(B∪C)＝A∩～B∩～C = A∩A∩～B∩～C ＝(A∩～B)∩(A∩～C)=(A-B)∩(A-C)

十、设A,B为任意集合，证明：AB<=>P(A)P(B)。（5分）证明：先证明充分性（=>）

X∈P(A)=> XA=> XB=> X∈P(B)再证明必要性（<=）

x∈A=> {x}A=> {x}∈P(A)=> {x}∈P(B)=> {x}B=>x∈B 综上所述，AB<=>P(A)P(B)

第五篇：大学离散数学复习试题

离散数学练习题目

一、选择题

1．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是错的。

A、A； B、{6，7，8}A； C、{{4，5}}A； D、{1，2，3}A。

2.已知集合A={a,b,c},B={b,c,e},则 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列语句中，不是命题的是____A_________ A.我说的这句话是真话； B.理发师说“我说的这句话是真话”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以这些煤不会燃烧；

4.下面___D______命题公式是重言式。

A.PQR ； B.(PR)(PQ)；C.(PQ)(QR)；

D、(P(QR))((PQ)(PR))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为___D______。

A、x(L(x)A(x,y))； B、x(L(x)y(J(y)A(x,y)))； C、xy(L(x)J(y)A(x,y))； D、xy(L(x)J(y)A(x,y))。7.关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是__B_____ A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）

B．z是该谓词公式的约束变元

C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元 8． 设SAB，下列各式中____B___________是正确的。

A、domSB ； B、domSA； C、ranSA； D、domS  ranS = S。9．设集合X，则空关系X不具备的性质是____A________。

A、自反性； B、反自反性； C、对称性； D、传递性。

10.集合A，R是A上的关系，如果R是等价关系，则R必须满足的条件是__D___ A.R是自反的、对称的 B.R是反自反的、对称的、传递的 C.R是自反的、对称的、不传递的 D.R是自反的，对称的、传递的 11.集合A={a,b,c,d},B={1,2,3},则下列关系中__ACD______是函数

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} 已知集合 RA,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},则顶点2的入度和出度分别是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.设完全图Kn有n个结点(n≥2)，m条边，当下面条件__C____满足时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 14.下面叙述正确的是____B______ A.二部图K3,3是欧拉图 B.二部图是平面图

K3,3是哈密尔顿图

C.二部图 K3,32

D.二部图K3,3是既不是欧拉图也不哈密尔顿图

15.已知某平面图的顶点数是12，边数是14，则该平面图有__D___个面 A.3 B.2 C.5 D.4 16．设G是n个结点、m条边和r个面的连通平面图，则m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面几种代数结构中，不是群的是___D____ A. B. C. D.(这里Z，Q，R，N分别表示整数集、有理数集、实数集、自然数集，+普通加法)

二、问答题

1.在程序设计过程中，有如下形式的判断语句： if(a>=0)if(b>1)if(c<0)cout<

请将这段程序化简，并说明化简的理由。解：简化的程序：

if(a>=0 && b>1 && c<0)cout<

设置命题变量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))经过等值演算可得，A与下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①证明R是偏序关系。

②写出偏序集（A，R）的极小元、极大元；最小元、最大元 ③写出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根据整除性质可知，R满足自反性，反对称性，传递性。所以R是A上的偏序关系。

②偏序集（A，R）的极小元：1，极大元：5, 6，7，8，9 最小元：1； 最大元：无

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m个男孩子，n个女孩排成一排，任何两个女孩不相邻，有多少种排法？

(n<=m)插空问题

(2)如果排成一个园环，又有多少种排法？

解：(1)考虑5个男孩，5个女孩的情况

男孩的安排方法： _B_B_B_B_B_ 排列总数P(5,5)女孩的安排方法：6个位置安排5个女孩，排列中数 P(6,5)所以：总的排列方法数是 m!*p(m+1,n)

(2)考虑男孩的圆排列情况，结果是(m-1)!*p(m,n)

4.某商家有三种品牌的足球，每种品牌的足球库存数量不少于10只，如果我想买5只足球，有多少种买法？如果每种品牌的足球最少买一只，有多少种买法？

解：①这是一个多重集的组合问题

类别数是k=3，选取的元素个数是 r=5 多重集组合数的计算公式是 N所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由选取的球只有2个 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(rk1)!C(kr1,r)

r!(k1)!

5．某软件公司将职工分为三种岗位。该公司65人，有些职工（例如项目管理人员、设计人员）可能从事不止一个岗位的工作。每个职工至少被分在一个岗位。现在软件设计岗位（岗位A）（包括需求分析、概要设计和详细设计等工作）的人数是15人，代码编写岗位（岗位B）的人数是32人，软件测试岗位（岗位C）的人数是28人，同时参加岗位A和岗位B的有12人, 同时参加岗位B和岗位C的有8人, 同时参加岗位A和岗位C组的有3人，问，三个岗位参加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 设S表示全班同学总人数，则 |S|=65 求：|A∩B∩C|=？

根据容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因为每个同学至少参加一个小组，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三个小组都参加的人数是13人

6.证明组合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

说明：也可以直接利用组合演算公式进行演算 7.求1228的个位数是多少? 解：1228的个位数就是1228 mod 10的余数1228mod10(12mod10)28mod1024*7mod10(27mod10)4mod108mod1064

8.已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于2, 问G至少有多少个顶点?

解：由握手定理∑d(v)=2m=20，度数为3的顶点有3个占去12度，还有8度由其余顶点占有，而由题意，其余顶点的度数可为0，1，当均为1时所用顶点数最少，所以应有8个顶点占有此8度，即G中至少有8+4=12个顶点。

9刑侦人员审一件盗窃案时，已经掌握的线索如下：（1）甲或乙盗窃了电脑。

（2）若甲盗窃了电脑，则作案时间不能发生在午夜前。（3）若乙证词正确，则在午夜时屋里灯光未灭。（4）若乙证词不正确，则作案时间发生在午夜前。（5）午夜时屋里灯光灭了。

请通过命题逻辑推理，推论出谁是真正的盗窃犯？（写出详细的推理步骤）解 设p： 甲盗窃了电脑，q： 乙盗窃了电脑，r： 作案时间发生在午夜前，s： 乙证词正确，t：午夜时屋里灯光灭了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的时间T与数据规模n的递推关系如下，求出T与n的显示关系表达式

T(n)T(n1)n1 T(1)0

解：

T(n)T(n1)n1 T(n2)n2n1T(n3)n3n2n1 T(nk)nkn2n1T(nk)kn-(12k)k(k1)T(nk)kn2令n-k=1，那么 k=n-1，所以：

n(n1)n(n1)n(n1) T(n)T(1)0222答：T与n的显示关系是：T(n)

11.解下列一阶同余方程组

n(n1)2x1(mod 3)x2(mod 4)x3(mod 5)解：已知a11,a22,a33;m13,m24,m35 方程组的齐次通解是：xkLcm(1,2,3)6k 60k 根据中国剩余定理，特解是：

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)M1m2m320,M2m1m315,M3m1m212 111M1mod m1是下列同余方程的解

3)，解得：x=2，即M12 M1x1(mod m1)即20x1(mod11同理可解得：M23，M33 11 7

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)mod m（120221533123）mod 60111所以：(4090108)mod 60238mod 6058

同余方程组的解是 xxx06k58 60k

12.假设需要加密的明文数据是a=8,选取两个素数p=7,q=19,使用RSA算法： ① 计算出密钥参数

② 利用加密算法计算出密文c ③ 利用解密算法根据密文c反求出明文a 解：① 取 p=7,q=19;计算 n=p*q=7*19=133 计算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 选取较小的数w,使w与108互质, 5是最小的,于是w=5 计算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余数为1, 于是算出d=65 至此加密、解密参数计算完成：

公钥w=5,n=133.私钥d=65,n=133.② 加密

cmwmodn85mod133((82mod133)*(83mod133))mod133

(64*113)mod13350③ 解密

acdmodn5065mod133

aA0A6 其中，A050, Ai(Ai1)2

根据上述递推公式可以计算出：A1502mod133106,A21062mod13364

A3642mod133106，„„, A61062mod13364 aA0A6(50*64)mod1338

解密后的明文与原来的明文是相等的，所以算法正确。

13.设A={1，2，3，4，6，9，12，24},R定义为R{(a,b)|ab(mod 3)}，（1）证明R是一个等价关系；（2）写出A的商集；

14.基于字典序的组合生成算法

问题说明：假设我们需要从5个元素中选取3个的所有组合，已知组合个数为 C（５，３）＝１０，按字典序，其具体组合为： 123,124,125,134,135,145,234,235,245,345 所谓按字典序生成组合，就是已知当前的组合（例如135），求下一个组合（例如，145）。下面给出算法的函数头：

//数组s[]:函数运行前，保存当前的组合，函数结束后，是新生成的下一个组合 //n,r:表示从n个元素中选取r个元素的组合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某单位要从A,B,C三人选派若干人出国考察, 需满足下述条件:(1)若A去, 则C必须去;(2)若B去, 则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案? 9