离散数学 数理逻辑

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

1、上海电力学院离散数学教程2021/9/211前言一、为什么要学习离散数学?2、离散数学:是许多数学分支的总称.主要括：数理逻辑,集合论,代数系统,图论.1、专业的需要:2、对本身素质的训练二、连续数学与离散数学1、连续数学:微积分,微分方程,复变函数等.三.教学方法1)引路2)预习3)作业4)章后总结2021/9/212前言四、参考书五、作业1)《离散数学》耿素云等编著，高教出版社2)《离散数学》何自强等编著，科学出版社如何使用参考书？每章每节后看参考书，然后总结，压缩即：薄厚薄2021/9/213

2、前言离散数学是现代数学的一个重要分支，是学习计算机科学与术的重要第一篇集合论（集合基本概念、关系、无限集）第二篇代数结构（代数系统、群、环、域、格）第三篇图论（图的基本概念以及不同类型的图）第四篇数理逻辑（命题逻辑和谓词逻辑）基础课之一。本课程以集合论、代数结构、数理逻辑、图论的四大部分为主干教学内容,并辅以组合论、数论基础、形式语言与自动机初步等内容。本教案选取课程的主干内容进行组织,包括：2021/9/214第1章命题逻辑数理逻辑是计算机科学的基础理论之一。可分为五大部分：第一篇数理逻辑第一章命题逻

3、辑逻辑演算、集合论、证明论、模型论、递归论。数理逻辑既是数学又是逻辑学：它研究数学中的逻辑问题，用数学方法研究形式逻辑。计算机的硬件，软件，算法及语言都具有数理逻辑的性质。我们在此仅讲授数理逻辑的基础部分——逻辑演算部分。它包括命题演算和（一阶）谓词演算两部分。2021/9/215第1章命题逻辑第一篇数理逻辑第一章命题逻辑1.2联结词1.3命题公式与翻译1.4~1.5命题逻辑的等值演算1.6其它联结词及联结词完备集1.1命题及表示法1.7对偶与析取范式和合取范式(范式)1.8命题逻辑推理理论2021/9

4、/216第2章谓词逻辑2.1谓词的概念与表示第一篇数理逻辑第二章谓词逻辑2.2命题函数与量词2.3~2.4一阶谓词公式2.5一阶谓词演算的等价式与蕴含式2.6一阶谓词前束范式2.7一阶逻辑的推理理论2021/9/2171.1命题及表示法命题逻辑研究的中心问题是推理，即研究推理中的前题和结论之第一篇数理逻辑第一章命题逻辑定义1：命题是能判断真假的陈述句。定义2：真值是陈述句为真或假的这种性质。间的形式关系，而不涉及前题和结论的具体内容。推理的基本单位为命题。注1：上命题必须是陈述句。而疑问句、祈使句和感叹

5、句等不是命题。注2：命题的真值是唯一的，但与我们是否知道它的真值无关。假命题：凡与事实不相符的命题，其真值为假。符号化：用“0”或“F”表示。真命题：凡与事实相符的命题，其真值为真。符号化：用“1”或“T”表示。2021/9/2181.1命题及表示法（1）三角形的三个内角和为180度。第一篇数理逻辑第一章命题逻辑（2）4为素数。例：判断下列语句是否为命题（3）1+101=110（4）你喜欢离散数学吗？（5）这朵花真美啊！（6）x>y（7）我正在说谎。2021/9/2191.1命题及表示第一篇数理逻辑第一

6、章命题逻辑例：(1)P：“雪是黑的”命题符号化：一般用大写字母A，B，…，P，Q，…或带下标的大命题常元与命题变元写字母或数字表示。(2)Q2：“上海是个美丽的城市”(3)：“X+2>8”命题常元：表示具体确定内容的命题。命题变元：表示任意的，没有赋予具体内容的抽象命题。注1：命题变元与命题常元的区别注2：命题变元与命题常元在逻辑演算中处理原则相同。2021/9/21101.2命题联结词第一篇数理逻辑第一章命题逻辑若干个简单命题通过命题联结词而构成的新命题。定义：简单命题（原子命题）不能再分解为更简单的

7、命题。1、否定词“”注：“”为一元运算，否定全部而非部分。2、合取词“”定义：复合命题定义：设P为一个命题，利用“”与P组成复合命题称为P的否命题，记为“P”。读作“非P”，其真值表见表1-1定义：设P和Q为两个命题，由P与Q用二元联结词“”成复合命题，记为“PQ”。读作“P且Q”2021/9/21111.2命题联结词第一篇数理逻辑第一章命题逻辑PQ：例1：P：“李军聪明”，Q：“李军用功”注：内容上无联系的两个命题也可以组成具有确定真值的命题。3：析取词“”定义：设P和Q为两个命题，

8、由P与Q用二元联结词“”组成例1：P：“开关坏了”，Q：“灯炮坏了”：PQ：注：“”表示可兼或。不可兼或不能用“”表示。PQ：“李军聪明且用功”复合命题，记为“PQ”。读作“P或Q”例2：P：“1+11=100”，Q：“熊猫为稀有动物”2021/9/21121.2命题联结词第一篇数理逻辑第一章命题逻辑4、条件“”例2：小李下午去打蓝球或在宿舍玩电脑。定义：设P和Q为两个命题，由P与Q用二元联结词“”组成复合命例1：有位父亲对