离散数学期末复习指导(专科)
离散数学期末复习指导（专科）
中央电大理工部计算机教研室
离散数学是中央电大计算机应用专业信息管理方向开设的必修统设课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使所学的知识达到必需、够用，更加适合大学专科层次的教育。目前该课程没有新教材，借用原教材。使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。
离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。
课程的主要内容
本课程分为三部分：集合论、数理逻辑和图论。
1、集合论部分（集合的基本概念和运算、关系及其性质）；
2、数理逻辑部分（命题逻辑、谓词逻辑）；
3、图论部分（图的基本概念、树及其性质）。
学习建议
离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。一、各章复习示例与解析
第一章集合
例1，将“大于3而小于或等于7的整数集合”用集合表示出来。
[解析]
集合的表示方法一般有两种，一种称为列举法，一种称为描述法。
列举法将集合的元素按任意顺序逐一列在花括号内，并用逗号分开。“大于3而小于或等于7的整数”有4、5、6、7，用列举法表示为{4、5、6、7}；
描述法是利用集合中的元素满足某种条件或性质用文字或符号在花括号内竖线后面表示出来。上例用描述法表示为{x| x Z并且3x7}，其中Z为整数集合。
答：{4、5、6、7}或{x| x Z并且3x7}。
例2，判定下列各题的正确与错误：
（1）a{{a}}；
（2）{a}{ a，b，c }；
（3）{ a，b，c }；
（4）{ a，b，c }；
（5）{a，b}{a，b，c，{ a，b，c }}；
（6）{{a}，1，3，4}{{a}，3，4，1}；
（7）{a，b}{a，b，{ a，b }}；
（8）如果A B=B，则A=E。
[解析]
此题涉及到集合中子集的概念，集合的包含关系，空集与集合的关系。解题时要注意区分两个集合之间的关系以及集合中元素与集合之间的关系的不同。
集合之间的关系分为包含关系（子集、真子集）、相等关系、幂集等，判断时要准确理解这些概念，才能正确地运用这些知识。
集合与它的元素之间的关系有两种：一个元素a属于一个集合A，记为a A；一个元素A不属于一个集合A，记为a A。要注意符号的记法（）与集合包含符号记法（，）的不同。
答：正确的是（2）、（4）、（5）、（7）；其余的都是错误的。
例3，设A，B是两个集合，A={1，2，3}，B={1，2}，请计算（A）–（B）。
[解析]
集合的概念一般在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，由集合A的所有子集组成的集合，称为A的幂集，记作（A）
或2A ；一是掌握幂集元数为2n
，n 为集合A 的元数。 集合的基本运算有交、并、差、补。
答：（A ）={，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}}
（B ）={，{1}，{2}，{1，2}}
于是（A ）–（B ）={{3}，{1，3}，{2，3}，{1，2，3}}
例4，试证明（A ~B ）（~A B ）=（A B ）（~A
~B ）
[解析]
证明集合恒等式要熟练运用教材15页集合的10个基本运算。一般来说，欲证P=Q ，即证P Q 并且Q
P ，也就是要证明，对于任意的x ，有下式成立。
x P x Q 和 x
Q x P
证明集合恒等式的另一种方法是利用已知的恒等式来代入。本题就是用的这个方法。 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在A –B=A ~B 证明中的特殊作用。 证明：
()()()()()()
()()()()()()
()()()()()()
B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~???=Φ?????Φ=???????=?????=???
第二章 关系与映射
例1，设集合A={1，2，3，4，5}，试求A 上的模2同余关系R 的关系矩阵和关系图。 [解析]
关系的概念是第二章的基础，又是第一章集合概念的应用。因此应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。
这道题要把R 表示出来，先要清楚“模2同余关系”的概念，如果x ，y 模2同余，就是指x ，y 除以2的余数相同。于是，
R={（1，1），（1，3），（1，5），（2，2），（2，4），（3，1），（3，3），（3，5），（4，2），（4，4），（5，1），（5，3），（5，5）}
求出了关系R 的表达式，就可以进一步求出关系矩阵和关系图了。
答：R 的关系矩阵为：???
???
?
?
?
?=101010101010101
01010
10101
R M
R 的关系图为：
例2，设集合A={1，2，3，，10}，A 上的关系R={（x ，y ）|x ，y A ，且x+y=10}，试
判断R 具有哪几种性质 [解析]
关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质（自反性、对称性、反对称性、传递性）的判定，可以依据其定义，也可以依据教材中49页上总结的关于关系矩阵和关系图的规律。
对于传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若（a 1，a 2）R ，（a 2，a 3）R ，，（a i-1，a i ）R ，则（a 1，a i ）R ；如若（a ，b ）R ，（b ，a ）
R ，则有（a ，a ）R ，
且（b ，b ）R 。
先写出R 的关系式，R={（1，9），（2，8），（3，7），（4，6），（5，5），（6，4），（7，3），（8，2），（9，1）}，并在此基础上判断R 是否具有四种关系的性质。 答：R 只具有关系的对称性。
例3，设集合{}d c b a A ,,,=，判定下列关系，哪些是自反的，对称的，反对称的和传递的：
()(){}()()(){}(){}()()(){}
()(){}
d b c a R c c b b a a R d c R a d c b a a R a b a a R ,,,,,,,,,,,,,,,,,54321=====解：均不是自反的；R 4是对称的；R 1，R 2，R 3，R 4，R 5是反对称的；R 1，R 2，R 3，R 4，R 5是传递的。
例4，设集合A={a ，b ，c ，d}，R 1，R 2都是A 上的二元关系，R 1={（a ，b ），（b ，c ），（c ，a ）}，R 2=，试求R 1和R 2的自反闭包，对称闭包和传递闭包。 [解析]
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理2，自反闭包()A I R R r ?=；定理3，对称闭包()1
-?=R R R s ；定理4的推论，
传递闭包() n
i i
R
R t 1
==
。
答：r （R 1）= R 1I A ={（a ，b ），（b ，c ），（c ，a ），（a ，a ），（b ，b ），（c ，c ）} s （R 1）= R 1 R 1-1
={（a ，b ），（b ，c ），（c ，a ），（b ，a ），（c ，b ），（a ，c ）} R 12
={（a ，c ），（b ，a ），（c ，b ）}
R 13 ={（a ，a ），（b ，b ），（c ，c ）} t （R 1）= R 1 R 1
2
R 13
={（a ，b ），（b ，c ），（c ，a ），（a ，c ），（b ，a ），（c ，b ），（a ，
a ），（
b ，b ），（
c ，c ）}
空关系R 2的自反闭包，对称闭包和传递闭包均为。
例5，设集合{
}5,4,3,2,1=A ，A 上的二元关系R 为： ()()()()()()()(){}5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1=R （１）写出R 的关系矩阵，画出R 的关系图； （２）证明R 是A 上的半序关系，画出其哈斯图；
（３）若A B ?，且{}5,4,3,2=B ，求B 的最大元，最小元，极大元，极小元，最小上界和最大下界。
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。
解：（1）R 的关系矩阵为
???
??
?
?
?
??=111000100001100
00010
00001
R M R 的关系图为
（2）因为R 是自反的，反对称的和传递的，所以R 是A 上的半序关系。（A ，R ）为半序集，（A ，R ）的哈斯图如下：
（3）当B={2，3，4，5}，B 的极大元为2，4；极小元为2，5；B 无最大元与最小元；B 也无上界与下界，更无最小上界与最大下界。
例6，下列映射中哪些是满射，哪些是单射，哪些是双射 （1）??
?=→是偶数是奇数
n n n N N 21)(,:11σσ
（2）?
??=→是偶数是奇数
，
n n n N 01)(},10{:22σσ
（3）1|2|)(,:33+=→a a N Z σσ （4）62)(,:44+=→a a R R σσ
4 1
3 2
映射的概念与映射种类的判定：映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。
答：（1），（3）是非单非满射；（2）是满射；（4）是双射。
第三章 命题逻辑
例1，试证明公式()()()()R P R Q Q P G →→→∧→=为恒真公式。 [解析]
判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种： 一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。
二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G 是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。
这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。 证明：
证法一：真值表法，见《离散数学学习指导书》60页例6（4）的解答。 证法二 ：
G=（（P Q ）（Q R ））（P R ）
=（P
Q ）（Q
R ）P
R
=（（（P Q ）（P R ）
（Q Q ）（Q R ））P ）R
=（（P
Q
P ）（P
R P ）（Q
R
P ））R
=（1（Q R P ））
R
=
Q
R
P R
=1 故G 为恒真公式。
例2，求()()P R Q P G →?∨∧=的主析取范式与主合取范式。 [解析]
求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。
另外，由已经得到的主析取（合取）范式，根据()G G G G =??=?∨,
1原理，参
阅《离散数学学习指导书》71页例15，也可以求得主合取（析取）范式。 解：（1）求主析取范式， [方法1] 利用真值表求解
因此
()()()()()()
7
65431m m m m m m R Q P R Q P R Q P R Q P R Q P R Q P G ∨∨∨∨∨=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧∧?∨∧?∧?=[方法2] 推导法
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()4
67513m m m m m m R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R R Q Q P P P R Q Q Q R P P
R Q R P P
R Q P P R Q P P R R Q P G ∨∨∨∨∨=?∧?∧∨?∧∧∨∧∧∨∧?∧∨∧?∧?∨∧∧?=?∧?∧∨∧?∧∨?∧∧∨∧∧∨∧?∧?∨∧?∧∨∧?∧?∨∧∧?=?∨∧?∨∧∨?∨∧∧?∨∨?∧∧?=∨∧?∨∧?=∨∧?∨?=∨?∨∧?=→?∨∧=
（2）求主合取范式
[方法1] 利用上面的真值表，()()P R Q P →?∨∧为0的有两行，它们对应的极大项分别为R Q P R Q P ∨?∨∨∨,，因此，
()()()()R Q P R Q P P R Q P ∨?∨∧∨∨=→?∨∧
[方法2] 利用已求出的主析取范式求主合取范式，已用去6个极小项，尚有2个极小项，即R Q P ?∧?∧?与R Q P ?∧∧?，于是，
()()()()()()()()
R Q P R Q P R Q P R Q P G G R Q P R Q P G ∨?∨∧∨∨=?∧∧?∨?∧?∧??=??=?∧∧?∨?∧?∧?=?
例3，利用形式演绎法证明 { P （Q R ），S P ，Q}蕴涵S R 。
[解析]
利用形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则P 、规则Q 和规则D ，需要进行一定的练习。 证明：
（1）S P 规则P （2）S 规则D
（3）P 规则Q ，根据（1），（2）
（4）P （Q R ） 规则P
（5）Q R 规则Q ，根据（3），（4） （6）Q 规则P
（7）R 规则 Q ，根据（5），（6） （8）S R 规则D ，根据（2），（7）
第四章 谓词逻辑
例1，在谓词逻辑中将下列命题符号化： （1）凡正数都大于0； （2）存在小于3的素数；
（3）没有不能表示成分数的有理数； （4）参加考试的人未必都能取得好成绩。 [解析]
反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。 解：
（1）))()((x G x F x →?，其中F （x ）：x 是正数，G （x ）：x 大于0； （2）))()((x G x F x ∧?，其中F （x ）：x 大于3，G （x ）：x 是素数；
（3）))()((x G x F x ?∧??，其中F （x ）：x 为有理数，G （x ）：x 能表示成分数。 “没有不能表示成分数的有理数”与“所有的有理数都能表示成分数”是同一个命题的不同的叙述方法，因此本命题也可以符号化为))()((x G x F x →?。
（4）))()((x G x F x →??，其中F （x ）：x 是参加考试的人，G （x ）：x 取得好成绩。与（3）类似，本命题可以符号化为))()((x G x F x ?∧?。
这个例子中几个命题的符号化均有典型性，请同学们注意分析。
例2，设I 是如下一个解释：{}3,2=D
F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1 求()()()()y x F Q x P y x ,∧??的真值。 [解析]
将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I 中的数值代入公式，求出真值。 解：
()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()()1
10111110003,332,333,222,223,2,,=∨=∧∧∧∨∧∧∧=∧∧∧∨∧∧∧=∧∧∧?=∧??F Q P F Q P F Q P F Q P x F Q x P x F Q x P x y x F Q x P y x
例3，试将一阶逻辑公式()()()()()x R y yQ y x yP x ∨??∨??,化成前束范式。 [解析]
在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。 解：
()()()()()()()()()()()()()()()()()()
x R z Q y x P z y x x R z Q z y x yP x x R y Q y y x yP x x R y yQ y x yP x G ∨?∨???=∨??∨??=∨??∨??=∨??∨??=,,,,
第五章 图论
例1，在具有n 个顶点的完全图K n 中删去多少条边才能得到树 [解析]
本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在
数据结构、数据库、计算机网络等课程中用到。
解：n 个顶点的完全图K n 中共有2
)
1(-?n n 条边，n 个顶点的树应有1-n 条边，于是，删去的边有：2
)
2()1()1(2)1(-?-=
---?n n n n n 。
例2，求下面有限图中点u 到各点间的最短路。（图上数字见教材231页第3题。左侧一列的四个点为u 1到u 4，右侧一列的四个点为u 5到u 8）
[解析]
计算权图中的最短路要格执行迪克斯特拉（Dijkstra ）算法的骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。 解：u u 1， d(u, u 1)=1，路(u, u 1)
u u 2，d(u, u 2)=9，路(u, u 4, u 3, u 7, u 2)
u u 3，d(u, u 3)=5，路(u, u 4, u 3 ,) u u 4，d(u, u 4)=3，路(u, u 4 )
u u 5，d(u, u 5)=11，路(u, u 1, u 5)或路 (u, u 4, u 3 , u 7 , u 2 , u 5) u u 6，d(u, u 6)=13，路(u, u 1, u 5, u 6) u u 7，d(u, u 7)=8，路(u, u 4 , u 3 , u 7) u u 8，d(u, u 8)=11，路(u, u 4, u 8)
u v ， d(u, v)=15，路(u, u 1, u 5 , u 6 ,v) 或路(u, u 4 , u 3 , u 7 , u 6 ,v)
例3，利用克鲁斯卡尔（Kruskal ）算法求一棵最优支撑树。
u v
[解析]
权图中的最优支撑树是图中
所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal ）算法。
解：按照Kruskal 给出的在权图中求最优支撑树的算法，可生成下面的最优支撑树：（权和为11）
生成的最优支撑树结果不是唯一的，又如下图（权和为11）也是一种最优支撑树。
例4，一棵树有两个节点度数为2，一个节点度数为3，三个节点度数为4，问它有几个度数为1的节点
解：我们知道一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。
根据这两点，可知树中各点的度数总和=2（树中点数1），设树叶有x 个， 于是，22+3+34+x=2（2+1+3+x-1）
得x=9。
上例可推广为“一棵树有n 2个节点度数为2，n 3个节点度数为3，…，n k 个节点度数为k ，问它有几个度数为1的节点”请同学们思考。
三、 综合练习及参考解答
A 3
B 2
C 1 1 2 4 2
D 3
E 3 2 1
F 2
G 2 H
（一）填空题
1、集合的表示方法有两种： 法和 法。请把“奇整数集合”表示出
来{ }。
2、 A ，B 是两个集合，A={1，2，3，4}，B={2，3，5}，则B-A= ，（B ）
（A ）= ，（B ）的元素个数为 。
3、 设}2,1{},
,{==B b a A ，则从A 到B 的所有映射是
。 4、 设命题公式)(R Q P G →?→=，则使公式G 为假的解释是 、 和 。
5、设G 是完全二叉树，G 有15个点，其中8个叶结点，则G 的总度数为 ，分枝点数为 。
6、全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2，5}， 求A B=
，（A ）
（C ）= ，
C= 。
7、设A 和B 是任意两个集合，若序偶的第一个元素是A 的一个元素，第二个元素是B 的一个元素，则所有这样的序偶集合称为集合A 和B 的 ，
记作A B ，即A B= 。A B 的子集R 称为A ，B 上的 。
8、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。
9、表达式x yL （x ，y ）中谓词的定义域是{a ，b ，c}，将其中的量词消除，写成与之等价的命题公式为 。
10、一个无向图表示为G=（P ，L ），其中P 是 的集合，L 是 的集合，并且要求 。
（二）选择题（选择一个正确答案的代号，填入括号中）
1. 设命题公式))(()(P R Q P P G ∨∧→?∨=，则G 是（ ）。
A.恒真的
B.恒假的
C.可满足的
D.析取范式
2、设集合},,{c b a A =，A 上的关系)},(),,(),,{(c b b a a a R =，则2R =（ ）。
)}.
,(),,(),,{()()};,(),,(),,{()()};
,(),,(),,{()()};
,(),,(),,{()(c c b a a a D b b c a b a C c b c a b a B c a b a a a A
3、一个公式在等价意义下，下面哪个写法是唯一的（ ）。
A ．析取范式
B ．合取范式
C ．主析取范式
D ．以上答案都不对 4、设命题公式G=（P Q ），H=P （Q
P ），则G 与H 的关系是（ ）。
A ．G H
B ．H G
C ．G=H
D ．以上都不是
5、已知图G 的相邻矩阵为???
??
?
?
?
??011111010111000
10001
11010
，则G 有（ ）
。 点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边 6、下列命题正确的是（ ）。
A ．{}=
B ．{}=
C ．{a}{a ，b ，c}
D ．{a ，b ，
c}
7、设集合A={a ，b ，c}，A 上的关系R={（a ，b ），（a ，c ），（b ，a ），（b ，c ），（c ，a ），（c ，
b ），（
c ，c ）}，则R 具有关系的（ ）性质。
A ．自反
B ．对称
C ．传递
D ．反对称 8、设R 为实数集，映射=R
R ，（x ）= -x 2
+2x-1，则是（ ）。
A ．单射而非满射
B ．满射而非单射
C ．双射
D ．既不是单射，也不是满射 9、下列语句中，（ ）是命题。
A ．下午有会吗
B ．这朵花多好看呀！
C ．2是常数。
D ．请把门关上。 10、下面给出的一阶逻辑等价式中，（ ）是错的。
A ． x （A （x ）
B （x ））=xA （x ）xB （x ）
B ． A
xB （x ）=x （A B （x ））
C ． x （A （x ）B （x ））=xA （x ）
xB （x ）
D ． xA （x ）=x （A （x ））
（三）计算题
1、设R 和S 是集合}4,3,2,1{=A 上的关系，其中
)}
4,4(),4,2(),3,2(),2,1{()}
4,3(),3,2(),3,1(),1,1{(==S R ，试求：
（1）写出R 和S 的关系矩阵； （2）计算111,,,
---???R S R S R S R 。
2、 设A={a ，b ，c ，d}，R 1，R 2是A 上的关系，其中R 1={（a ，a ），（a ，b ），（b ，a ），（b ，
b ），（
c ，c ），（c ，
d ），（d ，c ），（d ，d ）}，R 2={（a ，b ），（b ，a ），（a ，c ），（c ，a ），（b ，c ），（c ，b ），（a ，a ），（b ，b ），（c ，c ）}。 （1）画出R 1和R 2的关系图；
（2）判断它们是否为等价关系，是等价关系的求A 中各元素的等价类。 3、 用真值表判断下列公式是恒真恒假可满足
（1）（P
P ）Q
（2）（P Q ）
Q
（3）（（P Q ）（Q R ））
（P
R ）
4、 设解释I 为：
（1）定义域D={-2，3，6}； （2）F （x ）：x 3；
G （x ）：x 5。
在解释I 下求公式x （F （x ）G （x ））的真值。 5、 化简下式：
（（A B
C ）（A B ））（（A （B
C ））A ）
6、 已知A={1，2，3，4，5}，B={1，2，3}，R 是A 到B 的二元关系，并且R={（x ，y ）|x A
且y B 且2 x+y 4}，画出R 的关系图，并写出关系矩阵。
7、 画出下面偏序集（A ，）的哈斯图，并指出集合A 的最小元、最大元、极大元和极小
元。其中A={a ，b ，c ，d ，e}，={（a ，b ），（a ，c ），（a ，d ），（a ，e ），（b ，e ），（c ，e ），（d ，e ）}I A 。
8、 求命题公式)()(Q P Q P ∧?∨?的析取范式与合取范式。 9、给定解释I 如下：
定义域D={2，3}；
f （2） f （3） F （2，2） F （2，3） F （3，2） F （3，3）
3 2 0 0 1 1 求)))(),((),((y f x f F y x F y x →??。 10、求下面带权图的最优支撑树，并计算它的权。
4 7 8
20 12 8 9 10
15
（四）证明题
1、证明等价式R R P R Q R Q P =∧∨∧∨∧?∧?)()())((。
2、 利用形式演绎法证明：},,,,
{T R S T S R P Q P ?→?→?→∨蕴涵Q 。
3、 A ，B ，C 为任意的集合，证明：)()(C B A C B A ?-=--
4、 利用一阶逻辑的基本等价式，证明：)()())()((y yG x xF y G x F y x ?→?=→??
练习题参考解答
（一）填空题
1、列举；描述；}12|{Z k k x x ∈+=，
2、{5}；{{5}，{2，5}，{3，5}，{2，3，5}}；8
3、
1
={（a ，1），（b ，1）}；
2
={（a ，2），（b ，2）}；
3
={（a ，1），（b ，2）}；
4
={（a ，
2），（b ，1）}
4、（1，0，1）； （1，1，1）； （1，0，0）
5、 28； 7
6、{5}；{，{5}}；{1，3，4}
7、笛卡尔积（或直乘积）；{（x ，y ）|x A 且y B}；二元关系 8、并且（或合取）；或者（或析取）；蕴涵 9、（L （a ，a ）
L （a ，b ）
L （a ，c ））（L （b ，a ）L （b ，b ）L （b ，c ））
（L
（c ，a ）L （c ，b ）
L （c ，c ））
10、点；连接某些不同点对的边；一对不同点之间最多有一条边 （二）选择题（选择一个正确答案的代号，填入括号中）
1、C
2、A
3、C
4、A
5、C
6、A
7、B
8、D
9、C 10、A （三）计算题 1、解：（1）
?
?
???
????
???=?
?
???????
???=1000000011000010,0000100001000101
S R M M （2）S R ?={（1，2），（3，4）}
S R ?={（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4）}
1
-R ={（1，1），（3，1），（3，2），（4，3）} 11
--?R S ={（2，1），（4，3）}
2、解：
R1和R2的关系图如下：
R1的关系图 R2的关系图由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。
由于R2不是自反的，所以R2不是等价关系。
3、解：
（1）真值表
P P P （P P）Q
因此公式（1）为可满足。
（2）真值表
P Q （P Q）（P Q）Q
因此公式（2）为恒假。
（3）真值表
P Q Q R P R （（P Q）（Q R））（P R）
0 1 1 1 1 1 1
1 0 0 0 1 0 1
1 0 1 0 1 1 1
1 1 0 1 0 0 1
1 1 1 1 1 1 1
因此公式（3）为恒真。
4、解：
x（F（x）G（x））
（F（-2）G（-2））（F（3）G（3））（F（6）G（6））（10）（10）（01）
1
5、解：
（（A B C）（A B））（（A（B C））A）
=（A B） A （利用两次吸收律）
=（A B）~ A
=（A~ A）（B~ A）
= （B~ A）
= B A
6、解：
R={（1，1），（1，2），（1，3），（2，1），（2，2），（3，1）}
离散数学期末试卷A卷及答案
《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
安徽大学期末试卷离散数学上卷及参考答案.doc
安徽大学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 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。 离散数学期末试卷(A) XXXX大学XX学院2007 ～2008学年第一学期《离散数学》期末试卷年级专业题号得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题1．下列语句中只有不是命题。C A．今年元旦会下雪。B．1+1=10。C．嫦娥一号太棒了！D．嫦娥奔月的神话已成为现实。2．p?q 的主合取范式是。 B A．(p?q)?(p??q)B．(p??q)?(?p?q) C．(p?q)?(?p??q)D．(p?q)?(?p?q) 3．与p? q等值的命题公式是。D A．?p?q B．p??q C．p??q D．?p?q 4．在一阶逻辑中使用的量词只有个。B A．1B．2 C．3D．4 5．??xA(x)?。C A．??xA(x) B．?x?A(x) C．?x?A(x) D．?xA(x) 6．若|A|=4，则|P(A)|=。 C A．4B．8C．16 D．64 7．设A、B、C为任意集合，集合的对称差运算不具有的性质是。 D A．A?B = B?A B．(A?B)?C = B?(A?C) 班级学号一二三姓名____________ 四总分C．A?A = ?D．A?A = A 8．二元关系是。B A．两个集合的笛卡儿积B．序偶的集合C．映射的集合D．以上都不是9．下面关于函数的叙述中正确的是。D A．函数一定是满射B．函数一定是单射C．函数不是满射就单射D．函数是特殊的关系10．半群中的二元运算一定满足=。B A．交换律B．结合律C．分配律D．幂等律11．环中有个二元运算。 B A．一B．二C．三D．四12．群与独异点的区别是。 C A．满足交换律B．满足结 1 / 6 北京工业大学经管学院期末试卷 《离散数学》（A ） 学号 姓名： 成绩 一、单项选择题（每题2分，共18分） 1．令P ：今天下雪了，Q ：路滑，则命题“虽然今天下雪了，但是路不． 滑”可符号化为（ D ） A ．P→Q B ．P ∨Q C ．P ∧Q D ．P ∧Q p→q ，蕴涵式，表示假设、条件、“如果，就”。 “→”与此题无关 2. 关于命题变元P 和Q 的极大项M 1表示( C )。 书P1520，此题换作p 、q 更容易理解 A.┐P ∧Q B.┐P ∨Q p ∨┐q 01 1 M 1 ∨┐Q ∧┐Q 3.设R （x ）：x 是实数；S （）：x 小于y 。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（ D ） 4.在论域{}中与公式（x ?）A （x ）等价的不含存在量词的公式是（ B ） A.)b (A )a (A ∧ B. )b (A )a (A ∨ C. )b (A )a (A → D. )a (A )b (A → 5．下列命题公式为重言式的是（ C ） A ．Q→（P ∧Q ） B ．P→（P ∧Q ） C ．（P ∧Q ）→P D ．（ P ∨Q ）→Q 牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C 不存在1→0的情况 6. 设｛1，2，3｝，｛｝，下列二元关系R 为A 到B 的函数的是( A ) A. ｛<1>,<2>,<3>｝ B. ｛<1>,<2>｝ C. ｛<1>,<1>,<2>,<3>｝ D. ｛<1>,<2>,<3>,<1>｝ 2 / 6 7.偏序关系具有性质（ D ） 背 A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合，映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f ：A→B （1）若，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】 （2）若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】 （3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】 二、填空题（每空2分，共22分） １.设Q 为有理数集，笛卡尔集×Q ，*是S 上的二元运算，? 离散数学试题(A卷及答案） 一、证明题（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) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵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={ 浙江师范大学《离散数学》考试卷 （2010—2011学年第 1 学期） 考试形式闭卷使用学生软件工程、网络工程09 考试时间120分钟出卷时间2010 年12 月26 日 说明：考生应将全部答案都写在答题纸上，否则作无效处理。 一．选择题（每题2分，共20分）： 1. 设P：我平时认真学习，Q：我通过离散数学考试，则如下哪种说法能符号化为 P→Q：（） A．除非我平时认真学习，否则我不能通过离散数学考试。 B. 若我平时认真学习，则我通过离散数学考试。 C. 因为我平时不认真学习，所以我没有通过离散数学考试。 D. 我通过离散数学考试仅当我平时认真学习。 2．命题公式P→(P∨Q∨R) 为（）。 A．重言式B．可满足式C．矛盾式D．等值式 3．设集合A={c, {c}}，下列命题错误的是（）。 A. {c}∈P(A) B. {c}?P(A) C. {{c}}∈P(A) D. {{c}}?P(A) 4. 设f: N N, f(x)=(x) mod 5, 即x除以5的余数，则函数f （）. A. 仅单射 B. 仅满射 C. 双射 D. 既不单设也不满射 5．下列命题中正确的结论是：（） A．集合上A的关系如果不是自反的，就一定是反自反的； B．集合上A的关系如果不是对称的，就一定是反对称的； C．在任意关系R上，若 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷( A 卷) (时间120分钟) 开课院(系、部) ________________ 姓名 _________________ 学号 _______________ 一、选择题(每小题2分，共20分) 1. 下列语句中，哪个是真命题( ) A 、X ? 2 = 4 ； B 、我们要努力学习； C 如果ab 为奇数，那么a 是奇数，或b 是偶数； D 、如果时间流逝不止，你就可以长生不老。 2. 下列命题公式中，永真式的是( ) A (P r Q) — P ； B 、一(Q — P) P ； C 、(P —p) I Q ； D 、P — (P Q)。 3?在谓词逻辑中，令 F(x)表示x 是火车；G(y)表示y 是汽车；L(x, y)表示x 比y 快。命题“并不是所 有的火车比所有的汽车快”的符号表示中哪些是正确的？( ) L 一 x-y(F(x) G(y)r L(x, y)) II. x y(F(x) G(y) L(x,y)) III. x y(F(x) G(y) L(x, y)) A 、仅 I ； B 、仅 III ； C 、I 和 II ； D 、都不对。 4. 下列结论正确的是：( ) A 、若 A B=A C ，则 B=C ； B 、若 A B A B ，则 A = B ； C 若 A B 二A C ，则 B 二C ； D 、若 A B 且 C D ，则 A C B D 。 5. 设 A^ ，A -｛ ｝，A 3 =「(「｝)，A 4 = ，以下命 题为假的是( ) A 、A 2 - A 4 ； B 、A^ — A 3 ； C 、A 4 — A2 ； D 、A 4 - A 3。 6?设R 是集合A 二｛a,b,c,d ｝上的二元关系， R=｛ ::: a,d 「: d,a 「:: a,c 「：c,a 「： b, d j ：：d,b ?｝。下列哪些命题为真？( ) I. R R 是对称的 II. R R 是自反的 III. R R 不是传递的 A 、仅 I ； B 、仅 II ； C 、I 和 II ； D 、全真。 7. R 是二元关系且R = R 4，则一定是传递的是( ) A R 4 ； B 、R 3 ； C 、R 2 ； D 、R 。 &设R 1和R 2是非空集合A 上的等价关系，确定下列各式，哪些是 A 上的等价关系( ) A A A ~■ R<| ； B 、R ~■ R 2 ； C 、R 1 R 2 ； D 、R 1 R 2。 9?函数f :X > Y 可逆的充要条件是：( ) A 、A = B ； B 、|A|=|B| ； C 、f 为双射； D 、f 为满射。 10.下列集合中，哪个集合的基数与其他集合的基数不同( ) 四川大学期末考试试题（闭卷） （2014-2015学年第1学期） 课程号：304039040 课程名称：离散数学（A卷）任课教师：冯伟森石兵周莉陈瑜林兰 适用专业年级： 2013级计算机科学与技术学号：姓名： 一、单项选择题（本大题共16小题，每小题1分，共16分）提示：在每小题列出的四个备选项中只有一个是符 合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分 1.令R: 小王吃饭；S：小王看电视。则语句“小王一边吃饭一边看电视”可以符号化为（）。 （A)R∨S；（B）R∧S；（C）R→S；（D）～R∨～S 2.令P(x):x是实数，Q(x):x是有理数。则语句“并非每个实数都是有理数”可以符号化为（）。 （A）～?x(R(x)→Q(x))；（B）～(R(x)→Q(x))； （C）～?x(R(x)∧Q(x))；（D）～?x(R(x)∨Q(x)) 3.下列公式中，（）是永真公式。 （A）R→S；（B）R∧～R；（C）R∨～R；（D）(R→S) ∧(R∧～S) 4.下列公式中（）是等价公式。 （A）G∧(H∨S) ? (G∨H) ∧(G∨S)；（B）G∧(H∨S) ? (G∧H) ∧(G∧S)； （C）G∧(H∨S) ? (G∧H)∨(G∧S)；（D）G∧(H∨S) ? (G∨H) ∨(G∨S)； 5.公式?x((P(x)→Q(y，x))∧?z R(y，z))→S(x)中，自由变元是( )。 （A）x和y ；（B）y和z；（C）x和z；（D）z或者y 6.设集合A={1，2，3}，则A上所有非等价关系数目为（）。 （A） 512 (B) 507 (C) 508 (D) 506 7.下列关于有限集偏序集〈A,≤〉的描述，（）是正确的 (A) 一定存在最大元(B) 一定存在最小元 (C) 任意两元素都存在最大下界 (D) 一定存在极大元 8.下列说法不正确的是（） (A)任意两个非空集合之间都可构造函数(B) 任意两个非空集合之间都可构造单射函数 (C) 任意两个非空集合之间都可构造满射函数 (D) 任意两个非空集合之间如可构造单射函数，也可构造满射函数，那么一定可构造双射函数 9.下列各组数中，不能构成无向图的点度数序列的是（）。 (A) {1，1，2，2，3} (B) {1，3，5，7，8} (C) {2，2，2，2} (D) {2，2，3，8，1} 10.下列说法正确的是（）。 (A) 树至少有两个叶结点 (B) 存在既是二部图又是哈密顿图的简单无向图 (C) 平面图满足欧拉公式 n – m + f = 2 (D) 连通无向图都有非平凡生成树 11.已知图G中存在一条欧拉道路，以下说法正确的是（）： （A）图中没有奇度数结点；（B）图中只有2个奇度数结点； （C）图中有0个或2个奇度数结点；（D）无法确定图中奇度数结点的个数 12.在实数集R上，定义代数系统 -第 1页 北京工业大学经管学院期末试卷 《离散数学》（A ） 学号 姓名： 成绩 一、单项选择题（每题2分，共18分） 1．令P ：今天下雪了，Q ：路滑，则命题“虽然今天下雪了，但是路不． 滑”可符号化为（ ） A ．P →Q B ．P ∨Q C ．P ∧Q D ．P ∧Q 2. 关于命题变元P 和Q 的极大项M 1表示( )。 A.┐P ∧Q B.┐P ∨Q C.P ∨┐Q D.P ∧┐Q 3.设R （x ）：x 是实数；S （x,y ）：x 小于y 。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（ ） 4.在论域D={a,b}中与公式（x ?）A （x ）等价的不含存在量词的公式是（ ） A.)b (A )a (A ∧ B. )b (A )a (A ∨ C. )b (A )a (A → D. )a (A )b (A → 5．下列命题公式为重言式的是（ ） A ．Q →（P ∧Q ） B ．P →（P ∧Q ） C ．（P ∧Q ）→P D ．（P ∨Q ）→Q 6. 设A=｛1，2，3｝，B=｛a,b ｝，下列二元关系R 为A 到B 的函数的是( ) 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>｝ 7.偏序关系具有性质（ ） A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8 设R 为实数集合，映射:,R R σ→2()21,x x x σ=-+-则σ 是( ). (A) 单射而非满射 (B) 满射而非单射 华南农业大学离散数学期末考试2013试卷及答案 华南农业大学期末考试试卷（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 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 , 北方工业大学理学院 2007 ～2008学年《离散数学》期末试卷（B） 年级专业班级学号姓名____________ 试卷说明：闭卷考试，考试时间120分钟 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 化为。 13．p?q的主合取范式是。 14．完全二部图K r,s（r < s）的边连通度等于。 15．设A={a,b}，,则A上共有个不同的偏序关系。 16．模6加群 2014～2015第一学期考试卷 《离散数学》课程闭卷课程类别：必修考试时间 一、单项选择题(本大题共10小题，每小题2分，共20分) 1.下列不是命题的是[ C ]。 A.7能被3整除. B.5是素数当且仅当太阳从西边升起. C.x加7小于0. D.华东交通大学位于南昌北区. 2. 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为[ A ]。 A. p→q B. ?p→q C. ?q→p D. q→p 3. 下面4个推理定律中，不正确的为[ D ]。 A.A=>(A∨B) (附加律) B.(A∨B)∧?A=>B (析取三段论) C. (A→B)∧A=>B (假言推理) D. (A→B)∧?B=>A (拒取式) 4. 设解释I如下，个体域D={1,2},F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释I下，下列公式中真值为1的是[ A ]。 A.?x ?yF(x,y) B. ?x?yF(x,y) C. ?x?yF(x,y) D. ??x?yF(x,y) 5. 下列四个命题中哪一个为真？[ 的]。 A. ?∈? B. ?∈{a} C. ?∈{{?}} D. ??? 6. 设S={a,b,c,d}，R={ (完整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 =<>== 数学建模作业 姓名：王士彬 学院：计算机科学与技术 班级：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)若表中数据满足正态分布函数222/)(21)(σμπσ --=x e x y .试用最小二乘非线性拟合的方法求出分布参数σμ,值，并利用锁求参数值绘制拟合曲线，观察拟合效果. 解：(1)分别用最领近插值，分段线性插值（缺省值），分段三次样条插值，保形分段三次插值方法绘制在x ∈[-2,4.9]的光滑曲线，图形如下： 样条插值效果最好，其次线性插值，最近点插值效果最差，在这里效果好像不太明显。 最近点插值优点就是速度快，线性插值速度稍微慢一点，但效果好不少。所以线性插值是个不错的折中方法。样条插值，它的目的是试图让插值的曲线显得更平滑，为了这个目的，它们不得不利用到周围若干范围内的点，不过计算显然要比前两种大许多。 MATLAB 文件如下： 离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是 （１）（１）写出和的关系矩阵。（２）求及（1２分）五、求的主析取范式和主合取范式。（１０分） 六、设是到的关系，是到的关系，证明：（8分） 七、设是一个等价关系，设对某一个,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为 ( }},{{φφ)。 (２) 写出)()(R P Q P →∧∨的对偶式（ )()(R P Q P ∧?∨∧ ）。 （３）设A 是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（我校本科生的班级数 ），同学小王所在 的等价类为（小王所在的班的集合）。 （４）设},,,{},,,{><><==3121321R A 是A 上的关系，则R 满足下列性质的哪 几条：自反的，对称的，传递的，反自反的，反对称的。 （ 传递的，反自反的，反对称的 ） (5)写出命题公式Q P ?的两种等价公式( )()()()(P Q Q P P Q Q P ∨?∧∨?→∧→）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （３）（１）仅当今晚有时间，我去看电影。 《离散数学》期末复习题 一、填空题（每空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、设大学《离散数学》期末考试试卷及答案-(1)
离散数学期末试卷(A)
离散数学期末试卷
离散数学期末考试试题(有几套带答案)
浙江师范大学离散数学期末试卷A
大学《离散数学》期末考试试卷及答案-(1)
离散数学期末试卷A卷汇总
离散数学期末试卷
华南农业大学 离散数学 期末考试2013试卷及答案
北方工业大学离散数学期末试卷B
最新南昌大学_离散数学_期末试卷
北京理工大学数学专业离散数学期末试题
山东大学离散数学期末试题答案
离散数学期末考试试卷(A卷)
中国石油大学大学《离散数学》期末复习题及答案
- 大学《离散数学》期末考试试卷及答案-(1)
- 厦大离散数学期末试卷2015试题+完整答案(最新)
- 安徽大学期末试卷离散数学上卷及参考答案.doc
- 离散数学期末试卷及部分答案
- 离散数学期末考试试题(有几套带答案)
- 北方工业大学离散数学期末试卷B
- 山东大学离散数学期末试题答案
- 2012年北京语言大学离散数学期末考试A卷真题附答案
- 大学《离散数学》期末考试试卷及答案-(1)
- 苏州大学离散数学期末试卷
- 最新南昌大学_离散数学_期末试卷
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学期末试卷A卷及答案
- 最新离散数学期末试卷A卷
- 离散数学期末试卷
- 华南农业大学 离散数学 期末考试2013试卷及答案
- 离散数学期末试卷A卷及答案
- 离散数学期末试卷A卷汇总
- 国家开放大学电大本科《离散数学》期末试题标准题库及答案
- 大学《离散数学》期末考试试卷及答案-(1)