离散数学的研究对象-下一代互联网应用技术研发中心ppt课件

1、离散数学的研讨对象 由于数字电子计算机是一个离散构造，它只能处置离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其运用亲密相关的现代科学研讨领域，都面临着如何对离散构造建立相应的数学模型；又如何将已用延续数量关系建立起来的数学模型离散化，从而可由计算机加以处置。 离散数学(Discrete Mathematics)是计算机专业的一门重要根底课。它所研讨的对象是离散数量关系和离散构造数学构造模型。 离散数学的主要内容 到目前为止，离散数学所研讨的准确范围并没有严厉的定义，它和其它许多纯粹数学以及运用数学分支之间有着广泛的交叉和相互浸透。但是作为给计算机专业本科生开设的一

2、门专业根底课，其内容相对来说较为明确，主要包括数理逻辑、集合论、代数系统以及图论等几部分。 离散数学是数字电路、编译原理、数据构造、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程的根底。数理逻辑 数理逻辑是用数学的方法研讨关于推理、证明等问题的学科，也叫做符号逻辑。它的本质是研讨如何经过利用纯粹的公理系统和符号演算以及推理方法来替代人们思想中的逻辑推理过程，并由此将整个的数学建立在这样一个逻辑根底之上。 历史上诸多数学家的努力和推进，尤其是莱布尼茨、布尔、希尔伯特、罗素、图灵、哥德尔等人的任务，部分地实现了这一方式化数学的梦想，但同时也发现了数学根底本身存在的宏大困难。

3、集合论 集合论是德国著名数学家康托尔于19世纪末创建的。康托对于无穷集元素个数问题进展了杰出的研讨，引领数学研讨进入了一个全新的领域。他提出用一一对应准那么来比较无穷集元素的个数，将元素间能建立一一对应的集合称为个数一样也称作等势。并证明了无穷集的势之间存在着差别，有着不同的数量级，可分为不同的层次。 问题：试判别自然数集合x|x=1,2,3,和奇数集合x|x=1,3,5,哪个集合的元素个数多？图论 “图论是数学的一个分支，它以图为研讨对象。图论中的图是由假设干给定的点及衔接两点的线所构成的图形，这种图形通常用来描画某些事物之间的某种特定关系，用点代表事物，用衔接两点的线表示相应两个事物间具有

4、这种关系。 图论来源于著名的柯尼斯堡七桥问题。欧拉在1736年处理了这个问题，他用笼统分析法将这个问题化为第一个图论问题。欧拉证明了柯尼斯堡七桥问题是无解的，并推行了这个问题，给出了对于一个给定的图可以某种方式走遍的断定法那么。这使得欧拉成为图论及拓扑学的开创人。学习离散数学的方法 概念定理多：首先要准确严厉地掌握好概念和术语，正确了解他们的内涵和外延。由于公理、定理或定律的基石都是概念，只需正确地了解了概念，才干把握定理的本质，熟练地将公理、定理运用于处理问题。笼统思想多：完全的、准确的掌握一个概念的好主意是首先要深化了解概念的内涵，然后举一些属于和不属于该概念外延的正反两方面的实例。假设对

5、一些似是而非的例子也能区分的话，应该说这个概念正真理了解了。 只需求中学数学根底 。 第一部分 数理逻辑 先看著名物理学家爱因斯坦出过的一道题： 一个土耳其商人想找一个非常聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他翻开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，如今，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在本人头上，在我开灯后，请他们尽快说出本人头上戴的帽子是什么颜色的。说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯翻开。这时，那两个应试者

6、看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。请问这个人说得对吗？他是怎样推导出来的呢？ 要回答这样的问题，实践上就是看由一些诸如“商人戴的是红帽子这样的前提能否推出“猜出答案的应试者戴的是黑帽子这样的结论来。这又需求阅历如下过程： (1) 什么是前提？有哪些前提？ (2) 结论是什么？ (3) 根据什么进展推理？ (4) 怎样进展推理？ 下面的第一章，第二章回答第一个问题。第三章回答第二、三个问题。 以下图给出了逻辑部分的知识体系 例1.1 判别以下句子能否为命题。 (1) 4是素数。 (2) 是无理数。 (3) x大于y。 (4) 月球上有冰。 (5) 2100年元旦是

7、晴天。 (6) 大于吗？ (7) 请不要吸烟！ (8) 这朵花真美丽啊！ (9) 我正在说假话。能断定真假的陈说句称为命题作为命题的陈说句所表达的判别结果称为命题的真值，真值只取两个值：真或假。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值都是独一的。 判别给定句子能否为命题，应该分两步：首先断定它能否为陈说句，其次判别它能否有独一的真值。解: 此题的(9)个句子中，(6)是疑问句，(7)是祈使句，(8)是感慨句，因此这3个句子都不是命题。剩下的6个句子都是陈说句，但(3)无确定的真值，根据x,y的不同取值情况它可真可假，即无独一的真值，因此不是命题。假设(9)的真值为真，

8、即“我正在说假话为真，也就是“我正在说真话，那么又推出(9)的真值应为假；反之，假设(9)的真值为假，即“我正在说假话为假，也就是“我正在说假话，那么又推出(9)的真值应为真。于是(9)既不为真又不为假，因此它不是命题。像(9)这样由真推出假，又由假推出真的陈说句称为悖论。凡是悖论都不是命题。本例中，只需(1)，(2)，(4)，(5)是命题。(1)为假命题，(2)为真命题。虽然今天我们不知道(4)，(5)的真值，但它们的真值客观存在，而且是独一的，未来总会知道(4)的真值，到2100年元旦(5)的真值就真相大白了。罗素悖论一天，萨维尔村理发师挂出一块招牌：“村里一切不本人理发的男人都由我给他们

9、理发，我也只给这些人理发。于是有人问他：“您的头发由谁理呢?理发师顿时哑口无言。由于，假设他给本人理发，那么他就属于本人给本人理发的那类人。但是，招牌上阐明他不给这类人理发，因此他不能本人理。假设由另外一个人给他理发，他就是不给本人理发的人，而招牌上明明说他要给一切不本人理发的男人理发，因此，他应该本人理。由此可见，不论怎样的推论，理发师所说的话总是自相矛盾的。有趣的对话。甲对乙说：“他会回答我不对，对不对？请用对或不对来回答！例1.2 是有理数是不对的； 2是偶素数； 2或4是素数； 假设2是素数，那么3也是素数； 2是素数当且仅当3也是素数。 全是命题。定义1.1 设p为命题，复合命题“非

10、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都为真时，析取起来为假。前者称为相容或，后者称为排斥或(排异或)。例1.3 将以下命题符号化。 (1) 张晓静爱唱歌或爱听音乐。(

11、2) 张晓静是江西人或安徽人。(3) 张晓静只能挑选202或203房间。解 在解题时，先将原子命题符号化。 (1) p：张晓静爱唱歌。 q：张晓静爱听音乐。 显然(1)中“或为相容或，即p与q可以同时为真，符号化为pq. (2) r：张晓静是江西人。 s：张晓静是安徽人。易知，(2)中“或应为排斥或，但r与s不能同时为真，因此也可以符号化为rs. (3) t：张晓静挑选202房间。 u：张晓静挑选203房间。由题意可知，(3)中“或应为排斥或。t，u的结合取值情况有四种：同真，同假，一真一假(两种情况)。假设也符号化为tu，张晓静就能够同时得到两个房间，这违背题意。因此不能符号化为tu.如何到

12、达只能挑一个房间的要求呢？可以运用多个结合词，符号化为(tu)(tu)定义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与

13、后件q往往具有某种内在联络。而在数理逻辑中，p与q可以无任何内在联络。 3在数学或其它自然科学中，“假设p，那么q往往表达的是前件p为真，后件q也为真的推理关系。但在数理逻辑中，作为一种规定，当p为假时，无论q是真是假，pq均为真。也就是说，只需p为真q为假这一种情况使得复合命题pq为假。 定义1.5 设p，q为二命题，复合命题“p当且仅当q称作p与q的等价式，记作p q，称作等价结合词。并规定p q为真当且仅当p与q同时为真或同时为假。以上定义了五种最根本、最常用、也是最重要的结合词，将它们组成一个集合，称为一个结合词集。其中为一元结合词，其他的都是二元结合词。 通常用1表示真，用0表示假，复合命题的真假值如表1.