《离散数学教案》ppt课件

《《离散数学教案》ppt课件》由会员分享，可在线阅读，更多相关《《离散数学教案》ppt课件（647页珍藏版）》请在金锄头文库上搜索。

1、1,离散数学教案 课程编号：09464015 课程学分：4 课程学时：64 讲授：叶红,2,课程性质,离散数学（又称计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。,3,课程目标,离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。,4,与其他课程的关系,离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的先导和基础课程。,5,离散数学 上海科学技术文献出版社，1982

2、左孝凌等编著 Discrete Mathematical Structures（Fourth Edition） Higher Education Press，2001 Bernard Kolman，Robert C.Busby，Sharon Cutler Ross,教材与参考书,6,课程内容,本课程根据大纲的内容和相关独立性， 可分为四大部分 第一部分 数理逻辑 包括命题逻辑;谓词逻辑 第二部分 集合论 包括集合与关系;函数,7,课程内容,第三部分 代数系统 包括代数结构;格与布尔代数 第四部分 图论 讲课时数：62学时,8,学习方法,本课程有二个特点： （）定义、定理多。 本课内容定义定理例

3、题 （）课外作业较多。,9,学习方法,为了学好这门课，特提出三点要求： （）弄懂定义、定理，弄懂例题，加深对定义、定理的理解； （）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。 （3）做好课堂笔记.,10,学习方法,最后，做两点说明： （1）考试内容以课堂上讲的为范围； （2）每次课后均布置作业。希望大家认真完成。 和一个要求： 为搞好教学，需要双方共同努力。,11,第一篇 数理逻辑,逻辑学:研究思维形式及思维规律的科学。 逻辑学分为二类 辩证逻辑:是研究事物发展的客观规律。 形式逻辑:对思维的形式结构和规律进 行研究。 数理逻辑：是用数学的方法研究概念、 判断和推理的科学，属

4、于形式逻辑。,12,第一篇 数理逻辑,在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。 数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础古典数理逻辑(命题逻辑和谓词逻辑)。,13,第一章 命题逻辑,1.1 命题 1.2 命题联结词 1.3 命题公式 1.4 等价式 1.5 永真蕴含式 1.6 其他命题联结词 1.7 范 式 1.8 推论理论,14,第一章 命题逻辑,教学目的及要求： 深刻理解和掌握命题逻辑中基本概念和基本方法。 教学内容： 命题及表示、联结词、命题公式与翻译、真值表与等价公式、重

5、言式与蕴涵式、对偶与范式、推理理论。 教学重点： 命题逻辑中的基本概念和基本推理方法。 教学难点：推理理论。,15,1.1 命题,定义： 具有确定真假值的陈述句叫命题。 讨论定义： （1）命题可以是真的，或者是假的，但不能 同时为真又为假。 （2）命题分类： )原子命题（基本命题、本原命题）： 不能分解成为更简单的命题。 例：我是一位学生。,16,1.1 命题,)分子命题（复合命题）：若干个原子 命题使用适当的联结词所组成的新命题 例：我是一位学生和他是一位工人 （3）命题所用符号：常用大写个英文字母 表示命题。用、表示。 （4）命题中所有的“真”用“”表示， 命题中所有的“假”用“”表示。,

6、17,1.1 命题,例：判断下列语句是否为命题。 陈述句一般为命题 （1）十是整数。 （） （2）上海是一个村庄。（） （3）今天下雨。 （4）加拿大是一个国家。（） （5）是偶数而是奇数。 （6）她不是护士。 （7） （8）今天是星期天。,18,1.1 命题,命令句，感叹句，疑问句均不是命题。 （1）把门关上！ （2）你到哪里去？ 语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。 （3）他正在说谎。 （在命题逻辑中不讨论这类问题）,19,1.2 命题联结词,在命题演算中也有类似的日常生活中的联结词称做： “命题联结词”,下面先介绍五个常用的命题联结词。 否定词：（否定运算、非运算

7、） （）符号 ,读作“非”，“否定” 设命题为，则在的前面加否定词 ，变成，读做“的否定”或“非”,20,1.2 命题联结词,（）定义 P的真值表： （）举例： ：每一种生物均是动物。F ：有一些生物不是动物。T 这里不能讲成“每一种生物都不是动物”。 对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,21,1.2 命题联结词,合取词（“合取”、“积”、“与”运算） (1)符号 “” 设，为两个命题，则称与的合 取，读作：“与”、“与的合取”、“并 且”等。 (2)定义（由真值表给出）：,22,1.2 命题联结词,的真值表 ：,23,1.2 命题联结词,当且仅当和的真值均为“”

8、，则（） 的真值为“”。否则，其真值为“”。 注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的结果。,24,1.2 命题联结词,(3)举例： (a) P：王华的成绩很好 Q：王华的品德很好。 则：王华的成绩很好并且品德很好。 (b)P：我们去种树 Q：房间里有一台电视机 则：我们去种树与房间里有一台电视机。,25,1.2 命题联结词,(c) P：今天下大雨 Q：3+3=6 则：今天下大雨和3+3=6 由例(b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。,26,1.2 命题联结词,(d)P: 王大和王二是亲兄弟

9、。 Q: 他打开箱子然后拿出一件衣服来。 该语句不是合取联结词组成的命题。,27,1.2 命题联结词,析取词（或运算） （）符号“” 设、为二个命题，则（）称作与的“析取”，读作：“或”。 （）定义（由真值表给出）：,28,1.2 命题联结词,当且仅当、均为“”时，（）为“”。否则，其真值为“”,的真值表：,29,1.2 命题联结词,区分“可兼或”与“不可兼或（异或，排斥或）” “可兼或”即P或Q为“T”时（PQ）为“T” 例如： 灯泡有故障或开关有故障。 今晚写字或看书。 今天下雨或打雷。 以上例句均为可兼或。,30,1.2 命题联结词,“不可兼或”即P和Q的真值不同时，PQ为T。 （异或用

10、“”表示）,PQ的真值表：,31,1.2 命题联结词,例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。 以上两句均为不“可兼或”。,32,1.2 命题联结词,单条件联结词：（“蕴含”联结词、蕴含词） （）符号“”，读作：“如果则”、“蕴含” 、为二个命题，（）为新的命题，读作：“如果则”，“蕴含”，“仅当”， “当且”，“是的充分条件”。 （）定义,33,1.2 命题联结词,的真值表：,34,1.2 命题联结词,当为“”，为“”时，则（）为“”， 否则（）均为“”。 ：称为前件、条件、前提、假设 ：称为后件、结论。 （）举例： P：我拿起一本书 Q：我一口气读完了这本书,

11、35,1.2 命题联结词,PQ：如果我拿起一本书，则我一口气读完 了这本书。 (b) P：月亮出来了 Q：33=9 PQ：如果月亮出来了，则33=9。 通常称： (a)为形式条件命题前提和结果有某种形式 和内容上的联系。,36,1.2 命题联结词,(b)为实质条件命题前提和结果可以有联 系，也可以没有联系，只要满足单条件命 题的定义。 所以,是形式条件命题一定是实质条件命题,反 之不一定。“”是实质条件命题。 例：我买到了鱼；:我吃鱼。 ：如果我买到了鱼，则我吃鱼。 但“如果我没买到鱼，则我吃鱼”，在日常生活中不可能，但在单条件命题的定义中是允许的。,37,1.2 命题联结词,可以证明： Q

12、P 原命题 逆反命题 逆命题 反命题,38,1.2 命题联结词,列出真值表,由真值表得： 原命题逆反命题；逆命题反命题。,39,1.2 命题联结词,P Q的真值表: 每当和的真值相同时，则（）的真值为“”，否则（ ）的真值为“”。,40,1.2 命题联结词,（）举例： （a）设 ：ABC是等腰三角形 ：ABC有两只角相等 ：ABC是等腰三角形当且仅当 有两只角相等。,41,1.2 命题联结词,（b）下面均为等价联结词： 春天来了当且仅当燕子飞回来了。 平面上二直线平行，当且仅当二直线不相交。 当且仅当雪是白色的。,42,1.2 命题联结词,（）,中，、的地位是平等的，、 交换位置不会改变真值表

13、中的值。 （）当且仅当 仅当 当且 ,43,1.2 命题联结词,命题联结词在使用中的优先级 （）先括号内，后括号外 （）运算时联结词的优先次序为： （由高到低） （）联结词按从左到右的次序进行运算 （）最外层的括号一律均可省去 （）可写成,44,1.2 命题联结词,例 （）可省去括号 因为“”运算是可结合的。 而（）中的括号不能省去，因“”不满足结合律。,45,1.2 命题联结词,命题联结词小结： （1）五个联结词的含义与日常生活中的联结词 的含义大致相同。 （2）或”可分为可兼或（）和异或（ ） （不可兼或） （3） “”为一元运算，其余四个均为二元运算。,46,1.2 命题联结词,(4)

14、“”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。 (5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。,47,1.2 命题联结词,以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。 步骤如下： 找出各简单命题，分别符号化。 找出各联结词，把简单命题逐个联结起来。,48,1.2 命题联结词,例. 将下列命题符号化： （1）李明是计算机系的学生，他住在312室或 313室。 （2）张三和李四是朋友。 （3）虽然交通

15、堵塞，但是老王还是准时到达了 车站。 （4）只有一个角是直角的三角形才是直角三角 形。 （5）老王或小李中有一个去上海出差。,49,1.2 命题联结词,解： （1）首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 R：李明住在313室。 该命题符号化为：P（QR） （2）张三和李四是朋友。是一个简单句 该命题符号化为：P,50,1.2 命题联结词,（3）首先用字母表示简单命题。 P：交通堵塞。 Q：老王准时到达了车站。 该命题符号化为：PQ （4）首先用字母表示简单命题。 P：三角形的一个角是直角。 Q：三角形是直角三角形。 该命题符号化为：P Q,51,1.2 命题联结词,（5）首先用字母表示简单命题。 P：老王去上海出差。 Q：小李去上海出差。 该命题符号化为：P Q 也可符号化为：（PQ）（