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

离散数学与计算机科学 计算机科学导论第四讲,计算机科学技术学院 陈意云 0551-63607043 yiyunustc.edu.cn,课 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 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 z 2. D上的二元关系的定义 x y 当且仅当 x y x y 3. 整数上小于等于和小于关系分别是和的实例 4. 离散序 x y当且仅当x y，即不同的元素之间无关系,基 本 知 识,偏序集合 有偏序关系 的集合D，记为D, 1. 上界 若D, ，则子集SD的上界是元素xD，具有性质： y:S. y x 2. 最小上界 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 b 5. D上的底元用 或D表示 6. 例 为自然数集N增加 底元，并定义偏序 关系如图，则N 是有底元的CPO 称为提升集合,基 本 知 识,例 以集合关系为序 即是 两个集合的最小 上界就是它们的并集 即x y就是x y 1. 也可以为序，把 图上下颠倒 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 true f1 true f7 true false f2 false f8 false false f3 true f9 true true true f4 false f10 false false false f5 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 +1 x:nat. x +1 g(x : nat) = 10 x:nat. 10 f 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，即上述连续函数的不动点,小 结,本讲座小结 概述离散数学与计算机科学的关系。并以计算阶 乘的递归程序为例，介绍完全偏序集合及其上函数 的单调性、连续性、不动点等概念是怎样用于程序 的语义解释的 偏序理论在计算机科学中的应用 程序理论的各个方面，如形式语义、类型论、程 序分析、程序优化、程序验证都离不开偏序理论 在计算机科学的很多其他方面也都涉及偏序 这部分内容在“代数结构”课程中,小 结,离散数学是很多专业课程的先行课程 数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等 离散数学的发展方向 离散数学自身研究方面的进展随着计算机科学的 发展而深入，例如在下述方面都有很多的新成果， 也有值得继续研究的问题 研究智能推理的非经典逻辑 领域专用的自动定理证明 代数结构的深入探讨 图论与群论相互结合的理论,