《第1讲离散数学精选PPT.ppt》由会员分享，可在线阅读，更多相关《第1讲离散数学精选PPT.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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:本质上等价于一阶逻辑。nPro
3、log语言以逻辑演算为基础nLISP语言以演算为基础n人工智能：非单调推理，缺省推理。n信息安全等n第5页，此课件共34页哦6用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。D.E.KnuthD.E.Knuth的话第6页，此课件共34页哦7Dijkstra的话我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道要是我能年轻20岁的话我要回去学逻辑。n1 钱学森，关于思维科学的研究，思维科学，第3卷，1987。n2 M.Y.Vardi,A Brief
4、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 什么是命题(proposition)n命题：真假值唯
5、一确定的陈述句。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)n与，并且，而且，也n或，要么要么n非，不n如
6、果就，当，只有才，除非不，若则，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页哦2023/1/15命题逻辑16命题符号化n原子命题：p,q,r,p1,q1,r1,n联结词：n合取联结词：
7、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页哦2023/1/15回顾18命题符号化（举例）n(1)13不是偶数。解：p:13是偶数。p:13不是偶数.第18页，此课件共34页哦19合取联结词n定义2 设p、q为两个命题，复合命题“p而且q”称为p、q的合取式，记为pq，“”称作合取联 结词。pq真当且仅当p与q同时真.
8、pqpq000010100111第19页，此课件共34页哦2023/1/15回顾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页哦2023/1/15回顾22命题符号化（举例）n(4)她或许数学成绩好，或许英语成绩好。pq p：她数学成绩好.q：她英语成绩好.n(
9、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页哦2023/1/15回顾24命题符号化（举例）n(6)如果你努力学习，那么就可以得奖学金。pq p：你努力学习.q：你可以得奖学金.n(7)只要不下雨，我就骑自行车上班。pqn(8)
10、只有不下雨，我才骑自行车上班。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页，此课件共34页哦2023/1/15回顾27示例n(9)两个圆的面积相等当且仅当它们的半径相等。pq p：两个圆的面
11、积相等.q：两个圆的半径相等.第27页，此课件共34页哦28说明n上述五个联结词来源于日常使用的相应词汇，但并不完全一致，在使用时要注意：n以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能根据日常语言的含义去理解。n 不能“对号入座”，如见到“或”就表示为“”。n有些词含义不同，但也可表示为这五个联结词，如“但是”也可表示为“”。n 以后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容.第28页，此课件共34页哦29常用的联结词(connective)n合取(conjunction)：与，并且，而且，也n析取(disjunction)：或，要么要么n否定(negati
12、on)：非，不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页哦