离散数学期末考试

第第1页共2页淮阴工学院课程专业: 计科、计算机、软件 课程名称: 离散数学 学分: 3 试卷编号(A)3（10分）--课程编号-

4111460 考试方式: 闭 卷

考试时间: 100 分钟-:--得分统表:--题 号得 分号线

拟卷日期: 2009-12-20 审核人:一 二 总 分-学- 一、证明下列各题（本题共4小题，满分45分） 得分 1（10分）证明等值式：pq(pqpqpq)名订姓-姓-- 4（15分） S,级- 2（10分证明：如果f:AB,g:BC都是双射的，则f班-班装

g:AC也是双射的。淮阴工学院课程- 二、计算或简答题（本题共4小题，满分55分） 得分 3(20分 1（10分）试求下列公式的主析取范式和主合取范式：(PQ(PQ)号-号线学

求G点和桥（求G名订 4（15分）姓-姓 2（10分）-级-

R1,2,1,3,2,2,2,4,3,2

们去圆明园班-- (1)R(2)R(3)R;(4)(5)R班-装专业:淮阴工学院课程- 一、证明下列各题（445分-- 1、左边(pp)（pq)(qp)(q) （pq)(q) 分） （pq)(p) 分右边

5分）

(a,baaa,b而aa- 2（1）先证明

gAC是满射的。任取cC,则bB使得g(bc又

-号线学- 使得F(a)=b.于是，有

f （a)g(f(agb)cf g:AC是满射的（

分） 0,0 a,b-- （2）再证明--

g：AC是单射的。假设x,x1 2

使得f g(x1

)f g(x),2

因此，即g(f(x）＝g(f(x）。由于f，gx＝（

4分）。- 1 2 1 2名订 最后，姓-f C是双射的（姓--

2分）。

a,b-3

是群，又对任意a,bG，有

综上可- (a b)2a2 b2(a b) (a b)(a a) (b b)二、计算或级- a (b a) ba (a b) b(b a) b(a b) b

1、(P班装b班装

aa 是可交换的，故G,

为Abel.

(P(P-必要性：G, 为Abel群，自然G, 是群；又对任意a,bG，有--

(P-- (a b)2(a (a a)

(a b)(b b)a2

(b a) ba (a b) bb2……5

(P主析取范式-4、首先证明是可结合的，任给a,b,c,d,f S，有：

2RR-R分-

淮阴工学院课程-- R R分3（）a,,d,d是割点--

5分。-

边割个,e,e ,e,e ,e,e ,e,

,ee ,ee e

13分。- 5 1 3号线

2 4 1 2

2 3 3 4

1 4 5学- （2）2分p q r s4-

：今天是星期六,

：我们要去颐和园玩，

:我们去圆明园玩，

：颐和园游-人多……3分

p(qr),sq,p,

……2分订名- 结论：r……2分订姓-- 证明：q (2)s (3)q (4)p (5)p(qr) (6)qr (7)r……8分姓班-班装第第10页共2页《离散数学》期末复习提要一、命题逻辑[复习知识点]1、命题与联结词（否定、析取、合取、条件、等值，复合命题2、命题公式与赋值（成真、成假，真值表，公式类型（重言、矛盾、可满足本等值式3、命题公式之间的关系：蕴含、等价4、析取范式、合取范式，极小（大）项，主析取范式、主合取范式5、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）6、命题逻辑的推理理论：真值表法、直接证明法、间接证明法本章重点内容：命题与联结词、公式与解释（主）析取范式与（主）型的判定、命题逻辑的推理[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。P规则、T规则、附加前提证明法、CP规则[疑难解析]1、公式类型的判定是真值表法，二是等值演算法。2、范式确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补（律，结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。3、逻辑推理掌握逻辑推理时，要理解并掌握12个（3种证明法（明法、附加前提证明法和归谬法。二、谓词逻辑（一阶逻辑）[复习知识点]1（3要素、个体域、变元（约束出现与自由出现）2、谓词公式与解释，谓词公式的类型（永真、永假、可满足）3（（换规则、换名规则和代替规则）4、谓词推理理论本章重点内容：谓词与量词、公式与解释、谓词推理理论（US/UG、ES/EG规则）[复习要求]1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。[疑难解析]1、谓词与量词与改名规则（即换名规则和代替规则。2、公式与解释入公式，求出真值。三、集 合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及其运算律（律、德摩根律等，文氏Ven）图本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。[复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。[疑难解析]1、集合的概念重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。2、集合恒等式的证明对集合恒等式证明的练习，加深对集合性质的理解与掌握。四、二元关系[复习知识点]1、序偶、迪卡尔积，迪卡尔积的运算。2、关系表达式、关系矩阵与关系图3、复合关系（右复合）与逆关系4、关系的性质（自反性、反自反性、对称性、反对称性、传递性）5、关系的闭包（自反闭包、对称闭包、传递闭包）6、等价关系与等价类7、偏序关系与哈斯图、极大/小元、最大/小元8、函数及其性质（单射、满射、双射）9、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、偏序关系和映射的概念[复习要求]1、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。2、理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。3、掌握求复合关系与逆关系的方法。4、理解关系的性质（自反性、反自反性、对称性、反对称性、传递性，掌握其判别方法（定义、图。5、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。6、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元的求法。7、理解函数概念：函数、函数相等、A到B的函数、复合函数和反函数。8、理解单射、满射、双射等概念，掌握其判别方法。[疑难解析]1、关系的概念熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定递性，同时空关系具有对称性与反对称性，但是不具有自反性。3、关系的闭包7.10和4、偏序关系及偏序集中特殊元素的确定元只能在子集内确定。5、映射的概念与映射种类的判定五、图论[复习知识点]1、图的基本概念：无向图与有向图、顶点与边的关联关系、顶点（边）与顶点（边）之间邻接关系、简单图与多重图、顶点度数（度）与握手定理、图的同构、完全图、子（补）图；2、路与回路、简单（回）路；连通图与非连通图、连通分支、强连通图、单向连通图与弱连通图、点（边）连通度；3、图的矩阵表示：邻接矩阵、关联矩阵、可达矩阵；4（回）（半）欧拉图；哈密尔顿（回）（半）哈密尔顿图；5、无向树、生成树、带权树、最小生成树，基本回路、最小生成树避圈法Kruskal算法；6、有向树、树根、有序树、二叉树、前缀码、最佳前缀码、哈夫曼（Huffman）权图的最优二分树、二叉树的周游（即遍历；本章重点内容：握手定理、特殊图（欧拉图与哈密顿图、无（有）向树哈夫曼树、哈夫曼编码[复习要求]1、理解图的有关概念：图、完全图、子图、母图、生成子图、图的同构等。2、深刻理解握手定理及其推论的内容，并能熟练地应用它们。3、理解图的矩阵表示（关联矩阵、相邻矩阵）和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。45、深刻理解无向树的定义，熟练掌握无向树的主要性质，并能灵活应用它们。6、深刻理解生成树的有关概念与性质；理解基本回路、基本回路系统、用Kruskal算法求权图中最小生成树的方法。7、深刻理解有向树、根树、二叉树和前缀码的有关概念；掌握用霍夫曼（Huffman）算法求带权图的最优二分树，掌握求最佳前缀码方法，二叉树的中序和前序行遍法。考试说明考核方式1、期末笔试为120分钟的闭卷考试，占总评成绩的70％。2、平时成绩根据作业完成情况、半期考成绩、出勤情况和课堂表现确定，占总评成绩30％。各章比数理逻辑30分集合30分 图论40分考题类型单项选择题20分填空题20分证明题、计算题、分析题（包括综合分析）60分大题详细分析命题逻辑自然推理证明，综合分析题或证明题；构造命题的真值表，验证命题之间的关