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

1、离散数学与计算机科学计算机科学导论第四讲0551-61课 程 内 容课程内容围绕学科理论体系中的模型理论, 程序理论和计算理论1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力2. 程序理论关心的问题给定模型M，如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3. 计算理论关心的问题给定模型M和一类问题, 解决该类问题需多少资源2讲 座 提 纲离散数学和计算机科学的关系离散数学的特点、与计算机科学的关系基本知识偏序集合、最小上界、完全偏序集合、序理论、函数序、函数的单调性和连续性递归数学函数的不动点语义函数

2、的不动点、递归函数定义、递归函数定义的解、不动点算子、最小不动点定理编程语言递归函数的数学语义最小不动点语义3离散数学和计算机科学的关系本课程已谈及的相关内容数理逻辑经典逻辑、等式逻辑、程序逻辑、类型系统都包括合式公式、公理、推理规则、演绎推理集合论良基关系、良基归纳法，偏序关系(本次课)代数结构（抽象代数） 常见的抽象数据类型 (表、栈、二叉树等) 是代数本课程还会谈及可计算性和算法分析等4离散数学和计算机科学的关系离散数学的特点离散数学是数学的几个分支的总称，研究基于离散而不是连续的数学结构与光滑变化的实数不同，离散数学的研究对象，例如整数、图和逻辑中的命题，都包含有区别和分离的值，但所包

3、含的值并非光滑变化离散数学被视为处理可数集合（与自然数集有相同基数的集合）的数学分支离散数学无准确且普遍接受的定义，它经常被定义为不包含连续变化量及相关概念的数学，也用包含什么内容的方式来定义5离散数学和计算机科学的关系离散数学和计算机科学的关系离散数学的研究在20世纪后半叶，由于电子计算机的出现而迅猛发展离散数学的概念和表示法在研究和描述计算机科学一些分支（如计算机算法、编程语言、自动定理证明、密码学和软件研发)的对象和问题时非常有用把离散数学的概念用于现实世界的问题时（如运筹学中的问题），计算机实现是十分重要的6离散数学和计算机科学的关系本科期间的离散数学课程数理逻辑、图论、代数结构（抽象

4、代数）使用离散数学知识的课程：数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等7探讨的问题递归函数的语义两个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；否则计算不终止8探讨的问题递归函数的语义对应的两个递归数学函数的定义（

5、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, 9探讨的问题递归函数的语义对应的两个递归数学函数的定义（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)

6、else g(x2)它们代表什么函数？函数：集合A到集合B的一种二元关系R，并且对任何aA，正好只有一个bB，使得a, bR偏函数（部分函数）：最多只有一个bB 10探讨的问题递归函数的语义对应的两个递归数学函数的定义（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，等式两边相等11探讨的问题递归函数的语义对应的

7、两个递归数学函数的定义（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 , 12基 本 知 识偏序关系（部分序关系）1. 集合D上的二元关系，具有如下三个性质 自反性：x:D. x x 反对称性：x, y:D. x y y x x =

8、 y 传递性：x, y, z:D. x y y z x z2. D上的二元关系的定义x y 当且仅当 x y x y3. 整数上小于等于和小于关系分别是和的实例4. 离散序 x y当且仅当x y，即不同的元素之间无关系13基 本 知 识偏序集合有偏序关系 的集合D，记为D, 1. 上界若D, ，则子集SD的上界是元素xD，具有性质： y:S. y x2. 最小上界S的一 个上界，它小于等于S的任何其它上界3. 线性序 x, y:S. x y y x14基 本 知 识例 偏序集合a0, b0, a1, b1, a2, b2, ，其中对任意i j都有ai aj, bj并且bi aj, bj 两个线

9、性序a0a1a2，和b0b1b2 称它们为线性递增链 ai, bi有上界ai+1和bi+1等，但没有最小上界a0a1a2b0b1b2 ai和bi没有最小上界15基 本 知 识完全偏序集合1. 完全偏序集合D, （简称CPO） D中任何线性递增链a0a1a2都有最小上界2. 最小上界的表示：a0, a1, a2, 3. 例 使用离散序，任何集合都可看成CPO 任何有限偏序集合都是CPO 考虑普通算术序，自然数集合不是CPO 有理数的非平凡闭区间不是CPO，例如，所有小于 的有理数的最小上界是无理数 216基 本 知 识完全偏序集合4. 有底元（也叫最小元）的CPO D, 存在元素a，使得对D的任

10、何元素b都有a b5. D上的底元用 或D表示6. 例为自然数集N增加底元，并定义偏序关系如图，则N 是有底元的CPO称为提升集合01234 CPO N的图形表示17基 本 知 识例以集合关系为序即是两个集合的最小上界就是它们的并集即x y就是x y1. 也可以为序，把图上下颠倒2. 可以类似地定义下界、最大下界和顶元(最大元)等d1d2d3d1, d2d1, d3d2, d3d1, d2, d3()()18基 本 知 识序理论研究各种二元关系的数学理论格（lattice）在离散数学中有顶元和底元的D, 称为格有顶元或底元的D, 称为半格d1d2d3d1, d2d1, d3d2, d3d1,

11、d2, d3()()19基 本 知 识函数序1. 函数可以用二元集合表示 阶乘函数 0,1,1,1,2,2, 3,6, 平方函数 0,0,1,1,2,4, 2. 以函数的为偏序 则fg表示： f和g都有定义之处的函数值一样，但g可能定义在更多的变元上0,1,1,1,2,1常函数1阶乘函数0,1,1,1,2,20,1,1,10,10,5. . . . . . . . . . . . . . . . .20基 本 知 识单调函数 若D =D, D和E =E, E都是CPO，且f : D E 是它们基础集合上的函数，若dd蕴涵f(d) f (d), 则f 单调 若f 单调且a0, a1, a2, 是

12、递增链 ，则 f (a0), f (a1), f (a2), 也是递增链21例：从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 下面的偏序关系图基于把函数值为理解成没有定义22基 本 知 识连续函数 若D =D, D和E =E,

13、 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)xx023基 本 知 识连续函数 若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上，若

14、把x, y看成CPO时，则通常计算意义下的连续函数仍然连续 任何CPO上的常函数是平凡地连续的 若D是离散序，则D上每个函数都连续 从提升集合A到任何CPO的单调函数连续24递归数学函数的不动点语义函数的不动点若f :D D是集合D 到它自身的函数，则f 的不动点是使得f (x) = x的值x例在自然数上 平方函数的不动点有0和1 恒等函数有无数个不动点 后继函数没有不动点25递归函数的不动点语义函数的匿名表示： 抽象表示法1. 通常的表示如恒等函数Id(x : nat) = x, Id是函数名不便于把函数当作一级对象来操作2. 抽象表示法（ 抽象表达式是表达式的一种）f(x : nat) =

15、 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 = 626递归数学函数的不动点语义递归定义的解与相应函数的不动点的重要联系递归定义f (x:D) = M的相应函数：f :. M（注： 在此表示DD）函数f :.M的不动点正好是方程 f = M的解若(f :.M)N = N, 即MN/f = N, 则N是f = M的解方程f =

16、 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的不动点27递归数学函数的不动点语义不动点语义函数f :.M的不动点作为递归定义f (x:D) = M的语义1. 怎样计算得到不动点2. 不动点可能不唯一，取哪个不动点作为语义不同场合有不同选择：最小或最大不动点（注：不动点集上的偏序关系：函数包含序）本讲座内容需要最小不动点，第九讲用到最大不动点28递归数学函数的不动点语义不动点算子不动点算子是一簇函数，其类型是

17、 fix : ( ) fix为任何 的函数产生一个不动点 不动点算子的等式公理是fix = f: .f (fix f )使用表达式的演算规则，可得易于理解的等式fix g g(fix g) 等式公理定向可得归约规则 fix f: .f (fix f )， fix g g(fix g)29递归数学函数的不动点语义把不动点算子用于阶乘函数定义阶乘函数定义的相应高阶函数是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 th

18、en 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的阶乘30递归数学函数的不动点语义最小不动点定理若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 (

19、a) = a 再证a是最小不动点（略） 最后证明fix 连续（略）31编程语言递归函数的数学语义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!, = 阶乘函数32编

20、程语言递归函数的数学语义第二个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为偶数）33

21、编程语言递归函数的数学语义第二个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) 所得的这个函数就是函数h34编程语言递归函数的数学语义为什么选择最小不动点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