离散数学的研究对象课件_第1页
离散数学的研究对象课件_第2页
离散数学的研究对象课件_第3页
离散数学的研究对象课件_第4页
离散数学的研究对象课件_第5页
已阅读5页,还剩35页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

离散数学的研究对象

由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系,因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化,从而可由计算机加以处理。离散数学(DiscreteMathematics)是计算机专业的一门重要基础课。它所研究的对象是离散数量关系和离散结构数学结构模型。离散数学的研究对象由于数字电子计算机是一个离散结构,它只能1离散数学的主要内容

到目前为止,离散数学所研究的精确范围并没有严格的定义,它和其它许多纯粹数学以及应用数学分支之间有着广泛的交叉和相互渗透。但是作为给计算机专业本科生开设的一门专业基础课,其内容相对来说较为明确,主要包括数理逻辑、集合论、代数系统以及图论等几部分。离散数学是数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程的基础。离散数学的主要内容到目前为止,离散数学所研究的精确范围并没2数理逻辑数理逻辑是用数学的方法研究关于推理、证明等问题的学科,也叫做符号逻辑。它的本质是研究如何通过利用纯粹的公理系统和符号演算以及推理方法来代替人们思维中的逻辑推理过程,并由此将整个的数学建立在这样一个逻辑基础之上。历史上诸多数学家的努力和推动,尤其是莱布尼茨、布尔、希尔伯特、罗素、图灵、哥德尔等人的工作,部分地实现了这一形式化数学的梦想,但同时也发现了数学基础本身存在的巨大困难。数理逻辑数理逻辑是用数学的方法研究关于推理、证明等问题的学3集合论集合论是德国著名数学家康托尔于19世纪末创立的。康托对于无穷集元素个数问题进行了卓越的研究,引领数学研究进入了一个全新的领域。他提出用一一对应准则来比较无穷集元素的个数,将元素间能建立一一对应的集合称为个数相同(也称作等势)。并证明了无穷集的势之间存在着差别,有着不同的数量级,可分为不同的层次。问题:试判断自然数集合{x|x=1,2,3,…}和奇数集合{x|x=1,3,5,…}哪个集合的元素个数多?集合论集合论是德国著名数学家康托尔于19世纪末创立的。康4图论“图论”是数学的一个分支,它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。欧拉在1736年解决了这个问题,他用抽象分析法将这个问题化为第一个图论问题。欧拉证明了柯尼斯堡七桥问题是无解的,并推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。这使得欧拉成为图论﹝及拓扑学﹞的创始人。图论“图论”是数学的一个分支,它以图为研究对象。图论中的5学习离散数学的方法

概念定理多:首先要精确严格地掌握好概念和术语,正确理解他们的内涵和外延。因为公理、定理或定律的基石都是概念,只有正确地理解了概念,才能把握定理的实质,熟练地将公理、定理应用于解决问题。抽象思维多:完全的、精确的掌握一个概念的好主意是首先要深刻理解概念的内涵,然后举一些属于和不属于该概念外延的正反两方面的实例。如果对一些似是而非的例子也能辨别的话,应该说这个概念正真理理解了。只需要中学数学基础。学习离散数学的方法概念定理多:首先要精确严格地掌握好概6第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题:

一个土耳其商人想找一个十分聪明的助手协助他经商,有两人前来应聘,这个商人为了试试哪个更聪明些,就把两个人带进一间漆黑的屋子里,他打开灯后说:“这张桌子上有五顶帽子,两顶是红色的,三顶是黑色的,现在,我把灯关掉,而且把帽子摆的位置弄乱,然后我们三个人每人摸一顶帽子戴在自己头上,在我开灯后,请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后,商人将电灯关掉,然后三人都摸了一顶帽子戴在头上,同时商人将余下的两顶帽子藏了起来,接着把灯打开。这时,那两个应试者看到商人头上戴的是一顶红帽子,其中一个人便喊道:“我戴的是黑帽子。”

第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题:7

请问这个人说得对吗?他是怎么推导出来的呢?

要回答这样的问题,实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程:

(1)什么是前提?有哪些前提?

(2)结论是什么?

(3)根据什么进行推理?

(4)怎么进行推理?

下面的第一章,第二章回答第一个问题。第三章回答第二、三个问题。

请问这个人说得对吗?他是怎么推导出来的呢?8下图给出了逻辑部分的知识体系下图给出了逻辑部分的知识体系9例1.1判断下列句子是否为命题。

(1)4是素数。

(2)是无理数。

(3)x大于y。

(4)月球上有冰。

(5)2100年元旦是晴天。

(6)π大于吗?

(7)请不要吸烟!

(8)这朵花真美丽啊!

(9)我正在说假话。能判定真假的陈述句称为命题作为命题的陈述句所表达的判断结果称为命题的真值,真值只取两个值:真或假。真值为真的命题称为真命题,真值为假的命题称为假命题。任何命题的真值都是唯一的。

判断给定句子是否为命题,应该分两步:首先判定它是否为陈述句,其次判断它是否有唯一的真值。例1.1判断下列句子是否为命题。能判定真假的陈述句称为命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)的真值,到2100年元旦(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的合取式,记作p∧q,∧称作合取联结词。并规定p∧q为真当且仅当p与q同时为真。定义1.3

设p,q为二命题,复合命题“p或q”称作p与q的析取式,记作p∨q,∨称作析取联结词。并规定p∨q为假当且仅当p与q同时为假。

注意:按定义1.3在析取式p∨q中,若p,q都为真,则p∨q为真。“或”还有另外一种用法:当p,q都为真时,析取起来为假。前者称为相容或,后者称为排斥或(排异或)。例1.2是有理数是不对的;2是偶素数;2或14例1.3将下列命题符号化。

(1)张晓静爱唱歌或爱听音乐。

(2)张晓静是江西人或安徽人。

(3)张晓静只能挑选202或203房间。

解在解题时,先将原子命题符号化。

(1)p:张晓静爱唱歌。

q:张晓静爱听音乐。

显然(1)中“或”为相容或,即p与q可以同时为真,符号化为p∨q.例1.3将下列命题符号化。15

(2)r:张晓静是江西人。

s:张晓静是安徽人。

易知,(2)中“或”应为排斥或,但r与s不能同时为真,因而也可以符号化为r∨s.

(3)t:张晓静挑选202房间。

u:张晓静挑选203房间。

由题意可知,(3)中“或”应为排斥或。t,u的联合取值情况有四种:同真,同假,一真一假(两种情况)。如果也符号化为t∨u,张晓静就可能同时得到两个房间,这违背题意。因而不能符号化为t∨u.如何达到只能挑一个房间的要求呢?可以使用多个联结词,符号化为

(t∧┐u)∨(┐t∧u)

(2)r:张晓静是江西人。

s:16定义1.4

设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作p→q,→称作蕴涵联结词。并规定p→q为假当且仅当p为真q为假。

注意:在使用联结词→时,要特别注意以下几点:

1.在自然语言里,特别是在数学中,q是p的必要条件有许多不同的叙述方式。例如,“只要p,就q”,“因为p,所以q”,“p仅当q”,“只有q才p”,“除非q才p”,“除非q,否则非p”等等。以上各种叙述方式表面看来有所不同,但都表达的是q是p的必要条件,因而所用联结词均应符号化为→,上述各种叙述方式都应符号化为p→q.

2.在自然语言中,“如果p,则q”中的前件p与后件q往往具有某种内在联系。而在数理逻辑中,p与q可以无任何内在联系。

3.在数学或其它自然科学中,“如果p,则q”往往表达的是前件p为真,后件q也为真的推理关系。但在数理逻辑中,作为一种规定,当p为假时,无论q是真是假,p→q均为真。也就是说,只有p为真q为假这一种情况使得复合命题p→q为假。定义1.4设p,q为二命题,复合命题“如果p,则q”称作p17定义1.5

设p,q为二命题,复合命题“p当且仅当q”称作p与q的等价式,记作p↔

q,称作等价联结词。并规定p↔

q为真当且仅当p与q同时为真或同时为假。

以上定义了五种最基本、最常用、也是最重要的联结词┐,∧,∨,→,↔,将它们组成一个集合{┐,∧,∨,→,↔},称为一个联结词集。其中┐为一元联结词,其余的都是二元联结词。定义1.5设p,q为二命题,复合命题“p当且仅当q”称作p18

通常用1表示真,用0表示假,复合命题的真假值如表1.1。表1.1基本复合命题的真值

联结词可以嵌套使用,在嵌套使用时,规定如下优先顺序:(),┐,∧,∨,→,↔

,对于同一优先级的联结词,先出现者先运算。

通常用1表示真,用0表示假,复合命题的真假值如表1.19例1.7

令p:北京比天津人口多。

q:2+2=4.

r:乌鸦是白色的。

求下列复合命题的真值:

(1)((┐p∧q)∨(p∧┐q))→r

(2)(q∨r)→(p→┐r)

(3)(┐p∨r)↔(p∧┐r)

p,q,r的真值分别为1,1,0,容易算出(1),(2),(3)的真值分别为1,1,0。

例1.7令p:北京比天津人口多。

20离散数学的研究对象

由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系,因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化,从而可由计算机加以处理。离散数学(DiscreteMathematics)是计算机专业的一门重要基础课。它所研究的对象是离散数量关系和离散结构数学结构模型。离散数学的研究对象由于数字电子计算机是一个离散结构,它只能21离散数学的主要内容

到目前为止,离散数学所研究的精确范围并没有严格的定义,它和其它许多纯粹数学以及应用数学分支之间有着广泛的交叉和相互渗透。但是作为给计算机专业本科生开设的一门专业基础课,其内容相对来说较为明确,主要包括数理逻辑、集合论、代数系统以及图论等几部分。离散数学是数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程的基础。离散数学的主要内容到目前为止,离散数学所研究的精确范围并没22数理逻辑数理逻辑是用数学的方法研究关于推理、证明等问题的学科,也叫做符号逻辑。它的本质是研究如何通过利用纯粹的公理系统和符号演算以及推理方法来代替人们思维中的逻辑推理过程,并由此将整个的数学建立在这样一个逻辑基础之上。历史上诸多数学家的努力和推动,尤其是莱布尼茨、布尔、希尔伯特、罗素、图灵、哥德尔等人的工作,部分地实现了这一形式化数学的梦想,但同时也发现了数学基础本身存在的巨大困难。数理逻辑数理逻辑是用数学的方法研究关于推理、证明等问题的学23集合论集合论是德国著名数学家康托尔于19世纪末创立的。康托对于无穷集元素个数问题进行了卓越的研究,引领数学研究进入了一个全新的领域。他提出用一一对应准则来比较无穷集元素的个数,将元素间能建立一一对应的集合称为个数相同(也称作等势)。并证明了无穷集的势之间存在着差别,有着不同的数量级,可分为不同的层次。问题:试判断自然数集合{x|x=1,2,3,…}和奇数集合{x|x=1,3,5,…}哪个集合的元素个数多?集合论集合论是德国著名数学家康托尔于19世纪末创立的。康24图论“图论”是数学的一个分支,它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。欧拉在1736年解决了这个问题,他用抽象分析法将这个问题化为第一个图论问题。欧拉证明了柯尼斯堡七桥问题是无解的,并推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。这使得欧拉成为图论﹝及拓扑学﹞的创始人。图论“图论”是数学的一个分支,它以图为研究对象。图论中的25学习离散数学的方法

概念定理多:首先要精确严格地掌握好概念和术语,正确理解他们的内涵和外延。因为公理、定理或定律的基石都是概念,只有正确地理解了概念,才能把握定理的实质,熟练地将公理、定理应用于解决问题。抽象思维多:完全的、精确的掌握一个概念的好主意是首先要深刻理解概念的内涵,然后举一些属于和不属于该概念外延的正反两方面的实例。如果对一些似是而非的例子也能辨别的话,应该说这个概念正真理理解了。只需要中学数学基础。学习离散数学的方法概念定理多:首先要精确严格地掌握好概26第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题:

一个土耳其商人想找一个十分聪明的助手协助他经商,有两人前来应聘,这个商人为了试试哪个更聪明些,就把两个人带进一间漆黑的屋子里,他打开灯后说:“这张桌子上有五顶帽子,两顶是红色的,三顶是黑色的,现在,我把灯关掉,而且把帽子摆的位置弄乱,然后我们三个人每人摸一顶帽子戴在自己头上,在我开灯后,请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后,商人将电灯关掉,然后三人都摸了一顶帽子戴在头上,同时商人将余下的两顶帽子藏了起来,接着把灯打开。这时,那两个应试者看到商人头上戴的是一顶红帽子,其中一个人便喊道:“我戴的是黑帽子。”

第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题:27

请问这个人说得对吗?他是怎么推导出来的呢?

要回答这样的问题,实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程:

(1)什么是前提?有哪些前提?

(2)结论是什么?

(3)根据什么进行推理?

(4)怎么进行推理?

下面的第一章,第二章回答第一个问题。第三章回答第二、三个问题。

请问这个人说得对吗?他是怎么推导出来的呢?28下图给出了逻辑部分的知识体系下图给出了逻辑部分的知识体系29例1.1判断下列句子是否为命题。

(1)4是素数。

(2)是无理数。

(3)x大于y。

(4)月球上有冰。

(5)2100年元旦是晴天。

(6)π大于吗?

(7)请不要吸烟!

(8)这朵花真美丽啊!

(9)我正在说假话。能判定真假的陈述句称为命题作为命题的陈述句所表达的判断结果称为命题的真值,真值只取两个值:真或假。真值为真的命题称为真命题,真值为假的命题称为假命题。任何命题的真值都是唯一的。

判断给定句子是否为命题,应该分两步:首先判定它是否为陈述句,其次判断它是否有唯一的真值。例1.1判断下列句子是否为命题。能判定真假的陈述句称为命30解:

本题的(9)个句子中,(6)是疑问句,(7)是祈使句,(8)是感叹句,因而这3个句子都不是命题。剩下的6个句子都是陈述句,但(3)无确定的真值,根据x,y的不同取值情况它可真可假,即无唯一的真值,因而不是命题。若(9)的真值为真,即“我正在说假话”为真,也就是“我正在说真话”,则又推出(9)的真值应为假;反之,若(9)的真值为假,即“我正在说假话”为假,也就是“我正在说假话”,则又推出(9)的真值应为真。于是(9)既不为真又不为假,因此它不是命题。像(9)这样由真推出假,又由假推出真的陈述句称为悖论。凡是悖论都不是命题。本例中,只有(1),(2),(4),(5)是命题。(1)为假命题,(2)为真命题。虽然今天我们不知道(4),(5)的真值,但它们的真值客观存在,而且是唯一的,将来总会知道(4)的真值,到2100年元旦(5)的真值就真相大白了。解:31罗素悖论一天,萨维尔村理发师挂出一块招牌:“村里所有不自己理发的男人都由我给他们理发,我也只给这些人理发。”于是有人问他:“您的头发由谁理呢?”理发师顿时哑口无言。因为,如果他给自己理发,那么他就属于自己给自己理发的那类人。但是,招牌上说明他不给这类人理发,因此他不能自己理。如果由另外一个人给他理发,他就是不给自己理发的人,而招牌上明明说他要给所有不自己理发的男人理发,因此,他应该自己理。由此可见,不管怎样的推论,理发师所说的话总是自相矛盾的。罗素悖论一天,萨维尔村理发师挂出一块招牌:“村里所有不自己理32有趣的对话。甲对乙说:“你会回答我‘不对’,对不对?请用‘对’或‘不对’来回答!”有趣的对话。甲对乙说:“你会回答我‘不对’,对不对?请用‘对33例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的合取式,记作p∧q,∧称作合取联结词。并规定p∧q为真当且仅当p与q同时为真。定义1.3

设p,q为二命题,复合命题“p或q”称作p与q的析取式,记作p∨q,∨称作析取联结词。并规定p∨q为假当且仅当p与q同时为假。

注意:按定义1.3在析取式p∨q中,若p,q都为真,则p∨q为真。“或”还有另外一种用法:当p,q都为真时,析取起来为假。前者称为相容或,后者称为排斥或(排异或)。例1.2是有理数是不对的;2是偶素数;2或34例1.3将下列命题符号化。

(1)张晓静爱唱歌或爱听音乐。

(2)张晓静是江西人或安徽人。

(3)张晓静只能挑选202或203房间。

解在解题时,先将原子命题符号化。

(1)p:张晓静爱唱歌。

q:张晓静爱听音乐。

显然(1)中“或”为相容或,即p与q可以同时为真,符号化为p∨q.例1.3将下列命题符号化。35

(2)r:张晓静是江西人。

s:张晓静是安徽人。

易知,(2)中“或”应为排斥或,但r与s不能同时为真,因而也可以符号化为r∨s.

(3)t:张晓静挑选202房间。

u:张晓静挑选203房间。

由题意可知,(3)中“或”应为排斥或。t,u的联合取值情况有四种:同真,同假,一真一假(两种情况)。如果也符号化为t∨u,张晓静就可能同时得到两个房间,这违背题意。因而不能符号化为t∨u.如何达到只能挑一个房间的要求呢?可以使用多个联结词,符号化为

(t∧┐u)∨(┐t∧u)

(2)r:张晓静是江西人。

s:36定义1.4

设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作p→q,→称作蕴涵联结词。并规定p→q为假当且仅当p为真q为假。

注意:在使用联结词→时,要特别注意以下几点:

1.在自然语言里,特别是在数学中,q是p的必要条件

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论