《集合论与图论》第5讲1 第5讲二元关系的基本概念 内容提要 ? 1. 有序对与卡氏积 ? 2. 二元关系 ? 3. 二元关系的基本运算 《集合论与图论》第5讲2 有序对与卡氏积 ?有序对(有序二元组) ?有序三元组, 有序n元组 ?卡氏积 ?卡氏积性质 《集合论与图论》第5讲3 有序对(ordered pair) ?有序对: <a,b> = { {a}, {a,b} } 其中, a是第一元素, b是第二元素. ? <a,b>也记作(a,b) ?定理1: <a,b>=<c,d> ? a=c∧b=d ?推论: a≠b ? <a,b>≠<b,a> 《集合论与图论》第5讲4 有序对(引理1) ?引理1: {x,a}={x,b} ? a=b 证明: (?) 显然. (?) 分两种情况. (1) x=a. {x,a}={x,b} ? {a,a}={a,b} ? {a}={a,b} ? a=b. (2) x≠a. a∈{x,a}={x,b} ? a=b. # 《集合论与图论》第5讲5 有序对(引理2) ?引理2: 若A=B ≠?, 则 (1) ∪A=∪B (2)∩A=∩B 证明: (1) ?x, x∈∪A ??z(z∈A ∧ x∈z) ??z(z∈B ∧ x∈z) ? x∈∪B. (2) ?x, x∈∩A ??z( z∈A → x∈z ) ??z( z∈B → x∈z ) ? x∈∩B. # 《集合论与图论》第5讲6 有序对(定理1) ?定理1: <a,b>=<c,d> ? a=c∧b=d 证明: (?) 显然. (?) 由引理2, <a,b>=<c,d> ? {{a},{a,b}}={{c},{c,d}} ?∪{{a},{a,b}}=∪{{c},{c,d}}?{a,b}={c,d}. 又{{a},{a,b}}={{c},{c,d}} ?∩{{a},{a,b}}=∩{{c},{c,d}} ? {a}={c} ? a=c. 再由引理1, 得b=d. # 《集合论与图论》第5讲7 有序对(推论) ?推论: a≠b ? <a,b>≠<b,a> 证明: (反证) <a,b>=<b,a>?a=b, 与a≠b矛盾. # 《集合论与图论》第5讲8 有序三元组(ordered triple) ?有序三元组: <a,b,c>=<<a,b>,c> ?有序n(≥2)元组: <a 1 ,a 2 ,…,a n >=<<a 1 ,a 2 ,…,a n-1 >,a n > ?定理2: <a 1 ,a 2 ,…,a n >= <b 1 ,b 2 ,…,b n > ? a i = b i , i =1,2,…,n. # 《集合论与图论》第5讲9 卡氏积(Cartesian product) ?卡氏积: A×B={<x,y>|x∈A∧y∈B}. ?例: A={?,a}, B={1,2,3}. A×B={<?,1>,<?,2>,<?,3>,<a,1>,<a,2>,<a,3>}. B×A={<1,?>,<1,a>,<2,?>,<2,a>,<3,?>,<3,a>}. A×A={ <?,?>, <?,a>, <a,?>, <a,a>}. B×B={ <1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>, <3,1>,<3,2>,<3,3> }. # 《集合论与图论》第5讲10 卡氏积的性质 ?非交换: A×B ≠ B×A (除非A=B ∨ A=?∨B=?) ?非结合: (A×B)×C ≠ A×(B×C) (除非A=?∨B=?∨C=?) ?分配律: A×(B∪C) = (A×B)∪(A×C)等 ?其他: A×B=??A=?∨B=?等 《集合论与图论》第5讲11 卡氏积非交换性 ?非交换: A×B ≠ B×A (除非A=B ∨ A=?∨B=?) ?反例: A={1}, B={2}. A×B={<1,2>}, B×A={<2,1>}. 《集合论与图论》第5讲12 卡氏积非结合性 ?非结合: (A×B)×C ≠ A×(B×C) (除非A=?∨B=?∨C=?) ?反例: A=B=C={1}. (A×B)×C={<<1,1>,1>}, A×(B×C)={<1,<1,1>>}. 《集合论与图论》第5讲13 卡氏积分配律 ?1. A×(B∪C) = (A×B)∪(A×C) ?2. A×(B∩C) = (A×B)∩(A×C) ?3. (B∪C)×A = (B×A)∪(C×A) ?4. (B∩C)×A = (B×A)∩(C×A) 《集合论与图论》第5讲14 卡氏积分配律(证明1) ?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). # 《集合论与图论》第5讲15 例题1 ?例题1: 设A,B,C,D是任意集合, (1) A×B=??A=?∨B=? (2) 若A≠?, 则A×B?A×C ? B?C. (3) A?C ∧ B?D ? A×B?C×D, 并且当(A=B=?)∨(A≠?∧B≠?)时, A×B?C×D ? A?C∧B?D. 《集合论与图论》第5讲16 卡氏积图示 A B C A×(B∪C) = (A×B)∪(A×C) A?C∧B?D?A×B?C×D B A C D 《集合论与图论》第5讲17 例题1(证明(2)) (2) 若A≠?, 则A×B?A×C ? B?C. 证明: (?) 若B=?, 则B?C. 设B≠?, 由A≠?, 设x∈A. ?y, y∈B?<x,y>∈A×B ?<x,y>∈A×C ? x∈A∧y∈C ?y∈C. ∴B?C 《集合论与图论》第5讲18 例题1(证明(2),续) (2) 若A≠?, 则A×B?A×C?B?C. 证明(续): (?)若B=?,则A×B=??A×C. 设B≠?. ?<x,y>, <x,y>∈A×B ? x∈A∧y∈B ? x∈A∧y∈C ? <x,y>∈A×C ∴ A×B?A×C. # 讨论: 在(?)中不需要条件A≠?. 《集合论与图论》第5讲19 n维卡氏积 ?n维卡氏积: A 1 ×A 2 ×…×A n = { <x 1 ,x 2 ,…,x n > | x 1 ∈A 1 ∧x 2 ∈A 2 ∧…∧x n ∈A n } ?A n = A×A×…×A ?|A i |=n i ,i =1,2,…,n ? |A 1 ×A 2 ×…×A n | = n 1 ×n 2 ×…×n n . ?n维卡氏积性质与2维卡氏积类似. 《集合论与图论》第5讲20 n维卡氏积(性质) ?非交换: A×B×C≠B×C×A (要求A,B,C均非空,且互不相等) ?非结合: (非2元运算) ?分配律: 例如 A×B×(C∪D)=(A×B×C)∪(A×B×D) ?其他: 如A×B×C=??A=?∨B=?∨C=?. 《集合论与图论》第5讲21 二元关系 ? n元关系 ?二元关系 ?A到B的二元关系 ?A上的二元关系 ?一些特殊关系 《集合论与图论》第5讲22 n元关系(n-ary relation) ?n元关系: 是集合, 其元素全是有序n元组. ?例1: F 1 ={<a,b,c,d>,<1,2,3,4>, <物理,化学,生物,数学>}, F 1 是4元关系. ?例2: F 2 ={<a,b,c>,<α,β,γ>, <大李,小李,老李>} F 2 是3元关系. # 《集合论与图论》第5讲23 二元关系(binary relation) ? 2元关系(简称关系): 是集合,其元素全是有序对. ?例3:R 1 ={<1,2>,<α,β>,<a,b>} R 1 是2元关系. ?例4:R 2 ={<1,2>,<3,4>,<白菜,小猫>} R 2 是2元关系. ?例5: A={<a,b>,<1,2,3>,a,α,1} A不是关系. # 《集合论与图论》第5讲24 二元关系的记号 ?设F是二元关系, 则 <x,y>∈F ? x与y具有F关系? xFy ?对比: xFy(中缀(infix)记号) F(x,y) (前缀(prefix)记号) <x,y>∈F (后缀(suffix)记号) ?例如: 2<15 ? <(2,15) ? <2,15>∈<. 《集合论与图论》第5讲25 A到B的二元关系 ?A到B的二元关系: 是A×B的任意子集. R是A到B的二元关系 ? R?A×B ? R∈P(A×B) ?若|A|=m,|B|=n, 则|A×B|=mn, 故 |P(A×B)|=2 mn 即A到B不同的二元关系共有2 mn 个 2 2 m 《集合论与图论》第5讲26 A到B的二元关系(举例) ?例: 设A={a 1 ,a 2 }, B={b}, 则A到B的二元关系共有4个: R 1 =?, R 2 ={<a 1 ,b>}, R 3 ={<a 2 ,b>}, R 4 ={<a 1 ,b>,<a 2 ,b>}. B到A的二元关系也有4个: R 5 =?, R 6 ={<b,a 1 >}, R 7 ={<b,a 2 >}, R 8 ={<b,a 1 >,<b,a 2 >}. # 2 2 m 《集合论与图论》第5讲27 A上的二元关系 ?A上的二元关系: 是A×A的任意子集 R是A上的二元关系 ? R?A×A ? R∈P(A×A) ?若|A|=m, 则|A×A|=m 2 , 故 |P(A×A)|= 即A上不同的二元关系共有个 2 2 m 2 2 m 2 2 m 《集合论与图论》第5讲28 A上的二元关系(例1) ?例1: 设A={a 1 ,a 2 }, 则A上的二元关系共有16个: R 1 = ?, R 2 = {<a 1 ,a 1 >}, R 3 = {<a 1 ,a 2 >}, R 4 = {<a 2 ,a 1 >}, R 5 = {<a 2 ,a 2 >}, 2 2 m 《集合论与图论》第5讲29 A上的二元关系(例1,续1) R 6 = { <a 1 ,a 1 >, <a 1 ,a 2 > }, R 7 = { <a 1 ,a 1 >, <a 2 ,a 1 > }, R 8 = { <a 1 ,a 1 >, <a 2 ,a 2 > }, R 9 = { <a 1 ,a 2 >, <a 2 ,a 1 > }, R 10 = { <a 1 ,a 2 >, <a 2 ,a 2 > }, R 11 = { <a 2 ,a 1 >, <a 2 ,a 2 > }, 2 2 m 《集合论与图论》第5讲30 A上的二元关系(例1,续2) R 12 = { <a 1 ,a 1 >,<a 1 ,a 2 >,<a 2 ,a 1 > } R 13 = { <a 1 ,a 1 >,<a 1 ,a 2 >, <a 2 ,a 2 > } R 14 = { <a 1 ,a 1 >, <a 2 ,a 1 >,<a 2 ,a 2 > } R 15 = { <a 1 ,a 2 >,<a 2 ,a 1 >,<a 2 ,a 2 > } R 16 = {<a 1 ,a 1 >,<a 1 ,a 2 >,<a 2 ,a 1 >,<a 2 ,a 2 >}. # 2 2 m 《集合论与图论》第5讲31 A上的二元关系(例2) ?例2: 设B={b}, 则B上的二元关系共有2个: R 1 =?, R 2 ={<b,b>}. # ?例3: 设C={a,b,c}, 则C上的2元关系共有2 9 =512个! # 2 2 m 《集合论与图论》第5讲32 一些特殊关系 ?空关系 ?恒等关系 ?全域关系 ?整除关系 ?小于等于关系,… ?包含关系, ?真包含关系 《集合论与图论》第5讲33 特殊关系 设A是任意集合, 则可以定义A上的: ?空关系: ? ?恒等关系: I A = { <x,x> | x∈A } ?全域关系: E A = A×A = { <x,y> | x∈A ∧ y∈A} 《集合论与图论》第5讲34 特殊关系(续) 设A?Z, 则可以定义A上的: ?整除关系: D A = { <x,y> | x∈A ∧ y∈A ∧ x|y } ?例: A={1,2,3,4,5,6}, 则D A = {<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>, <2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<4,4>, <5,5>,<6,6>}. # 《集合论与图论》第5讲35 特殊关系(续) 设A?R, 则可以定义A上的: ?小于等于(less than or equal to)关系: LE A = { <x,y> | x∈A ∧ y∈A ∧ x≤y } ?小于(less than)关系, L A = { <x,y> | x∈A ∧ y∈A ∧ x<y } ?大于等于(greater than or equal to)关系 ?大于(great than)关系,… 《集合论与图论》第5讲36 特殊关系(续) 设A为任意集合, 则可以定义P(A)上的: ?包含关系: ? A = { <x,y> | x?A ∧ y?A ∧ x?y } ?真包含关系: ? A = { <x,y> | x?A ∧ y?A ∧ x?y } 《集合论与图论》第5讲37 与二元关系有关的概念 ?定义域, 值域, 域 ?逆, 合成(复合) ?限制, 象 ?单根, 单值 《集合论与图论》第5讲38 定义域,值域,域 对任意集合R, 可以定义: ?定义域(domain) : dom R = { x | ?y(xRy) } ?值域(range): ran R = { y | ?x(xRy) } ?域(field): fld R = dom R ∪ ran R 《集合论与图论》第5讲39 定义域,值域,域图示 A B dom R ran R 《集合论与图论》第5讲40 定义域,值域,域(举例) ?例: R 1 ={a,b}, R 2 ={a,b,<c,d>,<e,f>}, R 3 ={<1,2>,<3,4>,<5,6>}. 当a,b不是有序对时, R 1 和R 2 不是关系. dom R 1 =?, ran R 1 =?, fld R 1 =? dom R 2 ={c,e}, ran R 2 ={d,f}, fld R 2 ={c,d,e,f} dom R 3 ={1,3,5}, ran R 3 ={2,4,6}, fld R 3 ={1,2,3,4,5,6}. # 《集合论与图论》第5讲41 逆, 合成(复合) 对任意集合F,G, 可以定义: ?逆(inverse) : F -1 = { <x,y> | yFx } ?合成(复合)(composite): F○G = { <x,y> | ?z( xGz ∧ zFy) } x z y G F 《集合论与图论》第5讲42 关于合成 ?顺序合成(右合成): F○G = { <x,y> | ?z( xFz ∧ zGy) } ?逆序合成(左合成): F○G = { <x,y> | ?z( xGz ∧ zFy) } 《集合论与图论》第5讲43 限制,象 对任意集合F,A, 可以定义: ?限制(restriction): F↑A = { <x,y> | xFy ∧ x∈A } ?象(image): F[A] = ran(F↑A) F[A] = { y | ?x(x∈A ∧ xRy) } 《集合论与图论》第5讲44 单根,单值 对任意集合F, 可以定义: ?单根(single rooted): F是单根的? ?y( y∈ran F →?!x( x∈dom F ∧ xFy ) ) ? (?y∈ran F)(?!x∈dom F)(xFy) ?单值(single valued): F是单值的? ?x( x∈dom F →?!y( y∈ran F ∧ xFy ) ) ? (?x∈dom F)(?!y∈ran F)(xFy) 《集合论与图论》第5讲45 例题2 ?例2: 设A={a,b,c,d}, B={a,b,<c,d>}, R={ <a,b>, <c,d> }, F={ <a,b>, <a,{a}>, <{a},{a,{a}}> }, G={ <b,e>,<d,c> }. 求: (1) A -1 , B -1 ,R -1 . (2) B○R -1 , G○B, G○R, R○G. (3) F↑{a}, F↑{{a}}, F↑{a,{a}}, F -1 ↑{{a}}. (4) F[{a}], F[{a,{a}}], F -1 [{a}], F -1 [{{a}}]. 《集合论与图论》第5讲46 例题2(解(1)) ?已知: A={a,b,c,d}, B={a,b,<c,d>}, R={ <a,b>, <c,d> }, 求: (1) A -1 , B -1 ,R -1 . 解: (1) A -1 = ?, B -1 = {<d,c>}, R -1 = {<b,a>,<d,c>}. 《集合论与图论》第5讲47 例题2(解(2)) ?已知: B={a,b,<c,d>}, R={ <a,b>, <c,d> }, G={ <b,e>,<d,c> }. 求:(2) B○R -1 , G○B, G○R, R○G. 解: (2) B○R -1 ={<d,d>}, G○B={<c,c>}, G○R={<a,e>,<c,c>}, R○G={<d,d>}. 《集合论与图论》第5讲48 例题2(解(3)) ?已知: F={ <a,b>, <a,{a}>, <{a},{a,{a}}> }, 求: (3) F↑{a}, F↑{{a}}, F↑{a,{a}}, F -1 ↑{{a}}. 解: (3) F↑{a} = { <a,b>, <a,{a}> }, F↑{{a}} = { <{a},{a,{a}}> }, F↑{a,{a}} = F, F -1 ↑{{a}}={ <{a},a> }. 《集合论与图论》第5讲49 例题2(解(4)) ?已知: F={ <a,b>, <a,{a}>, <{a},{a,{a}}> }, 求: (4) F[{a}], F[{a,{a}}], F -1[ {a}], F -1[ {{a}}]. 解: (4) F[{a}] = { b, {a} }, F[{a,{a}}] = { b, {a}, {a,{a}} }, F -1 [{a}] = ?, F -1 [{{a}}] = { a }. # 《集合论与图论》第5讲50 例题3 ?设R={ <x,y> | x,y∈Z ∧ y=|x| }, A={ 0, 1, 2}, B={ 0, -1, -2 } 求: (1) R[A∩B] 和R[A]∩R[B]; (2) R[A]-R[B] 和R[A-B]. 解: (1) R[A∩B]=R[{0}]={0}, R[A]∩R[B]={0,1,2}∩{0,1,2}={0,1,2}; (2) R[A]-R[B]={0,1,2}-{0,1,2}= ?, R[A-B]=R[{1,2}]={1,2}. # 《集合论与图论》第5讲51 定理3 ?定理3: 设F,G是任意集合, 则 (1) dom(F∪G) = domF ∪ domG (2) ran(F∪G) = ranF ∪ ranG (3) dom(F∩G) ? domF ∩ domG (4) ran(F∩G) ? ranF ∩ ranG (5) domF-domG ? dom(F-G) (6) ran F-ranG ? ran(F-G) 《集合论与图论》第5讲52 定理3(证明(1)) ?(1) dom(F∪G) = domF ∪ domG 证明: (1) ?x, x∈dom(F∪G) ??y( x(F∪G)y ) ??y(xFy ∨ xGy) ??y(xFy)∨?y(xGy) ? x∈domF ∨ x∈domG ? x∈ domF ∪ domG ∴ dom(F∪G) = domF ∪ domG. 《集合论与图论》第5讲53 定理3(证明(4)) ?(4) ran(F∩G) ? ranF ∩ ranG 证明: (4) ?x, x∈ran(F∩G) ??y( y(F∩G)x ) ??y(yFx ∧ yGx) ??y(yFx) ∧?y(yGx) ? x∈ranF ∧ x∈ranG ? x∈ ranF ∩ ranG ∴ ran(F ∩ G) ? ranF ∩ ranG. 《集合论与图论》第5讲54 定理3(证明(5)) ?(5) domF-domG ? dom(F-G) 证明: (5) ?x, x∈domF-domG ? x∈domF ∧ x?domG ??y(xFy)∧??y(xGy) ??y(xFy)∧?y(xGy) ??y( x(F-G)y ) ? x∈ dom(F-G) ∴ domF-domG ? dom(F-G). # 《集合论与图论》第5讲55 定理4 ?定理4: 设F是任意集合, 则 (1) domF -1 = ranF; (2) ranF -1 = domF; (3) (F -1 ) -1 ? F, 当F是关系时, 等号成立. 《集合论与图论》第5讲56 定理4(证明(1)) ?(1) domF -1 = ranF; 证明: (1) ?x, x∈domF -1 ??y(xF -1 y) ??y(yFx) ? x∈ranF ∴ domF -1 = ranF. ?(2)可类似证明. 《集合论与图论》第5讲57 定理4(证明(3)) ?(3) (F -1 ) -1 ? F, 当F是关系时, 等号成立. 证明: (1) 设F是关系, 则?<x,y>, <x,y>∈(F -1 ) -1 ? x(F -1 ) -1 y ? yF -1 x ? xFy. 这时(F -1 ) -1 = F. 当F不是关系时, (F -1 ) -1 ?F, 例如, 设F={<a,b>,a}, 则 F -1 ={<b,a>}, (F -1 ) -1 ={<a,b>} ? F ∴ (F -1 ) -1 ? F. # 《集合论与图论》第5讲58 定理5 ?定理5: 设R 1 ,R 2 ,R 3 为集合, 则 (R 1 ○R 2 )○R 3 = R 1 ○(R 2 ○R 3 ) 证明: ?<x,y>, <x,y>∈(R 1 ○R 2 )○R 3 ??z( xR 3 z ∧ z(R 1 ○R 2 )y ) ??z( xR 3 z ∧?t( zR 2 t ∧ tR 1 y ) ) ??z?t( xR 3 z ∧ ( zR 2 t ∧ tR 1 y ) ) ??t?z( xR 3 z ∧ zR 2 t ∧ tR 1 y ) 《集合论与图论》第5讲59 定理5(续) 证明(续): ??t?z( xR 3 z ∧ zR 2 t ∧ tR 1 y ) ??t( ?z( xR 3 z ∧ zR 2 t) ∧ tR 1 y ) ??t( x(R 2 ○R 3 )t ∧ tR 1 y ) ? xR 1 ○(R 2 ○R 3 )y ? <x,y>∈R 1 ○(R 2 ○R 3 ) ∴ (R 1 ○R 2 )○R 3 = R 1 ○(R 2 ○R 3 ). # 说明: 定理5说明合成运算具有结合律. x z t y R 3 R 2 R 1 《集合论与图论》第5讲60 总结 ? 1. 有序对与卡氏积: <a,b>, A×B ? 2. 二元关系: R?A×B, R?A×A; ?, I A , E A ; xRy ? 3. 二元关系的基本运算: dom(R), ran(R), fld(R); R↑A, R[A]; R -1 , R○S 《集合论与图论》第5讲61 作业(#3) ? p80, 习题二, 6, 7, 11, 12