蚌埠医科大学：《离散数学》课程教学资源（讲义）第四章 二元关系与函数

第四章二元关系与函数【教学目的】：1.深刻理解关系的基本概念：掌握关系矩阵和关系图。2.熟练掌握关系的性质和判别方法。3.理解复合关系和逆关系的概念并熟练掌握其求法。4.深刻理解关系的自反、对称、传递闭包的概念并熟练掌握其求法。5.熟练掌握等价关系的判定与相关等价类的求法。6.深刻理解偏序关系的判定、偏序集的概念并熟练掌握其哈斯图表示法。7.了解全序集、良序集及相容关系的概念。【教学重点】：1.关系的基本概念；关系矩阵和关系图；2.复合关系和逆关系的概念及求法；3.关系的自反、对称、传递闭包的概念及其求法。4.等价关系的判定与相关等价类的求法5.函数基本概念：满射、单射、双射的概念及判别方法；6.单调递增、严格单调递增、单调递减和严格单调递减的判别方法。【教学难点】1.关系的自反、对称、传递闭包的概念及其求法。2.等价关系的判定与相关等价类的求法3.反函数的定义及求法【教学方法】：讲授【时数】：理论课12学时【教学内容】：4.1集合的笛卡儿积和二元关系1.有序对定义：由两个客体X和y，按照一定的顺序组成的二元组称为有序对，记作<x，y>实例：点的直角坐标(3，-4)有序对性质：有序性《x,y>*<y,x>（当xy时)，《x,y》与<u,v>相等的充分必要条件是：<x,y>=<u,v>X=u^y=V例1<2,x+5>=<3y-4,y>，求x,y.3y- 4 = 2, x+5 = y = y = 2, x = - 32.有序n元组定义：一个有序n（n≥3）元组<xl，x2，"，xn》是一个有序对，其中第一个元素是一个有序n-1元组，即<xl，x2，，xn>=<<xl，x2，"，x-1>，xn>当IF1时，<x>形式上可以看成有序1元组。实例n维向量是有序n元组。3.笛卡儿积及其性质定义：设A,B为集合，A与B的笛卡儿积记作AxB，即AxB=（《x,y》|xEA^yeB)例2A-{1,2,3]，B(a,b,c)AxB-[<1, a>,<1, b>,<1, c>,<2, a>,<2, b>,<2, c>,<3, a>,<3, b>,<3, c>)BxA =[<a, 1>,<b,1>,<c, 1>,<a, 2>,<b,2>,<c,2>,<a,3>,<b, 3>,<c, 3>]A={0), P(A) xA-(<0,0>, <(0),0>)

第四章 二元关系与函数 【教学目的】： 1.深刻理解关系的基本概念；掌握关系矩阵和关系图。 2.熟练掌握关系的性质和判别方法。 3.理解复合关系和逆关系的概念并熟练掌握其求法。 4.深刻理解关系的自反、对称、传递闭包的概念并熟练掌握其求法。 5.熟练掌握等价关系的判定与相关等价类的求法。 6.深刻理解偏序关系的判定、偏序集的概念并熟练掌握其哈斯图表示法。 7.了解全序集、良序集及相容关系的概念。 【教学重点】： 1.关系的基本概念；关系矩阵和关系图； 2.复合关系和逆关系的概念及求法； 3.关系的自反、对称、传递闭包的概念及其求法。 4.等价关系的判定与相关等价类的求法 5.函数基本概念；满射、单射、双射的概念及判别方法； 6. 单调递增、严格单调递增、单调递减和严格单调递减的判别方法。 【教学难点】： 1.关系的自反、对称、传递闭包的概念及其求法。 2.等价关系的判定与相关等价类的求法 3.反函数的定义及求法 【教学方法】：讲授 【时数】：理论课 12 学时 【教学内容】： 4.1 集合的笛卡儿积和二元关系 1.有序对定义：由两个客体 x 和 y，按照一定的顺序组成的二元组称为有序对，记作<x,y> 实例：点的直角坐标(3,−4) 有序对性质： 有序性 <x,y><y,x> （当 x y 时），<x,y> 与 <u,v> 相等的充分必要 条件是：<x,y>=<u,v>  x=u  y=v 例 1 <2, x+5> = <3y− 4, y>，求 x, y. 3y− 4 = 2, x+5 = y  y = 2, x = − 3 2.有序 n 元组定义 ： 一个有序 n (n3) 元组 <x1, x2, ., xn> 是一个有序对，其 中第一个元素是一个有序 n-1 元组，即<x1, x2, ., xn> = < <x1, x2, ., xn-1>, xn> 当 n=1 时, <x> 形式上可以看成有序 1 元组。实例 n 维向量是有序 n 元组。 3.笛卡儿积及其性质 定义：设 A,B 为集合，A 与 B 的笛卡儿积记作 AB， 即 AB ={ <x,y> | xA  yB } 例 2 A={1,2,3}, B={a,b,c} AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>} BA ={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>, <b,3>,<c,3>} 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如<xy>ER，可记作xRy：如果<x,y>gR，记作xy实例：(<1,2>,<a,b)，S=(<1,2>,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-<ai，bj>eR关系图：若A（xl，x2，，xm)，R是从A上的关系，R的关系图是GR-<A，R，其中A为结点集，R为边集.如果<xi，x>属于关系R，在图中就有一条从xi到xj的有向边注意：A，B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系4.2关系的运算1.关系的基本运算定义：定义域、值域和域domR= (x I y (<x,y>eR))ranR= (y/ 3x (<x,y)eR))fldR=domRUranR逆与合成R-1 = (<y,x) 1 <x,y)eR)RoS = [<x, z) / 3 y (<x,y>eRA<y,z)eS) )2.限制与像定义F在A上的限制FIA = (<x, y> I xFy ^ xeA)A在F下的像F[A] = ran(FIA)实例R=(<1,2>,<2,3>，<1,4>,<2,2>)R (1)=(<1, 2>,<1, 4)R[(1]]=(2, 4)

性质 不适合交换律 ABBA (AB, A, B) 不适合结合律 (AB)CA(BC) (A, B) 对于并或交运算满足分配律 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 中有一个为空集，则 AB 就是空集. A=B= 若|A|=m, |B|=n, 则 |AB|=mn 4.二元关系的定义 定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作 R.如<x,y>∈R, 可记作 xRy；如果 <x,y>R, 记作 x y 实例：R={<1,2>,<a,b>}, S={<1,2>,a,b}. R 是二元关系, 当 a, b 不是有序对时，S 不是二元关系根据上面的记法，可以写 1R2, aRb. 5.二元关系的表示 表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若 A={a1, a2, ., am}，B={b1, b2, ., bn}，R 是从 A 到 B 的关系，R 的关系 矩阵是布尔矩阵 MR = [ rij ] mn, 其中 rij = 1 < ai, bj> R. 关系图：若 A= {x1, x2, ., xm}，R 是从 A 上的关系，R 的关系图是 GR=<A, R>, 其中 A 为 结点集，R 为边集.如果<xi,xj>属于关系 R，在图中就有一条从 xi 到 xj 的有向边. 注意：A, B 为有穷集，关系矩阵适于表示从 A 到 B 的关系或者 A 上的关系，关系图适于表 示 A 上的关系 4.2 关系的运算 1.关系的基本运算定义： 定义域、值域 和 域 domR = { x | y (<x,y>R) } ranR = { y | x (<x,y>R) } fldR = domR  ranR 逆与合成 R−1 = {<y,x> | <x,y>R} R∘S = |<x,z> |  y (<x,y>R<y,z>S) } 2.限制与像 定义 F 在 A 上的限制 F↾A = {<x,y> | xFy  xA} A 在 F 下的像 F[A] = ran(F↾A) 实例 R={<1,2>, <2,3>, <1,4>, <2,2>} R↾{1}={<1,2>,<1,4>} 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=(<x, x> 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-<xx>eR)，则称R在A上是自反的(2）若Vx(xEA-<x,x>R)，则称R在A上是反自反的实例：反关系：A上的全域关系EA，恒等关系IA，小于等于关系LA整除关系DA反自反关系：实数集上的小于关系，幂集上的真包含关系实例例1A=(1,2,3)，R1，R2、R3是A上的关系，其中R1= [<1, 1>,<2, 2>)R2= (<1, 1>,<2,2>,<3, 3>,<1,2>)R3=[<1,3>]2.对称性与反对称性定义设R为A上的关系，(1）若VxVy(xyEAΛ<x,y>ER-<y,x>ER)，则称R为A上对称的关系.(2）若xVy(x,yEAΛ<x,y>ERΛ<y,x>ER-x-y)，则称R为A上的反对称关系实例：对称关系：A上的全域关系EA，恒等关系IA和空关系Q

R↾= R[{1,2}]={2,3,4} 注意：F↾AF, 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,x> | 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→<x,x>R), 则称 R 在 A 上是自反的. (2) 若x(x∈A→<x,x>R), 则称 R 在 A 上是反自反的. 实例： 反关系：A 上的全域关系 EA, 恒等关系 IA ，小于等于关系 LA, 整除关系 DA 反自反关系：实数集上的小于关系，幂集上的真包含关系 实例 例 1 A={1,2,3}, R1, R2, R3 是 A 上的关系, 其中 R1＝{<1,1>,<2,2>} R2＝{<1,1>,<2,2>,<3,3>,<1,2>} R3＝{<1,3>} 2.对称性与反对称性 定义 设 R 为 A 上的关系, (1) 若xy(x,y∈A∧<x,y>∈R→<y,x>∈R), 则称 R 为 A 上对称的关系. (2) 若 xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y), 则称 R 为 A 上的反对称关系. 实例： 对称关系：A 上的全域关系 EA, 恒等关系 IA 和空关系 

反对称关系：恒等关系IA，空关系是A上的反对称关系.例2设A=(1,2,3)，R1，R2，R3和R4都是A上的关系，其中R1=[<1,1>,<2,2>),R2= (<1,1>,<1, 2>,<2, 1>)R3= [<1,2>,<1,3>},R4= [<1,2>, <2, 1>,<1, 3>)3.传递性定义设R为A上的关系，若VXVyVz(x,y,zEA^<x,y>ER/<y,z>ER-<x,z)ER),则称R是A上的传递关系.实例例3设A=(1,2,3)，R1，R2,R3是A上的关系，其中R1= (<1, 1>, <2, 2>)R2= (<1, 2>,<2, 3>)R3= (<1, 3>)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＝{<1,1>,<2,2>}， R2＝{<1,1>,<1,2>,<2,1>} R3＝{<1,2>,<1,3>}， R4＝{<1,2>,<2,1>,<1,3>} 3.传递性 定义 设 R 为 A 上的关系, 若 xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R), 则称 R 是 A 上的传递关系. 实例 例 3 设 A＝{1,2,3}, R1, R2, R3 是 A 上的关系, 其中 R1＝{<1,1>,<2,2>} R2＝{<1,2>,<2,3>} R3＝{<1,3>} 4.关系性质的充要条件 设 R 为 A 上的关系, 则 (1) R 在 A 上自反当且仅当 IA R (2) R 在 A 上反自反当且仅当 R∩IA= (3) R 在 A 上对称当且仅当 R=R−1 (4) R 在 A 上反对称当且仅当 R∩R−1IA (5) R 在 A 上传递当且仅当 RRR 5.关系性质判别 自反 反自反 对称 反对称 传递 表达式 IAR R∩IA= R=R−1 R∩R−1 IA RRR 关系 矩阵 主对角线元 素 全是 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）RR （3）对 A 上任何包含 R 的自反（对称或传递）关系 R 有 RR. 一般将 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是一个等价关系，若<x,y>ER称x等价于y，记做～y实例设A1,2,…,8]，如下定义A上的关系RR=（<x,y>/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 是一个等价关系, 若<x,y>∈R, 称 x 等价于 y, 记做 x～y. 实例 设 A={1,2,.,8}, 如下定义 A 上的关系 R： R = { <x,y> | 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]不交