离散数学(01).ppt

1,办公电话：88451128住宅电话：82495874移动电话子邮件：xaLiaohuxaLiaohu,2,离散数学方世昌编著售价：20圆电话机系人：刘杰由各个班班长统一定购，可优惠20%,3,“离散数学”是一门相对于“连续数学”而命名的数学分支，也叫“不连续的数学”“离散数学”主要研究一些不连续的数学问题。概率论与数理统计中的随机变量就有离散型和连续型之区分；离散数学是现代数学的一个重要分支，上世纪八十年代，计算机科学得到迅猛发展，,4,迫切需要一门适合计算机科学的相关数学课程，离散数学由此建立，它是研究离散量的结构及相互关系的学科。它充分描述了计算机科学离散性的特点，是计算机科学与技术的理论基础，所以又称为计算机数学。是计算机、软件专业本科生必修的专业基础课；到硕士研究生段还将开设“组合数学”；到博士研究生段还将开设“计算数学”；,5,“离散数学”一方面给后继课，如“数据结构”、“编译系统”、“操作系统”、“数据库原理”等，提供必要的科学基础；另一方面，通过学习离散数学，培养和提高了同学们的抽象思维和逻辑推理能力，为大家今后继续学习和工作打下坚实的数学基础。我们选用的这本教材是方世昌著离散数学（第二版），西安电子科技大学,6,出版社出版。是高等学校工科电子类规划教材精选系列，本书是一本非常有特点的教材。初版出版十三年后，经过全国众多学校的应用，于1996年改进后出第二版；本书力求把握与计算机科学密切相关的问题，通过精选的大量实例深入浅出地介绍了数理逻辑、集合论、二元关系、函数、代数系统、格与布尔代数*、图论等（我们省掉其中的“无限集合”一章）,7,与计算机科学技术密切相关的课题，既着重于各部分内容之间的紧密联系，又深入探讨各部分内容的概念、理论、算法和实际应用。因而本书既有深度，又有广度，相信学了本书，即能培养思维能力，又能培养理论联系实际的扎实功底。各章内容大致如下：第一章数理逻辑将形式逻辑符号化后进行逻辑推理，来,8,证明命题的真值，对命题公式运算。第二章集合研究集合基本概念、集合之间的运算关系以及特殊集合。第三章二元关系是研究“关系”的运算、复合、划分，以及“关系”上的闭包运算等问题。本章内容占全书很大比例。,9,第四章函数本章内容我们已经是第三次学习，重点放在函数的映射问题上。第六章代数是研究“代数系统”中元素与运算构成群、半群、环与域的有关问题。完全不同于中学、大一学习过的代数问题,10,第七章格与布尔代数*(在时间充足时学习)是研究“代数系统”中“格”以及“特殊格”的有关问题。是对“代数系统”的进一步研究。第八章图论是研究平面图形中“结点”与“连线”之间的关系，路径的优化、网络、匹配等问题，,11,离散数学课每周上课两次，4学时，安排15周，共60学时。考核方式：期末笔试占70%，平时作业占30%，每人准备两个作业本（或者用合页纸），写清班级、学号、姓名。每星期交一次作业，由班长统一收齐交到四楼“专业教研室”。交新作业时领回批改过的作业，按学校规定每次作业将登记，批改三分之一。,12,第一章数理逻辑1.1命题,逻辑学分为：“形式逻辑”和“数理逻辑”两个部分，他们的最大区别在于，“形式逻辑”允许有二意性而“数理逻辑”决不允许。“数理逻辑”就是将“形式逻辑”数学符号化；例如：陈述句“你吃饱了”在“形式逻辑”中可以理解为：,13,（1）你的确是吃的过饱了（2）你这个人的行为很无聊，如同吃饱饭撑的。这就是“形式逻辑”的二意性。一个陈述句可能有两个意识。命题是逻辑学中的基本单位；陈述语句是逻辑学的形式语言，断言是一个陈述语句。,14,1.1.1命题在特定的范围、时间、和空间内具有唯一确定的真假性。这样的陈述语句就是命题；一个命题是一个或真或假而不能两者都是的断言。如果命题是真,我们说它的真值为真，如果命题是假,我们说它的真值是假。,15,例1下述都是命题:(a)今天下雪;(c)2是偶数而3是奇数;(b)3+3=6;(d)陈胜起义那天,杭州下雨;(e)2008年人类将登上火星。以上命题,(a)的真值取决于今天的天气,(b)和(c)是真,(d)已无法查明它的真值,但它是或真或假,将它归属于命题。(e)目前尚未确定其真假,但它是有真值的,应归属于命题。,16,例2下述都不是命题:(a)x+y4。(c)真好啊!(b)x=3。(d)你去哪里?(a)和(b)是断言，不是命题,因为它的真值取决于x和y的值。(c)和(d)都不是断言,所以不是命题。自然语句中有陈述句、祈使句、疑问句、和感叹句等，其中能判断对错的只有陈述句。,17,例3一个人说:“我正在说谎”。他是在说谎还是在说真话呢?如果他讲真话,那么他所说的是真,也就是他在说谎。我们得出结论如果他讲真话,那么他是在说谎。另一方面,如果他是说谎,那么他说的是假;因为他承认他是说谎,所以他实际上是在说真话,我们得出结论如果他是说谎,那么他是讲真话。,18,从以上分析,我们得出他必须既非说谎也不是讲真话。这样,断言“我正在说谎”事实上不能指定它的真假,所以不是命题。这种断言叫悖论。例：学生甲在教师乙处学习法律，约定一年学成甲支付学费2000圆，同时规定在学生甲和教师乙在同一场官司中，师生分别作为控辩双方，若学生方获胜为学成的标准；,19,学业结束后学生拒绝支付学费，他认为：教师您可以通过打官司解决，如果教师官司打输了，我自然不支付学费，如果教师官司打嬴了，说明我还没有学成，根据先前的约定，我仍然可以不支付学费。这也是个悖论的例子，无论教师乙的怎样努力，在签合同时就被学生甲算计进去了。,20,若一个命题已不能分解成更简单的命题,则这个命题叫原子命题或本原命题。例1中(a),(b),(d),(e)都是本原命题,但(c)不是,因为它可写成“2是偶数”和“3是奇数”两个命题。命题和本原命题常用大写字母P,Q,R:表示。如用P表示“4是质数”,则记为：P:4是质数。,21,第一章数理逻辑1.2命题联结词,1.1.2命题联结词命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复合命题。例如：P:明天下雪,Q:明天下雨是两个命题,利用联结词“不”,“并且”,“或”等可分别构成新命题:,22,“明天不下雪”;“明天下雪并且明天下雨”;“明天下雪或者明天下雨”等。即：“非P”;“P并且Q”;“P或Q”等。,23,在代数式x+3中,“x“,“3”叫运算对象,代数中的运算对象分有“变量(x)”和“常量(3)”；命题演算同样对原子命题有“变元(P)”和“常元(真、假)”之分；“+”叫运算符,x+3表示运算结果。在命题演算中,也用同样术语。联结词就是命题演算中的运算符,叫逻辑运算符或叫逻辑联结词。常用的有以下5个。,24,1.否定词设P表示命题,那么“P不真”是另一命题,表示为P,叫做P的否定,读做“非P”。从排中律知:如果P是假,则P是真,反之亦然。所以否定词可以如下表所示定义。归纳为：非真即假，非假即真。,25,这张表叫真值表,定义运算符的真值表,指明如何用运算对象的真值,来决定一个应用运算符的命题的真值。真值表的左边列出运算对象的真值的所有可能组合,结果命题的真值列在最右边的一列。为了便于阅读,我们通常用符号T(true)或1代表真,符号F(false)或0代表假。一般在公式中采用T和F,在真值表中采用1和0。,26,例4(a)P:4是质数。P:4不是质数。或4是质数,不是这样。(b)Q:这些都是男同学。Q:这些不都是男同学。(翻译成“这些都不是男同学”是错的。)原命题为p，非命题p一般的理解为：并非p；即在命题前加“并非”二字。,27,例如：p：上海是一个处处都清洁的城市；p：并非上海是一个处处都清洁的城市；而不能写成：上海是一个处处都不清洁的城市；2.合取词如果P和Q是命题,那么“P并且Q”也是一命题,记为PQ,称为P和Q的合取,读做“P与Q”或“P并且Q”。运算符定义如下表所示:从真值表可知PQ是真当且仅当P和Q俱真。,28,归纳为：p，q同真时pq为真，其余为假。类似集合运算中的：“交，”,例5P:王华的成绩很好,Q:王华的品德很好。PQ:王华的成绩很好并且品德很好。,29,3.析取词如果P和Q是命题,则“P或Q”也是一命题,记作PQ,称为P和Q的析取,读做“P或Q”。运算符定义如右表所示。从真值表可知PQ为真,当且仅当P或Q至少有一为真。归纳为：p，q同假时pq为假，其余为真。看的出：合取与析取有对偶的关系。,30,析取类似集合运算中的：“并，”,例6(a)P:今晚我写字,Q:今晚我看书。PQ:今晚我写字或看书,31,(b)P:今年是闰年;Q:今年她生孩子。PQ:今年是闰年或者今年她生孩子。逻辑运算符可以将两个无关的命题连接成一新命题。“或”字常见的含义有两种:一种是“可兼或”,如上例中的或,它不排除今晚既看书又写字这种情况。,32,一种是“排斥或”,例如“人固有一死,或重于泰山,或轻于鸿毛”中的“或”,它表示非此即彼,不可兼得。运算符表示可兼或,排斥或以后用另一符号表达。联结词是自然语言中的“或”、“或者”的逻辑抽象，而在自然语言中，“或”是多义的，可列表如下：,33,“可兼或”与“排斥或”的联系与区别,34,4.蕴涵词(涵常简写作含)如果P和Q是命题,那么“P蕴含Q”也是命题,记为PQ,称为蕴含式,读做“P蕴含Q”或“如果P,那么Q”，是典型的“因果关系”。运算对象P叫做前提,假设或前件,而Q叫做结论或后件。逻辑推理经常用到这种“因果关系”；运算符定义如下表所示。命题PQ是假,当且仅当P是真而Q是假。,35,归纳为：条件为真，结论为假时pq为假，其余为真。我们经常把“”（条件命题）简称为：单条件命题。以区别后面的双条件命题。,36,例7(a)P:天不下雨,Q:草木枯黄。PQ:如果天不下雨,那么草木枯黄。(b)R:G是正方形,S:G的四边相等。RS:如果G是正方形,那么G的四边相等。(c)W:桔子是紫色的,V:大地是不平的WV:如果桔子是紫色的,那么大地是不平的。,37,在日常生活中用蕴含式来断言前提和结论之间的因果或实质关系,如上例(a)和(b),这样的蕴含式叫形式蕴含,然而,在命题演算中,一个蕴含式的前提和结论并不需要有因果和实质联系,这样的蕴含式叫实质蕴含,如上例(c)中,桔子的颜色和大地的外形之间没有因果和实质关系存在,但蕴含式WV是真,38,因为前提是假而结论是真,这就是我们常说的”善意推断”。即：条件为假时，条件命题永真。例如：如果太阳从西边出来，那么每个星期我们就休息5天。这个命题的条件是假的，无论后面的结论是什么，整个条件命题是真的。,39,蕴含式PQ可以用多种方式陈述:“若P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”;“P仅当Q”等。,如上例(b)中的RS可陈述为“G是正方形的必要条件是它的四边相等”。,40,给定原命题PQ,我们把：QP,叫做命题PQ的逆命题PQ,叫做命题PQ的否命题QP，叫做命题PQ的逆否命题.其中原命题与逆否命题，逆命题与否命题是同真值的。,41,例如：P:如果天下雨，Q:那么地上湿。PQ（真）逆命题：如果地上湿，那么天下雨。否命题：如果天不下雨，那么地上不湿。这样就不一定为真，也可能是洒水车刚刚过去洒过水了。但逆否命题：如果地上不湿，那么天没下雨。是真的；,42,5.等值词如果P和Q是命题,那么“P等值于Q”也是命题,记为PQ,称为等值式,读做“P等值于Q”。运算符定义如下表所示。归纳为：p、q同真、假时pq为真，其余为假。,43,把蕴含式和等值式的真值表加以比较,易知如果PQ是真,那么PQ和QP俱真;反之如果PQ和QP俱真,那么PQ是真。由于这些理由,PQ也读做“P是Q的充要条件”或“P当且仅当Q”。如p和q是命题，复合命题p当且仅当q有时简称为双条件命题，且表为pq。,44,从以上5个定义可看出,联结词之意义由其真值表唯一确定,而不由命题的含义确定。使用以上5个联结词,可将一些语句翻译成逻辑式。翻译时为了减少圆括号(一般不用其它括号)的使用,我们作以下约定，运算符结合力的强弱顺序为;，,（同于四则运算中的次序）,45,凡符合此顺序的,括号均可省去。相同的运算符,按从左至右次序计算时,括号可省去最外层的圆括号可以省去。例如:(PQ)R)(RP)Q)可写成：(PQR)RPQ但有时为了看起来清楚醒目,也可以保留某些原可省去的括号。,46,例8(a)设P表示“他有理论知识”,Q表示“他有实践经验”则“他既有理论知识又有实践经验”可译为:PQ。(b)设P:明天下雨,Q:明天下雪,R:我去学校。则：(i)“如果明天不是雨夹雪则我去学校”可写成;(PQ)R;,47,(ii)“如果明天不下雨并且不下雪则我去学校”可写成;PQR;(iii)“如果明天下雨或下雪则我不去学校”可写成;PQR;iv)“明天,我将雨雪无阻一定去学校”可写成;(PQR)(PQR)(PQR)(PQR),48,(v)“当且仅当明天不下雪并且不下雨时我才去学校”可写成;PQR;(c)用逻辑符表达“说小学生编不了程序,或说小学生用不了个人计算机,那是不对的”。设P:小学生会编程序,Q:小学生会用个人计算机。则上句可译为：(PQ),49,(d)用逻辑符表达“若不是他生病或出差了,我是不会同意他不参加学习”。设P:他生病了,Q:他出差了,R:我同意他不参加学习,则上句可译为(PQ)R或PQR即：我同意他不参加学习的充要条件的他生病了或者出差了,50,翻译时要按逻辑关系翻译,而不能凭字面翻。例如,设P:林芬做作业,Q:林芳做作业,则“林芬和林芳同在做作业”可译为PQ,但“林芬和林芳是姐妹”就不能翻释成两个命题的合取,它是一个原子命题。1.1.3命题变元和命题公式通常,如果P代表真值未指定的任意命题,51,我们就称P为命题变元;如果P代表一个真值已指定的命题,我们就称P为命题常元。但由于在命题演算中并不关心具体命题的涵义,只关心其真假值。因此,我们可以形式地定义它们。以“真”,“假”为其变域的变元,称为命题变元;T(1)和F(0)称为命题常元。单个命题变元和命题常元叫原子公式。由以下形成规则,52,生成的公式叫命题公式(简称公式):(1)单个原子公式是命题公式。(2)如果A和B是命题公式,则(A),(AB),(AB),(AB),(AB)是命题公式。(3)只有有限步应用条款(1)和(2)生成的公式才是命题公式。这种定义叫归纳定义,也叫递归定义。由这种定义产生的公式也叫合式公式。,53,一个命题公式（合式公式）如同一个函数表达式，由命题变元和命题常元取代函数式中的变量和常量，由五个命题联结词取代函数式中的各种运算。命题公式的