《离散数学与计算机科学计算机科学导论第四讲幻灯片课件》由会员分享,可在线阅读,更多相关《离散数学与计算机科学计算机科学导论第四讲幻灯片课件(38页珍藏版)》请在金锄头文库上搜索。
1、离散数学与计算机科学计算机科学导论第四讲,计算机科学技术学院 陈意云 0551-63607043 ,课 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M,哪些问题可以由模型M解决;如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,讲 座 提 纲,离散数学和计算机科学的关系 离散数学的特点、与计算机科学的关系 基本知识 偏序集合、最小上界、完全偏序
2、集合、序理论、函数序、函数的单调性和连续性 递归数学函数的不动点语义 函数的不动点、递归函数定义、递归函数定义的解、不动点算子、最小不动点定理 编程语言递归函数的数学语义 最小不动点语义,离散数学和计算机科学的关系,本课程已谈及的相关内容 数理逻辑 经典逻辑、等式逻辑、程序逻辑、类型系统 都包括合式公式、公理、推理规则、演绎推理 集合论 良基关系、良基归纳法,偏序关系(本次课) 代数结构(抽象代数) 常见的抽象数据类型 (表、栈、二叉树等) 是代数 本课程还会谈及 可计算性和算法分析等,离散数学和计算机科学的关系,离散数学和计算机科学的关系 离散数学的研究在20世纪后半叶,由于电子计算机的出现
3、而迅猛发展 离散数学的概念和表示法在研究和描述计算机科学一些分支(如计算机算法、编程语言、自动定理证明、密码学和软件研发)的对象和问题时非常有用 把离散数学的概念用于现实世界的问题时(如运筹学中的问题),计算机实现是十分重要的,离散数学和计算机科学的关系,本科期间的离散数学课程 数理逻辑、图论、代数结构(抽象代数) 使用离散数学知识的课程: 数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等,探讨的问题递归函数的语义,两个C语言写的递归函数(x 0) int f(int x) if(x=0) return 1 else return x*f(x1); int g
4、(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,正好只有一个b
5、B,使得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 =
6、 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
7、 和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,即不同的元素之间无关系,基
8、 本 知 识,偏序集合 有偏序关系 的集合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中任何线性递增链a0
9、a1a2都有最小上界 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.
10、也可以为序,把 图上下颠倒 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
11、) 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,下面的偏序关系图基于把函数值为理解成没有定义,基 本 知 识,连续函数
12、若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, )
13、 例 在实轴闭区间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. 抽象表示法( 抽象
14、表达式是表达式的一种) 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
15、= 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. 不动点可能不唯一,取哪个不动点作为语义 不同场合有不同选择:最小或最大不动点 (注:不动点集上的偏序关系:函数包含序) 本讲座内容需要最小不动点,第九
16、讲用到最大不动点,递归数学函数的不动点语义,不动点算子 不动点算子是一簇函数,其类型是 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