计算学科中的数学方法省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算学科中数学方法,数学基本特征,第1页,数学方法,是指处理数学问题策略、路径和步骤，它是计算学科中最根本研究方法。,理论上，凡能被计算机处理问题均能够转换为一个数学问题，换言之，全部,能被计算机处理问题均能够用数学方法处理,；,反之，凡能以离散数学为代表,结构性,数学方法描述问题，当该问题所包括,论域为有穷,，或虽为无穷但,存在有穷表示,时，这个问题也一定能用计算机来处理。,第2页,数学基本特征,高度抽象性,：,量关系和空间形式,逻辑严密性,：,严格恪守形式逻辑基本法则，充分确保逻辑可靠性，才能确保结论正确性。,普遍适用性,：,数学高度抽象性决定了它普遍适用性。,第3页,数学方法作用,为科学技术研究提供简练准确形式化语言,为科学技术研究提供数量分析和计算方法,为科学技术研究提供了逻辑推理工具,第4页,计算学科中数学方法,计算学科中惯用数学概念和术语,第5页,集合,集合概念,结构性数学方法基础。,集合就是一组无重复对象全体。,集合中对象称为集合元素。,如：计算机专业学生全部必修课程能够组成一个集合，其中每门课程就是这一集合中元素。,集合描述方法,通惯用大写字母表示集合，用小写字母表示元素,第6页,集合三种描述方法,枚举法：列出全部元素表示方法。,如,1,至,5,整数集合可表示为：,=,1,，,2,，,3,，,4,，,5,；,外延表示法：当集合中所列元素普通形式很显著时，可只列出部分元素，其它则用省略号表示。,如斐波那契数列可表示为：,0,，,1,，,1,，,2,，,3,，,5,，,8,，,13,，,21,，,34,，,；,谓词表示法：用谓词来概括集合中元素属性。,如斐波那契数列可表示为：,F,n,|,F,n,+2,=,F,n,+1,+F,n,，,F,0,=0,，,F,1,=,1,，,n,0,第7页,集合运算,集合并,设,A,、,B,为两个任意集合，全部属于,A,或属于,B,元素组成集合,C,，,称为,A,和,B,并集。可表示为：,C,A,B,x,x,A,x,B,。,求并集运算称为并（运算）。,例,5.1,若,A,=,a,，,b,，,c,，,d,，,B,=,b,，,d,，,e,，,求集合,A,和,B,并。,解：,A,B,a,，,b,，,c,，,d,，,e,第8页,集合差,设,A,、,B,为两个任意集合，全部属于,A,而不属于,B,一切元素组成集合,S,，,称为,A,和,B,差集。可表示为：,S,=,A,B,=,x,x,A,x,B,。,求差集运算称为差（运算）。,例,5.2 若,A,=,a,，,b,，,c,，,d,，,B,=,b,，,d,，,e,，,求集合,A,和,B,差。,解：,A,B,=,a,，,c,第9页,交集交,设,A,、,B,为两个任意集合，由和全部相同元素组成集合,C,，,称为,A,和,B,交集。可表示为：,C,A,B,x,x,A,x,B,。,求交集运算称为交（运算）。,例,5.3 若,A,=,x,|,x,-5，,B,=,x,|,x,5,x,x,1,x,5,x,1,第10页,集合补,设,I,为全集，,A,为,I,任意一子集，,I,A,则为,A,补集，记为。可表示为,=,I,A,=,x,x,I,，,求补集运算称为补（运算）求补集运算称为补（运算）,例,5.4,若,I,=,x,5,x,5,，,A,=,x,0,x,1,，,求。,解：,=,I,A,=,x,5,x,0,1,x,5,第11页,集合乘积,1集合,A,1,，,A,2,，,A,n,乘积普通使用方法国数学家笛卡尔（,Rene Descartes）,名字命名，即笛卡尔积。该乘积表示以下：,A,1,A,2,A,n,=（,a,1,，,a,2,，,a,n,）,a,i,A,i,，,i,1，2，,n,A,1,A,2,A,n,结果是一个有序元组集合。,例,5.5 若,A,=1，2，3，,B,=,a,，,b,，,求,A,B,。,解：,A,B,=（1，,a,），（1，,b,），（2，,a,），（2，,b,），（3，,a,），（3，,b,）,第12页,函数,函数又称映射，是指把输入转变成输出运算，该运算也可了解为从某一“定义域”对象到某一“值域”对象映射。函数是程序设计基础，程序定义了计算函数算法，而定义函数方法又影响着程序语言设计，好程序设计语言普通都便于函数计算。,设,f,为一个函数，当输入值为,a,时输出值为,b,，,则记作：,第13页,关系,关系是一个谓词，其定义域为,k,元组集合。通常关系为二元关系，其定义域为有序正确集合，在这个集合中，我们说有序正确第一个元素和第二个元素相关系。如学生选课,学生,课程,成绩,张三,文学,90,张三,哲学,95,李四,数学,80,李四,艺术,85,王五,历史,92,王五,文学,88,第14页,等价关系,在关系中，有一个特殊关系，即等价关系，它满足以下,3,个条件：,自反性，即对集合中每一个元素,a,，,都有,aRa,；,对称性，即对集合中任意元素,a,，,b,，,aRb,成立当且仅当,bRa,成立；,传递性，即对集合中任意元素,a,，,b,，,c,，,若,aRb,和,bRc,成立，则,aRc,一定成立。,等价关系一个主要性质是：集合,A,上一个等价关系,R,可将,A,划分为若干个互不相交子集，称为等价类。,第15页,例,5.6 证实非负整数,N,上模3同余关系,R,为等价关系,证实：首先将该关系形式化地表示为：,R,=(,a,，,b,),a,，,b,N,，,a,mod 3=,b,mod 3,自反性证实,对集合中任何一个元素,a,N,，,都有,a,mod 3=,a,mod 3；,对称性证实,对集合中任意元素,a,，,b,N,，,若,a,mod 3=,b,mod 3，,则有,b,mod 3=,a,mod 3；,传递性证实,对集合中任意元素,a,，,b,，,c,N,，,若,a,mod 3=,b,mod 3，,b,mod 3=,c,mod 3，,则有,a,mod 3=,c,mod 3。,第16页,例5.7,假设某人在唱歌（事件,e,1,）,同时，还能够开车（事件,e,2,）,或者步行（事件,e,3,），,但一个人不能同时开车和步行。,问：以上反应并发觉象，如用关系来表示时，是否是等价关系？,答：以上反应是一个并发（,co,）,现象，如用关系来表示，则这种并发关系含有自反性和对称性，,即可表示为：,e,1,co,e,1,，,e,2,co,e,2,，,e,3,co,e,3,；,及,e,1,co,e,2,（,或,e,2,co,e,1,），,e,1,co,e,3,（,或,e,3,co,e,1,），,不满足传递性，即（,e,2,co,e,1,）（,e,1,co,e,3,）,不能推出,e,2,co,e,3,，,即不能在开车同时，又步行。,所以，以上并发关系不是等价关系。,第17页,计算学科中数学方法,计算学科中惯用数学概念和术语,第18页,全部计算机程序设计语言都是形式语言，其组成基础同普通自然语言一样，也是符号或字母。惯用符号有数字（0,9）、大小写字母（,A,Z,，,a,z,）、,括号、运算符（+，-，*，/）等。,有限字母表指是由有限个任意符号组成非空集合，简称为字母表，用,表示。字母表上元素称作字符或符号，用小写字母或数字表示，如,a,、,b,、,c,、1、2、3,等。,第19页,字母表能够了解为计算机输入键盘上符号集合。字母能够了解为键盘上每一个英文字母、数字、标点符号、运算符号等。,字符串，也称为符号串，指是由字符组成有限序列，惯用小写希腊字母表示。字母表,上字符串以以下方式生成：,（1）,为,上一个特殊串，称为空串，对任何,a,，,a=a=a,；,（2）,若,是上符号串，且,a,，,则,a,是上符号串；,（3）若,是上符号串，当且仅当它由（1）和（2）导出。,第20页,直观来说，上符号串是由其上符号以任意次序拼接起来组成，任何符号都能够在串中重复出现。,作为一个特殊串，由零个符号组成。应该指出是，空串,不一样于我们计算机键盘上空格键。,语言指是给定字母表上字符串集合。,比如，当=,a,，,b,，,则,ab,，,aabb,，,abab,，,bba,、,、（,a,n,b,n,n,1,都是上语言。不包含任何字符串语言称作空语言，用,表示。注意：,不一样于,，,前者表示由空串组成语言，后者表示空语言。,第21页,语言是字符串集合，所以，传统集合运算（如并、交、差、补、笛卡尔积）对语言都适用。除此之外，语言还有一个主要专门运算，即闭包运算。,语言、文法以及自动机有着亲密关系。语言由文法产生。短语结构语言、上下文相关语言、上下文无关语言和正规语言分别由,0,型文法、,1,型文法、,2,型文法和,3,型文法产生。自动机是识别语言数学模型，各类文法所对应自动机分别是图灵机、线性有界自动机、下推自动机和有限状态自动机。,需要指出是，语言与数学模型不是一一对应关系，一个语言能够由不一样文法产生，也能够由不一样自动机识别。,第22页,定义、定理和证实是数学关键，也是计算学科理论形态关键内容。其中，定义是蕴含在公理系统之中概念和命题；定理是被证实为真数学命题；证实是为使人们确信一个命题是真而作一个逻辑论证。,例5.8,在欧氏几何中，平面角定义为：平面角是在一平面内，但不在一直线上两条相交线相互倾斜度；等腰三角形定理为：两边相等三角形为等腰三角形。,第23页,计算学科中数学方法,证实方法,第24页,直接证实,假定,p,为真，经过使用公理或已证实定理以及正确推理规则证实,q,也为真，以此证实蕴含式,p,q,为真。这种证实方法为直接证实法。,例5.9,用直接证实法证实“若,p,是偶数，则,p,2,是偶数”。,证实：假定,p,是偶数为真，设,p=,2,k,（,k,为整数）。由此可得，,p,2,=,2（2,k,2,）。,所以，,p,2,是偶数（它是一个整数2倍）。,第25页,间接证实,因为蕴含式,p,q,与其逆否命题,q,p,等价，所以能够经过证实,q,p,来证实蕴含式,p,q,为真。这种证实方法为间接证实法。,例5.10,用间接证实法证实“若,p,2,是偶数，则,p,是偶数”。,证实：假定此蕴含式后件为假，即假定,p,是奇数。则对某个整数,k,来说有,p=,2,k+,1。,由此可得,p,2,=,4,k,2,+4,k,+1=2（2,k,2,+2,k,）+1，,所以，,p,2,是奇数（它是一个整数2倍加1）。因为对这个蕴含式后件否定蕴含着前件为假，所以该蕴含式为真。,第26页,首先假定一个与原命题相反命题成立，然后经过正确推理得出与已知（或假设）条件、公理、已证过定理等相互矛盾或自相矛盾结果，以此证实原命题正确。这种证实方法就是反证法，也称归谬法，是一个惯用数学证实方法。,例5.11,证 是无理数,第27页,归纳法定义,所谓归纳法，是指从特殊推理出普通一个证实方法。归纳法可分为不完全归纳法、完全归纳法和数学归纳法。,2不完全归纳法,不完全归纳法是依据部分特殊情况作出推理一个方法，该方法多用于无穷对象论证，然而，论证结果不一定正确。所以，不完全归纳法不能作为严格证实方法。,3完全归纳法,完全归纳法也称穷举法，它是对命题中存在全部特殊情况进行考虑一个方法，用该方法论证结果是正确，然而，它只能用于“有限”对象论证。,第28页,数学归纳法形式化定义,依据数学归纳法原理，能够对数学归纳法形式化地定义为：,P,(1)()(,P,(,n,),P,(,n,+1),P,(,n,),例5.12,求证命题,P,(,n,)：“,从1开始连续,n,个奇数之和是,n,平方”，即公式,1+3+5+（2,n,1）=,n,2,成立。,第29页,证实,归纳基础：当,n,=1,时，等式成立，即1=1,2,归纳步骤：,设对任意,k,1，,P,(,k,),成立，即：,1+3+5+（2,K,1）=,K,2,而,1+3+5+(2,K,1)+(2(,K,+1)1),=,K,2,+2,K,+1=(,K,+1),2,则当,P,(,k,),成立时，,P,(,K,+1),也成立，依据数学归纳法，该命题得证。,第30页,结构性证实,结构性证实经过找出一个使得命题,P,(,a,),为真元素,a，,从而完成该函数值存在性证实称为结构性证实。,结构性证实方法是计算科学中广泛使用一个证实方法，本章,Armstrong,公理系统完备性证实就采取了结构性证实方法。,第31页,计算学科中数学方法,递归和迭代,:很多序列项经常能够以这么方,式得到：由,a,n,1,得到,a,n,，,按这么法则，,能够从一个已知首项开始，有限次地重,复做下去，最终产生一个序列，该序列是,实现递归和迭代基础。,第32页,递归及其相关概念,20世纪30年代，正是可计算递归函数理论与图灵机、,演算和,POST,规范系统等理论一起为计算理论建立奠定了基础。,递归关系指是：一个数列若干连续项之间关系,递归数列指是：由递归关系所确定数列。,递归过程指是：调用本身过程。,递归算法指是：包含递归过程算法。,递归程序指是：直接或间接调用本身程序。,递归方法（也称递推法），是一个在“有限”步骤内，依据特定法则或公式对一个或多个前面元素进行运算，以确定一系列元素（如数或函数）方法。,第33页,递归与数学归纳法,例5.13,计算5,6,计算方法之一：6，6+6=12，12+6=18，18+6=24，24+6=30；,计算方法之二：5,6，4,6，3,6，2,6，1,6；1,6+6=12，12+6=18，18+6=24，24+6=30；,从5,6开始计算，假设一个刚学乘法小学生计算不出这个数，那么，这个小学生普通会先计算4,6，然后再加6就能够了，若仍计算不出，则会再追溯到3,6，直到1,6，然后，再依次加6，最终得到30。这种计算方法其实就反应了一个递归思想，这个例子还能够用更普通递归关系表示：,a,n,=C,a,n,-1,+,g,(,n,)，2，3，4，,其中，,C,是已知常数，,g,(,n,),是一个已知数列。,第34页,递归由递归基础和递归步骤两部分组成。,数学归纳法是一个论证方法，而递归是算法和程序设计一个实现技术；,数学归纳法是递归基础。假如已知,a,n,-1,就能够确定,a,n,。,从数学归纳法角度来看，这相当于数学归纳法归纳步骤内容。但仅有这个关系，还不能确定这个数列，若使它完全确定，还应给出这个数列初始值,a,1,，,这相当于数学归纳法归纳基础内容。,第35页,递归定义功效,例：,序列：2，5，11，23，,a,n,=2,a,n,1,+1，,请给出其递归定义。,解 该序列递归定义以下：,a,1,=2；,递归基础,a,n,=2,a,n,1,+1，,n,=2，3，4，；,递归步骤,例5.15,给出阶乘,F,(,n,)=,n,!,递归定义,解 阶乘,F,(,n,)=,n,!,递归定义以下：,F,(0)=1；,递归基础,F,(,n,)=,n,F,(,n,1)，,n,=1，2，3，；,递归步骤,第36页,定义集合,例5.16,现有文法,G,生成式以下：,S,0,A,1,；,S,是文法,G,开始符号,A,01,；,递归基础,A,0,A,1,；,递归步骤,该文法其实定义了这么一个集合：,L,(,G,)=,0,n,1,n,|,n,1,，,这是一个以相同个数“,0,”和“,1,”组成字符串集合，即一个特殊语言。,将学习到该语言能够由各种文法产生（如,0,型文法、,2,型文法等），而图灵机与,0,型文法相对应，所以，图灵机能够识别该语言。,第37页,阿克曼函数,该函数是由希尔伯特学生、德国著名数学家威尔海姆阿克曼于1928年发觉。这是一个图灵机可计算，但不是原始递归函数。下面，我们介绍这个经典递归函数，并给出对应计算过程。,阿克曼函数：,第38页,解阿克曼函数递归算法:,Begin,if m=0 then n+1,else if n=0 then A(m-1,1),else A(m-1,A(m,n-1),End,第39页,计算,A,(1,2),解:,A,(1,2)=,A,(0,A,(1,1),=,A,(0,A,(0,A,(1,0),=,A,(0,A,(0,A,(0,1),=,A,(0,A,(0,2),=,A,(0,3),=4,第40页,迭代,迭代与递归有着亲密联络，甚至，一类如,X,0,=,a,，,X,n,+1,=,f,(,n,),递归关系也能够看作是数列一个迭代关系。,能够证实，迭代程序都能够转换为与它等价递归程序，,反之，则不然。就效率而言，递归程序实现要比迭代程序实现花费更多时间和空间。所以，在详细实现时，又希望尽可能将递归程序转化为等价迭代程序。,第41页,斐波那契数求解算法而言，能够使用迭代方法或递归方法来处理。,一些递归算法，如求解梵天塔问题算法就不能用迭代方法，而只能用递归方法。,第42页,计算学科中数学方法,公理化方法,第43页,理论体系,从数学角度来说，理论是基本概念、基本原理或定律（联络这些概念判断）以及由这些概念与原理逻辑推理出来结论组成集合，该概念能够形式化定义为：,T,=，,其中：,（1）表示理论；,（2）表示基本概念集合；,（3）表示基本原理或定律集合；,（4）表示由这些概念与原理逻辑推理出来结论组成集合。,第44页,构建理论体系惯用方法,每一个理论都由一组特定概念和一组特定命题组成。,在一个理论中，基本概念（原始概念）和基本命题（原始命题）必须是明确，不然就会出现“循环定义”和“循环论证”严重问题。,构建一个理论体系必须采取科学方法。,公理化方法,逻辑和历史相统一方法,从抽象上升到详细方法。,第45页,公理化方法,公理化方法，我们在第,1,章已作过简单介绍，这是一个结构理论体系演绎方法，,从尽可能少基本概念、公理出发，利用演绎推理规则，推出一系列命题，从而建立整个理论体系思想方法。,第46页,公理系统3个条件,用公理化构建理论体系称为公理系统，该公理系统需要满足无矛盾性、独立性和完备性条件。,（1）无矛盾性。,（2）独立性。,（3）完备性。,第47页,简单化是科学研究追求目标之一。普通而言，正确一定是简单（注意，这句话是单向，反之不一定成立）。,关于公理系统完备性要求，自哥德尔发表关于形式系统“不完备性定理”论文后，数学家们对公理系统完备性要求大大放宽了。,也就是说，能完备更加好，即使不完备，一样也含有主要价值。,第48页,公理化方法在计算学科中应用,公理化方法主要用于计算学科理论形态方面研究。在计算学科各分支领域，均采取了公理化方法。如,形式语义学,关系数据库理论,分布式代数系统,计算认知领域,第49页,例,5.18,正整数公理化概括,原始概念：,1,；,原始命题（公理）：任何正整数,n,或者等于,1,，或者能够从,1,开始，重复地“加,1,”来得到它。,第50页,例,5.19,平面几何公理化概括（欧氏几何）,以点、线、面为原始概念，以,5,条公设和,5,条公理为原始命题，给出了平面几何中,119,个定义，,465,条命题及其证实，组成了历史上第一个数学公理体系。,原始概念：点、线、面,原始命题（公设和公理）以下：,公设,1,：两点之间可作一条直线；,公设,2,：一条有限直线可不停延长；,公设,3,：以任意中心和直径能够画圆；,公设,4,：凡直角都彼此相等；,公设,5,：在平面上，过给定直线之外一点，存在且仅存在一条平行线，即所谓“平行公设（公理）”。,第51页,例,5.20,中国古代唯一一次公理化尝试：周髀算经,据相关记载，,周髀算经,成书于公元前,100,年左右。在,周髀算经,中，介绍了一个描述天象盖天学说，该学说构建了一个几何宇宙模型。,该学说中公理有两个：一个是“天地为平行平面，天地相距,80,000,里，在北极下方大地中央有一底面直径为,23,000,里，高为,60,000,里上尖下粗“璇玑”（即极下，极下阳光照不到，故不生万物）；,另一个是关于太阳光照以及人目所见极限范围，即“日照四旁各十六万七千里；人所望见，远近宜如日光所照”，其大意为，日光向四面照射极限距离是,167,000,里，人所见到也是这个距离。换言之，日光照不到,167,000,里之外，人也看不见,167,000,里之外。,第52页,从公理能够演绎出：夏至南万六千里，冬至南十三万五千里，日中立竿无影。此一者天道之数。周髀长八尺，夏至之日晷一尺六寸。髀者，股也；正晷者，勾也。正南千里，勾一尺五寸；正北千里，勾一尺七寸。其大意为，在某地竖一个,8,尺高竿，太阳移动了一千里，这个竿影子和原来相差一寸，即日影千里差一寸。,而从“日照四旁”,167,000,里，以及用公理演绎出冬至日道半径,238,000,里，又可导出宇宙半径为,405,000,里，从而构建了一个天、地为圆形平行平面宇宙模型。,第53页,今天，我们知道，这个宇宙模型描述与实际天象吻合得并不好，与同时代古希腊类似模型相比，也存在较大差距，而当初，我国天文学家完全能够用代数方法相当准确地处理一些天文学问题，至于宇宙终究是什么形状或结构，完全能够不去过问。然而，,周髀算经,是个例外，并成为我国古代学者惟一一次公理化方法尝试，这种思想，是受外来原因影响，还是我国本土科学中某种随机出现变异？已引发科学史领域教授极大兴趣。,第54页,计算学科中数学方法,形式化方法,第55页,详细公理系统和抽象公理系统,在欧氏几何公理系统中，原始概念（点、线、面）和全部公理都有直观背景或客观意义，像这么有现实世界背景公理系统，普通被称为详细公理系统。,因为非欧几何出现，使人们感到详细公理系统过于受直觉局限。因而，在19世纪末和20世纪初，一些出色数学家和逻辑学家开始了对抽象公理系统研究。,第56页,在抽象公理系统中，原始概念直觉意义被忽略，甚至没有任何预先设定意义，而公理也无需以任何实际意义为背景，它们无非是一些形式约定符号串。这时，抽象公理系统能够有各种解释。,形式化运算规则1+1能够解释为一个苹果加一个苹果，或者为一本书加一本书；,布尔代数抽象公理系统能够解释为相关命题真值命题代数，或者相关电路设计研究开关代数。,第57页,形式系统组成部分,初始符号。初始符号不含有任何意义。,形式规则。形式规则要求一个程序，借以判定哪些符号串是本系统中公式，哪些不是。,公理。即在本系统公式中，确定不加推导就能够断定公式集。,变形规则。变形规则亦称演绎规则或推导规则。变形规则要求，从已被断定公式，怎样得出新被断定公式。被断定公式又称为系统中定理。,第58页,形式系统基本特点,严格性,形式系统中，初始符号和形式规则都要进行严格定义，不允许出现在有限步内无法判定公式。形式系统采取是一个纯形式机械方法，它严格性高于普通数学推导。,抽象性,抽象性不是形式系统专利，抽象是人们认识客观世界基本方法，只不过形式系统含有更强抽象性。,形式系统抽象性表现在它本身仅仅是一个符号系统，除了表示符号间关系（字符号串变换）外，不表示任何别意义。,第59页,形式系统不足,不完备性,1931年，哥德尔提出关于形式系统“不完备性定理”指出：假如一个形式数学理论是足够复杂（复杂到全部递归函数在其中都能够表示），而且它是无矛盾，那么在这一理论中存在一个语句，而这一语句在这一理论中是既不能证实，也不能否证。,第60页,形式系统不足,不可判定性,假如对一类语句,C,而言，存在一个算法,AL，,使得对,C,中任一语句,S,而言，能够利用算法,AL,来判定其是否成立，则,C,称为可判定，不然，称为不可判定。,著名“停机问题”就是一个不可判定性问题。该问题是指，一个任给图灵机对于一个任给输入而言是否停机问题。图灵证实这类问题是不可判定。,需要指出是：计算机系统就是一个形式系统，所以，计算机系统一样也含有形式系统不足。,第61页,形式化与公理化,形式化不一定造成公理化，公理系统也不一定是形式系统。,如欧氏几何公理系统就不是形式系统。,形式化与公理化即使不一样，但在近代数学中，形式系统大都是形式化公理系统。,第62页,计算学科中数学方法,一个实例,Armstrong,公理系统,第63页,预备知识,定义1：设,R,=,是一个关系模式，其中，,R,是关系名，,U,为组成该关系属性名集合，,F,为,R,上一个函数依赖关系集合。设,X,，,Y U,，,r,Ins,(,R,)，,则对任何,u,，,v,r,，,只要,u,X,=,v,X,，,就必有,u,Y,=,v,Y,，,则称满足,X,Y,，,也称中存在函数依赖,X,Y,。,注：关系模式,R,=,上全部实例集合记作,Ins,(,R,)。,定义2：在关系模式,R,=,中，为,F,所逻辑蕴含函数依赖全体集合称为,F,闭包（,Closure），,记为,F,+,。,定义3：在关系模式,R,=,中，若,XU,，,则,X,+,=,A,|,X,A,能从,F,出发，由,Armstrong,公理系统推导出来，,X,+,称为属性集,X,关于函数依赖集,F,闭包。,第64页,算法,在实际工作中，普通不直接计算,F,+,，,而是经过计算,X,+,而到达一样目标。下面，给出计算属性闭包算法和一个例子。,算法：在关系模式,R,=,中，求属性集,X,(,X U,),关于函数依赖属性闭包,X,+,。,输入：关系模式,R,=,中全部属性集,U,，,在,U,上函数依赖,F,，,U,子集,X,。,输出：属性闭包,X,+,。,第65页,步骤：,（1）令,X,(0),=,X,，,i,=0,（2）,令,X,(,i,+1),=,X,(,i,),A,|,VX,(,i,),，,V,W,F,，,A,W,（3）,判断等式,X,(,i,+1),=,X,(,i,),是否成立，若成立则转（4），不然转（2）,（4）令,X,+,=,X,(,i,),，,输出,X,+,。,第66页,例,5.20,F,由以下5个函数依赖组成：,F=AC，BC，ABD，BCDE，DE,计算：(,BD,),+,（1）,X,(0),=,BD,（2）,X,(1),=,BD,C,，,即,X,(1),=,BDC,（,在此，将属性集,BD,和,C,并集,BD,C,简记为,BDC,，,下同），则,X,(1),X,(0),，,继续,（3）,X,(2),=,BDC,E,，,则,X,(2),X,(1),，,继续,（4）,X,(3),=,BDCE,，,则,X,(3),=,X,(2),，,所以(,BD,),+,=,X,(2),=,BDCE,。,第67页,Armstrong,公理系统3条公理,设,U,为关系模式,R,属性名集合，,F,是,U,上一组函数依赖集合。对关系模式,R,=,而言有以下推理规则：,（1）若,Y,X,U,，,则,X,Y,（,自反律,Reflexivity）,（2）,若,X,Y,，,且,ZU,，,则,XZ,YZ,（,增广律,Augmentation）,（3）,若,X,Y,及,Y,Z,，,则,X,Z,（,传递律,Transitivity）,以上3条公理组成了函数依赖一个有效而完备公理系统，该公理系统是数据库技术中模式分解算法理论基础。,第68页,Armstrong,公理系统正确性和完备性要求,建立函数依赖公理系统目标在于有效而准确地计算函数依赖逻辑蕴含，即从已知函数依赖推出未知函数依赖。这里有两个要求，一个要求是用公理系统推出全部函数依赖都是正确；另一个要求是确保每一个函数依赖都能够用该公理系统推出，假如,F,+,中竟然存在一个函数依赖不能用这些公理推出，那么这些公理就不够用，就不完全，就得补充新公理。,显然，以上第一个要求是要证实公理系统正确性，第二个要求是要证实公理系统完备性。,第69页,证实：分别证实自反律、增广律和传递律正确性。,（,1,）设,r,Ins,(,R,),，,t,，,s,r,，,X,，,Y U,，,YX,若,tX=sX,，,依据条件,Y X,，,则必有,tY=sY,。,依据函数依赖定义，若,t,X,=,s,X,，,必有,t,Y,=,s,Y,，,则,X,Y,成立,(,自反律得证,),。,（,2,）设,r,Ins,(,R,),，,t,，,s,r,，,X,，,Y,，,ZU,，,X,Y,若,t,XZ,=,s,XZ,，,则有,t,X,=,s,X,及,t,Z,=,s,Z,再依据条件,X,Y,以及,t,X,=,s,X,，,则必有,t,Y,=,s,Y,第70页,由、可知，,t,Y,=,s,Y,，,t,Z,=,s,Z,，,即,t,YZ,=,s,YZ,。,依据函数依赖定义，若,t,XZ,=,s,XZ,，,必有,t,YZ,=,s,YZ,，,则,XZ,YZ,成立（增广律得证）。,（,3,）设,r,Ins,(,R,),，,t,，,s,r,，,X,，,Y,，,ZU,，,X,Y,，,Y,Z,若,t,X,=,s,X,，,依据条件,X,Y,，,则必有,t,Y,=,s,Y,。,再依据条件,Y,Z,及,t,Y,=,s,Y,，,则必有,t,Z,=,s,Z,。,依据函数依赖定义，若,t,X,=,s,X,，,必有,t,Z,=,s,Z,，,则,X,Y,成立（传递律得证）。,第71页,计算学科中数学方法,练习题,第72页,1.数学有哪些基本特征？,2,数学方法有什么作用？,3,什么叫集合？集合基本运算有哪几个？,4,什么是函数？,5,什么是关系？等价关系要满足哪些条件？,6,并发关系是否是等价关系,?,试举例说明。,7,什么是字符串？什么是语言？语言、文法与自动机有何关系？,第73页,8,什么是布尔值？布尔运算定义？,9,数学方法中有哪几个证实方法？,10,请用伪代码给出求解斐波那契数递归算法。,11,求以下阿克曼函数值：,（,1,）,A,(0,1),（,2,）,A,(1,0),（,3,）,A,(1,1),（,4,）,A,(2,1),（,5,）,A,(2,2),第74页,12,什么是递归和迭代？二者有何联络？,13,给出“理论”形式化定义。,14,构建理论体系惯用方法有哪些？,15,简述公理系统,3,个条件。,16,分别对正整数、平面几何（欧氏几何）进行公理化概括。,17,什么是形式化方法？形式化系统由哪几部分组成？,第75页,