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

《离散数学与计算机科学计算机科学导论第四讲.ppt》由会员分享，可在线阅读，更多相关《离散数学与计算机科学计算机科学导论第四讲.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学与计算机科学计算机科学导论第四讲 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望课课 程程 内内 容容课程内容课程内容围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论,程序理论和计算理论程序理论和计算理论1.模型理论关心的问题模型理论关心的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M解决；如何解决；如何比较模型的表达能力比较模型的表达能力2.程序理论关心的问题程序理论关心的问题给定模型给定模型M，如何用模型，如何用模型M解决问

2、题解决问题包括程序设计范型、包括程序设计范型、程序设计语言程序设计语言、程序设计、程序设计、形式语义形式语义、类型论、程序验证、程序分析等、类型论、程序验证、程序分析等3.计算理论关心的问题计算理论关心的问题给定模型给定模型M和一类问题和一类问题,解决该类问题需多少资源解决该类问题需多少资源讲讲 座座 提提 纲纲离散数学和计算机科学的关系离散数学和计算机科学的关系离散数学的特点、与计算机科学的关系离散数学的特点、与计算机科学的关系基本知识基本知识偏序集合、偏序集合、最小上界、完全偏序集合最小上界、完全偏序集合、序理论、序理论、函数序、函数序、函数的单调性和连续性函数的单调性和连续性递归数学函数

3、的不动点语义递归数学函数的不动点语义函数的不动点、递归函数定义、递归函数定义的函数的不动点、递归函数定义、递归函数定义的解、不动点算子、最小不动点定理解、不动点算子、最小不动点定理编程语言递归函数编程语言递归函数的数学语义的数学语义最小不动点语义最小不动点语义离散数学和计算机科学的关系离散数学和计算机科学的关系本本课课程已程已谈谈及的相关内容及的相关内容数理逻辑数理逻辑经典逻辑、等式逻辑、程序逻辑、类型系统经典逻辑、等式逻辑、程序逻辑、类型系统都包括合式公式、公理、推理规则、演绎推理都包括合式公式、公理、推理规则、演绎推理集合论集合论良基关系、良基归纳法，偏序关系良基关系、良基归纳法，偏序关系

4、(本次课本次课)代数结构（抽象代数）代数结构（抽象代数）常见的抽象数据类型常见的抽象数据类型(表、栈、二叉树等表、栈、二叉树等)是代数是代数本课程还会谈及本课程还会谈及可计算性和算法分析等可计算性和算法分析等离散数学和计算机科学的关系离散数学和计算机科学的关系离散数学的特点离散数学的特点离散数学是数学的几个分支的总称，研究基于离离散数学是数学的几个分支的总称，研究基于离散而不是连续的数学结构散而不是连续的数学结构与光滑变化的实数不同，离散数学的研究对象与光滑变化的实数不同，离散数学的研究对象，例如整数、图和逻辑中的命题例如整数、图和逻辑中的命题，都包含有区别和，都包含有区别和分分离离的值的值，

5、但所包含的值并非，但所包含的值并非光滑变化光滑变化离散数学被视为处理可数集合离散数学被视为处理可数集合（与与自然数自然数集集有相有相同同基数的集合）的数学分支基数的集合）的数学分支离散数学离散数学无准确且普遍接受的定义，它无准确且普遍接受的定义，它经常被定经常被定义为不包含连续变化量及相关概念的数学，义为不包含连续变化量及相关概念的数学，也用也用包含什么内容的包含什么内容的方式来定义方式来定义离散数学和计算机科学的关系离散数学和计算机科学的关系离散数学和离散数学和计计算机科学的关系算机科学的关系离散数学的研究在离散数学的研究在20世世纪纪后半叶，由于后半叶，由于电电子子计计算算机的出机的出现现

6、而迅猛而迅猛发发展展离散数学的概念和表示法在研究和描述离散数学的概念和表示法在研究和描述计计算机科算机科学一些分支（如学一些分支（如计计算机算法、算机算法、编编程程语语言、自言、自动动定定理理证证明、密明、密码码学和学和软软件研件研发发)的的对对象和象和问题时问题时非常非常有用有用把离散数学的概念用于现实世界的问题时（如运把离散数学的概念用于现实世界的问题时（如运筹学中的问题），筹学中的问题），计算机计算机实现是十分重要的实现是十分重要的离散数学和计算机科学的关系离散数学和计算机科学的关系本科期本科期间间的离散数学的离散数学课课程程数理数理逻辑逻辑、图论图论、代数、代数结结构（抽象代数）构（抽

7、象代数）使用离散数学知识的课程：使用离散数学知识的课程：数据结构、操作系统、编译技术、人工智能、数数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等据库、算法设计与分析、程序设计语言基础等探讨的问题探讨的问题递归函数的语义递归函数的语义两个两个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);非形式地描述，这两个非形式地描述，这两个

8、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

9、 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

10、,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，等式两边相等，等式两边相等探讨的问

11、题探讨的问题递归函数的语义递归函数的语义对应的两个递归数学函数的定义（对应的两个递归数学函数的定义（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 ,基基 本本 知知 识识偏序关系

12、（部分序关系）偏序关系（部分序关系）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，记为，记为

13、D,1.上界上界若若 D,，则子集，则子集S D的的上界上界是元素是元素x D，具具有性质：有性质：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等，等，但没有最小上界但没有最小上界a0a1a2b

14、0b1b2 ai和和bi没有最小上界没有最小上界基基 本本 知知 识识完全偏序集合完全偏序集合1.完全偏序集合完全偏序集合 D,（简称（简称CPO）D中任何线性递增链中任何线性递增链a0a1a2都有最小上界都有最小上界2.最小上界的表示：最小上界的表示：a0,a1,a2,3.例例 使用离散序，任何集合都可看成使用离散序，任何集合都可看成CPO 任何有限偏序集合都是任何有限偏序集合都是CPO 考虑普通算术序，自然数集合不是考虑普通算术序，自然数集合不是CPO 有理数的非平凡闭区间不是有理数的非平凡闭区间不是CPO，例如，所有例如，所有小小于于 的有理数的最小上界是无理数的有理数的最小上界是无理数

15、 2基基 本本 知知 识识完全偏序集合完全偏序集合4.有底元（也叫最小元有底元（也叫最小元）的）的CPO D,存在元素存在元素a，使得对使得对D的任何元素的任何元素b都有都有a b5.D上的底元上的底元用用 或或 D表示表示6.例例为自然数集自然数集N N增加增加底元底元，并定义偏序，并定义偏序关系如图，则关系如图，则N N 是有底元的是有底元的CPO称称为提升集合提升集合01234 CPO N N 的图形表示的图形表示基基 本本 知知 识识例例以集合以集合关系关系为序序即即是是两个集合的最小两个集合的最小上界就是它上界就是它们的并集的并集即即x y就是就是x y1.也可以也可以为序，把为序，

16、把图上下颠倒图上下颠倒2.可以类似地定义下界、可以类似地定义下界、最大下界和顶元最大下界和顶元(最大元最大元)等等d1d2d3d1,d2d1,d3d2,d3d1,d2,d3()()基基 本本 知知 识识序理序理论研究各种二元关系的研究各种二元关系的数学理数学理论格（格（lattice）在离散数学中在离散数学中有有顶元和底元的元和底元的 D,称为格称为格有有顶元或底元的元或底元的 D,称为半格称为半格d1d2d3d1,d2d1,d3d2,d3d1,d2,d3()()基基 本本 知知 识识函数序函数序1.函数可以用二元集合表示函数可以用二元集合表示 阶乘函数阶乘函数 0,1,1,1,2,2,3,6

17、,平方函数平方函数 0,0,1,1,2,4,2.以函数的以函数的为偏序偏序 则fg表示：表示：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,D 和和E E=E,E 都都是是CPO，且且f:D E 是是它它们们基基础础集集合合上上的的函函数数，若若dd 蕴蕴涵涵f(d)f(d),则则f 单调单调 若若f 单调且单调且a0,a1,a2,是递增链是递增链，则，则 f(a0),f(a

18、1),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 f0f1f2f3 f4f5f6f7 f8f9f10 下面的偏序关系图基于把下面的偏序关系图基于把函数值为函数值为 理解成没有定义理解成没有定义基基 本本 知知 识识连续函数连续函数 若若D

19、D=D,D 和和E 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,D 和和E E=E,E 都都是是CPO，且且f:D E 是它们基础集合上的函数，是它们基础集合上的函数，且对且对D的每个递增链

20、的每个递增链 a0,a1,a2,，都有，都有 f(a0),f(a1),f(a2),=f(a0,a1,a2,)例例 在在实实轴轴闭闭区区间间x,y上上，若若把把x,y看看成成CPO时时，则通常计算意义下的连续函数仍然连续则通常计算意义下的连续函数仍然连续 任何任何CPO上的常函数是平凡地连续的上的常函数是平凡地连续的 若若D D是离散序，则是离散序，则D D上每个函数都连续上每个函数都连续 从提升集合从提升集合A 到任何到任何CPO的单调函数连续的单调函数连续递归数学函数的不动点语义递归数学函数的不动点语义函数的不动点函数的不动点若若f:D D是是集合集合D 到它到它自身自身的函数，的函数，则则

21、f 的不动的不动点是使得点是使得f(x)=x的值的值x例例在在自然数上自然数上 平方函数的不动点有平方函数的不动点有0和和1 恒等函数有无数个不动点恒等函数有无数个不动点 后继函数没有不动点后继函数没有不动点递归函数的不动点语义递归函数的不动点语义函数的匿名表示：函数的匿名表示：抽象表示法抽象表示法1.通常的表示通常的表示如恒等函数如恒等函数Id(x:nat)=x,Id是函数名是函数名不便于把函数当作一级对象来操作不便于把函数当作一级对象来操作2.抽象表示法（抽象表示法（抽象表达式是抽象表达式是 表达式的一种）表达式的一种）f(x:nat)=x+1 x:nat.x+1g(x:nat)=10 x

22、: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的求解的求解就就转化

23、转化为为找函数找函数 f:.M的不动的不动点点例：例：f(x)=if x=0 then 1 else x f(x 1)的相应函数：的相应函数：F f:nat nat.y:nat.if x=0 then 1 else x f(x 1)阶乘函数是阶乘函数是F的不动点的不动点递归数学函数的不动点语义递归数学函数的不动点语义不动点语义不动点语义函数函数 f:.M的不动的不动点作为点作为递归定义递归定义f(x:D)=M的的语义语义1.怎样计算得到不动点怎样计算得到不动点2.不动点可能不唯一，取哪个不动点作为语义不动点可能不唯一，取哪个不动点作为语义不同场合有不同选择：最小或最大不动点不同场合有不同选择：

24、最小或最大不动点（注：不动点集上的偏序关系：函数包含序）（注：不动点集上的偏序关系：函数包含序）本讲座内容需要最小不动点，第九讲用到最大不本讲座内容需要最小不动点，第九讲用到最大不动点动点递归数学函数的不动点语义递归数学函数的不动点语义不动点算子不动点算子不动点算子是一簇函数，其类型是不动点算子是一簇函数，其类型是 fix :()fix 为任何为任何 的函数产生一个不动点的函数产生一个不动点 不动点算子的等式公理是不动点算子的等式公理是fix =f:.f(fix f)使用使用 表达式的演算规则，可得易于理解的等式表达式的演算规则，可得易于理解的等式fix g g(fix g)等式公理定向可得归

25、约规则等式公理定向可得归约规则 fix f:.f(fix f)，fix g g(fix g)递归数学函数的不动点语义递归数学函数的不动点语义把不动点算子用于阶乘函数定义把不动点算子用于阶乘函数定义阶乘函数阶乘函数定义的相应高阶函数定义的相应高阶函数是是F f:nat nat.x:nat.if x=0 then 1 else x f(x 1)(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)

26、(n-1)从这里已经知道从这里已经知道0的阶乘等于的阶乘等于1若若n 若若n的值给定，则对的值给定，则对fix F有限步展开可得有限步展开可得n的阶乘的阶乘递归数学函数的不动点语义递归数学函数的不动点语义最小不动点定理最小不动点定理若若D 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的的最最小小上上界界相相同同

27、,因此因此f(a)=a 再证再证a是最小不动点（略）是最小不动点（略）最后证明最后证明fix 连续（略）连续（略）编程语言递归函数的数学语义编程语言递归函数的数学语义C阶乘函数定义的相应高阶函数的最小不动点阶乘函数定义的相应高阶函数的最小不动点相应的高阶函数相应的高阶函数是是（其连续性的证明略去）（其连续性的证明略去）F f:nat nat.x:nat.if x=0 then 1 else x f(x 1)计算过程：（计算过程：（Fn 表示对表示对F最多展开最多展开n次）次）F0()=,F1()=0,0!,F2()=0,0!,1,1!F3()=0,0!,1,1!,2,2!,fix(F)=Fn(

28、)|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(x 2)相应的高阶函数相应的高阶函数是是F g:nat nat.x:nat=if x=0 then 1 else(if x=1 then g(3)else g(x 2)计算过程：计算过程：F0()=,F1()=0,1,F2()=0,1 F3()=,0,1,2,1 ,fix(F)=F

29、n()|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(x 2)的不动的不动点点 因为因为(g:nat nat.x:nat=if x=0 then 1 else (if x=1 then g(3)else g(x

30、 2)h =x:nat=if x=0 then 1 else (if x=1 then h(3)else h(x 2)所得的这个函数就是函数所得的这个函数就是函数h编程语言递归函数的数学语义编程语言递归函数的数学语义为什么选择最小不动点为什么选择最小不动点C函数：函数：int g(int x)if(x=0)return 1 else if(x=1)return g(3)else return g(x 2);相应高阶函数：相应高阶函数：F g:nat nat.x:nat=if x=0 then 1 else(if x=1 then g(3)else g(x 2)F的最小不动点的最小不动点 f(x

31、)=1（x为偶数）为偶数）最小不动点的特点：最小不动点的特点：是定义得最少的不动点是定义得最少的不动点仅包括从递归定义能演绎出来的信息，没有来自仅包括从递归定义能演绎出来的信息，没有来自对相应递归方程的任何对相应递归方程的任何“个人臆想个人臆想”对某个变元没有定义，意味着计算不终止对某个变元没有定义，意味着计算不终止编程语言递归函数的数学语义编程语言递归函数的数学语义实分析中的不动点实分析中的不动点求解实数方程求解实数方程 x=1+1/x经常用迭代方法求解经常用迭代方法求解 x:R.1+1/x(连续函数连续函数)0 5(迭代初值迭代初值),xi (xi 1),i 1得到的迭代序列得到的迭代序列

32、1.2,1.833333,1.545455,1.647059,1.607143,1.622222,1.616438,1.618644,1.617801,1.618123,收敛于极限收敛于极限(1+5)/2，即上述连续函数的不动点，即上述连续函数的不动点小小 结结本讲座小结本讲座小结概述离散数学与计算机科学的关系。概述离散数学与计算机科学的关系。并并以计算阶以计算阶乘的递归程序为例，介绍完全偏序集合及其上函数乘的递归程序为例，介绍完全偏序集合及其上函数的单调性的单调性、连续性连续性、不动点等概念是怎样用于程序不动点等概念是怎样用于程序的语义解释的的语义解释的偏序理论在计算机科学中的应用偏序理论在

33、计算机科学中的应用程序理论的各个方面，如形式语义、类型论、程程序理论的各个方面，如形式语义、类型论、程序分析、程序优化、程序验证都离不开偏序理论序分析、程序优化、程序验证都离不开偏序理论在计算机科学的很多其他方面也都涉及偏序在计算机科学的很多其他方面也都涉及偏序这部分内容在这部分内容在“代数结构代数结构”课程中课程中小小 结结离散数学是很多专业课程的先行课程离散数学是很多专业课程的先行课程数数据据结结构构、操操作作系系统统、编编译译技技术术、人人工工智智能能、数数据库、算法设计与分析、程序设计语言基础等据库、算法设计与分析、程序设计语言基础等离散数学的发展方向离散数学的发展方向离散数学自身研究方面的进展随着计算机科学的离散数学自身研究方面的进展随着计算机科学的发展而深入，例如在下述方面都有很多的新成果，发展而深入，例如在下述方面都有很多的新成果，也有值得继续研究的问题也有值得继续研究的问题研究智能推理的非经典逻辑研究智能推理的非经典逻辑领域专用的自动定理证明领域专用的自动定理证明代数结构的深入探讨代数结构的深入探讨图论与群论相互结合的理论图论与群论相互结合的理论