离散数学期末考试.doc

专业:计科、计算机、软件课程名称:离散数学学分:3试卷编号(A)课程编号:4111460考试方式:闭卷考试时间:100分钟拟卷人: 拟卷日期:2009-12-20审核人: 得分统表: 题号一二总分 得分                      一、证明下列各题(本题共4小题,满分45分)得分    1、(10分)证明等值式:2、(10分)证明:如果都是双射的,则也是双射的。3、(10分)给定群,则为Abel群4、(15分)给定代数结构,其中S中元为实数有序对,定义为,试证:是可交换独异点。二、计算或简答题:(本题共4小题,满分55分)得分    1、(10分)试求下列公式的主析取范式和主合取范式:2、(10分)设,求3、(20分)无向图如右图所示,(1)求的全部点割集和边割集,并指出其中的割点和桥(割边);(2)求的点连通度和边连通度。4、(15分)在自然推理系统P中构造下面推理的证明:如果今天是星期六,我们就到颐和园或圆明园去玩。如果颐和园游人太多,我们就不去颐和园玩。今天是星期六。颐和园游人太多。所以我们去圆明园玩。专业:计科、计算机、软件课程名称:离散数学学分:3试卷编号(A)        一、证明下列各题(本题共4小题,满分45分)1、2、(1)(2)3、充分性:因为是群,又对任意,有可见,是可交换的,:为Abel群,自然是群;又对任意,有4、首先证明是可结合的,任给,有:而故满足结合律,是半群。……7分其次证明有幺元,任给,有因此,是幺元。……5分最后,证明满足交换律,任给,有,故满足见换律。……3分综上可知,是可交换独异点。二、计算或简答题:(本题共4小题,满分55分)1、主析取范式为……3分2、3、(1)(2)4、设:今天是星期六,:我们要去颐和园玩,:我们去圆明园玩,:颐和园游人多……3分前提:……2分结论:……2分   证明:……8分《离散数学》期末复习提要一、命题逻辑[复习知识点]1、命题与联结词(否定、析取、合取、条件、等值),复合命题2、命题公式与赋值(成真、成假),真值表,公式类型(重言、矛盾、可满足),公式的基本等值式3、命题公式之间的关系:蕴含、等价4、析取范式、合取范式,极小(大)项,主析取范式、主合取范式 5、公式类型的判别方法(真值表法、等值演算法、主析取/合取范式法)6、命题逻辑的推理理论:真值表法、直接证明法、间接证明法本章重点内容:命题与联结词、公式与解释、(主)析取范式与(主)合取范式、公式类型的判定、命题逻辑的推理[复习要求]1、理解命题的概念;了解命题联结词的概念;理解用联结词产生复合命题的方法。2、理解公式与赋值的概念;掌握求给定公式真值表的方法,用基本等值式化简其它公式,公式在解释下的真值。3、了解析取(合取)范式的概念;理解极大(小)项的概念和主析取(合取)范式的概念;掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。P规则、T规则、附加前提证明法、CP规则[疑难解析]1、公式类型的判定判定公式的类型,包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种,一是真值表法,二是等值演算法。2、范式求范式,包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点:一是准确理解掌握定义;另一是巧妙使用基本等值式中的分配律、同一律和互补律(排中律、矛盾律),结果的前一步适当使用幂等律,使相同的短语(或子句)只保留一个。3、逻辑推理掌握逻辑推理时,要理解并掌握12个(除第10,11)推理规则和3种证明法(直接证明法、附加前提证明法和归谬法)。二、谓词逻辑(一阶逻辑)[复习知识点] 1、谓词、量词、个体词(一阶逻辑3要素)、个体域、变元(约束出现与自由出现)2、谓词公式与解释,谓词公式的类型(永真、永假、可满足)3、谓词公式的等值式(代换实例、消去量词、量词否定和量词辖域收与扩)和置换规则(置换规则、换名规则和代替规则)4、谓词推理理论本章重点内容:谓词与量词、公式与解释、谓词推理理论(US/UG、ES/EG规则)[复习要求]1、理解谓词、量词、个体词、个体域、变元的概念;理解用谓词、量词、逻辑联结词描述一个简单命题;了解命题符号化。2、理解公式与解释的概念;掌握在有限个体域下消去公式量词,求公式在给定解释下真值的方法;了解谓词公式的类型。[疑难解析]1、谓词与量词理解谓词与量词引入的意义,概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则(即换名规则和代替规则)。2、公式与解释能将一阶逻辑公式表达式中的量词消除,写成与之等价的公式,然后将解释中的数值代入公式,求出真值。