离散数学-数理逻辑

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

1、离散数学杨敏yangm@whu.edu.cn武汉大学国际软件学院1教材与参考资料教材：《离散数学》（第2版），屈婉玲、耿素云、张立昂编，清华大学出版社参考资料：《离散数学》，刘玉珍、刘咏梅编，武汉大学出版社《DiscreteMathematicalStructures》(SixthEdition)，BernardKolman,FobertC.BusbyandSharonRoss，高等教育出版社有影印版、译本《DiscreteMathematicsandItsApplications》(SixthEdition)

2、，[美]KennethH.Rosen，机械工业出版社影印版、译本2课程主要内容数理逻辑集合论图论代数系统*3目的、意义和要求研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学内容：第1-7章重点第9、14章备选第8、11章自学第10、12、13章不要求4学习要求1、课堂要求：按时上课认真听讲2、课外要求：复习(每次课后，安排半个小时)认真、按时完成作业(每次课后，安排1个小时)5学习考查方法1、出勤率：10%不定期检查出勤情况2、作业

3、完成情况：10%对作业完成情况进行登记3、课堂测验+期中考试：20%共5次4、期末考试（闭卷）：60%6第一篇数理逻辑第1章导论数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用7（1）定义§1.1数理逻辑的概念数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析符号化研究公式间的关系推导、演算8（2）方法引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。例：A、B、C、D4人做百米竞赛，观众甲

4、、乙、丙预报比赛结果的名次为：甲：C第一，B第二乙：C第二，D第三丙：A第二，D第四比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？1.引入pi,qi,ri,si分别表示“A排名第i，B排名第i，C排名第i，D排名第i”2.给出个命题之间的关系（1）(r1∧┐q2)∨(┐r1∧q2)1（2）(r2∧┐s3)∨(┐r2∧s3)1（3）(p2∧┐s4)∨(┐p2∧s4)13.通过演算规则，得出结果9（3）内容谓词逻辑命题逻辑10（4）分支模型论证明论公理集合论递归论11§1.2数理逻辑的发展简

5、史创立阶段起源阶段完善阶段发展历史12起源阶段德国数学家、哲学家G.Leibniz（1646~1716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。13创立阶段英国数学家G.Bool于1847年发表《逻辑的数学分析》，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。德国数学家G.Frege于1879年在《概念的演算》一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。14完善阶段英国逻辑学家A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了

6、《数学原理》中，使数理逻辑成为了一门专门的学科。20世纪30年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。15§1.3数理逻辑的地位和作用1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计16第2章命题逻辑2.1命题逻辑基本概念2.2命题逻辑等值演算2.3范式2.4命题逻辑推理理论172.1命题逻辑基本概念2.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(¬,

7、,,,)2.2.2命题公式及其分类命题公式及其赋值真值表命题公式的分类18§2.1.1命题与联结词1、命题及相关概念（1）命题的定义两者必居其一且只居其一——二值逻辑命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。命题：一个具有真假意义的陈述句。什么是真值：只包含真/假两个值的量。T/1—真F/0—假19注意：（1）感叹句、祈使句、疑问句都不是命题（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题20中国的首都在北京。1+1=10请开门！x+y

8、=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。例1判断下列个自然语言是否是命题21（2）几个基本概念真命题与假命题命题变元与命题常元真命题:真值为真的命题假命题:真值为假的命题若p即可以表示真命题，又可以表示假命题，则称p为命题变元。T永远表示真命题，F表示假命题，称T和F为命题常元。22例2真命题假命题真值不确定疑问句感叹句祈使句悖论(1),(2),(5)是命题,(3