当前位置：文档库 › 离散数学期末复习指导

离散数学期末复习指导

离散数学期末复习指导（专科）

山东广播电视大学计算机与通信学院

2008年6月

离散数学是中央电大计算机应用专业信息管理方向开设的必修统设课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使所学的知识达到必需、够用，更加适合大学专科层次的教育。目前该课程没有新教材，借用原教材。使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。

离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。

课程的主要内容

本课程分为三部分：集合论、数理逻辑和图论。

1、集合论部分（集合的基本概念和运算、关系及其性质）；

2、数理逻辑部分（命题逻辑、谓词逻辑）；

3、图论部分（图的基本概念、树及其性质）。

学习建议

离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。

一、各章复习示例与解析

第一章集合

例1，将“大于3而小于或等于7的整数集合”用集合表示出来。

[解析]

集合的表示方法一般有两种，一种称为列举法，一种称为描述法。

列举法将集合的元素按任意顺序逐一列在花括号内，并用逗号分开。“大于3而小于或等于7的整数”有4、5、6、7，用列举法表示为{4、5、6、7}；

描述法是利用集合中的元素满足某种条件或性质用文字或符号在花括号内竖线后面表示出来。上例用描述法表示为{x| x∈Z并且3

答：{4、5、6、7}或{x| x∈Z并且3

例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 的关系矩阵为：???????

? ??=10

01010101010101010101R

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 ,,,,,,,,,,,,,,,,,5

4321==

=解：均不是自反的；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 t 1

。

答：r （R 1）= R 1?I 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 12

? 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 的关系矩阵为

?????

? ??=11

01000011000001000001

R 的关系图为（2）因为R 是自反的，反对称的和传递的，所以R 是A 上的半序关系。（A ，R ）为半序集，（A ，R ）的哈斯图如下：

（3）当B={2，3，4，5}，B 的极大元为2，4；极小元为2，5；B 无最大元与最小元；B 也无上界与下界，更无最小上界与最大下界。

4 ? 1

3 ? 2

例6，下列映射中哪些是满射，哪些是单射，哪些是双射？（1）??

?=→是偶数

是奇数n n n N N 2

)(,:11σσ

（2）??

?=→是偶数

是奇数，n n n N 0

)(},10{:22σσ

（3）1|2|)(,:33+=→a a N Z σσ （4）62)(,:44+=→a a R R σσ [解析]

映射的概念与映射种类的判定：映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。答：（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]

因此

()()()()()()

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] 推导法 ()()()()()()()()()()()()()()()()()

()()()()()()()()()()()()()()

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 中的数值代入公式，求出真值。解：

()()()()()()()()()()()()()

()()()()()()()()()()()()()()()()()()()()()()()()

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 ）算法求一棵最优支撑树。

[解析]

权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal ）算法。解：按照Kruskal 给出的在权图中求最优支撑树的算法，可生成下面的最优支撑树：（权和为11）

生成的最优支撑树结果不是唯一的，又如下图（权和为11）也是一种最优支撑树。

v A

例4，一棵树有两个节点度数为2，一个节点度数为3，三个节点度数为4，问它有几个度数为1的节点？

解：我们知道一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。

根据这两点，可知树中各点的度数总和=2?（树中点数-1），设树叶有x个，

于是，2?2+3+3?4+x=2?（2+1+3+x-1）

得x=9。

上例可推广为“一棵树有n2个节点度数为2，n3个节点度数为3，…，n k个节点度数为k，问它有几个度数为1的节点？”请同学们思考。

三、综合练习及参考解答

（一）填空题

1、集合的表示方法有两种：法和法。请把“奇整数集合”表示出

来{ }。

2、A，B是两个集合，A={1，2，3，4}，B={2，3，5}，则B-A= ，ρ（B）

-ρ（A）= ，ρ（B）的元素个数为。

3、设}2,1{

A，则从A到B的所有映射是

。

4、设命题公式)

=，则使公式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 的相邻矩阵为?????

? ??01

1010111000

10001

11010，则G 有（）

。 A.5点，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）计算1

---???R

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）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。

（1）画出R1和R2的关系图；

（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、求命题公式)

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

求)))

x→

?。

(

)

(

10、求下面带权图的最优支撑树，并计算它的权。

（四）证明题

1、证明等价式R

(

∧

)

))

(。

(

∨

(

∧

∨

2、利用形式演绎法证明：}

→

∨蕴涵Q。

→

3、A，B，C为任意的集合，证明：)

(

)

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）

?????

???????=?????

???????=10

00001

1000010,00

100001000101

（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）} 1

--?R

S ={（2，1），（4，3）}

2、解：

R 1和R 2的关系图如下：

R 1的关系图 R 2的关系图

由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。

由于R2不是自反的，所以R2不是等价关系。

3、解：

（1）真值表

（2

因此公式（2）为恒假。

（3

4、解：

?x（F（x）∨G（x））

?（F（-2）∨G（-2））∨（F（3）∨G（3））∨（F（6）∨G（6））

?（1∨0）∨（1∨0）∨（0∨1）

? 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）}

R 的关系图为

关系矩阵???????

? ??=00

000001011111R

7、解：

（A ，≤）的哈斯图为：

a 为A 的极小元，也是最小元； e 为A 的极大元，也是最大元。

8、解：

?（P ∨Q ）?（P ∧Q ） ?（?（P ∨Q ）→（P ∧Q ））∧（（P ∧Q ）→?（P ∨Q ））

?（（P ∨Q ）∨（P ∧Q ））∧（（?P ∨?Q ）∨（?P ∧?Q ））） ?（P ∨Q ）∧（?P ∨?Q ）

上面结果为合取范式。利用∧对∨分配得：（P ∨Q ）∧（?P ∨?Q ）

?（P ∧?P ）∨（P ∧?Q ）∨（Q ∧?P ）∨（Q ∧?Q ） ?（P ∧?Q ）∨（Q ∧?P ）上面结果为析取范式。 9、解：

?x ?y （F （x ，y ）→F （f （x ），f （y ）））

? ?x （（F （x ，2）→F （f （x ），f （2）））∧（F （x ，3）→F （f （x ），f （3）））） ? （F （2，2）→F （f （2），f （2）））∧（F （2，3）→F （f （2），f （3）））∧（F （3，2）→F （f （3），f （2）））∧（F （3，3）→F （f （3），f （3））） ?（0→1）∧（0→1）∧（1→0）∧（1→0）

1 2

3 3

4 ?

5 ?

b d

? 0

10、解：带权图的最优支撑树如下，权和为28。

4 7

8 9

（四）证明题

1、证明：

=∧

∧

∨

∧

∨

∧

∨

∧

∨

∧

∨

∧

∨

∧

))

(

)

(

))

(

)

((

)

((

)

((

)

((

))

(

)

(

)

(

))

(

2、证明：

（1）T

S→规则P

（2）T

?规则P

（3）S

?规则Q，根据（1）、（2）和基本蕴涵式（12）（4）R

S→

?规则P

（5）R规则Q，根据（3）、（4）和基本蕴涵式（11）（6）R

→规则P

（7）P

?规则Q，根据（5）、（6）和基本蕴涵式（12）（8）Q

P∨规则P

（9）Q规则Q，根据（7）、（8）和基本蕴涵式（10）

3、证明：

（A-B）-C=（A?~B）?~C

= A?（~B?~C）

= A?~（B?C）

= A-（B?C）

4、证明：

?x?y（F（x）→G（y））=?x（F（x）→?y G（y））

= ?x（?F（x）∨?y G（y））

= ?x（?F（x））∨?y G（y）

= ??xF（x）∨?y G（y）

= ?xF（x）→?yG（y）

离散数学期末试题

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

离散数学期末试题及答案

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的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).

离散数学第三版课后习题答案

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论

离散数学习题解答习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；

7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}

离散数学期末试卷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人同时选修三门课程。问（１）三门课程都不选的学生有多少？（２）只选修计算机课程的学生有多少？

离散数学习题解答

习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！答：不是命题. （9）吸烟请到吸烟室去！答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1.

（2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化答:列出两种符号化的真值表：

安徽大学期末试卷离散数学上卷及参考答案.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

离散数学期末试题及答案完整版

离散数学期末试题及答案 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的补元( ).

离散数学期末测验试题(有几套带答案1)

离散数学期末测验试题（有几套带答案1)

————————————————————————————————作者: ————————————————————————————————日期: ?

离散数学试题(A卷及答案）一、证明题（10分）１)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ）二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)）五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C）六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={| x,y∈Ｎ∧ｙ=x2｝，R*S=｛｜ｘ,ｙ∈N∧y=x2+1},S＊R={| x,y∈Ｎ∧ｙ=(x+１)2}, 七、若ｆ:A→B和ｇ:B→C是双射，则(gf)－１＝f－1g-1(1０分）。证明：因为ｆ、ｇ是双射,所以ｇf:A→C是双射，所以ｇf有逆函数(gf）-１：C→Ａ。同理可推f-1g－1：Ｃ→Ａ是双射。因为∈ｆ-1g-1?存在ｚ(∈g-1∧∈f∧<ｚ,ｘ>∈g)?∈ｇf?＜x,y＞∈（gf）-1,所以(gf)-1＝f-１g-1。 R{１，２}＝{<1,1＞，<２,4>},S[{1，２}]＝｛１,４}。

离散数学期末试卷及答案

一．判断题（共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．自然数集关于数的加法和乘法构成环。( ) 8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。( ) 9．设A={a,b,c},则A上的关系R={,}是传递的。( ) 10．设A、B、C为任意集合，则A?(B?C)=(A?B)?C。( ) 二、填空题（共10题，每题3分，共30分） 11．设p：天气热。q：他去游泳。则命题“只有天气热，他才去游泳”可符号化为。 12．设M(x)：x是人。S(x)：x到过月球。则命题“有人到过月球”可符号化为。 13．p?q的主合取范式是。 14．完全二部图K r,s（r < s）的边连通度等于。 15．设A={a,b}，,则A上共有个不同的偏序关系。 16．模6加群中，4是阶元。 17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。. 18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度

列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{,}，则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24．求图示带权图中的最小生成树，并计算最小生成树的权。 25．设R*为正实数集，代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。四、证明题（共3小题，共20分） 26 （8分）在自然推理系统P中构造下述推理的证明：前题：p→(q∨r)，?s→?q，p∧?s 结论：r 27 （6分）设是群，H={a| a∈G∧?g∈G，a*g=g*a},则是G的子群 28．（6分）设G是n(≥3)阶m条边、r个面的极大平面图，则r=2n-4。

离散数学课后答案

离散数学课后答案习题一 6.将下列命题符号化。（1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：（1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q

大学《离散数学》期末考试试卷及答案-(1)

安徽大学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 、全真。

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

离散数学试题(Ｂ卷答案１）一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ（(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ）（Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ

（2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C）（x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C）ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ）六、已知R、S是Ｎ上的关系,其定义如下：R={| x,ｙN∧y=ｘ2} R*S＝｛| x，y N∧y＝x２+1} Ｓ*R=｛<ｘ,y>| x,ｙN∧y=(x＋1)２},R{1，２}＝{＜1，1>，＜2，４>｝,Ｓ[{1,2}]={1,4}。七、设Ｒ={<ａ，b>,,＜c，ａ>}，求ｒ(R)、s(Ｒ)和t(Ｒ) （１5分）。解：r(R）=｛,，,,<ｂ,b＞，｝

离散数学期末试卷(A)

离散数学期末试卷(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．满足结

《离散数学》期末考试试题

《离散数学》期末考试试题一、填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化为。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>，则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7．公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。

离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。（2）解：原子命题：我爱北京天安门。复合命题：如果不是练健美操，我就出外旅游拉。（3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解：

离散数学期末复习指导

离散数学期末试题

离散数学期末试题及答案

离散数学第三版课后习题答案

离散数学期末试卷A卷及答案

离散数学习题解答

安徽大学期末试卷离散数学上卷及参考答案.doc

离散数学期末试题及答案完整版

离散数学期末测验试题(有几套带答案1)

离散数学期末试卷及答案

最新离散数学期末考试试题配答案

离散数学课后答案

大学《离散数学》期末考试试卷及答案-(1)

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

最新离散数学习题答案

离散数学期末试卷(A)

《离散数学》期末考试试题

离散数学课后习题答案(左孝凌版)