离散数学期末考试

淮阴工学院课程考试试卷第1页共2页班级姓名学号----------------------------装--------------------------订----------------------线-----------------------------专业:计科、计算机、软件课程名称:离散数学学分:3试卷编号(A)课程编号:4111460考试方式:闭卷考试时间:100分钟拟卷人:拟卷日期:2009-12-20审核人:得分统表:题号一二总分得分1、（10分）证明等值式：()()()()pqpqpqpq2、（10分）证明：如果:,:fABgBC都是双射的，则:fgAC也是双射的。3、（10分）给定群,G，则,G为Abel群222()()(,())ababGabab4、（15分）给定代数结构,S，其中S中元为实数有序对，定义为,,,2abcdacbdbd，试证：,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)3RRRRR3、(20分)无向图G如右图所示,（1）求G的全部点割集和边割集，并指出其中的割点和桥（割边）；（2）求G的点连通度()G和边连通度()G。4、（15分）在自然推理系统P中构造下面推理的证明：如果今天是星期六，我们就到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六。颐和园游人太多。所以我们去圆明园玩。专业:计科、计算机、软件课程名称:离散数学学分:3试卷编号(A)二、计算或简答题：（本题共4小题，满分55分）得分淮阴工学院课程考试试卷第3页共2页班级姓名学号----------------------------装--------------------------订----------------------线-----------------------------一、证明下列各题（本题共4小题，满分45分）1、())()()5pppqqpqq左边＝（（分）)()3pqqp（（分）)()2pqpq（（分）右边2、（1）:,,(),,fgACcCbBgbcaA先证明是满射的。任取则使得又.ab使得F()=于是，有)(()():4fgagfagbcfgAC（）是满射的（分）（2）2,,()(),fgACxxAfgxfgx112再证明：是单射的。假设使得(()(()gfxgfx12即）＝）。4fgxx12由于，都是单射的，＝（分）。2fgAC：是双射的（分）。3、充分性：因为,G是群，又对任意,abG，有222()()()()()ababababaabb()()()()ababaabbbababb5baab……可见，是可交换的，故,G为Abel.必要性：,G为Abel群，自然,G是群；又对任意,abG，有2()()()()()abababababaabb22()()5aabbab……4、首先证明是可结合的，任给,,,,,abcdefS，有：(,,),,2,,22(2),2224abcdefacbdbdefacebdfbdbdbdacebdfbdbfdfbdf而,(,,),,2,22(2),2224,abcdefabcddfdfacebefdfbdfdfacebdfbdbfdfbdf故满足结合律，,S是半群。……7分其次证明有幺元0,0，任给,abS，有0,0,0,020,,,0,00,020,.ababbabababbab因此，0,0是幺元。……5分最后，证明满足交换律，任给,,,abcdS，有,,,2,,abcdacbdbdcdab，故满足见换律。……3分综上可知，,S是可交换独异点。二、计算或简答题：（本题共4小题，满分55分）1、()()()(()())PQPQPQPQQP……2()(()())PQPQQP……2((()()))((()()))PPQPQQPQPQ()()()()PPQPPQQPQPPQ……20()PQM……1主析取范式为123mmm……3分2、11,2,1,32R分2,32,2,2,4,3,22R分淮阴工学院课程考试试卷第4页共2页班级姓名学号----------------------------装--------------------------订----------------------线-----------------------------12,32R分2R分322R分3、（1）2,,,acdd点割集个：是割点5分。513241223341457,,,,,,,,,,,,,eeeeeeeeeeeeee边割集个：是桥13分。（2）＝＝12分4、设p：今天是星期六,q：我们要去颐和园玩，r:我们去圆明园玩，s：颐和园游人多……3分前提：(),,,pqrsqps……2分结论：r……2分证明：(1)(2)(3)(4)(5)()(6)(7)sqsqppqrqrr……8分第5页共2页《离散数学》期末复习提要一、命题逻辑[复习知识点]1、命题与联结词（否定、析取、合取、条件、等值），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、命题公式之间的关系：蕴含、等价4、析取范式、合取范式，极小（大）项，主析取范式、主合取范式5、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）6、命题逻辑的推理理论：真值表法、直接证明法、间接证明法本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。P规则、T规则、附加前提证明法、CP规则[疑难解析]1、公式类型的判定判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。第6页共2页3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。二、谓词逻辑（一阶逻辑）[复习知识点]1、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）2、谓词公式与解释，谓词公式的类型（永真、永假、可满足）3、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩）和置换规则（置换规则、换名规则和代替规则）4、谓词推理理论本章重点内容：谓词与量词、公式与解释、谓词推理理论（US/UG、ES/EG规则）[复习要求]1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。[疑难解析]1、谓词与量词理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则（即换名规则和代替规则）。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释中的数值代入公式，求出真值。三、集合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及其运算律（交换律、结合律、分配律、吸收律、德摩根律等），文氏（Venn）图本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。[复习要求]第7页共2页1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。[疑难解析]1、集合的概念重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。2、集合恒等式的证明对集合恒等式证明的练习，加深对集合性质的理解与掌握。四、二元关系[复习知识点]1、序偶、迪卡尔积，迪卡尔积的运算。2、关系表达式、关系矩阵与关系图3、复合关系（右复合）与逆关系4、关系的性质（自反性、反自反性、对称性、反对称性、传递性）5、关系的闭包（自反闭包、对称闭包、传递闭包）6、等价关系与等价类7、偏序关系与哈斯图、极大/小元、最大/小元8、函数及其性质（单射、满射、双射）9、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、偏序关系和映射的概念[复习要求]1、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。2、理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。3、掌握求复合关系与逆关系的方法。4、理解关系的性质（自反性、反自反性、对称性、反对称性、传递性），掌握其判别方法（定义、图）。5、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。第8页共2页6、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元的求法。7、理解函数概念：函数、函数相等、A到B的函数、复合函数和反函数。8、理解单射、满射、双射等概念，掌握其判别方法。[疑难解析]1、关系的概念熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、偏序关系的基础。对于五种性质的判定，可以依据教材上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。3、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记定理7.10和7.114、偏序关系及偏序集中特殊元素的确定理解与掌握偏序关系与偏序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定。5、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐