5计算学科中的数学方法

第5章计算学科中的数学方法理论上，凡能被计算机处理的问题均可以转换为一个数学问题，凡能以离散数学为代表的构造性数学方法描述的问题，当该问题所涉及的论域为有穷，或者为无穷但存在有穷表示时，这个问题也一定能用计算机来处理。一、数学的基本特征及数学方法的作用（P97-P98）二、计算学科中常用的数学概念和术语1.集合（已讲）2.函数和关系•论域：一定场合（语境）中思考和议论所涉及的对象的范围。即某一范围内被论及对象的全部所构成的集合。•个体：可以独立存在的物体。•谓词：用来刻画个体的性质，或关系的词，刻画一个个体性质的词为一元谓词，刻画几个个体之间关系的词称为n元谓词。（1）谓词：充当谓语（说明主语“怎么样”，“是什么”）和能同副词结合的动词、形容词（辞海）。（Predicate，谓词、断言）•命题：一个能分辩真假的陈述句称作一个命题•量词：全称量词：所有的存在量词：存在（2）谓词逻辑：将命题分解为主词、谓词和量词，研究其形式结构，导出有关的逻辑形式和规律的逻辑理论（辞海）。（3）函数（映射）：把输入变成输出的运算，f(a)=b（4）关系•定义，（见上次课）A1×A2×…×An中的任一子集称为A1,A2,…,An的一个几元关系。•二元关系：A1×A2的一个子系。有序对。P100，例，选课关系：R={(张,文)，(张,哲)，(李,数)，(李,艺)，(王,史)，(王,文)}}•二元关系中的特例：集合A上的关系：A×A（A到A自身的关系），A2。例A={0,1,2,3}，则={(0,0),(03),(20),(2,1),(2,3),(3,2)}是A上的一个关系。例实数集R，1={(x,y)|(x,y)R2,x＜y},1是R上的“小于”关系，x1y。•集合A上的关系性质设是集合A上的关系。①若对于所有的aA。有aa，则称是自反的。②对于所有的a,bA，若每当有ab就有ba，则称是对称的。③对于所有的a,b,cA，若每当有ab和bc就有ac，则称是可传递的。•等价关系：集合A上的关系，如果它是自反、对称且可传递的，则称为A上的等价关系。如：集合元素中的相等关系，直线之间的平行关系，三角形的相似关系，位同一条街的居民之间的关系等。•等价类设是A上的等价关系，若ab成立，则a等价于b（在下）。定义：设是A上的等价关系，则A中等价于a的全体元素的集合称为a所生成的等价类。记为[a]={b|bA,ab}•例5.6，“同余关系”是等价关系•例5.7，“并发关系”是非等价关系3.字母、字符和语言。4.布尔逻辑（P102-P103）•蕴含：命题P与命题Q组成的复合命题，PQ：“如果…那么”，“如果…必须”，“必须…以便”P：前件，Q：后件。PQ真值表：当P为假时，Q无论真假，PQ总为真。5.定义、定理和证明。PQ01011011PQ101000=1(1)01=1(1)10=0(0)11=1(1)三、证明方法1.直接证明与间接证明2.反证法3.归纳法。P(1)(n)(P(n)P(n+1))nP(n).4.构造性证明四、递归和迭代1.定义：P106复习汉诺塔h(n)=2h(n-1)+1（3）递归过程：调用自身的过程。（4）递归算法：包含递归过程的算法。an=can-1+g(n),n=2,3,4,…递归是算法和程序设计的一种实现技术，数学归纳法是递归的基础。2.递归的定义功能例，文法G的生成式（规则）S0A1。A01，递归基础A1=01A0A1递归步骤An=0An-11L(G)={0n1n|n≥1}定义一种语言例，阿克曼函数n+1若m=0A(m,n)=A((m-1),1)若n=0A(m-1,A(m,n-1))若m,n＞03.迭代反复替换迭代程序递归程序转换五、公理化方法1.公理系统的要求2.例（P110）•元矛盾性•独立性•完备性六、形式化方法符号化+抽象公理化