第5章 函数 本章研究一种称为函数的特殊关系，主要涉及把一个有限集合变换成另一个有限集合的离散函数，它是高等数学与复变函数中所讨论的单值函数概念的推广，是一类应用广泛的重要函数。在一般地介绍函数的概念后，将讨论一些重要而基本的函数(如满射函数、单射函数及双射函数)、复合函数及逆函数、特征函数和模糊子集等。本章中所研究的内容，对于后续课程(如数据结构、开关理论、程序语言的设计与实现、形式语言与自动机等)以及进行科学研究都是不可缺少的工具。 5.1函数的基本概念 函数是满足某些条件的关系，即函数是关系，但关系不一定都是函数。下面给出函数的定义。 定义5.1.1设f是从集合X到集合Y的关系。如果对任意一个x∈X，都存在唯一的y∈Y，使〈x,y〉∈f，则称关系f为函数(function)或映射(mapping)，并记为f: X→Y或XfY。 如果〈x,y〉∈f，也可写成y=f(x)。 对于函数f: X→Y，如果有〈x,y〉∈f，则称x为自变量(independent variable)，y称为函数f在x处的值(value)； 或称y为在映射f下x的像(image)，称x为y的原像(preimage)。如果函数f: X→Y，则称X为f的定义域(domain)，Y称为f的陪域(codomain)； Rf是f的值域(range)，有时也用f(X)表示函数f的值域Rf，即 f(X)=Rf={y|y∈Y∧(x)(x∈X∧y=f(x))} 显然，RfY。 由定义5.1.1可知，函数f: X→Y满足下面两个性质。 (1) 全域性。函数的定义域必须是集合X，而不能是它的真子集，即Df=X。 (2) 唯一性(单值)。给定X中的任意元素x，在Y中只能有唯一的元素y，使〈x,y〉∈f，即对x∈X，若存在y,z∈Y，使得〈x,y〉∈f，〈x,z〉∈f，则必有y=z。 【例5.1.1】已知f: X→Y，其中X={x1,x2,x3,x4}，Y={y1,y2,y3,y4,y5,y6}， f={〈x1,y5〉,〈x2,y1〉,〈x3,y2〉,〈x4,y3〉}。求f的定义域、值域、陪域。 解显然f满足全域性和唯一性，因此f是函数，且其定义域为Df=X={x1,x2,x3,x4}，值域为Rf={y1,y2,y3,y5}，陪域为Y={y1,y2,y3,y4,y5,y6}，示意图如图5.1.1所示。 图5.1.1定义域、值域、陪域示意图 【例5.1.2】图5.1.2中给出了4个关系图，试判断哪些关系是函数，哪些不是函数。 图5.1.2关系图 解在图5.1.2中，因为Df1=X1，Df2=X2，且都满足唯一性，所以f1和f2是函数。f3满足全域性，即Df3=X3，但x2有两个像,即y2和y3，即f3不满足唯一性，因此f3不是函数。f4满足唯一性，但Df4X4，其中x4没有像，即不满足全域性，故f4不是函数。 【例5.1.3】判断下列关系中哪些能构成函数。 (1) f1={〈x1,x2〉|x1,x2∈N,x1+x2<10}。 (2) f2={〈x1,x2〉|x1,x2∈R,x22=x1}。 (3) f3={〈x1,x2〉|x1,x2∈N,x2为小于或等于x1的素数的个数}。 (4) f4={〈x1,x2〉|x1,x2∈R,x21=x2}。 解(1) f1={〈x1,x2〉|x1,x2∈N,x1+x2<10}不能构成函数。原因有以下两点。 ① 不满足全域性。Df={0,1,2,3,4,5,6,7,8,9}N。 ② 不满足唯一性。例如，f1(1)=1,f1(1)=2,…,f1(1)=8，即x1对应的x2可以为1，2，…，7或8等。 (2) f2={〈x1,x2〉|x1,x2∈R,x22=x1}不能构成函数。原因有以下两点。 ① 不满足全域性。Df=R+∪{0}R。 ② 不满足唯一性。一个x1对应两个不同的x2，如22=4，(-2)2=4。 (3) f3={〈x1,x2〉|x1,x2∈N,x2为小于或等于x1的素数的个数}能构成函数。显然满足全域性； 因为对于任意一个自然数x1，小于x1的素数个数是唯一的，所以也满足唯一性。 举例如下。 因为小于或等于0的素数不存在，所以f3(0)=0。 因为小于或等于1的素数不存在，所以f3(1)=0。 因为小于或等于2的素数只有2，所以f3(2)=1。 因为小于或等于3的素数有2和3，所以f3(3)=2。 因为小于或等于4的素数有2和3，所以f3(4)=2。 (4) 因为f4满足全域性和唯一性，所以f4是函数。 【例5.1.4】设N是自然数集合，函数S： N→N定义成S(n)＝n+1。显然 S(0)=1,S(1)=2,S(2)=3,… 它满足全域性和唯一性，所以S是一个函数。 定义5.1.2设X和Y是两个集合，并且有X′X。于是，任何函数f: X′→Y都称为从X到Y的偏函数(partial function)。对于任何元素x∈X-X′，没有定义f(x)的值。 显然，如果f是从X到Y的函数，则f也必然是从X到Y的偏函数； 但因为偏函数不一定满足函数的全域性，所以偏函数却不一定是函数。为了强调函数的全域性，故把函数称为全函数(total function)。有了全函数的概念，则偏函数的意义就更明显了。但是，由于主要研究的是全函数，故仍把全函数简称为函数。 【例5.1.5】设R为实数集合，R+为正实数集合，R+R，令f: R+→R，使f(x)=x (取正值)。因为在R-R+内，f是没有定义的，所以f是从R到R的偏函数。但f是从R+到R的函数。 因为一个关系是可以用关系图和关系矩阵来表示的，而函数是一种特殊的关系，所以函数也可以用图和矩阵来表示。 函数f的图记为Gf： 如果f(x)=y，则从结点x有一条到结点y的有向边。 函数f的关系矩阵记为Mf： 由函数的全域性和唯一性知，矩阵Mf中的每一行有且仅有一个元素为“1”。于是，可以将Mf进行简化，简化后的Mf是一个两列矩阵，第一列由定义域Df中的元素组成，第二列由值域Rf中的元素组成。 【例5.1.6】设X={a,b,c,d,e}，Y={α,β,γ,δ,ε}，f={〈a,α〉,〈b,γ〉,〈c,γ〉,〈d,ε〉,〈e,β〉}。 求Df，Rf，Gf，Mf和简化的Mf。 解Df=X={a,b,c,d,e}； Rf={α,β,γ,ε}Y； Gf如图5.1.3所示。 图5.1.3Gf图 函数f的关系矩阵为 αβγδεMf=abcde1000000100001000000101000 简化的关系矩阵为 Mf=aαbγcγdεeβ 众所周知，笛卡儿乘积X×Y的任意一个子集都是从X到Y的关系。但笛卡儿乘积的子集不一定能构成从X到Y的函数。 【例5.1.7】已知X={a,b,c}，Y={0,1}，则存在多少个从X到Y的二元关系?存在多少个从X到Y的函数? 解X×Y={〈a,0〉,〈a,1〉,〈b,0〉,〈b,1〉,〈c,0〉,〈c,1〉}，|X×Y|=6，关系是笛卡儿乘积的子集，而|ρ(X×Y)|=26，所以存在26个从X到Y的二元关系。但是函数是满足全域性和唯一性的二元关系，其中只有|Y||X|=23个关系可以构成函数，如图5.1.4所示。 图5.1.4从X到Y的所有函数 即这些函数有 f0＝{〈a,0〉，〈b,0〉，〈c,0〉}，f1＝{〈a,0〉，〈b,0〉，〈c,1〉}， f2＝{〈a,0〉，〈b,1〉，〈c,0〉}，f3＝{〈a,1〉，〈b,0〉，〈c,0〉}， f4＝{〈a,0〉，〈b,1〉，〈c,1〉}，f5＝{〈a,1〉，〈b,0〉，〈c,1〉}， f6＝{〈a,1〉，〈b,1〉，〈c,0〉}，f7＝{〈a,1〉，〈b,1〉，〈c,1〉}。 由此可以看出构成函数的一个规律： 因为函数的定义域是X，而X中的每个元素有且仅有一个像，故以Y中某一元素为像的序偶一定有|X|个； 其次X中任一元素都可以从Y中任选一元素作它的像，所以每个元素的像有|Y|种选法，因此可以构成|Y||X|个函数。 如果令YX表示从X到Y的所有函数组成的集合，即 YX={f|f: X→Y} 以|YX|表示这些函数的数目，且令|X|=m，|Y|=n，则|YX|=nm。如上例中|X|=3，|Y|=2，则|YX|=23=8(种)。 有了函数的概念后，再来了解几种重要的特殊函数，这些特殊函数对研究某些具体领域中的实际问题是十分有用的。 定义5.1.3给定函数f: X→Y。 (i) 如果f(X)=Rf=Y，则称f是满射的(surjective)或满射函数(surjection)。 (ii) 对任意x1、x2∈X，如果x1≠x2f(x1)≠f(x2)(或f(x1)=f(x2)x1=x2)，则称f是单射的(injective)或单射函数(injection)。 (iii) 如果f既是单射的又是满射的，则称f为双射的(bijective)或双射函数(bijection)。 当X和Y都是有限集合时，如果f是满射的，必有|X|≥|Y|； 如果f是单射的，必有|X|≤|Y|。如果f是双射函数，必有|X|=|Y|。 定义5.1.4函数IX: X→X，对于所有的x∈X，都有IX(x)=x，则称IX为恒等函数(identity function)。 由定义可知，恒等函数一定是双射函数。 【例5.1.8】设f1,f2,f3,f4为以下定义的从R到R的函数，问它们各是什么函数？ (1) f1(x)=x2。 (2) f2(x)=2x。 (3) f3(x)=x3。 (4) f4(x)=x3-x2。 解(1) 因为f1(x)=f1(-x)=x2，所以f1不是单射函数； 因为Rf1R，即Rf1≠R，所以f1不是满射函数。 (2) 显然f2是单射函数； 因为Rf2R，即Rf2≠R，所以f2不是满射函数。 (3) 显然f3是满射函数，也是单射函数，所以f3是双射函数。 (4) 显然f4(x)是满射函数，不是单射函数，如f4(1)=0，f4(0)=0。 下面给出几个常用的函数。 【例5.1.9】设f: X→Y，如果存在C∈Y，使得对所有的x∈X都有f(x)=C，则称f是常数函数(constant function)，记为f(x)≡C。 【例5.1.10】设f: R→R，对任意x1,x2∈R，如果x1f(x2)，就称f为严格单调递减的(strictly decreasing)。它们统称为单调函数。 习题5.1 (1) 设A={a,b,c}，B＝{1,2,3}，试说明下列从A到B的二元关系中，哪些能构成函数。 ① f1={〈a,1〉,〈a,2〉,〈b,1〉,〈c,3〉}。 ② f2={〈a,1〉,〈b,1〉,〈c,1〉}。 ③ f3={〈a,2〉,〈c,3〉}。 ④ f4={〈a,3〉,〈b,2〉,〈c,3〉,〈b,3〉}。 ⑤ f5={〈a,2〉,〈b,1〉,〈b,2〉}。 (2) 设I为整数集合，I+为正整数集合，给定函数f: I→I+，且具体给定成f(i)=|2i|+2。 试求出f的值域。 (3) 设E是全集，ρ(E)是E的幂集，定义f: ρ(E)×ρ(E)→ρ(E)，且具体给定成： 对任意S1,S2∈ρ(E)，有f(〈S1,S2〉)=S1∩S2。试证明f是函数，且f的陪域与值域相等。 (4) 令X={1,2,3,4}，判定下列关系是否是从X到X的函数。若是函数，请指出它的定义域和值域。 ① f1={〈2,3〉,〈1,4〉,〈2,1〉,〈3,2〉,〈4,4〉}。 ② f2={〈3,1〉,〈4,2〉,〈1,1〉}。 ③ f3={〈2,1〉,〈3,4〉,〈1,4〉,〈2,3〉,〈4,4〉}。 ④ f4={〈2,1〉,〈3,1〉,〈1,1〉,〈4,1〉}。 (5) 设N是自然数集合，R为实数集合。下列函数中哪些是满射函数?哪些是单射函数?哪些是双射函数? ① f: N→N，f(n)=n2+2。 ② f: N→N，f(n)=n(mod 3)。 ③ f: N→N，f(n)=1,n是奇数0,n是偶数。 ④ f: N→{0,1}，f(n)=1,n是奇数0,n是偶数。 ⑤ f: N→R，f(n)=lgn。 ⑥ f: R→R，f(r)=r2+2r-15。 ⑦ f: N2→N，f(n1,n2)=nn21。 (6) 设X和Y都是有穷集合，且|X|=m，|Y|=n，则从X到Y有多少种不同的单射函数?有多少种不同的双射函数?存在单射函数和双射函数的必要条件是什么? (7) 令A={1,2,3,…,10}，找出一个从A2到A的函数，能否找到一个从A2到A的满射函数？能否找到一个从A2到A的单射函数?为什么? (8) 证明函数f: R→R，f(r)=2r-15是双射函数。 (9) 设A={a1,a2,…,an}，试证明任何从A到A的函数，如果它是单射函数，则它必是满射函数； 反之亦真。 5.2复合函数与逆函数 前面曾经指出，函数是一类特殊关系。关系有合成运算，故函数也有合成运算。下面给出函数合成运算的定义。 定义5.2.1设f: X→Y； g: Y→Z是两个函数，于是 gf={〈x,z〉|x∈X∧z∈Z∧(y)(y∈Y∧y=f(x)∧z=g(y))} 称为f和g的合成函数(composition function)，习惯上称为复合函数。 注意： 由定义可知，复合函数gf与合成关系fg实际上表示同一个集合(合成关系)。这里把符号的次序颠倒过来，并把合成函数称为复合函数，是为了与《高等数学》中复合函数的表示法取得一致。在下文中，谈及复合函数时，gf均按定义5.2.1理解。 定理5.2.1设函数f: X→Y； g: Y→Z，则复合函数gf是从X到Z的函数，并且对每个x∈X，都有(gf)(x)=g(f(x))。 证显然gf是从X到Z的关系，下面来证gf也是从X到Z的函数。 先证全域性。对于任意x∈X，因为f是函数，f满足全域性，所以存在x的像y∈Y，使〈x,y〉∈f。又因为g是函数，g也满足全域性，所以对于每个y∈Y，必有y的像z∈Z，使〈y,z〉∈g。根据复合关系的定义，由〈x,y〉∈f且〈y,z〉∈g可知，必有〈x,z〉∈gf。因此，对每个x∈X，在Z中都存在与之对应的像z，即Dgf=X。所以，gf满足全域性。 再证唯一性。假定gf中包含序偶〈x,z1〉和〈x,z2〉，由〈x,z1〉,〈x,z2〉∈gf知，必存在y1、y2∈Y，使〈x,y1〉∈f，且〈y1,z1〉∈g和〈x,y2〉∈f，且〈y2,z2〉∈g。因为f是一个函数，由唯一性知，y1=y2，记之为y，于是有〈y,z1〉,〈y,z2〉∈g。又因为g也是一个函数，也满足唯一性，所以也必有z1=z2，即对任意x∈X，只能存在唯一的z∈Z，使〈x,z〉∈gf。所以gf满足唯一性。 综上知，gf是从X到Z的函数。 令f(x)=y，g(y)=z，则(gf)(x)=z=g(y)=g(f(x))。定理得证。■ 【例5.2.1】设集合X={x1,x2,x3,x4}，Y={y1,y2,y3,y4,y5}和Z={z1,z2,z3}。给定函数f: X→Y； g: Y→Z为 f={〈x1,y2〉,〈x2,y1〉,〈x3,y3〉,〈x4,y5〉} g={〈y1,z1〉,〈y2,z2〉,〈y3,z3〉,〈y4,z3〉,〈y5,z2〉} 求复合函数gf，并给出它的图解。 解gf={〈x1,z2〉,〈x2,z1〉,〈x3,z3〉,〈x4,z2〉}。 图5.2.1给出了gf: X→Z的图解。 定理5.2.2函数的复合运算满足结合律，即如果f: X→Y，g: Y→Z，h: Z→W 都是函数，则有 h(gf)=(hg)f 证设函数f: X→Y； g: Y→Z和h: Z→W，且令f(x)=y，g(y)=z，h(z)=w，则 (h(gf))(x)=h((gf)(x))=h(g(f(x)))=h(g(y))=h(z)=w ((hg)f)(x)=(hg)(f(x))=(hg)(y)=h(g(y))=h(z)=w 再由x∈X的任意性知，定理成立。■ 复合函数满足结合律的图解表示如图5.2.2所示。 图5.2.1复合函数gf的图解 图5.2.2复合函数满足结合律 由于复合运算满足结合律，故可略去括号，即写成h(gf)=(hg)f=hgf。 【例5.2.2】设R为实数集合，对任意的x∈R，令f(x)=x+2，g(x)=2x，h(x)=3x。求gf，fg，h(gf)，(hg)f。 解 (gf)(x)=g(f(x))=g(x+2)=2(x+2) (fg)(x)=f(g(x))=f(2x)=2x+2=2(x+1) 可知 gf(x)≠fg(x) 因为 (h(gf))(x)=h((gf)(x))=h(g(f(x))) =h(g(x+2))=h(2(x+2))=6(x+2) ((hg)f)(x)=(hg)f(x)=(hg)(x+2)=h(g(x+2)) =h(2(x+2))=6(x+2) 可见 (h(gf))(x)=((hg)f)(x) 即h(gf)=(hg)f。 由例5.2.2可知，合成函数满足结合律，但是不满足交换律。 定理5.2.3设有n个函数： f1: X1→X2； f2: X2→X3； …； fn: Xn→Xn+1，则 fnfn-1…f1: X1→Xn+1 若X1=X2=…=Xn+1=X，并且f1=f2=…=fn=f，则上述复合运算可表示为 fn=ff…f: X→X 【例5.2.3】设I是整数集合，并且函数f: I→I为f(i)=2i+1。试求复合函数f3(i)。 解 f3(i)=(fff)(i)=(ff)(f(i))=(ff)(2i+1) =f(f(2i+1))=f(4i+3)=8i+7 定义5.2.2给定函数f: X→X，如果f2=f，则称f为等幂函数(idempotent function)。 【例5.2.4】设I是整数集合，Nm={0,1,2,…,m-1}，给定函数f: I→Nm，且f(i)=i(mod m)。试证明，对于n≥1都有fn=f。 注： i(mod m)表示“i除m所得的余数”，m称为模(modulus)。 证对任意i∈I，有 f2(i)=(ff)(i)=f(f(i))=f(i(mod m)) =(i(mod m))(mod m)=i(mod m)=f(i) 得f2(i)=f(i)，故f是个等幂函数，即f2=f，于是有 f3=f2f=ff=f2=f f4=f3f=ff=f2=f  fn=fn-1f=ff=f2=f 故对于所有n≥1都有fn=f，得证。 定理5.2.4设函数f: X→Y； g: Y→Z。 (i) 如果f和g都是满射函数，则gf也是满射函数。 (ii) 如果f和g都是单射函数，则gf也是单射函数。 (iii) 如果f和g都是双射函数，则gf也是双射函数。 证(i) 对任意z∈Z，因为g是满射函数，所以至少存在一个y∈Y，使g(y)=z； 又因为f是满射函数，所以对于y∈Y，至少存在一个x∈X使f(x)=y，由此得z=g(y)=g(f(x))=(gf)(x)，即〈x,z〉∈gf。由z∈Z的任意性，可知gf是满射函数。 (ii) 设x1,x2∈X且x1≠x2，因为f是单射函数，所以f(x1)≠f(x2)； 又因为f(x1),f(x2)∈Y且g是单射函数，所以g(f(x1))≠g(f(x2))。因此，当x1,x2∈X且x1≠x2时，有(gf)(x1)≠(gf)(x2)，即gf是单射函数。 (iii) 由(i)和(ii)即可证得(iii)。■ 定理5.2.5设函数f: X→Y； g: Y→Z。 (i) 如果gf是满射函数，则g必是满射函数。 (ii) 如果gf是单射函数，则f必是单射函数。 (iii) 如果gf是双射函数，则g是满射函数，f是单射函数。 证(i) 对任意z∈Z，因为gf是满射函数，所以必存在x∈X，使〈x,z〉∈gf； 又因为〈x,z〉∈gf，所以必存在y∈Y，使〈x,y〉∈f且〈y,z〉∈g。由此可得，对任意z∈Z，必存在y∈Y使z=g(y)，故g是满射函数。 (ii) 因为gf是单射函数，所以对任意x1,x2∈X且x1≠x2，有(gf)(x1)≠(gf)(x2)，即g(f(x1))≠g(f(x2))； 又因为g是函数，满足唯一性，所以由g(f(x1))≠g(f(x2))，知f(x1)≠f(x2)。因此，对任意x1,x2∈X且x1≠x2，有f(x1)≠f(x2)，即f是单射函数。 (iii) 由(i)和(ii)即可证得(iii)。■ 定理5.2.6设f: X→Y，IX是X上的恒等函数，IY是Y上的恒等函数，则 fIX=IYf=f 证设x∈X，y∈Y，则IX(x)=x，IY(y)=y，于是有 (fIX)(x)=f(IX(x))=f(x)，(IYf)(x)=IY(f(x))=f(x) 故有fIX=IYf=f成立。■ 由定理5.2.6易知，当X=Y时，有fIX=IXf=f。 给定从X到Y的关系R，其逆关系R-1一定是从Y到X的关系，即一个关系的逆关系总是存在的。但是，当把从X到Y的函数f看作关系时，其逆关系f-1是否也一定是Y到X的函数呢?下面的定理回答了这个问题。 定理5.2.7设函数f: X→Y，f的逆关系f-1是从Y到X的函数，当且仅当f是双射函数。 证(充分性)因为f是双射函数，从而是满射函数，所以对任意y∈Y，都存在x∈X，使得〈x,y〉∈f，即〈y,x〉∈f-1，故任意y∈Y=Df-1，y在f-1对应下都有像x，满足全域性； 又由f是单射函数，知对任意y∈Y，存在唯一的x∈X，使得〈x,y〉∈f，即〈y,x〉∈f-1，从而任意y∈Y=Df-1，y在f-1对应下的像x都唯一，即f-1满足唯一性。所以，f-1是从Y到X的函数(还可进一步证明f-1也是双射函数)。 (必要性) 使用反证法。如果f不是单射函数，即存在x1,x2∈X，x1≠x2，且存在y∈Y，使得〈x1,y〉∈f，〈x2,y〉∈f，即〈y,x1〉∈f-1，〈y,x2〉∈f-1，即y在f-1对应下有两个不同的像x1和x2，即f-1不满足唯一性，这和f-1是函数矛盾，所以f是单射函数。如果f不是满射函数，则存在y∈Y，在X中没有元素与之对应，即RfY，因此Df-1=RfY，所以f-1不满足全域性，这也和f-1是函数矛盾，所以f是满射函数。因此f是双射函数。■ 【例5.2.5】设函数f1: X→Y，f2: X→Z，其中X={a,b,c}，Y={1,2,3,4}，Z={1,2,3}，f1={〈a,1〉,〈b,2〉,〈c,3〉}，f2={〈a,2〉,〈b,3〉,〈c,1〉}。问f1和f2的逆关系是否为函数？ 解(方法1)对函数f1，Y中元素4没有原像，即f1不是满射函数，如图5.2.3(a)所示，从而Y中元素4在f-11对应下没有像，即f-11不满足全域性，如图5.2.3(b)所示，因此f-11不是函数。 对函数f2，f2的逆关系f-12={〈1,c〉,〈2,a〉,〈3,b〉}，如图5.2.3(d)所示，因为Z中任一元素在f-12对应下均有像，因此f-12满足全域性； 因为Z中不同元素在f-12对应下的像均不同，因此f-12满足唯一性。所以f-12是函数。 (方法2) 因为f1不是满射函数，所以f1不是双射，因此由定理5.2.7知，f-11不是函数。不难验证f2是双射函数，如图5.2.3(c)所示，因此由定理5.2.7知，f-12是函数。 图5.2.3函数映射 定义5.2.3设f: X→Y是一个双射函数，f的逆关系为一个函数，称为f的逆函数或反函数(inverse function)，并记为f-1，并称f是可逆的(invertible)。 如例5.2.5中的f1是不可逆的，f2是可逆的，且其反函数为f-12={〈1,c〉,〈2,a〉,〈3,b〉}。 定理5.2.8如果函数f:X→Y是可逆的，则有f-1f=IX、ff-1=IY。 证设x∈X、y∈Y，如果f(x)=y，则f-1(y)=x，可得 (f-1f)(x)=f-1(f(x))=f-1(y)=x 即 f-1f=IX 同理可证 (ff-1)(y)=f(f-1(y))=f(x)=y 即 ff-1=IY■ 【例5.2.6】设f: X→Y，其中X={0,1,2}，Y={a,b,c}，f={〈0,c〉,〈1,a〉,〈2,b〉}。求f-1f，ff-1。 解不难验证f是一个双射函数，因此它的反函数f-1存在，且 f-1={〈c,0〉,〈a,1〉,〈b,2〉} 从而有 (f-1f)(0)=f-1(f(0))=f-1(c)=0 (f-1f)(1)=f-1(f(1))=f-1(a)=1 (f-1f)(2)=f-1(f(2))=f-1(b)=2 即 f-1f={〈0,0〉,〈1,1〉,〈2,2〉}=IX 又因为 (ff-1)(a)=f(f-1(a))=f(1)=a (ff-1)(b)=f(f-1(b))=f(2)=b (ff-1)(c)=f(f-1(c))=f(0)=c 所以 ff-1={〈a,a〉,〈b,b〉,〈c,c〉}=IY 定理5.2.9如果f是双射函数，则(f-1)-1=f。 证由双射函数的定义知，〈x,y〉∈(f-1)-1〈y,x〉∈f-1〈x,y〉∈f。再由〈x,y〉的任意性可知，定理成立。■ 定理5.2.10已知函数f: X→Y和g: Y→Z都是可逆的，则gf也是可逆的，且 (gf)-1=f-1g-1 证首先证明gf是可逆的。因为f和g都是可逆的，由定理5.2.7知，它们必都是双射函数； 进而由定理5.2.4知，gf也为双射函数，故由定理5.2.7知，(gf)-1存在，即gf也是可逆的。 其次证明(gf)-1=f-1g-1。对任意〈z,x〉∈(gf)-1，有 〈z,x〉∈(gf)-1〈x,z〉∈gf(y)(y∈Y∧〈x,y〉∈f∧〈y,z〉∈g) (y)(y∈Y∧〈z,y〉∈g-1∧〈y,x〉∈f-1)〈z,x〉∈f-1g-1 再由〈z,x〉的任意性可知，(gf)-1=f-1g-1。■ 【例5.2.7】令FX表示从X到X的所有双射函数组成的集合，其中X={1,2,3}，求FX的所有元素及其逆函数。 解FX={f1,f2,f3,f4,f5,f6}，其中 f1={〈1,1〉,〈2,2〉,〈3,3〉}=IX，f2={〈1,1〉,〈2,3〉,〈3,2〉}， f3={〈1,2〉,〈2,1〉,〈3,3〉}， f4={〈1,3〉,〈2,2〉,〈3,1〉}， f5={〈1,2〉,〈2,3〉,〈3,1〉}， f6={〈1,3〉,〈2,1〉,〈3,2〉}。 它们的逆函数分别是f-11=f1，f-12=f2，f-13=f3，f-14=f4，f-15=f6，f-16=f5。任取fi,fj∈FX，fifj的复合运算由表5.2.1给出。 表5.2.1合成运算表  f1f2f3f4f5f6 f1f1f2f3f4f5f6 f2f2f1f6f5f4f3 f3f3f5f1f6f2f4 f4f4f6f5f1f3f2 f5f5f3f4f2f6f1 f6f6f4f2f3f1f5 例5.2.7中定义的函数对应集合X中元素的排列。3个元素的这样排列有3!＝6种，因 而有6个从X到X的函数是双射的。如果X有n个元素，那么有n!个从X到X的双射函数。 习题5.2 (1) 设函数f: X→Y； g: Y→X，则当且仅当gf=IX和fg=IY时，有g=f-1。 (2) 设函数f: R→R和g: R→R分别给定成f(x)=2x+1，g(x)=x2-2，求gf，fg，f2，(gf)f和gf2。 (3) 设f，g，h均为从N到N的函数，其中N是自然数集合，使得 f(n)=n+1，g(n)=2n，h(n)=0,n是偶数1,n是奇数 求ff，fg，gf，gh、hg和(fg)h。 (4) 设f，g和h均为从R到R的偏函数，其中f(x)=1/x，g(x)=x2，h(x)=x。 ① 求出各偏函数的定义域。 ② 求出各偏函数的像。 ③ 试求出复合函数ff，hg和gh的代数表达式。 (5) 设函数f: R→R为f(x)=x3-2。试求出其逆函数f-1。 (6) 设集合X={1,2,3,4}。试定义一个函数f： X→X，能使f≠IX，并且是单射的。 ① 求f2，f3，f-1和ff-1。 ② 能否求出另一个函数g： X→X，能使g≠IX，但是gg=IX。 5.3特征函数与模糊子集 本节讨论一种从全集E到集合{0,1}的函数，这种函数把全集E中的元素均映射到0或1。这些简单的函数能够建立元素与集合、集合与集合之间的一一对应关系。借助这些函数，可对集合进行运算，并能以此推广到表达模糊集合的概念。 定义5.3.1设E是全集，AE，函数ψA： E→{0,1}定义为 ψA(x)=1,x∈A0,xA 则称ψA为集合A的特征函数(characteristic function)或指示函数(indicator function)。 【例5.3.1】设全集E={a,b,c}，它有8个子集。 对于空集，有ψ(a)=0，ψ(b)=0，ψ(c)=0，故空集的特征函数为ψ={〈a,0〉,〈b,0〉,〈c,0〉}。 对于子集{a}，有ψ{a}(a)=1，ψ{a}(b)=0，ψ{a}(c)=0，故子集{a}的特征函数为ψ{a}={〈a,1〉,〈b,0〉,〈c,0〉}。 对于子集{a,b}，有ψ{a,b}(a)=1，ψ{a,b}(b)=1，ψ{a,b}(c)=0，故ψ{a,b}={〈a,1〉,〈b,1〉,〈c,0〉}。 同理，可求得其他子集的特征函数； 反之，若给定某集合的特征函数，也可求得该集合。例如，给定ψB={〈a,0〉,〈b,1〉,〈c,1〉}，则B={b,c}。 可见，特征函数与集合之间建立了一一对应关系。下面给出特征函数的一些基本性质。 定理5.3.1设A，B为全集E的任意两个子集，对所有x∈E，有以下性质。 (i) ψA(x)=0A=。 (ii) ψA(x)=1A=E。 (iii) ψA(x)≤ψB(x)AB。 (iv) ψA(x)=ψB(x)A=B。 (v) ψ~A(x)=1-ψA(x)。 (vi) ψA∪B(x)=ψA(x)+ψB(x)-ψA∩B(x)。 (vii) ψA∩B(x)=ψA(x)·ψB(x)。 (viii) ψA-B(x)=ψA(x)-ψA∩B(x)。 证(iii) 先证ψA(x)≤ψB(x)AB。对任意x∈E，若ψA(x)=0，则ψB(x)=0或ψB(x)=1，即若xA，则xB或x∈B； 若ψA(x)=1，则必有ψB(x)=1，即若x∈A，则必有x∈B。综上，知AB。从而有ψA(x)≤ψB(x)AB。 再证ABψA(x)≤ψB(x)。对任意x∈E，若x∈A，则由AB，知x∈B，即若ψA(x)=1，则ψB(x)=1，此时ψA(x)≤ψB(x)成立； 若xA，此时x∈B或xB，即若ψA(x)=0，则ψB(x)=1或ψB(x)=0，此时ψA(x)≤ψB(x)也成立。从而有ABψA(x)≤ψB(x)。 综上知，ψA(x)≤ψB(x)AB。 (vi) 对任意x∈E，分以下两种情况。 ① 若x∈A∪B，则ψA∪B(x)=1。x∈A∪B有以下3种可能。  如果x∈A∧x∈B，则ψA(x)=1，ψB(x)=1，ψA∩B(x)=1，此时等式成立。  如果x∈A∧xB，则ψA(x)=1，ψB(x)=0，ψA∩B(x)=0，此时等式成立。  如果xA∧x∈B，则ψA(x)=0，ψB(x)=1，ψA∩B(x)=0，此时等式成立。 ② 若xA∪B，则ψA∪B(x)=0。由xA∪B知xA∧xB，即xA∩B，因此ψA(x)=0，ψB(x)=0，ψA∩B(x)=0，此时等式也成立。 综上知，ψA∪B(x)=ψA(x)+ψB(x)-ψA∩B(x)。 其余的证明类似，留作练习。■ 【例5.3.2】证明： ~(~A)=A。 证任意x∈E，由定理5.3.1(v)，得 ψ~(~A)(x)=1-ψ~A(x)=1-(1-ψA(x))=ψA(x) 因此由定理5.3.1(iv)，知~(~A)=A成立。 【例5.3.3】证明： A∩(B∪C)=(A∩B)∪(A∩C)。 证任意x∈E，由定理5.3.1(vii)和(vi)，得 ψA∩(B∪C)(x)=ψA(x)·ψB∪C(x) =ψA(x)·(ψB(x)+ψC(x)-ψB∩C(x)) =ψA(x)·ψB(x)+ψA(x)·ψC(x)-ψA(x)·ψB∩C(x) =ψA∩B(x)+ψA∩C(x)-ψA∩(B∩C)(x) =ψA∩B(x)+ψA∩C(x)-ψ(A∩B)∩(A∩C)(x) =ψ(A∩B)∪(A∩C)(x) 因此由定理5.3.1(iv)，知A∩(B∪C)=(A∩B)∪(A∩C)。 特征函数不仅可用来描述集合、集合间的关系，而且还可以用来描述集合的运算。例如，设E为全集，E的子集A，B，C的特征函数分别是ψA，ψB，ψC,则： C=A∪B当且仅当对任意x∈E，有ψC(x)=max{ψA(x),ψB(x)}； C=A∩B当且仅当对任意x∈E，有ψC(x)=min{ψA(x),ψB(x)}； C=A-B当且仅当对任意x∈E，有ψC(x)=ψA(x)-ψA∩B(x)；  至此，讨论过的所有集合都具有一个最显著的共同点： 当给定某一集合时，可用3.1节中给出的3种方法(枚举法、部分列举法、构造法)及特征函数对该集合中所含元素给予直观、确切的描述，以便能够明确判断出某一元素属于或不属于该集合。然而，在自然界和人类社会中遇到的许多事物在分类形成“集合”时，多数情形下却难以清楚明确地规定出能够判断作为对象的事物是否属于或不属于某个“集合”的若干准则，如高和矮、美与丑、老年和中年等都没有绝对分明的界限。针对这样的客观事实，1965年，数学家卢菲特·阿利亚斯卡·扎德(Lotfi Aliasker Zadeh)发表了关于模糊集(fuzzy set)的开创性论文，由此创立了模糊集合论。模糊集合可以看作第3章学过的集合的推广，这也是上文中的集合加上引号的原因。 隶属函数是模糊集合论中的基本概念之一，它实际上是特征函数的推广。这里只对模糊集合论的最基础知识给予介绍，即模糊集的概念及其运算和模糊关系。 设E={x1,x2,…,xn}，将E的任一子集A表示为{〈x1,ψA(x1)〉,〈x2,ψA(x2)〉,…,〈xn,ψA(xn)〉}， 其中 ψA(xi)=1,xi∈A0,xiA 如果将ψA(xi)的取值范围不仅局限于0和1，而是取0和1之间的任何数(包括0和1)，例如 A～={〈x1,0.2〉,〈x2,0〉,〈x3,0.3〉,〈x4,1〉,〈x5,0.8〉} 那么，A～可做以下理解： 它表示x1属于A～的可能性小，x2不属于A～，x3属于A～的可能性也很小，x4属于A～，x5属于A～的可能性较大(或基本上属于A～)。这样的一个集合A～就是一个模糊子集，其中0.2，0.3，0.8，…分别表示对应元素属于该集合A～的程度。下面给出它的一般化定义。 定义5.3.2设E为全集，M为闭区间［0,1］，AE。建立函数 μA～: E→M 则称μA～为隶属函数(membership function)，子集A～称为μA～所表示特征的模糊子集(fuzzy subset)，E称为μA～所决定的论域(universe of discourse)。对于元素x∈E，μA～(x)称为x属于模糊子集A～的程度或隶属度(membership degree)。 μA～(x)靠近1，表示x属于A～的程度高； μA～(x)靠近0，表示x属于A～的程度低。 注： 当M={0,1}时，隶属函数就变为特征函数了，而模糊子集A～即为通常意义上的集合。 【例5.3.4】令A～表示“比0大得多的实数”，这就是一个模糊子集，且此时描述A～的隶属函数显然具有主观意识。例如，可令 μA～(x)=11+100x2，x>00,x≤0,x∈R 定义5.3.3设E为全集，μA～，μB～，μC～分别为模糊子集A～，B～，C～的隶属函数，任意x∈E，有： (i) 若μA～(x)=μB～(x)，则称A～与B～相等(equal)，记为A～=B～。 (ii) 若μA～(x)=0，则称A～为空集(empty)，记为A～=。 (iii) 若μA～(x)≤μB～(x)，则称A～为B～的子集(subset)，记为A～B～。 (iv) 若μC～(x)=max{μA～(x),μB～(x)}，称C～为A～与B～的并集(union)，记为C～=A～∪B～。 (v) 若μC～(x)=min{μA～(x),μB～(x)}，称C～为A～与B～的交集(intersection)，记为C～=A～∩B～。 若min{μA～(x),μB～(x)}=0，称A～与B～不相交(disjoint)，记为A～∩B～=。 (vi) 由μ~A～(x)=1-μA～(x)表示特征的模糊子集，~A～称为A～的补集(complement)。 【例5.3.5】设E为某高校全体学生，A～表示“身材特别高的人”的模糊子集，B～表示“身材高的人”的模糊子集，则有A～B～。 【例5.3.6】令E={a,b,c,d,e}，给定子集A～的隶属函数μA～为 μA～(a)=1，μA～(b)=0.9，μA～(c)=0.4，μA～(d)=0.2，μA～(e)=0 则可表示为 A～={〈a,1〉,〈b,0.9〉,〈c,0.4〉,〈d,0.2〉,〈e,0〉} 也可采用扎德记法来表示A～为 A～=1/a+0.9/b+0.4/c+0.2/d+0/e 注意上式右端不是分式求和，这里分母位置放的是全集E中的所有元素，分子位置放的是元素相应的隶属程度。 【例5.3.7】设E={a,b,c,d,e}，A～和B～为E上的两个模糊子集(扎德记法)，其中 A～=0.2/a+0.3/b+0.5/c+0.8/d+0.1/e B～=0.1/a+0.7/b+0.4/c+0.1/d+0.9/e 试求A～∪B～，A～∩B～，~A～，~B～，A～∪~A～和A～∩~A～。 解A～∪B～=0.2/a+0.7/b+0.5/c+0.8/d+0.9/e A～∩B～=0.1/a+0.3/b+0.4/c+0.1/d+0.1/e ~A～=0.8/a+0.7/b+0.5/c+0.2/d+0.9/e ~B～=0.9/a+0.3/b+0.6/c+0.9/d+0.1/e A～∪~A～=0.8/a+0.7/b+0.5/c+0.8/d+0.9/e A～∩~A～=0.2/a+0.3/b+0.5/c+0.2/d+0.1/e 可见，A～∪~A～≠E，A～∩~A～≠。 模糊集合的包含关系、运算的基本性质如下。 定理5.3.2设A～，B～，C～为任意3个模糊子集，则下列结论成立。 (1) 自反性： A～A～。 (2) 反对称性： 如果A～B～，B～A～，则A～=B～。 (3) 传递性： 如果A～B～，B～C～，则A～C～。 (4) 等幂律： A～∪A～=A～，A～∩A～=A～。 (5) 交换律： A～∪B～=B～∪A～，A～∩B～=B～∩A～。 (6) 结合律： (A～∪B～)∪C～=A～∪(B～∪C～)； (A～∩B～)∩C～=A～∩(B～∩C～)。 (7) 吸收律： A～∩(A～∪B～)=A～； A～∪(A～∩B～)=A～。 (8) 分配律： A～∩(B～∪C～)=(A～∩B～)∪(A～∩C～)； A～∪(B～∩C～)=(A～∪B～)∩(A～∪C～)。 (9) 双重否定律： ~(~A～)=A～。 (10) 德·摩根律： ~(A～∪B～)=~A～∩~B～； ~(A～∩B～)=~A～∪~B～。 (11) 同一律： A～∪=A～； A～∩E=A～。 (12) 零律： A～∪E=E； A～∩=。 证这里仅证明(5)和(9)，其余的请读者自行完成。 (5) 任意x∈E，都有 μA～∪B～ (x)=max{ μA～(x), μB～(x)}=max{ μB～(x), μA～(x)}= μB～∪A～(x) μA～∩B～ (x)=min{ μA～(x), μB～(x)}=min{ μB～(x), μA～(x)}= μB～∩A～(x) 故由模糊子集相等的定义(定义5.3.3(i))，得A～∪B～=B～∪A～，A～∩B～=B～∩A～。 (9) 任意x∈E，都有 μ ~(~A～)(x)=1- μ ~A～(x)=1-［1- μA～(x)］=μA～(x) 故由模糊子集相等的定义(定义5.3.3(i))，得~(~A～)=A～。■ 注意，由例5.3.7可知，A～∪~A～≠E，A～∩~A～≠，即一般来说模糊子集不满足补余律，这一点与在3.2节中学习的经典集合的运算性质不同。 定义5.3.4笛卡儿乘积A1×A2×…×An的子集R～称为一个模糊关系(fuzzy relation)，其中R～的隶属函数为 μR～(x1,x2,…,xn)∈［0,1］ 其中xi∈Ai(i=1,2,…,n)。特别是，当n=2，A1=A2=A时，称R～为A上的二元模糊关系(binary fuzzy relation)。 显然，模糊关系R～也是用隶属函数μR～来描述的，μR～(xi,xj)的值接近于1,表示xi和xj有R～关系的程度大； μR～(xi,xj)的值接近于0，表示xi和xj有R～关系的程度小。 【例5.3.8】设A＝{全体汽车}，定义A的关系R～为： 对任意x,y∈A，〈x,y〉∈R～当且仅当x比y好，显然R～就是一个模糊关系； 又如设A＝{全体中国人}，〈x,y〉∈R～当且仅当x和y相像，显然R～也是一个模糊关系。 【例5.3.9】设R为实数集合，R上的模糊关系S~的隶属函数μS~定义为 μS~(x,y)=0,x≤y1/(1+100/(x-y)2),x>y 同前面讨论过的关系一样，模糊关系也可用关系图和关系矩阵来表示，并且还可定义模糊关系的逆关系、模糊关系的复合运算等，在此不做更深入的讨论。值得一提的是，模糊的概念已经应用到了自然科学与社会科学的许多方面，目前已形成了模糊拓扑、模糊概率论、模糊最优化、模糊逻辑与模糊推理等内容，并在气象、地震、模糊识别与人工智能、故障诊断、信息检索、医疗诊断、机器人等方面都有许多实际的应用和研究。 习题5.3 (1) 利用特征函数的性质证明下列集合恒等式。 ① (A∩B)∩C=A∩(B∩C)。 ② A∩(A∪B)=A。 ③ A∩(A-B)=A-B。 ④ A-(B∩C)=(A-B)∪(A-C)。 (2) 用特征函数表示下列各式成立的充要条件。 ① (A-B)∪(A-C)=A。 ② AB=。 ③ AB=A。 ④ A∩B=A∪B。 (3) 设A～，B～是E上的两个模糊子集，它们的并集A～∪B～和交集A～∩B～都仍然是模糊子集。试证明模糊子集的∪和∩运算均满足等幂律、结合律、吸收律、分配律和德·摩根律。 (4) 设E={a,b,c,d,e}，给定E上的两个模糊子集A～和B～为 A～={〈a,0.2〉,〈b,0.3〉,〈c,0.5〉,〈d,0.8〉,〈e,0.1〉} B～={〈a,0.1〉,〈b,0.7〉,〈c,0.4〉,〈d,0.1〉,〈e,0.9〉} 求A～∪B～，A～∩B～，~A～ 和~B～。 5.4集合的基数 在抽象地研究集合时(即对集合中元素的性质不加考虑时)，一个集合中元素的多少是一个极其重要的属性。我们经常要回答一个集合有多大，两个集合哪个大、哪个小?这便是集合的大小与比较问题，而基数是度量一个集合“大小”的唯一标志。对于有限集合来说，其大小与比较问题总是可以实现的。问题是对于两个无限集合S1和S2，是否还可以比较它们的大小呢？这正是本节所要研究的问题。 众所周知，一个无限集合中含有无穷多个元素。显然，对于无限集来说，“元素个数”这个概念是完全没有意义的，也不可能再以元素个数的大小来度量两个无限集合的大小。乔治·康托尔(George Cantor)系统地研究了两个无限集合数目相等的特征，提出了一一对应的概念，把两个集合能否建立一一对应关系作为它们数目是否相同的标准。为此，首先引入“势”(cardinality)的概念。 定义5.4.1如果集合A与B的元素之间存在一个双射函数f: A→B，则称A与B具有相同的基数，或称A与B等势(equinumerous)，记为A~B。 因为对于有限集合来说，A与B元素个数相同的充要条件是它们之间存在一个双射函数，因此两个集合“具有相同的基数”是有限集合的“具有同样多个元素”这一概念的推广。 【例5.4.1】设正整数的平方数集合S1={1,4,9,16,…}，正整数集合S2={1,2,3,4,…}，令函数f: S2→S1，其中f(n)=n2,n∈S2。显然在定义域S2上f是个双射函数，即得S1~S2。 【例5.4.2】设S1是开区间(0,1)上所有实数构成的集合，S2是半轴(0,+∞)上所有实数构成的集合，则S1~S2。 证令f: S1→S2，其中f(x)=tanπ2x，x∈(0,1)。显然f是从(0,1)到(0,+∞)的双射，即得S1~S2。 对于以上两例，注意到S1~S2，说明它们具有相同的基数，另外S1又是S2的一个真子集。此例揭示了一个极其重要的事实，即对于无限集合来说，它可以和它的一个真子集一一对应，这是有限集做不到的。这个现象说明了无限集与有限集之间的一个重要区别。 定理5.4.1在集合族上的等势关系是一个等价关系。 证设S为集合族，则 对任意A∈S，必有A~A，即等势关系具有自反性； 对任意A,B∈S，若A~B，必有B~A，即等势关系具有对称性； 对任意A,B,C∈S，若A~B，B~C，必有A~C，即等势关系具有传递性。 综上知，结论成立。■ 定义5.4.2与自然数集合N等势的任意集合称为可数集合(countably infinite set)，可数集合的基数记为0，读做“阿列夫(Aleph)零”。 例如，无穷集合A={1,4,9,…,n2,…}，B={1,8,27,…,n3,…}，C=1,12,13,…,1n,…均为可数集合，如果分别令它们的基数为|A|，|B|，|C|，则有|A|=|B|=|C|=0。 定理5.4.2A为可数集合的充要条件是A可以排成无穷序列 A={a1,a2,a3,…,an,…} 的形式。 证若A可排成上述无穷序列形式，可令函数f: N→A，且给定成f(n)=an+1,n∈N，显然f是个双射函数，故A是可数集合。 反之，若A为可数集，那么存在双射函数f: N→A，故A={f(0),f(1),f(2),…}，令an+1=f(n)，则有A={a1,a2,a3,…,an,…}。定理得证。■ 定理5.4.3任一无限集，必含有可数子集。 证令A为一无限集，从A中取一元素a1，因为A是无限的，A-{a1}非空，所以从A-{a1}中可取元素a2且a1≠a2，得a1,a2； 又因为A-{a1,a2}非空，所以可从其中取元素a3且a1≠a3，a2≠a3，得a1,a2,a3。如此继续下去，就得到A的一个无穷序列a1,a2,a3,…,an,…，且它们彼此互异，如果令 A*={a1,a2,a3,…,an,…} 显然A*A，且A*是个可数集。■ 定理5.4.3说明，可数集合的基数是无限集合的基数中最小者。 定理5.4.4任一无限集，必与它的某个真子集等势。 证设M为任一无限集，由定理5.4.3知，M必有一个可数子集M*={a1,a2,a3,…}，令B=M-M*，则M-{a1}是M的一个真子集。令函数f: M→M-{a1}，且给定成 f(ai)=ai+1,ai∈M*,i=1,2,3,… f(b)=b,b∈B 则f是M与M-{a1}间的一个双射函数，故定理得证。■ 这一定理标志了无限集的特征，因此也可用它作为无限集的定义，以此来判别一个集合是有限集还是无限集。下面给出可数集合的一些主要性质(定理5.4.5~定理5.4.8)。 定理5.4.5可数集合的任意一个无限子集也是可数的。 证设A是可数集合，A1是A的一个无限真子集。因为A可数，所以A中的元素可排列成a0,a1,a2,…,an,…。现在从a0开始向右逐个检查，把那些不属于A1的元素从序列中删除，剩下的元素形成一个新的序列，并将其重新编号为 ai0,ai1,ai2,…,ain,… 可得A1={ai0,ai1,ai2,…,ain,…}，令f(n)=ain,n∈N，则f是从N到A1的双射函数，故A1是可数的。■ 定理5.4.6若A是可数集合，B是有限集合，且A∩B=，则A∪B也是可数集合。 证因为A是可数集合，所以A中元素可排成无穷序列形式 A={a1,a2,a3,…} 设B中有n个元素，即B={b1,b2,…,bn}，则 A∪B={b1,b2,…,bn,a1,a2,a3,…} 可见，A∪B可排成无穷序列形式，因而由定理5.4.2知，A∪B是可数集合。■ 定理5.4.7若A、B都是可数集合，且A∩B=，则A∪B也是可数集合。 证设A={a1,a2,a3,…}，B={b1,b2,b3,…}，则 A∪B={a1,b1,a2,b2,a3,b3,…} 因此由定理5.4.2知，A∪B可数。■ 推论1若A是可数集合，B是可数集合或有限集合，则A∪B是可数集合。 证令C=B-A∩B，则A∩C=，A∪B=A∪C。 如果B是可数集合，此时若C是有限集合，由定理5.4.6知，A∪C是可数集合，即A∪B是可数集合； 若C是可数集合，由定理5.4.7知，A∪C是可数集合，即A∪B是可数集合。 如果B是有限集合，则C是有限集，由定理5.4.6知，A∪C是可数集合，即A∪B是可数集合。 综上可知，A∪B可数。■ 【例5.4.3】证明： 整数集合I={…,-2,-1,0,1,2,…}是可数集合。 证显然，正整数集合I+={1,2,3,…}和负整数集合I-={-1,-2,-3,…}都是可数集合，由定理5.4.7知I+∪I-是可数集合，再由定理5.4.6知I=I+∪I-∪{0}也是可数集合。 定理5.4.8设Ai(i=1,2,3,…)都是可数集合，Ai∩Aj=(i≠j)，则∪+∞i=1Ai也是可数集合。 证因为Ai(i=1,2,3,…)都是可数集合，所以可设 A1={a11,a12,a13,…,a1n,…} A2={a21,a22,a23,…,a2n,…} A3={a31,a32,a33,…,a3n,…}  图5.4.1A中元素的排列 令A=A1∪A2∪A3∪…，A中元素的排列如图5.4.1所示。 于是得 A={a11,a12,a21,a31,a22,a13,a14,a23,…} 显然，A中元素可以无穷序列方式排列，故A是可数集合，即∪+∞i=1Ai是可数集合。■ 推论2设Ai(i=1,2,3,…)都是可数集合，则∪+∞i=1Ai也是可数集合。 证令C1=A1，Ci=Ai-Ai∩∪i-1j=1Aj(i≥2)，则Ci是有限集合或可数集合，且Ci∩Cj=(i≠j)。但∪+∞i=1Ai=∪+∞i=1Ci，故∪+∞i=1Ai是可数集合。■ 【例5.4.4】证明： 有理数集合Q是可数集合。 证设Ai=1i,2i,3i,…(i=1,2,3,…)，则Ai是可数的，于是由推论2可知所有正有理数组成的集合Q+=∪+∞i=1Ai可数。同理，可证所有负有理数集合Q-可数。再由定理5.4.6和定理5.4.7可知，全体有理数集Q=Q+∪Q-∪{0}是可数的。 至此，大家或许会想，是否任意两个无限集都可以使之一一对应呢?假如这样引入“势”的概念就没有什么意义了。另外，由例5.4.3可知，有理数集合是无限集合，同时它也是个可数集合。是否任意无限集合都是可数集合呢？下面介绍几个定理。 定理5.4.9集合［0,1］是不可数的。 证假设［0,1］是可数的，则其所有元素可排成下列无穷序列形式，即 a1,a2,a3,a4,a5,… 任取x∈［0,1］，将其表示成无穷小数形式ai=0.y1y2y3…，其中yi∈{0,1,2,…,9} (如0.2可表示为0.1999…，0.123可表示为0.122 999…)。于是上述序列可表示为 a1=0.a11a12a13…a1n… a2=0.a21a22a23…a2n… a3=0.a31a32a33…a3n…  现在构造一个无穷小数q，其形式为0.q1q2q3…，使 qj=1,ajj≠12,ajj=1j=1,2,3,… 则q∈［0,1］且与所有的ai(i=1,2,3,…)均不相同，这说明q不包括在上述序列之中，与题设矛盾，所以［0,1］是不可数的。■ 把集合［0,1］的基数记为1，读为“阿列夫1”。显然1≠0，后面还将证明1>0，常称1为连续统(continuum)的势。 推论3开区间(0,1)的基数也是1。 证令f: ［0,1］→(0,1)，且给定成 f(x)=12,x=0 1n+2,x=1nn=1,2,3,… x,其他 显然，f是［0,1］到(0,1)的一个双射函数，从而［0,1］与(0,1)等势，故基数相同。■ 定理5.4.10全体实数组成的集合R是不可数的，并且它的基数就是1。 证令f: (0,1)→(-∞,+∞)，且给定成 f(x)=tanπx-π2 显然，f是(0,1)到(-∞,+∞)的一个双射函数，从而(0,1)与(-∞,+∞)等势，故R是不可数，且基数也为1。■ 有了可数集与不可数集的基数概念后，再来讨论集合大小与比较问题。为此先给出下面的定义。 定义5.4.3设A，B是任意集合，用|A|，|B|分别表示A和B的基数。 (i) 如果存在从A到B的双射函数，则称A和B的基数相同，记为|A|=|B|。 (ii) 如果存在从A到B的单射函数，则称A的基数不大于B的基数，记为|A|≤|B|。 (iii) 如果存在从A到B的单射，但不存在从A到B的双射，则称A的基数小于B的基数，记为|A|<|B|。 前面讨论了欲证明两个集合等势，必须构造这两个集合间的双射函数，这往往是比较困难的。下面介绍一种较为简单的方法，它的基本思想是基于下面两个定理(定理5.4.11和定理5.4.12)。 定理5.4.11(策梅罗定理，Zermelo’s Theorem)设A，B为任意集合，则以下3种情况有且仅有一条成立。 (i) |A|=|B|。 (ii) |A|<|B|。 (iii) |A|>|B|。 此定理也称为基数的三歧性定理，它的证明依赖于选择公理，限于篇幅，这里不予证明。 定理5.4.12(康托尔伯恩斯坦定理，CantorBernstein Theorem)设A，B为任意集合，如果|A|≤|B|、|B|≤|A|，则|A|=|B|。 证设|A|≠|B|，则由定理5.4.11知，或者|A|<|B|，或者|B|<|A|，且只能是其中一种情况。 若|A|<|B|，则|B|<|A|不成立，且|A|≠|B|，这与|B|≤|A|矛盾。 若|B|<|A|，则|A|<|B|不成立，且|A|≠|B|，这与|A|≤|B|矛盾。 综上知，|A|=|B|。■ 这个定理为证明两个集合具有相同基数提供了更为简便的方法： 如果能够构造一个单射函数f: A→B，即说明|A|≤|B|； 如果能构造单射函数g: B→A，即有|B|≤|A|； 若上述单射函数f和g同时存在，则根据本定理即可得到|A|=|B|。 【例5.4.5】证明［0,1］与(0,1)具有相同的基数。 证构造单射函数为 f: (0,1)→［0,1］，f(x)=x,x∈(0,1) g: ［0,1］→(0,1)，g(x)=x2+14,x∈［0,1］ 再根据定理5.4.12可知，［0,1］与(0,1)具有相同的基数。 定理5.4.13设A为有限集，则|A|<0<1。 证先证明|A|<0。令|A|=n，则A~{0,1,2,…,n-1}。令函数f: {0,1,2,…,n-1}→N且给定成f(i)=i,i∈{0,1,2,…,n-1}。显然，f是个单射函数，故|A|≤0。 另外，设g为{0,1,2,…,n-1}→N的任意函数，再令 k=1+max{g(0),g(1),g(2),…,g(n-1)} 则k∈N，但g(0)≠k，g(1)≠k，…，g(n-1)≠k，于是对给定 的k∈N，在{0,1,2,…,n-1}中找不到i使g(i)=k，故g不是满射函数。再由g的任意性可知，{0,1,2,…,n-1}与N之间不存在满射函数，因此也就不存在双射函数。由此得证|A|<0。 其次证明0<1。令函数f: N→［0,1］，且给定成f(n)=1n+1，显然f是个单射函数，故有0≤1 ； 又因为N是可数集，［0,1］是不可数集，所以N与［0,1］间不存在双射函数，故0<1。 综上知，|A|<0<1。■ 定理5.4.14(康托尔定理，Cantor’s Theorem)设A为任意集合，则|A|<|ρ(A)|。 证首先证明|A|≤|ρ(A)|。定义从A到ρ(A)的函数f： 任意x∈A，f(x)={x}。显然f为一个单射，从而|A|≤|ρ(A)|。 其次证明|A|≠|ρ(A)|。若不然，假设存在从A到ρ(A)的双射函数g，使得任意x∈A，g(x)∈ρ(A)。定义集合S={x|xg(x)}，当然SA，故S∈ρ(A)。由于g为从A到ρ(A)满射函数，存在y∈A，使g(y)=S，考虑y∈S与否，可知 y∈Sy∈{x|xg(x)}yg(y)yS 即y∈S且yS同时成立，矛盾，因此从A到ρ(A)的双射函数g不存在，得|A|≠|ρ(A)|。 综上可知，|A|<|ρ(A)|。■ 这一定理表明，无论一个集合的基数多么大，还有基数比它更大的集合存在，也就是说，不可能存在一个最大基数的集合。 习题5.4 (1) 求下列集合的基数。 ① A={x|x∈N,x2=5}。 ② B={10,20,30,40,…}。 ③ C={x|x∈Q,0≤x≤1}。 (2) 构造从集合A到B的双射函数，从而说明A和B具有相同的势。 ① A=(0,1),B=(0,2)。 ② A=N,B=N×N。 ③ A=R,B=(0,+∞)。 ④ A=［0,1］,B=14,12。 第3篇〓代数系统 代数系统(algebra system)也称为代数结构或抽象代数，是近世代数研究的主要对象。它是用代数的方法从不同的研究对象中概括出一般的数学模型并研究其规律、性质和结构。可以说，近世代数的基本概念、方法和结果已成为计算机科学与工程领域中研究人员的基本工具。 本篇从研究代数运算入手，介绍代数系统的基本概念。继之介绍满足一些特殊性质的典型代数系统，如半群、群、环、域、格和布尔代数等。代数系统理论在理论物理、结构化学、计算机科学等学科中具有广泛的应用。在计算机科学中，代数系统可用于研究抽象数据结构的性质及操作； 代数系统也是程序设计语言、编码理论、信息安全等相关内容的理论基础； 作为一种特殊的代数系统，格在计算机应用逻辑与计算机自动推理中起着重要作用； 布尔代数的运算性质广泛地应用于逻辑电路设计的分析与综合。