(完整word版)北京理工大学数学专业离散数学期末试题(MTH17068,MTH17175)
亲爱的读者：
本文内容由我和我的同事精心收集整理后编辑发布到
文库，发布之前我们对文中内容进行详细的校对，但
难免会有错误的地方，如果有错误的地方请您评论区
留言，我们予以纠正，如果本文档对您有帮助，请您
下载收藏以便随时调用。下面是本文详细内容。
最后最您生活愉快 ~O(∩_∩)O ~
课程编号：MTH17068 北京理工大学2012-2013学年第一学期
2011级离散数学试题A 卷
一、选择题（本大题共10小题，每小题2分，共20分）
1.下列不是命题的是
A.7能被3整除
B.5是素数当且仅当太阳从西边升起
C.x+7<0
D.北京理工大学位于北京市西城区
2.设p ：王平努力学习，q ：王平取得好成绩。命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为
A.p q →
B.p q ?→
C.q p →
D.q p ?→
3.下列4个推理定律中正确的是
A.A A B ?∨（附加律）
B.()A B A B ∨∧??（析取三段论）
C.()A B A B →∧?（假言推理）
D.()A B B A →∧??（拒取式）
4.设解释I 如下：个体域{}()()()()1,2,1,12,20,1,22,11D F F F F =====。在此解释下，下列各式真值为1的是
A.(),x yF x y ??
B.(),x yF x y ??
C.(),x yF x y ??
D.(),x yF x y ??? 5.下列4个命题为真的是 A.Φ∈Φ B.{}a Φ∈ C.{}{}Φ∈Φ
D.Φ?Φ
6.设{},,A a b c =上的二元关系{},,,,,R a a b b a c =<><><>，则关系R 的对称闭包()s R 为
A.A R I
B.R
C.{},R c a <>
D.A R I
7.设{},,A a b c =，则下列是A 的划分的是
A.{}{}{},,b c c
B.{}{}{},,,a b a c
C.{}{},,a b c
D.{}{}{},,a b c
8.下列编码是前缀码的是
A.{1,11,101}
B.{1,001,0011}
C.{1,01,001,000}
D.{0,00,000}
9.下列图既是Euler 图又是Hamilton 图的是 A.9K B.10K C.2,3K
D.3,3K
10.下列图一定是平面图的是
A.5K
B.,,9,22G V E V E =<>==
C.3,3K
D.,,10,8G V E V E =<>==
二、填空题（本大题共10小题，每小题2分，共20分）
1.若对命题P 赋值1，对命题Q 赋值0，则命题P Q ?的真值为_______________。
2.命题()p q r →→在连接词完备集
{},,?∧∨中等值形式之一为
__________________。 3.设{}{}1,4,2,4A B ==，则()()P A P B -=______________。
4.设R 是等价关系，则R 具有______________性质。
5.设函数()()21,2f x x g x x =+=，则()f g x =______________。
6.设G 是n 阶完全图，则G 的边数m=___________。
7.命题“设G 为n 阶无向简单图，若(),u v V G ?∈，u ，v 不相邻，且()()1d u d v n +≤-，则G 不是Hamilton 图”的真值为_______。
8.若无向连通图G 是Euler 图，则G 中每个顶点的度数为________。
9.设树T 有m 个顶点n 条边，则T 中顶点数与边数的关系是__________。 10.对于完全图n K ，点色数()n K χ=___________。
三、（10分）某项工作需要A,B,C,D 四个人中的两个人去完成，选派满足下面的3个条件，问有几种派法？如何选派？
（1）若A 去，则B 和C 中要去一人；（红色部分为原文缺失，选补之）
（2）B ，C 不能都去；
（3）若C 去，则D 留下。
四、（10分）用等值演算法求()()P Q P Q ?→→∨?的主析取范式和主合取范式。
五、（10分）设
（1）画出A 的Hasse 图；（2）求A 的极大元和极小元；（3）求{}4,6B =的上确界和下确界。
六、（10分）设集合()()()()()()(){}0,0,0,1,1,0,1,3,2,2,2,3,3,1A =，
A 上的关系()()()(){},,,|,,,R a b c d a b c d A a b c d =<>∈∧+=+。
（1）证明R 是A 上的等价关系；（2）给出由R 确定的对A 的划分。
七、（10分）设无向带权图G 如下，求G 的最小生成树T 及T 的权总和，要求写出求解过程。
八、（10分）给定无向简单图G=
12n m C -≥+时，G 是Hamilton 图。
课程编号：MTH17068 北京理工大学2013-2014学年第一学期 2012级离散数学试题A 卷
一、选择题（本大题共10小题，每小题2分，共20分）
1.下列命题为假命题的是
A.如果2是偶数，那么一个公式的析取范式唯一
B.如果2是偶数，那么一个公式的析取范式不唯一
C.如果2是奇数，那么一个公式的析取范式唯一
D.如果2是奇数，那么一个公式的析取范式不唯一
2.设p ：天下大雨，q ：他在室内运动。命题“除非天下大雨，否则他不在室内运动”可符号化为 A.q p ?∨ B.p q ?→ C.p q ?→? D.p q →?
3.下列4个推理定律中不正确的为
A.A A B ?∨（附加律）
B.()A B A B ∨∧??（析取三段论）
C.()A B A B →∧?（假言推理）
D.()A B B A →∧??（拒取式）
4.“没有不犯错误的人”的逻辑符号化为 设H(x)：x 是人，P(x)：x 犯错误。
A.()()()x H x P x ?→
B.()()()()x H x P x ??∧?
C.()()()()
x H x P x ??→? D.()()()x H x P x ?→
5.下列是真命题的有
A.{}{}{}a a ?
B.{}{}{}{},Φ∈ΦΦ
C.{}{},Φ∈ΦΦ
D.{}{}{}Φ∈Φ 6.设集合{},,A a b c =上的关系如下，具有传递性的是
A.{},,,,,,,R a c c a a b b a =<><><><>
B.{},,,R a c c a =<><>
C.{},,,,,,,R a b c c b a b c =<><><><>
D.{},R a a =<>
7.设{},,A a b c =，则下列是集合A 的划分的是
A.{}{}{},,b c c
B.{}{}{},,,a b a c
C.{}{},,a b c
D.{}{}{},,a b c
8.下列编码是前缀码的是 A.{1,11,101} B.{1,001,0011} C.{1,01,001,000}
D.{0,00,000}
9.下图中既不是Euler 图，也不是Hamilton 图的图是
A
10.下面的图为平面图的是
A.5K
B.,,9,22G V E V E =<>==
C.3,3K
D.,,10,8G V E V E =<>==
二、填空题（本大题共10小题，每小题2分，共20分）
1.若对命题P 赋值1，对命题Q 赋值0，则命题P Q ?的真值为_______________。
2.命题()p q r →→在联结词全功能集{},,?∧∨中等值形式之一为__________________。
3.设集合{}{}1,4,2,4A B ==，则()()P A P B -=______________。
4.设关系R 是相容关系，则R 满足______________性质。
5.给定集合A={1,2,3,4,5}，在集合A 上定义两种关系：R={<1,2>,<3,4>,<2,2>}，
S={<4,2>,<2,5>,<3,1>,<1,3>}，则R S =______________，S R =______________。
6.设G 是图3,4K ，则G 的边数m=___________。
7.命题“G 为n 阶无向简单图，若(),u v V G ?∈，u ，v 不相邻，且()()1d u d v n +≤-，G 不是Hamilton 图”的真值为_______。
8.无向连通图G 是Euler 图，当且仅当G 中每一个顶点的度数都为________。 9.设G 是完全二叉树，G 有7个点，其中4个叶点，则G 的总度数为__________。 10.对于完全图n K ，点色数()n K χ=___________。
三、（10分）某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习。选派必须满足以下条件：（1）若赵去，钱也去；（2）李、周二人中必有一人去；（3）钱、孙两人中去且仅去一人；（4）孙、李两人同去或同不去；（5）若周去，则赵、钱同去。
用等值演算法分析该公司如何选派他们出国？
四、（10分）用等值演算法求命题公式()P Q R →→的主析取范式和主合取范式。
五、（10分）设
画出R 的Hasse 图；（2）求A 的极大元和极小元；（3）求{}3,6,9B =的上确界和下确界。
六、（10分）设A,B 为任意集合，证明：
（1）()()()P A P B P A B =；（2）()()()P A P B P A B ?。
七、（10分）如下图所示的赋权图表示某七个城市
127,,,v v v 及预先算出它们之间的一些直接通信
能够通信而且总造价最小。 八、（10分）今要将6人分成3去完成3项任务。已知每个人至少与其余5个人 中的3个人能相互合作。
（1）能否使得每组的2个人都能相互合作？
（2）你能给出几种不同的分组方案？
课程编号：MTH17175 北京理工大学2015-2016学年第一学期
2013级离散数学期末试题？卷（实为离散数学Ⅱ，组合数学） 1.（10分）某车站有1-6六个入口，每个入口每次只能进一个人，问一小组9个人进站的方案数有多少？
解I ：把两个入口间设上一个标志，加上这5个标志相当于每一个排列有14个元素，问题转化为重集{1*p 1,1*p 2,…,1*p 9,5*标志}的全排列（p i 代表9个人，i=1,…,9），故进站方案数为14!/5!=726485760；
解II ：考虑9个人选择方案，第1个人有6种选择，第2个人除了选择入口，还要考虑在第1个人的前面或后面，故有7种选择…同理，第9个人有14种选择，根据乘法法则，故进站方案数为6×7×…×14=726485760。
2.（10分）证明10人中一定有4人相互认识或有3人相互不认识。
证明：在这10个人中任意挑选一个人，不妨把这个人称作p 。则其他的9个人可以分为下面的两个集合F 和S 。其中F=与p 相识的人的集合，S=与p 不相识的人的集合，
如果S 中有4个（或4个以上）人，则或者这4个人（或4个人以上）或者彼此认识，或者有两个人彼此不认识。如果有4个人彼此认识，则结论成立。如果在S 中有2人彼此不认识，则由于这两个人都与p 不认识，因此有3人彼此不认识，故定理结论成立。
如果S 中最多有3个人，则由鸽笼原理知，F 中至少有6个人。由定理2.3知，F 中一定有3人相互认识或有3人相互不认识。如果有3个人彼此不认识，则定理成立。如果有3个人彼此认识，则把p 加入，就有4个彼此认识的人，故定理得证。 3.（20分）设 n 对夫妻围一圆桌而坐，求：
（1）每对夫妻相邻而坐的方案数；（2）男女相间而坐的方案数；
53v 1720
（3）男女相间而坐，每个男人都不和他的妻子相邻的排列数。
（3）解：不妨令n 个女人先围成一圈，方案数为(n-1)!。对任一这种给定方案，顺时针给每个女人编号1,2,…,n 。设第i 号女人顺时针与下一个女人之间的位置为第i 号位置，第i 号女人的丈夫的编号也为第i 号，1≤i ≤n 。让n 个男人坐到上述编号的n 个位置上。设a i 是坐在第i 号位置上的男人，则a i ≠i,i-1,2≤i ≤n ，a 1≠n,1。这样的限制也即要求在下面3行n 列的排列中
a 1 a 2 a 3 … a n-1 a n
1 2 3 … n -1 n
n 1 2 … n -2 n-1
每列中都无相同元素。满足这样的限制的排列a 1a 2…a n 称为二重错排。设二重错排
的个数为Un ，原问题所求的方案数就是U n (n-1)!。设A i 为a i =i,i-1,2≤i ≤n ，
A 1为a 1=n,1的排列a 1a 2…a n 的集合，则|A i |=2(n-1)!，因为A i 表示两个位置集合，关键是计算k 个A i 的交集的排列数。考虑(n,1)(1,2)(2,3)…(n -1,n)这n 对数的k 对中各取一数，且互不相同的取法的计数，这相当于从n,1,1,2,2,3,3,4,…,n -1,n-1,n 中取k 个互不相邻数的组合的计数，但首尾的n 不能同时取。根据前面的不相邻组合，其计数为C(2n-k+1,k)-C(2n-4-(k-2)+1,k-2)= C(2n-k,k)×(2n)/(2n-k)，根据容斥原理，有
()
=??-==-- ?-??∑00
22(1)()!2n k n k n n k U q n k k n k 。 4.（20分）r 个相同的球放入n 个不同的盒子里，求：（1）允许有空盒的方案数； （2）无空盒的方案数；（3）每个盒中至少有q 个球的方案数。
5.（10分）证明错排数D n =(n-1)(D n-1+D n-2)，n ≥2。
证明： {1,2,…,n}的错排可以分为两种互不相容的类型。
①对于k ∈{2,3,…,n}，令a 1=k,a k =1。由于a 1≠1，故选取a 1的方法有n-1种。而a 1=k,a k =1的值已定，故将剩下的n-2个数进行错排，由乘法法则，这种类型的错排列数为(n-1)D n-2 。
②对于k ∈{2,3,…,n}，令a 1=k,a k ≠1 。选取a 1的方法仍有n-1种。由于a 1=k 已定，且a k ≠1 ，故将剩下的n-1个数{2,3,…,k -1,1, k+1,…,n}进行错排（此时将1看作k ），由乘法法则，这种类型的错排数为(n-1)D n-1 。由于这两种类型互不相容，由加法法则有D n =(n-1)(D n-1+D n-2)。
6.（10分）求序列(0, 1×2×3, 2×3×4,…, n(n+1)(n+2),…)的普通母函数。
∞=∞-=∞-=∞==-=--=---=++-=+??+??+++++=-∑∑∑∑02323
434024112(1)(1)6(1)(2)(1)6(1)(2)(1)0123234...(1)(2)...6()((1)
解：由牛顿二项式定理的推论，有 将上式两端同时微分两次得 将上式两端再微分得 两边同乘以得 因此 是序列n
n n n n n n n n x x n n x x n n n x x x x n n n x x x x n n n x x f x x ????++0123234,...,(1)(2),...)，，的普通母函数。n n n 7.（10分）设有1,2,4,8,16,32克砝码各一枚，问能称出哪些重量？各有几种方案？并说明其组合意义。
证明：
==++++++------=?????-------==++++=-∑2481632248163264
248163264632630
()(1)(1)(1)(1)(1)(1)
1111111111111(1 (1)
k f x x x x x x x x x x x x x x x x x x x x x x x x x 从普通母函数f(x)可以得知，用这些砝码可以称出从0克到63克的重量，而且办法都是惟一的。实际是0到63的数的二进制表示是惟一的。
8.（10分）一个平面上n 条直线两两相交，任意三条直线不相交于一点，问这些直线将平面分成多少个不同区域？
课程编号：MTH17175 北京理工大学2016-2017学年第一学期
2014级离散数学期末试题A 卷
一、（10分）求命题公式()P Q R →?的主析取范式和主合取范式。
二、（10分）在系统P 中构造下面推理的证明。
如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。
三、（10分）甲、乙、丙、丁有且仅有两人参加比赛，下面四种判断均正确：
（1）甲、乙有且只有一人参加；（2）若丙参加，则丁必参加；（3）乙或丁至少参加一人；
（4）丁不参加，则甲也不参加。试推断哪两人参加了比赛。
四、（15分）给定集合()()(){}1,2,3,4,5,6,
X = 及其上一个关系()(){}
11221221,,,|R x y x y x y x y =+=+。 （1）证明R 是X 上等价关系；（2）求X 关于R 的商集。
五、（15分）设A,B 为任意集合，证明公式：
（1）()()A B P A P B ???；（2）若()()P A P B ∈，则A B ∈。
六、（10分）求从1v 到其它顶点的最短路。
七、（10分）中国邮递员问题。
求带权图G 中的最优投递路线，邮局在1v 。
八、（10分）设G 是6阶无向简单图。
证明G 或它的补图G 中存在三个顶点彼此相邻。
九、（10分）一次会议有20人参加，其中每个人都有不少于10个朋友。问能否让这20人围成一桌入席，使任意相邻两人都是朋友？
结尾处，小编送给大家一段话。米南德曾说过，“学会学习的人，是非常幸福的人”。在每个精彩的人生中，学习都是永恒的主题。作为一名专业文员教职，我更加懂得不断学习的重要性，“人生在勤，不索何获”，只有不断学习才能成就更好的自己。各行各业从业人员只有不断的学习，掌握最新的相关知识，才能跟上企业发展的步伐，才能开拓创新适应市场的需求。本文档也是由我工作室专业人员编辑，文档中可能会有错误，如有错误请您纠正，不胜感激！
At the end, Xiao Bian gives you a passage. Minand once said, "people who learn to learn are very happy people.". In every wonderful life, learning is an eternal theme. As a professional clerical and teaching position, I understand the
importance of continuous learning, "life is diligent, nothing can be gained", only continuous learning can achieve better self. Only by constantly learning and mastering the latest relevant knowledge, can employees from all walks of life keep up with the pace of enterprise development and innovate to meet the needs of the market. This document is also edited by my studio professionals, there may be errors in the document, if there are errors, please correct, thank you!
v 1v 2v 3v 4v 5v 6212334455
67
华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x
2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5
离散数学考试试题（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 ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（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 。
《离散数学J》考试试卷（期中） 课程代码143140320命题单位学院：计算机学院信息教研室 学院:_______________班级:_____________姓名:_______________学号:____________ 1．将下列命题将其符号化。（4分） ①.李平不是不聪明，而是不用功。 假设p:李平聪明，q:李平用功 ②.如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 假设p：我懂得希腊文，q：我了解柏拉图 2．在一阶逻辑中将下列命题符号化。（9分） ①.整数都是有理数，并不是每个有理数一定是整数，有些有理数不是整数。 假设I(x)：x是整数，Q(x)：x是有理数。 ②.某些汽车比所有的火车慢。 假设F(x)：x是火车。G(x)：y是汽车。H(x,y)：x比y快 ③.谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。 假设：M(x)表示“x是人”，K(x)表示“x游戏人生”，L(x)表示“x 一事无成”，H(x,y)表示“x主宰y”，N(x)表示“x是奴隶”。 3．试证明： (┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R))=R(10分) 4．求公式G＝(P→Q)∧R的主析取范式和主合取范式。(12分) 5．先将些列论断符号化，再证明论断的正确性。（15分） 所有的大一学生都要学习英语；并非所有的大一学生都要学习离散数学；故有些学习英语的不学习离散数学。 假设谓词如下：P(x)：x是大一学生；Q(x)：x要学习英语； R(x)：x要学习离散数学。 6．某班学生50人，会排球的有40人，会篮球的35人，会足球的10人，以上三种运动都会的5人，都不会的没有，问只会两种运动的有几人？
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 题 序 一 二 三 四 五 总分 成 绩 签 名 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}P(A) B ．{a}P(A) C ．{{a}}P(A) D ．{{a}}P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．01 B ．0011100000 C ．00 D ．00 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨q D ．r →p ∨q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(x)A(x)┐A B ．(x)(B →A(x))B →(x)A(x) C ．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D ．(x)(y)(A(x)→B(y))( x)A(x)→(y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={
安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等 价关系，R 应取( ) A. ｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C. {〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 2010-2011学年第一学期离散数学期中考试试卷答案 一、（本题满分12分）在命题逻辑中将下列命题符号化。 （1）小王边走路边听音乐。（2）除非a能被2整除，a才能被4整除。 （3）派小张、小李中的一人去开会。（4）小张和小李是同学。 （5）今天是星期一仅当明天是星期二。（6）若2+2≠4，则3+3≠6；反之亦然。 解：（1）令p：小王走路；q：小王听音乐。符号化为p∧q （2）令p：a能被2整除；q：a能被4。符号化为q→p （3）令p：派小张去开会；q：派小李去开会。符号化为（p∧┐q）∨（┐p∧q） （4）令p：小张和小李是同学。符号化为p （5）令p：今天是星期一；q：明天是星期二。符号化为p→q （6）令p：2+2=4；q：3+3=6。符号化为┐p?┐q 二、（本题满分12分）在一阶逻辑中将下列命题符号化。 （1）有的有理数能被2整除。（2）没有不犯错误的人。 （3）人都不一样高。（4）说火车比汽车跑的快是不对的。 （5）4>2与3≥1互为充要条件。（6）除非李键是东北人，否则他一定怕冷。解：（1）令F(x)：x为有理数；G(x)：x能被2整除。符号化为?x(F(x)∧G(x)) （2）令F(x)：x是人，G(x)：x犯错误，则命题符号化为：?x（F（x）→G(x)） （3）令F(x)：x是人；H(x,y)：x与y一样高。符号化为?x?y（F（x）∧F（y）→┐H（x，y））（4）令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快，┐?x?y（F（x）∧G（y）→H（x，y））（5）令F(x,y)：x>y，G(x,y):x≥y，a:4，b:2，c:3，d:1。符号化为F(a,b)?G(c,d) （6）令F(x)：x是东北人，G(x)：x怕冷，a：李键，符号化为┐G（a）→F（a） 三、（本题满分8分）给出公式(q →r) ∧ ( p→p)的真值表并求出成真赋值和成假赋值。解：真值表如下 成真赋值：000、001、011、100、101、111；成假赋值：010、110 四、（本题满分10分）设p:2能整除5，q:太阳从西方升起，r:一年分四季。求下列复合命题的真值： （1）((p ∨q) → r)∧(r→ (p ∧q)) （2）((┐q ?p) → (r ∨p)) ∨ ((┐p ∧┐q) ∧r) 解：由题意，p、q、r的真值分别为0、0、1。（1）的真值为0；（2）的真值为1。 五、（本题满分12分）使用等值演算法判断公式下列公式的类型。 一（6%）选择填空题。 (1) 设S = {1，2，3}，R 为S 上的二元关系，其关系图如右图所示，则R 具有（ ）的性质。 A. 自反、对称、传递； B. 反自反、反对称； C. 自反、传递； D. 自反。 (2) 设A = {1, 2, 3, 4}， A 上的等价关系 R = { (4)没有不犯错的人。 五（10%）在自然推理系统Ｐ中构造下面推理的证明： 如果他是计算机系本科生或者是计算机系研究生，则他一定学过DELPHI语言且学过C++语言。只要他学过DELPHI语言或者Ｃ++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 六（10%）在自然推理系统中构造下面推理的证明（个体域：人类）： 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 七（14%）下图给出了一些偏序集的哈斯图，判断其是否为格，对于不是格的说明理由，对于是格的说明它们是否为分配格、有补格和布尔格（布尔代数）。 八（12%）设S = {1, 2, 3, 4, 6, 8, 12, 24}，“ ”为S上整除关系， (1)画出偏序集> ,S的哈斯图； < (2)设B = { 2, 3, 4, 6, 12}，求B的极小元、最小元、极大元、最大元，下界，上界。 九（8%）画一个无向图，使它是： (1)是欧拉图，不是哈密尔顿图； (2)是哈密尔顿图，不是欧拉图； (3)既不是欧拉图，也不是哈密尔顿图； 并且对欧拉图或哈密尔顿图，指出欧拉回路或哈密尔顿回路，对于即不是欧拉图也不是哈密尔顿图的说明理由。 十（8%）设6个字母在通信中出现的频率如下： 12 13 :c :b% 45 :a% % :e% :f 9 5 : d% % 16 用Huffman算法求传输它们的最佳前缀码。要求画出最优树，指出每个字母对应的编码，n个按上述频率出现的字母需要多少个二进制数字。 并指出传输)2 ( n 10≥离散数学期末试题及答案完整版
河海大学文天学院09级离散数学期中考试试卷答案
厦门大学离散数学2015-2016期末考试试题答案年
相关主题
文本预览