计算机方法论-chapter 5 计算学科中的数学方法ppt课件

1、计算学科中的数学方法计算学科中的数学方法邹复好邹复好:fuhao_计算机科学中的问题求解初探计算机科学中的问题求解初探计算学科中的数学方法计算学科中的数学方法 实际上，凡能被计算机处置的问题均可以转换为一实际上，凡能被计算机处置的问题均可以转换为一个数学问题；凡能以离散数学为代表的构造性数学方法个数学问题；凡能以离散数学为代表的构造性数学方法描画的问题，当该问题所涉及的论域为有穷，或者为无描画的问题，当该问题所涉及的论域为有穷，或者为无穷但存在有穷表示时，这个问题也一定能用计算机来处穷但存在有穷表示时，这个问题也一定能用计算机来处置。置。引 言 数学有延续数学和离散数学之

2、分，离散数学源于算术，延续数学源于数学有延续数学和离散数学之分，离散数学源于算术，延续数学源于几何。几何。 自牛顿开创微积分后，延续数学就以微积分为根底。自牛顿开创微积分后，延续数学就以微积分为根底。 计算学科与物理等学科不同，它的根本问题是计算学科与物理等学科不同，它的根本问题是“能行性问题。能行性问题。“能能行性这个根本问题决议了计算机本身的构造和它处置的对象都是离散行性这个根本问题决议了计算机本身的构造和它处置的对象都是离散型的，而延续型的问题只需经过型的，而延续型的问题只需经过“离散化的处置后才干被计算机处置。离散化的处置后才干被计算机处置。因此，在计算学科中，采用的数学方法，主要是离

3、散数学的方法。因此，在计算学科中，采用的数学方法，主要是离散数学的方法。引 言 在对待数学的问题上，计算机科学家与数学家的偏重点在对待数学的问题上，计算机科学家与数学家的偏重点不一样：不一样： 数学家关怀的是数学家关怀的是“是什么是什么What is it的问题，重点的问题，重点放在数学本身的性质上；放在数学本身的性质上； 计算机科学家那么不同，他们不仅要知道计算机科学家那么不同，他们不仅要知道“是什么的问是什么的问题，更要处理题，更要处理“怎样做怎样做How to do it的问题。的问题。在计算领域，人们发明了基于离散数学的在计算领域，人们发明了基于离散数学的“详细数学的详细数学的大量概念

4、和方法如学科中的各种方式化方法。大量概念和方法如学科中的各种方式化方法。一、数学的根本特征及数学方法的作用一、数学的根本特征及数学方法的作用高度笼统高度笼统逻辑严密逻辑严密普遍适用普遍适用l 为科学技术研讨提供简约准确的方式化言语为科学技术研讨提供简约准确的方式化言语l 为科学技术研讨提供数量分析和计算的方法为科学技术研讨提供数量分析和计算的方法l 为科学技术研讨提供逻辑推理的工具为科学技术研讨提供逻辑推理的工具二、计算学科中常用的数学概念和术语二、计算学科中常用的数学概念和术语 集合集合 函数和关系函数和关系谓词和布尔逻辑谓词和布尔逻辑字母表、字符串和言语字母表、字符串和言语定义、定理和证明

5、定义、定理和证明 论域：一定场所语境中思索和议论所涉论域：一定场所语境中思索和议论所涉及的对象的范围。即某一范围内被论及对象及的对象的范围。即某一范围内被论及对象的全部所构成的集合。的全部所构成的集合。1 1集合的概念集合的概念集合是数学的根本概念，它是构造性数学集合是数学的根本概念，它是构造性数学方法的根底。方法的根底。 集合就是一组无反复的对象的全体。集集合就是一组无反复的对象的全体。集合中的对象称为集合的元素。合中的对象称为集合的元素。 如：计算机专业学生全部必修课程可以如：计算机专业学生全部必修课程可以组成一个集合，其中的每门课程就是这一集组成一个集合，其中的每门课程就是这一集合中的元

6、素。合中的元素。一集合一集合集合集合 2 2集合的描画方法集合的描画方法通常用大写字母表示集合，用小写字母表示元素，描画通常用大写字母表示集合，用小写字母表示元素，描画集合的方式主要有以下集合的方式主要有以下3 3种：种：1 1枚举法：列出一切元素的表示方法。枚举法：列出一切元素的表示方法。如如1 1至至5 5的整数集合可表示为：的整数集合可表示为：A=A=1 1，2 2，3 3，4 4，5 5 ；2 2外延表示法：当集合中所列元素的普通方式很明显时，外延表示法：当集合中所列元素的普通方式很明显时，可只列出部分元素，其他那么用省略号表示。可只列出部分元素，其他那么用省略号表示。如斐波那契数列可

7、表示为：如斐波那契数列可表示为： 0 0，1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434， ；3 3谓词表示法：用谓词来概括集合中元素的属性。谓词表示法：用谓词来概括集合中元素的属性。如斐波那契数列可表示为：如斐波那契数列可表示为：Fn|Fn+2=Fn+1+FnFn|Fn+2=Fn+1+Fn，F0=0F0=0，F1=1F1=1，n0n0。集合集合 3集合的运算集合的运算 集合的根本运算有并、差、交、补和乘积等运算。集合的根本运算有并、差、交、补和乘积等运算。1集合的并集合的并 设设A、B为两个恣意集合，一切属于为两个恣意集合，一切属于A或属于或属于B的元素构成的集

8、合的元素构成的集合C，称为，称为A和和B的并集。可表示为：的并集。可表示为：CABxxAxB，称为并，称为并运算。运算。 例例1 假设假设A=a，b，c，d，B=b，d，e，求集合，求集合A和和B的并。的并。 解：解：ABa，b，c，d，e2集合的差集合的差 设设A、B为两个恣意集合，一切属于为两个恣意集合，一切属于A而不属于而不属于B的一切元素构成的集合的一切元素构成的集合S，称为称为A和和B的差集。可表示为：的差集。可表示为：S=AB=xxAxB，称为差，称为差运算。运算。 例例2 假设假设A=a，b，c，d，B=b，d，e，求集合，求集合A和和B的差。的差。 解：解：AB=a，c集合集合

9、3集合的交集合的交 设设A、B为两个恣意集合，由和的一切一样元素构成的集合为两个恣意集合，由和的一切一样元素构成的集合C，称，称为为A和和B的交集。可表示为：的交集。可表示为：CABxxAxB，称，称为交运算。为交运算。例例3 假设假设A=x | x 5，B=x | x 5x | x 1x5 x 14集合的补集合的补 设设I为选集，为选集，A为为I的恣意一子集，的恣意一子集，IA那么为那么为A的补集，记为的补集，记为 。可。可表示为表示为 =IA=xxI，xA求补集的运算称为补运算。求补集的运算称为补运算。 例例4 假设假设I=x5x5，A=x0 x1，求，求 。 解：解： =IA=x5x01

10、x5AAAA集合集合5集合的乘积集合的乘积集合集合A1，A2，An的乘积普通用法国数学家笛卡尔的乘积普通用法国数学家笛卡尔Rene Descartes的名字命名，即笛卡尔积。该乘积表示如下：的名字命名，即笛卡尔积。该乘积表示如下：A1A2An=a1，a2，anaiAi，i1，2，nA1A2An的结果是一个有序的结果是一个有序n元组的集合。元组的集合。 例例5 假设假设A=1，2，3，B=a，b，求，求AB。 解：解：AB=1，a，1，b，2，a，2，b，3，a，3，b二函数和关系二函数和关系1函数函数函数又称映射，是指把输入转变成输出的运算，该运算函数又称映射，是指把输入转变成输出的运算，该运

11、算也可了解为从某一也可了解为从某一“定义域的对象到某一定义域的对象到某一“值域的对象的值域的对象的映射。映射。 设设f为一个函数，当输入值为为一个函数，当输入值为a 时输出值为时输出值为b，那么记作：，那么记作：f(a)=b。2关系关系关系是一个谓词，其定义域为关系是一个谓词，其定义域为k元组的集合。通常的关系元组的集合。通常的关系为二元关系，其定义域为有序对的集合，通常有序对的第一为二元关系，其定义域为有序对的集合，通常有序对的第一个元素和第二个元素有关系。如学生选课。个元素和第二个元素有关系。如学生选课。函数和关系函数和关系n定义：定义：A1A2 An中的任一子集称为中的任一子集称为A1,

12、 A2, , An的一的一个个n元关系。元关系。n 二元关系：二元关系： A1A2 的一个子集，或称有序对。的一个子集，或称有序对。n 例例6，选课关系：，选课关系：R=(张张, 文文)，(张张, 哲哲)， (李李, 数数)，(李李, 艺艺)，(王王, 史史)，( 王王, 文文)函数和关系函数和关系n二元关系中的特例：集合二元关系中的特例：集合A上的关系：上的关系：AAnA到到A本身的关系，记为本身的关系，记为A2。n 例例7 A=0, 1, 2, 3，那么，那么n =(0, 0), (0 3), (2 0), (2, 1), (2, 3), (3, 2)是是A上的一个关上的一个关系；系；n

13、AA有有16个元素。个元素。n 例例8 实数集实数集R，1=(x, y)|(x, y) R2, xy, 1是是R上的上的“小小于关系，记为于关系，记为x1y。函数和关系函数和关系给定给定R=1, 2, 3, 4，写出关系，写出关系1(xy)和和3(x=y)的元组的元组 。R R=(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4) (4,1), (4,2), (4,3), (4,4)1(xy)= (2,1), (3,1), (3,2), (4,1), (4,2), (4,3)3(x=

14、y)= (1,1), (2,2), (3,3), (4,4)n 集合集合A上的关系性质上的关系性质n 设设是集合是集合A上的关系。上的关系。n 假设对于一切的假设对于一切的 a A。有。有aa，那么称，那么称是是自反的。自反的。n 对于一切的对于一切的 a, b A，假设每当有，假设每当有ab就有就有ba， n 那么称那么称 是对称的。是对称的。n 对于一切的对于一切的a, b, c A，假设每当有，假设每当有ab和和bc就有就有n ac，那么称，那么称是可传送的。是可传送的。函数和关系函数和关系n 等价关系：集合等价关系：集合A上的关系上的关系 ，假设它是自反、，假设它是自反、对称且可传送的

15、，那么称对称且可传送的，那么称为为A上的等价关系。上的等价关系。n 如：集合元素中的相等关系，直线之间的平行关如：集合元素中的相等关系，直线之间的平行关n 系，三角形的类似关系，位于同一条街的居系，三角形的类似关系，位于同一条街的居 民之间的关系等。民之间的关系等。函数和关系函数和关系n 等价类等价类n 设设是是A上的等价关系，假设上的等价关系，假设ab成立，那么成立，那么a等价等价n 于于b在在下。下。n 定义：设定义：设是是A上的等价关系，那么上的等价关系，那么A中等价于中等价于a 的的全全n 体元素的集合称为体元素的集合称为a所生成的等价类。所生成的等价类。n 记为记为a=b|bA, a

16、bn 例例9，“同余关系是等价关系同余关系是等价关系n 例例10，“并发关系是非等价关系并发关系是非等价关系n 例例11，“小于关系小于关系不具备自反性和对称性；不具备自反性和对称性；“等等于关系于关系具备自反性、对称性、可传送。具备自反性、对称性、可传送。函数和关系函数和关系p 个体：可以独立存在的物体。个体：可以独立存在的物体。p 谓词：用来描写个体的性质或关系的词谓词：用来描写个体的性质或关系的词p 描写一个个体性质的词为一元谓词，描写几描写一个个体性质的词为一元谓词，描写几个个体之间关系的词称为个个体之间关系的词称为n元谓词。元谓词。1. 谓词：充任谓语阐明主语谓词：充任谓语阐明主语“

17、怎样样，怎样样，“是什么是什么和能同副词结合的动词、描画词辞海。和能同副词结合的动词、描画词辞海。 Predicate，谓词、断言，谓词、断言三谓词与布尔逻辑三谓词与布尔逻辑命题逻辑命题逻辑2. 命题逻辑命题逻辑命题：一个能分辨真假的陈说句称作一个命题。命题：一个能分辨真假的陈说句称作一个命题。例如例如 地球上海洋面积比陆地大。地球上海洋面积比陆地大。 他喜欢周杰伦的歌吗？他喜欢周杰伦的歌吗？ 22 5。 今天天气太不好啦。今天天气太不好啦。 2x30。 三角之和小于三角之和小于180度。度。 非命题非命题( (值：真值：真值：假值：假非命题非命题是陈说句，但不能分辨真假，非命题是陈说句，但不

18、能分辨真假，非命题值：假值：假命题逻辑命题逻辑结合词：结合词： 合取合取 析取析取 取反取反 蕴含蕴含 等值等值异或异或例，例， 今天下雨。今天下雨。 值为假值为假原子命题经过结合词组成复合命题。原子命题经过结合词组成复合命题。命题逻辑命题逻辑关于析取和异或：关于析取和异或： 析取表示析取表示“可兼或可兼或例，例，P P：刘翔是：刘翔是110110米栏冠军米栏冠军 Q Q：刘翔是：刘翔是200200米栏冠军米栏冠军 P Q P Q 为复合命题，表示为复合命题，表示“刘翔或者是刘翔或者是110110米栏冠军，米栏冠军，或者是或者是200200米栏冠军米栏冠军例，今天晚上我在家看电视或去剧场看戏。

19、例，今天晚上我在家看电视或去剧场看戏。 P Q P Q？ 不能兼或不能兼或同时成立也为真。同时成立也为真。命题逻辑命题逻辑关于析取和异或：关于析取和异或： 异或：异或：P P和和Q Q相反时，相反时， P Q P Q为真为真可用可用、 来表达来表达普通不将普通不将列为根本结合词列为根本结合词命题逻辑命题逻辑关于蕴含：关于蕴含： 蕴含：表示蕴含：表示“假设假设，那么，那么P QP Q，假设，假设P P，那么，那么Q Q。当且仅当当且仅当P P为真，为真，Q Q为假，为假，P QP Q为假。为假。真值表真值表Q Q为真为真命题逻辑命题逻辑例，例， P P：月亮出来了。：月亮出来了。 Q Q：3 3

20、3 39 9。 P Q P Q成立成立 只需后件为真，不论前件是真是假，蕴含均成立。只需后件为真，不论前件是真是假，蕴含均成立。命题逻辑命题逻辑真值表真值表Q Q为假为假例，例，P P：教师教学生，：教师教学生， Q Q：地球今天爆炸：地球今天爆炸 PQ PQ：为假。：为假。例，例，P P：雪是黑的，：雪是黑的， Q Q：太阳从西边出来：太阳从西边出来 PQ PQ：假设雪是黑的，太阳就会从西边出来：假设雪是黑的，太阳就会从西边出来命题逻辑命题逻辑关于等值：关于等值： 当前件后件取同一值时，等值为真。当前件后件取同一值时，等值为真。真值表真值表 命题：一个能分辩真假的陈说句称作一个命题命题：一个

21、能分辩真假的陈说句称作一个命题 量词：全称量词量词：全称量词 ：一切的：一切的 存在量词存在量词 ：存在：存在3. 谓词逻辑：将命题分解为主词、谓词和量词，谓词逻辑：将命题分解为主词、谓词和量词，研讨研讨 其方式构造，导出有关的逻辑其方式构造，导出有关的逻辑方式和规方式和规 律的逻辑实际辞海。律的逻辑实际辞海。谓词逻辑谓词逻辑谓词逻辑谓词逻辑谓词逻辑与命题逻辑谓词逻辑与命题逻辑 在命题逻辑中，是把简单命题作为根本单元或作为在命题逻辑中，是把简单命题作为根本单元或作为原子命题来对待的，不再对简单命题的内部构造进展分原子命题来对待的，不再对简单命题的内部构造进展分析。析。 谓词逻辑引入谓词和量词对

22、简单命题做了进一步分谓词逻辑引入谓词和量词对简单命题做了进一步分析。析。 商定以小写字母表示命题、函数，而以大写字母来商定以小写字母表示命题、函数，而以大写字母来表示谓词。表示谓词。 本课程限于一阶谓词逻辑或称狭义谓词逻辑。本课程限于一阶谓词逻辑或称狭义谓词逻辑。谓词逻辑谓词逻辑例例 张三是学生李四是学生张三是学生李四是学生1 1 在命题逻辑里，这是两个不同的命题，只能分别以两在命题逻辑里，这是两个不同的命题，只能分别以两个不同的符号表示。个不同的符号表示。2 2然而它们都有主词和谓词。主词然而它们都有主词和谓词。主词“张三、张三、“李四不同。李四不同。谓词谓词“是学生是一样的。假设以大写符号

23、是学生是一样的。假设以大写符号P P表示表示“是学生，是学生，便可把这两个命题分别写成便可把这两个命题分别写成P(P(张三张三) ) 和和P(P(李四李四) )3 3普通地，可引入变量普通地，可引入变量x x来表示主词，于是符号来表示主词，于是符号P(x)P(x)就表就表示示“x x是学生通常把是学生通常把P(x)P(x)称作谓词称作谓词个体与谓词个体与谓词1 1个体个体 ：个体是指研讨对象中不依赖于人的客观而独立存：个体是指研讨对象中不依赖于人的客观而独立存在的详细的或笼统的客观实体在的详细的或笼统的客观实体 个体常项或个体常元个体常项或个体常元 ； 个体变项或个体变元个体变项或个体变元 ；

24、 个体域或论域个体域或论域 。2 2谓词：用来描写个体词的性质或个体词之间关系的词。普谓词：用来描写个体词的性质或个体词之间关系的词。普通来说，通来说，“x x是是A A类型的命题可以用类型的命题可以用A Ax x表达。对于表达。对于“x x大于大于y y这种两个个体之间关系的命题，可表达为这种两个个体之间关系的命题，可表达为B Bx x，y y，这，这里里B B表示表示“大于大于谓词。谓词。 把把A Ax x称为一元谓词，称为一元谓词，B Bx x，y y称为二元谓词，称为二元谓词，M Ma a，b b，c c称为三元谓词，依次类推，通常把二元以上谓词称作多元称为三元谓词，依次类推，通常把二

25、元以上谓词称作多元谓词。谓词。 谓词逻辑谓词逻辑符号化符号化 D(x): D谓词，谓词，x个体个体 例：例：D张三：张三是要死的张三：张三是要死的D谓词：要死谓词：要死的的 Dx：人是要死的：人是要死的x是人是人 量词量词1 1全称量词全称量词例：例：“凡事物都是运动的。这命题中的凡事物都是运动的。这命题中的“凡凡 是表示是表示个体变元数量的词，个体变元数量的词，“凡的等义词有凡的等义词有“一切的、一切的、“切的、切的、“任任个、个、“每一个，它是全称量词。每一个，它是全称量词。符号符号:(:(x)x)读作一切的读作一切的x x或任一或任一x x，一切，一切x x，而，而就称就称为全称量词，它

26、所约束的个体是为全称量词，它所约束的个体是x x。定义：命题定义：命题( (x)P(x)x)P(x)当且仅当对论域中的一切当且仅当对论域中的一切x x来说，来说，P(x)P(x)均为真时方为真。均为真时方为真。 ( (x)P(x)x)P(x)也写为也写为( (x)(P(x)x)(P(x) 留意留意( (x)(P(x)x)(P(x)Q(x)Q(x) ( (x)P(x)x)P(x)Q(x)Q(x) 量词的运算优先级高于逻辑结合词量词的运算优先级高于逻辑结合词性质性质:(:(x)Q(x)x)Q(x)F F，当且仅当对一切的，当且仅当对一切的x xD D都有都有Q(x)Q(x)F F。量词量词2 2存

27、在量词存在量词例：例：“有的事物是动物。这命题中有的事物是动物。这命题中“有的就是表示有的就是表示个体变元数量的词，个体变元数量的词，“有的的等义词有有的的等义词有“存在一个存在一个、“有一个、有一个、“有些它是存在量词。有些它是存在量词。符号符号:(:(x)x)读作至少有一个读作至少有一个x x或存在或存在个个x x或有某些或有某些x x而而就是对个体词起约束作用的存在量词，所就是对个体词起约束作用的存在量词，所约束的变元是约束的变元是x x。定义：命题定义：命题( (x)Q(x)x)Q(x)当且仅当在论域中至少有一个当且仅当在论域中至少有一个x0 x0，Q(x0)Q(x0)为真时方为真。为

28、真时方为真。( (x)Q(x)x)Q(x)也写为也写为( (x)(Q(x)x)(Q(x)留意留意( (x)(P(x)x)(P(x)Q(x)Q(x) ( (x)P(x)x)P(x)Q(x)Q(x)性质性质: (: (x)P(x)x)P(x)F F成立，当且仅当有一个成立，当且仅当有一个x0 x0 D D ，使使P(x0P(x0D)D)F F谓词逻辑谓词逻辑量词：量词： 一切的；一切的； 存在存在 x(D(x)x(D(x)：凡人必死：凡人必死 x(G(x)x(G(x)：某些人活到：某些人活到100100岁岁例，例，M(x)M(x)：x x是人，是人，D(x)D(x)：x x是要死的是要死的 x(M

29、(x)D(x)x(M(x)D(x)：例，例，P(x)P(x)：x x是苹果，是苹果，S(x)S(x)：x x是红色的是红色的 x(P(x)S(x)x(P(x)S(x)： x(P(x)S(x)x(P(x)S(x)：T TT TT TT TF F谓词逻辑谓词逻辑例，例，A(x)A(x)：x x是球，是球，B(x)B(x)：x x是圆的是圆的 x(A(x) B(x)x(A(x) B(x)：F F例，例，D(x)D(x)：x x是狗，是狗，P(x)P(x)：x x会叫，会叫，Q(x)Q(x)：x x咬人咬人 x(D(x) P(x) x(D(x) P(x) Q(x)Q(x)存在一条会叫不咬人的狗，即会叫

30、的狗不一定咬人存在一条会叫不咬人的狗，即会叫的狗不一定咬人 x(x(Q(x) P(x) Q(x)Q(x) P(x) Q(x)谓词逻辑谓词逻辑例，例， 将以下命题符号化，并指出真值情况。将以下命题符号化，并指出真值情况。1没有人登上过月球。没有人登上过月球。2一切人的头发未必都是黑色的。一切人的头发未必都是黑色的。解：个体域为全总个体域，令解：个体域为全总个体域，令Mx：x是人。是人。1令令Fx：x登上过月球。命题登上过月球。命题1符号化为：符号化为： xMxFx设设a是是1969年登上月球完成阿波罗方案的一名美国人，那么年登上月球完成阿波罗方案的一名美国人，那么MaFa为真，故命题为真，故命题

31、1为假。为假。2令令Hx：x的头发是黑色的。命题的头发是黑色的。命题2可符号化为：可符号化为： xMxHx我们知道有的人头发是褐色的，所以我们知道有的人头发是褐色的，所以xMxHx为假，故命题为假，故命题2为真。为真。 谓词逻辑谓词逻辑例，将以下命题符号化。例，将以下命题符号化。1 1猫比老鼠跑得快。猫比老鼠跑得快。2 2有的猫比一切老鼠跑得快。有的猫比一切老鼠跑得快。3 3并不是一切的猫比老鼠跑得快。并不是一切的猫比老鼠跑得快。4 4不存在跑得同样快的两只猫。不存在跑得同样快的两只猫。解：设个体域为全总个体域。令解：设个体域为全总个体域。令C Cx x：x x是猫；是猫；M My y：y y

32、是是老鼠；老鼠；Q Qx x，y y：x x比比y y跑得快；跑得快；L Lx x，y y：x x和和y y跑得同样跑得同样快。快。这这4 4个命题分别符号化为：个命题分别符号化为：1 1x x y yC Cx xMMy yQ Qx x，y y；2 2x xC Cx xy yM My yQ Qx x，y y；3 3x x y yC Cx xMMy yQ Qx x，y y；4 4x x y yC Cx xCCy yLLx x，y y。4. 字母表、字符串和言语字母表、字符串和言语1字母表2字符串3言语：给定字母表上的字符串的集合集合运算、闭包运算言语、文法与自动机言语由文法产生自动机是识别言语的数学模型5. 定义、定理和证明定义、定理和证明 1定义：定义是蕴含在公理系统之中的概念和命题。2定理：定理是被证明为真的数学命题。3证明：证明是为使人们确信一个命题为真，而作的一种逻辑论证。三、证明方法三、证明方法直