第4章二元关系和函数课件.ppt

第四章 二元关系和函数本章主要内容:l集合的笛卡集合的笛卡尔积与二元关系与二元关系l关系的运算l关系的性质l关系的闭包l等价关系和偏序关系l函数的定义和性质l函数的复合和反函数4.1 集合的笛卡儿积与二元关系定义4.1 由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作,其中x是它的第一元素,y是它的第二元素 平面直角坐标系中点的坐标就是有序对,例如,<1,－1 >,<2,0>,(1,1), (－1,1) ,…都代表坐标系中不同的点有序对的特点：1.当xy时,2.两个有序对相等,即 ＝ 的充分必要条件是x＝u且y＝v 定义4.2 一个有序n元组(n≥3)是一个有序对,其中第一个元素是一个有序n－1元组,一个有序n元组记作,即 ＝ < , xn> 例如,空间直角坐标系中点的坐标<1,－1,3>,<2,4.5,0>等都是有序3元组n维空间中点的坐标或n维向量都是有序n元组定义4.3 设A,B为集合,用A中元素为第一元素,B中元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作A×B。

符号化表示为 A×B＝{|x∈A∧y∈B}.例如,A＝{a,b},B＝{0,1,2},则 A×B＝{,,,,,}； B×A＝{<0,a>,<0,b>, <1,a>,<1,b>,<2,a>,<2,b>}如果A中有m个元素,B中有n个元素,则A×B和B×A中都有多少个元素?mn个若A×B,则有x∈A和y∈B若A×B,则有xA或者y B. 笛卡儿积运算的性质: 1.若A,B中有一个空集,则它们的笛卡儿积是空集,即 B＝B×＝ 2.当A≠B且A,B都不是空集时,有 A×B≠B×A所以,笛卡儿积运算不适合交换律 3.当A,B,C都不是空集时,有 (A×B)×C≠A×(B×C).所以,笛卡儿积运算不适合结合律 4.笛卡儿积运算对∪或∩运算满足分配律即 A×(B∪C)＝(A×B)∪(A×C)； (B∪C)×A ＝(B×A)∪(C×A)； A×(B∩C)＝(A×B)∩(A×C)； (B∩C)×A ＝(B×A)∩(C×A)。

证明 A×(B∪C)＝(A×B)∪(A×C)证明 对于任意的, A×(B∪C) x∈A∧y∈B∪C  x∈A∧(yB∨y∈C) (x∈A∧yB)∨(x∈A∧y∈C) A×B∨∈A×C  (x,y)∈(A×B)∪(A×C). 所以 A×(B∪C)＝(A×B)∪(A×C)  例4.1 设A={1,2},求P(A)×A 解 P(A)×A ＝{,{1},{2},{1,2}}×{1,2} ＝{<,1>,<,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}例4.2 设A,B,C,D为任意集合,判断以下等式是否成立,说明为什么 (1) (A∩B)×(C∩D)＝(A×C)∩(B×D)； (2) (A∪B)×(C∪D)＝(A×C)∪(B×D)；(3) (A—B)×(C—D)＝(A×C)－(B×D)； (4) (AB) ×(CD) ＝(A×C)  (B×D)。

解.(1)成立.因为对于任意的, (A∩B)×(C∩D) xA∩B∧yC∩D xA∧xB ∧yC∧yD A×C∧ B×D (A×C)∩(B×D) (2)不成立举一反例如下：若A＝D＝,B＝C＝{1} 则有：(A∪B)×(C∪D)＝B×C＝{<1,1>},(A×C)∪(B×D)＝∪＝ (3)和(4)都不成立例4.3 设A,B,C,D为任意集合,判断以下命题的真假.(1)若AC且BD,则有A×BC×D2)若A×BC×D,则有AC且BD. 解 (1)命题为真请思考：为什么？(2)命题为假.当A＝B＝时,或者A≠且B≠时,该命题的结论是成立的但是当A和B之中仅有一个为时,结论不一定成立,例如,令A＝C＝D＝,B＝｛1｝,这时A×BC×D,但BD 定义4.4 设A1,A2, … , An是集合(n≥2),它们的n阶笛卡儿积,记作A1×A2×…×An,其中 Al×A2×…×An＝{|x1∈Al∧x2∈A2∧…xn∈An}。

例如: A={a,b},则A3={,, ,, ,, ,}作业P135l4.1 4.4(2) 4.5二元关系Relation 所谓二元关系就是在集合中两个元素之间的某种相关性.例如,甲、乙、丙三个人进行乒乓球比赛,如果任何两个人之间都要赛一场,那么共要赛三场假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙,这个结果可以记作{<乙,甲>,<甲,丙>,<乙,丙>},其中表示x胜y它表示了集合{甲,乙,丙}中元素之间的一种胜负关系. 例子.有A,B,C三个人和四项工作α,,,,已知A可以从事工作α,δ,B可以从事工作,C可以从事工作α,那么人和工作之间的对应关系可以记作 R＝＝{,,,,}这是人的集合{A,B,C}到工作的集合{α,,,}之间的关系 定义4.5 如果一个集合为空集或者它的元素都是有序对, 则称这个集合是一个二元关系,一般记作R对于二元关系R,如果∈R,则记作xRy；如果R,则记作定义4.6 设A,B为集合,A×B的任何子集所定义的二元关系称作从A到B的二元关系,特别当A＝B时,则叫做A上的二元关系。

l关系关系R A B, R is a relation from A to B. lR A A, R is a relation on A. A上有多少个不同的二元关系?|A|=n|A×A|=n2|P(A×A)|=2n2每一个子集代表一个A上的关系,共2n2个关系.对于任何集合A都有3种特殊的关系:1. 空关系 就是空集2. 全域关系EA3. 恒等关系IA 定义4.7 对任何集合A, EA＝{｜x∈A∧y∈A}＝A×A IA＝{｜x∈A}例如：A={0,1,2},则 EA＝{<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>｝ IA＝{<0,0>,<1,1>,<2,2)}常用的三种关系:1.小于等于关系 例如: 设A为实数集R的某个子集,则A上的小于等于关系定义为 LA＝{｜x,y∈A∧x≤y｝2. 整除关系设B为正整数集Z＋的某个子集,则B上的整除关系定义为 DB＝{｜x,y∈B∧xy}.例如: A={4,0.5,-1},B={1,2,3,6},则LA＝{<-1.-1>,<-1.0.5>, <-1,4>.<0.5,0.5>, <0.5,4>,<4,4>｝DB＝{<1,1>,<1,2>,<1,3>,<1,6>, <2,2>,<2,6>, <3,3>,<3,6>, <6,6>}.3.包含关系例4.4 设A＝{a,b},R是P(A)上的包含关系, R＝{|x,y∈P(A)∧xy>,则有P(A)＝{,{a},{b},A}。

R＝{<,>,<,{a}>,<,{b}>,<,A>,<{a},{a}>,<{a},A>,<{b},{b}>,< {b},A>,}.1.集合的表示 例如：设A＝{1,2,3,4}, A上的关系R＝{<1,1>,<1,2>,<2,3>,<2,4>,<4,2>} 2.关系图3.关系矩阵关系的三种表示：关系矩阵和关系图 设V是顶点的集合,E是有向边的集合,令V＝A＝{x1,x2,···,xn},如果xiRxj,则有向边∈E.那么G＝就是R的关系图设A＝{x1,x2,···,xn},R是A上的关系,则R的关系矩阵可表示为：作业P135-136l4.8(2)-(4) 本章主要内容:l集合的笛卡尔积与二元关系l关系的运算关系的运算l关系的性质l关系的闭包l等价关系和偏序关系l函数的定义和性质l函数的复合和反函数定理： 设R,S为集合A上关系,则 R∩S、R∪S、 R－S 、 RS、~R也是A上关系例：设R,S为集合A ={1,2,3}上关系, R={<1,2>,<1,3>}，S={<1,2>,<2,1>,<3,3>}，则R∩S ={<1,2>}R∪S ={<1,2>,<2,1>,<3,3>，<1,3>}R－S={<1,3>}~R=A×A-R={<1,1>,<2,2><2,1>,<2,3>,<3,1>,<3,2>,<3,3>} 4.2 关系的运算l关系R的定义域,值域和域l关系F的逆l关系F与G的合成l关系F在集合A上的限制l集合A在关系F下的象l关系R的n次幂定义4.8 关系R的定义域 domR,值域ranR和域fldR分别是 domR＝{xy(∈R)} ranR＝{y| x(∈R)} fldR＝domR∪ranR。

domR就是R的所有有序对的第一个元素构成的集合,ranR就是R的所有有序对的第二个元素构成的集合.例:实数集R上的关系S={|x,y∈R∧x2+y2=1},domS=ranS=fldS=[－1,1］.例4.5 下列关系都是整数集Z上的关系,分别求出它们的定义域和值域, (1)R1＝{｜x,y∈Z∧x≤y}；(2)R2＝{｜x,y∈Z∧x2+y2=1}；(3)R3＝{｜x,y∈Z∧y＝2x}；(4)R4＝{｜x,y∈Z∧ x＝ y=3} 解 (1) domR1＝ranR1＝Z. (2) R2＝{<0,1 >,<0,－1>,<1,0>,<－1,0>} domR2＝ranR2＝{0,1,－1}. (3) domR3＝Z ranR3＝{2z|z∈Z},即偶数集 (4) domR4＝ranR4＝{-3,3}. 从A到B的某些关系R的图解方法(不是R的关系图)1.用封闭的曲线表示R的定义域(或集合A)和值域(或集合B).2.从x到y画一个箭头,如果∈R逆、逆、 复合复合 定义4.9 设F,G为任意的关系,A为集合,则(1)F的逆记作F-1 F-1＝{|yFx}.(2)F与G的复合记作F◦G, F◦G＝{｜z(xFz∧zGy)}  例4.6 设F,G是N上的关系,其定义为 F＝{｜x,y∈N∧y＝x2 } G＝{｜x,y∈N∧y＝x＋1}。

求: G ◦ F =? F ◦ G=? G-1 =?解：1)对任何的x∈N有 F ◦ G(x)=G(F(x))=x2 +1 F ◦ G={ ｜ x,y∈N} 3) 对任何的x∈N有 G ◦ F (x)=F (G(x))=(x +1)2 G ◦ F ={ ｜ x,y∈N} l由这个例子不难看出,合成运算不是可l交换的,即对任何关系F,G,一般说来F◦G≠G◦F. 定理4.1 设F,G,H是任意的关系,则有l(3)(F◦G) ◦H＝F◦ (G◦H)l(4)l怎样证明?关系的基本运算的主要性质 定理4.2 设F,G,H为任意的关系,则有(1)F◦ (GH)=F◦GF◦H(2) (GH)◦F=G◦F  H◦F (3) F◦ (GH) F◦GF◦H(4) (GH)◦F  G◦F  H◦F怎样证明? 定义4.10 设R为A上的关系,n为自然数,则R的n次幂规定如下：R0=IAR1=R0◦R=R ◦ R0在有穷集A上给定了关系R和自然数n,求Rn的方法:l1.集合运算:依据定义l2.关系矩阵:用关系矩阵M表示关系R,计算M·M,在两个矩阵相乘时,第i行第j列的元素rij满足下式(i,j=1,2,3,4)rij = ri1 · r1j + ri2 · r2j + ri3 · r3j + ri4 · r4j这里的加法+是逻辑加,即0+0=0,0+1=1,1+0=1,1+1=13.关系图:对R的关系图G中的任何一个结点x,考虑从x出发的长为n的路径,如果路径的终点是y,则在Rn的关系图中有一条从x到y的有向边.定理4.3 设R为A上的关系,m,n是自然数,则下面的等式成立.本章主要内容:l集合的笛卡尔积与二元关系l关系的运算l关系的性关系的性质l关系的闭包l等价关系和偏序关系l函数的定义和性质l函数的复合和反函数作业P136l4.10l4.11l4.134.3 关系的性质l设R是A上的关系,R的性质主要有以下5种：l自反性l反自反性l对称性l反对称性l传递性49定定义1 设R是非空集合X上的二元关系。

若对X中的每个元素x，都有  R，则称R是X上的自反关系例例1 设X={a,b,c,d}，R={,,,,,} 由自反关系的定义知R是X上的自反关系 若R={,,,}，则R是X上的恒等关系 由此可知恒等关系一定是自反关系，但自反关系不一定是恒由此可知恒等关系一定是自反关系，但自反关系不一定是恒等关系50定定义2 设R是非空集合X上的二元关系若对X中的每个元素x，都有  R，则称R是X上的反自反关系例例2 设X={a,b,c,d}，R={,,(a,d>,} 由反自反关系的定义知R是X上的反自反关系51定定义3 设R是非空集合X上的二元关系若对于任意的x,yX，当 R 时，有 R，则称R是X上的对称关系例例1 设X={a,b,c}，R1={,} ，R2={,} ，R3=X2 由对称关系的定义知R1，R2，R3都是X上的对称关系。

例例2 设R是实数集合，S={ | xR∧yR∧x=y} 由实数的性质知，当x=y时，有y=x，由对称关系的定义知S是R上的对称关系推而广之，凡是相等关系都是对称关系52定定义4 设R是非空集合X上的二元关系若对于任意的x,yX，当 R 且 x≠ y时，有  R ，则称R是X上的反对称关系例例1 设R是实数集合，S={ | xR∧yR∧x≤y} 由实数的性质知，当x≤y且 y≤x时，有x=y，由反对称关系的定义知S是R上的反对称关系53定定义5 设R是非空集合X上的二元关系若对于任意的x,y,zX，当 R 且 R 时，有 R ，则称R是X上的传递关系例例1 设X={a,b,c,d}，R={,,,,,} 由传递关系的定义知R是X上的传递关系例例2 设X是平面上直线的集合，R={ | xX∧yX∧x∥y} 由平面几何的知识知，若x∥y 且y∥z，则 x∥z。

由传递关系的定义知R是X上的传递关系例例3 相等关系是传递关系l全关系X2是自反的、对称的、传递的l幺关系I 是自反的、对称的、反对称的、传递的l空关系是反自反的、对称的、反对称的、传递的 判断下列关系的性质l集合A上的全域关系:自反的、对称的和传递的l恒等关系自反的、对称的和传递的.l整除关系自反的、反对称的和传递的l小于等于关系自反的、反对称的和传递的l幂集上的包含关系自反的、反对称的和传递的l设A为非空集合:l1.A上的关系可以是①自反的, ②反自反的,或者③既不是自反的也不是反自反的. l例如:Q={1,2,3},令lR={<1,1>,<2,2>,<3,3>,<1,2>} IQ  RlR={<2,3>,<3,2>} IQR=lR={<1,1>,<2,2>} IQR≠且IQRl2. A上的关系可以是①对称的, ②反对称的,或者③既是对称的又是反对称的, ④既不是对称的也不是反对称的. l例如:Q={1,2,3},令lR={<1,2>,<2,1>,<3,3>} R-1=RlR={<1,2>,<1,3>} R R-1  IQ lR={<1,1>} R  IQ lR= {<1,2>,<2,1>,<1,3>}lR◦R R是什么关系? 例4.9 试判断图4.5中关系的性质。

设R1,R2是A上的关系,如果经过某种运算后仍保持原来的性质,则在相对应的格内划√,否则划×例：设R1,R2为A上的对称关系,证明R1∩R2也是A上的对称关系证明：对于任意的  R1∩R2  R1   R2  R1  R2  R1 R2所以, R1R2在A上是对称的例: R1 , R2 是A上的反对称关系, A={x1, x2}, R1 ={< x1, x2 >}, R2 ={< x2, x1 >},R1∪ R2 ={< x1, x2 >, < x2, x1 >}不是A上的反对称关系.作业l4.7l 4.14l 4.17l 4.18l4.20l4.22l4.23l4.25本章主要内容:l集合的笛卡尔积与二元关系l关系的运算l关系的性质l关系的关系的闭包包l等价关系和偏序关系l函数的定义和性质l函数的复合和反函数634.4 关系的闭包定义4.11 设R是非空集合A上的关系,R的自反闭包<对称闭包或传递闭包)是A上的关系R’,且R’满足以下条件:(1)R’是自反的(对称的或传递的)；(2)RR’；(3)对A上的任何包含R的自反关系(对称或传递关系)R”都有R’  R”.一般将R的自反reflexive闭包记作r(R),对称symmetric闭包记作s(R),传递transitive闭包记作t(R)。

64例4.10 设A＝{a,b,c,d},R＝{,,,},则R和r(R),s(R),t(R)的关系图如图4.6所示, 65A上关系R的闭包l定理4.4 设R为非空集合A上的关系,则有 (1)r(R)＝R∪R0；(2)s(R)＝R∪R-1；(3)t(R)=R∪R2∪R3∪…(4)A是含有n个元素的集合t(R)=R∪R2∪R3∪…∪Rk , k≤n 66例4.10 设A＝{a,b,c,d},R＝{,,,},则r(R),s(R),t(R)有解:(1)r(R)＝R∪R0 ={,,,}∪{,,,} ={,,,,.,,}(2)s(R)＝R∪R-1 ={,,,}∪{,,,} ={,,,,,}(3)t(R)=R∪R2∪R3∪… ={,,,}∪{,,,} ∪{,,,} ={,,,,,,,, }67闭包的矩阵表示(定理4.4的公式转换成矩阵表示）Mr＝M＋EMs=M+M’Mt=M+M2+M3+…其中E表示同阶的单位矩阵(主对角线元素为1,其他元素都是0)M'表示M的转置,而+均表示矩阵中对应元素的逻辑加。

68在例4.10中3个结果矩阵是:作业设A＝{a,b,c,d},R＝{,,,,},请画出R和r(R),s(R),t(R)的关系图本章主要内容:l集合的笛卡尔积与二元关系l关系的运算l关系的性质l关系的闭包l等价关系和偏序关系等价关系和偏序关系l函数的定义和性质l函数的复合和反函数714.5 等价关系和偏序关系定义4.12 设R为非空集合A上的关系,如果R是自反的、对称的和传递的,则称R为A上的等价关系.对任何x,y∈A,如果|x,y∈A∧x≡y(mod 3)},其中x-y(mod 3)的含义就是x-y可以被3整除. R为A上的等价关系,它的关系图如下所示,其中1~4~7,2~5~8,3~6.74把模3的等价关系推广,对任何正整数n可以定义整数集合Z上模n的等价关系. R＝｛|x,y∈Z∧x≡y(mod n)}例如,当n＝5时,整数之间的等价性满足: ···~－10~－5~0~5~10~…, …~－9~－4~1~6~11~… …~－8~－3~2~7~12~… ···~－7~－2~3~8~13~…, …~－6~－1~4~9~14~….75设R是非空集合A上的等价关系,则A上互相等价的元素构成了A的若干个子集,叫做等价类.定义4.13 设R是非空集合A上的等价关系,对任意的x∈A,令称 为x关于R的等价类,简称为x等价类,简记为[x].在例4.11中有 [1]＝[4]＝[7]＝{1,4,7}, [2]＝[5]＝[8]＝{2,5,8}, [3]＝[6]= {3,6}. 76等价类的性质.定理4.5 设R是非空集合A上的等价关系,对任意的x,y∈A,下面的结论成立. (1) [x]≠,且[x]A； (2) 若xRy,则[x]=[y]； (3) 若xRy,则[x]∩[y]＝； (4) =A.77商集定义4.14 设R为非空集合A上的等价关系,以R的不交的等价类为元素的集合叫做A在R下的商集,记作A／R, A／R＝{ ｜x∈A}.在例4.11中,A在R下的商集是A/R={{1,4,7},{2,5,8},{3,6}} 例4.13(1)非空集合A上的恒等关系 是A上的等价关系,对任意x∈A有[x]＝{x},商集A/ ={{x}|x∈A}.78(2)在整数集合z上模n的等价关系,其等价类是[0]＝{···,－2n, －n,0,n,2n,···}={nz|nz∈Z}＝nZ,[1]＝{···,－2n＋1,－n十1,1,n＋1,2n＋1,…} ={nz＋1｜z∈Z}＝nZ＋1[2]＝{···,－2n＋2,－n＋2,2,n＋2,2n十2,…} ={nz＋2｜z∈Z}＝nZ＋2, ······[n－1]＝{···,－2n＋n－1, －n＋n － 1,n－1,n＋n－1,···｝={nz+n －1｜zZ }=nZ+n －1.商集为{[0],[1],…,[n－1]｝79划分定义4.15 设A是非空集合,如果存在一个A的子集族(P(A))满足以下条件(1)；(2)中任意两个元素不交；(3)中所有元素的并集等于A,则称为A的一个划分,且称中的元素为划分块.80例. 考虑集合A＝{a,b,c,d}的下列子集族(1) {{a},{b,c},{d}},(2) {{a,b,c,d}},(3) {{a,b},{c},{a,d}},(4) {,{a,b},{c,d}},(5) {{a},{b,c}},81例4.15 设A＝{1,2,3},求出A上所有的等价关系.解: 先求A的各种划分:只有1个划分块的划分1,具有两个划分块的划分2,3和4,具有3个划分块的划分5,请看下图| 82设对应于划分i的等价关系为Ri,i＝1,2,…,5.则有R5＝{<1,1>,<2,2>,<3,3>}＝ IA ；R1＝{<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>}∪IA＝EA；R2＝{<2,3>,<3,2>}∪IA ； .R3＝{<1,3>,<3,1>}∪IA ；R4＝{<1,2>,<2,1>}∪IA.作业P137l4.31l4.32l4.33l4.34l4.35l4.3784偏序关系定义4.1 设R为非空集合A上的关系,如果R是自反的、反对称的和传递的,则称R为A上的偏序关系.简称偏序,记作≤ .任何集合A上的恒等关系,集合的幂集P(A)上的包含关系,实数集上的小于等于关系,正整数集上的整除关系都是偏序关系.85l定义4.17 一个集合A与A上的偏序关系R一起叫做偏序集,记作.l定义4.18 设为偏序集,对于任意的x,y∈A,如果x≤y或者y≤x成立,则称x与y是可比的,如果x＜y(即x≤y∧x≠y),且不存在zA使得x是偏序集,其中A＝{1,2,3,4,5}, ≤是整除关系.那么,对任意x∈A都有1≤x,所以,1和1,2,3,4,5都是可比的,但是2不能整除3,3也不能整除2,所以2和3是不可比的.对于1和2来说,1＜2,并且不存在z∈A使得1整除z并且z整除2,所以,2盖住 1.同样,4盖住2,但4不盖住1,因为有1＜2＜4成立.显然,如果x与y不可比,则一定不会有x盖住y或y盖住x. 87全序关系l 定义4.19 设为偏序集,若对任意的:x,y∈A,x和y都可比,则称≤为A上的全序关系,且称为全序集.例如,{1,2,3,4,5}上的小于等于关系是全序关系,而整除关系不是全序关系.88例4.16 画出<{1,2,…,12},R整除>和的哈斯图.解 :哈斯图如图4,9所示89例4.17 设偏序集的哈斯图如图所示,求出集合A的偏序≤.解 A＝{a,b,c,d,e, f, g, h>. ≤＝{,,, ,,,,,}∪ IA.90最大元,最小元,极大元,极小元定义4.20 设为偏序集,B  A.y是B的最小元:若y∈B,使得x(x∈B→y≤x)y是B的最大元:若y∈B,使得x(x∈B→x≤y) y是B的极小元:若y∈B,使得x(x∈B∧x＜y)y是B的极大元:若y∈B,使得x(x∈B∧y＜x)91上界,下界,上确界,下确界定义4.21 设为偏序集,BA.y是B的上界:若y∈A,使得x(x∈B→x≤y)y是B的下界:若y∈A,使得x(x∈B→y≤x)B的最小上界或上确界:令C＝{y|y为B的上界},则称C的最小元为上确界B的最大下界或下确界:令D＝{y|y为B的下界},则称D的最大元为下确界92 在图4.9中,如果B＝{2,3,6}, B的上界?最小上界? B的下界?最大下界?B的上界是6和12,最小上界是6,B的下界是1,最大下界也是1.而在图4.10中,令B＝{c,d,e}, 问题同上。

则B的上界和最小上界都是e,B的下界为a,b,但B没有最大下界.如果最小上界或最大下界存在,一定是唯一的.93 一些结论：（1）最大（小）元未必存在，若存在则必唯一；（2）极大（小）元必存在，但不唯一；（3）最大（小）元也必须是极大（小）元；（4）上（下）界未必存在，若存在也未必唯一；（5）上（下）确界未必存在，若存在则必唯一；（6）若a是子集B的最大（小）元，则a必是子 集B的上（下）确界；反之，若a是子集B 的上（下）确界且a ∈B，则a必是B的最 大（小）元作业P138-139l4.40l4.41l4.42l4.43l4.45l4.46(3)(4)本章主要内容:l集合的笛卡尔积与二元关系l关系的运算l关系的性质l关系的闭包l等价关系和偏序关系l函数的定函数的定义和性和性质l函数的复合和反函数96 4.6 函数的定义和性质l定义4.22 设X,Y为集合，F为X到Y二元关系,若对任意的x∈domF都存在唯一的y∈ranF使得xFy成立,则称F为函数. 例如,如下关系 X={x1,x2,x3} Y ={y1 ,y2}F1＝{,,}是函数F2＝{ , , ,｝不是函数,因为对于x1domF有x1Fy1,x1Fy2同时成立.97如果∈函数F,则记作 F(x)＝y,称y是F在x的函数值.l 定义4.23 设A,B是集合,如果函数f满足以下条件 (1) domf＝A, (2) ranfB, 则称f是从A到B的函数,记作f:A→B.l定义4.24 设A,B为集合,所有从A到B的函数构成集合BA,读作“B上A”.即 BA ={f | f:A→B },98l例2：设P是一个程序，输入输出都是整数，(m, n)∈fP意为输入m时程序运行输出n。

则fP是一个函数l例3：标识图是一个图，每个顶点或每条边或两者都带有标记例如一个图的顶点代表一个城市，边代表两个城市之间的距离设V是顶点集，L是标记集，则f：V→L是一个函数用E作边集，g：E→L，也是一个函数99例如A＝{0,1,2},B＝{a,b},则BA={f1,f2…,f8} f1＝{<0,a>,<1,a>,<2,a>}, f2＝{<0,a>, <1,a> ,<2,b>}, f3 ＝{<0,a>, <1,b> <2,c>} f4＝{<0,a>,<1,b>,<2,b>}, f5＝{<0,b> ,<1,a>,<2,a>}, f6＝{<0,b> <1,a>,<2,b>}, f7＝{<0,b> ,<1,b>,<2,a>}, f8={<0,b>, <1,b> ,<2,b>}.|A|=m,|B|=n,m,n不是0,|BA|=?100l 定义4.25 设f:A→B,A’A,则A’在f下的象是 f(A’)＝{f(x)|x∈A’}＝f[A’],当A’＝A时,称f(A’)=f(A)＝ranf是函数的象.101函数的性质l 定义4.26 设函数f:A→B.(1)若ranf＝B,则称f是满射的(或到上的)(2)若对于任何的x1, x2 ∈A, x1≠x2 ,都有f (x1)≠f(x2 ),则称f是单射的(或一一的),(3)若f既是满射的,又是单射的,则称f是双射的(或一一到上的)102例如,函数f:{1,2}→{0},f(1)＝f(2)＝0,那么f是满射的,但不是单射的.函数f:N→N,f(x)＝2x是单射的,但不是满射的,因为ranf不含有奇数,即ranfN.而函数f:Z→Z,f(x)=x＋1是双射的.103l定理. 设A，B都是有限集，|A|=|B|,lf：A→B是一个函数,处处有定义。

lf一一f满lf满f一一104 例4.18 分别确定以下各题中的f是否为从A到B的函数,并对其中的f:A→B指出它是否为单射、满射或双射的.如果不是,请说明理由. (1)A＝{1,2,3,4,5｝,B＝{6,7,8,9,10}, f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}.105(2) A＝{1,2,3,4,5｝,B＝{6,7,8,9,10}, f＝{<1,8> ,<3,10>,<2,6>, < 4,9>}.(3) A＝{1,2,3,4,5｝,B＝{6,7,8,9,10}, f＝{<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}.106(3)A,B为实数集 f(x)=x3 . 双射(4)A,B为实数集 f(x)= 不是函数 (5)A,B为正整数集, f(x)＝x＋1. 是单射，不是满射107(6)A,B为正整数集是单射不是满射因为f(1)=f(2)=1108例:判断以下函数的单射、满射和双射(1)f:R ×R-> R ×R,R为实数集， f()=(x+y,x-y)(2)f: N × N -> N, N为自然数集0 ∈N,f()=|x2-y2|例:判断以下函数的单射、满射和双射；求A在f下的像f(A)l(1)f: R-->R , f(x)=x , A={6}l2）f: N--> N × N ， f(x)=, A={2,5}l3) f: Z--> N ， f(x)=|x| ,A={-1,2}l定义：函数相等、包含l 设f:A → B,g:C → D,如果A=C，B=D,且对每个x ∈A,有f(x)=g(x),称函数f等于g,记为f=g.l如果A  C，B=D,且对每个x ∈A,有f(x)=g(x),称函数f包含于g,记为f  g.空函数l设X,Y为集合，l（1）当X=时，X到Y的空关系为一函数，称为空函数。

l（2）当X≠  且Y=时, X到Y的空关系不是一函数112(1)设:A→B,如果存在y∈B使得对所有的x∈A都有f(x)＝y,则称f:A→B是常函数.(2)A上的恒等关系IA就是A上的恒等函数,对于所有的x∈A有IA(x)=x.(3)设f:R→R,对于任意的x1 , x2 ∈R,如果x1＜x2则有f(x1)≤f(x2),称y为单调递增的.如果x1＜x2则有f(x1)＜f(x2),就称f为严格单调递增的.类似地也可以定义单调递减和严格单调递减的函数,它们统称为单调函数.(4)设A为集合,对于任意的A’A,A’的特征函数 :A→｛0,1}定义为113(5)设R是A上的等价关系,定义一个从A到A/R的函数g:A → A/R且g(a)＝[a],它把A中的元素a映到a的等价类[a].我们称g是从A到商集A/R的自然映射.例如,A＝{1,2,3},R＝{<1,2>,<2,1>}∪ IA,则有 g(1)＝g(2)＝{1,2}, g(3)＝{3}.作业P139l4.49(3)-(4)l4.54l4.55本章主要内容:l集合的笛卡尔积与二元关系l关系的运算l关系的性质l关系的闭包l等价关系和偏序关系l函数的定义和性质l函数的复合和反函数函数的复合和反函数1164.9 函数的复合和反函数定理⒋9.1 设 f:X → Y,g:Y→ Z, 那么合成关系f◦g为X->Z的函数。

证明：（1）先证明Dom(f◦g)=X. 因为对任意x∈X，有y=f(x); 又对任意y∈Y,有z=g(y);所以 z=g(f(x) )= f◦g(x) (2)证明单值性假设任意x∈X,有两个z1,z2,使得z1= f◦g(x）z2= f◦g(x）)， 由 ◦定 义 ， 存 在 y1,y2,使 得 y1=f(x),z1=g(y1); y2=f(x),z2=g(y2);因f是函数，得y1=y2,又因g是函数，得z1=z2117例4.21 设f,g,h RR ,且有 f(x)＝x＋3,g(x)＝2x＋1,h(x)＝x/2.求g ◦ g, h ◦ f, g ◦ h, f ◦ h, f ◦ h ◦ g(x)g ◦ g(x)=g(g(x))＝2(2x＋1)＋1=4x＋3；g ◦ g={(x,4x+3>}h ◦ f={}＝{}；g ◦ h ={< x,h (g (x))>＝{}f ◦ h＝{}＝{}；f ◦ h ◦ g(x)＝g (h(f (x)))= g (h(x+3)))=g((x+3)/2)=2 · ((x＋3) /2)+1=x+4118定理4.9.3 设f:A→B,g:B →C, (1)如果f,g是满射的,则f ◦ g:A→C也是满射的. (2)如果f,g是单射的,则f ◦ g:A→C也是单射的.(3)如果f,g是双射的,则f ◦ g:A→C也是双射的.119函数的反函数定理4.9.5 设f:A→B是双射的,则f -1是函数,并且是从B到A的双射函数.对双射函数f:A→B,称f -1 :B→A是f的反函数.对任何双射函数f:A→B及其反函数f -1 :B→A,它们的复合函数都是恒等函数,且满足 （1）f -1 ◦ f＝ IB, f ◦ f -1 =IA （2） （ f -1 ） -1 = f定理4.9.7 设 f:X → Y,g:Y→ Z都是可以可逆的，那么复合关系f◦g也是可逆的，且 (f ◦ g) -1 = g -1 ◦ f -1 122例4.21 设f,g,h RR ,且有 f(x)＝x2-2, g(x)＝x＋4.求 (1) f◦g, g◦f (2) 判断 f◦g, g◦f是否为单射、满射和双射 （3）求f,g, f◦g, g◦f中可逆的反函数123本章 重点l集合的笛卡尔积与二元关系l关系的运算： 关系的逆运算、复合运算、闭包运算。

计算、证明l关系的性质：判断、证明l等价关系、等价类、商集、划分间的关系l偏序关系: 哈斯图、8个值的计算l函数的定义和性质（单射,满射,双射）l函数的复合和反函数124作作 业P1404.56 , 4.61。