计算机科学导论——思想与方法第2版董荣胜全套配套课件 chapter5.ppt

第五章 学科中的数学方法 在计算学科中 采用的数学方法主要是离散数学方 法 本章首先简单介绍数学的基本特征及数学方法的 作用 然后 介绍计算学科中常用的数学概念和术语 包括集合 函数和关系 代数系统 含群 环 格 布尔代数 布尔代数与数字逻辑电路等 字母表 字符串和语言 定义 定理和证明 必要条件和充 分条件 证明方法 递归和迭代 公理化方法等内容 最后 介绍计算学科中的形式化方法 包括形式系 统的组成 基本特点和局限性 形式化方法的定义 以及形式规格和形式验证等内容 5 1 引 言 数学有连续数学和离散数学之分 离散数学源于算术 连 续数学源于几何 自牛顿开创微积分后 连续数学就以微积分 为基础 用连续的观点 对数学进行研究 对自然科学 如物 理学等 的各种现象进行描述 从而成为人们认识客观世界的 一个重要工具 计算学科与物理等学科不同 它的根本问题是 能行性 问 题 能行性 这个根本问题决定了计算机本身的结构和它处 理的对象都是离散型的 而连续型的问题只有经过 离散化 的处理后才能被计算机处理 因此 在计算学科中 采用的数 学方法 主要是离散数学的方法 理论上 凡是能用离散数学 为代表的构造性数学方法描述的问题 当该问题所涉及的论域 为有穷 或虽为无穷但存在有穷表示时 这个问题一定能用计 算机来处理 由于计算机的软硬件都是形式化的产物 因此 很自然的还可以得到一个这样的结论 凡是能被计算机处理的 问题都可以转换为一个数学问题 在对待数学的问题上 计算机科学家与数学家的 侧重点不一样 数学家关心的是 是什么 What is it 的问题 重点放在数学本身的性质上 计算机 科学家则不同 他们不仅要知道 是什么 的问题 更 要解决 怎么做 How to do it 的问题 由于传统数学研究的对象过于抽象 导致对具体 问题 特别是有关计算的本质即字符串变换的具体过 程 关心不够 因此 在计算领域 人们又创造了基 于离散数学的 具体 数学的大量概念和方法 如学科 中的各种形式化方法 本章主要介绍数学的基本特征 数学方法的作用 计算学科中常用的数学概念和术语 集合 函数和 关系 代数系统 字母表 字符串和语言 定义 定 理和证明 必要条件和充分条件 证明方法 递归 和迭代 公理化方法 以及形式化方法等内容 5 2 数学的基本特征 数学是研究现实世界的空间形式和数量关系的一门科学 它具有以下3 个基本特征 1 高度的抽象性 抽象是任何一门科学乃至全部人类思维都具有的特性 然而 数学的 抽象程度大大超过自然科学中一般的抽象 它最大的特点在于抛开现实事 物的物理 化学和生物学等特性 而仅保留其量的关系和空间的形式 2 逻辑的严密性 数学高度的抽象性和逻辑的严密性是紧密相关的 若数学没有逻辑的 严密性 在自身理论中矛盾重重 漏洞百出 那么用数学方法对现实世界 进行抽象就失去了意义 正是由于数学的逻辑严密性 我们在运用数学工 具解决问题时 只有严格遵守形式逻辑的基本法则 充分保证逻辑的可靠 性 才能保证结论的正确性 3 普遍的适用性 数学的高度抽象性决定了它的普遍适用性 数学广泛地应用于其他科 学与技术 甚至人们的日常生活之中 5 3 数学方法的作用 数学方法是指解决数学问题的策略 途径和步骤 数学方法在现代科学技术的发展中已经成为一种必 不可少的认识手段 它在科学技术方法论中的作用主 要表现在以下3个方面 1 为科学技术研究提供简洁精确的形式化语言 人类在日常交往中使用的语言称自然语言 它是 人与人之间进行交流和对现实世界进行描述的一般的 语言工具 而随着科学技术的迅猛发展 对于微观和 宏观世界中存在的复杂的自然规律 只有借助于数学 的形式化语言才能抽象地表达 许多自然科学定律 如牛顿的万有引力定律等 都是用简明的数学公式表 示的 数学模型就是运用数学的形式化语言 在观测 和实验的基础上建立起来的 它有助于人们认识和把 握超出感性经验之外的客观世界 2 为科学技术研究提供数量分析和计算的方法 一门科学要从定性分析发展到定量分析 数学方 法从中起了杠杆的作用 计算机的问世更为科学的定 量分析和理论计算提供了必要条件 使一些过去无法 解决的数学课题找到了解决的可能性 如原子能的研 究和开发 空间技术的发展等都是借助于精确的数值 计算和理论分析进行的 3 为科学技术研究提供逻辑推理的工具 数学的逻辑严密性这一特点使它成为建立一种理 论体系的手段 在这方面最有意义的就是公理化方法 数学逻辑用数学方法研究推理过程 把逻辑推理形 式加以公理化 符号化 为建立和发展科学的理论体 系提供有效的工具 5 4 计算学科中常用的数学概念和术语 5 4 1 集合 1 集合的概念 集合是数学的基本概念 它是构造性数学方法的基础 集合就是一组 无重复的对象的全体 集合中的对象称为集合的元素 如 计算机专业学 生全部必修课程可以组成一个集合 其中的每门课程就是这一集合中的元 素 2 集合的描述方法 通常用大写字母表示集合 用小写字母表示元素 描述集合的方式主 要有以下3种 1 枚举法 列出所有元素的表示方法 如1至5的整数集合可表示为 A 1 2 3 4 5 2 外延表示法 当集合中所列元素的一般形式很明显时 可只列出部 分元素 其他则用省略号表示 如斐波那契数列可表示为 0 1 1 2 3 5 8 13 21 34 3 谓词表示法 用谓词来概括集合中元素的属性 如斐波那契数列可表示为 Fn Fn 2 Fn 1 Fn F0 0 F1 1 n 0 3 集合的运算 集合的基本运算有并 差 交 补和乘积等运算 1 集合的并 设A B为两个任意集合 所有属于A或属于B的元素构成的集合C 称为A和 B的并集 可表示为 C A B x x A x B 求并集的运算称为并 运算 例5 1 若A a b c d B b d e 求集合A和B的并 解 A B a b c d e 2 集合的差 设A B为两个任意集合 所有属于A而不属于B的一切元素构成的集合S 称 为A和B的差集 可表示为 S A B x x A x B 求差集的运算称为差 运算 例5 2 若A a b c d B b d e 求集合A和B的差 解 A B a c 3 集合的交 设A B为两个任意集合 由和的所有相同元素构成的集合C 称为A和B的交 集 可表示为 C A B x x A x B 求交集的运算称为交 运算 例5 3 若A x x 5 B x x 5 x x 1 x 5 x 1 4 集合的补 设I为全集 A为I的任意一子集 I A则为A的补集 记为 可表示为 I A x x I x A 求补集的运算称为补 运算 例5 4 若I x 5 x 5 A x 0 x 1 求 解 I A x 5 x 0 1 x 5 5 集合的乘积 集合A1 A2 An的乘积一般用法国数学家笛卡尔 Rene Descartes 的名字命名 即笛卡尔积 该乘积表示如下 A1 A2 An a1 a2 an ai Ai i 1 2 n A1 A2 An的结果是一个有序n元组的集合 例5 5 若A 1 2 3 B a b 求A B 解 A B 1 a 1 b 2 a 2 b 3 a 3 b 5 4 2 函数和关系 1 函数 函数又称映射 是指把输入转变成输出的运算 该运算也可理解为从 某一 定义域 的对象到某一 值域 的对象的映射 函数是程序设计的基 础 程序定义了计算函数的算法 而定义函数的方法又影响着程序语言 的设计 好的程序设计语言一般都便于函数的计算 设f为一个函数 当输入值为a 时输出值为b 则记作 2 关系 关系是一个谓词 其定义域为k元组的集合 通常的关系为二元关系 其定义域为有序对的集合 在这个集合中 我们说有序对的第一个元 素和第二个元素有关系 如学生选课 如图5 1所示 图5 1 学生选课表 在图5 1中 我们用关系的术语可以说 张三与文学以及哲学课有关 系 选课关系 李四与艺术以及数学课有关系 王五与历史以及文学 课有关系 3 等价关系 在关系中 有一种特殊的关系 即等价关系 它满足以下3个条件 1 自反性 即对集合中的每一个元素a 都有aRa 2 对称性 即对集合中的任意元素a b aRb成立当且仅当bRa成立 3 传递性 即对集合中的任意元素a b c 若aRb和bRc成立 则 aRc一定成立 等价关系的一个重要性质是 集合A上的一个等价关系R可将A划分为 若干个互不相交的子集 称为等价类 例5 6 证明整数N上的模3的同余关系R为等价关系 证明 首先将该关系形式化地表示为 R a b a b N a b 3N 1 自反性证明 对集合中的任何一个元素a N 都有a a 0 3N 2 对称性证明 对集合中的任意元素a b n N 若a b 3n 3N 则有 b a 3 n 3N 3 传递性证明 对集合中的任意元素a b c n m N 若a b 3n b c 3m 两等式左右两边分别相加 则有 a b b c 3n 3m 即a c 3 n m 3N 综上所述 该关系满足自反性 对称性和传递性 因此该关系为等价关系 例5 7 假设某人在唱歌 事件e1 的同时 还可以开车 事件e2 或者 步行 事件e3 但一个人不能同时开车和步行 问 以上反映的并发现象 如用关系来表示时 是否是等价关系 答 以上反映的是一种并发 co 现象 如用关系来表示 则这种并发关 系具有自反性和对称性 即可表示为 e1 co e1 e2 co e2 e3 co e3 以及e1 co e2 或e2 co e1 e1 co e3 或e3 co e1 但不满足 传递性 即 e2 co e1 e1 co e3 不能推出e2 co e3 即不能 在开车的同时 又步行 因此 以上并发关系不是等价关系 另外 常见的等价关系还有 相似 平行 等 而 朋 友 同学关系 等则不是等价关系 5 4 3 代数系统 集合是数学中最基本的概念 从集合出发可以派生 映射 的概念 进 一步 对于一个非空集合A 可以定义 任意一个由A A到A的映射称为 集合A上的一个二元运算 An到A的映射则称为集合A上的一个n元运算 由集合A以及连同若干定义在该集合上的运算f1 f2 fn所组成的 系统称为代数系统 该系统可以形式化的描述为 群 环 格 布尔代数是4种最基本的代数系统 本节主要介绍群和布 尔代数 在此之前 先介绍与代数系统有关的基础知识 运算及其性质 1 运算及其性质 定义1 设A B C为三个集合 映射f A B C称为从笛卡尔积 A B到集合C的代数运算 二元运算的性质有 1 封闭性 设 是定义在集合A上的二元运算 若对于任意的x y A 都有x y A 则称二元运算 在A上是封闭的 2 可交换性 设 是定义在集合A上的二元运算 若对于任意的x y A 都有x y y x 则称该二元运算 是可交换的 3 可结合性 设 是定义在集合A上的二元运算 若对于任意的x y z A 都有 x y c x y z 则称该二元运算 是可结 合的 4 可分配性 设 是定义在集合A上的两个二元运算 若对于 任意的x y z 都有x y z x y x z 且 x y z x z y z 则称运算 对于运算 是可分配的 5 幺元 设 是集合A上的一个二元运算 若存在一个元素el A 对于任意的元素a A 都有el a a 称el是A上关于运算 的左幺元 若存在一个元素er A使得对于所有的a er a 称er是A上关于运算 的右幺元 若存在元素e A 它既是左幺元 又是右幺元 称e为幺元 这时对于任意的a A有e a a e a 6 零元 设 是集合A上的二元运算 若存在一个元素 l A 使 得对于所有的a A 有 l a l 称 l 是A上关于运算 的左零元 若 存在一个元素 r A 使得对于所有的a A 有a r r 称 r是A 上关于运算 的右零元 若存在元素 A 它既是左零元 又是右零元 则称 为零元 这时对于所有的a A 有 a a 7 逆元 设 是集合A上的具有单位元e的。