离散数学与计算机科学计算机科学导论第四讲

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,中国科大,*,离散数学与计算机科学,计算机科学导论第四讲,计算机科学技术学院,陈意云,0551-,6,3607043,课 程 内 容,课程内容,围绕学科理论体系中的模型理论,程序理论和计算理论,1.,模型理论关心的问题,给定模型,M,，哪些问题可以由模型,M,解决；如何比较模型的表达能力,2.,程序理论关心的问题,给定模型,M,，如何用模型,M,解决问题,包括程序设计范型、,程序设计语言,、程序设计、,形式语义,、类型论、程序验证、程序分析等,3.,计算理论关心的问题,给定模型,M,和一类问题,解决该类问题需多少资源,讲 座 提 纲,离散数学和计算机科学的关系,离散数学的特点、与计算机科学的关系,基本知识,偏序集合、,最小上界、完全偏序集合,、序理论、函数序、,函数的单调性和连续性,递归数学函数的不动点语义,函数的不动点、递归函数定义、递归函数定义的解、不动点算子、最小不动点定理,编程语言递归函数,的数学语义,最小不动点语义,离散数学和计算机科学的关系,本课程已谈及的相关内容,数理逻辑,经典逻辑、等式逻辑、程序逻辑、类型系统,都包括合式公式、公理、推理规则、演绎推理,集合论,良基关系、良基归纳法，偏序关系,(,本次课,),代数结构（抽象代数）,常见的抽象数据类型,(,表、栈、二叉树等,),是代数,本课程还会谈及,可计算性和算法分析等,离散数学和计算机科学的关系,离散数学的特点,离散数学是数学的几个分支的总称，研究基于离散而不是连续的数学结构,与光滑变化的实数不同，离散数学的研究对象,，,例如整数、图和逻辑中的命题,，都包含有区别和,分,离,的值,，但所包含的值并非,光滑变化,离散数学被视为处理可数集合,（,与,自然数,集,有相同,基数的集合）的数学分支,离散数学,无准确且普遍接受的定义，它,经常被定义为不包含连续变化量及相关概念的数学，,也用,包含什么内容的,方式来定义,离散数学和计算机科学的关系,离散数学和计算机科学的关系,离散数学的研究在,20,世纪后半叶，由于电子计算机的出现而迅猛发展,离散数学的概念和表示法在研究和描述计算机科学一些分支（如计算机算法、编程语言、自动定理证明、密码学和软件研发,),的对象和问题时非常有用,把离散数学的概念用于现实世界的问题时（如运筹学中的问题），,计算机,实现是十分重要的,离散数学和计算机科学的关系,本科期间的离散数学课程,数理逻辑、图论、代数结构（抽象代数）,使用离散数学知识的课程：,数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等,探讨的问题,递归函数的语义,两个,C,语言写的递归函数（,x,0,）,int f(int x),if(x=0)return 1 else return x,*,f(x,1,);,int g(int x),if(x=0)return 1,else if(x=1)return g(3),else return g(x,2,);,非形式地描述，这两个,C,函数的语义都能讲清楚,本讲座介绍，如何用数学语言给出它们的语义？,若,x,是偶数，结果为,1,；否则计算不终止,探讨的问题,递归函数的语义,对应的两个递归数学函数的定义（,x,0,）,f,(,x,),if,x,=0 then 1 else,x,f,(,x,1,),g,(,x,),if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),它们代表什么函数？,函数：集合,A,到集合,B,的一种二元关系,R,，并且对任何,a,A,，正好只有一个,b,B,，使得,a,b,R,例：阶乘函数,0,1,1,1,2,2,3,6,4,24,5,120,探讨的问题,递归函数的语义,对应的两个递归数学函数的定义（,x,0,）,f,(,x,),if,x,=0 then 1 else,x,f,(,x,1,),g,(,x,),if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),它们代表什么函数？,函数：集合,A,到集合,B,的一种二元关系,R,，并且对任何,a,A,，,正好只有一个,b,B,，使得,a,b,R,偏函数（部分函数）：,最多只有一个,b,B,探讨的问题,递归函数的语义,对应的两个递归数学函数的定义（,x,0,）,f,(,x,)=if,x,=0 then 1 else,x,f,(,x,1,),g,(,x,)=,if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),把它们分别看成是关于,f,和,g,的方程,阶乘函数是第一个方程的解,把,f,用,0,1,1,1,2,2,3,6,代入，对于,任意的自然数,x,，等式两边相等,探讨的问题,递归函数的语义,对应的两个递归数学函数的定义（,x,0,）,f,(,x,)=if,x,=0 then 1 else,x,f,(,x,1,),g,(,x,)=,if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),把它们分别看成是关于,f,和,g,的方程,阶乘函数是第一个方程的解,第二个方程有无数个解（,a,可取任意自然数）,1,x,是偶数,h,(,x,)=,a,x,是奇数,即,0,1,1,a,2,1,3,a,4,1,5,a,基 本 知 识,偏序关系（部分序关系）,1.,集合,D,上的二元关系,，具有如下三个性质,自反性：,x,:,D,.,x,x,反对称性：,x,y,:,D,.,x,y,y,x,x,=,y,传递性：,x,y,z,:,D,.,x,y,y,z,x,z,2,.D,上的二元关系,的定义,x,y,当且仅当,x,y,x,y,3.,整数上,小于等于和小于关系分别是和,的实例,4.,离散序,x,y,当且仅当,x,y,，即不同的元素之间无关系,基 本 知 识,偏序集合,有偏序关系,的集合,D,，记为,D,1.,上界,若,D,，则子集,S,D,的,上界,是元素,x,D,，,具有性质：,y,:,S,.,y,x,2.,最小上界,S,的一 个上界，它小于等于,S,的任何其它上界,3.,线性序,x,y,:,S,.,x,y,y,x,基 本 知 识,例,偏序集合,a,0,b,0,a,1,b,1,a,2,b,2,，,其中对任意,i,j,都有,a,i,a,j,b,j,并且,b,i,a,j,b,j,两个线性序,a,0,a,1,a,2,，和,b,0,b,1,b,2,称它们为线性递增链,a,i,b,i,有上界,a,i,+1,和,b,i,+1,等，,但没有最小上界,a,0,a,1,a,2,b,0,b,1,b,2,a,i,和,b,i,没有最小上界,基 本 知 识,完全偏序集合,1.,完全偏序集合,D,（简称,CPO,）,D,中任何线性递增链,a,0,a,1,a,2,都有最小上界,2.,最小上界的表示：,a,0,a,1,a,2,3.,例,使用离散序，任何集合都可看成,CPO,任何有限偏序集合都是,CPO,考虑普通算术序，自然数集合不是,CPO,有理数的非平凡闭区间不是,CPO，,例如，所有,小于,的有理数的最小上界是无理数,2,基 本 知 识,完全偏序集合,4.,有底元（也叫最小元,）的,CPO,D,存在元素,a,，,使得对,D,的任何元素,b,都有,a,b,5.,D,上的底元,用,或,D,表示,6.,例,为自然数集,N,增加,底元,，并定义偏序,关系如图，则,N,是有底元的,CPO,称为提升集合,0,1,2,3,4,CPO,N,的图形表示,基 本 知 识,例,以集合,关系为序,即,是,两个集合的最小,上界就是它们的并集,即,x,y,就是,x,y,1.,也可以,为序，把,图上下颠倒,2.,可以类似地定义下界、,最大下界和顶元,(,最大元,),等,d,1,d,2,d,3,d,1,d,2,d,1,d,3,d,2,d,3,d,1,d,2,d,3,(,),(,),基 本 知 识,序理论,研究各种二元关系的,数学理论,格（,lattice,）,在离散数学中,有顶元和底元的,D,称为格,有顶元或底元的,D,称为半格,d,1,d,2,d,3,d,1,d,2,d,1,d,3,d,2,d,3,d,1,d,2,d,3,(,),(,),基 本 知 识,函数序,1.,函数可以用二元集合表示,阶乘函数,0,1,1,1,2,2,3,6,平方函数,0,0,1,1,2,4,2.,以函数的,为偏序,则,f,g,表示：,f,和,g,都有,定义之处的函数值一样，但,g,可能定义在更多的变元上,0,1,1,1,2,1,常函数1,阶乘函数,0,1,1,1,2,2,0,1,1,1,0,1,0,5,.,.,.,.,.,.,.,.,基 本 知 识,单调函数,若,D,=,D,D,和,E,=,E,E,都是,CPO,，,且,f,:,D,E,是它们基础集合上的函数，,若,d,d,蕴涵,f,(,d,),f,(,d,),则,f,单调,若,f,单调且,a,0,a,1,a,2,是递增链,，则,f,(,a,0,),f,(,a,1,),f,(,a,2,),也是递增链,例：从,B,到,B,的单调函数,f,(,),f,(,true,),f,(,false,),f,(,),f,(,true,),f,(,false,),f,0,f,6,false,true,f,1,true,f,7,true false,f,2,false,f,8,false false,f,3,true,f,9,true,true true,f,4,false,f,10,false,false false,f,5,true true,f,0,f,1,f,2,f,3,f,4,f,5,f,6,f,7,f,8,f,9,f,10,下面的偏序关系图基于把函数值为,理解成没有定义,基 本 知 识,连续函数,若,D,=,D,D,和,E,=,E,E,都是,CPO,，,且,f,:,D,E,是它们基础集合上的函数，,且对,D,的每个递增链,a,0,a,1,a,2,，都有,f,(,a,0,),f,(,a,1,),f,(,a,2,),=,f,(,a,0,a,1,a,2,),例,在实轴闭区间,x,y,上，若把,x,y,看成,CPO,时，则通常计算意义下的连续函数仍然连续,lim,f,(,x,),f,(,x,0,),x,x,0,基 本 知 识,连续函数,若,D,=,D,D,和,E,=,E,E,都是,CPO,，,且,f,:,D,E,是它们基础集合上的函数，,且对,D,的每个递增链,a,0,a,1,a,2,，都有,f,(,a,0,),f,(,a,1,),f,(,a,2,),=,f,(,a,0,a,1,a,2,),例,在实轴闭区间,x,y,上，若把,x,y,看成,CPO,时，则通常计算意义下的连续函数仍然连续,任何,CPO,上的常函数是平凡地连续的,若,D,是离散序，则,D,上每个函数都连续,从提升集合,A,到任何,CPO,的单调函数连续,递归数学函数的不动点语义,函数的不动点,若,f,:,D,D,是,集合,D,到它,自身,的函数，,则,f,的不动点是使得,f,(,x,)=,x,的值,x,例,在,自然数上,平方函数的不动点有,0,和,1,恒等函数有无数个不动点,后继函数没有不动点,递归函数的不动点语义,函数的匿名表示：,抽象表示法,1.,通常的表示,如恒等函数,Id,(,x,:,nat,)=,x,Id,是函数名,不便于把函数当作一级对象来操作,2.,抽象表示法（抽象表达式是表达式的一种）,f,(,x,:,nat,)=,x,+1,x,:,nat,.,x,+1,g,(,x,:,nat,)=10,x,:,nat,.10,f,5,(,x,:,nat,.,x,+1),5=5+1=6,(,f,: