《离散数学期末考试》由会员分享，可在线阅读，更多相关《离散数学期末考试（10页珍藏版）》请在金锄头文库上搜索。
1、淮 阴 工 学 院 课 程 考 试 试 卷第 1 页 共 2 页班级 姓名 学号 -装-订-线-专业:计科、计算机、软件课程名称: 离散数学学分:3试卷编号(A)课程编号:4111460考试方式: 闭 卷考试时间:100分钟拟 卷 人:拟卷日期:2009-12-20 审 核 人:得分统表:题 号一二总 分得 分1、 （10 分）证明等值式：()()()()pqpqpqpq 2、 （10 分）证明：如果都是双射的，则也是双射的。:,:fAB g BC:fg ACo3、 （10 分）给定群，则为 Abel 群,G e,G e222()()( ,()ab a bGababee4、 （15 分）给定代
2、数结构，其中 S 中元为实数有序对，定义为,S ，,2a bc dac bdbd试证：是可交换独异点。,S 一、证明下列各题一、证明下列各题（本题共 4 小题，满分 45 分）得 分淮 阴 工 学 院 课 程 考 试 试 卷第 2 页 共 2 页班级 姓名 学号 -装-订-线-1、 （10 分）试求下列公式的主析取范式和主合取范式：()()PQPQ 2、 （10 分）设，求1,2 , 1,3 , 2,2 , 2,4 , 3,2R (1)1 ; (2)2,3 ; (3)1; (4); (5)3RRRRR3、(20 分)无向图如右图所示, G（1）求的全部点割集和边割集，并指出其中的割G点和桥（割
3、边） ；（2）求的点连通度和边连通度。G( )G( )G4、 （15 分）在自然推理系统 P 中构造下面推理的证明：如果今天是星期六，我们就到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六。颐和园游人太多。所以我们去圆明园玩。专业:计科、计算机、软件课程名称: 离散数学学分:3试卷编号 (A)二、计算或简答题：二、计算或简答题：（本题共 4 小题，满分 55 分）得 分淮 阴 工 学 院 课 程 考 试 试 卷第 3 页 共 2 页班级 姓名 学号 -装-订-线-一、证明下列各题一、证明下列各题（本题共 4 小题，满分 45 分）1、()()()5pppqqpqq L
4、左边（分）)()3pqqp L（分）)()2pqpqL（分）右边2、 （1） :,( ),fg ACcCbBg bcaA o先证明是满射的。任取则使得又.ab使得F( )=于是，有)( ( )( ):4fg ag f ag bcfg AC ooL L（）是满射的（分）（2）2,()(),fgACx xAfg xfg xooo112再证明：是单射的。假设使得( ()( ()g f xg f x12即）。4fgxxL L12由于，都是单射的，（分）。2fgACoL L：是双射的（分）。3、充分性：因为是群，又对任意，有,G e, a bG222()()()()()ababababaabbeeeee
5、eee()()()()ababaabbbababbeeeeeeeeee5baabee 可见，是可交换的，故为 Abel.e,G e必要性：为 Abel 群，自然是群；又对任意，有,G e,G e, a bG2()()()()()abababababaabbeeeeeeeeee22()()5aabbabeeee 4、首先证明是可结合的，任给，有：,a bc de fS(,),2,22(2),2224a bc de fac bdbde face bdfbdbdbdace bdfbdbfdfbdf 而,(,),2,22 (2),2224,a bc de fa bcd dfdface befdfb d
6、fdface bdfbdbfdfbdf 故满足结合律，是半群。7 分,S 其次证明有幺元，任给，有0,0, a bS0,0,0,02 0,0,00,020,.a babba ba babba b 因此，是幺元。5 分0,0最后，证明满足交换律，任给，有,a bc dS，故满足见换律。3 分,2,a bc dac bdbdc da b综上可知，是可交换独异点。,S 二、计算或简答题：计算或简答题：（本题共 4 小题，满分 55 分）1、()()()()()PQPQPQPQQP 2()()()PQPQQP 2()()()()PPQPQQPQPQ ()()()()PPQPPQQPQPPQ 20()P
7、QM 1主析取范式为3 分123mmm2、11,2 , 1,32R L分2,32,2 , 2,4 , 3,22R L分淮 阴 工 学 院 课 程 考 试 试 卷第 4 页 共 2 页班级 姓名 学号 -装-订-线-12,32RL分 2R L分 322RL分3、 （1） 2,a cddL L点割集个：是割点5分。 513241223341457,ee ee ee ee ee ee eeL L边割集个：是桥13分。（2）L L12分4、设：今天是星期六, ：我们要去颐和园玩，:我们去圆明园玩， ：颐和园游pqrs 人多3 分前提：2 分(), ,pqr sq p s 结论： 2 分 r证明：8 分
8、(1)(2)(3)(4)(5)()(6)(7)sqsqppqrqrr 第 5 页 共 2 页离散数学离散数学期末复习提要期末复习提要一、一、 命题逻辑命题逻辑复习知识点1、 命题与联结词（否定、析取、合取、条件、等值） ，复合命题2、 命题公式与赋值（成真、成假） ，真值表，公式类型（重言、矛盾、可满足） ，公式的基本等值式3、 命题公式之间的关系：蕴含、等价4、 析取范式、合取范式，极小（大）项，主析取范式、主合取范式 5、 公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）6、 命题逻辑的推理理论：真值表法、直接证明法、间接证明法本章重点内容：命题与联结词、公式与解释、 （主）
9、析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理复习要求1、 理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、 理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、 了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、 掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、 掌握命题逻辑的推理理论。P 规则、T 规则、附加前提证明法、CP 规则疑难解析1、公式类型的判定判定公式的类型，包括判定公
10、式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律） ，结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。第 6 页 共 2 页3、逻辑推理掌握逻辑推理时，要理解并掌握 12 个（除第 10，11）推理规则和 3 种证明法（直接证明法、附加前提证明法和归谬法） 。二、二、 谓词逻辑（一阶逻辑）谓词逻辑（一阶逻辑）复习知识点 1、 谓词、量词、个体词（一阶逻辑 3 要素） 、个体域、变元（约束
11、出现与自由出现）2、 谓词公式与解释，谓词公式的类型（永真、永假、可满足）3、 谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩）和置换规则（置换规则、换名规则和代替规则）4、 谓词推理理论本章重点内容：谓词与量词、公式与解释、谓词推理理论（US/UG、ES/EG 规则）复习要求1、 理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、 理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。疑难解析1、谓词与量词理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的
12、自由性、约束性与改名规则（即换名规则和代替规则） 。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释中的数值代入公式，求出真值。三、三、 集集 合合复习知识点1、 集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、 集合的交、并、差、补以及对称差等运算及其运算律（交换律、结合律、分配律、吸收律、 德摩根律等） ，文氏（Venn）图本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。复习要求第 7 页 共 2 页1、 理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、 掌握集合的表示法和集合的交、并、差、补、对称
13、差等基本运算。3、 掌握集合运算基本规律，证明集合等式的方法。疑难解析1、集合的概念重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为 2n。2、集合恒等式的证明对集合恒等式证明的练习，加深对集合性质的理解与掌握。四、四、 二元关系二元关系复习知识点1、 序偶、迪卡尔积，迪卡尔积的运算。2、 关系表达式、关系矩阵与关系图3、 复合关系（右复合）与逆关系 4、 关系的性质（自反性、反自反性、对称性、反对称性、传递性） 5、 关系的闭包（自反闭包、对称闭包、传递闭包）6、 等价关系与等价类7、 偏序关系与哈斯图、极大/小元、最大/小元8、 函数及其性质（单射、满射、双射）9、 复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、偏序关系和映射的概念复习要求1、 了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。2、 理解关系
