chapter1.pptVIP

离散数学课幻灯片 教学方法要点 教学目的旨在通过学习本课培养和提高学生的抽象思维能力和逻辑推理能力。 教师方面力求讲透概念的来龙去脉和论证推理的逻辑严谨性；注意理论的实际应用，培养学生解决实际问题的能力。 学生方面要充分发挥主观能动性，课前尽可能预习以争取课堂上最好的听课效果，课后尽可能多做习题，从中理解和掌握有关的概念。 离散数学简介 离散数学是计算机科学与技术的理论基础，如果说“高科技本质上是数学技术”的话，计算机科学与技术基本上是离散数学技术。 自从计算机产生到以后的每一步发展都离不开数学，1936 年 A.M. Turing发表了著名论文：‘理想计算机’，从而给出了计算机设计的理论模型，1946 年在 J.von. Neumann 领导下制造了世界第一台计算机ENIAC. 离散数学一般包含如下5个主题：数学推理、组合分析、离散结构、算法思维、应用及模拟。 第一章 数理逻辑 前言 研究人的思维形式和规律的科学称为逻辑学，由于研究的对象和方法各有侧重而又分为形式逻辑、辨证逻辑和数理逻辑。 数理逻辑是应用数学方法研究推理的科学。数理逻辑又叫符号逻辑，因为它的主要工具是符号体系。数理逻辑的核心是把逻辑推理符号化，即变成象数学演算一样完全形式化了的逻辑演算。 本章主要介绍命题演算(1.1---1.5)和谓词演算(1.6---1.8)。 第一章 数理逻辑 1 命题 2 重言式 3 范式 4 联结词扩充与归约 5 推理规则证明方法 6 谓词与量词 7 谓词演算永真公式 8 谓词演算推理规则 命题的概念 所谓命题，是具有真假意义的陈述句，也就是能够确定或分辨其真假的陈述句，且真与假必居其一。简言之，命题是非真即假的陈述句。 命题是真就说其真值为真，命题是假就说其真值为假。 关于命题的注记 某些命题可能无法查明其真值。如例1(d), (e). 命题真假会因时因地而异。例如： a) 人一只手有五指 b) 现在是上午 那些‘自称谓’的陈述句可能产生自相矛盾的结论，故不在我们讨论之列。例如：某人说: ‘我正在说谎’(见P.1例3) 请注意: 数理逻辑的任务不在于研究某个具体命题的真假问题，而在于它可以赋予真或假的可能性，特别是研究各命题规定其真值后它们之间的联系。 原子命题,复合命题与命题联结词 不能再细分的命题称为原子命题。例如，“明天下雪”、“明天下雨”都是原子命题。 原子命题常可通过一些命题联结词构成新命题，这种命题称为复合命题。例如，“明天下雪或明天下雨”是复合命题。 命题联结词又称为逻辑运算符，常用的有五种，它们是：否定词、合取词、析取词、蕴涵词和等价词。 1 否定词 ? 设P表示命题，则‘P不真’ 是另一命题，记为 ? P，读为 ‘非P’ 否定词可用右表定义，此表称为 ? P的真值表 2 合取词 ∧ 若 P,Q 表示命题，则 ‘P并且Q’ 也是命题，记为 P∧Q ,读为 ‘P合取Q’. P∧Q 的真值表如右表所示。由真值表可知 P∧Q 真,当且仅当 P,Q 俱真. 3 析取词 ∨ 若 P,Q 表示命题，则 ‘P或者Q’ 也是命题，记为 P∨Q,读为 ‘P析取Q’. P∨Q 的真值表如右表所示。由真值表可知 P∨Q 真,当且仅当P,Q 至少有一个真 4 蕴涵词 → 若 P,Q 表示命题，则 ‘P蕴涵Q’ 也是命题，记为 P→Q,读为 ‘P蕴涵Q’. P→Q 的真值表如右表所示。由真值表可知P→Q为假,当且仅当P为假而Q为真. 关于 P→Q 真值表的说明 在日常生活中当P=0时，P→Q 没有实际意义。故人们只考虑 P=1 的情形。但在P→Q 真值表中规定：当 P=0 时，不管 Q 如何 P→Q 的真值都为1. 有没有道理呢？ 例如，张三对李四说：‘我去图书馆一定帮你借那本书’。可以将这句话表为命题 P→Q(P表示:张三去图书馆,Q表示:张三借那本书)。后来张三因有事未去图书馆，即 P=0，此时按规定 P→Q 为真。我们应理解为张三讲了真话，即他要是去图书馆我们相信他一定会为李四借书。这种理解也称为‘善意推定’。 逆反命题与原命题的真值表完全一样 设P→Q为原命题, 则?Q→?P为逆反命题。 ?Q→?P为假 当且仅当 ?Q真并且?P假; 也就是当且仅当 Q假并且P真; 也就是当且仅当 P真并且Q假; 也就是当且仅当 P→Q为假. 所以逆反命题与原命题的真值表完全一样. 也就是它们本质上相同. 5 等值词 ? 若 P,Q 表示命题，则 ‘P等值于Q’ 也是命题,记为 P?Q, 读为 ‘P等值于Q’. P?Q 的真值表如右表所示. 由真值表可知 P?Q 为真,当且仅当P