离散数学 邱晓红 part1

《离散数学 邱晓红 part1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数理逻辑主讲:邱晓红数理逻辑简介数理逻辑是用数学方法研究形式逻辑的科学。数学方法即符号方法，故数理逻辑又称符号逻辑。包含命题逻辑、谓词逻辑、证明论、模型论、递归函数、公理化集合论、归纳逻辑、模态逻辑、多值逻辑和时态逻辑等内容，与计算机有密切关系。2各知识点关联图3第一部分：数理逻辑第一章命题逻辑1.1命题及其表示1.2逻辑联结词1.3命题公式与解释1.4真值表与等价公式1.5命题公式的分类与蕴含式1.6其它逻辑联结词和最小功能完备联结词组1.7对偶与范式1.8推理理论习题一实验一真值表的程序计算第2章谓词逻辑2.1谓词的基本概念2.2谓词公式与解释2.3变元的约束2.4谓

2、词演算的等价式与蕴含式2.5谓词公式范式2.6谓词演算的推理理论习题二实验二命题逻辑简单推理系统第3章基于归结原理的推理证明**3.1谓词公式与子句集3.2海伯伦（HERBRAND）理论3.3归结原理(RESOLUTIONMETHOD)3.4归结过程的控制策略习题三实验三归结原理的程序实现4第一章：命题逻辑主要内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对偶与范式、推理理论。教学要求：深刻理解和掌握命题逻辑中的基本概念和基本方法。重点：命题逻辑中的基本概念和基本推理方法难点：推理理论。实践活动：真值表的程序计算51.1命题及其表

3、示定义1.1.1能够判断真假的陈述句称为命题（Proposition）。命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。67解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题

4、。（1）、（3）、（7）、（8）、（10）都是命题，其中（10）虽然现在无法判断真假，但随着科技的进步是可以判定真假的。需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1的（8）1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题8命题分类命题标识符根据命题的结构形式，命题分为原子命题和复合命题。定义1.1.2不能被分解为更简单的陈述语句的命题称为原子命题(SimpleProposition)。由两个或两个以上原子命题组合而成的命题称为复合命题(CompoundProposition)。定义1.1.

5、3表示原子命题的符号称为命题标识符(Identifier)。命题标识符依据表示命题的情况，分为命题常元和命题变元。91.2逻辑联结词一个复合命题，不论其构成多么复杂，一般都可以分析出构成该命题的原子命题。下面介绍5种常用的逻辑联结词(LogicalConnectives)，分别是“非”（否定联结词）、“与”（合取联结词）、“或”（析取联结词）、“若…则…”（条件联结词）、“…当且仅当…”（双条件联结词），通过这些联结词可以把多个原子命题复合成一个复合命题。101.2.1否定联结词111.2.2合取联结词121.2.3析取联结词131.2.4条件联结词141.2.5双条件联

6、结词151.2.6字位运算与布尔检索16171.3命题公式与解释上一节介绍了5种常用的逻辑联结词，利用这些逻辑联结词可将具体的命题表示成符号化的形式。对于较为复杂的命题，需要由这5种逻辑联结词经过各种相互组合以得到其符号化的形式，那么怎样的组合形式才是正确的、符合逻辑的表示形式呢？181.3.1命题公式191.3.2命题的符号化20命题的符号化范例211.4真值表与等价公式22真值表23真值表范例24251.4.2等价公式26271.4.2.1．真值表法2812组常用的等价公式291.4.2.2．等值演算法303132333435361.5命题公式的分类与蕴含式37383

7、91.5.3蕴含式40411.5.3.1．真值表法421.5.3.2．等值演算法431.5.3.3．分析法441.6其它逻辑联结词和最小功能完备联结词组45461.6.1.2与非联结词(Nand)()471.6.1.3或非联结词(Nor)（）48491.6.2最小功能完备联结词组501.6.3联结词的逻辑电路表示5152531.7对偶与范式541.7.1.2对偶原理(DualityPrinciple)55561.7.2命题公式的范式57581.7.2.2析取范式与合取范式59求公式范式的步骤60611.7.2.3范式的应用62