《离散数学课件(第1章)》由会员分享，可在线阅读，更多相关《离散数学课件(第1章)（96页珍藏版）》请在金锄头文库上搜索。
1、离散数学教案,计算机科学与技术学院课程学时：64 主 讲：宋 成,河南理工大学电子教案,第0篇：引言,课程的性质 离散数学与计算机 课程的主要内容 课程的目的 教学要求 学习方法 教材和参考书 考核方式,引言,一、课程的性质离散数学（又称计算机数学）是现代数学的重要分支， 是计算机专业核心基础课程之一。,二、离散数学与计算机 计算机开辟了脑力劳动机械化和自动化的新纪元。 计算机的诞生，人们就要为它进一步发展创建新的理论，就需要寻找新的数学工具。例：为了描述新开拓的应用领域中的各种数据的结构，就需要适宜的数学工具。,引言,引言,计算机各分支领域中的理论问题交错的使用着现代数学的各种不同的论题 因
2、为计算机系统从本质上说是一种离散性的结构，它的许多性质可以在有限数学系统的框架中来理解，从中选出一些必要的而且是基本的主干论题称为离散数学 因此，离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科,引言,离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，是计算机科学与技术专业的核心骨干课程，也是计算机专业考研的重要内容。 它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。因此，它充分描述了计算机科学离散性的特征,引言,三、课程的内容离散数学课程的主要内容可以分为四个部分数理逻辑，包括命题逻辑和谓词逻辑（教材第一
3、、二章）集合论，包括集合与关系和函数（教材第三、四章）代数系统，包括代数系统的一般概念，几类典型的代数系统和格（教材的第五、六章）图论，包括图的基本概念，几种特殊的图（教材的第七章）,引言,四、学习该课程的目的 为了学习计算机的后续课程，如数据结构、操作系统、编译原理、数据库原理、形式语言及自动机、软件工程与方法学、计算机网络与人工智能、高级程序设计语言、算法分析、逻辑设计、系统结构、容错技术等提供了必要的数学基础，为阅读计算机文章作充分的数学准备,引言,数理逻辑：人工智能、数据库、形式语言与自动机、高级程序设计语言 集合论：信息结构与检索、数据结构 代数系统：开关理论、逻辑设计和程序理论、语
4、法分析 图论：可计算性理论、计算机网络、数据结构 通过学习离散数学可以培养和提高自己的抽象思维和逻辑推理能力，获得解决实际问题的能力，为以后的软硬件学习和研究开发工作打下坚实的数学基础,引言,五、教学要求通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用离散数学中的一些基本概念、基本思想、基本方法等,引言,六、学习方法 本课程有三个特点 课时少，内容多且抽象 定义、定理多本课内容=定义+定理+例题 课外作业较多 为了学好这门课，特提出四点要求 课前预习，课中互动，课后复习 弄懂定义、定理，弄懂例题，加深对定义、定理的理解 在复习的基础上，做好课外作业，同学之间可以讨论，但要弄懂、弄通 做
5、好课堂笔记,引言,七、教材与参考书 离散数学左孝凌等著 上海科学技文献出版社 离散数学-理论.分析.题解左孝凌等著 上海科学技文献出版社 离散数学及其应用魏雪丽等编著 机械工业出版社 Discrete Mathematics and Its Applications(英文版)（美）Kenneth H.Rosen著 机械工业出版社,引言,八、考核方式基本考试成绩占：70%平时成绩占：30% 做两点说明： 考试类容以课堂上讲的为范围； 课后布置的作业，希望大家认真完成 为搞好教学，需要双方共同的努力,逻辑学：研究思维形式及思维规律的科学。 逻辑学分为两类： 辩证逻辑：研究事物发展的客观规律； 形式
6、逻辑：对思维的形式结构和规律进行研究。,第一篇：数理逻辑,数理逻辑：用数学的方法研究概念、判断和推理的科学，属于形式逻辑 数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础古典数理逻辑（命题逻辑和谓词逻辑）。,第一章：命题逻辑,1.1 命题 1.2 命题联接词 1.3 命题公式与翻译 1.4 真值表与等价公式 1.5 重言式与蕴含式 1.6 其他连接词 1.7 对偶与范式 1.8 推理理论,第一章：命题逻辑,教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法 教学类容：命题及表示、连接词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对
7、偶与范式、推理理论 教学重点：命题逻辑中的基本概念和基本推理方法教学难点：推理理论,第一章：命题逻辑,1.1 命题定义：在数理逻辑中把能够确定真假值的陈述句 叫命题 讨论定义： 只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题； 一个语句虽是陈述句,但不能判断真假不是命题； 命题可以是真的，也可以是假的，但不能同时为真又为假，为真的命题为真命题，为假的命题为假命题； 虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以；,第一章：命题逻辑,5. 命题的分类 原子命题不能分解成更简单的命题，如：我是一位学生 复合命题若干个原子命题使用适当的连接
8、词组成的新命题，如：我是一位学生和他是一位工人 6. 命题所用符号（标识符）：常用大写26个英文字母表示命题。 用A、B、CZ表示或带下表的大写字母等 7. 命题中所有的“真”用“T”或“1”表示命题中所有的“假”用“F”或“0”表示,第一章：命题逻辑,例：判断下列命题是否为命题 上海是个小村庄。 存在外星人。 北京是中国的首都。 4是素数或6是素数。 今天你吃了吗？ 禁止吸烟！ 天气多好啊！ 11+1=100 我正在说谎。,是假命题 命题（待定） 真命题 假命题 不是命题 不是命题 不是命题 视上下文而定 悖论（命题逻辑中不讨论此类问题）,如果我的确正在撒谎，那么这句话是真的，所以我不在撤谎
9、，如果我不在撒谎，那么这句话是假的，因而我正在撒谎 。 只给不自己刮胡子的人刮胡子,第一章：命题逻辑,如果命题标识符表示一个具体、确定的命题，称为命题常量。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。 命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。 如果命题变元表示原子命题时，该命题变元称为原子变元。,1.2 命题联接词在命题演算中，也有类似日常生活中的联接词，称为“逻辑联接词”或“命题联接词”。常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。 1. 否定联接词（否定、非） （1）定义：设P为命
10、题，则P的否定是一个复合命题，记作： P ，读作“非P”或“P的否定”。若P为T，则 P为F；若P为F，则 P的真值为T。,第一章：命题逻辑,第一章：命题逻辑,（2）P和P的关系（真值表）如表1.1所示：,联结词“”也可以看作逻辑运算，它是一元运算,第一章：命题逻辑,（3）举例：P：王强是一名大学生。P：王强不是一名大学生。Q：每一种生物都是动物Q：有些生物不是动物或不是每一种生物都是动物 注：对量化命题的否定，除了对动词进行否定外，同时对量化词也要加以否定,第一章：命题逻辑,2. 合取联接词（与、积） （1）定义：设P和Q均为命题，则P和Q的合取是一个复合命题，记作PQ，读作“P与Q”或“P
11、合取Q”。定义为：当且仅当P和Q均为T时，PQ的才为T。 （2）联结词“”的真值表如表1.2所示。联结词“”也可以看成逻辑运算，它是二元逻辑运算。,第一章：命题逻辑,（3）举例：（a）设 P：2008年在北京举办奥运会。Q：中国是世界四大文明古国之一。,则PQ：2008年在北京举办奥运会 并且中国是世界四大文明古国之一。,（b） 设P：王华的成绩很好。Q：王华的品德很好则PQ：王华的成绩很好并且品德很好,（c） 设P：我们去种树。Q：房间里有台电视机则PQ：我们去种树与房间里有台电视机,注：由例（a）(c)可见,在日常生活中，合取词用在两个有关系的命题之间，而在逻辑学中，可以用在两个毫不相干的
12、两个命题中,第一章：命题逻辑,3. 析取联接词 （1）定义：设P和Q均为命题，则P和Q的析取是一个复合命题，记作PQ，读作“P或Q”或者“P析取Q”。定义为：当且仅当P和Q均为F时，PQ才为F。 （2）联结词“”的真值表如表1.3所示。联结词“” 可看成二元逻辑运算。,第一章：命题逻辑,“”与汉语中的“或”相似，但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。 （3）举例：,在家电视上看这场杂技或在剧场里看这 场杂技。(不可兼) 灯泡有故障或开关有故障。(可兼, “”是可兼或) 今天下雨或打雷(可兼或),注：不可兼或（异或）通常用“”表示，P和Q的真值不同时PQ为T，真值表如表1.4
13、,第一章：命题逻辑,4. （单）条件联接词 （1）定义：设P和Q均为命题，其条件命题是个复合命题，记为：PQ。读作“如果P则Q”，“P蕴含Q”，“P仅当Q”“Q当且P”或“P是Q的充分条件” 。定义为：当且仅当P为T，Q为F时，PQ才为F。P称为条件命题PQ的前件、条件、前提、假设，Q称为条件命题PQ的后件、结论。,（2）联结词“”的真值表如表1.5所示。 联结词“” 也可看成二元逻辑运算。,第一章：命题逻辑,联结词“”与汉语中的“如果，那么”或“若，则”相似，但又是不相同的。 （3）举例： 设P：小王努力学习。Q：小王学习成绩优秀。则PQ：如果小王努力学习，那么他的学习成绩就优秀。 P：月亮
14、出来了。Q：3*3=9。则PQ：如果月亮出来了，则3*3=9,通常称：a为形式条件命题前提和结果有某种形式和内容上的联系b为实质条件命题前提和结果可以有联系，也可以没有联系，只要满足条件命题的定义 所以，形式条件命题一定是实质条件命题，反之不一定。有些实质条件命题在日常生活中不可能，但是在条件命题的定义中是允许的。,第一章：命题逻辑,5. 双条件联接词 （1）定义：设P和Q均为命题，其复合命题PQ称为双条件命题，读作：“P双条件Q”或者“P当且仅当Q”。定义为：当且仅当P和Q的真值相同时，PQ为T。 （2）联结词“”的真值表如表1.6所示。,双条件联结词表示的是一个充分必要关系，与前面所述相同
15、，也可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。,第一章：命题逻辑,（3）举例：设P：张华是三好学生。Q：张华德、智、体全优秀。则PQ：张华是三好学生当且仅当德、智、体全优秀。注：在双条件联接词中，P和Q的地位是平等的，即P、Q交换位置不会改变真值表中的值P当且仅当Q PQP当且Q Q PP仅当Q PQ,第一章：命题逻辑,命题联接词小结 命题联接词在使用中的优先级 先括号内，后括号外 运算时的优先次序依次为：、 、 、 、 联接词按从左到右的次序进行运算 最外层的括号一律可以省去 五个联接词的含义与日常生活中的联接词含义大致相同 “或”可分为可兼（ ）或和不可兼或（） （异或）
16、“”为一元运算，其余的为二元运算 “”分形式条件命题和实质条件命题 命题符号化的步骤： 找出各简单命题，分别符号化 找出各联接词，把简单命题逐个联接起来,第一章：命题逻辑,1.3 命题公式与翻译 约定： （1）我们只注意命题的真假值，而不再注意命题的汉语意义。 （2）对命题的联接词，我们只注意真值表的定义，不注意他在日常生活中的含义 命题公式（合式公式） 命题常元：表示确定的命题 T，F 。 命题变元：以真假为其变域的变元，或没有指定真值的命题，常用大写英文字母表示 命题公式：由命题变元、常元、联接词、括号以规则的格式联接起来的字符串。,第一章：命题逻辑,【定义】按下列规则可生成命题公式： 单个命题变元和常元是命题公式。 如果A是命题公式，那么A是命题公式。 如果A和B是命题公式，那么(AB)、(AB)、 (AB)和(AB)是命题公式。 当且仅当有限次地应用了、所得到的命题变元、联接词和括号的符号串是命题公式。,
