《应用离散数学》方景龙版-3.3 二元关系的性质与闭包

集合论部分第四章、二元关系和函数4.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定义一个有序n (n³3) 元组 <x1, x2, …, x n> 是一个有序对，其中第一个元素是一个有序n-1元组，即<x1, x2, …, x n> = < <x1, x2, …, x n-1>, x n>当n=1时, <x> 形式上可以看成有序 1 元组.实例 n 维向量是有序 n元组.笛卡儿积及其性质定义设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={<Æ,Æ>, <{Æ},Æ>}性质：不适合交换律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证明A´(BÈC)=(A´B)È(A´C)证任取<x,y><x,y>∈A×(B∪C)Û x∈A∧y∈B∪CÛ x∈A∧(y∈B∨y∈C)Û (x∈A∧y∈B)∨(x∈A∧y∈C)Û <x,y>∈A×B∨<x,y>∈A×CÛ <x,y>∈(A×B)∪(A×C)所以有A×(B∪C) = (A×B)∪(A×C).例3 (1) 证明A=B Ù C=D Þ A´C=B´D(2) A´C=B´D是否推出A=B Ù C=D ? 为什么？解 (1) 任取<x,y><x,y>ÎA´C Û xÎA Ù yÎCÛ xÎB Ù yÎD Û <x,y>ÎB´D(2) 不一定. 反例如下：A={1}，B={2}, C=D=Æ, 则A´C=B´D 但是A¹B.二元关系的定义定义设A,B为集合, A×B的任何子集所定义的二元关系叫做从A到B的二元关系, 当A=B时则叫做A上的二元关系.例 4 A={0,1}, B={1,2,3}, R1={<0,2>}, R2=A×B, R3=Æ, R4={<0,1>}. 那么R1, R2, R3, R4是从A 到B的二元关系, R3和R4同时也是A上的二元关系.计数|A|=n, |A×A|=n2, A×A的子集有个. 所以A上有个不同的二元关系.例如 |A|=3, 则A上有=512个不同的二元关系.设A 为任意集合，Æ是A 上的关系，称为空关系E, I A 分别称为全域关系与恒等关系，定义如下：AE={<x,y>|x∈A∧y∈A}=A×AAI={<x,x>|x∈A}A例如, A={1,2}, 则E={<1,1>,<1,2>,<2,1>,<2,2>}AI={<1,1>,<2,2>}A小于等于关系L A, 整除关系D A, 包含关系RÍ定义：L={<x,y>| x,y∈A∧x≤y}, AÍR，R为实数集合AD={<x,y>| x,y∈B∧x整除y},BBÍZ*, Z*为非0整数集R={<x,y>| x,y∈A∧xÍy}, A是集合族.Í类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.例如A = {1, 2, 3}, B ={a, b}, 则L={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}AD={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}AA=P(B)={Æ,{a},{b},{a,b}}, 则A上的包含关系是R={<Æ,Æ>,<Æ,{a}>,<Æ,{b}>,<Æ,{a,b}>,<{a},{a}>,Í<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}二元关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={a1, a2, …, a m}，B={b1, b2, …, b n}，R是从A到B的关系，R 的关系矩阵是布尔矩阵M R = [ r ij ] m´n, 其中r ij= 1Û < a i, b j> ÎR.关系图：若A= {x1, x2, …, x m}，R是从A上的关系，R的关系图是G R=<A, R>, 其中A为结点集，R为边集.如果<x i,x j>属于关系R，在图中就有一条从x i到x j 的有向边.注意：A, B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵M和关系图G R如下：R4.2 关系的运算基本运算定义：定义域、值域和域dom R = { x | $y (<x,y>ÎR) }ran R = { y | $x (<x,y>ÎR) }fld R = dom RÈ ran R例1 R={<1,2>,<1,3>,<2,4>,<4,3>}, 则dom R={1, 2, 4}ran R={2, 3, 4}fld R={1, 2, 3, 4}逆与合成R-1 = {<y,x> | <x,y>ÎR}R∘S = |<x,z> | $ y (<x,y>ÎRÙ<y,z>ÎS) }例2 R={<1,2>, <2,3>, <1,4>, <2,2>}S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}R-1={<2,1>, <3,2>, <4,1>, <2,2>}R∘S ={<1,3>, <2,2>, <2,3>}S∘R ={<1,2>, <1,4>, <3,2>, <3,3>}定义 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}R↾Æ=ÆR[{1,2}]={2,3,4}注意：F↾AÍF, F[A] Íran F基本运算的性质定理1 设F是任意的关系, 则(1) (F-1)-1=F(2) dom F-1=ran F, ran F-1=dom F证 (1) 任取<x,y>, 由逆的定义有<x,y>∈(F -1)-1 Û <y,x>∈F-1 Û <x,y>∈F所以有 (F-1)-1=F(2) 任取x,x∈dom F-1 Û $y(<x,y>∈F-1)Û $y(<y,x>∈F) Û x∈ran F所以有dom F-1= ran F. 同理可证 ran F-1 = dom F.定理2 设F, G, H是任意的关系, 则(1) (F∘G)∘H=F∘(G∘H)(2) (F∘G)-1= G-1∘F-1证 (1) 任取<x,y>,<x,y>Î(F∘G)∘HÛ$t(<x,t>∈F∘G∧<t,y>∈H) Û $t ($s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)Û $t $s (<x,s>∈F∧<s,t>∈G∧<t,y>∈H)Û $s (<x,s>∈F∧$t (<s,t>∈G∧<t,y>∈H))Û $s (<x,s>∈F∧<s,y>∈G∘H)Û <x,y>∈F∘(G∘H)所以 (F∘G)∘H = F∘(G∘H)(2) 任取<x,y>,<x,y>∈(F∘G)-1Û <y,x>∈F∘GÛ $t (<y,t>∈F∧(t,x)∈G)Û $t (<x,t>∈G-1∧(t,y)∈F-1)Û <x,y>∈G-1∘F-1所以 (F∘G)-1 = G-1∘F-1幂运算设R为A上的关系, n为自然数, 则R 的n次幂定义为：(1) R0={<x,x> | x∈A }=I A(2) R n+1 = R n∘R注意：对于A上的任何关系R1和R2都有R 10 = R20 = IA对于A上的任何关系R 都有R1 = R性质：定理3 设A为n元集, R是A上的关系, 则存在自然数s 和t, 使得R s = R t.证R为A上的关系, 由于|A|=n, A上的不同关系只有个.当列出R 的各次幂R0, R1, R2, …, , …,必存在自然数s 和t 使得R s=R t.定理4 设R 是A 上的关系, m, n∈N, 则(1) R m∘R n=R m+n(2) (R m)n=R mn证用归纳法(1) 对于任意给定的m∈N, 施归纳于n.若n=0, 则有R m∘R0=R m∘I=R m=R m+0A假设R m∘R n=R m+n, 则有R m∘R n+1=R m∘(R n∘R)=(R m∘R n)∘R=R m+n+1 ,所以对一切m, n∈N有R m∘R n=R m+n.(2) 对于任意给定的m∈N, 施归纳于n.若n=0, 则有(R m)0=I A=R0=R m×0假设 (R m)n=R mn, 则有(R m)n+1=(R m)n∘R m=(R mn)∘R m=R mn+m=R m(n+1)所以对一切m,n∈N有 (R m)n=R mn.4.3 关系的性质自反性反自反性定义设R为A上的关系,(1) 若"x(x∈A→<x,x>ÎR), 则称R在A上是自反的.(2) 若"x(x∈A→<x,x>ÏR), 则称R在A上是反自反的.实例：反关系：A上的全域关系E A, 恒等关系I A小于等于关系L A, 整除关系D A反自反关系：实数集上的小于关系幂集上的真包含关系例1 A={1,2,3}, R1, R2, R3是A上的关系, 其中R＝{<1,1>,<2,2>}1R＝{<1,1>,<2,2>,<3,3>,<1,2>}2R＝{<1,3>}3R自反,2R反自反,3R既不是自反也不是反自反的1对称性反对称性定义设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上的全域关系E A, 恒等关系I A和空关系Æ反对称关系：恒等关系I A，空关系是A上的反对称关系.例2 设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系,其中R＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}1R＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}3R对称、反对称.1R对称，不反对称.2R反对称，不对称.3R不对称、也不反对称.4传递性定义设R为A上的关系, 若"x"y"z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.实例：A上的全域关系E,恒等关系I A和空关系ÆA小于等于关系, 小于关系，整除关系，包含关系，真包含关系例3 设A＝{1,2,3}, R1, R2, R3是A上的关系, 其中R＝{<1,1>,<2,2>}1R＝{<1,2>,<2,3>}2R＝{<1,3>}3R和R3 是A上的传递关系1R不是A上的传递关系2关系性质的充要条件设R为A上的关系, 则(1) R在A上自反当且仅当I A ÍR(2) R在A上反自反当且仅当R∩I A=Æ(3) R在A上对称当且仅当R=R-1(4) R在A上反对称当且仅当R∩R-1ÍI A(5) R在A上传递当且仅当R°RÍR证明模式证明R在A上自反任取x,xÎAÞ ……………..….……. Þ <x,x>ÎR前提推理过程结论例4 证明若I A ÍR ，则 R在A上自反.证任取x,xÎA Þ <x,x> ÎIÞ <x,x>ÎRA因此R 在A 上是自反的.证明模式证明R在A上对称任取<x, y><x,y>ÎRÞ……………..….……. Þ <y,x>ÎR前提推理过程结论例5 证明若R=R-1 , 则R在A上对称.证任取<x,y><x,y>ÎR Þ <y,x>ÎR-1Þ <x,y>ÎR因此R 在A 上是对称的.证明模式证明R在A上反对称任取<x, y><x,y>ÎRÙ<y,x>ÎRÞ ………..………. Þ x=y前提推理过程结论例6 证明若R∩R-1ÍI A , 则R在A上反对称.证任取<x,y><x,y>ÎR Ù<y, x>ÎRÞ <x,y>ÎR Ù<x,y>ÎR-1Þ <x,y>ÎR∩R-1Þ <x,y>ÎI AÞ x=y因此R 在A 上是反对称的.证明模式证明R在A上传递任取<x, y>，<y, z><x,y>ÎRÙ<y, z>ÎRÞ…..………. Þ <x,z>ÎR前提推理过程结论例7 证明若R°RÍR , 则R在A上传递.证任取<x,y>，<y, z><x,y>ÎR Ù<y,z>ÎRÞ <x,z>ÎR°RÞ <x,z>ÎR因此R 在A 上是传递的.4.4 关系的闭包闭包定义定义设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R¢, 使得R¢满足以下条件：（1）R¢是自反的（对称的或传递的）（2）RÍR¢（3）对A上任何包含R的自反（对称或传递）关系R¢¢ 有R¢ÍR¢¢. 一般将R 的自反闭包记作r(R), 对称闭包记作s(R), 传递闭包记作t(R).闭包的构造方法定理1 设R为A上的关系, 则有(1) r(R) = R∪R0(2) s(R) = R∪R-1(3) t(R) = R∪R2∪R3∪…说明：对于有穷集合A (|A|=n) 上的关系, (3)中的并最多不超过R n. 若R是自反的，则r(R)=R; 若R是对称的，则s(R)=R; 若R是传递的，则t(R)=R. 设关系R, r(R), s(R), t(R)的关系矩阵分别为M, M r, M s 和M t , 则M= M + ErM= M + M’sM= M + M2 + M3 + …tE 是和M 同阶的单位矩阵, M’是M 的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.设关系R, r(R), s(R), t(R)的关系图分别记为G, G r, G s, G t , 则G r, G s, G t 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新边：考察G的每个顶点, 如果没有环就加上一个环，最终得到G r . 考察G的每条边, 如果有一条x i 到x j 的单向边, i≠j, 则在G中加一条x j 到x i 的反方向边，最终得到G s. 考察G的每个顶点x i, 找从x i 出发的每一条路径，如果从x i 到路径中任何结点x j 没有边，就加上这条边. 当检查完所有的顶点后就得到图G t .4.5 等价关系和偏序关系定义设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的余数相等.验证模 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)自反性、对称性、传递性得到验证定义设R为非空集合A上的等价关系, "x∈A，令[x]R = { y | y∈A∧xRy }称 [x]R 为x 关于R 的等价类, 简称为x 的等价类, 简记为[x].实例A={ 1, 2, … , 8 }上模 3 等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}等价类的性质：定理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) ∪{ [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)定义设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R| x∈A }实例A={1,2,…,8},A关于模3等价关系R的商集为A/R = { {1,4,7}, {2,5,8}, {3,6} }A关于恒等关系和全域关系的商集为：A/I= { {1},{2}, … ,{8}}AA/E= { {1, 2, … ,8} }A集合的划分：定义设A为非空集合, 若A的子集族π(πÍP(A)) 满足下面条件：(1) ÆÏπ(2) "x"y (x,y∈π∧x≠y→x∩y=Æ)(3) ∪π=A则称π是A的一个划分, 称π中的元素为A的划分块.例1 设A＝{a, b, c, d},给定π1,π2,π3,π4,π5,π6如下：π= { {a, b, c}, {d} }，π2= { {a, b}, {c}, {d} }1π= { {a}, {a, b, c, d} }, π4= { {a, b}, {c} }3π= { Æ,{a, b}, {c, d} }, π6= { {a, {a}}, {b, c, d} }5则π1和π2是A的划分, 其他都不是A 的划分.为什么？等价关系与划分的一一对应商集A/R 就是A 的一个划分不同的商集对应于不同的划分任给A 的一个划分π, 如下定义A 上的关系R：R = {<x,y> | x,y∈A∧x 与y 在π的同一划分块中}则R 为A上的等价关系, 且该等价关系确定的商集就是π.例2 给出A＝{1,2,3}上所有的等价关系求解思路：先做出A的所有划分, 然后根据划分写出对应的等价关系.例3 设A={1, 2, 3, 4}，在A´A上定义二元关系R：<<x,y>,<u,v>>ÎR Û x+y = u+v，求R 导出的划分.解A´A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>,<2,3>,<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>,<4,2>, <4,3>, <4 ,4>}根据 <x,y> 的x + y = 2,3,4,5,6,7,8 将A´A划分成7个等价类：(A´A)/R={ {<1,1>}, {<1,2>,<2,1>},{<1,3>, <2,2>, <3,1>},{<1,4>, <2,3>, <3,2>, <4,1>},{<2,4>, <3,3>, <4,2>},{<3,4>, <4,3>}, {<4,4>} }定义非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作≼. 设≼为偏序关系, 如果<x, y>∈≼, 则记作x≼y, 读作x“小于或等于”y. 实例集合A上的恒等关系I A 是A上的偏序关系.小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系.x与y 可比：设R为非空集合A上的偏序关系,x,yÎA, x与y可比Û x≼y ∨y≼x.结论：任取两个元素x和y, 可能有下述情况：x≺y (或y≺x), x＝y, x与y不是可比的.全序关系：R为非空集合A上的偏序, "x,yÎA, x与y 都是可比的，则称R 为全序（或线序）实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系覆盖：设R为非空集合A上的偏序关系, x, y∈A, 如果x ≺y且不存在zÎA 使得x ≺z ≺y, 则称y 覆盖x.实例：{ 1, 2, 4, 6 }集合上的整除关系,2 覆盖 1,4 和 6 覆盖 2.4 不覆盖 1.定义集合A和A上的偏序关系≼一起叫做偏序集, 记作 <A,≼>.实例：整数集和小于等于关系构成偏序集<Z,≤>，幂集P(A)和包含关系构成偏序集<P(A),RÍ>.哈斯图：利用偏序自反、反对称、传递性简化的关系图特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边偏序集的特定元素定义设<A,≼>为偏序集, BÍA, 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) 若Ø$x (x∈B∧y ≺x) 成立, 则称y 为B的极大元.特殊元素的性质对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.定义设<A, ≼>为偏序集, BÍA, yÎA.(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 函数的定义和性质函数定义：定义设F 为二元关系, 若 "x∈dom F 都存在唯一的y∈ran F 使xFy 成立, 则称F 为函数. 对于函数F, 如果有xFy, 则记作y=F(x), 并称y 为F 在x 的值.例1 F1={<x1,y1>,<x2,y2>,<x3,y2>}F={<x1,y1>,<x1,y2>}2F是函数, F2不是函数1函数相等：定义设F, G为函数, 则F =G Û FÍG∧GÍF如果两个函数F 和G 相等, 一定满足下面两个条件：(1) dom F = dom G(2) "x∈dom F = dom G 都有F(x) = G(x)实例函数F(x)=(x2-1)/(x+1), G(x)=x-1不相等, 因为 dom FÌdom G.定义设A, B为集合, 如果f 为函数dom f = Aran f Í B,则称f 为从A到B的函数, 记作f：A→B.实例f：N→N, f(x)=2x 是从N 到N 的函数g：N→N, g(x)=2也是从N 到N 的函数定义所有从A 到B 的函数的集合记作B A,读作“B上A”，符号化表示为B A ={ f | f：A→B }计数：|A|=m, |B|=n, 且m, n>0, |BA|=n m.A=Æ, 则B A=BÆ={Æ}.A≠Æ且B=Æ, 则B A=ÆA= Æ.例2 设A = {1, 2, 3}, B = {a, b}, 求B A.解B A = {f0, f1, … , f7}, 其中f={<1,a>,<2,a>,<3,a>}, f1={<1,a>,<2,a>,<3,b>}f={<1,a>,<2,b>,<3,a>}，f3={<1,a>,<2,b>,<3,b>}2f={<1,b>,<2,a>,<3,a>}，f5={<1,b>,<2,a>,<3,b>}4f={<1,b>,<2,b>,<3,a>}, f7={<1,b>,<2,b>,<3,b>}6定义设函数f：A→B, A1ÍA.A在f 下的像：f(A1) = { f(x) | x∈A1 }1函数的像f(A)注意：函数值f(x)∈B, 而像f(A1)ÍB.函数的性质定义设f：A→B,（1）若ran f = B, 则称f：A→B是满射的.（2）若 "y∈ran f 都存在唯一的x∈A使得f(x)=y, 则称f：A→B是单射的. （3）若f：A→B既是满射又是单射的, 则称f：A→B是双射的f满射意味着："y ÎB, 都存在xÎA使得 f(x) = y.f 单射意味着：f(x) = f(x2) Þ x1= x21例4判断下面函数是否为单射, 满射, 双射的, 为什么?(1) f：R→R, f(x) = -x2+2x-1(2) f：Z+→R, f(x) = ln x, Z+为正整数集(3) f：R→Z, f(x) = ëxû(4) f：R→R, f(x) = 2x+1(5) f：R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集.解 (1) f：R→R, f(x)=-x2+2x-1在x=1取得极大值0. 既不单射也不满射.(2) f：Z+→R, f(x)=ln x单调上升, 是单射. 但不满射, ran f={ln1, ln2, …}.(3) f：R→Z, f(x)= ëxû满射, 但不单射, 例如f(1.5)=f(1.2)=1.(4) f：R→R, f(x)=2x+1满射、单射、双射, 因为它是单调的并且ran f=R.(5) f：R+→R+, f(x)=(x2+1)/x有极小值f(1)=2. 该函数既不单射也不满射.构造从A到B的双射函数有穷集之间的构造例5 A=P({1,2,3}), B={0,1}{1,2,3}解 A={Æ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={ f, f1, … , f7 }, 其中f={<1,0>,<2,0>,<3,0>}, f1={<1,0>,<2,0>,<3,1>},f={<1,0>,<2,1>,<3,0>}, f3={<1,0>,<2,1>,<3,1>},2f={<1,1>,<2,0>,<3,0>}, f5={<1,1>,<2,0>,<3,1>},4f={<1,1>,<2,1>,<3,0>}, f7={<1,1>,<2,1>,<3,1>}.6令f：A→B,f(Æ)=f, f({1})=f1, f({2})=f2, f({3})=f3,f({1,2})=f, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f74常函数、恒等函数、单调函数1. 设f：A→B, 若存在c∈B 使得 "x∈A 都有f(x)=c, 则称f：A→B是常函数.2. 称A 上的恒等关系I A为A 上的恒等函数, 对所有的x∈A 都有I A(x)=x.3. 设f：R→R，如果对任意的x1, x2∈R，x1<x2, 就有f(x1) £ f(x2), 则称f 为单调递增的；如果对任意的x1, x2∈A, x1< x2, 就有f(x1) < f(x2), 则称f 为严格单调递增的.类似可以定义单调递减和严格单调递减的函数.例8 (1) A的每一个子集A’都对应于一个特征函数, 不同的子集对应于不同的特征函数. 例如A={a, b, c}, 则有= { <a,0>, <b,0>, <c,0> }，cÆc= { <a,1>, <b,1>, <c,0>}{a,b}(2) 给定集合A，A 上不同的等价关系确定不同的自然映射, 其中恒等关系确定的自然映射是双射, 其他的自然映射一般来说是满射. 例如A={1, 2, 3}, R={<1,2>,<2,1>}∪IAg(1) = g(2) = {1,2}, g(3) = {3}4.7 函数的复合和反函数函数复合的定理定理设F, G是函数, 则F∘G也是函数, 且满足(1) dom(F∘G)={ x | x∈dom F Ù F(x)∈dom G}(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)).函数复合运算的性质定理设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也是双射的.证 (1) "c∈C, 由g：B→C 的满射性, $b∈B 使得g(b)=c. 对这个b, 由f：A→B 的满射性，$a∈A使得f(a)=b. 由合成定理有f∘g(a)=g(f(a))=g(b)=c从而证明了f∘g：A→C是满射的.(2) 假设存在x1, x2∈A使得f∘g(x1) = f∘g(x2)由合成定理有g(f(x1))=g(f(x2)).因为g：B→C是单射的, 故f(x1)=f(x2). 又由于f：A→B也是单射的, 所以x1=x2. 从而证明f∘g：A→C是单射的.(3) 由 (1) 和 (2) 得证.定理设f: A®B，则f = f∘I= I A∘fB反函数存在的条件任给函数F, 它的逆F -1不一定是函数, 是二元关系.实例：F={<a,b>,<c,b>}，F -1={<b,a>,<b,c>}任给单射函数f：A→B, 则f -1是函数, 且是从 ran f 到A的双射函数, 但不一定是从B 到A 的双射函数.实例：f : N →N, f(x) = 2x,f -1 : ran f→N, f -1 (x) = x/2反函数定理设f：A→B是双射的, 则f -1：B→A也是双射的.证因为f 是函数, 所以f -1 是关系, 且dom f -1 = ran f = B , ran f -1 = dom f = A,对于任意的y∈B = dom f -1, 假设有x1, x2∈A使得<y,x1>∈f -1∧<y,x2>∈f -1成立, 则由逆的定义有<x1,y>∈f∧<x2,y>∈f根据f 的单射性可得x1 = x2, 从而证明了f -1是函数，且是满射的. 下面证明f -1的单射性.若存在y1, y2∈B 使得f -1 (y1) = f -1 (y2) = x, 从而有<y1,x>∈f -1∧<y2,x>∈f -1Þ <x,y1>∈f∧<x,y2>∈fÞ y1 = y2反函数的定义及性质对于双射函数f：A→B, 称f -1：B→A是它的反函数.反函数的性质定理设f：A→B是双射的, 则f -1∘f = I, f∘f -1 = I AB对于双射函数f：A→A, 有f -1∘f = f∘f -1 = IA函数复合与反函数的计算问题描述——多机调度问题：有2台机器c1, c2；6项任务t1, t2, …, t6. 每项任务的加工时间分别为：l(t)=l(t3)=l(t5)=l(t6)=1, l(t2)=l(t4)=21任务之间的顺序约束是：任务t3只有在t6和t5完成之后才能开始加工；任务t2只有在t6, t5和t4都完成后才能开始加工；任务t1只有在t3和t2完成之后才能开始加工.调度：任务安排在机器上加工的方案截止时间：开始时刻0，最后停止加工机器的停机时刻问题描述集合任务集T={t1, t2, ... , t n}, nÎZ+机器集M={c1, c2, ... , c m}，mÎZ+时间集 N函数和关系加工时间——函数l:T®Z+.顺序约束R ——T上的偏序关系，定义为R={<t i, t j>| t i, t jÎT, i=j 或t i 完成后t j 才可以开始加工}可行调度分配到机器：T 的划分 p={T, T2, ... , T m}，划分块T j 是T 的非空子集，1由安排在机器c j上加工的所有任务组成.每个机器上的任务开始时间"T jÎp，存在调度函数 s j:T j®N，满足以下条件：(1) 任意时刻i，每台机器上正在加工至多1个任务"i, 0 £ i<D,| { t k| t kÎT j, s j(t k)£i<s j(t k)+l(t k) }| £1, j=1, 2, …, m(2) 任务的安排满足偏序约束"t iÎT i, t jÎT j, <t i,t j>ÎRÛ s i(t i)+l(t i)£s j(t j) i, j=1, 2, …, m机器j 的停止时间D=max{s j(t k)| t kÎT j}+l(t k)j所有任务的截止时间D=max{D| j=1,2,...,m}.j我们的问题就是确定使得D达到最小的可行调度.（注：文档可能无法思考全面，请浏览后下载，供参考。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：§3.2 二元关系及其运算习题3.21. 设}}{{φφ，=A ，求)(A P A ⨯。

解 略2. 设C B A ，，是任意集合，若C A B A ⨯⊆⨯，是否一定有C B ⊆成立？为什么？解 当φ=A 时，若C A B A ⨯⊆⨯，C B ⊆不一定成立；当φ≠A 时，若C A B A ⨯⊆⨯，则C B ⊆一定成立，反证如下：若C B ⊆不成立，则存在C x B y ∉∧∈；又因为φ≠A ，所以存在A x ∈，这样，序偶C A y x B A y x ⨯>∉<∧⨯>∈<,,，与C A B A ⨯⊆⨯矛盾。

3. 设D C B A ，，，是任意集合，下列等式中哪些成立？哪些不成立？对于成立的给出证明，对于不成立的举一反例。

（1）)()()()(D B C A D C B A ⨯⨯=⨯ （2）)()()()(D B C A D C B A ⨯⨯=⨯（3）)()()()(D B C A D C B A ⨯-⨯=-⨯-解 （1）成立，证明如下：DC y B A xD C B A y x ∈∧∈⇔⨯>∈<)()(,D y C y B x A x ∈∧∈∧∈∧∈⇔)()(D y B x C y A x ∈∧∈∧∈∧∈⇔ D B y x C A y x ⨯>∈<∧⨯>∈⇔<,,)()(,D B C A y x ⨯⨯>∈⇔<（2）不成立，例如取}{a A =，}{b B =，}{c C =，}{d D =，则左边},{},{d c b a ⨯=},,,,,,,{><><><><=d b c b d a c a ，右边},,,{><><=d b c a 。

（3）不成立，例如取},{b a A =，}{b B =，},{d c C =，}{d D =，则左边}{}{c a ⨯=},{><=c a ，右边},{},,,,,,,{><-><><><><=d b d b c b d a c a},,,,,{><><><=c b d a c a 。

方世昌离散数学第三版教材课件第3章二元关系31 基本概念 32 关系的合成 33 关系上的闭包运算 34 次序关系 35 等价关系和划分 31 基本概念311 关系关系的数学概念是建立在日常生活中关系的概念之上的让我们先看两个例子例31-1 设 A abcd 是某乒乓球队的男队员集合 B efg 是女队员集合如果A和B元素之间有混双配对关系的是a 和gd和e我们可表达为 R 〈ag〉〈de〉这里R表示具有混双配对关系的序偶集合所有可能具有混双配对关系的序偶集合是 A×B 〈xy〉x∈A∧y∈B 〈ae〉〈af〉〈ag〉〈be〉〈bf〉〈bg〉〈ce〉〈cf〉〈cg〉〈de〉〈df〉〈dg〉例31-2 设学生集合A1 abcd 选修课集合A2 日语法语成绩等级集合A3 甲乙丙如果四人的选修内容及成绩如下 a 日乙 b 法甲c 日丙 d 法乙我们可表达为S 〈a日乙〉〈b法甲〉〈c日丙〉〈d法乙〉这里S表示学生和选修课及成绩间的关系而可能出现的全部情况为 A1×A2×A3 〈xyz〉x∈A1∧y∈A2∧z∈A3 〈a日甲〉〈a 日乙〉〈a日丙〉〈a法甲〉〈a法乙〉〈a法丙〉〈b日甲〉〈b日乙〉〈b日丙〉〈b 法甲〉〈b法乙〉〈b法丙〉〈c日甲〉〈c日乙〉〈c日丙〉〈c法甲〉〈c法乙〉〈d法丙〉定〈c法丙〉〈d日甲〉〈d日乙〉〈d日丙〉〈d法甲〉〈d法乙〉义31―1 1 A×B的子集叫做A到B的一个二元关系2 A1×A2××An n≥1 的子集叫做A1×A2××An上的一个n元关系3 从定义可看出关系是一个集合所有定义集合的方法都可用来定义关系例31-1和例31-2是列举法的例子一个谓词Px1x2xn 可以定义一个n元关系R R 〈x1x2xn〉P x1x2xn 例如实数R上的二元关系＞可定义如下＞〈xy〉x∈R∧y∈R∧x＞y 反之一个n元关系也可定义一个谓词当n 1时R 〈x〉P x 称为一元关系它是一重组集合表示论述域上具有性质P的元素集合其意义与R xP x 相同仅记法不同而已例如设P x 表示x是质数论述域是N则质数集合可表示为〈x〉｜P x 或x｜P x 关系也可归纳地定义自然数上的小于关系可定义如下1 基础〈01〉∈＜2 归纳如果〈xy〉∈＜那么i 〈xy1〉∈＜ ii 〈x1y1〉∈＜ 3 极小性对一切xy∈Nx＜y当且仅当〈xy〉是由有限次应用条款 1 和 2 构成定义31―2 设R是的子集如果R 则称R为空关系如果则称R为全域关系现在定义关系相等的概念在关系相等的概念中不仅需要n重组集合相等还需其叉积扩集也相同定义31―3设R1是上的n元关系R2是上的m元关系那么R1 R2当且仅当n m且对一切i1≤i≤nAi Bi并且R1和R2是相等的有序n重组集合 312 二元关系最重要的关系是二元关系本章主要讨论二元关系今后术语关系都指二元关系若非二元关系将用三元或n元一类术语指出二元关系有自己专用的记法和若干新术语设 A x1x2x7 B y1y2y6 R〈x3y1〉〈x3y2〉〈x4y4〉〈x6y2〉 A到B的二元关系R可如图31―1那样形象地表示〈x3y1〉∈R也可写成x3Ry1称为中缀记法读做x3和y1有关系R中缀记法常用来表示诸如＜＞等关系例如〈35〉∈＜通常写作3＜5 A叫做关系R的前域B叫做关系R的陪域 D R x｜y 〈xy〉∈R 叫做关系R的定义域R R y｜x 〈xy〉∈R 叫做关系R的值域关系是序偶的集合对它可进行集合运算运算结果定义一个新关系设R和S是给定集合上的两个二元关系则R∪SR∩SR-S 等可分别定义如下x R∪S y xRy∨xSy x R∩S y xRy∧xSy x R-S y xRy∧xy x y xRy 例31-3平面上的几何图形是平面R2的子集也是一种关系设参看图31―2 R1 〈xy〉｜〈xy〉∈R2∧x2y2≤9 R2 〈xy〉｜〈xy〉∈R2∧1≤x≤3 ∧0≤y≤3 R3 〈xy〉｜〈xy〉∈R2∧x2y2≥4 则 R1∪R2 〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∨ 1≤x≤3∧0≤y≤3 R1∩R3〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∧x2y2≥4 R1-R3 〈xy〉｜〈xy〉∈R2∧ x2y2≤9∧ L x2y2≥4 〈xy〉｜〈xy〉∈R2∧ x2y2≥4 313 关系矩阵和关系图表达有限集合到有限集合的二元关系时矩阵是一有力工具定义31―4 给定集合A a1a2am 和B b1b2bn 及一个A到B的二元关系R 使例31-4 设A a1a2 B b1b2b3 R 〈a1b1〉〈a2b1〉〈a1b3〉〈a2b2〉则其关系矩阵为例31-5 设A 1234 A上的二元关系R 〈xy〉｜x＞y 试求出关系矩阵解R 〈41〉〈42〉〈43〉〈31〉〈32〉〈21〉例31-6 设 A 12345 R 〈12〉〈22〉〈32〉〈34〉〈43〉其图示如图31―3所示图中结点5叫做孤立点利用关系R的图示也可写出关系R 314 关系的特性在研究各种二元关系中关系的某些特性扮演着重要角色我们将定义这些特性并给出它的图示和矩阵的特点定义31―5 设R是A上的二元关系 1如果对A中每一xxRx那么R是自反的即 A上的关系R是自反的x x∈A→xRx A 123 R1 〈11〉〈22〉〈33〉〈12〉是自反的其关系图和关系矩阵的特点如图31―4所示 2 如果对A中每一xxRx那么R是反自反的即 A上的关系R是反自反的 x x∈A→xRx 例如 A 123 R2 〈21〉〈13〉〈32〉是反自反的其关系图和关系矩阵的特点如图31―5所示有些关系既不是自反的又不是反自反的如图31―6 例如R3 〈11〉〈12〉〈32〉〈23〉〈33〉 3 如果对每一xy∈AxRy蕴含着yRx那么R是对称的即A上的关系R是对称的x y x∈A∧y∈A∧xRy→yRx 例如A 123 R4 〈12〉〈21〉〈13〉〈31〉〈11〉是对称的其关系图和关系矩阵的特点如图31―7所示 4 如果对每一xy∈AxRyyRx蕴含着x y那么R是反对称的即A上的关系R是反对称的x y x∈A∧y∈A∧xRy∧yRx→x y 例如A 123 R5 〈12〉〈23〉是反对称的其关系图和关系矩阵的特点如图31―8所示 5 如果对每一xyz∈AxRyyRz蕴含着xRz那么R是传递的即A上的关系R是传递的x y z x∈A∧y∈A∧z ∈A∧xRy∧yRz→xRz 例如A 1234R5 〈41〉〈43〉〈42〉〈32〉〈31〉〈21〉是传递的其关系图和关系矩阵如图31―10所示例31-7 1 任何集合上的相等关系是自反的对称的反对称的和传递的但不是反自反的 2 整数集合I上关系≤是自反的反对称的可传递的但不是反自反的和对称的关系＜是反自反的反对称的可传递的但不是自反的和对称的 3 设 ab 试考察上的下列关系 i 关系与有同样长度是自反的对称的可传递的但不是反自反的和反对称的 ii xRy当且仅当x是y的真词头这里R是反自反的反对称的可传递的但不是自反的和对称的 iii xRy当且仅当x的某真词头是y的一个真词尾这里R既不是自反的又不是反自反的因为aaRaa但abRab既不是对称的也不是反对称的并且不是传递的 4 非空集合上的空关系是反自反的对称的反对称的和传递的但不是自反的空集合上的空关系则是自反的反自反的对称的反对称的和可传递的 5 基数大于1的集合上的全域关系是自反的对称的和传递的但不是反自反的和反对称的例如图31―11所示的关系 321 关系的合成前边已经指出关系是序偶的集合因此可以进行集合运算本节介绍一种对关系来说更为重要的运算合成运算假设R1是A到B的关系R2是B到C的关系参看图32-1合成关系R1R2是一个A到C的关系如果在关系图上从a∈A到c∈C有一长度路径中弧的条数为2的路径其第一条弧属于R1其第二条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合其第一条弧属于R1其第二条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合定义32―1 设R1是从A到B的关系R2是从B到C的关系从A到C的合成关系记为R1R2定义为 R1R2 〈ac〉｜a∈A∧c∈C∧b〔b∈B∧〈ab〉∈R1∧〈bc〉∈R2〕例32-11 如果R1是关系是的兄弟R2是关系是的父亲那么R1R2是关系是的叔伯R2R2是关系是的祖父 2 给定集合A 1234 B 234 C 123 设R是A到B的关系S是B到C的关系 R 〈xy〉｜xy 6 〈24〉〈33〉〈42〉S 〈yz〉｜y-z 1 〈21〉〈32〉〈43〉则R·S 〈23〉〈32〉〈41〉如图32―2所示 3 设A 12345 R和S都是A上二元关系如果 R 〈12〉〈34〉〈22〉 S 〈42〉〈25〉〈31〉〈13〉则R·S 〈15〉〈32〉〈25〉 S·R 〈42〉〈32〉〈14〉 R·S ·R 〈32〉 R· S·R 〈32〉 R·R 〈12〉〈22〉 S·S〈45〉〈33〉〈11〉 4 设R是A到B的二元关系IAIB分别是A和B上的相等关系则IA·R R·IB R 5 如果关系R的值域与关系S的定义域的交集是空集则合成关系R·S是空关系下边介绍合成关系的性质定理32―1 设R1是从A到B的关系R2和R3是从B到C的关系R4是从C到D的关系那么 1 R1 R2∪R3 R1R2∪R1R3 2 R1 R2∩R3 R1R2∩R1R3 3 R2∪R3 R4 R2R4∪R3R4 4 R2∩R3 R4 R2R4∩R3R41 2 3 部分的证明留作练习我们仅证明 2 部分证先证明公式因为〈ac〉∈R1 R2∩R3 b〔〈ab〉∈R1∧〈bc〉∈R2∩R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2 ∧〈ab〉∈R1∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2〕∧b〔〈ab〉∈R1∧〈bc〉∈R3〕〈ac〉∈R1R2∧〈ac〉∈R1R3 〈ac〉∈R1R2∩R1R3 即〈ac〉∈R1 R2∩R3 〈ac〉∈R1R2∩R1R3 所以R1 R2∩R3 R1R2∩R1R3 再证包含可能是真包含举反例证明如果 A a B b1b2b3 C c A到B的关系R1〈ab1〉〈ab2〉 B到C的关系R2 〈b1c〉〈b3c〉 B到C的关系R3〈b2c〉〈b3c〉那么R1 R2∩R3 R1R2∩R1R3 〈ac〉此时R1 R2∩R3 ≠R1R2∩R1R3证毕定理32―2 设R1R2和R3分别是从A到BB到C和C到D的关系那么 R1R2 R3 R1 R2R3 证先证 R1R2R3 R1 R2R3 设〈ad〉∈ R1R2 R3那么对某c∈C〈ac〉∈R1R2和〈cd〉∈R3因为〈ac〉∈R1R2存在b∈B使〈ab〉∈R1和〈bc〉∈R2因为〈bc〉∈R2和〈cd〉∈R3得〈bd〉∈R2R3所以〈ad〉∈R1 R2R3 这样就证明了 R1R2 R3 R1 R2R3 R1 R2R3 R1R2 R3的证明是类似的留给读者自证上述证明也可用等价序列表达 322 关系R的幂当R是A上的一个关系时R可与自身合成任意次而形成A上的一个新关系在这种情况下RR常表示为R2RRR表示为R3等等我们能归纳地定义这一符号如下定义32―2设R是集合A上的二元关系n∈N那么R的n次幂记为Rn定义如下 1R0是A上的相等关系R0 〈xx〉｜x∈A 2 Rn1 Rn·R 定理32―3 设R是A上的二元关系并设m和n是N的元素那么 1Rm·Rn Rmn 2 Rm n Rmn 可用归纳法证明请读者自证定理32―4 设｜A｜ nR是集合A上的一个关系那么存在i和j使Ri Rj而0≤i＜j≤证A上的每一二元关系是A×A的子集因为｜A×A｜ n2｜ρ A×A ｜因此A上有个不同关系所以R的不同的幂不会超过个但序列R0R1 有项因此R的这些幂中至少有两个是相等的证毕定理32―5 设R是集合A上的一个二元关系若存在i和ji＜j使Ri Rj记d j-i那么 1 对所有k≥0Rik Rjk 2 对所有km≥0Rimdk Rik 3 记S R0R1R2Rj-1 那么R的每一次幂是S的元素即对n∈NRn∈S 证 1 和 2 部分用归纳法证明留作练习3 对于 c 设n∈N如果n＜j那么根据S的定义Rn∈S假设n≥j那么我们能将n表示为imdk这里k＜d根据 b 部分得Rn Rik因为ik＜j这证明了Rn∈S定理中的ij在实用时宜取最小的非负整数以保证S中无重复元素例32-2 设 A abcd R 〈ab〉〈cb〉〈bc〉〈cd〉其关系图如图32―3所示则R0 〈aa〉〈bb〉〈cc〉〈dd〉 R2 〈ac〉〈bb〉〈bd〉〈cc〉 R3〈ab〉〈ad〉〈bc〉〈cb〉〈cd〉 R4 〈ac〉〈bb〉〈bd〉〈cc〉它们的关系图如图32―4所示由于R4 R2根据定理32―5 c 对所有n∈NRn∈ R0R1R2R3 可见不必再算了事实上易证R5 R3R6 R4 R2用归纳法可得R2n1 R3和R2n R2这里n≥1 323 合成关系的矩阵表达定理32―6 设X x1x2xm Y y1y2yn Z z1z2zp R是X到Y的关系MR 〔aij〕是m×n矩阵S是Y到Z的关系MS 〔bij〕是n×p矩阵则MR·S 〔cij〕 MR·MS这里证因为如果存在某k使aik和bki都等于1则cij 1但aik和bkj都等于1意味着xiRyk和ykSzj所以xi R·S zj可见如此求得的MR·S确实表达了R·S的关系因此上述等式是正确的如果不仅存在一个k使aik和bki都是1此时cij仍为1只是从xi到zj不止一条长度为2的路径但等式仍然正确上段的论证已隐含了不止一个k的情况本定理说明合成关系矩阵可用关系矩阵布尔矩阵的乘法表达例32-3设X 12 Y abc Z αβ R 〈1a〉〈1b〉〈2c〉 S 〈aβ〉〈bβ〉则定理32―7 关系矩阵的乘法是可结合的证利用关系合成的可结合性证明 MR·MS ·MT MR·S·MT M R·S ·T MR· S·T MR·MS·T MR· MS·MT 不仅合成关系可用关系矩阵表达而且关系的集合运算也可用关系矩阵表达设R和S是X到Y上的二元关系MR 〔aij〕MS 〔bij〕cij是运算后所得新关系之关系矩阵的元素则 MR∩S MR∧MS cij aij∧bij MR∪S MR∨MS cij aij∨bij cij aij MR-S MR∧ cij aij∧ bij 331 逆关系在讨论闭包运算时要用到逆关系的概念因此我们先介绍逆关系定义33―1设R是从A到B的二元关系关系R的逆或叫R的逆关系记为是一从B到A的二元关系定义如下例33-11 I上的关系2 集合族上的关系的逆是关系3 空关系的逆是空关系4 B×A即A×B的全域关系的逆等于B×A的全域关系定理33―1设R是从A到B的关系而S是从B到C 的关系则定理33―2 设RR1和R2都是从A到B的二元关系那么下列各式成立 332 关系的闭包运算关系的闭包运算是关系上的一元运算它把给出的关系R扩充成一新关系R′使R′具有一定的性质且所进行的扩充又是最节约的定义33―2设R是A上的二元关系R的自反对称传递闭包是关系R′使 i R′是自反的对称的传递的ii R′R iii 对任何自反的对称的传递的关系R〃如果R〃R那么R〃R′ R的自反对称和传递闭包分别记为r R s R和t R 由定义可以看出R的自反对称传递闭包是含有R并且具有自反对称传递性质的最小关系如果R已经是自反的对称的传递的那么具有该性质并含有R的最小关系就是R自身下一定理说明这一点定理33―4设R是集合A上的二元关系那么 a R是自反的当且仅当r R R b R是对称的当且仅当s R R c R是传递的当且仅当t R R 证 a 如果R是自反的那么R具有定义33―2对R′所要求的性质因此r R R反之如果r R R那么根据定义33―2的性质 i R是自反的b 和 c 的证明是类似的略构造R的自反对称和传递闭包的方法就是给R补充必要的序偶使它具有所希望的特性下面我们用关系图来说明如何实现这一点定理33―5 设R是集合A上的二元关系那么r R R ∪E 这里E是A上相等关系在本节中均如此证设R′ R∪E显然R′是自反的且R′R余下只需证明最小性现假设R〃是A上的自反关系且R〃R因R〃是自反的所以R〃E又R〃R所以R〃R∪E R′这样定义33―2都满足所以R′ r R 证毕设G是集合A上二元关系R的关系图我们把G的所有弧都画成有来有往即如果有从a到b的弧那么也有从b到a的弧就得到了R的对称闭包的有向图下一定理体现了这一想法定理33―7 设R 是集合A上的二元关系那么例33-2 a 整数集合I 上的关系＜的自反闭包是≤对称闭包是关系≠传递闭包是关系＜自身b 整数集合I上的关系≤的自反闭包是自身对称闭包是全域关系传递闭包是自身 c E的自反闭包对称闭包和传递闭包都是 E d ≠的自反闭包是全域关系对称闭包是≠≠的传递闭包是全域关系e 空关系的自反闭包是相等关系对称闭包和传递闭包是自身 f 设R是I上的关系xRy当且仅当y x1那么t R 是关系＜定理33―8设R是集合A上的二元关系这里A有n个元素那么证设〈xy〉∈t R 于是必存在最小的正整数k使〈xy〉∈Rk现证明k≤n若不然存在A的元素序列x a0a1a2ak-1ak y使xRa1a1Ra2ak-1Ry因k＞na0a1ak中必有相同者不妨设ai aj0≤i＜j≤k于是xRa1a1Ra2ai-1RaiajRaj1ak-1Ry 成立即〈xy〉∈Rs这里s k- j-i但这与k是最小的假设矛盾于是k≤n又〈xy〉是任意的故定理得证例33-3 设A abcd R如图33―1 a 所示则t R R∪R2∪R3∪R4如图33―1 b 所示本例即是32-2 定理33―9 1 如果R是自反的那么s R 和t R 都是自反的 2 如果R是对称的那么r R 和t R 都是对称的 3 如果R是传递的那么r R 是传递的定理33―10 设R是集合A上的二元关系那么 1 rs R sr R 2 rt R tr R 3 ts R st R 2 注意到ER RE R 和对一切n∈NEn E可得 34 次序关系 341 偏序集合定义34―1 如果集合A上的二元关系R是自反的反对称的和传递的那么称R为A上的偏序称序偶〈AR〉为偏序集合如果R是偏序〈AR〉常记为〈A ≤〉≤是偏序符号由于≤难以书写通常写作≤读做小于或等于因为小于或等于也是一种偏序故不会产生混乱R是偏序时aRb就记成a≤b 如果R是集合A上的偏序则 R 也是A上的偏序如果用≤表示R 可用≥表示R〈A≤〉和〈A ≥〉都是偏序集合并互为对偶例34-1 1 〈I≤〉是偏序集合这里≤表示整数中的小于或等于关系 2 〈ρ A 〉是偏序集合这里是集合间的包含关系 3 A 2468 D代表整除关系M代表整倍数关系则 D 〈22〉〈44〉〈66〉〈88〉〈24〉〈26〉〈28〉〈48〉 M 〈22〉〈44〉〈66〉〈88〉〈42〉〈62〉〈82〉〈84〉〈AD〉〈AM〉都是偏序集合且互为对偶例2 a P 1234 〈P≤〉的哈斯图为图34―2 b A 236122436 〈A整除〉的哈斯图为图34―3 c A 1212 〈A整除〉的哈斯图为图34―4 定义34―2 设〈A≤〉是一偏序集合B是A的子集 a 元素b∈B是B的最大元素如果对每一元素x∈Bx≤b b 元素b∈B是B的最小元素如果对每一元素x∈Bb≤x 例3考虑在偏序整除下整数1到6的集合其哈斯图为图34―5 a 如果B 1236 那么1是B的最小元素6是B的最大元素 b 如果B 23 因为2和3互相不能整除那么B没有最小元素和最大元素 c 如果B 4 那么4是B的最大元素也是B的最小元素定理34―1 设〈A≤〉是一偏序集合且B A如果B有最大最小元素那么它是唯一的证假设a和b都是B的最大元素那么a≤b和b≤a从≤的反对称性得到a b当a和b都是B的最小元素时证明是类似的定义34―3设〈A≤〉是一偏序集合B是A的子集 a如果b∈B且B中不存在元素x使b≠x且b≤x那么元素b∈B叫做B的极大元素b 如果b∈B且B中不存在元素x使b≠x且x≤b那么元素b∈B叫做B的极小元素定义34―4设〈A≤〉是一偏序集合B是A的子集a 如果对每一b∈Bb≤a那么元素a∈A叫做B的上界如果对每一b∈Ba≤b那么元素a∈A叫做B的下界 b 如果a是一上界并且对每一B的上界a′有a≤a′那么元素a∈A叫做B的最小上界记为lub如果a是一下界并且对每一B的下界a′有a′≤a那么元素a∈A叫做B的最大下界记为glb 例34-4 a 考虑偏序集合〈〈11〉〈10〉〈01〉〈00〉≤〉这里≤按〈 ab〉≤〈cd〉a≤c∧b≤d 规定其哈斯图如图34―6 如果B 〈10〉那么〈10〉是B的最小和最大元素也是B的极大和极小元素B的上界是〈10〉和〈11〉〈10〉是最小上界B的下界是〈00〉和〈10〉〈10〉是最大下界 b 考虑偏序集合〈I≤〉设B 2i｜i∈N那么B既没有最大元素和极大元素也没有上界和最小上界B的最小元素和极小元素是0B的下界集合是 i｜i∈I∧i≤0 0是最大下界 c 考虑在偏序集合〈 256101530 整除〉其哈斯图如图34―7设B是全集合 256101530 那么2和5都是B的极小元素但B没有最小元素集合B没有下界所以没有最大下界元素30是B的最大元素极大元素上界最小上界定理34―2 如果〈A≤〉是非空有限的偏序集合则A的极小大元素常存在最大下界和最小上界也可能存在或不存在但如果它们存在则是唯一的定理34―3 设〈A≤〉是偏序集合且B A 如果B的最小上界最大下界存在那么是唯一的下述定理描述了存在于诸特异元素之间的某些关系定理34―4 设〈A≤〉是偏序集合B是A的子集 a 如果b是B的最大元素那么b是B的极大元素 b 如果b是B的最大元素那么b是B的lub c 如果b是B的一个上界且b∈B那么b是B的最大元素证明可由最大元素极大元素和lub的定义直接得出故略去另外读者不难给出表达最小元素极小元素和glb间关系的定理 342 拟序集合定义34―5如果集合A上的二元关系R是传递的和反自反的那么R叫做A上的拟序〈AR〉称为拟序集合常借用符号＜表示拟序拟序是反对称的虽然定义中没有明确指出但容易证明这一点因为如果xRy和yRx由R的传递性得xRx但这与R的反自反性矛盾所以xRy∧yRx常假于是xRy∧yRx→x y常真即R是反对称的例34-5 a 实数集合中的＜是拟序关系 b 集合族中的真包含是拟序关系拟序集合和偏序集合是紧密相关的唯一区别是相等关系E下述定理将说明这一点定理34―5在集合A上 a 如果R是一拟序那么rR R∪E是偏序 b 如果R是一偏序那么R-E是一拟序 343线序集合和良序集合如果≤是一偏序或a≤b或b≤a我们说a和b是可比较的偏序集合中的元素不一定都可比较所以叫偏序下面介绍的都是可比较的情况定义34―6在偏序集合〈A≤〉中如果每一ab∈A或者a≤b或者b≤a那么≤叫做A上的线序或全序这时的序偶〈A≤〉叫做线序集合或链例34-6 a P a ab abc 〈P〉是线序集合其哈斯图如图34―8所示 b 〈I≤〉是线序集合其哈斯图不完全如图34―9所示 c 设S是区间套的集合〔0a ｜a∈R 则〈S〉是线序集合 d 〈 1236 整除〉不是线序集合如果A是多于一个元素的集合那么〈ρ A 〉不是线序集合定义34―7如果A上的二元关系R是一线序且A的每一非空子集都有一最小元素那么R叫做A上的良序序偶〈AR〉叫做良序集合定理34―6〈N≤〉是良序集合证我们必须证明N的每一非空子集S在关系≤之下都有一最小元素因为S非空所以在S中可以取一个数n显然S中所有不大于n的数形成非空集T S如果T有最小数那么这最小数就是S中的最小数但从0到n只有n1个自然数于是T中所含的数最多是n1个所以T有最小数因此定理成立例34-8 a 每一有限线序集合是良序的 b 线序集合〈I≤〉不是良序集合因为I的某些子集诸如I自身不包含最小元素 c 关系≤是实数R的线序但不是良序例如子集A 01〕无最小元素如果A中的a是最小元素那么也在A中而≤a且不相等这与假设a是线序关系≤下A的最小元素矛盾2 应用N上的良序定义出Nn上的良序例如n 2时N2上的次序关系可如下定义〈ab〉〈cd〉a＜c∨ a c∧b d 〈N2〉是良序集合关系严格小于可如下定义〈ab〉＜〈cd〉〈ab〉≤〈cd〉∧〈ab〉≠〈cd〉类似地应用I上的线序能定义出线序集合〈In≤〉 3 应用字母表∑上的线序可定义出∑上的通常叫词典序的线序定义34―8 设∑是一有限字母表指定了字母表序线序如果xy∈∑ a x是y的词头或 b x zu和y zv这里z∈∑是x和y的最长公共词头且在字母表序中u的第一个字符前于v的第一个字符那么x≤y≤叫做词典序4 由于〈N〉和有限线序集合都是良序集合可应用它们定义出∑上的一个良序通常叫标准序定义34―9设∑是一有限字母表指定了字母表序‖x‖表示x∈∑的长度如果xy∈∑ a ‖x‖＜‖y‖或b ‖x‖‖y‖且在∑的词典序中x前于y那么x≤y ≤叫做标准序不论在词典序和标准序下∑的每一元素都有直接后继者设∑ abc 且a≤b≤cx∈∑在标准序下 xa和xb的直接后继者分别是xb和xc xc的直接后继者是ya这里y是x的直接后继者在词典序下x的直接后继者是xa在标准序下 xb和xc的直接前趋分别是xa和xb xa的直接前趋是yc这里y是x的直接前趋在词典序下 xa的直接前趋是x非a结尾的串都无直接前趋例如babaab但有无限个前趋 345 数学归纳法的推广前章我们把数学归纳法第一第二原理看作是自然数域上的一个推理规则本小节我们把它推广到一般的良序集合对任一个自然数n我们先取0如果n≠0取0的后继者1如果n≠1再取1的后继者2如此进行下去最终会得出n 给定一个良序集合如果对它的任一元素x我们先取该集合的最小元素m0如果x≠m0取m0的后继者m1如果x≠m1再取m1的后继者m2如此以往最终会得出x那么就称这样的良序集合是像自然数的例 8 1 设∑ ab 良序集合〈∑标准序〉是像自然数的因为定长的串的个数有限给定任一个串x在x之前的串的个数有限所以从∧开始反复取后继者终可得出x 2 良序集合〈N×N≤〉不像自然数这里≤按上一小节规定因为有许多元素没有直接前趋例如〈50〉就是这样因而有无限个元素前于〈50〉所以从〈00〉开始反复地取后继者不可能取得〈50〉像自然数的良序集合可以应用数学归纳法第一原理因为第一原理是建立在后继运算上而这种良序集合的每一元素都可通过重复地取后继者得到设m0是该良序集合〈S≤〉的最小元素S x 是元素x的后继者则推理规则如下对不像自然数的良序集合不能应用数学归纳法第一原理因为这种良序集合的有些元素不能由后继运算得到但对它可应用数学归纳法第二原理第二原理是建立在良序集合上的适用于一切良序集合设〈S≤〉是良序集合＜表示≤-E 即x＜y表示x≤y且x≠y 则推理规则如下下面证明良序集合上这个推理规则是有效的假设我们能证明前提例34-10〈Q≤〉是线序集合现说明在此线序集合中第二原理不是有效推理规则设谓词P x 表示x小于或等于5 i 当x≤5时 y〔y＜x→P y 〕是真P x 也真所以是真综合 i 和 ii 得在论述域Q上 x 〔 y y＜x→P y →P x 〕是真但结论 x P x 是假这说明第二原理不能应用于线序集合〈Q≤〉 35 等价关系和划分 351 等价关系二元关系的另一重要类型是等价关系其定义如下定义35―1 如果集合A上的二元关系R是自反的对称的和传递的那么称R是等价关系设R是A上的等价关系abc是A的任意元素如果aRb 即〈ab〉∈R 通常我们记作a～b读做a等价于b 定义35―2 设k是一正整数而ab∈I如果对某整数ma-b m·k那么a和b是模k等价写成a≡b modk 整数k叫做等价的模数定理35―1模k等价是任何集合A I上的等价关系证如果A 例35-1 c 已指出它是等价关系如果A≠则 i 自反的因为对任一aa-a 0·k得出a≡a modk ii 对称的因为a≡b mod k 时存在某m∈I使a-b m·k于是b-a-m·k 因此 b≡a mod k iii 传递的设a≡b mod k 和b≡c mod k 那么存在m1m2∈I 使a-b m1k和b-c m2·k 将两等式两边相加得a-c m1m2 ·k所以a≡c mod k 例1 a 同学集合A abcdefgA中的关系R是住在同一房间这是等价关系因为 i 任一个人和自己同住一间具有自反性 ii 若甲和乙同住一间则乙和甲也同住一间具有对称性 iii 若甲和乙同住一间乙和丙同住一间则甲和丙也同住一间具有传递性现假设a和b同住一间def同住一间c住一间则 R 〈aa〉〈ab〉〈ba〉〈bb〉〈cc〉〈dd〉〈ee〉〈ff〉〈de〉〈ed〉〈ef〉〈fe〉〈df〉〈fd〉其有向图如图35―1所示 b 数中的相等关系集合中的相等关系命题演算中的关系等都是等价关系 c 空集合中的二元关系R是等价关系因为i x x∈→xRx ii x y〔x∈∧y∈∧xRy→yRx〕iii x y z〔x∈∧y∈∧z∈∧xRy∧yRz→xRz〕都无义地真所以R是等价关系集合A上的全域关系R A×A是等价关系模数等价是整数域或其子集上的等价关系并且是等价关系中极为重要的一类定理 35-1 模k等价是任何集合A I上的等价关系证如果A 例35-1 3 已指出它是等价关系如果A≠则 i 自反的因为对任一aa-a 0·k得出a≡a mod k ii 对称的因为a≡b modk 时存在某m∈I使a-b m·k于是b-a -m·k因此b≡amodk iii 传递的设a≡b modk 和b≡c modk 那么存在m1m2∈I使a-b m1k和b-c m2·k将两等式两边相加得a-c m1m2 ·k所以a≡c modk 例35-2 a 若R是I上模4等价关系则〔0〕4 -8-4048 〔1〕4 -7-3159 〔2〕4 -6-22610 〔3〕4 -5-13711 b 若R是I上模2等价关系则〔0〕2 -4-2024 〔1〕2 -3-1135 每一集合中的数相互等价 c 时钟是按模12方式记数的设备13点钟和1点钟有相同的记数定义35―3 设R是集合A上等价关系对每一a∈Aa关于R的等价类是集合 x｜xRa 记为〔a〕R简记为〔a〕称a为等价类〔a〕的表示元素如果等价类个数有限则R的不同等价类的个数叫做R的秩否则秩是无限的对每一a∈A等价类〔a〕R非空因为a∈〔a〕R 例 35-3 1 如图35―2设A abcdef R 〈aa〉〈bb〉〈cc〉〈ab〉〈ba〉〈ac〉〈ca〉〈bc〉〈cb〉〈dd〉〈ee〉〈de〉〈ed〉〈ff〉则等价关系R的等价类如下〔a〕〔b〕〔c〕 abc 〔d〕〔e〕 de 〔f〕 f等价关系R的秩是3 2 I上模4等价的等价类是〔0〕4〔1〕4〔2〕4〔3〕4 参看例2 a I上模2等价的等价类是〔0〕2 〔1〕2 参看例2 b3 集合A上相等关系的秩等于A的元素个数定理35―2 设R是非空集合A上的等价关系aRb 当且仅当〔a〕〔b〕证充分性因为a∈〔a〕〔b〕即a∈〔b〕所以aRb 定理35―3设R是集合A上的等价关系则对所有ab∈A或者〔a〕〔b〕或者〔a〕∩〔b〕证如果A 断言无义地真现设A≠若〔a〕∩〔b〕≠则存在某元素c∈〔a〕和c∈〔b〕根据定理35―2得〔a〕〔c〕〔b〕又因〔a〕和〔b〕都非空〔a〕∩〔b〕和〔a〕〔b〕不能兼得因而定理得证定义35― 4 给定非空集合A和非空集合族πA1A2Am 如果那么称集合族π是A的覆盖定理35―4设R是集合A上的等价关系则证先证定理35―5设R1和R2是集合A上的等价关系那么R1 R2当且仅当〔a〕R1｜a∈A 〔a〕R2｜a∈A 证必要性因为R1 R2所以对任意a∈A有〔a〕R1 x｜xR1a x｜xR2a。