第四章二元关系与函数【教学目的】：1.深刻理解关系的基本概念：掌握关系矩阵和关系图。2.熟练掌握关系的性质和判别方法。3.理解复合关系和逆关系的概念并熟练掌握其求法。4.深刻理解关系的自反、对称、传递闭包的概念并熟练掌握其求法。5.熟练掌握等价关系的判定与相关等价类的求法。6.深刻理解偏序关系的判定、偏序集的概念并熟练掌握其哈斯图表示法。7.了解全序集、良序集及相容关系的概念。【教学重点】：1.关系的基本概念；关系矩阵和关系图；2.复合关系和逆关系的概念及求法；3.关系的自反、对称、传递闭包的概念及其求法。4.等价关系的判定与相关等价类的求法5.函数基本概念：满射、单射、双射的概念及判别方法；6.单调递增、严格单调递增、单调递减和严格单调递减的判别方法。【教学难点】1.关系的自反、对称、传递闭包的概念及其求法。2.等价关系的判定与相关等价类的求法3.反函数的定义及求法【教学方法】：讲授【时数】：理论课12学时【教学内容】：4.1集合的笛卡儿积和二元关系1.有序对定义：由两个客体X和y，按照一定的顺序组成的二元组称为有序对，记作实例：点的直角坐标(3，-4)有序对性质：有序性《x,y>*（当xy时)，《x,y》与相等的充分必要条件是：=X=u^y=V例1=，求x,y.3y- 4 = 2, x+5 = y = y = 2, x = - 32.有序n元组定义：一个有序n（n≥3）元组=，xn>当IF1时，形式上可以看成有序1元组。实例n维向量是有序n元组。3.笛卡儿积及其性质定义：设A,B为集合，A与B的笛卡儿积记作AxB，即AxB=（《x,y》|xEA^yeB)例2A-{1,2,3]，B(a,b,c)AxB-[,,,,,,,,)BxA =[,,,,,,,,]A={0), P(A) xA-(, )
第四章 二元关系与函数 【教学目的】： 1.深刻理解关系的基本概念；掌握关系矩阵和关系图。 2.熟练掌握关系的性质和判别方法。 3.理解复合关系和逆关系的概念并熟练掌握其求法。 4.深刻理解关系的自反、对称、传递闭包的概念并熟练掌握其求法。 5.熟练掌握等价关系的判定与相关等价类的求法。 6.深刻理解偏序关系的判定、偏序集的概念并熟练掌握其哈斯图表示法。 7.了解全序集、良序集及相容关系的概念。 【教学重点】： 1.关系的基本概念；关系矩阵和关系图； 2.复合关系和逆关系的概念及求法； 3.关系的自反、对称、传递闭包的概念及其求法。 4.等价关系的判定与相关等价类的求法 5.函数基本概念；满射、单射、双射的概念及判别方法； 6. 单调递增、严格单调递增、单调递减和严格单调递减的判别方法。 【教学难点】： 1.关系的自反、对称、传递闭包的概念及其求法。 2.等价关系的判定与相关等价类的求法 3.反函数的定义及求法 【教学方法】：讲授 【时数】：理论课 12 学时 【教学内容】： 4.1 集合的笛卡儿积和二元关系 1.有序对定义：由两个客体 x 和 y，按照一定的顺序组成的二元组称为有序对，记作 实例：点的直角坐标(3,−4) 有序对性质： 有序性 （当 x y 时）， 与 相等的充分必要 条件是：= x=u y=v 例 1 = ，求 x, y. 3y− 4 = 2, x+5 = y y = 2, x = − 3 2.有序 n 元组定义 ： 一个有序 n (n3) 元组 是一个有序对，其 中第一个元素是一个有序 n-1 元组，即 = , xn> 当 n=1 时, 形式上可以看成有序 1 元组。实例 n 维向量是有序 n 元组。 3.笛卡儿积及其性质 定义：设 A,B 为集合，A 与 B 的笛卡儿积记作 AB， 即 AB ={ | xA yB } 例 2 A={1,2,3}, B={a,b,c} AB={,,,,,,,,} BA ={,,,,,,, ,} A={},P(A)A={, }
性质不适合交换律AxB+BxA(A+B,AO+,BO+)不适合结合律（AxB)×CAx（BxC)(AO+,BO+)对于并或交运算满足分配律Ax(BUC)=(AxB)(AxC)(BUOXA=(BXA)U(CXA)Ax (BnC)=(AxB)n (AxC)(Bn)×A=(BxA)n(CXA)若A或B中有一个为空集，则AxB就是空集AOx=xOB-0若|A|=m，[B|=n,则「AxB|=mn4.二元关系的定义定义如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系，简称为关系，记作R如ER，可记作xRy：如果gR，记作xy实例：(,,a,b)，R是二元关系，当a，b不是有序对时，S不是二元关系根据上面的记法，可以写1R2，aRb.5.二元关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A{al，a2，"，am)，Bbl，b2，，bn)，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=［rij］n，其中rij=l-eR关系图：若A（xl，x2，，xm)，R是从A上的关系，R的关系图是GR-属于关系R，在图中就有一条从xi到xj的有向边注意：A，B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系4.2关系的运算1.关系的基本运算定义：定义域、值域和域domR= (x I y (eR))ranR= (y/ 3x (eRA I xFy ^ xeA)A在F下的像F[A] = ran(FIA)实例R=(,，,)R (1)=(,<1, 4)R[(1]]=(2, 4)
性质 不适合交换律 ABBA (AB, A, B) 不适合结合律 (AB)CA(BC) (A, B) 对于并或交运算满足分配律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA) 若 A 或 B 中有一个为空集，则 AB 就是空集. A=B= 若|A|=m, |B|=n, 则 |AB|=mn 4.二元关系的定义 定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作 R.如∈R, 可记作 xRy；如果 R, 记作 x y 实例：R={,}, S={,a,b}. R 是二元关系, 当 a, b 不是有序对时，S 不是二元关系根据上面的记法，可以写 1R2, aRb. 5.二元关系的表示 表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若 A={a1, a2, ., am}，B={b1, b2, ., bn}，R 是从 A 到 B 的关系，R 的关系 矩阵是布尔矩阵 MR = [ rij ] mn, 其中 rij = 1 R. 关系图：若 A= {x1, x2, ., xm}，R 是从 A 上的关系，R 的关系图是 GR=, 其中 A 为 结点集，R 为边集.如果属于关系 R，在图中就有一条从 xi 到 xj 的有向边. 注意：A, B 为有穷集，关系矩阵适于表示从 A 到 B 的关系或者 A 上的关系，关系图适于表 示 A 上的关系 4.2 关系的运算 1.关系的基本运算定义： 定义域、值域 和 域 domR = { x | y (R) } ranR = { y | x (R) } fldR = domR ranR 逆与合成 R−1 = { | R} R∘S = | | y (RS) } 2.限制与像 定义 F 在 A 上的限制 F↾A = { | xFy xA} A 在 F 下的像 F[A] = ran(F↾A) 实例 R={, , , } R↾{1}={,} R[{1}]={2,4}
RIO=OR[(1, 2)]={2, 3, 4)注意：FIACF,F[A]CranF3.关系基本运算的性质定理1设F是任意的关系，则(1)(F-1)-1=F(2)domF-1=ranF,ranF-1=domF定理2设FG，H是任意的关系，则(1)(F)FFo(GH)(2) (FoG)-1= G-1-F-14.A上关系的幂运算设R为A上的关系，n为自然数，则R的n次幂定义为：(1) RO=( 1 XEA )=IA(2) Rn+1 = RnR注意：对于A上的任何关系RI和R2都有RI0=R20=IA对于A上的任何关系R都有RI = R5.幂的求法对于集合表示的关系R，计算Rn就是n个R右复合。矩阵表示就是n个矩阵相乘，其中相加采用逻辑加.6.幂运算的性质定理3设A为n元集，R是A上的关系，则存在自然数和t，使得Rs=Rt.定理4设R是A上的关系，m，nEN，则(1) Rmre RrFRm+n(2)(Rm) rFRmn4.3关系的性质1.自反性与反自反性定义设R为A上的关系，(1）若Vx(xEA-eR)，则称R在A上是自反的(2）若Vx(xEA-R)，则称R在A上是反自反的实例：反关系：A上的全域关系EA，恒等关系IA，小于等于关系LA整除关系DA反自反关系：实数集上的小于关系，幂集上的真包含关系实例例1A=(1,2,3)，R1，R2、R3是A上的关系，其中R1= [,)R2= (,,,)R3=[]2.对称性与反对称性定义设R为A上的关系，(1）若VxVy(xyEAΛER-ER)，则称R为A上对称的关系.(2）若xVy(x,yEAΛERΛER-x-y)，则称R为A上的反对称关系实例：对称关系：A上的全域关系EA，恒等关系IA和空关系Q
R↾= R[{1,2}]={2,3,4} 注意：F↾AF, F[A] ranF 3.关系基本运算的性质 定理 1 设 F 是任意的关系, 则 (1) (F−1)−1=F (2) domF−1=ranF, ranF−1=domF 定理 2 设 F, G, H 是任意的关系, 则 (1) (F∘G)∘H=F∘(G∘H) (2) (F∘G)−1= G−1∘F−1 4.A 上关系的幂运算 设 R 为 A 上的关系, n 为自然数, 则 R 的 n 次幂定义为： (1) R0={ | x∈A }=IA (2) Rn+1 = Rn∘R 注意： 对于 A 上的任何关系 R1 和 R2 都有 R10 = R20 = IA 对于 A 上的任何关系 R 都有 R1 = R 5.幂的求法 对于集合表示的关系 R，计算 Rn 就是 n 个 R 右复合。矩阵表示就是 n 个矩阵相乘, 其中相 加采用逻辑加. 6.幂运算的性质 定理 3 设 A 为 n 元集, R 是 A 上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt. 定理 4 设 R 是 A 上的关系, m, n∈N, 则 (1) Rm∘Rn=Rm+n (2) (Rm)n=Rmn 4.3 关系的性质 1.自反性与反自反性 定义 设 R 为 A 上的关系, (1) 若x(x∈A→R), 则称 R 在 A 上是自反的. (2) 若x(x∈A→R), 则称 R 在 A 上是反自反的. 实例： 反关系：A 上的全域关系 EA, 恒等关系 IA ，小于等于关系 LA, 整除关系 DA 反自反关系：实数集上的小于关系，幂集上的真包含关系 实例 例 1 A={1,2,3}, R1, R2, R3 是 A 上的关系, 其中 R1＝{,} R2＝{,,,} R3＝{} 2.对称性与反对称性 定义 设 R 为 A 上的关系, (1) 若xy(x,y∈A∧∈R→∈R), 则称 R 为 A 上对称的关系. (2) 若 xy(x,y∈A∧∈R∧∈R→x=y), 则称 R 为 A 上的反对称关系. 实例： 对称关系：A 上的全域关系 EA, 恒等关系 IA 和空关系
反对称关系：恒等关系IA，空关系是A上的反对称关系.例2设A=(1,2,3)，R1，R2，R3和R4都是A上的关系，其中R1=[,),R2= (,,)R3= [,},R4= [, ,)3.传递性定义设R为A上的关系，若VXVyVz(x,y,zEA^ER/ER-, )R2= (,)R3= ()4.关系性质的充要条件设R为A上的关系，则(1）R在A上自反当且仅当IA CR(2)R在A上反自反当且仅当RNIAO(3）R在A上对称当且仅当R-R-1(4)R在A上反对称当且仅当Rn R-1cIA(5）R在A上传递当且仅当RRCR5.关系性质判别自反反自反对称传递反对称表达式IACRRnIA-O-R-1RORCRRnR-IC IA关系主对角线元主对角线元素矩阵是对称矩阵若rij=l,且对M2中1所在位素矩阵全是0详j，则rji=0全是1M中相应位置都是1关系图每个顶点都每个顶点都没如果两个顶点之间如果两点之间有如果顶点xi连有有环有边，是一对方向边，是一条有向通到xk，则从环相反的边（无单边）边（无双向边）xi到xk有边4.4关系的闭包1.闭包定义定义设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R，使得R满足以下条件：（1）R是自反的（对称的或传递的）(2) RR（3）对A上任何包含R的自反（对称或传递）关系R有RR一般将R的自反闭包记作r（R)，对称闭包记作s（R)，传递闭包记作t（R)2.闭包的构造方法定理1设R为A上的关系，则有(1) r(R) =RURO(2) S(R) = RUR-1
反对称关系：恒等关系 IA，空关系是 A 上的反对称关系. 例 2 设 A＝{1,2,3}, R1, R2, R3 和 R4 都是 A 上的关系，其中 R1＝{,}， R2＝{,,} R3＝{,}， R4＝{,,} 3.传递性 定义 设 R 为 A 上的关系, 若 xyz(x,y,z∈A∧∈R∧∈R→∈R), 则称 R 是 A 上的传递关系. 实例 例 3 设 A＝{1,2,3}, R1, R2, R3 是 A 上的关系, 其中 R1＝{,} R2＝{,} R3＝{} 4.关系性质的充要条件 设 R 为 A 上的关系, 则 (1) R 在 A 上自反当且仅当 IA R (2) R 在 A 上反自反当且仅当 R∩IA= (3) R 在 A 上对称当且仅当 R=R−1 (4) R 在 A 上反对称当且仅当 R∩R−1IA (5) R 在 A 上传递当且仅当 RRR 5.关系性质判别 自反 反自反 对称 反对称 传递 表达式 IAR R∩IA= R=R−1 R∩R−1 IA RRR 关系 矩阵 主对角线元 素 全是 1 主对角线元素 全是 0 矩阵是对称矩阵 若 rij＝1, 且 i≠j, 则 rji＝0 对 M2 中 1 所在位 置, M 中相应位置都 是 1 关系图 每个顶点都 有 环 每个顶点都没 有环 如果两个顶点之间 有边, 是一对方向 相反的边(无单边) 如果两点之间有 边, 是一条有向 边(无双向边) 如果顶点 xi 连 通到 xk , 则从 xi 到 xk 有边 4.4 关系的闭包 1.闭包定义 定义 设 R 是非空集合 A 上的关系, R 的自反（对称或传递）闭包是 A 上的关系 R, 使得 R 满足以下条件： （1）R是自反的（对称的或传递的） （2）RR （3）对 A 上任何包含 R 的自反（对称或传递）关系 R 有 RR. 一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R). 2.闭包的构造方法 定理 1 设 R 为 A 上的关系, 则有 (1) r(R) = R∪R0 (2) s(R) = R∪R−1
(3)t(R)=RUR2URU...说明：对于有穷集合A（IA=n）上的关系，（3)中的并最多不超过Rn.若R是自反的，则r(R)=R；若R是对称的，则s(R)=R；若R是传递的，则t(R)=R设关系R,r(R)，sR)，t(R)的关系矩阵分别为MMr，Ms和Mt，则Mr=M+EMs = M + MMt =M +M2+M+E是和M同阶的单位矩阵，M是M的转置矩阵注意在上述等式中矩阵的元素相加时使用逻辑加设关系R,r(R)，s(R)，t(R)的关系图分别记为G,Gr，Gs，Gt，则Gr，Gs，Gt的项点集与G的顶点集相等。除了G的边以外，以下述方法添加新边：考察G的每个顶点，如果没有环就加上一个环，最终得到Gr：考察G的每条边，如果有一条xi到xi的单向边，i≠j，则在G中加一条xi到xi的反方向边，最终得到Gs.考察G的每个顶点xi，找从xi出发的每一条路径，如果从xi到路径中任何结点xj没有边，就加上这条边．当检查完所有的顶点后就得到图Gt.4.5等价关系与偏序关系1.等价关系的定义定义设R为非空集合上的关系．如果R是自反的、对称的和传递的，则称R为A上的等价关系设R是一个等价关系，若ER称x等价于y，记做～y实例设A1,2,…,8]，如下定义A上的关系RR=（/x,yEAAx=y(mod3)}其中=y(mod3）叫做x与y模3相等，即x除以3的余数与y除以3的余数相等.2.等价关系的验证验证模3相等关系R为A上的等价关系，因为VxEA，有x=x(mod3)Vx,yEA,若x=y(mod3)，则有y=x(mod3)Vx,y,zEA,若x=y(mod3)，y=z(mod3),则有x=z(mod3)自反性、对称性、传递性得到验证3.等价类定义设R为非空集合A上的等价关系，VxEA，令[X]R=y|yEAΛxRy】称【X]R为X关于R的等价类，简称为X的等价类，简记为[X]4.等价类的性质定理1设R是非空集合A上的等价关系，则(1）VxEA，［X是A的非空子集(2）Vx,yEA,如果XR，则［x]=[y](3）x,yEA,如果xy，则［与[不交
(3) t(R) = R∪R2∪R3∪. 说明： 对于有穷集合 A (|A|=n) 上的关系, (3)中的并最多 不超过 Rn. 若 R 是自反的，则 r(R)=R; 若 R 是对称的，则 s(R)=R; 若 R 是传递的，则 t(R)=R. 设关系 R, r(R), s(R), t(R)的关系矩阵分别为 M, Mr, Ms 和 Mt , 则 Mr = M + E Ms = M + M’ Mt = M + M2 + M3 + . E 是和 M 同阶的单位矩阵, M’是 M 的转置矩阵. 注意在上述等式中矩阵的元素相加时使用逻辑加. 设关系 R, r(R), s(R), t(R)的关系图分别记为 G, Gr, Gs, Gt , 则 Gr, Gs, Gt 的顶点集 与 G 的顶点集相等. 除了 G 的边以外, 以下述方法添加新边： 考察 G 的每个顶点, 如果没有环就加上一个环，最终得到 Gr . 考察 G 的每条边, 如 果有一条 xi 到 xj 的单向边, i≠j, 则在 G 中加一条 xj 到 xi 的反方向边，最终得到 Gs. 考察 G 的每个顶点 xi, 找从 xi 出发的每一条路径，如果从 xi 到路径中任何结点 xj 没有边，就加上这条边. 当检查完所有的顶点后就得到图 Gt . 4.5 等价关系与偏序关系 1.等价关系的定义 定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上 的等价关系. 设 R 是一个等价关系, 若∈R, 称 x 等价于 y, 记做 x～y. 实例 设 A={1,2,.,8}, 如下定义 A 上的关系 R： R = { | x,y∈A∧x≡y(mod 3) } 其中 x≡y(mod 3) 叫做 x 与 y 模 3 相等, 即 x 除以 3 的余数与 y 除以 3 的余数 相等. 2.等价关系的验证 验证模 3 相等关系 R 为 A 上的等价关系, 因为 x∈A, 有 x ≡ x(mod 3) x, y∈A, 若 x ≡ y(mod 3), 则有 y ≡ x(mod 3) x, y, z∈A, 若 x ≡ y(mod 3), y ≡ z(mod 3), 则有 x≡z(mod 3) 自反性、对称性、传递性得到验证 3.等价类 定义 设 R 为非空集合 A 上的等价关系, x∈A，令[x]R = { y | y∈A∧xRy } 称 [x]R 为 x 关于 R 的等价类, 简称为 x 的等价类, 简记为[x]. 4.等价类的性质 定理 1 设 R 是非空集合 A 上的等价关系, 则 (1) x∈A, [x] 是 A 的非空子集. (2) x, y∈A, 如果 x R y, 则 [x]=[y]. (3) x, y∈A, 如果 x y, 则 [x]与[y]不交
(4）U（［X】「XEA)=A，即所有等价类的并集就是A.实例A={1，2，.*，8】上模3等价关系的等价类：[1]=[4]=[7]= [1, 4, 7] ,[2]=[5]=[8]=(2, 5, 8] ,[3]=[6]=[3, 6]以上3类两两不交，[1,4,7]U(2,5,8]U[3,6] =[1,2,.,8]5.商集定义设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记做A/R，A/R=【【X]R【xEA】6.集合的划分定义设A为非空集合，若A的子集族元（CP(A)）满足下面条件：(1)(2) Vxy (x, yE ^xy+xny-0)(3)Uπ=A则称元是A的一个划分，称元中的元素为A的划分块7.等价关系与划分的一一对应商集A/R就是A的一个划分不同的商集对应于不同的划分任给A的一个划分元，如下定义A上的关系RR=(Ix,yEAΛx与y在π的同一划分块中)则R为A上的等价关系，且该等价关系确定的商集就是1，8.偏序关系定义非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作E实例：整数集和小于等于关系构成偏序集.哈斯图：利用偏序自反、反对称、传递性简化的关系图特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边10.偏序集的特定元素定义设为偏序集，BCA，yEB.(1）若Vx(xEBK<x）成立，则称y为B的最小元.(2）若Vx(xEBxy）成立，则称y为B的最大元(3）若3-X（xEBΛx<y）成立，则称y为B的极小元
(4) ∪{ [x] | x∈A}=A，即所有等价类的并集就是 A. 实例 A={ 1, 2, . , 8 }上模 3 等价关系的等价类： [1]=[4]=[7]={1,4,7}， [2]=[5]=[8]={2,5,8}， [3]=[6]={3,6} 以上 3 类两两不交， {1,4,7}{2,5,8}{3,6} = {1,2, . ,8} 5.商集 定义 设 R 为非空集合 A 上的等价关系, 以 R 的所有等价类作为元素的集合称为 A 关于 R 的商集, 记做 A/R, A/R = { [x]R | x∈A } 6.集合的划分 定义 设 A 为非空集合, 若 A 的子集族π(πP(A)) 满足下面条件： (1) π (2) xy (x,y∈π∧x≠y→x∩y=) (3) ∪π=A 则称π是 A 的一个划分, 称π中的元素为 A 的划分块. 7.等价关系与划分的一一对应 商集 A/R 就是 A 的一个划分 不同的商集对应于不同的划分任给 A 的一个划分π, 如下 定义 A 上的关系 R： R = { | x,y∈A∧x 与 y 在π的同一划分块中}则 R 为 A 上 的等价关系, 且该等价关系确定的商集就是π. 8.偏序关系 定义 非空集合 A 上的自反、反对称和传递的关系，称为 A 上的偏序关系，记作≼. 设≼为 偏序关系, 如果∈≼, 则记作 x≼y, 读作 x“小于或等于”y. x 与 y 可比：设 R 为非空集合 A 上的偏序关系, x,yA, x 与 y 可比 x≼y ∨ y≼x. 结论：任取两个元素 x 和 y, 可能有下述情况： x≺y (或 y≺x), x＝y, x 与 y 不是可比的. 全序关系： R 为非空集合 A 上的偏序, x,yA, x 与 y 都是可比的，则称 R 为全序（或 线序） 覆盖：设 R 为非空集合 A 上的偏序关系, x, y∈A, 如果 x ≺ y 且不存在 zA 使得 x ≺ z ≺ y, 则称 y 覆盖 x. 9.偏序集与哈斯图 定义 集合 A 和 A 上的偏序关系≼一起叫做偏序集, 记作 . 实例：整数集和小于等于关系构成偏序集，幂集 P(A)和包含关系构成 偏序集 . 哈斯图：利用偏序自反、反对称、传递性简化的关系图 特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的 元素的顺序在前，具有覆盖关系的两个结点之间连边 10.偏序集的特定元素 定义 设为偏序集, BA, y∈B. (1) 若x(x∈B→y≼x) 成立, 则称 y 为 B 的最小元. (2) 若x(x∈B→x≼y) 成立, 则称 y 为 B 的最大元. (3) 若x (x∈B∧x ≺ y) 成立, 则称 y 为 B 的极小元
(4）若3-x（xEBΛy为偏序集，BCA，yeA.(1）若Vx(xEB→xy）成立，则称y为B的上界(2）若Vx(xEBKx）成立，则称y为B的下界(3）令C一（yy为B的上界），则称C的最小元为B的最小上界或上确界（4）令D=(y丨y为B的下界），则称D的最大元为B的最大下界或下确界性质下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确界：反之不对4.6函数的定义与性质1.函数的定义定义设F为二元关系，若VxEdomF都存在唯一的yEranF使xFy成立，则称F为函数，对于函数F,如果有xFy，则记作J-F(x),并称y为F在x的值.2.函数相等定义设F,G为函数，则F=GFcGΛGcF如果两个函数F和G相等，一定满足下面两个条件：(1)domF=domG(2)VxEdomF=domG都有F(x)=G(x)3.从A到B的函数定义设A,B为集合，如果为函数domf= AranfcB,则称f为从A到B的函数，记作f:A→B4.B上A定义所有从A到B的函数的集合记作BA读作"B上A”，符号化表示为BA=( I f: A-B)5.函数的像定义设函数f:A→B,AlcAAI在下的像：AI)=((x)|xEA1)函数的像A)注意：函数值(x)EB，而像A1)CB
(4) 若x (x∈B∧y ≺ x) 成立, 则称 y 为 B 的极大元 性质 对于有穷集，极小元和极大元必存在，可能存在多个. 最小元和最大元不一定存在，如果存在一定惟一. 最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元. 定义 设为偏序集, BA, yA. (1) 若x(x∈B→x≼y) 成立, 则称 y 为 B 的上界. (2) 若x(x∈B→y≼x) 成立, 则称 y 为 B 的下界. (3) 令 C＝{y | y 为 B 的上界}, 则称 C 的最小元为 B 的最小上界 或 上确界. (4) 令 D＝{y | y 为 B 的下界}, 则称 D 的最大元为 B 的最大下界 或 下确界. 性质 下界、上界、下确界、上确界不一定存在 下界、上界存在不一定惟一 下确界、上确界如果存在，则惟一 集合的最小元就是它的下确界，最大元就是它的上确界；反之不对. 4.6 函数的定义与性质 1.函数的定义 定义 设 F 为二元关系, 若 x∈domF 都存在唯一的 y∈ranF 使 xFy 成立, 则称 F 为 函数. 对于函数 F, 如果有 xFy, 则记作 y=F(x), 并称 y 为 F 在 x 的值. 2.函数相等 定义 设 F, G 为函数, 则 F = G FG∧GF 如果两个函数 F 和 G 相等, 一定满足下面两个条件： (1) domF = domG (2) x∈domF = domG 都有 F(x) = G(x) 3.从 A 到 B 的函数 定义 设 A, B 为集合, 如果 f 为函数 domf = A ranf B, 则称 f 为从 A 到 B 的函数, 记作 f：A→B. 4.B 上 A 定义 所有从 A 到 B 的函数的集合记作 BA, 读作“B 上 A”，符号化表示为 BA ={ f | f：A→B } 5.函数的像 定义 设函数 f：A→B, A1A. A1 在 f 下的像： f(A1) = { f(x) | x∈A1 } 函数的像 f(A) 注意：函数值 f(x)∈B, 而像 f(A1)B
6.函数的性质定义设f：A-B,（1）若ranf=B，则称f:A→B是满射的（2）若VyEranf都存在唯一的xEA使得x)=y，则称f:A→B是单射的（3）若:A→B既是满射又是单射的，则称f：AB是双射的7.常函数、恒等函数、单调函数设f:A-B,若存在cEB使得VxEA都有x)=c,则称f:A→B是常函数称A上的恒等关系IA为A上的恒等函数，对所有的xEA都有IA(x)=x.设f：RR，如果对任意的xl,x2ER，xl<x2，就有(x1)≤f(x2)，则称了为单调递增的；如果对任意的xl,x2EA,xl<x2，就有(xl)<(x2)，则称f为严格单调递增的.类似可以定义单调递减和严格单调递减的函数4.7函数的复合与反函数1.函数复合的定理定理设F,G是函数，则FG也是函数，且满足(1)dom(FG)=( x|xEdomF ^ F(x)EdomG)(2) VxEdom(FoG) 有 FG(x)=G(F(x)推论1设F,G,H为函数，则(FG)H和F(GH)都是函数，且（FG)H=F(GH)推论2设f：A-B,g:B-C,则fog：A-C,且VxEA都有fog(x)=g((x)2.函数复合运算的性质定理设f:A-B，g:B→C.(1)如果f:A→B,g：B→C都是满射的，则fg：A-→C也是满射的(2)如果f:A-→B,g：B→C都是单射的，则fog：A→C也是单射的(3)如果f:A→B,g:B-C都是双射的，则fog：A-C也是双射的3.反函数的定义及性质对于双射函数f：A→B,称f-1：B→A是它的反函数定理设f:A→B是双射的，则f-1-f=IB, fof-1=IA对于双射函数 f:A-A,有f-1of=fof-1=IA
6.函数的性质 定义 设 f：A→B, （1）若 ranf = B, 则称 f：A→B 是满射的. （2）若 y∈ranf 都存在唯一的 x∈A 使得 f(x)=y, 则称 f：A→B 是单射的. （3）若 f：A→B 既是满射又是单射的, 则称 f：A→B 是双射的 7.常函数、恒等函数、单调函数 设 f：A→B, 若存在 c∈B 使得 x∈A 都有 f(x)=c, 则称 f：A→B 是常函数. 称 A 上的恒等关系 IA 为 A 上的恒等函数, 对所有的 x∈A 都有 IA(x)=x. 设 f：R→R，如果对任意的 x1, x2∈R，x1<x2, 就有 f(x1) f(x2), 则称 f 为单调递增的； 如果对任意的 x1, x2∈A, x1< x2, 就有 f(x1) < f(x2), 则称 f 为 严格单调递增的. 类似可以 定义单调递减 和严格单调递减 的函数. 4.7 函数的复合与反函数 1.函数复合的定理 定理 设 F, G 是函数, 则 F∘G 也是函数, 且满足 (1) dom(F∘G)={ x | x∈domF F(x)∈domG} (2) x∈dom(F∘G) 有 F∘G(x) = G(F(x)) 推论 1 设 F, G, H 为函数, 则 (F∘G)∘H 和 F∘(G∘H)都是函数, 且 (F∘G)∘H = F∘(G∘H) 推论 2 设 f：A→B, g：B→C, 则 f∘g：A→C, 且x∈A 都有 f∘g(x) = g(f(x)). 2.函数复合运算的性质 定理 设 f：A→B, g：B→C. (1) 如果 f：A→B, g：B→C 都是满射的, 则 f∘g：A→C 也是满射的. (2) 如果 f：A→B, g：B→C 都是单射的, 则 f∘g：A→C 也是单射的. (3) 如果 f：A→B, g：B→C 都是双射的, 则 f∘g：A→C 也是双射的. 3.反函数的定义及性质 对于双射函数 f：A→B, 称 f −1：B→A 是它的反函数. 定理 设 f：A→B 是双射的, 则 f −1∘f = IB, f∘f −1 = IA 对于双射函数 f：A→A, 有 f −1∘f = f∘f −1 = IA