复旦大学 计算机院 赵一鸣 离散数学(中文课件)5

1、4.偏序集合中的几个特殊元素定义：设(A,)是一个偏序集合, BA,若存在一个元素bB,对所有bB都有bb, 则称b是B的最大元；若都有bb, 则称b是B的最小元。特别B=A时，称b为A的最大元或最小元。例：A1=1,2,3,4,5,6,(A1,)1为A1的最小元，6为A1的最大元(A1,|)A1的最小元为1，A1的最大元无。A2=2,3,6,12,24,36,(A2,|)A2既无最小元，也无最大元。偏序集或它的子集不一定存在最小元(最大元)偏序集存在最小元(最大元)，它的子集也不一定存在最小元(最大元)定理：在(A,)中，BA，若B存在最大元(最小元)，则必唯一。证明：假设B有两个最大元a1

2、,a2,定义：设(A,)是一个偏序集合, BA,若存在一个元素bB, 且在B中不存在元素b使bb,bb,则称b是B的极大元；若B中不存在元素b使bb, bb,则称b是B的极小元。特别B=A时，称b为A的极大元(极小元)注意极大元与最大元的区别。例：A1=1,2,3,4,5,6,(A1, )1为A1的极小元，6为A1的极大元(A1,|)这些说明：极大元(极小元)不唯一最大元(最小元)必是极大元(极小元)对任何非空有限子集，极大元、极小元一定存在若子集B有最大元(最小元)，则B的极大元(极小元)唯一定义：设(A,)是一个偏序集合, BA,若存在一个元素aA, 对所有bB都有ba, 则称a是B的上界

3、；对所有bB都有 ab, 则称a是B的下界。注意最大元(最小元)与上界(下界)的区别最大元(最小元)要求最大元(最小元)B,而上界(下界)无此要求例:A2=2,3,6,12,24,36,(A2,|)P=2,3,6,B=2,3, 上界(下界)可能存在，也可能不存在。上界(下界)不一定唯一。上界(下界)可以是B中的元素，也可以不是定义：设(A,)是一个偏序集合, BA，若aA是B的上界且对B中每个上界a都有aa, 则称a为B的上确界(或称最小上界)；若aA是B的下界且对B中每个下界a都有aa,则称a为B的下确界(或称最大下界)。例:A2=2,3,6,12,24,36,(A2,|)P=2,3,6,P

4、的上界6,12,24,36，B=2.3,例:A3=6,9,36,54,(A3,|)B=6,9, 上确界(下确界)唯一上确界(下确界)可以是B中的元素，也可以不是存在上界(下界)，上确界(下确界)不一定存在。RAB,R为A到B的二元关系，DomRA。若DomR=A,且规定对每个aA,有唯一的b与之对应，即不允许出现(a,c),(a,b)R出现。满足这两条的称为函数。第三章 函数3.1 函数的基本概念一、函数的定义及其表示定义3.1：设A和B是两个任意集合, f是从A到B的二元关系。若f具有性质:(1)f的定义域Domf=A；(2)如果(a,b),(a,b)f, 则b=b。则称关系f是从A到B的函

5、数,记为f:AB,称b为a的象,a为b的原象,记为b= f(a)。f的值域记为Rf。又称f为从A到B的映射。(1)由DomRA变为DomR=A,即定义域有区别。(2)对于关系允许(a,b),(a,b)R,而函数则是不允许的除非b=b。例：设A=1,2,3,4,B=a,b,c,从A到B的关系:R1=(1,a),(2,b),(3,c),R2=(1,a),(1,b),(2,b),(3,c),(4,c),R3=(1,a),(2,b),(3,b),(4,a)DR1=1,2,3A,不是函数。DR2=1,2,3,4=A,但(1,a),(1,b)R2,故不是函数。R3是函数定义：设函数f:AB, 若存在bB，

6、使得对所有aA,有f(a)=b,则称f为常值函数。定义 3.6：设函数f:AA, 若对所有aA,有f(a)=a,则称f为A上的恒等函数,记为IA。下面讨论函数象集的运算。二、函数的象定义3.2：设函数f:AB,XA,YB,定义:f(X)=f(a)|aX，称f(X)是在f 下X的象。f -1(Y)=aA|f(a)Y,称f -1(Y)是在f下Y的原象。定理(一)：设函数f:AB, (1)设XA,则X,当且仅当f(X)(2)对每个aA, f(a)= f(a)对于a.f(a),a的象f(a).a的象 f(a)定理(二)：设函数f:AB, A1,A2为A的子集，(1)若A1A2,则f(A1) f(A2)

7、(2) f(A1A2) f(A1)f(A2)(3) f(A1A2)= f(A1)f(A2)(4) f(A1)- f(A2) f(A1-A2)要注意(2),(4)等式不一定成立证明：(3) f(A1)f (A2) f(A1A2)f(A1A2) f(A1)f (A2)因此f(A1A2)= f(A1)f(A2)(4)对任意y f(A)-f(B)，目标y f(A-B)要注意的是等式不成立定理(三)：设函数f:AB, AiA (y=1,2,n)，三、不同函数的个数下面我们来讨论集合A到集合B可以定义多少个不同的函数。从关系来讲，AB的子集都是A到B的关系，故集合A到集合B的二元关系个数是2|A|B|，而

8、根据函数定义，AB的子集不一定是A到B的函数。设|A|=m,|B|=n,A到B的函数有nm个，用BA表示A到B的函数全体所组成的集合，则|BA|=nm四、几类特殊的函数这里要介绍在函数中常要讨论的几个特殊函数：满射，内射和双射。定义3.3：(1)设函数f:AB,若Rf=B,则称f为满射或称f为到上的。(2)设函数f:AB, 若a1,a2A,a1a2有f(a1)f(a2),则称f为内射或称f为一对一的。(3)设函数f:AB, 若f是满射,且内射, 则称f为双射,或称f为一一对应的。例:设函数f1:R(实数集)C(复数集), f1(a)=i|a|; f1不是内射,不是满射。设函数f2:R(实数集)

9、C(复数集), f2(a)=ia;f2为内射,不是满射。设函数f:ZZm=0,1,m-1, f(a)=a mod m满射,不是内射。定义：设函数f、g:AB,若对任意aA,有f(a)=g(a)，则称函数f和g相等，记为f=g。例：在实数范围内，f(x)=x+1,g(x)= x(x+1)/x两个函数是否相等必须考察它们的定义域是否相同。3.2 逆函数与复合函数一、复合函数定理：设函数g:AB,f:BC,则A到C的复合关系gf是A到C的函数。证明：先证明对A中任一元素,都有C中元素与之对应,然后证明对A中每个元素,都只对应C中一个元素(1)对A中任一元素a,都有C中元素与之对应(2)对A中每个元素

10、,都只对应C中一个元素即证明对A中元素a，若有x,yC，使得(a,x)gf，(a,y)gf，必有x=y。定义3.5：设函数g:AB,f:BC,称复合关系gf是从A到C的复合函数,记为fg:AC。对aA,有(fg)(a)= f(g(a)。注意：这里采用复合函数习惯记法,目的是为了将变元放在函数记号的右侧，使(fg)(a)= f(g(a),所以用记号(fg)，而不用gf。例：A=1,2,3, f、g是集合A到A的函数。g=(1,2),(2,1),(3,3), f=(1,2),(2,3),(3,1)一般fggf定理3.3：设函数g:AB,f:BC,h:CD,则(hf )g=h(fg)证明：函数是特殊

11、的关系,关系的复合运算满足结合律,则函数的复合运算自然满足结合律定理 3.4：设函数g:AB,f:BC, fg: AC, 则(1)若f和g是满射,则fg是满射。(2)若f和g是内射, 则fg是内射。(3) f和g是双射, 则fg是双射。证明：(1)要证明fg满射，就是证明对C中每个元素都有A中元素与之对应。(2)所谓内射就是要证明当ab时，fg(a) fg(b)(3)f和g是双射,所以f和g当然满射, 内射，所以fg是双射。注意定理 3.4的逆是不一定成立的，请考虑原因但是fg是满射，f必定满射；fg内射，g必定内射。fg双射，则f必定满射，g必定内射。二、逆函数例:A=1,2,3,B=a,b, f:AB, f=(1,a),(2,b),(3,b)是函数，但其逆关系f-1 =(a,1),(b,2),(b,3),不符合函数的定义，不是函数。定理：设函数f:AB, 则f的逆关系是函数当且仅当f是双射。证明：(1)若f -1是函数，则f是双射(i)先证明f是满射。对于任意bB，找aA,使得(a,b) f ，(ii) f内射。若存在a1,a2A，有f(a1)= f(a2)=bB,目标证明a1=a2。(2)若f是双射，则f -1是函数分析：要证明f-1是函数即