计算科学内容和方法

1、第五章 计算科学内容和方法,第5章计算学科的内容 与方法,5.1 计算科学的基本问题,能行性,能行性：什么能（有效地）自动进行，什么不能（有效地）自动进行。 “能行性”这个计算学科的根本问题决定了计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型的问题也必须在转化为离散型问题以后才能被计算机处理。 例如，计算定积分就是把它变成离散量，再用分段求和的方法来处理的,计算科学的发展主线,具体来说，有三大问题： 1）计算的平台和环境问题（计算模型问题） 2）计算过程的能行操作和效率问题（算法问题） 3）计算的正确性问题（语义学问题） 计算机研究的目标是:拓展和提高计算机的应用领域和应用水平。

2、围绕学科的三个基本问题使学科的发展形成了三条相对独立的主线，形成了许多相对独立的分支学科和研究方向。 不同时期，围绕着学科的一些重大问题和基本问题，若干方向便构成了所谓的主流方向，由主流方向又形成了学科的发展主线,计算的平台与环境问题,计算的平台与环境问题是指描述计算问题的计算模型，或者实际制造出来的针对各种待处理问题特点和要求的自动计算机器。 不难看出，理论研究中提出的各种计算模型，各种实际的计算机系统，各种高级程序设计语言，各种计算机体系结构，各种软件开发工具与环境，编译程序与操作系统，数据库系统等都是围绕这一基本问题发展而来的，其内容实质可归结为计算的模型问题，也就是说，这个基本问题实际

3、上关心的是计算问题在理论上是否能行的问题,计算过程的能行操作与效率问题,含义是：当一个问题在判明为可计算的性质后，从具体解决这个问题着眼，必须按照能行可构造的特点与要求，给出实际解决该问题的一步一步的具体操作，同时还必须确保这样一种过程的开销成本是我们能够承受的。 相关的分支学科有：数值与非数值计算方法，算法设计与分析，结构化程序设计技术，密码学与快速算法，演化计算，程序设计方法学，自动布线，RISC技术，人工智能的逻辑基础等,计算的正确性问题,计算的正确性是指：一个计算问题在给出了能行操作序列并解决了其效率问题之后，必须确保计算的正确性，否则，计算是无意义的，也是容易产生不利影响的。 这一基

4、本问题相关的分支学科有：算法理论，程序设计方法学，程序设计语言的语义学，进程代数与分布式事件代数，程序测试技术，电路测试技术，软件工程技术，计算语言学，容错理论与技术，Petri网理论，CSP理论，CCS理论，分布式网络协议等。 今天，计算的正确性问题常常归结为各种语言的语义问题,计算科学的三大基本问题,计算学科的三个基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的问题。 循着这一线索，我们不难看出，整个学科正是在围绕这些基本问题和不同时期重大问题而展开的研究与发展中形成了学科的发展主线与主流方向,第5章计算学科的内容 与方法,5.2 计算科学内容的

5、三个层面,计算科学的应用层,包括人工智能应用与系统，信息、管理与决策系统，移动计算、计算可视化、科学计算等计算机应用的各个方向。其中，人工智能应用与系统涵盖人工智能，机器人，神经元计算，知识工程，自然语言处理与机器翻译，自动推理等方向；信息、管理与决策系统涵盖数据库设计与数据管理技术，数据表示与存储（包括多媒体技术），数据与信息检索，管理信息系统，计算机辅助系统，决策系统等方向；计算可视化涵盖计算机图形学，计算几何，模式识别与图像处理等方向,计算科学的专业基础层,它是为应用层提供技术和环境的一个层面，包括软件开发方法学，计算机网络与通信技术，程序设计科学，计算机体系结构，电子计算机系统基础。其

6、中，软件开发方法学涵盖顺序、并行与分布式软件开发方法学，如软件工程技术，软件开发工具和环境等方向；计算机网络与通信技术涵盖计算机网络互联技术，数据通信技术，以及信息保密与安全技术等方向；程序设计科学涵盖数据结构技术，数值与符号计算，算法设计与分析，程序设计语言，程序设计语言的文法与语义，程序设计方法学，程序理论等方向；电子计算机系统基础涵盖数字逻辑技术，计算机组成原理，故障诊断与器件测试技术，操作系统，编译技术，数据库系统实现技术，容错技术等方向,计算科学的基础层,它包括计算的数学理论，高等逻辑等内容。其中，计算的数学理论涵盖可计算性（递归论）与计算复杂性理论，形式语言与自动机理论，形式语义学

7、（主要指代数语义，公理语义等），Petri网理论等方向；高等逻辑涵盖模型论，各种非经典逻辑与公理集合论等方向。 支撑这三个层面的是计算科学这一学科的理工科基础科目，包括物理学（主要是电子技术科学）、基础数学（含离散数学）等,移动计算与全球定位 计算机自动控制 计算机辅助制造 计算机集成制造系统 计算 机器人 计算可视化与虚拟现实 数据与信息检索 计算机创作 计算机网络应用软件 科学 科学计算 多媒体信息系统 计算机辅助设计 信息、管理与决策系统 自然语言处理 应用 模式识别与图像处理技术 计算机图形学 计算几何 人工智能与知识工程 层 数据表示与存储 网络与开放系统互联标准 软件测试技术 人机

8、工程学（人机界面） 计算 软件开发方法学: 软件工程技术、程序设计方法学、软件开发工具和环境、软件开发规范 科学 编码理论 密码学 计算机体系结构 程序理论 数据表示理论与数据库系统 专业 电子计算机系统基础 计算机接口与通信 计算机网络与数据通信技术 自动推理 基础 故障诊断与器件测试技术 容错技术 汇编技术 操作系统 高级语言 程序设计 层 数字系统设计 符号计算与计算机代数 数据结构技术 算法设计与分析 编译与解释技术 计算 控制论基础 数字系统设计基础 信息论基础 网论（Petri网理论等） 形式语义学 科学 框图理论 算法理论 可计算性（递归论） 计算复杂性 程序设计语言理论 基础

9、计算模型（各种抽象机） 模型论与非经典逻辑 公理集合论 形式语言与自动机 层 数学 光电子技术基础 电路基础 电子线路基础 数字与模拟电路基础 数值分析与计算方法 与 大学物理学 函数论基础（复变函数、演算、泛函分析等） 泛代数 概率与数理统计 物理 常微分方程 偏微分方程 集合论与图论 组合数学 抽象代数 数理逻辑基础 层 空间解析几何 数学分析 布尔代数 高等代数 数论,第5章计算学科的内容 与方法,5.3 计算科学的发展主线,计算科学的发展主线,在计算机基础研究、应用基础研究和技术开发与应用的研究中，计算学科逐步发展形成了三条相对独立的主线： 1）计算模型与计算机系统 2）计算模型、语言

10、与软件开发方法学 3）应用数学与计算机应用,第5章计算学科的内容 与方法,5.4 计算科学的分类与分支学科简介,构造性数学基础,对数学基础问题的讨论促进了构造性数学的产生和发展，产生了数学发展史上著名的三大逻辑学派：逻辑主义学派，形式主义学派和直觉主义逻辑学派。 尽管数学科学的发展在计算科学的发展中得到广泛的应用，但是与计算科学在科学方法论上形成一致的是构造性数学。这是直觉主义所以受到计算科学家欢迎的原因。 可以这么说：历史上，对计算的能行性和可构造性研究的最著名的产物要数图灵机。如果没有19世纪末20世纪初关于数学基础问题的讨论，没有直觉主义学派对数学的贡献，计算科学可能要推迟出现,构造性数

11、学基础,数理逻辑与抽象代数是计算科学最重要的两项数学基础，它们的研究思想和研究方法在计算科学许多有深度的领域得到了最广泛的应用。 数理逻辑是研究推理的科学，特别，在过去主要是研究数学中推理的科学。数理逻辑与哲学有着密切的联系，其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了数理逻辑的研究内容,构造性数学基础,在计算科学的研究和发展中，应该接受什么样的数学理论呢？罗宾逊认为，如果大家不对一个数学理论的可解释性提出非议，那么，有几条通常被看作是基本的可接受性的准则： (1) 一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作是可接受的； (2) 一个数学理论是可接受的，要是它能够作为自然科学

12、的一个基础； (3) 一个数学理论要由美学标准来判断，比如它的美或内在的适当性。 (3)中提及的标准，迄今还无从进行任何科学的研究,构造性数学基础,对于(1)中提出的标准，足可以使我们认识到数理逻辑对计算科学的重要性。 众所周知，在计算科学的各个分支学科中，使用了各种数学理论，包括数理逻辑。要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证该数学理论对客观世界或应用范畴的（语义）解释是无矛盾的，用逻辑学的术语来说就是该数学理论必须存在模型。这在方法论上是靠逻辑学中的模型理论提供的。而要学习模型论的内容，仅有命题演算、一阶谓词演算的知识是不够的。 对于(2)中提及的标准，读者在今后的学习中

13、会逐步体会到其涵义,构造性数学基础,现在，有经验和成熟的计算科学家都知道，除了数理逻辑以外，对计算科学最重要的数学分支是代数，特别是抽象代数。 在计算科学中，代数方法被广泛应用于许多分支学科。例如，可计算性与计算复杂性，形式语言与自动机理论，密码学，算法理论，数据表示理论，网络与通信理论，Petri网理论，程序理论，形式语义学等许多方面都离不开代数,计算的数学理论,所谓计算的数学理论是指一切关于能行性问题的数学理论的总和。也有一种更具体的定义是指一切关于计算与计算模型问题的数学理论的总和。 计算理论广义的可以看作同计算的数学理论，狭义的主要指算法理论、可计算理论、计算复杂性理论,计算机组成原理

14、、器件与体系结构,计算机组成原理与设计是计算机发展的一个主流方向。这一方向的主要任务是根据各种计算模型研究计算机的工作原理，并按照器件、设备和工艺条件设计、制造具体的计算机。 早期计算机的设计是建立在分离元器件的基础之上，这方面的工作更多的是集中在对各个部件微观的精细分析，后来，随着集成电路技术的进步，工作的重点已开始转到计算机的组织结构。 集成电路对电路和功能部件的高集成度和计算机设计与软件开发之间建立的密切关系，使这一方向的发展逐步形成了一个新的计算机体系结构方向,计算机应用基础,要开展各个领域的各种计算机具体应用，就必须首先要有一些计算机应用基础知识。对计算科学专业的学生来说，计算机应用

15、基础知识包括算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术等,计算机基本应用技术,我们知道，计算机应用和计算机基本应用技术是一回事，涉及到的分支学科很多。然而，从计算机应用的定义和科学方法论的角度出发，大致可以将计算机应用分支学科的范畴确定下来，即它所研究的内容在方法和技术上为计算机在各个领域的具体应用奠定了基础,软件基础,软件是计算科学一个较大的学科门类，包括众多的分支学科方向，主要有高级程序设计语言、数据结构理论、程序设计原理、编译程序原理与编译系统实现技术、数据库原理与数据库管理系统、操作系统原理与实现技术、软件工程技术、程序设计方法学、各种应用软件等,新一代计算机体系结构

16、与软件开发方法学,所谓新一代计算机体系结构是相对于过去的体系结构而言的。目前，对这类体系结构的研究内容很多，主要是各种新型并行计算机的体系结构、集群式计算机体系结构，体系结构的可扩展性、任务级并性、指令级并行性、动态可改变结构等方面的内容，也有一些内容还不成熟，正在发展之中。 高起点的软件开发方法学的主要基础是新一代计算机体系结构、高等逻辑、形式语义学、计算模型理论以及算法基础。这实际上也指出了新一代计算机体系结构与软件开发方法学（包括并行与分布式计算机系统、人工智能计算机系统、并行与分布式软件开发方法学等）是计算科学界需要长期努力奋斗的工作重点,第5章计算学科的内容 与方法,5.5 计算学科

17、中的数学方法 5.5.1 数学的基本特征,数学方法,是指解决数学问题的策略、途径和步骤，它是计算学科中最根本的研究方法。 理论上，凡能被计算机处理的问题均可以转换为一个数学问题，换言之，所有能被计算机处理的问题均可以用数学方法解决； 反之，凡能以离散数学为代表的构造性数学方法描述的问题，当该问题所涉及的论域为有穷，或虽为无穷但存在有穷表示时，这个问题也一定能用计算机来处理,数学的基本特征,高度的抽象性 ：量的关系和空间的形式 逻辑的严密性 ：严格遵守形式逻辑的基本法则，充分保证逻辑的可靠性，才能保证结论的正确性。 普遍的适用性 ：数学的高度抽象性决定了它的普遍适用性,数学方法的作用,为科学技术

18、研究提供简洁精确的形式化语言 为科学技术研究提供数量分析和计算的方法 为科学技术研究提供了逻辑推理的工具,5.5计算学科中的数学 方法,5.5.2 为什么说数理逻辑和代数是计算科学的主要基础,为什么说数理逻辑和代数是计算科学的主要基础,1) 首先，从计算模型和可计算性的研究来看，可计算函数和可计算谓词（一种能够能行判定其真值的断言或逻辑公式）是等价的，相互之间可以转化。这就是说，计算可以用函数演算来表达，也可以用逻辑系统来表达。作为计算模型可以计算的函数恰好与可计算谓词是等价的，而且，数理逻辑本身的研究也广泛使用代数方法，同时，逻辑系统又能通过自身的无矛盾性保证这样一种计算模型是合理的。由此可

19、见，作为一种数学形式系统，图林机及其与它等价的计算模型的逻辑基础是坚实的,为什么说数理逻辑和代数是计算科学的主要基础,2) 实际计算机的设计与制造中，使用数字逻辑技术实现计算机的各种运算的理论基础是代数和布尔代数。布尔代数只是在形式演算方面使用了代数的方法，其内容的实质仍然是逻辑。依靠代数操作实现的指令系统具有（原始）递归性，而数字逻辑技术和集成电路技术只是计算机系统的一种产品的技术形式,为什么说数理逻辑和代数是计算科学的主要基础,3) 从计算机程序设计语言方面考察，语言的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源于数理逻辑和代数。程序

20、设计语言中的许多机制和方法，如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和逻辑的方法。这就是说，数理逻辑和代数为语言学提供了方法论的基础,为什么说数理逻辑和代数是计算科学的主要基础,4) 在计算机体系结构的研究中，象容错计算机系统、Transputer计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算模型等都直接或间接与逻辑与代数密不可分。如容错计算机的重要基础之一是多值逻辑，Transputer计算机的理论基础是CSP理论，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及其计算模型主要采用逻辑与代数的方法

21、,为什么说数理逻辑和代数是计算科学的主要基础,5) 从计算机各种应用的程序设计方面考察，任何一个可在存储程序式电子数字计算机上运行的程序，其对应的计算方法首先都必须是构造性的，数据表示必须离散化，计算操作必须使用逻辑或代数的方法进行，这些，都应体现在算法和程序之中。此外，到现在为止，程序的语义及其正确性的理论基础仍然是数理逻辑，或进一步的模型论,为什么说数理逻辑和代数是计算科学的主要基础,高等代数和一般抽象代数只解决了个体对象为简单个体的论域上的大量运算问题，但是对具有结构特征和属性成分的复杂个体的论域上的运算问题，表达和处理是不方便的，常常是有困难的。针对这类对象的运算操作及其正确性等语义学

22、问题，有必要发展泛代数和高阶逻辑理论,5.5计算学科中的数学 方法,5.5.3 计算学科中常用的数学 概念和术语,集合,构造性数学方法的基础。 集合就是一组无重复的对象的全体。 集合中的对象称为集合的元素。 如：计算机专业学生全部必修课程可以组成一个集合，其中的每门课程就是这一集合中的元素,函数,函数又称映射，是指把输入转变成输出的运算，该运算也可理解为从某一“定义域”的对象到某一“值域”的对象的映射。函数是程序设计的基础，程序定义了计算函数的算法，而定义函数的方法又影响着程序语言的设计，好的程序设计语言一般都便于函数的计算。 设f为一个函数，当输入值为a时输出值为b，则记作,关系,关系是一个

23、谓词，其定义域为k元组的集合。通常的关系为二元关系，其定义域为有序对的集合，在这个集合中，我们说有序对的第一个元素和第二个元素有关系。如学生选课 学生 课程 成绩 张三 文学 90 张三 哲学 95 李四 数学 80 李四 艺术 85 王五 历史 92 王五 文学 88,等价关系,在关系中，有一种特殊的关系，即等价关系，它满足以下3个条件： 自反性，即对集合中的每一个元素a，都有aRa； 对称性，即对集合中的任意元素a，b，aRb成立当且仅当bRa成立； 传递性，即对集合中的任意元素a，b，c，若aRb和bRc成立，则aRc一定成立。 等价关系的一个重要性质是：集合A上的一个等价关系R可将A划

24、分为若干个互不相交的子集，称为等价类,例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，即不能在开车的同时，又步行。 因此，以上并发关系不是等价关系,

25、定义、定理和证明是数学的核心，也是计算学科理论形态的核心内容。其中，定义是蕴含在公理系统之中的概念和命题；定理是被证明为真的数学命题；证明是为使人们确信一个命题是真的而作的一种逻辑论证。 例5.8 在欧氏几何中，平面角的定义为：平面角是在一平面内，但不在一直线上的两条相交线的相互倾斜度；等腰三角形的定理为：两边相等的三角形为等腰三角形,5.5计算学科中的数学 方法,5.5.3 证明方法,直接证明,假定p为真，通过使用公理或已证明的定理以及正确的推理规则证明q也为真，以此证明蕴含式pq为真。这种证明方法为直接证明法。 例5.9 用直接证明法证明“若p是偶数，则p2是偶数”。 证明：假定p是偶数为

26、真，设p=2k（k为整数）。由此可得，p2=2（2k2）。因此，p2是偶数（它是一个整数的2倍,间接证明,因为蕴含式pq与其逆否命题qp等价，因此可以通过证明qp来证明蕴含式pq为真。这种证明方法为间接证明法。 例5.10 用间接证明法证明“若p2是偶数，则p是偶数”。 证明：假定此蕴含式后件为假，即假定p是奇数。则对某个整数k来说有p=2k+1。由此可得p2=4k2+4k+1=2（2k2+2k）+1，因此，p2是奇数（它是一个整数的2倍加1）。因为对这个蕴含式后件的否定蕴含着前件为假，因此该蕴含式为真,首先假定一个与原命题相反的命题成立，然后通过正确的推理得出与已知（或假设）条件、公理、已证

27、过的定理等相互矛盾或自相矛盾的结果，以此证明原命题正确。这种证明方法就是反证法，也称归谬法，是一种常用的数学证明方法。 例5.11 证 是无理数,归纳法的定义,所谓归纳法，是指从特殊推理出一般的一种证明方法。归纳法可分为不完全归纳法、完全归纳法和数学归纳法。 2不完全归纳法 不完全归纳法是根据部分特殊情况作出推理的一种方法，该方法多用于无穷对象的论证，然而，论证的结果不一定正确。因此，不完全归纳法不能作为严格的证明方法。 3完全归纳法 完全归纳法也称穷举法，它是对命题中存在的所有特殊情况进行考虑的一种方法，用该方法论证的结果是正确的，然而，它只能用于“有限”对象的论证,数学归纳法的形式化定义,

28、根据数学归纳法的原理，可以对数学归纳法形式化地定义为： P(1)()(P(n)P(n+1)P(n) 例5.12 求证命题P(n)：“从1开始连续n个奇数之和是n的平方”，即公式 1+3+5+（2n1）=n2成立,证明,归纳基础：当n=1时，等式成立，即1=12 归纳步骤： 设对任意k1，P(k)成立，即： 1+3+5+（2K1）=K2 而 1+3+5+(2K1)+(2(K+1)1) = K2+2K+1=(K+1)2 则当P(k)成立时，P(K+1)也成立，根据数学归纳法，该命题得证,构造性证明,构造性证明通过找出一个使得命题P(a)为真的元素a，从而完成该函数值的存在性证明称为构造性证明。 构

29、造性证明方法是计算科学中广泛使用的一种证明方法，本章Armstrong公理系统的完备性证明就采用了构造性的证明方法,5.5计算学科中的数学 方法,5.5.5 递归和迭代 (构造性方法,递归及其有关概念,很多序列项常常可以以这样的方式得到：由an1得到an，按这样的法则，可以从一个已知的首项开始，有限次地重复做下去，最后产生一个序列，该序列是 实现递归和迭代的基础。 20世纪30年代，正是可计算的递归函数理论与图灵机、演算和POST规范系统等理论一起为计算理论的建立奠定了基础,递归及其有关概念,递归关系指的是：一个数列的若干连续项之间的关系 递归数列指的是：由递归关系所确定的数列。 递归过程指的

30、是：调用自身的过程。 递归算法指的是：包含递归过程的算法。 递归程序指的是：直接或间接调用自身的程序。 递归方法（也称递推法），是一种在“有限”步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素（如数或函数）的方法,递归与数学归纳法,例5.13 计算56 计算方法之一：6，6+6=12，12+6=18，18+6=24，24+6=30； 计算方法之二：56，46，36，26，16；16+6=12，12+6=18，18+6=24，24+6=30； 从56开始计算，假设一个刚学乘法的小学生计算不出这个数，那么，这个小学生一般会先计算46，然后再加6就可以了，若仍计算不出，则

31、会再追溯到36，直到16，然后，再依次加6，最后得到30。这种计算方法其实就反映了一种递归的思想，这个例子还可以用更一般的递归关系表示： an=Can-1+g(n)，2，3，4， 其中，C是已知常数，g(n)是一个已知数列,递归由递归基础和递归步骤两部分组成。 数学归纳法是一种论证方法，而递归是算法和程序设计的一种实现技术； 数学归纳法是递归的基础。如果已知an-1就可以确定an。从数学归纳法的角度来看，这相当于数学归纳法归纳步骤的内容。但仅有这个关系，还不能确定这个数列，若使它完全确定，还应给出这个数列的初始值a1，这相当于数学归纳法归纳基础的内容,递归的定义功能,例： 序列：2，5，11，

32、23，an=2an1+1，请给出其递归定义。 解 该序列的递归定义如下： a1=2； 递归基础 an=2an1+1，n=2，3，4，；递归步骤 例5.15 给出阶乘F(n)=n!的递归定义 解 阶乘F(n)=n!的递归定义如下： F(0)=1；递归基础 F(n)=nF(n1)，n=1，2，3，；递归步骤,阿克曼函数,该函数是由希尔伯特的学生、德国著名数学家威尔海姆阿克曼于1928年发现的。这是一个图灵机可计算的，但不是原始递归的函数。下面，我们介绍这个经典的递归函数，并给出相应的计算过程。 阿克曼函数,解阿克曼函数的递归算法,Begin if m=0 then n+1 else if n=0

33、then A(m-1,1) else A(m-1,A(m,n-1) End,计算A(1,2,解: A(1,2)= A(0, A(1,1) =A(0, A(0, A(1,0) =A(0, A(0, A(0,1) =A(0, A(0,2) =A(0,3) =4,迭代,迭代与递归有着密切的联系，甚至，一类如X0=a，Xn+1=f(n)的递归关系也可以看作是数列的一个迭代关系。 可以证明，迭代程序都可以转换为与它等价的递归程序， 反之，则不然。就效率而言，递归程序的实现要比迭代程序的实现耗费更多的时间和空间。因此，在具体实现时，又希望尽可能将递归程序转化为等价的迭代程序,斐波那契数的求解算法而言，可以

34、使用迭代方法或递归方法来解决。 一些递归算法，如求解梵天塔问题的算法就不能用迭代方法，而只能用递归方法,5.5计算学科中的数学 方法,5.5.6 公理化方法,理论体系,从数学的角度来说，理论是基本概念、基本原理或定律（联系这些概念的判断）以及由这些概念与原理逻辑推理出来的结论组成的集合，该概念可以形式化的定义为： T=， 其中： （1）表示理论； （2）表示基本概念的集合； （3）表示基本原理或定律的集合； （4）表示由这些概念与原理逻辑推理出来的结论组成的集合,构建理论体系的常用方法,每一个理论都由一组特定的概念和一组特定的命题组成。 在一个理论中，基本概念（原始概念）和基本命题（原始命题）

35、必须是明确的，否则就会出现“循环定义”和“循环论证”的严重问题。 构建一个理论体系必须采用科学的方法。 公理化方法 逻辑和历史相统一的方法 从抽象上升到具体的方法,公理化方法,公理化方法是一种构造理论体系的演绎方法，也是计算科学的一种典型方法。 从尽可能少的基本概念、公理出发，运用演绎推理规则，推出一系列的命题，从而建立整个理论体系的思想方法。 它能帮助学生认识一个系统如何严格表述，认识到完备性和无矛盾性对一个公理系统的重要性，认识每一条公理深刻的背景，独立性和它的作用。可惜，其深刻的哲学意义、学术深度和理解上的困难性使得它在本科的课程中较少出现,公理化方法,近年来，这一方法出现在一些学科的前

36、沿研究中。除了形式语义学的研究中使用公理化方法外，开放信息系统的思想和设计，自定义逻辑框架系统的研究，以及分布式代数系统的研究都采用了公理化方法或吸取了公理化方法的思想。随着学科发展的深化，预计这一方法还将在一些分支方向上得到运用，并推动学科进一步深入发展,公理系统的3个条件,用公理化构建的理论体系称为公理系统，该公理系统需要满足无矛盾性、独立性和完备性的条件。 （1）无矛盾性。 （2）独立性。 （3）完备性,简单化是科学研究追求的目标之一。一般而言，正确的一定是简单的（注意，这句话是单向的，反之不一定成立）。 关于公理系统的完备性要求，自哥德尔发表关于形式系统的“不完备性定理”的论文后，数学

37、家们对公理系统的完备性要求大大放宽了。 也就是说，能完备更好，即使不完备，同样也具有重要的价值,公理化方法在计算学科中的应用,公理化方法主要用于计算学科理论形态方面的研究。在计算学科各分支领域，均采用了公理化方法。如 形式语义学 关系数据库理论 分布式代数系统 计算认知领域,例5.18 正整数的公理化概括,原始概念：1； 原始命题（公理）：任何正整数n或者等于1，或者可以从1开始，重复地“加1”来得到它,例5.19 平面几何的公理化概括（欧氏几何,以点、线、面为原始概念，以5条公设和5条公理为原始命题，给出了平面几何中的119个定义，465条命题及其证明，构成了历史上第一个数学公理体系。 原始

38、概念：点、线、面 原始命题（公设和公理）如下： 公设1：两点之间可作一条直线； 公设2：一条有限直线可不断延长； 公设3：以任意中心和直径可以画圆； 公设4：凡直角都彼此相等； 公设5：在平面上，过给定直线之外的一点，存在且仅存在一条平行线，即所谓的“平行公设（公理,例5.20 中国古代唯一的一次公理化尝试：周髀算经,据有关记载，周髀算经成书于公元前100年左右。在周髀算经中，介绍了一个描述天象的盖天学说，该学说构建了一个几何宇宙模型。 该学说中的公理有两个：一个是“天地为平行平面，天地相距80,000里，在北极下方的大地中央有一底面直径为23,000里，高为60,000里的上尖下粗的 “璇玑

39、”（即极下，极下阳光照不到，故不生万物）； 另一个是关于太阳光照以及人目所见的极限范围，即“日照四旁各十六万七千里；人所望见，远近宜如日光所照”，其大意为，日光向四周照射的极限距离是167,000里，人所见到也是这个距离。换言之，日光照不到167,000里之外，人也看不见167,000里之外,从公理可以演绎出：夏至南万六千里，冬至南十三万五千里，日中立竿无影。此一者天道之数。周髀长八尺，夏至之日晷一尺六寸。髀者，股也；正晷者，勾也。正南千里，勾一尺五寸；正北千里，勾一尺七寸。其大意为，在某地竖一个8尺高的竿，太阳移动了一千里，这个竿的影子和原来的相差一寸，即日影千里差一寸。 而从“日照四旁”1

40、67,000里，以及用公理演绎出的冬至日道半径238,000里，又可导出宇宙半径为405,000里，从而构建了一个天、地为圆形平行平面的宇宙模型,今天，我们知道，这个宇宙模型的描述与实际的天象吻合得并不好，与同时代古希腊类似模型相比，也存在较大的差距，而当时，我国天文学家完全可以用代数方法相当精确地解决一些天文学问题，至于宇宙究竟是什么形状或结构，完全可以不去过问。然而，周髀算经是个例外，并成为我国古代学者惟一的一次公理化方法的尝试，这种思想，是受外来因素的影响，还是我国本土科学中某种随机出现的变异？已引起科学史领域专家的极大兴趣,5.6计算学科中的数学 方法,5.6.7 形式化方法,具体公理

41、系统和抽象公理系统,在欧氏几何公理系统中，原始概念（点、线、面）和所有的公理都有直观的背景或客观的意义，像这样有现实世界背景的公理系统，一般被称为具体公理系统。 由于非欧几何的出现，使人们感到具体公理系统过于受直觉的局限。因而，在19世纪末和20世纪初，一些杰出的数学家和逻辑学家开始了对抽象公理系统的研究,在抽象公理系统中，原始概念的直觉意义被忽视，甚至没有任何预先设定的意义，而公理也无需以任何实际意义为背景，它们无非是一些形式约定的符号串。这时，抽象公理系统可以有多种解释。 形式化的运算规则1+1可以解释为一个苹果加一个苹果，或者为一本书加一本书； 布尔代数抽象公理系统可以解释为有关命题真值

42、的命题代数，或者有关电路设计研究的开关代数,形式系统的组成部分,初始符号。初始符号不具有任何意义。 形式规则。形式规则规定一种程序，借以判定哪些符号串是本系统中的公式，哪些不是。 公理。即在本系统的公式中，确定不加推导就可以断定的公式集。 变形规则。变形规则亦称演绎规则或推导规则。变形规则规定，从已被断定的公式，如何得出新的被断定公式。被断定的公式又称为系统中的定理,形式系统的基本特点,严格性 形式系统中，初始符号和形式规则都要进行严格的定义，不允许出现在有限步内无法判定的公式。形式系统采用的是一种纯形式的机械方法，它的严格性高于一般的数学推导。 抽象性 抽象性不是形式系统的专利，抽象是人们认

43、识客观世界的基本方法，只不过形式系统具有更强的抽象性。 形式系统的抽象性表现在它自身仅仅是一个符号系统，除了表示符号间的关系（字符号串的变换）外，不表示任何别的意义,形式系统的局限性,不完备性 1931年，哥德尔提出的关于形式系统的“不完备性定理”指出：如果一个形式的数学理论是足够复杂的（复杂到所有的递归函数在其中都能够表示），而且它是无矛盾的，那么在这一理论中存在一个语句，而这一语句在这一理论中是既不能证明，也不能否证的,形式系统的局限性,不可判定性 如果对一类语句C而言，存在一个算法AL，使得对C中的任一语句S而言，可以利用算法AL来判定其是否成立，则C称为可判定的，否则，称为不可判定的。

44、 著名的“停机问题”就是一个不可判定性的问题。该问题是指，一个任给的图灵机对于一个任给的输入而言是否停机的问题。图灵证明这类问题是不可判定的。 需要指出的是：计算机系统就是一种形式系统，因此，计算机系统一样也具有形式系统的局限性,形式化与公理化,形式化不一定导致公理化，公理系统也不一定是形式系统。 如欧氏几何公理系统就不是形式系统。 形式化与公理化虽然不同，但在近代数学中，形式系统大都是形式化的公理系统,第5章计算学科的内容 与方法,5.5 布尔代数基础,逻辑与代数是计算机科学最重要的基础，布尔代数是数理逻辑早期的雏形，是一种用代数演算的方法来研究思维结构的逻辑系统。 问题：什么是逻辑呢？ 对

45、逻辑来说不存在清规戒律，每个人都可以构造自己的逻辑，即他自己的语言形式，只要他愿意。对他的唯一要求是：如果他想讨论这种逻辑，那么他必须说清楚他的方法，并给出语法规则，而不是给出哲学论据。 Carnap（卡尔纳普,5.5 布尔代数基础,5.5.1 集合的基本概念与 基本运算,概念,由事物或对象组成的集体，无论它们是由其成员通过枚举方式直接表示出来的，还是由其成员所具有的某些本质属性表示出来的，都称为集合。 称两个集合是相等的，如果构成这两个集合的成员完全相同。集合的成员也叫元素。 一个集合A中元素的个数叫做集合A的基数，记为A。 请注意，这不是基数的严格的定义。对有穷集合，这样定义基数勉强可行，

46、但对无穷集合不恰当。有关集合基数的概念和知识将来读者会在离散数学或集合论等课程中系统地学习，目前，我们暂且使用这种不严格的直观上的定义,2. 集合的三种描述方法,枚举法：列出所有元素的表示方法。 如1至5的整数集合可表示为： =1，2，3，4，5； 外延表示法：当集合中所列元素的一般形式很明显时，可只列出部分元素，其他则用省略号表示。 如斐波那契数列可表示为： 0，1，1，2，3，5，8，13，21，34， ； 谓词表示法：用谓词来概括集合中元素的属性。 如斐波那契数列可表示为： Fn|Fn+2=Fn+1+Fn，F0=0，F1=1，n0,3. 从属与包含关系,通常用大写英文字母作为集合的名称。

47、若某事物a是集合A的一个元素，则记为： aA 并说“a属于A”，或者说“a在A中”。 若a不是集合A的元素，则记为： a A 当以枚举形式表示一个集合时，我们用一个大括号把这些枚举的元素括起来以表示这个集合,3. 从属与包含关系,例1 麻雀，黄鹂，杜鹃，白鹭，红嘴鸥是一个由五种鸟组成的集合； 如果a,b,c,d,x,y,z是由英语的26个小写字母组成的集合。 例2 Axax2+bx+c0 且 a,b,cR，R是实数集。 例3 Ba,b,aa,ab,bb,aaa,aab,abb,bbb,aaaa, 这种带省略的表示形式实际上可表示一些集合元素有某种出现规律的无穷集合,3. 从属与包含关系,集合的

48、表示应当注意以下两点： (1) 同一个集合中的元素是互不相同的。 (2) 集合中的元素之间不规定次序。 与空集合相对应的一个大的集合是所谓的全集合，即一切事物构成的集合。这是一个虚构的集合，但它在布尔代数的运算中是有用的。我们用1来表示这个虚设的全集合,3. 从属与包含关系,考虑两个集合A和B。若集合A的每一个元素也是集合B的一个元素，则称集合B包含集合A，也称集合A包含在集合B中，记为AB 若AB，则称A是B的子集合，B是A的母集合。显然，对任何集合A，有AA。 若集合A、B之间存在AB且AB，则称A是B的真子集合，记为AB。若AB，又有BA，则可以得出结论AB。这是因为A的元素都是B的元素

49、，而B的元素也是A的元素，说明A，B中拥有相同的元素，所以A和B相同，故相等。显然，对任何集合A，A1。特别地，1,3. 从属与包含关系,通常用大写英文字母作为集合的名称。若某事物a是集合A的一个元素，则记为： aA 并说“a属于A”，或者说“a在A中”。 若a不是集合A的元素，则记为： a A 当以枚举形式表示一个集合时，我们用一个大括号把这些枚举的元素括起来以表示这个集合。 例1 麻雀，黄鹂，杜鹃，白鹭，红嘴鸥是一个由五种鸟组成的集合,4. 集合的基本运算,集合的并 设A、B为两个任意集合，将集合A的元素和集合B的元素合并在一起，组成一个新的集合C，称为集合A和集合B的并集，简称A和B的并

50、。可表示为： CABxxAxB 求并集的运算称为并（运算）。 例5.1 若A=a，b，c，d，B=b，d，e，求集合A和B的并。 解：ABa，b，c，d，e,集合的交,设A、B为两个任意集合，定义A和B的公共元素构成的集合C为A和B的交集，简称A和B的交，记为: CABxxAxB 例5.3 若A=x | x -5，B=x|x5xx1x5x1,集合的差,设A、B为两个任意集合，所有属于A而不属于B的一切元素构成的集合S，称为A和B的差集。可表示为： S=AB=xxAxB。 求差集的运算称为差（运算）。 例5.2 若A=a，b，c，d，B=b，d，e，求集合A和B的差。 解：AB=a，c,集合的补

51、,设I为全集，A为I的任意一子集，IA则为A的补集，记为A。可表示为 A=IA=xxI， 求补集的运算称为补（运算）求补集的运算称为补（运算） 例5.4 若I=x5x5，A=x0 x1，求。 解：A=IA=x5x01x5,集合的乘积,集合A1，A2，An的乘积一般用法国数学家笛卡尔（Rene Descartes）的名字命名，即笛卡尔积。该乘积表示如下： A1A2An=（a1，a2，an）aiAi，i1，2，n A1A2An的结果是一个有序元组的集合。 例5.5 若A=1，2，3，B=a，b，求AB。 解：AB=（1，a），（1，b），（2，a），（2，b），（3，a），（3，b,集合运算的定理

52、,定理1 设A为一个集合，B为A的补集合，I为全集，则 (1) AB， (2) ABI， (3) I， (4) I， (5) (A)A， (6) (I)I， (7) ()。 我们选择证明其中的(1)，其余的证明留给读者作为练习,集合运算的定理,证明 (1) 用反证法。设AB，则必存在非空元素xAB，故xA且xB，此与B为A的补集合矛盾。所以， AB。 例4 设Aa,b,c,d，Bc,d,e,f，Ce,f,g,h，则 ABc,d， ABa,b,c,d,e,f， AC， ACa,b,c,d,e,f,g,h,集合运算的定理,根据定义，不难证明定理2。 定理2 对任意集合A和集合B，有 (1) ABB

53、A， （交换律） (2) ABBA， （交换律） (3) AAA， (4) AAA， （幂等律） (5) AA， (6) AA1， (7) A， (8) AA,集合运算的定理,我们选择证明其中的(2)，其余的(1)、(3)-(8)大家可以自己试着去证明。 证明 (2) 我们分两部分来证明。首先证明左边的集合是右边集合的子集合，然后再证明右边的集合是左边集合的子集合。这样，若两个集合互为子集合时，必然相等。 设任意元素xAB，则xA或者xB，也可表述为xB或者xA，故ABBA； 同理可证，BAAB。 所以，ABBA。 定理2(2)的上述证明方法是证明两个集合相等时最常用的方法，也是最基本的方法,

54、5. 集合上的一些基本关系,下面我们在集合相补、包含、交与并的基础上，首先来建立一些基本关系。 定理3 设A，B为任意集合，则 (1) ABA， (2) ABB， (3) AAB， (4) BAB。 我们选择证明其中的(1)，其余的(2)-(4)大家可以自己试着去证明。 证明 (1) 设任意元素xAB，由交的定义知，xA，故ABA。,5. 集合上的一些基本关系,定理4 设A、B为任意集合，则 (1) AB，当且仅当ABA， (2) ABA，当且仅当ABB， (3) ABB，当且仅当AB。 这个定理说明了一个循环等价关系。象这样的等价关系，今后可用来作等价的概念定义。 证明 (1) 我们分两部分

55、来证明定理的充分性。 设任意元素xAB，故xA且xB，可得ABA； 又设任意元素xA，由AB知xB，故xAB，可得AAB。 综合、，知ABA。 由ABA导出AB是显然的。,5. 集合上的一些基本关系,上面的证明中，仍然采用了论证两个集合相等最基本的方法，即设法先证明等式两边的集合互为子集合。若两个集合互为子集合，那么，显然这两个集合是相等的。 证明一个定理，有时候需要从定义出发推导、论证，有时候需要引用已知的结论来简化证明步骤。事实上，定理4(1)的证明中第一部分可以直接引用定理3的(1)。今后我们应该逐步习惯于简化的证明方式,5. 集合上的一些基本关系,定理5（De Morgan 律） 设A

56、、B为任意集合，则 (1) (AB)AB， (2) (AB)AB。 证明 我们只要证明其中的一个就可以了，因为这两个式子中的任何一个是另一个在相补关系下的直接结果。下面，我们证明(1)。 设任意元素x(AB)，则x(AB)，因此x A或xB。换言之xA或xB，故xAB。所以， (AB)AB； 反之，设任意元素xAB，则xA或xB。换 言之xA或xB，因此x(AB)，故x(AB)。所以: AB(AB) 从而，可知(AB)AB。,5. 集合上的一些基本关系,定理6 对任意的集合A，A。 证明 使用反证法。假设定理不成立，即存在集合A，使得A不成立。这就是说，存在元素x,但xA，这与是空集合相矛盾。

57、故定理成立，空集合是一切集合的子集合。 定理7 空集合是唯一的。 证明 设1和2都是空集合，由定理6知: 11 且 21， 所以12。,6. 集合上的一些运算定律,定理8 设A、B、C是任意的集合，则 (1) A(BC)(AB)C， （结合律） (2) A(BC)(AB)C， （结合律） (3) A(BC)(AB)(AC)， （分配律） (4) A(BC)(AB)(AC)。 （分配律） 证明 (3) 设xA(BC)，则xA或xBC。若是前一种情况，那么xAB且xAC，因而x(AB)(AC)；若是后一种情况，那么xB且xC，因此xAB且xAC，也有: x(AB)(AC)。 这就证明了: A(BC

58、)(AB)(AC,6. 集合上的一些运算定律,反之，设x(AB)(AC)，则xAB且xAC。 若xA，那么xA(BC)；若xA，那么必有xB且xC， 因此xBC，也有xA(BC)。这就证明了: (AB)(AC)A(BC)； 所以，A(BC)(AB)(AC)。,7. 集合上的其它一些关系,利用集合上的基本关系和基本运算，可以导出集合上的其它一些关系。 定理9 设A、B、C是任意的集合，那么下列关系成立： (1) 若AB且AC，则ABC； (2) 若AC且BC，则ABC。 定理10 设A、B、C是任意的集合，若AB，则 (1) ACBC， (2) ACBC。 由定理3和定理10易证定理11,7.

59、集合上的其它一些关系,定理11 设A，B是任意的集合，则有A(AB)A。 证明 依定理3有A(AB)A。又AAA，AAB，因此，由定理10知AAA(AB)，故AA(AB)。所以，A(AB)A。 定理12 设A、B是任意的集合，则AB，当且仅当AB。 定理13 设A是一个集合，那么下列等式成立： (1) 若对任意的集合B，都有AB，则A； (2) 若对任意的集合B，都有BA，则A1。 证明 (1) 由题设，特别当B时，有A，但A， 所以A。 定理14 设A、B是两个集合，那么下列等式成立： (1) 若AB，则A且B； (2) 若AB1，则A1且B1。 证明 (1) 因AAB，故A；同理可证，B。,8. 集合的差与对称差(中学已经学习,定义1 集合A，B的差AB定义为一切属于A但不属于B的元素构成的集合，即ABAB。 对任意集合A，B，不难证明定理15。 定理15 设A，B，C都是集合，那么下列等式成立： (1) 1AA； (2) AB，当且仅当AB； (3) (AB)BAB； (4) C(AB)(CA)(CB)。 （分配律） 交关于差是可分配的。但是，并关于差却不是可分配的。大家可以通过思考和举一反例来认识这一点,8. 集合的差与对称差,定义2 集合A，B的对称差AB定义为A与B之差和B与A之差的并，即AB(AB)(BA)。 显然，A与B的对称差也可以写成如下的定义形式： AB(