华工离散数学命题逻辑课件讲述

《华工离散数学命题逻辑课件讲述》由会员分享，可在线阅读，更多相关《华工离散数学命题逻辑课件讲述（110页珍藏版）》请在金锄头文库上搜索。

1、离散数学及其应用 离散数学及其应用 华南理工大学 计算机科学与工程学院 1 离散数学及其应用 离散数学 研究离散对象及其相互间关系的一门数学学科。 它是以研究离散量的结构和相互间的关系为主要目标，描述了计算 机科学离散性的特点. 从数学的角度出发：连续数学和离散数学，都是刻画和分析现实世 界的重要工具。 基础数学的延伸 算法与数据结构的理论基础 概率统计、算法设计与分析的理论基础 其他专业课程的描述和建模工具 2 离散数学及其应用 为什么要学习离散数学？ 离散数学是现代数学的一个重要分支，是计算机专业的一门重要的 专业基础课程。 是数据结构、操作系统、计算机网络、算法设计与分析、软件工 程、人

2、工智 能、形式语言、编译原理等计算机本科阶段核心课程的 基础，也是遗传算法、数据挖掘、模式识别、密码学、网络通信理 论等课程的重要基础。 该课程所提供的训练十分有益于概括抽象能力、逻辑思维能力、归 纳构造能力的提高，十分有益于严谨、完整、规范的科学态度的培 养。 3 2015年10月21日9时48分Chen Qiong,South China Univ.of Tech.3 离散数学及其应用 计算机科学与离散数学的关系 计算机科学的任务是用计算机的硬件、外设和软件构成一个 系统，使得许多不同领域的问题都能在这样的计算机系统中得 到解决。 为了完成这个任务，就必须用一种符号语言构成一个包括了 不同

3、领域的通用模型。 离散数学就是指出构成一个包括了不同领域的通用模型的思 维方法，并且告诉我们怎样用不同的语言（符号语言、图形语 言和逻辑语言等）从最简单的对象（集合）出发表示通用模 型。 4 离散数学及其应用 计算机科学与离散数学的关系 离散数学的思维方法能够为计算机科学所用 计算机科学知识的掌握需要三方面的能力-构造模型、算法 设计、程序设计的能力 思维训练：构造性思维 5 离散数学及其应用 离散数学课程教学目标 知识获取能力：建立良好的知识结构，为学习其他课程打下 基础 基本应用能力：掌握离散数学的语言，能对实际问题给出清 晰的描述（建模） 工程实践能力：掌握离散数学的分析方法，针对实际问

4、题设 计解决方案并加以实施 研究能力：培养思维严谨性，提升抽象思考和严格推理能力 培养创新意识：了解现代数学思想和学科进展， 6 2015年10月21日9时48分Chen Qiong,South China Univ.of Tech. 6 6 离散数学及其应用 离散数学的应用 在计算机科学方面的应用 是数据结构、操作系统、计算机网络、算法设计与分析、软件工 程、人工智 能、形式语言、编译原理等计算机本科阶段核心课程的基础， 也是遗传算法、数 据挖掘、模式识别、密码学、网络通信理论、等课程的 重要基础。 在通信方面的应用 代数系统在开关线路的计数，数字通信的纠错码方面的应用 在现实生活中的应用

5、TSP 在企业管理、交通规划、战争指挥、金 融分析，生物、医药等领域都有 重要的应用。 7 2015年10月21日9时48分Chen Qiong,South China Univ.of Tech. 7 7 离散数学及其应用 离散数学的一些应用 关系数据库 四色定理 网络规划 信息安全 计算复杂性问题：该问题可计算吗？该问题能/不能计算？计算机复杂性如何 ？ 操作系统中，如何调度进程使得系统效率最优？ 程序结构度量：判断程序结构是否相似 提高信息传输效率的通信编码的设计 通信网络频率分配 设计集成电路线路的布局，达到最优效率 数字通信的可靠性：如何设计高效的检错码和纠错码？ 8 离散数学及其应用

6、 离散数学的一些应用 中国邮递员问题 学生考试日程表的安排 人携带狼、羊和草渡河的问题 物流运输的最优路径的计算 达到最高效率的工作流程的安排 生产调度和人员安排 酒店的清洁工的工序安排 库房和运输管理 航班调度，交通规划 考生录取 9 离散数学及其应用 学习内容 数理逻辑 集合，函数和关系 图论 数理逻辑是研究推理的学科，在人工智能、程序理论和数 据库理论等的 研究中有重要的应用。集合论和图论为数据结 构和算法分析奠定了数学基础， 也为许多问题从算法角度如 何加以解决提供了进行抽象描述的一些重要方法。 10 结束下一页 离散数学及其应用 关于课程学习 课程特点 知识点集中、概念定理多 方法性

7、强 -阅读、思考、练习、阅读、总结. 课程考核 过程考核、在线测试、期末考试 11 离散数学及其应用 参考资料 教材：陈琼等编著：离散数学及其应用，机械工业出版社 Kenneth H.Rosen, Discrete Mathematics and Applications, 机械 工业出版社 耿素云、屈婉玲著：离散数学，高教出版社 傅彦、顾小丰著：离散数学及其应用，电子工业出版社 B Kolman,Robert C. Busby, Sharon Ross, Discrete Mathematics Structures, 高等教育出版社 12 离散数学及其应用 第一部分 数理逻辑 数理逻辑是研

8、究推理逻辑规则的一个数学分支，它采用数学 符号化的方法，给出推理规则来建立推理体系。进而讨论推理 体系的一致性、可靠性和完备（全）性等。 数理逻辑的研究内容是两个演算加四论，具体为命题演算、 谓词演算、集合论、模型论、递归论和证明论。 数理逻辑是形式逻辑与数学相结合的产物。但数理逻辑研究 的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各 门学科只研究自身的具体规律。 13 离散数学及其应用 第1章 命题逻辑 1.1 命题与联结词 1.2 命题公式及其分类 1.3 命题演算的关系式 1.4 范式 1.5 命题演算的推理 14 离散数学及其应用 1.1 命题与联接词 1.1.1 命题的概念

9、定义 命题的真值 联结词 15 离散数学及其应用 命题及其真值 命题:是用陈述句表示的一个或者为真或者为假，但不能同时 既为真又为假的判断语句。 命题的真值: 判断的结果,真（T或1）或假（F或0) 真命题: 真值为真的命题 假命题: 真值为假的命题 16 离散数学及其应用 例题 判断下列句子中那些是命题？若是命题的，判断其真值。 1.北京是中国的首都。 2.2+3=6。 3.3-x=5。 4.请关上门。 5.几点了？ 6.除地球外的星球有生物。 7.多漂亮的花啊！ 8.我只给所有不给自己理发的人理发。 17 Y 真 Y 假 N 真值不确定 N 疑问句 N 感叹句 N 祈使句 N 悖论 Y 真

10、值确定, 但未知 离散数学及其应用 命题的表示 引入英文字母表示任意的命题 表示命题的符号称为命题变量，通常用p、q、r.、P、Q、R. 表示命题变量。 命题变量没有真值，只有表示一个确定的命题后，才有真值。 如用p表示命题：“2+3=6”，这时p的真值为假（F）， 也可以用p表示命题：“2+3=5”,这时p的真值为真（T）。 18 离散数学及其应用 简单命题与复合命题 简单命题(原子命题):不能分解为更简单的陈述语句的命题 简单命题：“北京是中国的首都”。 复合命题:由两个或几个简单句和连词组合而成的命题 复合命题：“如果明天天气好, 我们就去爬山。” 命题的符号化：用英文字母或英文字母和联

11、结词的组合表示命 题，称为命题的符号化。 联结词 - 连词 19 离散数学及其应用 联结词 （一）否定 定义1.1.4 设p是一个命题，p表示一个新命题“非p”。命题p 称为p的否定。当且仅当p的真值为假时，p的真值为真。 p的真值表： 例如：p：今天是晴天。则 p：今天不是晴天。 “非”，“不”，“没有”，“无”，“并非”等都可用来 表示。 20 pp T F F T 离散数学及其应用 联结词 （二）合取 定义1.1.5 设p、q表示任意两个命题, pq 可表示复合命题“p 并且q”。当且仅当p和q的真值同时为真时，pq的真值为 真。 pq的真值表： 例如： p: 今天是晴天； q: 今天去

12、公园。 pq: 今天是晴天并且今天去公园。 “和”，“与”，“也”，“并且”，“既 .又.”，“ 不仅.而且.”，“虽然.但是.”等都可用来表示。 21 p qpq T T T F F T F F T F F F 离散数学及其应用 联结词 （三）析取 定义1.1.6 设p、q表示任意两个命题, p q 可表示复合命题 “p或q”。当且仅当p和q的真值同时为假时，p q的真值为 假。 p q的真值表： 例如： p: 今天去看电影； q: 今天去公园。 p q: 今天去看电影或今天去公园。 “或”，“可能.可能.”，“或者.或者.”等可用表 示。 22 p qp q T T T F F T F F

13、 T T T F 离散数学及其应用 联结词 自然语言中的“或”具有二义性：兼容性或和不兼容性或。 兼容性或 电灯不亮是灯泡或线路有问题所致. 不兼容性或（排斥或） 派小王或小李中的一人去开会 表示兼容性或 例如：p: 电灯不亮是灯泡有问题所致； q: 电灯不亮是线路有问题所 致。 p q :电灯不亮是灯泡或线路有问题所致。 p：派小王去开会，q：派小李去开会， (p q)(p q): 派小王或小李中的一人去开会 23 离散数学及其应用 联结词 （四）蕴涵 定义1.1.7 设p、q表示任意两个命题, p q 可表示复合命题“如果p ，则q”。当且仅当p的真值为真，q的真值为假时，pq的真值为 假

14、。 p q的真值表： 例如： p:今天天气晴朗； q:我们去海滩。 p q: 如果今天天气晴朗，我们就去海滩。 24 p qpq T T T F F T F F T F T T 离散数学及其应用 联结词 蕴涵式：pq p为蕴涵前件，q为蕴涵后件 p是q的充分条件，q是p的必要条件 表示：“如果p，则q”，“如果p，那么q”，“当p则q”，“p仅当q”等。 假设：p：天气晴朗；q：我们去海滩。 1.如果天气晴朗，我们去海滩。pq 2.仅当天气晴朗，我们去海滩。 qp 25 离散数学及其应用 联结词 （五）等价 定义1.1.8 设p、q表示任意两个命题, p q 可表示复合命题“p当且仅当q” 。

15、当且仅当p和q的真值同时为真或同时为假时，pq的真值为真。 p q的真值表： 例如： p:两个三角形是全等的。q：两个三角形的三条对应边相等。 pq表示“两个三角形是全等的当且仅当它们的三条对应边相等”。 26 p qpq T T T F F T F F T F F T 离散数学及其应用 联结词 等值式pq 表示p与q互为充分必要条件的逻辑关系 表示形如“p当且仅当q”，“如果p，那么q，反之亦然”等的命 题。 27 离散数学及其应用 例题 将下列命题符号化： 虽然天气很冷，老王还是来了。 小王和小李是好朋友。 小王和小李是好学生。 小王或小李中的一人是游泳冠军。 只有你学过微积分或是数学系的学生，才可以选修这门课。 如果明天早晨6点不下雨，我就去跑步。 今天下雨与3+3=6。 登陆服务器必须输入一个有效的口令。 2+3=5的充要条件是加拿大位于亚洲。 28 离散数学及其应用 解： 虽然天气很冷，老王还是来了。 设p：天气很冷。q：老王来了。 则符号化为：pq。 小王和小李是好朋友。 这句虽然有连词“和”，但是个简单句， 可用p表示：小王和小李是好朋友。 小王和小李是好学生。 设p：“小王是好学生” q ：“小李是好学生”， 则符号化为： pq。 29 离散数学及其应用 解： 小王或小李中的