计算学科中的数学方法

1、第5章 计算学科中的数学方法,理论上，凡能被计算机处理的问题均可以转换为一个数学问题，凡能以离散数学为代表的构造性数学方法描述的问题，当该问题所涉及的论域为有穷，或者为无穷但存在有穷表示时，这个问题也一定能用计算机来处理。,一、数学的基本特征及数学方法的作用（P97-P98） 二、计算学科中常用的数学概念和术语,集合（已讲） 函数和关系,论域：一定场合（语境）中思考和议论所涉及的对象的范围。即某一范围内被论及对象的全部所构成的集合。,个体：可以独立存在的物体。 谓词：用来刻画个体的性质，或关系的词，刻画 一个个体性质的词为一元谓词，刻画几个 个体之间关系的词称为n元谓词。,（1）谓词：充当谓语

2、（说明主语“怎么样”，“是什么”） 和能同副词结合的动词、形容词（辞海）。 （Predicate，谓词、断言）,命题：一个能分辩真假的陈述句称作一个命题 量词：全称量词 ：所有的 存在量词 ：存在,（2）谓词逻辑：将命题分解为主词、谓词和量词，研究 其形式结构，导出有关的逻辑形式和规 律的逻辑理论（辞海）。,（3）函数（映射）：把输入变成输出的运算，f (a)=b （4）关系,定义，（见上次课）A1A2 An中的任一 子集称为A1, A2, , An的一个几元关系。 二元关系： A1A2 的一个子系。有序对。 P100，例，选课关系：R=(张, 文)，(张, 哲)， (李, 数)，(李, 艺)

3、，(王, 史)，( 王, 文),二元关系中的特例：集合A上的关系：AA （A到A自身的关系），A2。 例 A=0, 1, 2, 3，则 =(0, 0), (0 3), (2 0), (2, 1), (2, 3), (3, 2)是A 上的一个关系。 例 实数集R，1=(x, y)|(x, y) R2, xy, 1是R 上的“小于”关系，x1y。,集合A上的关系性质 设是集合A上的关系。 若对于所有的 a A。有aa，则称是自反的。 对于所有的 a, b A，若每当有ab就有ba， 则称 是对称的。 对于所有的a, b, c A，若每当有ab和bc就有 ac，则称是可传递的。,等价关系：集合A上的

4、关系 ，如果它是自反、对 称且可传递的，则称为A上的等价关系。 如：集合元素中的相等关系，直线之间的平行关 系，三角形的相似关系，位同一条街的居民 之间的关系等。,等价类 设是A上的等价关系，若ab成立，则a等价 于b（在下）。 定义：设是A上的等价关系，则A中等价于a 的全 体元素的集合称为a所生成的等价类。 记为a=b|bA, ab 例 5.6，“同余关系”是等价关系 例 5.7，“并发关系”是非等价关系,字母、字符和语言。 布尔逻辑（P102-P103）,蕴含：命题P与命题Q组成的复合命题，P Q ：“如果 那么”，“如果必须”，“必须 以便” P ：前件，Q：后件。 P Q真值表：,当P为假时，Q无论真假，PQ总为真。,定义、定理和证明。,三、证明方法,直接证明与间接证明 反证法 归纳法。P (1) (n) (P(n) P(n+1) nP(n). 构造性证明,四、递归和迭代,定义：P106 复习汉诺塔h(n)=2h(n-1)+1,（3）递归过程：调用自身的过程。 （4）递归算法：包含递归过程的算法。 an= can-1+ g(n)