第1讲离散数学优秀PPT.ppt

《第1讲离散数学优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第1讲离散数学优秀PPT.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1讲离散数学现在学习的是第1页，共34页2简单历史三个阶段（一）1、初始阶段：1660年代19世纪末将数学应用于逻辑nAristotle：形式逻辑（主词和谓词逻辑）。nLeibniz：建立直观而又精确的思维演算。遇有争论，双方可以拿起笔来说：让我们来算一下。nGeorge Boole:逻辑代数。nDe Morgan:关系逻辑。1 王宪钧，数理逻辑引论，北京大学出版社，1982。现在学习的是第2页，共34页3简单历史三个阶段（二）2、过度阶段：19世纪末 1940前后逻辑应用于数学n非欧几何与公理化方法。n微积分与实数理论，Piano算术。n集合论与数学基础(1900年世界数学家大会)n悖论与

2、第三次数学危机，Hilbert计划。现在学习的是第3页，共34页4简单历史三个阶段（三）3、成熟阶段：1930s 1970年成为数学的独立分支Gdel完全性定理和不完全性定理。四个分支：n公理集合论：大基数，连续统问题n递归论（可计算性理论）：Turing机，不可解性n模型论：实数的非标准模型n证明论：超穷归纳法,Gentzen的数论和谐性证明现在学习的是第4页，共34页5与计算机科学的联系n布尔电路：香弄Shanon是第一人。n计算理论：可计算性，Turing机，形式语言，自动机，计算复杂性。n程序语义与验证技术.Intel bug:5亿美元。n程序的自动生成与转换。nSQL:本质上等价于一

3、阶逻辑。nProlog语言以逻辑演算为基础nLISP语言以演算为基础n人工智能：非单调推理，缺省推理。n信息安全等n现在学习的是第5页，共34页6用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。D.E.KnuthD.E.Knuth的话现在学习的是第6页，共34页7Dijkstra的话我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道要是我能年轻20岁的话我要回去学逻辑。n1 钱学森，关于思维科学的研究，思维科学，第3卷，1987。n2 M.Y.Va

4、rdi,A Brief History of Logic,2003.现在学习的是第7页，共34页8第1章 命题逻辑n命题演算或命题逻辑（Propositional calculus or propositional logic）n符号化n精确化现在学习的是第8页，共34页9命题逻辑n逻辑主要研究推理过程，而推理过程必须依靠命题来表达。n在命题逻辑中，“命题”被看作最小单位。n数理逻辑中最基本、最简单的部分。现在学习的是第9页，共34页10第1章 主要内容n 命题与联结词n 命题公式、真值表n 重言式、逻辑等值式n 对偶与范式n 推理理论与形式结构现在学习的是第10页，共34页11 什么是命题(

5、proposition)n命题：真假值唯一确定的陈述句。n地球围绕太阳转。n2+2=5。n多冷啊！关上门吧！n你去锻炼身体了吗？n火星上有生命。nx+1=3。n这句话是假的。现在学习的是第11页，共34页12更多命题(1)13不是偶数。(2)13是偶数也是奇数。(3)他一边走路一边唱歌。(4)她或许数学成绩好，或许英语成绩好。(5)开往烟台的K285次火车三点或四点出发。(6)如果你努力学习，那么就可以得奖学金。(7)只要不下雨，我就骑自行车上班。(8)只有不下雨，我才骑自行车上班。(9)两圆的面积相等当且仅当它们的半径相等。现在学习的是第12页，共34页13常用的联结词(connective

6、)n与，并且，而且，也n或，要么要么n非，不n如果就，当，只有才，除非不，若则，n当且仅当现在学习的是第13页，共34页14复合命题n1854年n英国数学家 George Boole(1815-1864)nThe laws of Thought现在学习的是第14页，共34页15 什么是命题(续)n原子(atomic)命题：又称简单(simple)命题：不含联结词的命题。n复合(compound)命题：含联结词的命题。n我痛但快乐着。n如果天气好，我就去锻炼。n老王或老李中的一个人去出差，当且仅当不是他们都去或者都不去。现在学习的是第15页，共34页2022/12/5命题逻辑16命题符号化n原子

7、命题：p,q,r,p1,q1,r1,n联结词：n合取联结词：n析取联结词：n否定联结词：n蕴涵联结词：n等价联结词：n逻辑真值：0，1 或 F，T现在学习的是第16页，共34页17否定联结词n定义1 设p为一个命题,复合命题“非p”称为p的否定式，记为p，“”称为否定联结词.“p”为真当且仅当p为假。n 若p代表“13是偶数”，n则(1)可表示为p.pp0110现在学习的是第17页，共34页2022/12/5回顾18命题符号化（举例）n(1)13不是偶数。解：p:13是偶数。p:13不是偶数.现在学习的是第18页，共34页19合取联结词n定义2 设p、q为两个命题，复合命题“p而且q”称为p、

8、q的合取式，记为pq，“”称作合取联 结词。pq真当且仅当p与q同时真.pqpq000010100111现在学习的是第19页，共34页2022/12/5回顾20命题符号化（举例）n(2)13是偶数也是奇数。pq p：13是偶数.q：13是奇数.n(3)他一边走路一边唱歌。pq p：他走路.q：他唱歌.现在学习的是第20页，共34页21析取联结词n定义3 设p、q为两个命题，复合命题“p或者q”称为p、q的析取式，记为pq，“”称作析取联结词。p q为真当且仅当p与q中至少有一个为真.pqp q000011101111现在学习的是第21页，共34页2022/12/5回顾22命题符号化（举例）n(

9、4)她或许数学成绩好，或许英语成绩好。pq p：她数学成绩好.q：她英语成绩好.n(5)开往烟台的K285次火车三点或四点出发。(pq)(pq)p：开往烟台的K285次火车三点出发.q：开往烟台的K285次火车四点出发.现在学习的是第22页，共34页23蕴涵联结词n定义4 设p、q为命题,复合命题“如果p,则q”称为p对q的蕴涵式，记作p q,其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“”称为蕴涵联结词。“p q”假当且仅当p真而q假.pqp q001011100111现在学习的是第23页，共34页2022/12/5回顾24命题符号化（举例）n(6)如果你努力学习，那么就可以得奖学金。

10、pq p：你努力学习.q：你可以得奖学金.n(7)只要不下雨，我就骑自行车上班。pqn(8)只有不下雨，我才骑自行车上班。qp p：下雨.q：我骑自行车上班.现在学习的是第24页，共34页25命题符号化（举例）解：p：天气好；q：我去锻炼；n例：仅当天气好，我才去锻炼。注意！原命题符号化结果是：q p类比：当天气好，我就去锻炼。当且仅当天气好，我才去锻炼。现在学习的是第25页，共34页26等价联结词n定义5 设p、q为命题,复合命题“p当且仅当q”称作p、q的等价式,记作pq,“”称作等价联结词。npq真当且仅当p、q同时为真或同时为假.pqpq001010100111现在学习的是第26页，共

11、34页2022/12/5回顾27示例n(9)两个圆的面积相等当且仅当它们的半径相等。pq p：两个圆的面积相等.q：两个圆的半径相等.现在学习的是第27页，共34页28说明n上述五个联结词来源于日常使用的相应词汇，但并不完全一致，在使用时要注意：n以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能根据日常语言的含义去理解。n 不能“对号入座”，如见到“或”就表示为“”。n有些词含义不同，但也可表示为这五个联结词，如“但是”也可表示为“”。n 以后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容.现在学习的是第28页，共34页29常用的联结词(connective)n合取

12、(conjunction)：与，并且，而且，也n析取(disjunction)：或，要么要么n否定(negation)：非，不n蕴涵(conditional)：如果就，当，只有才，除非不，若则，n等价(biconditional)：当且仅当现在学习的是第29页，共34页30命题符号化n原子命题：p,q,r,p1,q1,r1,n联结词：n合取联结词：n析取联结词：n否定联结词：n蕴涵联结词：n等价联结词：n逻辑真值：0，1 或 F，T现在学习的是第30页，共34页31命题符号化（举例、续）n例：老王或老李中的一个人去出差，当且仅当不是他们都去或者都不去。解：p：老王去出差；q：老李去出差；原命题符号化结果是：(pq)(pq )(pq)(pq)现在学习的是第31页，共34页32联结词集n，n一元联结词n二元联结词，现在学习的是第32页，共34页33联结词优先级n，现在学习的是第33页，共34页34作业：nP13 习题一1、2(选三个)、6、7n注：要求注明各命题符号表示的命题现在学习的是第34页，共34页