计算机数学基础

计算学科中常用的数学概念和术语

集合

1. 集合的概念

集合是数学的基本概念它是构造性数学方法的基础。集合就是一组无重复的对象的全体，集合中的对象称为集合的元素，如计算机专业学生全部必修课程可以组成一个集合，其中的每门课程就是这一集合中的元素。

2. 集合的描述方法

通常用大写字母表示集合，用小写字母表示元素。描述集合的方式主要有以下3种

• 1枚举法列出所有元素的表示方法

如1至5的整数集合可表示为 A={12345}

• 2外延表示法当集合中所列元素的一般形式很明显时可只列出部分元素其他则用省略号表示

如斐波那契数列可表示为 { 0112358132134 }

• 3谓词表示法用谓词来概括集合中元素的属性

如斐波那契数列可表示为 {Fn|Fn+2=Fn+1+FnF0=0F1=1n0} === 集合的运算 === 集合的基本运算有并差交补和乘积等运算

• 1集合的并

设AB为两个任意集合所有属于A或属于B的元素构成的集合C称为A和B的并集可表示为CABxxAxB

求并集的运算称为并运算

例1 若A={a,b,c,d} ，B={b,d,e}求集合A和B的并

解A,B,a,b,c,d,e

• 2集合的差

设AB为两个任意集合所有属于A而不属于B的一切元素构成的集合S称为A和B的差集可表示为S=AB=xxAxB

求差集的运算称为差运算

例2 若A={a,b,c,d}B={b,d,e}求集合A和B的差

解AB={a,c}

• 3集合的交

设AB为两个任意集合由和的所有相同元素构成的集合CAB称为A和B的交集可表示为CABxxAxB

求交集的运算称为交运算

例3 若A={x | x > -5}B={x|x<1}求集合和B的交A

解ABxx>﹣5xx<1x–5<x<1

• 4集合的补

设I为全集A为I的任意一子集I–A则为A的补集记为A可表示为

A=I–A=xxIAx∉

求补集的运算称为补运算

例4 若I=x–5﹤x﹤5A=x0﹤x﹤1求A

解A=I–A=x–5﹤x﹤01﹤x﹤5

• 5集合的乘积

集合A1A2An的乘积一般用法国数学家笛卡尔Rene Descartes的名字命名，即笛卡尔积该乘积表示如下：

A1A2An={a1a2anaiAii12n}

n A1A2An的结果是一个有序元组的集合

例5 若A={123}B={ab}求AB

解AB={1a1b2a2b3a3b}

函数和关系

1. 函数

函数又称映射是指把输入转变成输出的运算该运算也可理解为从某一定义域的对象到某一值域的对象的映射函数是程序设计的基础程序定义了计算函数的算法而定义函数的方法又影响着程序语言的设计好的程序设计语言一般都便于函数的计算，设f为一个函数当输入值为a时输出值为b则记作 baf=)(

2. 关系

关系是一个谓词其定义域为k元组的集合通常的关系为二元关系其定义域为有序对的集合在这个集合中我们说有序对的第一个元素和第二个元素有关系如学生选课如图1所示

图1 学生选课表

在图1中我们用关系的术语可以说张三与文学以及哲学课有关系选课关系,李四与艺术以及数学课有关系,王五与历史以及文学课有关系

3. 等价关系

在关系中有一种特殊的关系即等价关系它满足以下3个条件

1. 自反性即对集合中的每一个元素a都有aRa
2. 对称性即对集合中的任意元素abaRb成立当且仅当bRa成立
3. 传递性即对集合中的任意元素abc若aRb和bRc成立则aRc一定成立

等价关系的一个重要性质是集合A上的一个等价关系R可将A划分为若干个互不相交的子集称为等价类

例6 证明非负整数N上的模3的同余关系R为等价关系

证明：

首先将该关系形式化地表示为

R=(ab)abNa mod 3=b mod 3

1. 自反性证明：对集合中的任何一个元素aN都有a mod 3= a mod 3
2. 对称性证明：对集合中的任意元素abN若a mod 3=b mod 3则有

b mod 3=a mod 3

• 3传递性证明

对集合中的任意元素abcN若a mod 3=b mod 3b mod 3=c mod 3则有a mod 3=c mod 3

综上所述该关系满足自反性对称性和传递性因此该关系为等价关系 。

例7 假设某人在唱歌事件e1的同时还可以开车事件e2或者步行事件e3但一个人不能同时开车和步行

问以上反映的并发现象如用关系来表示时是否是等价关系

答以上反映的是一种并发co现象如用关系来表示则这种并发关系具有自反性和对称性即可表示为e1 co e1e2 co e2e3 co e3以及e1 co e2或e2 co e1e1 co e3或e3 co e1但不满足传递性即e2 co e1e1 co e3不能推出e2 co e3即不能在开车的同时又步行因此以上并发关系不是等价关系

字母表字符串和语言

所有的计算机程序设计语言都是形式语言其构成基础同一般自然语言一样也是符号或字母常用的符号有数字0∼9大小写字母AZaz括号运算符+-*/等

有限字母表指的是由有限个任意符号组成的非空集合简称为字母表用Σ表示字母表上的元素称作字符或符号用小写字母或数字表示如abc123等

字母表可以理解为计算机输入键盘上符号的集合字母可以理解为键盘上的每一个英文字母数字标点符号运算符号等

字符串也称为符号串指的是由字符组成的有限序列常用小写希腊字母表示字母表Σ上的字符串以下列方式生成

1. ε为Σ上的一个特殊串称为空串对任何aaε=εa=a
2. 若σ是上的符号串且a则σa是上的符号串
3. 若α是上的符号串当且仅当它由1和2导出

直观来说上的符号串是由其上的符号以任意次序拼接起来构成的任何符号都可以在串中重复出现ε作为一个特殊的串由零个符号组成应当指出的是空串ε不同于我们计算机键盘上的空格键。

语言指的是给定字母表上的字符串的集合例如当={ab}则{abaabbababbba}εanbnn1都是上的语言不包含任何字符串的语言称作空语言用Ф表示注意ε不同于Ф前者表示由空串组成的语言后者表示空语言。

语言是字符串的集合因此传统的集合运算如并交差补笛卡尔积对语言都适用除此之外语言还有一种重要的专门的运算即闭包运算 。

语言文法以及自动机有着密切的关系语言由文法产生短语结构语言上下文有关语言上下文无关语言和正规语言分别由0型文法1型文法2型文法和3型文法产生自动机是识别语言的数学模型各类文法所对应的自动机分别是图灵机线性有界自动机下推自动机和有限状态自动机。

需要指出的是语言与数学模型不是一一对应的关系一种语言可以由不同的文法产生也可以由不同的自动机识别。

布尔逻辑

布尔逻辑是建立在TRUE和FALSE两个值上的数学体系值TRUE和FALSE称作布尔值一般用0和1表示。

最基本的布尔运算是非NOT符号为¬和并AND符号为运算其他的布尔运算如或OR符号为异或XOR符号为⊕等值Equivalence符号为↔蕴含Implication符号为 → 运算均可以用最基本的非和并运算来表示，下面综合列出各运算的定义：

¬0=1 1=0¬ 
00=001=010=011=1 
00=001=110=111=1 
⊕ 00=0 ⊕ 0⊕1=110=1 ⊕ 11=0
00=1↔0↔1=010=0↔11=1↔ 
00=1→0→1=11→0=011=1→

定义定理和证明

定义定理和证明是数学的核心也是计算学科理论形态的核心内容其中定义是蕴含在公理系统之中的概念和命题定理是被证明为真的数学命题证明是为使人们确信一个命题是真的而作的一种逻辑论证。

例8 在欧氏几何中平面角的定义为平面角是在一平面内但不在一直线上的两条相交线的相互倾斜度等腰三角形的定理为两边相等的三角形为等腰三角形