计算学科中的数学方法

《计算学科中的数学方法》由会员分享，可在线阅读，更多相关《计算学科中的数学方法（75页珍藏版）》请在金锄头文库上搜索。

1、计算学科中的数学方法数学的基本特征数学方法o是指解决数学问题的策略、途径和步骤，它是 计算学科中最根本的研究方法。o理论上，凡能被计算机处理的问题均可以转换 为一个数学问题，换言之，所有能被计算机处 理的问题均可以用数学方法解决；o反之，凡能以离散数学为代表的构造性数学方 法描述的问题，当该问题所涉及的论域为有穷 ，或虽为无穷但存在有穷表示时，这个问题也 一定能用计算机来处理。数学的基本特征o高度的抽象性 ：量的关系和空间的形式 o逻辑的严密性 ：严格遵守形式逻辑的基本法 则，充分保证逻辑的可靠性，才能保证结论的 正确性。 o普遍的适用性 ：数学的高度抽象性决定了它 的普遍适用性。 数学方法的

2、作用o为科学技术研究提供简洁精确的形式化语言 o为科学技术研究提供数量分析和计算的方法o为科学技术研究提供了逻辑推理的工具 计算学科中的数学方法计算学科中常用的数学概念和术语集合o集合的概念 n构造性数学方法的基础。n集合就是一组无重复的对象的全体。n集合中的对象称为集合的元素。n如：计算机专业学生全部必修课程可以组成一个集 合，其中的每门课程就是这一集合中的元素。o集合的描述方法n通常用大写字母表示集合，用小写字母表示元素集合的三种描述方法o枚举法：列出所有元素的表示方法。 如1至5的整数集合可表示为： =1，2，3，4，5；o外延表示法：当集合中所列元素的一般形式很 明显时，可只列出部分元

3、素，其他则用省略号 表示。 如斐波那契数列可表示为： 0，1，1，2，3，5，8，13，21，34， ；o谓词表示法：用谓词来概括集合中元素的属性 。 如斐波那契数列可表示为：Fn|Fn+2=Fn+1+Fn，F0=0，F1=1，n0 集合的运算 o集合的并 n设A、B为两个任意集合，所有属于A或属于B的元 素构成的集合C，称为A和B的并集。可表示为：C ABxxAxB。n求并集的运算称为并（运算）。o例5.1 若A=a，b，c，d，B=b，d，e，求集 合A和B的并。n解：ABa，b，c，d，e集合的差 o设A、B为两个任意集合，所有属于A而不属于 B的一切元素构成的集合S，称为A和B的差集

4、。可表示为：S=AB=xxAxB。n求差集的运算称为差（运算）。o例5.2 若A=a，b，c，d，B=b，d，e，求集 合A和B的差。n解：AB=a，c交集的交o设A、B为两个任意集合，由和的所有相同元素 构成的集合C，称为A和B的交集。可表示为： CABxxAxB。n求交集的运算称为交（运算）。o例5.3 若A=x | x -5，B=x|x 5xx， 其中： （1）表示理论； （2）表示基本概念的集合； （3）表示基本原理或定律的集合； （4）表示由这些概念与原理逻辑推理出来的结 论组成的集合。 构建理论体系的常用方法 o每一个理论都由一组特定的概念和一组特定的 命题组成。o在一个理论中，基

5、本概念（原始概念）和基本 命题（原始命题）必须是明确的，否则就会出 现“循环定义”和“循环论证”的严重问题。o构建一个理论体系必须采用科学的方法。n公理化方法n逻辑和历史相统一的方法n从抽象上升到具体的方法。公理化方法 o公理化方法，我们在第1章已作过简单介绍， 这是一种构造理论体系的演绎方法，n从尽可能少的基本概念、公理出发，运用演绎推理 规则，推出一系列的命题，从而建立整个理论体系 的思想方法。 公理系统的3个条件 o用公理化构建的理论体系称为公理系统，该公 理系统需要满足无矛盾性、独立性和完备性的 条件。 （1）无矛盾性。 （2）独立性。 （3）完备性。o简单化是科学研究追求的目标之一。

6、一般而言 ，正确的一定是简单的（注意，这句话是单向 的，反之不一定成立）。o关于公理系统的完备性要求，自哥德尔发表关 于形式系统的“不完备性定理”的论文后，数学 家们对公理系统的完备性要求大大放宽了。n也就是说，能完备更好，即使不完备，同样也具有 重要的价值。 公理化方法在计算学科中的应用 o公理化方法主要用于计算学科理论形态方面的 研究。在计算学科各分支领域，均采用了公理 化方法。如n形式语义学n关系数据库理论n分布式代数系统n计算认知领域例5.18 正整数的公理化概括o原始概念：1；o原始命题（公理）：任何正整数n或者等于1， 或者可以从1开始，重复地“加1”来得到它。 例5.19 平面几

7、何的公理化概括（欧氏几何）o以点、线、面为原始概念，以5条公设和5条公理为原 始命题，给出了平面几何中的119个定义，465条命题 及其证明，构成了历史上第一个数学公理体系。 原始概念：点、线、面 原始命题（公设和公理）如下： 公设1：两点之间可作一条直线； 公设2：一条有限直线可不断延长； 公设3：以任意中心和直径可以画圆； 公设4：凡直角都彼此相等； 公设5：在平面上，过给定直线之外的一点，存在且仅存 在一条平行线，即所谓的“平行公设（公理）”。例5.20 中国古代唯一的一次公理化尝试：周髀算经o 据有关记载，周髀算经成书于公元前100年 左右。在周髀算经中，介绍了一个描述天象的盖 天学说

8、，该学说构建了一个几何宇宙模型。o 该学说中的公理有两个：一个是“天地为平行平 面，天地相距80,000里，在北极下方的大地中央有 一底面直径为23,000里，高为60,000里的上尖下 粗的 “璇玑”（即极下，极下阳光照不到，故不生万 物）；o另一个是关于太阳光照以及人目所见的极限范围，即 “日照四旁各十六万七千里；人所望见，远近宜如日 光所照”，其大意为，日光向四周照射的极限距离是 167,000里，人所见到也是这个距离。换言之，日 光照不到167,000里之外，人也看不见167,000里 之外。o 从公理可以演绎出：夏至南万六千里，冬至南十 三万五千里，日中立竿无影。此一者天道之数。周髀

9、 长八尺，夏至之日晷一尺六寸。髀者，股也；正晷者 ，勾也。正南千里，勾一尺五寸；正北千里，勾一尺 七寸。其大意为，在某地竖一个8尺高的竿，太阳移 动了一千里，这个竿的影子和原来的相差一寸，即日 影千里差一寸。o 而从“日照四旁”167,000里，以及用公理演绎 出的冬至日道半径238,000里，又可导出宇宙半径 为405,000里，从而构建了一个天、地为圆形平行 平面的宇宙模型。o 今天，我们知道，这个宇宙模型的描述与实际的 天象吻合得并不好，与同时代古希腊类似模型相比， 也存在较大的差距，而当时，我国天文学家完全可以 用代数方法相当精确地解决一些天文学问题，至于宇 宙究竟是什么形状或结构，完

10、全可以不去过问。然而 ，周髀算经是个例外，并成为我国古代学者惟一 的一次公理化方法的尝试，这种思想，是受外来因素 的影响，还是我国本土科学中某种随机出现的变异？ 已引起科学史领域专家的极大兴趣。计算学科中的数学方法形式化方法 具体公理系统和抽象公理系统 o在欧氏几何公理系统中，原始概念（点、线、 面）和所有的公理都有直观的背景或客观的意 义，像这样有现实世界背景的公理系统，一般 被称为具体公理系统。 o由于非欧几何的出现，使人们感到具体公理系 统过于受直觉的局限。因而，在19世纪末和20 世纪初，一些杰出的数学家和逻辑学家开始了 对抽象公理系统的研究。o在抽象公理系统中，原始概念的直觉意义被忽

11、 视，甚至没有任何预先设定的意义，而公理也 无需以任何实际意义为背景，它们无非是一些 形式约定的符号串。这时，抽象公理系统可以 有多种解释。n形式化的运算规则1+1可以解释为一个苹果 加一个苹果，或者为一本书加一本书；n布尔代数抽象公理系统可以解释为有关命题 真值的命题代数，或者有关电路设计研究的 开关代数。形式系统的组成部分o初始符号。初始符号不具有任何意义。o形式规则。形式规则规定一种程序，借以判定 哪些符号串是本系统中的公式，哪些不是。o公理。即在本系统的公式中，确定不加推导就 可以断定的公式集。o变形规则。变形规则亦称演绎规则或推导规则 。变形规则规定，从已被断定的公式，如何得 出新的

12、被断定公式。被断定的公式又称为系统 中的定理。形式系统的基本特点 o严格性n形式系统中，初始符号和形式规则都要进行严格的 定义，不允许出现在有限步内无法判定的公式。形 式系统采用的是一种纯形式的机械方法，它的严格 性高于一般的数学推导。o抽象性n抽象性不是形式系统的专利，抽象是人们认识客观 世界的基本方法，只不过形式系统具有更强的抽象 性。o形式系统的抽象性表现在它自身仅仅是一个符 号系统，除了表示符号间的关系（字符号串的 变换）外，不表示任何别的意义。 形式系统的局限性 o不完备性n1931年，哥德尔提出的关于形式系统的“不 完备性定理”指出：如果一个形式的数学理 论是足够复杂的（复杂到所有

13、的递归函数 在其中都能够表示），而且它是无矛盾的 ，那么在这一理论中存在一个语句，而这 一语句在这一理论中是既不能证明，也不 能否证的。形式系统的局限性 o不可判定性n如果对一类语句C而言，存在一个算法AL，使 得对C中的任一语句S而言，可以利用算法AL来 判定其是否成立，则C称为可判定的，否则，称 为不可判定的。n著名的“停机问题”就是一个不可判定性的问题 。该问题是指，一个任给的图灵机对于一个任 给的输入而言是否停机的问题。图灵证明这类 问题是不可判定的。o需要指出的是：计算机系统就是一种形式系 统，因此，计算机系统一样也具有形式系统 的局限性。形式化与公理化 o形式化不一定导致公理化，公

14、理系统也不一定 是形式系统。n如欧氏几何公理系统就不是形式系统。n形式化与公理化虽然不同，但在近代数学中，形式 系统大都是形式化的公理系统。计算学科中的数学方法一个实例Armstrong公理系统 预备知识 o定义1：设R=是一个关系模式，其中，R是关 系名，U为组成该关系属性名的集合，F为R上的一个 函数依赖关系的集合。设X，Y U，rIns(R)，则对 任何u，vr，只要uX=vX，就必有uY=vY，则 称满足XY，也称中存在函数依赖XY。o注：关系模式R=上的所有实例的集合记作 Ins(R)。o定义2：在关系模式R=中，为F所逻辑蕴含的 函数依赖全体的集合称为F的闭包（Closure），记

15、为 F+。o定义3：在关系模式R=中，若XU，则X+= A|XA能从F出发，由Armstrong公理系统推导出来 ，X+称为属性集X关于函数依赖集F的闭包。算法 o在实际工作中，一般不直接计算F+，而是通过 计算X+而达到同样的目的。下面，给出计算属 性闭包的算法和一个例子。o算法：在关系模式R=中，求属性集 X(X U)关于函数依赖的属性闭包X+。o输入：关系模式R=中的全部属性集U ，在U上的函数依赖F，U的子集X。o输出：属性闭包X+。 步骤： （1）令X(0) =X，i=0 （2）令X(i+1)=X(i)A|VX(i) ，VWF，AW （3）判断等式X(i+1)=X(i)是否成立，若成

16、立则转（ 4），否则转（2） （4）令X+=X(i)，输出X+。例5.20 F由下列5个函数依赖组成：F=AC，BC，ABD，BCDE，DE 计算：(BD)+ （1）X(0)=BD （2）X(1)=BDC，即X(1)=BDC（在此，将属性 集BD和C的并集BDC简记为BDC，下同） ，则X(1)X(0)，继续 （3）X(2) =BDCE，则X(2)X(1)，继续 （4）X(3) = BDCE，则X(3) = X(2)，所以(BD)+ = X(2) = BDCE。 Armstrong公理系统的3条公理 o设U为关系模式R的属性名集合，F是U 上的一组函数依赖的集合。对关系模式R=而言有以下推理规则： （1）若YXU，则XY（自反律Reflexivity） （2）若XY，且ZU，则XZYZ（增广律 Augmentation） （