1、主讲教师：常亮主讲教师：常亮E-mail: QQ： 737059669办公室电话办公室电话 : 2291071 手机手机 : 13481395869辅导教师：周小川辅导教师：周小川答疑时间：星期四答疑时间：星期四 上午上午 10:20-11:50答疑地点：答疑地点： 5教教 5楼楼 软件工程教研室软件工程教研室离散数学离散数学第二部分第二部分 数理逻辑数理逻辑教材：第教材：第 4章章 -第第 5章章从历史观看数理逻辑从历史观看数理逻辑o 数理逻辑：数理逻辑： 以数学的方法研究思维规律和推理过程的以数学的方法研究思维规律和推理过程的学科。学科。o 将数学应用于逻辑。将数学应用于逻辑。o 逻辑：研
2、究思维形式及其规律逻辑：研究思维形式及其规律n Aristotle：形式逻辑：形式逻辑 (主词和谓词逻辑主词和谓词逻辑 )；一般格式；一般格式 :三段论三段论所有的人都是要死的，所有的人都是要死的，苏格拉底是人，苏格拉底是人，所以，苏格拉底是要死的。所以，苏格拉底是要死的。o 17世纪，世纪， Leibniz：把推理过程像数学一样利用公：把推理过程像数学一样利用公式来描述，从而得出正确的结论；建立直观而又精确式来描述，从而得出正确的结论；建立直观而又精确的思维演算。的思维演算。n 遇有争论，双方可以拿起笔来说：让我们来算一下。遇有争论，双方可以拿起笔来说：让我们来算一下。从历史观看数理逻辑从历
3、史观看数理逻辑o 基本思路：基本思路： 首先引进一套首先引进一套 符号体系符号体系 ，规定，规定 一些规则一些规则 ，导出导出 一些定律一些定律 ，然后借助于这些符号、规则、定律，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样。因将逻辑推理的过程在形式上变得像代数演算一样。因此，数理逻辑又称此，数理逻辑又称 符号逻辑符号逻辑 。对命题形式化 /符号化推理谓词逻辑谓词逻辑命题逻辑命题逻辑命题符号、联结词 命题符号、联结词谓词、量词、个体词数理逻辑在计算机科学中的应用数理逻辑在计算机科学中的应用o 数字逻辑电路数字逻辑电路 布尔逻辑布尔逻辑 （命题逻辑的一种专门（命题逻
4、辑的一种专门化的形式）化的形式）o SQL 本质上等价于本质上等价于 一阶逻辑一阶逻辑o 逻辑程序设计逻辑程序设计 以以 一阶逻辑一阶逻辑 为基础为基础o 计算理论（可计算性，计算理论（可计算性， Turing机）机）o 程序语义与验证技术程序语义与验证技术o 程序的自动生成与转换程序的自动生成与转换o 人工智能（知识表示与推理）人工智能（知识表示与推理）o 智能规划智能规划 o Dijkstra的话的话o Edsger Wybe Dijkstra (1930-2002)， 最伟大的计算机科学家o 第七位图灵奖获得者 (1972 年 )o 我们熟悉的内容：n 提出 “goto有害 ”n 堆栈n
5、 进程的三个工作状态：就绪 、 运行、阻塞n 提出信号量和 PV原语n 解决了 “哲学家共餐 ”问题n 银行家算法n Dijkstra最短路径算法n 第一个 Algol 60编译器的设计者和实现者 o 我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我觉悟了，我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道就不会犯这么多错误，不少东西逻辑学家早就说了，可我不知道。要是我能年轻。要是我能年轻 20岁的话我要回去学逻辑。岁的话
6、我要回去学逻辑。第第 4章章 命题逻辑命题逻辑4.1 命题逻辑的基本概念命题逻辑的基本概念o 什么是命题？什么是命题？n 命题是或为真或为假的具有唯一真值的陈述句。命题是或为真或为假的具有唯一真值的陈述句。例如：例如：o 4是偶数。是偶数。o 桂林属于广东省。桂林属于广东省。o 命题的真值：对命题判断的结果。命题的真值：对命题判断的结果。o 真值的取值真值的取值 : 真、假真、假成为命题的两个条件成为命题的两个条件o 命题是或为真或为假的命题是或为真或为假的 具有唯一真值具有唯一真值 的的 陈述句陈述句 。o 条件条件 1：给定的句子是一个陈述句：给定的句子是一个陈述句o 请不要吸烟！请不要吸
7、烟！o 这朵花真美丽啊！这朵花真美丽啊！o 大于大于 2吗？吗？o 条件条件 2：给定的句子有唯一的真值：给定的句子有唯一的真值 (要么为真要么为假）要么为真要么为假）o 我正在说假话。我正在说假话。o x加加 1大于大于 5，其中的，其中的 x是变数。是变数。o 注意：注意：o a能被能被 4整除，其中的整除，其中的 a是一个给定的正整数。是一个给定的正整数。o 木星上有水。木星上有水。o 关键：尽管我们不知道它的真值，但其真值是客观存在的，而关键：尽管我们不知道它的真值，但其真值是客观存在的，而且是唯一的。且是唯一的。感叹句、祈使句、疑问句都不是命题。陈述句中的悖论以及判断结果不唯一确定的
8、也不是命题。例例 4.1判断下列语句哪些是命题？如果是命题，其真值如何？判断下列语句哪些是命题？如果是命题，其真值如何？ 5能被 3整除。 你 现 在好 吗 ? 请 勿喧 哗 ！ 1+2 = 3。 x + y = 6。 好美的音 乐 啊 ! 地球外的星球上也有生命。 3是偶数。 我正在 说 的是 谎话 。 李明 选 修了离散数学。一个陈述句是一个陈述句是否为命题，否为命题， 关键关键在于其是否具有在于其是否具有惟一真值惟一真值 ，而与，而与我们是否知道其我们是否知道其真假无关真假无关 。假不是命题不是命题真不是命题不是命题真值未知假不是命题（悖论，即，矛盾）真值可唯一确定(1) 2 + 5 8
9、。(2) 这这 只兔子跑得真快呀！只兔子跑得真快呀！(3) 请请 不要不要 讲话讲话 ！ (4) 王侯将相，宁有种乎？王侯将相，宁有种乎？(5) 己所不欲，勿施于人！己所不欲，勿施于人！(6) 2050年元旦是晴天年元旦是晴天 。(7) 我正在说谎。我正在说谎。(8) 这道题太难。这道题太难。(9) x大于大于 y，其中的，其中的 x和和 y是任意的两个数是任意的两个数(10) a大于大于 b，其中的，其中的 a和和 b是两个是两个 给给 定的数定的数(11) x2+10，其中的，其中的 x是任意一个数是任意一个数 . (12) 如果天气好，那么我去散步。如果天气好，那么我去散步。 真 值为 “假 ”, 假命 题 真 值现 在不知道EX1： 真 值现 在不知道真 值为 “真 ”, 真命 题 复合命 题 ，真 值 唯一
