离散数学研究对象市公开课一等奖百校联赛特等奖课件.pptx

离散数学研究对象离散数学研究对象因为数字电子计算机是一个离散结构，它只能处理离散或离散化了数量关系，所以，不论计算机科学本身，还是与计算机科学及其应用亲密相关当代科学研究领域，都面临着怎样对离散结构建立对应数学模型；又怎样将已用连续数量关系建立起来数学模型离散化，从而可由计算机加以处理。离散数学(DiscreteMathematics)是计算机专业一门主要基础课。它所研究对象是离散数量关系和离散结构数学结构模型。第1页离散数学主要内容离散数学主要内容到当前为止，离散数学所研究准确范围并没有严格定义，它和其它许多纯粹数学以及应用数学分支之间有着广泛交叉和相互渗透。不过作为给计算机专业本科生开设一门专业基础课，其内容相对来说较为明确，主要包含数理逻辑、集合论、代数系统以及图论等几部分。离散数学是数字电路、编译原理、数据结构、操作系统、数据库系统、算法分析与设计、人工智能、计算机网络等专业课程基础。第2页数理逻辑数理逻辑是用数学方法研究关于推理、证实等问题学科，也叫做符号逻辑。它本质是研究怎样经过利用纯粹公理系统和符号演算以及推理方法来代替人们思维中逻辑推理过程，并由此将整个数学建立在这么一个逻辑基础之上。历史上很多数学家努力和推进，尤其是莱布尼茨、布尔、希尔伯特、罗素、图灵、哥德尔等人工作，部分地实现了这一形式化数学梦想，但同时也发觉了数学基础本身存在巨大困难。第3页集合论集合论是德国著名数学家康托尔于19世纪末创建。康托对于无穷集元素个数问题进行了卓越研究，引领数学研究进入了一个全新领域。他提出用一一对应准则来比较无穷集元素个数，将元素间能建立一一对应集合称为个数相同（也称作等势）。并证实了无穷集势之间存在着差异，有着不一样数量级，可分为不一样层次。问题：试判断自然数集合x|x=1,2,3,和奇数集合x|x=1,3,5,哪个集合元素个数多？第4页图论“图论”是数学一个分支，它以图为研究对象。图论中图是由若干给定点及连接两点线所组成图形，这种图形通惯用来描述一些事物之间某种特定关系，用点代表事物，用连接两点线表示对应两个事物间含有这种关系。图论起源于著名柯尼斯堡七桥问题。欧拉在1736年处理了这个问题，他用抽象分析法将这个问题化为第一个图论问题。欧拉证实了柯尼斯堡七桥问题是无解，并推广了这个问题，给出了对于一个给定图能够某种方式走遍判定法则。这使得欧拉成为图论及拓扑学创始人。第5页学习离散数学方法学习离散数学方法1.概念定理多：首先要准确严格地掌握好概念和术语，正确了解他们内涵和外延。因为公理、定理或定律基石都是概念，只有正确地了解了概念，才能把握定理实质，熟练地将公理、定理应用于处理问题。2.抽象思维多：完全、准确掌握一个概念好主意是首先要深刻了解概念内涵，然后举一些属于和不属于该概念外延正反两方面实例。假如对一些似是而非例子也能区分话，应该说这个概念正真理了解了。3.只需要中学数学基础。第6页第一部分数理逻辑先看著名物理学家爱因斯坦出过一道题：一个土耳其商人想找一个十分聪明助手帮助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色，三顶是黑色，现在，我把灯关掉，而且把帽子摆位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴帽子是什么颜色。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴是一顶红帽子，其中一个人便喊道：“我戴是黑帽子。”第7页请问这个人说得对吗？他是怎么推导出来呢？要回答这么问题，实际上就是看由一些诸如“商人戴是红帽子”这么前提能否推出“猜出答案应试者戴是黑帽子”这么结论来。这又需要经历以下过程：(1)什么是前提？有哪些前提？(2)结论是什么？(3)依据什么进行推理？(4)怎么进行推理？下面第一章，第二章回答第一个问题。第三章回答第二、三个问题。第8页下列图给出了逻辑部分知识体系第9页例1.1判断以下句子是否为命题。(1)4是素数。(2)是无理数。(3)x大于y。(4)月球上有冰。(5)21元旦是晴天。(6)大于吗？(7)请不要吸烟！(8)这朵花真漂亮啊！(9)我正在说假话。能判定真假陈说句称为命题命题作为命题陈说句所表示判断结果称为命题真值真值，真值只取两个值：真或假。真值为真命题称为真命题真命题，真值为假命题称为假命题假命题。任何命题真值都是唯一。判断给定句子是否为命题，应该分两步：首先判定它是否为陈说句，其次判断它是否有唯一真值。第10页解:本题(9)个句子中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因而这3个句子都不是命题。剩下6个句子都是陈说句，但(3)无确定真值，依据x,y不一样取值情况它可真可假，即无唯一真值，因而不是命题。若(9)真值为真，即“我正在说假话”为真，也就是“我正在说真话”，则又推出(9)真值应为假；反之，若(9)真值为假，即“我正在说假话”为假，也就是“我正在说假话”，则又推出(9)真值应为真。于是(9)既不为真又不为假，所以它不是命题。像(9)这么由真推出假，又由假推出真陈说句称为悖论。凡是悖论都不是命题。本例中，只有(1)，(2)，(4)，(5)是命题。(1)为假命题，(2)为真命题。即使今天我们不知道(4)，(5)真值，但它们真值客观存在，而且是唯一，未来总会知道(4)真值，到21元旦(5)真值就真相大白了。第11页罗素悖论罗素悖论一天，萨维尔村剪发师挂出一块招牌：“村里全部不自己剪发男人都由我给他们剪发，我也只给这些人剪发。”于是有些人问他：“您头发由谁理呢?”剪发师顿时哑口无言。因为，假如他给自己剪发，那么他就属于自己给自己剪发那类人。不过，招牌上说明他不给这类人剪发，所以他不能自己理。假如由另外一个人给他剪发，他就是不给自己剪发人，而招牌上明明说他要给全部不自己剪发男人剪发，所以，他应该自己理。由此可见，不论怎样推论，剪发师所说话总是自相矛盾。第12页有趣对话。甲对乙说：“你会回答我不对，对不对？请用对或不对往返答！”第13页例1.2是有理数是不对；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。全是命题。定义定义1.1设p为命题，复合命题“非p”(或“p否定”)称为p否否定式定式,记作p，符号称作否定联结词否定联结词。并要求p为真当且仅当p为假。定义定义1.2设p,q为二命题，复合命题“p而且q”(或“p与q”)称为p与q合取式合取式，记作pq，称作合取联结词合取联结词。并要求pq为真当且仅当p与q同时为真。定义定义1.3设p，q为二命题，复合命题“p或q”称作p与q析取式析取式，记作pq，称作析取联结词析取联结词。并要求pq为假当且仅当p与q同时为假。注意注意：按定义1.3在析取式pq中，若p，q都为真，则pq为真。“或”还有另外一个使用方法：当p，q都为真时，析取起来为假。前者称为相容或相容或，后者称为排斥或排斥或(排异或排异或)。第14页例1.3将以下命题符号化。(1)张晓静爱唱歌或爱听音乐。(2)张晓静是江西人或安徽人。(3)张晓静只能挑选202或203房间。解解在解题时，先将原子命题符号化。(1)p：张晓静爱唱歌。q：张晓静爱听音乐。显然(1)中“或”为相容或，即p与q能够同时为真，符号化为pq.第15页(2)r：张晓静是江西人。s：张晓静是安徽人。易知，(2)中“或”应为排斥或，但r与s不能同时为真，因而也能够符号化为rs.(3)t：张晓静挑选202房间。u：张晓静挑选203房间。由题意可知，(3)中“或”应为排斥或。t，u联合取值情况有四种：同真，同假，一真一假(两种情况)。假如也符号化为tu，张晓静就可能同时得到两个房间，这违反题意。因而不能符号化为tu.怎样到达只能挑一个房间要求呢？能够使用多个联结词，符号化为(tu)(tu)第16页定义定义1.4设p，q为二命题，复合命题“假如p，则q”称作p与q蕴涵式蕴涵式，记作pq，称作蕴涵联结词蕴涵联结词。并要求pq为假当且仅当p为真q为假。注意：在使用联结词时，要尤其注意以下几点：1在自然语言里，尤其是在数学中，q是p必要条件有许多不一样叙述方式。比如，“只要p，就q”，“因为p，所以q”，“p仅当q”，“只有q才p”，“除非q才p”，“除非q，不然非p”等等。以上各种叙述方式表面看来有所不一样，但都表示是q是p必要条件，因而所用联结词均应符号化为，上述各种叙述方式都应符号化为pq.2在自然语言中，“假如p，则q”中前件p与后件q往往含有某种内在联络。而在数理逻辑中，p与q能够无任何内在联络。3在数学或其它自然科学中，“假如p，则q”往往表示是前件p为真，后件q也为真推理关系。但在数理逻辑中，作为一个要求，当p为假时，不论q是真是假，pq均为真。也就是说，只有p为真q为假这一个情况使得复合命题pq为假。第17页定义定义1.5设p，q为二命题，复合命题“p当且仅当q”称作p与q等价式等价式，记作pq，称作等价联结词等价联结词。并要求pq为真当且仅当p与q同时为真或同时为假。以上定义了五种最基本、最惯用、也是最主要联结词，将它们组成一个集合，称为一个联结词集。其中为一元联结词，其余都是二元联结词。第18页通惯用1表示真，用0表示假，复合命题真假值如表1.1。表1.1基本复合命题真值联结词能够嵌套使用，在嵌套使用时，要求以下优先次序：()，对于同一优先级联结词，先出现者先运算。第19页例例1.7令p：北京比天津人口多。q：2+24.r：乌鸦是白色。求以下复合命题真值：(1)(pq)(pq)r(2)(qr)(pr)(3)(pr)(pr)解解p，q，r真值分别为1，1，0，轻易算出(1)，(2)，(3)真值分别为1，1，0。第20页