离散数学与计算机科学计算机科学导论第四讲市公开课一等奖百校联赛特等奖课件.pptx

离散数学与计算机科学离散数学与计算机科学计算机科学导论第四讲计算机科学导论第四讲计算机科学技术学院计算机科学技术学院陈意云陈意云0551-第1页课课 程程 内内 容容课程内容课程内容围绕学科理论体系中模型理论围绕学科理论体系中模型理论,程序理论和计算理论程序理论和计算理论1.模型理论关心问题模型理论关心问题 给定模型给定模型M，哪些问题能够由模型，哪些问题能够由模型M处理；怎样处理；怎样比较模型表示能力比较模型表示能力2.程序理论关心问题程序理论关心问题给定模型给定模型M，怎样用模型，怎样用模型M处理问题处理问题包含程序设计范型、包含程序设计范型、程序设计语言程序设计语言、程序设计、程序设计、形式语义形式语义、类型论、程序验证、程序分析等、类型论、程序验证、程序分析等3.计算理论关心问题计算理论关心问题给定模型给定模型M和一类问题和一类问题,处理该类问题需多少资源处理该类问题需多少资源第2页讲讲 座座 提提 纲纲离散数学和计算机科学关系离散数学和计算机科学关系离散数学特点、与计算机科学关系离散数学特点、与计算机科学关系基本知识基本知识偏序集合、偏序集合、最小上界、完全偏序集合最小上界、完全偏序集合、序理论、序理论、函数序、函数序、函数单调性和连续性函数单调性和连续性递归数学函数不动点语义递归数学函数不动点语义函数不动点、递归函数定义、递归函数定义解、函数不动点、递归函数定义、递归函数定义解、不动点算子、最小不动点定理不动点算子、最小不动点定理编程语言递归函数编程语言递归函数数学语义数学语义最小不动点语义最小不动点语义第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);非形式地描述，这两个非形式地描述，这两个C函数语义都能讲清楚函数语义都能讲清楚本讲座介绍，怎样用数学语言给出它们语义？本讲座介绍，怎样用数学语言给出它们语义？若若x是偶数，结是偶数，结果为果为1；不然计算不；不然计算不终止终止第8页探讨问题探讨问题递归函数语义递归函数语义对应两个递归数学函数定义（对应两个递归数学函数定义（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,b R例：阶乘函数例：阶乘函数 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(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,b R偏函数（部分函数）：偏函数（部分函数）：最多只有一个最多只有一个b B 第10页探讨问题探讨问题递归函数语义递归函数语义对应两个递归数学函数定义（对应两个递归数学函数定义（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，即不一样元素之间无关系，即不一样元素之间无关系 第13页基基 本本 知知 识识偏序集合偏序集合有偏序关系有偏序关系 集合集合D，记为，记为 D,1.上界上界若若 D,，则子集，则子集S D上界上界是元素是元素x D，含有含有性质：性质：y:S.y x2.最小上界最小上界S一一 个上界，它小于等于个上界，它小于等于S任何其它上界任何其它上界3.线性序线性序 x,y:S.x y y x 第14页基基 本本 知知 识识例例 偏序集合偏序集合a0,b0,a1,b1,a2,b2,，其中对任意其中对任意i j都有都有ai aj,bj而且而且bi aj,bj 两个线性序两个线性序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，比如，全部比如，全部小于小于 有理数最小上界是无理数有理数最小上界是无理数 2第16页基基 本本 知知 识识完全偏序集合完全偏序集合4.有底元（也叫最小元有底元（也叫最小元）CPO D,存在元素存在元素a，使得对使得对D任何元素任何元素b都有都有a b5.D上底元上底元用用 或或 D表示表示6.例例为自然数集自然数集N N增加增加底元底元，并定义偏序，并定义偏序关系如图，则关系如图，则N N 是有底元是有底元CPO称称为提升集合提升集合01234 CPO N N 图形表示图形表示第17页基基 本本 知知 识识例例以集合以集合关系关系为序序即即是是两个集合最小两个集合最小上界就是它上界就是它们并集并集即即x y就是就是x y1.也能够也能够为序，把为序，把图上下颠倒图上下颠倒2.能够类似地定义下界、能够类似地定义下界、最大下界和顶元最大下界和顶元(最大元最大元)等等d1d2d3d1,d2d1,d3d2,d3d1,d2,d3()()第18页基基 本本 知知 识识序理序理论研究各种二元关系研究各种二元关系数学理数学理论格（格（lattice）在离散数学中在离散数学中有有顶元和底元元和底元 D,称为格称为格有有顶元或底元元或底元 D,称为半格称为半格d1d2d3d1,d2d1,d3d2,d3d1,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,2 0,1,1,1 0,1 0,5.第20页基基 本本 知知 识识单调函数单调函数 若若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(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,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第23页基基 本本 知知 识识连续函数连续函数 若若D 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时时，则通常计算意义下连续函数依然连续则通常计算意义下连续函数依然连续 任何任何CPO上常函数是平凡地连续上常函数是平凡地连续 若若D D是离散序，则是离散序，则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)=x+1 x: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=6第26页递归数学函数不动点语义递归数学函数不动点语义递归定义解与对应函数不动点主要联络递归定义解与对应函数不动点主要联络递归定义递归定义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(x 1)对应函数：对应函数：F f:nat nat.y:nat.if x=0 then 1 else x f(x 1)阶乘函数是阶乘函数是F不动点不动点第27页递归数学函数不动点语义递归数学函数不动点语义不动点语义不动点语义函数函数 f:.M不动不动点作为点作为递归定义递归定义f(x:D)=M语义语义1.怎样计算得到不动点怎样计算得到不动点2.不动点可能不唯一，取哪个不动点作为语义不动点可能不唯一，取哪个不动点作为语义不一样场所有不一样选择：最小或最大不动点不一样场所有不一样选择：最小或最大不动点（注：不动点集上偏序关系：函数包含序）（注：不动点集上偏序关系：函数包含序）本讲座内容需要最小不动点，第九讲用到最大不本讲座内容需要最小不动点，第九讲用到最大不动点动点第28页递归数学函数不动点语义递归数学函数不动点语义不动点算子不动点算子不动点算子是一簇函数，其类型是不动点算子是一簇函数，其类型是 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(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)(n-1)从这里已经知道从这里已经知道0阶乘等于阶乘等于1若若n 若若n值给定，则对值给定，则对fix F有限步展开可得有限步展开可得n阶乘阶乘第30页递归数学函数不动点语义递归数学函数不动点语义最小不动点定理最小不动点定理若若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最小上界相同最小上界相同,所以所以f(a)=a 再证再证a是最小不动点（略）是最小不动点（略）最终证实最终证实fix 连续（略）连续（略）第31页编程语言递归函数数学语义编程语言递归函数数学语义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()|n 0=,0,0!,0,0!,1,1!,0,0!,1,1!,2,2!,=阶乘函数阶乘函数 第32页编程语言递归函数数学语义编程语言递归函数数学语义第二个第二个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)=Fn()|n 0=,0,1,0,1,2,1,0,1,2,1,4,1,=f(x)=1（x为偶数）为偶数）第33页编程语言递归函数数学语义编程语言递归函数数学语义第二个第二个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 2)h =x:nat=if x=0 then 1 else (if x=1 then h(3)else h(x 2)所得这个函数就是函数所得这个函数就是函数h第34页编程语言递归函数数学语义编程语言递归函数数学语义为何选择最小不动点为何选择最小不动点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)=1（x为偶数）为偶数）最小不动点特点：最小不动点特点：是定义得最少不动点是定义得最少不动点仅包含从递归定义能演绎出来信息，没有来自对仅包含从递归定义能演绎出来信息，没有来自对对应递归方程任何对应递归方程任何“个人臆想个人臆想”对某个变元没有定义，意味着计算不终止对某个变元没有定义，意味着计算不终止第35页编程语言递归函数数学语义编程语言递归函数数学语义实分析中不动点实分析中不动点求解实数方程求解实数方程 x=1+1/x经惯用迭代方法求解经惯用迭代方法求解 x:R.1+1/x(连续函数连续函数)0 5(迭代初值迭代初值),xi (xi 1),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，即上述连续函数不动点，即上述连续函数不动点第36页小小 结结本讲座小结本讲座小结概述离散数学与计算机科学关系。概述离散数学与计算机科学关系。并并以计算阶以计算阶乘递归程序为例，介绍完全偏序集合及其上函数乘递归程序为例，介绍完全偏序集合及其上函数单调性单调性、连续性连续性、不动点等概念是怎样用于程序不动点等概念是怎样用于程序语义解释语义解释偏序理论在计算机科学中应用偏序理论在计算机科学中应用程序理论各个方面，如形式语义、类型论、程程序理论各个方面，如形式语义、类型论、程序分析、程序优化、程序验证都离不开偏序理论序分析、程序优化、程序验证都离不开偏序理论在计算机科学很多其它方面也都包括偏序在计算机科学很多其它方面也都包括偏序这部分内容在这部分内容在“代数结构代数结构”课程中课程中第37页小小 结结离散数学是很多专业课程先行课程离散数学是很多专业课程先行课程数数据据结结构构、操操作作系系统统、编编译译技技术术、人人工工智智能能、数数据库、算法设计与分析、程序设计语言基础等据库、算法设计与分析、程序设计语言基础等离散数学发展方向离散数学发展方向离散数学本身研究方面进展伴随计算机科学离散数学本身研究方面进展伴随计算机科学发展而深入，比如在下述方面都有很多新结果，发展而深入，比如在下述方面都有很多新结果，也有值得继续研究问题也有值得继续研究问题研究智能推理非经典逻辑研究智能推理非经典逻辑领域专用自动定理证实领域专用自动定理证实代数结构深入探讨代数结构深入探讨图论与群论相互结合理论图论与群论相互结合理论第38页