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

离散数学与计算机科学计算机科学导论第四讲,计算机科学技术学院陈意云0551-63607043,课 程 内 容,课程内容围绕学科理论体系中的模型理论,程序理论和计算理论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(x1);int g(int x)if(x=0)return 1 else if(x=1)return g(3)else return g(x2);非形式地描述，这两个C函数的语义都能讲清楚本讲座介绍，如何用数学语言给出它们的语义？,若x是偶数，结果为1；否则计算不终止,探讨的问题递归函数的语义,对应的两个递归数学函数的定义（x 0）f(x)if x=0 then 1 else x f(x1)g(x)if x=0 then 1 else(if x=1 then g(3)else g(x2)它们代表什么函数？函数：集合A到集合B的一种二元关系R，并且对任何aA，正好只有一个bB，使得a,bR例：阶乘函数 0,1,1,1,2,2,3,6,4,24,5,120,探讨的问题递归函数的语义,对应的两个递归数学函数的定义（x 0）f(x)if x=0 then 1 else x f(x1)g(x)if x=0 then 1 else(if x=1 then g(3)else g(x2)它们代表什么函数？函数：集合A到集合B的一种二元关系R，并且对任何aA，正好只有一个bB，使得a,bR偏函数（部分函数）：最多只有一个bB,探讨的问题递归函数的语义,对应的两个递归数学函数的定义（x 0）f(x)=if x=0 then 1 else x f(x1)g(x)=if x=0 then 1 else(if x=1 then g(3)else g(x2)把它们分别看成是关于f 和g的方程阶乘函数是第一个方程的解把f 用 0,1,1,1,2,2,3,6,代入，对于任意的自然数x，等式两边相等,探讨的问题递归函数的语义,对应的两个递归数学函数的定义（x 0）f(x)=if x=0 then 1 else x f(x1)g(x)=if x=0 then 1 else(if x=1 then g(3)else g(x2)把它们分别看成是关于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 z2.D上的二元关系的定义x y 当且仅当 x y x y3.整数上小于等于和小于关系分别是和的实例4.离散序 x y当且仅当x y，即不同的元素之间无关系,基 本 知 识,偏序集合有偏序关系 的集合D，记为D,1.上界若D,，则子集SD的上界是元素xD，具有性质：y:S.y x2.最小上界S的一 个上界，它小于等于S的任何其它上界3.线性序 x,y:S.x y y x,基 本 知 识,例 偏序集合a0,b0,a1,b1,a2,b2,，其中对任意i j都有ai aj,bj并且bi aj,bj 两个线性序a0a1a2，和b0b1b2 称它们为线性递增链 ai,bi有上界ai+1和bi+1等，但没有最小上界,基 本 知 识,完全偏序集合1.完全偏序集合D,（简称CPO）D中任何线性递增链a0a1a2都有最小上界2.最小上界的表示：a0,a1,a2,3.例 使用离散序，任何集合都可看成CPO 任何有限偏序集合都是CPO 考虑普通算术序，自然数集合不是CPO 有理数的非平凡闭区间不是CPO，例如，所有小于 的有理数的最小上界是无理数,基 本 知 识,完全偏序集合4.有底元（也叫最小元）的CPO D,存在元素a，使得对D的任何元素b都有a b5.D上的底元用 或D表示6.例为自然数集N增加底元，并定义偏序关系如图，则N 是有底元的CPO称为提升集合,基 本 知 识,例以集合关系为序即是两个集合的最小上界就是它们的并集即x y就是x y1.也可以为序，把图上下颠倒2.可以类似地定义下界、最大下界和顶元(最大元)等,基 本 知 识,序理论研究各种二元关系的数学理论格（lattice）在离散数学中有顶元和底元的D,称为格有顶元或底元的D,称为半格,基 本 知 识,函数序1.函数可以用二元集合表示 阶乘函数 0,1,1,1,2,2,3,6,平方函数 0,0,1,1,2,4,2.以函数的为偏序 则fg表示：f和g都有定义之处的函数值一样，但g可能定义在更多的变元上,基 本 知 识,单调函数 若D=D,D和E=E,E都是CPO，且f:D E 是它们基础集合上的函数，若dd蕴涵f(d)f(d),则f 单调 若f 单调且a0,a1,a2,是递增链，则 f(a0),f(a1),f(a2),也是递增链,例：从B到B的单调函数f()f(true)f(false)f()f(true)f(false)f0 f6 false truef1 true f7 true falsef2 false f8 false falsef3 true f9 true true truef4 false f10 false false falsef5 true true,下面的偏序关系图基于把函数值为理解成没有定义,基 本 知 识,连续函数 若D=D,D和E=E,E都是CPO，且f:D E 是它们基础集合上的函数，且对D的每个递增链 a0,a1,a2,，都有 f(a0),f(a1),f(a2),=f(a0,a1,a2,)例 在实轴闭区间x,y上，若把x,y看成CPO时，则通常计算意义下的连续函数仍然连续lim f(x)f(x0),xx0,基 本 知 识,连续函数 若D=D,D和E=E,E都是CPO，且f:D E 是它们基础集合上的函数，且对D的每个递增链 a0,a1,a2,，都有 f(a0),f(a1),f(a2),=f(a0,a1,a2,)例 在实轴闭区间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+1x:nat.x+1g(x:nat)=10 x:nat.10f 5(x:nat.x+1)5=5+1=6(f:nat nat.y:nat.fy)(x:nat.x+1)5=(y:nat.(x:nat.x+1)y)5=(y:nat.y+1)5=5+1=6,递归数学函数的不动点语义,递归定义的解与相应函数的不动点的重要联系递归定义f(x:D)=M的相应函数：f:.M（注：在此表示DD）函数f:.M的不动点正好是方程 f=M的解若(f:.M)N=N,即MN/f=N,则N是f=M的解方程f=M的求解就转化为找函数f:.M的不动点例：f(x)=if x=0 then 1 else x f(x1)的相应函数：F f:nat nat.y:nat.if x=0 then 1 else x f(x1)阶乘函数是F的不动点,递归数学函数的不动点语义,不动点语义函数f:.M的不动点作为递归定义f(x:D)=M的语义1.怎样计算得到不动点2.不动点可能不唯一，取哪个不动点作为语义不同场合有不同选择：最小或最大不动点（注：不动点集上的偏序关系：函数包含序）本讲座内容需要最小不动点，第九讲用到最大不动点,递归数学函数的不动点语义,不动点算子不动点算子是一簇函数，其类型是 fix:()fix为任何 的函数产生一个不动点 不动点算子的等式公理是fix=f:.f(fix f)使用表达式的演算规则，可得易于理解的等式fix g g(fix g)等式公理定向可得归约规则 fix f:.f(fix f)，fix g g(fix g),递归数学函数的不动点语义,把不动点算子用于阶乘函数定义阶乘函数定义的相应高阶函数是F f:nat nat.x:nat.if x=0 then 1 else x f(x1)(fixnatnat F)n/用不动点归约来计算n的阶乘 F(fixF)n(f:natnat.x:nat.if x=0 then 1 else x f(x-1)(fix F)n if n=0 then 1 else n(fix F)(n-1)从这里已经知道0的阶乘等于1若n 若n的值给定，则对fix F有限步展开可得n的阶乘,递归数学函数的不动点语义,最小不动点定理若D是有底元的CPO，且f:DD是连续函数，则f 有最小不动点 fix(f)=f n()|n 0 先证a 是不动点（a f n()|n 0）f(a)f(f n()|n 0)=f n+1()|n 0)/根据连续函数的性质 f n()|n 0和f n+1()|n 0的最小上界相同,因此f(a)=a 再证a是最小不动点（略）最后证明fix 连续（略）,编程语言递归函数的数学语义,C阶乘函数定义的相应高阶函数的最小不动点相应的高阶函数是（其连续性的证明略去）F f:nat nat.x:nat.if x=0 then 1 else x f(x1)计算过程：（Fn 表示对F最多展开n次）F0()=,F1()=0,0!,F2()=0,0!,1,1!F3()=0,0!,1,1!,2,2!,fix(F)=Fn()|n 0=,0,0!,0,0!,1,1!,0,0!,1,1!,2,2!,=阶乘函数,编程语言递归函数的数学语义,第二个C函数定义相应高阶函数的最小不动点g(x)if x=0 then 1 else(if x=1 then g(3)else g(x2)相应的高阶函数是F g:nat nat.x:nat=if x=0 then 1 else(if x=1 then g(3)else g(x2)计算过程：F0()=,F1()=0,1,F2()=0,1 F3()=,0,1,2,1,fix(F)=Fn()|n 0=,0,1,0,1,2,1,0,1,2,1,4,1,=f(x)=1（x为偶数）,编程语言递归函数的数学语义,第二个C函数定义相应高阶函数的其他不动点 1,x是偶数 h(x)=都是 a,x是奇数(a可任意取值)函数g:nat nat.x:nat=if x=0 then 1 else(if x=1 then g(3)else g(x2)的不动点 因为(g:nat nat.x:nat=if x=0 then 1 else(if x=1 then g(3)else g(x2)h=x:nat=if x=0 then 1 else(if x=1 then h(3)else h(x2)所得的这个函数就是函数h,编程语言递归函数的数学语义,为什么选择最小不动点C函数：int g(int x)if(x=0)return 1 else if(x=1)return g(3)else return g(x2);相应高阶函数：F g:nat nat.x:nat=if x=0 then 1 else(if x=1 then g(3)else g(x2)F的最小不动点 f(x)=1（x为偶数）最小不动点的特点：是定义得最少的不动点仅包括从递归定义能演绎出来的信息，没有来自对相应递归方程的任何“个人臆想”对某个变元没有定义，意味着计算不终止,编程语言递归函数的数学语义,实分析中的不动点求解实数方程 x=1+1/x经常用迭代方法求解 x:R.1+1/x(连续函数)0 5(迭代初值),xi(xi1),i 1得到的迭代序列1.2,1.833333,1.545455,1.647059,1.607143,1.622222,1.616438,1.618644,1.617801,1.618123,收敛于极限(1+5)/2，即上述连续函数的不动点,小 结,本讲座小结概述离散数学与计算机科学的关系。并以计算阶乘的递归程序为例，介绍完全偏序集合及其上函数的单调性、连续性、不动点等概念是怎样用于程序的语义解释的偏序理论在计算机科学中的应用程序理论的各个方面，如形式语义、类型论、程序分析、程序优化、程序验证都离不开偏序理论在计算机科学的很多其他方面也都涉及偏序这部分内容在“代数结构”课程中,小 结,离散数学是很多专业课程的先行课程数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等离散数学的发展方向离散数学自身研究方面的进展随着计算机科学的发展而深入，例如在下述方面都有很多的新成果，也有值得继续研究的问题研究智能推理的非经典逻辑领域专用的自动定理证明代数结构的深入探讨图论与群论相互结合的理论,