课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决；如何 比较模型的表达能力 本讲座讨论递归函数的语 2.程序理论关心的问题义，了解离散数学的重要性 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、 程序设计、 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题，解决该类问题需多少资源
课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源2 本讲座讨论递归函数的语 义, 了解离散数学的重要性
讲座提纲 离散数学和计算机科学的关系 -离散数学的特点、与计算机科学的关系 基本知识 偏序集合、最小上界、完全偏序集合、函数序、 函数的单调性和连续性 递归函数的定义式的求解 函数的不动点、递归函数定义、递归函数定义的 解、不动点算子、最小不动点定理 编程语言递归函数的数学语义 -最小不动点语义 3
讲 座 提 纲 • 离散数学和计算机科学的关系 – 离散数学的特点、与计算机科学的关系 • 基本知识 – 偏序集合、最小上界、完全偏序集合、函数序、 函数的单调性和连续性 • 递归函数的定义式的求解 – 函数的不动点、递归函数定义、递归函数定义的 解、不动点算子、最小不动点定理 • 编程语言递归函数的数学语义 – 最小不动点语义 3
离散数学和计算机科学的关系 本课程已谈及的相关内容 数理逻辑 ·经典逻辑、等式逻辑、 程序逻辑、类型系统 ·都包括合式公式、公理、推理规则、演绎推理 集合论 良基关系、良基归纳法，偏序关系（本次课) 代数结构（抽象代数） 常见的抽象数据类型（表、栈、二叉树等）是代数 本课程还会介绍 可计算性和算法分析等
离散数学和计算机科学的关系 • 本课程已谈及的相关内容 – 数理逻辑 • 经典逻辑、等式逻辑、程序逻辑、类型系统 • 都包括合式公式、公理、推理规则、演绎推理 – 集合论 良基关系、良基归纳法，偏序关系（本次课） – 代数结构（抽象代数） 常见的抽象数据类型 (表、栈、二叉树等) 是代数 • 本课程还会介绍 – 可计算性和算法分析等 4
离散数学和计算机科学的关系 离散数学的特点 离散数学是数学的几个分支的总称，研究基于离 散而不是连续的数学结构 与光滑变化的实数不同，离散数学的研究对象， 例如整数、图和逻辑中的命题，都包含有区别和 分离的值，且所包含的值并非光滑变化 离散数学被视为处理可数集合（与自然数集有相 同基数的集合)的数学分支 离散数学无准确且普遍接受的定义，它经常被定 义为不包含连续变化量及相关概念的数学，也用 包含什么内容的方式来定义
离散数学和计算机科学的关系 • 离散数学的特点 – 离散数学是数学的几个分支的总称，研究基于离 散而不是连续的数学结构 – 与光滑变化的实数不同，离散数学的研究对象， 例如整数、图和逻辑中的命题，都包含有区别和 分离的值，且所包含的值并非光滑变化 – 离散数学被视为处理可数集合（与自然数集有相 同基数的集合）的数学分支 – 离散数学无准确且普遍接受的定义，它经常被定 义为不包含连续变化量及相关概念的数学，也用 包含什么内容的方式来定义 5
离散数学和计算机科学的关系 离散数学和计算机科学的关系 离散数学的研究在20世纪后半叶，由于电子计算 机的出现而迅猛发展 离散数学的概念和表示法在研究和描述计算机科 学一些分支的对象和问题时非常有用，如计算机 算法、编程语言、自动定理证明、密码学和软件 研发 把离散数学的概念用于现实世界的问题时（如运 筹学中的问题)，计算机实现是十分重要的
离散数学和计算机科学的关系 • 离散数学和计算机科学的关系 – 离散数学的研究在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) 若x是偶数，结 if (x=-0)return 1; 果为1；否则计算 else if(x==l)return g③)； 不终止 else return g(x-2); 一非形式地，这两个C函数的语义都能描述 -本讲座介绍，如何用数学语言给出它们的语义？
探讨的问题——递归函数的语义 • 两个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》 -x) ifx=0 then 1 else xx fx-1) -g(c) ifx =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),…}
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（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，并且对 任何aA，正好只有一个bB，使得a, bR – 上述第一个定义代表阶乘函数 { 0, 1, 1, 1, 2, 2, 3, 6, 4, 24, 5, 120, … } 9
探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -x) ifx=0 then 1 else xx fx-1) -g(c) ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 它们是递归定义式，代表什么函数？ 函数：集合A到集合B的一种二元关系R,并且对 任何a∈A,正好只有一个b∈B,使得(a,b》∈R 上述第二个定义代表什么函数？ 注：x是奇数时，计算g(x)的演算不终止
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（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，并且对 任何aA，正好只有一个bB，使得a, bR – 上述第二个定义代表什么函数？ 注：x是奇数时，计算g(x)的演算不终止 10
探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -x) ifx=0 then 1 else xx fx-1) -g(c) ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 它们是递归定义式，代表什么函数？ 函数：集合A到集合B的一种二元关系R,并且对 任何a∈A,正好只有一个beB,使得(a,b》∈R 偏函数(partial function,部分函数)：..最多只 有一个b∈B 注：需要这个概念来回答上述问题
探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（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，并且对 任何aA，正好只有一个bB，使得a, bR – 偏函数（partial function, 部分函数）：…最多只 有一个bB … 注：需要这个概念来回答上述问题 11