第1讲-------离散数学.ppt

1,第一部分数理逻辑,数理逻辑(MathematicalLogic)又称符号逻辑(SymbolicLogic)是用数学方法来研究推理的形式结构和推理规律的数学学科。与计算机科学、人工智能、语言学等有密切的联系。有证明论、模型论、递归论、集合论四大分支本课程介绍数理逻辑最基本的内容：逻辑演算中的命题逻辑和一阶逻辑,2,简单历史三个阶段（一）,1、初始阶段：1660年代19世纪末将数学应用于逻辑Aristotle：形式逻辑（主词和谓词逻辑）。Leibniz：建立直观而又精确的思维演算。遇有争论，双方可以拿起笔来说：让我们来算一下。GeorgeBoole:逻辑代数。DeMorgan:关系逻辑。1王宪钧，数理逻辑引论，北京大学出版社，1982。,3,简单历史三个阶段（二）,2、过度阶段：19世纪末1940前后逻辑应用于数学非欧几何与公理化方法。微积分与实数理论，Piano算术。集合论与数学基础(1900年世界数学家大会)悖论与第三次数学危机，Hilbert计划。,4,简单历史三个阶段（三）,3、成熟阶段：1930s1970年成为数学的独立分支Gdel完全性定理和不完全性定理。四个分支：公理集合论：大基数，连续统问题递归论（可计算性理论）：Turing机，不可解性模型论：实数的非标准模型证明论：超穷归纳法,Gentzen的数论和谐性证明,5,与计算机科学的联系,布尔电路：香弄Shanon是第一人。计算理论：可计算性，Turing机，形式语言，自动机，计算复杂性。程序语义与验证技术.Intelbug:5亿美元。程序的自动生成与转换。SQL:本质上等价于一阶逻辑。Prolog语言以逻辑演算为基础LISP语言以演算为基础人工智能：非单调推理，缺省推理。信息安全等,6,用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。D.E.Knuth,D.E.Knuth的话,7,Dijkstra的话,我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道要是我能年轻20岁的话我要回去学逻辑。1钱学森，关于思维科学的研究，思维科学，第3卷，1987。2M.Y.Vardi,ABriefHistoryofLogic,2003.,8,第1章命题逻辑,命题演算或命题逻辑（Propositionalcalculusorpropositionallogic）符号化精确化,9,命题逻辑,逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位。数理逻辑中最基本、最简单的部分。,10,第1章主要内容,命题与联结词命题公式、真值表重言式、逻辑等值式对偶与范式推理理论与形式结构,11,什么是命题(proposition),命题：真假值唯一确定的陈述句。地球围绕太阳转。2+2=5。多冷啊！关上门吧！你去锻炼身体了吗？火星上有生命。x+1=3。这句话是假的。,12,更多命题,(1)13不是偶数。(2)13是偶数也是奇数。(3)他一边走路一边唱歌。(4)她或许数学成绩好，或许英语成绩好。(5)开往烟台的K285次火车三点或四点出发。(6)如果你努力学习，那么就可以得奖学金。(7)只要不下雨，我就骑自行车上班。(8)只有不下雨，我才骑自行车上班。(9)两圆的面积相等当且仅当它们的半径相等。,13,常用的联结词(connective),与，并且，而且，也或，要么要么非，不如果就，当，只有才，除非不，若则，当且仅当,14,复合命题,1854年英国数学家GeorgeBoole(1815-1864)ThelawsofThought,15,什么是命题(续),原子(atomic)命题：又称简单(simple)命题：不含联结词的命题。复合(compound)命题：含联结词的命题。我痛但快乐着。如果天气好，我就去锻炼。老王或老李中的一个人去出差，当且仅当不是他们都去或者都不去。,2020/6/10,命题逻辑,16,命题符号化,原子命题：p,q,r,p1,q1,r1,联结词：合取联结词：析取联结词：否定联结词：蕴涵联结词：等价联结词：逻辑真值：0，1或F，T,17,否定联结词,定义1设p为一个命题,复合命题“非p”称为p的否定式，记为p，“”称为否定联结词.“p”为真当且仅当p为假。若p代表“13是偶数”，则(1)可表示为p.,2020/6/10,回顾,18,命题符号化（举例）,(1)13不是偶数。解：p:13是偶数。p:13不是偶数.,19,合取联结词,定义2设p、q为两个命题，复合命题“p而且q”称为p、q的合取式，记为pq，“”称作合取联结词。pq真当且仅当p与q同时真.,2020/6/10,回顾,20,命题符号化（举例）,(2)13是偶数也是奇数。pqp：13是偶数.q：13是奇数.(3)他一边走路一边唱歌。pqp：他走路.q：他唱歌.,21,析取联结词,定义3设p、q为两个命题，复合命题“p或者q”称为p、q的析取式，记为pq，“”称作析取联结词。pq为真当且仅当p与q中至少有一个为真.,2020/6/10,回顾,22,命题符号化（举例）,(4)她或许数学成绩好，或许英语成绩好。pqp：她数学成绩好.q：她英语成绩好.(5)开往烟台的K285次火车三点或四点出发。(pq)(pq)p：开往烟台的K285次火车三点出发.q：开往烟台的K285次火车四点出发.,23,蕴涵联结词,定义4设p、q为命题,复合命题“如果p,则q”称为p对q的蕴涵式，记作pq,其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“”称为蕴涵联结词。“pq”假当且仅当p真而q假.,2020/6/10,回顾,24,命题符号化（举例）,(6)如果你努力学习，那么就可以得奖学金。pqp：你努力学习.q：你可以得奖学金.(7)只要不下雨，我就骑自行车上班。pq(8)只有不下雨，我才骑自行车上班。qpp：下雨.q：我骑自行车上班.,25,命题符号化（举例）,解：p：天气好；q：我去锻炼；,例：仅当天气好，我才去锻炼。,注意！,原命题符号化结果是：qp,类比：当天气好，我就去锻炼。当且仅当天气好，我才去锻炼。,26,等价联结词,定义5设p、q为命题,复合命题“p当且仅当q”称作p、q的等价式,记作pq,“”称作等价联结词。pq真当且仅当p、q同时为真或同时为假.,2020/6/10,回顾,27,示例,(9)两个圆的面积相等当且仅当它们的半径相等。pqp：两个圆的面积相等.q：两个圆的半径相等.,28,说明,上述五个联结词来源于日常使用的相应词汇，但并不完全一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能根据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“”。有些词含义不同，但也可表示为这五个联结词，如“但是”也可表示为“”。以后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容.,29,常用的联结词(connective),合取(conjunction)：与，并且，而且，也析取(disjunction)：或，要么要么否定(negation)：非，不蕴涵(conditional)：如果就，当，只有才，除非不，若则，等价(biconditional)：当且仅当,30,命题符号化,原子命题：p,q,r,p1,q1,r1,联结词：合取联结词：析取联结词：否定联结词：蕴涵联结词：等价联结词：逻辑真值：0，1或F，T,31,命