离散数学与计算机科学计算机科学导论第四讲,计算机科学技术学院 陈意云 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 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 +1x: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 i