离散数学数理逻辑.ppt

《离散数学数理逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学数理逻辑.ppt（227页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学讲义之离散数学讲义之数理逻辑数理逻辑 主讲:邱晓红数理逻辑简介数理逻辑是用数学方法研究形式逻辑的科学。数学方法即符号方法，故数理逻辑又称符号逻辑。包含命题逻辑、谓词逻辑、证明论、模型论、递归函数、公理化集合论、归纳逻辑、模态逻辑、多值逻辑和时态逻辑等内容，与计算机有密切关系。2各知识点关联图3第一部分：数理逻辑第一部分：数理逻辑第一章第一章 命题逻辑命题逻辑1.1 1.1 命题及其表示命题及其表示1.2 1.2 逻辑联结词逻辑联结词1.3 1.3 命题公式与解释命题公式与解释1.4 1.4 真值表与等价公式真值表与等价公式1.5 1.5 命题公式的分类与蕴含式命题公式的分类与蕴含式1.

2、6 1.6 其它逻辑联结词和最小功能其它逻辑联结词和最小功能 完备联结词组完备联结词组1.7 1.7 对偶与范式对偶与范式1.8 1.8 推理理论推理理论习习 题题 一一实验一实验一 真值表的程序计算真值表的程序计算第第2 2章章 谓词逻辑谓词逻辑2.12.1谓词的基本概念谓词的基本概念2.22.2谓词公式与解释谓词公式与解释2.32.3变元的约束变元的约束2.42.4谓词谓词演算的等价式演算的等价式与与蕴蕴含式含式2.52.5谓词谓词公式范式公式范式2.6 2.6 谓词谓词演算的推理理演算的推理理论论习习 题题 二二实验实验二二 命命题逻辑简单题逻辑简单推理系推理系统统第第3 3章章 基于基

3、于归结归结原理的推理原理的推理证证明明*3.13.1谓词谓词公式公式与与子句集子句集3.2 3.2 海伯海伯伦伦（HERBRANDHERBRAND）理）理论论3.3 3.3 归结归结原理原理(RESOLUTION(RESOLUTION METHOD)METHOD)3.4 3.4 归结过归结过程的控制策略程的控制策略习习 题题 三三实验实验三三 归结归结原理的程序原理的程序实现实现4第一章：命题逻辑第一章：命题逻辑 主要内容：主要内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对偶与范式、推理理论。教学要求：教学要求：深刻理解和掌握命题逻辑中的基本概念和基

4、本方法。重点：重点：命题逻辑中的基本概念和基本推理方法 难点：难点：推理理论。实践活动：实践活动：真值表的程序计算 51.1 1.1 命命题题及其表示及其表示定义定义1.1.1 1.1.1 能够判断真假的陈述句称为命题命题（Proposition）。命题的判断结果称为命题的真值真值，常用T(True)（或1）表示真真，F(False)（或0）表示假假。真值为真的命题称为真命题真命题，真值为假的命题称为假命题假命题。判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。67解解 在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述

5、句，但（5）没有确定的真值，其真假随x、y取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。（1）、（3）、（7）、（8）、（10）都是命题，其中（10）虽然现在无法判断真假，但随着科技的进步是可以判定真假的。需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例的（8）1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题 8命题分类命题标识符命题标识符 根据命题的结构形式，命题分为原子命题和复合命题。定义定义1.1.2 1.1.2 不能被分解为

6、更简单的陈述语句的命题称为原子命题原子命题(Simple Proposition)。由两个或两个以上原子命题组合而成的命题称为复合命题复合命题(Compound Proposition)。定义定义1.1.3 1.1.3 表示原子命题的符号称为命题标识命题标识符符(Identifier)。命题标识符依据表示命题的情况，分为命题命题常元常元和命题变元命题变元。91.2 1.2 逻辑联结词逻辑联结词一个复合命题，不论其构成多么复杂，一般都可以分析出构成该命题的原子命题。下面介绍5种常用的逻辑联结词逻辑联结词(Logical Connectives)，分别是“非”（否定联结词否定联结词）、“与”（合取

7、联结词合取联结词）、“或”（析取联析取联结词结词）、“若则”（条件联结词条件联结词）、“当且仅当”（双条件联结词双条件联结词），通过这些联结词可以把多个原子命题复合成一个复合命题。10否定联结词 11合取合取联结词联结词12析取析取联结词联结词13条条件件联结词联结词141.2.5 1.2.5 双条双条件件联结词联结词15字位运算与布尔检索 16171.3 1.3 命命题题公式公式与与解解释释上一节介绍了5种常用的逻辑联结词，利用这些逻辑联结词可将具体的命题表示成符号化的形式。对于较为复杂的命题，需要由这5种逻辑联结词经过各种相互组合以得到其符号化的形式，那么怎样的组合形式才是正确的、符合逻辑

8、的表示形式呢？18命命题题公式公式19命题的符号化 20命题的符号化范例211.4 1.4 真值真值表表与与等价公式等价公式22真值表 23真值表范例2425等价公式等价公式2627真值真值表法表法2812组常用的等价公式 29等等值值演算法演算法303132333435361.5 1.5 命命题题公式的分公式的分类与蕴类与蕴含式含式373839蕴蕴含式含式4041真值真值表法表法42等等值值演算法演算法43分析法分析法441.6 1.6 其其它逻辑联结词它逻辑联结词和最小功能完和最小功能完备联结词组备联结词组45461.6.1.2 1.6.1.2 与与非非联结词联结词(Nand)()(Nan

9、d)()471.6.1.3 1.6.1.3 或非或非联结词联结词(Nor)(Nor)（）（）4849最小功能完最小功能完备联结词组备联结词组50联结词联结词的的逻辑电逻辑电路表示路表示5152531.7 1.7 对对偶偶与与范式范式541.7.1.2 1.7.1.2 对对偶原理偶原理(Duality Principle)(Duality Principle)5556命命题题公式的范式公式的范式57581.7.2.2 1.7.2.2 析取范式析取范式与与合取范式合取范式59求公式范式的步骤 60611.7.2.3 1.7.2.3 范式的范式的应应用用62命命题题公式的主析取范式和主合取范式公式的

10、主析取范式和主合取范式6364656667（2 2）等值演算法）等值演算法686970717273（2 2）等值演算法）等值演算法 74751.7.3.3 1.7.3.3 主析取范式和主合取范式主析取范式和主合取范式关关系系7677781.7.3.4 1.7.3.4 主范式的主范式的应应用用79(2)(2)命命题题公式公式类类型的判定型的判定8081（3 3）解决实际问题解决实际问题821.8 1.8 推理理推理理论论 8384直接直接证证法法8586878889间间接接证证法法90归谬归谬法法91习题课9293提示：94提示：95提示：9697解 9899答案：100101102103解答1

11、04105106107108109110解 111112113114证明 115116实验一实验一 真值表的程序计算真值表的程序计算117118第二章：谓词逻辑第二章：谓词逻辑 主要内容：主要内容：谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。教学要求：教学要求：深刻理解和掌握谓词逻辑的基本概念和基本推理方法。重点：重点：谓词逻辑中的基本概念和基本推理方法 难点：难点：谓词演算的推理理论。实践活动：实践活动：命题逻辑简单推理系统 1191202.12.1谓词谓词的基本的基本概概念念121122123124量量词词12512

12、62.22.2谓词谓词公式公式与与解解释释127谓词谓词公式的解公式的解释释1281292.32.3变变元的元的约约束束130131132换换名名规则规则133134代替代替规则规则1352.42.4谓词谓词演算的等价式演算的等价式与蕴与蕴含式含式136137138谓词谓词公式的分公式的分类类139140141142谓词谓词演算的等价式演算的等价式1432.4.3.1 2.4.3.1 量量词词的消去的消去1441452.4.3.2 2.4.3.2 量量词与词与“”“”之之间间的的关关系系1462.4.3.3 2.4.3.3 量量词词作用域的作用域的扩张与扩张与收收缩缩1471482.4.3.4

13、 2.4.3.4 量量词与词与命命题联结词题联结词之之间间的一些的一些等价式等价式149谓词谓词演算的演算的蕴蕴含式含式1501511522.52.5谓词谓词公式范式公式范式 153154155156157斯柯林范式斯柯林范式1582.6 2.6 谓词谓词演算的推理理演算的推理理论论159规则规则（全（全称称指定指定规则规则）（）（Universal Universal SpecificationSpecification）160（全（全称称推广推广规则规则）（）（Universal Universal GeneralizationGeneralization）161（存在指定（存在指定规则规

14、则）（）（Existential Existential SpecificationSpecification）162（存在推广（存在推广规则规则）（）（Existential Existential GeneralizationGeneralization）163164165166167习题课168169解 170171解 172173174175176177178179解180181 证明：182实验二实验二 命题逻辑简单推理系统命题逻辑简单推理系统183184185186187第三章：第三章：基于归结原理的推理证明基于归结原理的推理证明 主要内容：主要内容：谓词公式与子句集的概念,斯柯林

15、(Skolem)标准范式及其求取过程,海伯伦（Herbrand）理论的H域及其解释,置换与合一,命题和谓词归结原理,归结过程的控制策略。教学要求：教学要求：深刻理解和掌握归结原理的基本概念和基本归结过程。重点：重点：归结原理的基本概念和基本归结方法 难点：难点：归结原理的实现方法。实践活动：实践活动：归结原理的程序实现 188第第3 3章章 基于归结原理的推理证明基于归结原理的推理证明*1893.13.1谓词谓词公式公式与与子句集子句集 1903.1.1.2 3.1.1.2 斯柯林斯柯林(Skolem)(Skolem)标标准范式准范式191192193194子句子句与与子句集子句集195不可不

16、可满满足意足意义义下的一致性下的一致性1963.1.4 3.1.4 P PP1P1P2P2PnPn的子句集的子句集1973.2 3.2 海伯海伯伦伦（HerbrandHerbrand）理）理论论198199原子集原子集2003.2.3 3.2.3 H H域上的解域上的解释释2012023.3 3.3 归结归结原理原理(Resolution Method)(Resolution Method)2033.3.1.2 3.3.1.2 置置换换的合成的合成204置置换结换结合律合律205最一般合一置最一般合一置换换的求取算法的求取算法206命命题逻辑题逻辑中的中的归结归结原理原理207归结归结推理推理过过程程208一一阶谓词逻辑阶谓词逻辑中的中的归结归结原理原理209210211212归结归结原理的完原理的完备备性性213利用利用归结归结原理原理进进行定理行定理证证明明214215应应用用归结归结原理原理进进行行问题问题求解求解2162172182193.4 3.4 归结过归结过程的控制策略程的控制策略 220(2)(2)控制策略的分控制策略的分类类221归结归结控制策略及其控制策略及其应应用用举举例例222223224225实验三实验三 归结原理的程序实现归结原理的程序实现226227