数据结构域算法设计-第一章命题逻辑(1,2,3) 课件

《数据结构域算法设计-第一章命题逻辑(1,2,3) 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第一章命题逻辑(1,2,3) 课件（66页珍藏版）》请在金锄头文库上搜索。

1、离散数学,Discrete Mathematics,主讲教师,王卫苹 电话：62332931 邮箱： 办公地点：信息机电楼728室,课程简介,现代数学重要分支 以研究离散量的结构和相互间的关系为主要目标。 信息类学科基础理论的核心课程。 是数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析等课程必不可少的先行课程。 培养缜密思维，提高综合素质。,主要内容,数理逻辑 命题逻辑、一阶谓词逻辑 集合论 集合及其运算、二元关系与函数 代数结构 代数系统的基本概念、群、环、域、格与布尔代数 图论 图的基本概念、欧拉图与哈密顿图、树、平面图,数理逻辑和集合论作为两块基石奠定了离散数学乃至整个数

2、学理论的基础，在上面生长着代数结构、序结构、拓扑结构和混合结构，这四大结构涵盖与生长出许多数学分支，同时各分支间交叉融合，又形成了许多新的数学分支，形成了庞大的数学体系。,教材介绍,教材名称：离散数学 编著者：杨炳儒，谢永红，刘宏岚，洪源，罗熊. 高等教育出版社 教材特色： 本教材以认知结构教学论（亦称KM教学论）基本内涵为贯穿，即“双图融合”的教学机制；“教学回路”的教学模式；“立体结构”的教学内容；“三段论式”的教学方法。 具有全新的模式与体例，其演绎铺展的路径如下： 全书概述-篇引论（树形类化图）-章粗概图-章应用概图-按节展开（核心知识点；嵌入思维形式注记图；每节小结）-章习题类化（常

3、见题典型解析）-章知识逻辑结构图-扩展阅读-习题-篇知识逻辑结构图。,参考资源,屈婉玲，耿素云离散数学高等教育出版社 左孝陵，刘永才离散数学上海科学技术文献出版社 中国高校计算机课程网离散数学课程讨论http:/ 平时成绩组成： 上课出勤 作业,第一篇 数理逻辑,Mathematical Logic,什么是数理逻辑,数理逻辑是用数学方法来研究推理规律的数学学科。 主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系主要研究方法：数学的方法 引进一套符号体系的方法。 所以数理逻辑又称符号逻辑。 与计算机科学的联系 计算机及计算机科学与数理逻辑有着十分密切的关系。人们说数字电子计算机是

4、数理逻辑与电子学结合的产物。,Dijkstra算法及其它,Dijkstra(迪杰斯特拉)算法（最短路径算法）有向图中任意两个顶点之间的最短路径问题。 1972图灵奖（http:/ Dijkstra的话“我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话我要回去学逻辑。”程序算法数据； 算法逻辑控制,数理逻辑的知识体系,第一章命题逻辑,引言,逻辑主要研究推理过程，而推理过程必须依靠命题来表述。 在命题逻辑中，“命题”被看作最小单位。 命题逻辑是数理逻辑中最

5、基本、最简单的部分。,命题逻辑部分知识逻辑概图,命题逻辑在计算机科学技术相关领域的应用概图,1.1.命题的基本概念,命题：具有真假意义的陈述句。,1.1.1 命题,什么是命题 推理是数理逻辑研究的中心问题，推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位，称具有真假意义的陈述句为命题。 真值 命题总是具有一个确定真或假的“值”，称为真值。 真值只有“真”和“假”两种，分别记为True（真）和False（假），用1和0表示。 真值为真的命题称为真命题，真值为假的命题称为假命题。 判断给定的句子是否为命题的基本步骤 首先应是陈述句； 其次要有唯一的真值。,1.1.1

6、命题,1）该吃早饭了！祈使句，不是命题。 2）多漂亮的花呀！感叹句，不是命题。 3）明天你有什么安排吗？疑问句，不是命题。 4）我正在说谎。不是命题。因为无法判定其真假值，若假设它为假即我正在说谎，则意味着它的反为真，即我正在说实话，二者相矛盾；若假定它为真即我正在说实话，则意味着它的反为假，我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题。,1.1.1 命题,5） x-y 2。不是命题。因为x, y的值不确定，某些x, y使xy2为真，某些x, y使xy2为假，即xy2的真假随x, y的值的变化而变化。因此xy2的真假无法确定，所以xy2不是命题。 6）不在同一直线上的三点确

7、定一个平面。是命题。 7）郑州是河南省的省会。是命题。 8）下一个星期天会下雪。是命题。因为它的真值虽然目前无法确定，但它是有唯一真值的。,1.1.1 命题,9）这碗汤味太淡了。是命题。它的真假似乎不能唯一的判定，因为它因人而异，但这个语句的真假取决于说话人的主观判断（即可以认为此语句是“我认为这碗汤味太淡了”的缩写）。 10）1011+1000=10011。是命题，虽然当它表示的数是十进制数或其他非二进制数时此语句是假的，当它表示的数为二进制数时，此命题是真的。但是，这个语句毕竟是处于一系列语句中的一个特定位置上，由前后文关系，立即可以确定它所表示的数是二进制数还是非二进制数，并且一个数不可

8、能既是二进制数，又是其他非二进制数。故此语句是能分辨真假的。,1.1.2 命题的分类,命题可以分为两种类型： 一种命题是不能再分解为更简单命题的，称作原子命题，又可称为简单命题； 另一种命题是通过联结词、标点符号将原子命题联结而成，称作复合命题。例如： 1）玫瑰是红的并且紫罗兰是蓝的。 2）如果明天是个好天气，我们就去野炊。 复合命题的基本性质是：其真值可以由其原子命题的真值以及它们复合成该复合命题的联结方式确定。,1.1.3 命题标识符,命题标识符 为了能用数学的方法来研究命题之间的逻辑关系和推理，需要将命题符号化。 通常使用大写字母P, Q, 或用带下标的大写字母或用数字，如Ai，12等表

9、示命题。 例如： P：今天下雨 意味着P表示“今天下雨”这个命题的名。 也可用数字表示此命题 例如： 12：今天下雨 表示命题的符号称为命题标识符，P和12就是命题标识符。,1.1.3 命题标识符,命题常元 一个命题标识符如果表示确定的简单命题，就称为命题常元。 命题变元 如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元。 因为命题变元可以表示任意简单命题，所以它不能确定真值，故命题变元不是命题。 指派 当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派。,小结,只有陈述句才有可能是命题，但并不是所有的陈述句都能成为命题。 本小节的思维形式注记图：,1

10、.2 联 结 词,联结词：确定复合命题的逻辑形式。,原子命题和联结词可以组合成复合命题。 联结词确定复合命题的逻辑形式，它来源于自然语言中的联结词，但与自然语言中的联结词有一定的差别； 从本质上讲，这里讨论的联结词只注重“真值”，而不顾及具体内容，故亦称“真值联结词”。,1.2.1 否定联结词,定义1.1 设P为任一命题，复合命题“非P”（或“P的否定”）称为P的否定式，记作P，读作“非P”。称为否定联结词。 P的逻辑关系为P不成立，P为真当且仅当P为假。 命题P的真值与其否定P的真值之间的关系,1.2.1 否定联结词,例1.2 设 P：这是一个三角形P：这不是一个三角形 例1.3 设 P：雪

11、是白色的P：雪不是白色的在此例中，不能将P认为是命题“雪是黑色的”。因为雪不是白色的情况中有蓝色、红色等许多种可能。 在日常语言中，还可以用“非”、“不”、“没有”、“无”、“并不”等多种方式表示否定。,1.2.2 合取联结词,定义1.2 设P,Q为任意二命题，复合命题“P并且Q”（或“P与Q”）称为P和Q的合取式，记作PQ，读作“P与Q”，称为合取联结词。 PQ的逻辑关系为P与Q同时成立。PQ为真当且仅当P与Q同时为真。 命题PQ的真值与命题P和命题Q的真值之间的关系如表所示。,1.2.2 合取联结词,在自然语言中，还可用“并且”、“同时”、“以及”、“既又”、“不但而且”、“虽然但是”等多

12、种方式表达合取。 例1.4 设 P：今天打雷Q：今天下雨则 PQ：今天打雷且下雨 例1.5 设 P：小李在看书Q：小李在听音乐则 PQ：小李一边在看书，一边在听音乐,1.2.3 析取联结词,定义1.3 设P,Q为任意二命题，复合命题“P或Q”称为P和Q的析取式。记作PQ，读作“P或Q”，称为析取联结词。 PQ的逻辑关系为P与Q中至少一个成立。PQ为真当且仅当P与Q中至少一个为真。 命题PQ的真值与命题P和命题Q的真值之间的关系如表所示。,1.2.3 析取联结词,联结词是可兼或，因为当命题P和Q的真值都为真时，其值也为真。但自然语言中的“或”既可以是“排斥或 ”也可以是“可兼或 ”。 例1.6

13、晚上我们去教室学习或去电影院看电影。（排斥或） 例1.7 他可能数学考了100分或英语考了100分。（可兼或） 例1.8 刘静今天跑了200米或300米远。（既不表示“可兼或”也不表示“排斥或”，它只是表示刘静所跑的大概路程，因此它不是命题联结词，故例1.8是原子命题。）,1.2.3 析取联结词,由以上例子可以看出联结词“”和自然语言中的“或”的意义不完全相同。 与“”联结词相似，在自然语言中，通常是具有某种关系的两条语句之间使用析取“或”，但在数理逻辑中，任何两个命题都可以通过用析取“”联结起来得到一个新命题。 例1.9 设 P：今天打雷Q：今天打闪则 PQ：今天打雷或今天打闪 例1.10

14、设 P：今天是星期一Q：今天天气很好则 PQ：今天是星期一或天气很好,1.2.4 蕴涵联结词,定义1.4 设P,Q为任意二命题，复合命题“如果P，则Q”称为P和Q的蕴涵式，记为P Q，读作“如果P则Q”。 称为蕴涵联结词。称P为前件，Q为后件。 P Q的逻辑关系为Q是P的必要条件。P Q为假当且仅当P为真Q为假。 命题P Q的真值与命题P和命题Q的真值之间的关系如表所示。,1.2.4 蕴涵联结词,说明： 1）蕴涵联结词也称为条件联结词。“如果P，则Q”也称为P与Q的条件式。 2）蕴涵式的真值关系不太符合自然语言中的习惯，这一点请读者务必注意。 3）给定命题公式PQ，命题公式QP称为PQ的逆换式

15、；PQ称为PQ的反换式；QP称为它的逆反式。逆换式类似于中学数学里所学的命题的逆命题；反换式类似于否命题；逆反式类似于逆否命题。,1.2.4 蕴涵联结词,例1.11 甲对乙说：“如果今晚我们班上不开会，则我就和你一起去玩。”请问：在什么情形下，乙认为甲的这句话是假？解：如果班上没有开会，甲与乙一起去玩，则自然认为甲说的话为真；如果班上开会了，甲没有与乙一起去玩，则没有理由认为甲的话为假；如果班上没开会，甲没有与乙一起去玩，则显然认为甲的话为假；如果班上开会了，但甲未参加而与乙一起去玩了，则也不能认为甲的话为假。 在自然语言中，对于“如果则”这样的语句，当前提为假时，结论不管真假，这个语句的意义是无法判断的。因此在条件命题中，当前提为假时无论结论真值如何，其取值都为真的情况称为“善意的推定”。,1.2.4 蕴涵联结词,例1.12 设 P：明天天气晴朗Q：我们就去郊游则 P Q：如果明天天气晴朗，我们就去郊游。 例1.13 设 P：x4Q：x216则 PQ：如果x4，则x216。 对于“如果P则Q”在日常语言中有多种表达方式，诸如“只要P就Q”、“当P则Q”、“因为P所以Q”、“P仅当Q”、“只有Q才P”、“除非Q才P”、“除非Q，否则非P”等。尽管叙述的方式表面看起来不同，但只要表示Q是P的必要条件，都可以符号化为PQ。,