离散数学考前复习.ppt

第一部分数理逻辑第二部分集合论第三部分图论第四部分抽象代数第一部分数理逻辑第一章命题逻辑第二章一阶谓词逻辑1.1命题和命题联结词1.2命题公式及其赋值1.3等值演算与联结词完备集1.4析取范式与合取范式1.5推理的形式结构1.6自然推理系统P1.命题：能判断真假的陈述句。1.1命题和命题联结词2.命题的真值：判断结果1.1命题和命题联结词原子命题：不能被分解为更简单的陈述句复合命题：原子命题通过联结词联结而成4、命题联结词pp例：1.张晓婧爱唱歌或爱听音乐。2.张晓婧是内蒙人或是陕西人。3.张晓婧只能挑选202或203房间。p注意：①“只要p，就q‘，’因为p，所以q”，“p仅当q”，‘只有q，才p“，”除非q才p“，”除非q，否则非p“都可抽象为p→q。②p，q可以没有任何内在联系。pp例：p：北京比天津人口多q：2＋2＝4r：乌鸦是黑色的5、语句形式化1.1命题和命题联结词命题常元：表示具体确定内容的命题。命题变元：表示不确定具体内容的命题。1.2命题公式及其赋值1.2命题公式及其赋值1.2命题公式及其赋值1.2命题公式及其赋值1.2命题公式及其赋值1.2命题公式及其赋值1.3命题公式的等值式基本等值式（A，B，C为任意命题公式）1.3命题公式的等值式因A，B，C可以代入任意的命题公式，故以上等值式称为等值式模式。等值演算的应用：1.验证等值式2.判定公式的类型3.解决工作生活中的判断问题联结词的完备集联结词的完备集1.4析取范式与合取范式若A为永真式，则A中必同时含有pi和﹁pi，反之亦然。定义：①由有限个简单合取式构成的析取式称为析取范式。②由有限个简单析取式构成的合取式称为合取范式。③析取范式与合取范式称为范式。定理3.任一命题公式都存在与之等值的析取范式和合取范式。定义：在含有n个命题变元的简单合（析）取式中，若每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变元或它的否定是出现在从左算起的第i位上（字典序），称这样的简单合（析）取式为极小（大）项。将极小项的成真赋值对应的二进制数转化为十进制数为i，将对应的极小项记为mi。将极大项的成假赋值对应的二进制数转化为十进制数为i，将对应的极大项记为Mi。1.4析取范式与合取范式1.4析取范式与合取范式1.4析取范式与合取范式例：要在A，B，C中挑选2名出国进修，选派时满足下列条件：①若A去，则C同去②若B去，则C不能去③若C不去，则A或B可以去问有几种选派方案，分别是什么？1.5推理的形式结构1.5推理的形式结构1.5推理的形式结构例：若下午温度超过30度，则王晓燕必去游泳。若她去游泳，她就不会去看电影。所以若王晓燕没去看电影，下午温度必超过了30度。1.5推理的形式结构注意：①以上都是蕴含式模式②若某推理的形式结构与某定律一致，则推理正确③成立的等值式可产生两条定律④推理定律可产生相应的推理规则1.6自然推理系统P1.6自然推理系统P1.6自然推理系统P例：若小王是理科生，则他的数学成绩一定很好。如果小王不是理科生，他一定是文科生。小王的数学成绩不好。所以小王是文科生。例：如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。2.归谬法将结论的否定作为前提引入，能推出矛盾来，则推理正确所有的人总是要死的。苏格拉底是人。所以苏格拉底是要死的。第二章谓词逻辑2.1一阶逻辑命题符号化2.谓词3.量词：个体词之间的数量关系例：所有的人都是要死的。有的人用左手写字。例：在美国留学的学生未必都是亚洲人。有的兔子比所有的乌龟跑的快。对任意的整数x，都存在整数y使得x＋y＝10。2.2一阶逻辑公式及解释2.2一阶逻辑公式及解释合式公式也称谓词公式，简称公式2.2一阶逻辑公式及解释2.2一阶逻辑公式及解释2.2一阶逻辑公式及解释定理.闭式在任何解释下都变成命题。2.2一阶逻辑公式及解释定理.重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。2.3一阶逻辑等值式与置换规则2.3一阶逻辑等值式与置换规则D=N，F(x)：x是奇数G(x)：x是偶数2.3一阶逻辑等值式与置换规则2.3一阶逻辑等值式与置换规则2.4一阶逻辑前束范式定理1：任一谓词公式都可以化成为与之等值的前束范式。2.4一阶逻辑前束范式2.5一阶逻辑的推理理论第四组消去量词和引入量词的推理规则UI规则成立的条件：（1）取代x的y应为任意不在A(x)中约束出现的个体变项；（2）用y取代A(x)中自由出现的x时，必须将所有的自由出现x都取代；（3）自由变元y也可替换为个体域中任意的个体常元c，c为任意不在A(x)中出现过的个体常项。含义：如果个体域的所有个体都具有性质A，则个体域中的任一个个体都具有性质A。ES规则成立的条件：（1