离散数学-4-1[2014-10-27]

1、主讲教师：常亮 E-mail: QQ：737059669 办公室电话: 2291071 手机:辅导教师：周小川 答疑时间：星期四 上午 10:20-11:50 答疑地点：5教5楼 软件工程教研室,离散数学,第二部分 数理逻辑,教材：第4章-第5章,从历史观看数理逻辑,数理逻辑：以数学的方法研究思维规律和推理过程的学科。 将数学应用于逻辑。 逻辑：研究思维形式及其规律 Aristotle：形式逻辑(主词和谓词逻辑)；一般格式:三段论 所有的人都是要死的， 苏格拉底是人， 所以，苏格拉底是要死的。 17世纪，Leibniz：把推理过程像数学一样利用公式来描述，从而得出正确

2、的结论；建立直观而又精确的思维演算。 遇有争论，双方可以拿起笔来说：让我们来算一下。,从历史观看数理逻辑,基本思路：首先引进一套符号体系，规定一些规则，导出一些定律，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样。因此，数理逻辑又称符号逻辑。,对命题形式化/符号化,推理,谓词逻辑,命题逻辑,真值表法 主析取范式法/主合取范式法 等值演算法 构造证明法(形式证明系统) 归结推理方法(消解法),命题符号、联结词,等值演算法 构造证明法(形式证明系统) 归结推理方法(消解法),命题符号、联结词 谓词、量词、个体词,数理逻辑在计算机科学中的应用,数字逻辑电路 布尔逻辑（命题

3、逻辑的一种专门化的形式） SQL 本质上等价于一阶逻辑 逻辑程序设计以一阶逻辑为基础 计算理论（可计算性，Turing机） 程序语义与验证技术 程序的自动生成与转换 人工智能（知识表示与推理） 智能规划 ,Dijkstra的话,Edsger Wybe Dijkstra (1930-2002)，最伟大的计算机科学家 第七位图灵奖获得者(1972 年) 我们熟悉的内容： 提出“goto有害” 堆栈 进程的三个工作状态：就绪、运行、阻塞 提出信号量和PV原语 解决了“哲学家共餐”问题 银行家算法 Dijkstra最短路径算法 第一个Algol 60编译器的设计者和实现者 我现在年纪大了，搞了这么多年

4、软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话我要回去学逻辑。,第4章 命题逻辑,4.1 命题逻辑的基本概念 什么是命题？ 命题是或为真或为假的具有唯一真值的陈述句。 例如： 4是偶数。 桂林属于广东省。 命题的真值：对命题判断的结果。 真值的取值: 真、假,成为命题的两个条件,命题是或为真或为假的具有唯一真值的陈述句。 条件1：给定的句子是一个陈述句 请不要吸烟！ 这朵花真美丽啊！ 大于2吗？ 条件2：给定的句子有唯一的真值(要么为真要么为假） 我正在说假话。 x加1大于5，

5、其中的x是变数。 注意： a能被4整除，其中的a是一个给定的正整数。 木星上有水。 关键：尽管我们不知道它的真值，但其真值是客观存在的，而且是唯一的。,感叹句、祈使句、疑问句都不是命题。,陈述句中的悖论以及判断结果不唯一确定的也不是命题。,例4.1,判断下列语句哪些是命题？如果是命题，其真值如何？ 5能被3整除。 你现在好吗? 请勿喧哗！ 1+2 = 3。 x + y = 6。 好美的音乐啊! 地球外的星球上也有生命。 3是偶数。 我正在说的是谎话。 李明选修了离散数学。,一个陈述句是否为命题，关键在于其是否具有惟一真值，而与我们是否知道其真假无关 。,假,不是命题,不是命题,真,不是命题,不

6、是命题,真值未知,假,不是命题（悖论，即，矛盾）,真值可唯一确定,(1) 2 + 5 8。 (2) 这只兔子跑得真快呀！ (3) 请不要讲话！ (4) 王侯将相，宁有种乎？ (5) 己所不欲，勿施于人！ (6) 2050年元旦是晴天。 (7) 我正在说谎。 (8) 这道题太难。 (9) x大于y，其中的x和y是任意的两个数 (10) a大于b，其中的a和b是两个给定的数 (11) x2+10，其中的x是任意一个数. (12) 如果天气好，那么我去散步。, 真值为“假”, 假命题, 真值现在不知道,EX1：, 真值现在不知道,真值为“真”, 真命题, 复合命题，真值唯一,命题的符号化,命题的符号

7、化：用英文字母、数学符号等表示命题。 p：4是偶数； q：煤是白的； p1：离散数学考试张三及格了； r：土星上有水； s：桂林属于广东省。 以1（或T）表示命题的真值为真；以0（或F）表示命题的真值为假。 讨论上面各个命题的真值： p的真值为1（或T）； q、s的真值为0（或F）； p1 、r的真值现在还不知道。,命题的分类,根据其真值分类： 真命题：真值为“真”的命题 假命题：真值为“假”的命题 根据其复杂程度分类： 简单命题/原子命题：由简单陈述句确定的命题，不能分解成更简单的命题 最小的基本单位 复合命题：由若干个简单命题通过联结词联结起来构成的新命题。 如果天气好，那么我去散步。 因

8、为32，所以3 2。,4.1.2 联结词,5个重要的联结词 否定联结词 p 合取联结词 p q 析取联结词 p q 蕴涵联结词 p q 等价联结词 p q,否定式与否定联结词,设p为命题，复合命题 “非p”称为p的否定式，记作p。 符号称作否定联结词。 p为真当且仅当p为假。 真值表 相应具有否定意义的词：“并非”、“不是”等。 (例子)将如下命题符号化： 期中考试，张三没有考及格 p ：期中考试，张三考试及格了 p,求“我们班上所有的同学都大于18岁”的否定。 p：我们班上所有的同学都大于18岁。 则p的含义为？ 并不是我们班上所有同学都大于18岁。 我们班上并不是所有同学都大于18岁。 我

9、们班上所有的同学都不大于18岁。,练习：,合取式与合取联结词,设p, q为命题，复合命题“p并且q”称为p与q的合取式，记作pq。 符号称作合取联结词。 pq为真当且仅当p与q同时为真。 真值表 其他具有合取意义的词：并且、既又、虽然但是、不但而且、一边一边等。,将下列命题符号化。 (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. 解： 令 p：王晓用功，q：王晓聪明，则 (1) pq (2) pq (3) pq. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解：令 r : 张辉是三好学生，s :王丽是三好学生 ，则 (4) rs.

10、 (5)是简单命题；令 t : 张辉与王丽是同学。,练习：,（1）(4)说明描述合取式的灵活性与多样式。 并且、既又、不是而是、虽然但是、不但而且、一边一边 （5）中“与”联结的是句子的主语成分，因而（5）中句子是简单命题。 不要见到“与”、“和”就使用,析取式与析取联结词,设p, q为命题，复合命题“p或q”称为p与q的析取式，记作pq。 符号称作析取联结词。 pq为假当且仅当p与q同时为假。 真值表 相应具有析取意义的词：“或”。,相容或（可兼或） 特点：所谈及的两者可以同时为真 例：他可能是100米或者是400米赛跑的冠军。 令 p：他是100米赛跑的冠军，q: 他是400米赛跑的冠军；

11、 则该复合命题可符号化为 pq 排斥或（不可兼或） 特点：所谈及的两者不能同时为真。 例：派小王或小李中的一人去开会。 令p：派小王去开会，q ：派小李去开会； 则该命题可符号化为（pq)(pq) 即，“小王去而小李不去” 或“小李去而小王不去”。 注意：不能见了“或”就表示为PQ。,“或”的二义性,1. 将下列命题符号化。 (1)张三或者李四考了90分。 (2)第一节课上数学课或者上政治课。,练习：,蕴涵式与蕴涵联结词,设 p, q为命题，复合命题“如果p, 则q ”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件。 符号称作蕴涵联结词。 pq为假当且仅当 p 为真 q

12、为假。 真值表,进一步的说明,pq表示的基本逻辑关系是： p是q的充分条件； q是p的必要条件。 相应具有蕴涵意义的词： “如果p, 那么q” 如果2是偶数，那么4是偶数。 “只要p, 就q” “因为p, 所以q” 因为鸽子是鸟类动物，所以鸽子会飞。 “p仅当q” “只有q, 才p” “除非 q, 才 p” 除非雪是黑的，7才是偶数。 “除非 q, 否则非 p” 除非雪是黑的，否则7不是偶数。,进一步的说明,p与q不一定有内在联系，仅是形式结构的推理。 如果3+3=6，则雪是白色的。 因为23，所以1+1=2。 pq的真值仅取决于p与q的取值情况，不一定要求p、q之间有内在联系 因为23，所以

13、1+1=2。 如果3+3=6，则雪是白色的。 如果太阳从西边出来，我就不姓张。 如果今天是星期二，则明天是星期三。 当p为假时，无论q是真是假，pq都为真。,等价式与等价联结词,设 p, q为命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq。 符号称作等价联结词。 pq为真当且仅当p与q同时为真或同时为假。 真值表 pq的逻辑关系：p与q互为充分必要条件。,将下列命题符号化，并讨论它们的真值： (1) 2+3=5的充分必要条件是太阳从东方升起。 (2) 2是偶数的充分必要条件是美国位于非洲。 (3) 两个正方形A和B的面积相等当且仅当它们的边长相等。 注意：常见的错误，认为(1) 为假。 再次强调： pq和pq的真值仅体现p与q的取值关系；而与p和q之间是否有什么内在联系无关。,练习：,复合命的题符号化,三个步骤： 简单命题符号化 联结词符号化 “联结”简单命题 注意： 要按逻辑关系进行，而不能仅凭字面翻译。 不能“对号入座”，如见到“或”就表示为“”，见到“与”就表示为“”。 复合命题的真假值一定要根据联结词的定义去理解，而不能据日常语言的含义去理解。 五个联结词的优先顺序为： , , 若遇有括号时，应该先进行括号中的运算。 如果出现的联结词同级，又无括号时，则按从左到右的顺序。,将下列