资源描述
1.1、集合、集合 集合集合：对象的汇集。如：L=a,b,c,d 就是四个字母的汇集形成的集合。元素或成员元素或成员：构成集合的所有对象。如：b是集合L的一个元素，表示成：bL 另一方面z不是L的元素，记作：z L 单元素集单元素集：集合中只有一个元素，即有一个元素构成的集合。空集空集：集合中没有一个元素，用表示。集合元素性质定义：设集合A已经定义，P是A的元素具有的性质，则可以定义一个新集合B如下：B=x:x A且x具有性质P 子集子集：如果集合A的每一个元素都是集合B的元素，则称A是B的子集，记作：A B 真子集真子集：如果A B，但AB，则称A是B的真子集。集合的性质集合的性质：设A、B和C是集合，则下述算律成立1、幂等率 AA=A AA=A2、交换律 AB=BA AB=BA3、结合律 (AB)C=A(BC)(AB)C=A(BC)4、分配律 (AB)C=（AC)(BC)(AB)C=（AC)(BC)5、吸收律 (AB)A=A (AB)A=A6、De Morgan律 A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)幂集：集合A的所有子集所有子集的汇集本身是一个集合，叫做A的幂集 记作：2A非空集合的非空集合的划分划分：如果是A的一些子集的集合，使得满足 (1)的每一个元素非空，即非空集合；(2)的不同元素是不相交的；(3)=A，其中表示中所有元素的汇集 则是A的一个划分。例如：(a,b),c,d是a,b,c,d的一个划分；奇自然数集合和偶自然数集合构成自然数N的一个划分。1.2、关系与函数、关系与函数 ：由两个元素构成的对，前后有别。如a和b的有序对记作(a,b)，a和b叫做它的。：两个集合A和B的迪卡儿积是aA且bB的所有有序对(a,b)构成的集合，记作AB。：两个集合A和B的二元关系是AB的子集。：设n是任一自然数，如果a1,a2,an是任意n个对象，也可以有相同对象，则(a1,a2,an)是一个。n叫做序列长度长度。从而就有：有序2元组、有序3元组、。有序n元组 ：集合A1,An上的n元关系就是A1。An一个子集。即有序n元组的集合。：集合A到集合B的函数是A和B上的具有下述特殊性质的二元关系R:对于每一个元素aA，在R中恰好存在一个有序对以a为第一分量，第二分量bB。一般的，设f:A1An|B是一个函数，f(a1,an)=b，其中：aiAi，且bB，有时称a1,an是f的自变量，b是f对应的值。：如果对任意两个不同的值a,aA，f(a)f(a)则称函数f:A|B是一对一的。：如果B的每一个元素都是A的某一个元素在f下的值或叫象，则称函数f:A|B满射到B。：如果函数f:A|B既是一对一的，又是满射到B的，则称f是A与B之间的双射。：记作R-1，R-1=(a,b):(b,a)R 显然，若R AB，则R-1 BA。：设Q和R是两个二元关系，他们的合成Q。R(简记QR)为:QR=(a,b):对于某个c，(a,c)Q且(c,b)R 注意：两个函数f:A|B和g:B|C的合成是一个函数h:A|C，使得对每一个aA，h(a)=g(f(a)1.3、特殊类型的二元关系、特殊类型的二元关系 1、AA的二元关系二元关系 设A是一个集合，R AA是A上的一个二元关系，可以用一个有向图表示关系R。A的每一个元素用一个小圆圈表示(叫做有向图的顶点)，从a到b画一个箭头当且仅当(a,b)R，这些箭头是该有向图的边。例如：用图1-1中图表示关系R=(a,b),(b,a),(a,d),(d,c),(c,c),(c,a)adcb图1-1 二元关系的有向图表示自反关系自反关系：如果对于每一个aA，(a,a)R，则称关系R AA 是自反自反的对称关系对称关系：如果只要(a,b)R就有(b,a)R，则称关系R AA 是对称对称的 没有(a,a)形式的有序对的对称关系可以表示成或称。反对称关系反对称关系：如果当(a,b)R且ab时，(b,a)R，则称关系R是反对称反对称的传递关系传递关系：如果只要(a,b)R且(b,c)R就有(a,c)R，则称关系R是传递传递的等价关系等价关系：把自反、对称、传递的关系叫做等价关系等价关系。如书上图1-6。等价类等价类：表示等价关系的无向图由若干个集团组成，把等价关系的这种集团 叫做等价类等价类。定理1.3.1 设R是非空集合A上的等价关系，则R的等价类构成A的一个划分。（证明：利用等价关系性质采用反证法，略）另外，由于二元关系R可以表示成图，所以也有类似于图的、。1.4、有穷集合与无穷集合：如果存在双射函数f:A|B，则称集合A与B等势。：一般的，如果对某个自然数n，一个集合与1,2,n等势，则称这个集合是有穷的有穷的。：如果一个集合不是有穷的，则称它是无穷的无穷的。例如：自然数集合N是无穷的；整数集合、实数集合都是无穷的。：称与N等势的集合是可数无穷的可数无穷的。：称有穷集合或可数无穷集合是可数的可数的。（可枚举的）相反，不是可数的集合称为。另外，要证明集合A是可数无穷的，必须给出A与N之间的一个双射函数f。见书1.5、三个基本的证明技术、三个基本的证明技术 1、的原理的原理 如果A是一个自然数的集合使得：（1）0A；（2）对于每一个自然数n，0,1,n A蕴函n+1A;则A=N 非形式地非形式地说(数学归纳法的原理)：任何一个包含0的自然数集合，如果它具有下述性质：它只要包含所有小于等于n的自然数就包含n+1，则它实际上就是全体自然数的集合。一般的一般的，用归纳法证明下述断言：“对于所有的自然数n，性质P成立。”用下述方式把数学归纳法原理应用于集合A=n:对于n，P为真：（1）基础步骤：证明0A，即对于0，P成立。（2）归纳假设：假设对任意固定的n0，P对于0,1,n成立。（3）归纳步骤：利用归纳假设证明P对于n+1成立，于是根据归纳原理，A等于N，即P对于每一个自然数成立。换句话说，如果企图把换句话说，如果企图把A的元素的元素(“鸽子鸽子”)与与B的元素的元素(“鸽巢鸽巢”)配对，迟配对，迟早不得不把一只以上的鸽子放入一个巢里。早不得不把一只以上的鸽子放入一个巢里。鸽巢原理可以用第一个基本原理鸽巢原理可以用第一个基本原理-数学归纳法证明。数学归纳法证明。(见书上见书上)设设R是有穷集合是有穷集合A上的二元关系，上的二元关系，a,bA。如果在R中有一条从a到b的通路，则有一条长度不超过|A|的通路。：假设(a1,a2,an)是从a1=a到an=b的最短通路，即长度最小的通路，又假设n|A|。由鸽巢原理，A有一个元素重复出现在这条通路上，比如说ai=aj，1ij n。于是，(a1,a2,ai,aj+1,an)是另一条更短的从a到b的通路，这与假设(a1,a2,an)是从a到b的最短通路相矛盾。(完毕)3、：设设R是集合是集合A上的二元关系，上的二元关系，D=a:aA且(a,a)R称为R的对角线集合。对于每一个aA，令Ra=b:bA且(a,b)R，则D与每一个Ra都不相同。即，把R看成一个正方阵列，对角线的补与每一行都不同。（见书上例1.5.3）理由：关于a是否是元素的问题，对角线集合D与Ra集合总是不同的。若aD，则必然(a,a)R；若aRa，则必然(a,a)R;矛盾！即对角线上无关系的元素所在行自然不相等；对角线上有关系的元素又多余该对角线上元素。定理定理1.5.2 集合集合2N是不可数的。是不可数的。（自然数的幂集自然数的幂集）证明：(大概思路)利用反证法假设它是可数无穷的，再利用对角线原理证明假设不成立。略，见书。1.6、闭包与算法、闭包与算法 设RA2是集合A上的有向图。R的是关系 R*=(a,b):a,bA且在R中存在从a到b的通路 例子见书图1-9，构造算法见P17下 定义1.6.1函数的增长率函数的增长率：算法随问题规模变化的增长规律。(1)所有次数相同的多项式具有相同的增长率。(2)nd2n nn 例子：以R关系的自反传递闭包计算为例，说明函数增长率。p17定义1.6.1算法复杂度O(nn+1)p20改进后新算法复杂度O(n5)p21再改进后新算法复杂度O(n3)本科生算法分析和数据结构课程中已经介绍过。略。封闭性：封闭性：定义定义 1.6.3 设D是一个集合，R Dn+1是D上的一个n+1元关系，其中n0。又设B是D的子集。如果只要b1,bnB且(b1,bn,bn+1)R，就有bn+1B，则称B在R下是封闭的。任何“集合B在关系R1,R2,Rm下是封闭的”形式的性质称为B的封闭性。定理定理1.6.1 设P是由集合D上的关系定义的封闭性，A是D的子集，则有唯一的包含A具有性质P的极小集合B。（证明：略）闭包闭包：定理1.6.1中的B是A在关系R1,Rm下的闭包闭包。关于形式语言及表示我们前面已经讨论过。下面我们简单地讨论一下语言的有穷表示-正则表达式与正则语言 计算理论中一个核心问题：用有穷的规定有穷的规定说明表示无穷语言无穷语言。例1.8.1 令L=w0,1*：在w中1出现两次或三次，并且第一次和第二次不相邻 这个语言可以只用单元集和语言运算符号、。、*描述如下：0*。1。0*。0。1。0*(1。0*)*)进一步简单地写成：L=0*10*010*(10*)-正则表达式正则表达式正则表达式定义定义：字母表上的正则表达式是字母表 (,),*上可以如下获得的所有字符串：(1)、和的每一个成员是正则表达式。(2)、如果和是正则表达式，则()也是正则表达式。(3)、如果和是正则表达式，则()也是正则表达式。(4)、如果是正则表达式，则*也是正则表达式。(5)、除上述(1)-(4)得到之外，没有任何别的正则表达式。如果如果是任意一个正则表达式，则是任意一个正则表达式，则L()是是表示的语言。即表示的语言。即L是从字是从字符串到语言的函数。符串到语言的函数。函数L的定义：(1)、L()=空集；对于每一个a，L(a)=a (2)、如果和是正则表达式，则L()=L()L()(3)、如果和是正则表达式，则L()=L()L()(4)、如果是正则表达式，则L(*)=L()*例1.8.2 L(ab)*a)是什么？计算如下：L(ab)*a)=L(ab)*)L(a)-由(2)得到 =L(ab)*)a -由(1)得到 =L(ab)*a -由(4)得到 =(L(a)L(b)*a -由(3)得到 =(ab)*a -由(1)两次得到 =a,b*a =wa,b*：w以a结束。例1.8.3 (c*(a(bc*)*)表示的语言是什么？-该正则表达式表示a,b,c上不含子串ac的所有字符串的集合。正则语言正则语言：定义字母表上的正则语言正则语言类由所有可写成L=L()的语言L组成，其中是上的任一正则表达式。即，正则语言是所有能够用正则表达式描述的语言。也就是，上的正则语言正则语言类恰好是语言集合 a：a 关于并、连接和Kleene星号函数的闭包。语言识别装置语言识别装置：专门为某个语言L设计的、用来回答“字符串w是L的成员吗？”这样的问题的算法。例如，识别语言L=w0,1*：w不含子串111 的装置运算如下：从左到右读字符串，每次读一个。有一个计数器，开始时为0，每当在输入串中遇到0时将它置回到0，每当遇到1时加1。如果计数器已经达到3，则停止计算并且回答“No”；如果读完整个字符串且计数器没有达到3，则停止计算并且回答“Yes”。语言识别装置和语言生成器是语言有穷说明的两种类型。本课程后续将研究两者之间的关系。（完）
展开阅读全文