《集合论与图论》第6讲1 第6讲关系表示与关系性质 内容提要 ?关系运算性质(续) ?关系矩阵, 关系图 ?自反, 反自反, 对称, 反对称, 传递 《集合论与图论》第6讲2 关系基本运算的性质(续) ?定理6~定理9 ?定理6: 设R 1 ,R 2 ,R 3 是集合,则 (1) R 1 ○(R 2 ∪R 3 ) = (R 1 ○R 2 )∪(R 1 ○R 3 ) (2) (R 1 ∪R 2 )○R 3 = (R 1 ○R 3 )∪(R 2 ○R 3 ) (3) R 1 ○(R 2 ∩R 3 ) ? (R 1 ○R 2 )∩(R 1 ○R 3 ) (4) (R 1 ∩R 2 )○R 3 ? (R 1 ○R 3 )∩(R 2 ○R 3 ) 《集合论与图论》第6讲3 定理6(证明(1)) ? (1) R 1 ○(R 2 ∪R 3 ) = (R 1 ○R 2 )∪(R 1 ○R 3 ) ?证明: ?<x,y>, <x,y>∈R 1 ○(R 2 ∪R 3 ) ??z(x(R 2 ∪R 3 )z∧zR 1 y)??z((xR 2 z∨xR 3 z)∧zR 1 y) ??z((xR 2 z∧zR 1 y)∨(xR 3 z∧zR 1 y)) ??z(xR 2 z∧zR 1 y)∨?z(xR 3 z∧zR 1 y) ?x(R 1 ○R 2 )y∨x(R 1 ○R 3 )y?x((R 1 ○R 2 )∪(R 1 ○R 3 ))y ?<x,y>∈(R 1 ○R 2 )∪(R 1 ○R 3 ) 《集合论与图论》第6讲4 定理6(证明(3)) ? (3) R 1 ○(R 2 ∩R 3 ) ? (R 1 ○R 2 )∩(R 1 ○R 3 ) ?证明: ?<x,y>, <x,y>∈R 1 ○(R 2 ∩R 3 ) ??z(x(R 2 ∩R 3 )z∧zR 1 y)??z((xR 2 z∧xR 3 z)∧zR 1 y) ??z((xR 2 z∧zR 1 y)∧(xR 3 z∧zR 1 y)) ??z(xR 2 z∧zR 1 y)∧?z(xR 3 z∧zR 1 y) ?x(R 1 ○R 2 )y∧x(R 1 ○R 3 )y?x((R 1 ○R 2 )∩(R 1 ○R 3 ))y ?<x,y>∈(R 1 ○R 2 )∩(R 1 ○R 3 ). # 《集合论与图论》第6讲5 定理6(讨论(3)) ?(3) R 1 ○(R 2 ∩R 3 ) ? (R 1 ○R 2 )∩(R 1 ○R 3 ) ?反例(说明=不成立): 设R 1 ={<b,d>,<c,d>}, R 2 ={<a,b>}, R 3 ={<a,c>}. 则R 1 ○(R 2 ∩R 3 ) = R 1 ○? = ?, R 1 ○R 2 ={<a,d>}, R 1 ○R 3 ={<a,d>}, (R 1 ○R 2 )∩(R 1 ○R 3 )={<a,d>}. # a b c d 《集合论与图论》第6讲6 定理7 ?定理7: 设F,G为二集合, 则 (F○G) -1 = G -1 ○F -1 . G G -1 F F -1 《集合论与图论》第6讲7 定理7(证明) ?(F○G) -1 = G -1 ○F -1 ?证明: ?<x,y>, <x,y>∈(F○G) -1 ? <y,x>∈(F○G) ??z(yGz∧zFx)??z(zG -1 y∧xF -1 z) ??z((xF -1 z∧zG -1 y) ? <x,y>∈G -1 ○F -1 . # xy z 《集合论与图论》第6讲8 定理8 ?定理8: 设R,S,A,B,A,为集合,A≠?,则 (1) R↑(A∪B) = (R↑A)∪(R↑B); (2) R↑∪A = ∪{ R↑A | A∈A}; (3) R↑(A∩B) = (R↑A)∩(R↑B); (4) R↑∩A = ∩{ R↑A | A∈A}; (5) (R○S)↑A = R○(S↑A). 《集合论与图论》第6讲9 定理8(证明(2)) ?(2) R↑∪A = ∪{ R↑A | A∈A}; ?证明: ?<x,y>, x(R↑∪A)y ? xRy∧x∈∪A ? xRy ∧?A( A∈A ∧ x∈A ) ??A( xRy ∧x∈A ∧A∈A ) ??A( x(R↑A)y ∧ A∈A ) ? x(∪{ R↑A | A∈A} )y. ∴ R↑∪A = ∪{ R↑A | A∈A} 《集合论与图论》第6讲10 定理8(证明(4)) ? (4) R↑∩A = ∩{ R↑A | A∈A}; (A≠?) ?证明:?<x,y>, x(R↑∩A)y ? xRy∧x∈∩A ?(0∨xRy)∧x∈∩A ?(?A(?A∈A)∨xRy)∧x∈∩A ??A(?A∈A∨xRy)∧?A(A∈A→x∈A) ??A((?A∈A∨xRy)∧(?A∈A∨x∈A)) ??A(?A∈A∨((xRy)∧ x∈A))??A(?A∈A)∨x(R↑A)y) ??A(A∈A→x(R↑A)y)? x(∩{ R↑A | A∈A} )y. ∴ R↑∩A = ∩{ R↑A | A∈A} 《集合论与图论》第6讲11 定理8(证明(5)) ? (5) (R○S)↑A = R○(S↑A) ?证明: ?<x,y>, x((R○S)↑A)y ? x(R○S)y ∧ x∈A ??z(xSz∧zRy ) ∧ x∈A ??z(xSz∧zRy ∧ x∈A) ??z((xSz∧x∈A) ∧ zRy ) ??z( x(S↑A)z ∧ zRy ) ? x(R○(S↑A))y. ∴ R↑∪A = ∪{ R↑A | A∈A}. # 《集合论与图论》第6讲12 定理9 ?定理9: 设R,S,A,B,A,为集合,A≠?,则 (1) R[A∪B] = R[A]∪R[B]; (2) R[∪A]= ∪{ R[A] | A∈A }; (3) R[A∩B] ? R[A]∩R[B]; (4) R[∩A] ?∩{ R[A] | A∈A}; (5) R[A]-R[B] ? R[A-B]; (6) (R○S)[A] = R[S[A]]. 《集合论与图论》第6讲13 定理9(证明(2)) ?(2) R[∪A] = ∪{ R[A] | A∈A }; ?证明: ?y, y∈R[∪A] ??x(xRy∧x∈∪A) ??x( xRy ∧?A( A∈A ∧ x∈A) ??A( A∈A ∧?x( xRy ∧ x∈A ) ) ??A(A∈A∧y∈R[A]) ? y∈∪{ R[A] | A∈A }. ∴ R↑∪A = ∪{ R↑A | A∈A}. 《集合论与图论》第6讲14 定理9(证明(4)) ? (4) R[∩A] ?∩{ R[A] | A∈A}; ?证明: ?y, y∈R[∩A] ??x(xRy∧x∈∩A) ??x(xRy∧?A(A∈A→x∈A)) ??x?A(xRy∧(A∈A→x∈A)) ??A?x(xRy∧(A∈A→x∈A)) (*) ??A?x(A∈A→(xRy∧x∈A)) (**) ??A(A∈A→?x(xRy∧x∈A))??A(A∈A→y∈R[A]) ?y∈∩{ R[A] | A∈A }. ∴ R[∩A] ?∩{ R[A] | A∈A}. 《集合论与图论》第6讲15 定理9(证明(4),续) ?(*) ?x?A(xRy∧(A∈A→x∈A)) ??A?x(xRy∧(A∈A→x∈A)) ?(**) ?A?x(xRy∧(A∈A→x∈A)) ??A?x(A∈A→(xRy∧x∈A)) 容易证明: ?(*) ?x?yB(x,y) ? ?y?xB(x,y) ?(**) p∧(q→r) ? q→(p∧r) 《集合论与图论》第6讲16 定理9(证明(4),续) ?(*) ?x?yB(x,y) ? ?y?xB(x,y) ?证明: 在任何解释下, 若左?1, 则右?1. 《集合论与图论》第6讲17 定理9(证明(4),续) ?(**) p∧(q→r) ? q→(p∧r) ?证明1: (p∧(q→r))→(q→(p∧r))是永真式 真值表, 等值演算 ?证明2: (反证) 设“左?1”且“右?0” 即p∧(q→r)?1且q→(p∧r)?0. 由p∧(q→r)?1得p=1, q→r=1; 由q→(p∧r)?0得q=1, p∧r=0; 所以r=0, q→r=0, 矛盾! # 《集合论与图论》第6讲18 定理9(证明(5)) ? (5) R[A]-R[B] ? R[A-B]; ?证明: ?y, y∈R[A]-R[B] ? y∈R[A]∧?y∈R[B] ??x(xRy∧x∈A) ∧??x(xRy∧x∈B) ??x(xRy∧x∈A) ∧?x(?xRy∨?x∈B) ??x(xRy∧x∈A) ∧?x(xRy→?x∈B) ? ?x(xRy∧x∈A∧?x∈B) ??x(xRy∧x∈A-B) ? y∈R[A-B]. ∴ R[A]-R[B] ? R[A-B]. 《集合论与图论》第6讲19 定理9(证明(5),续) ?x(xRy∧x∈A) ∧?x(xRy→?x∈B) ? ?x(xRy∧x∈A∧?x∈B) 前提: ?x(xRy∧x∈A), ?x(xRy→?x∈B) 结论: ?x(xRy∧x∈A∧?x∈B) 证明: (1) ?x(xRy∧x∈A), 前提引入 (2) cRy∧c∈A, (1)EI (3) ?x(xRy→?x∈B), 前提引入 (4) cRy→?c∈B, (3)UI 《集合论与图论》第6讲20 定理9(证明(5),续) 前提: ?x(xRy∧x∈A), ?x(xRy→?x∈B) 结论: ?x(xRy∧x∈A∧?x∈B) 证明: (1) ?x(xRy∧x∈A), 前提引入 (2) cRy∧c∈A, (1)EI (3) ?x(xRy→?x∈B), 前提引入 (4) cRy→?c∈B, (3)UI (5) cRy, (2)化简 (6) ?c∈B, (4)(5)假言推理 《集合论与图论》第6讲21 定理9(证明(5),续) 证明: (1) ?x(xRy∧x∈A), 前提引入 (2) cRy∧c∈A, (1)EI (3) ?x(xRy→?x∈B), 前提引入 (4) cRy→?c∈B, (3)UI (5) cRy, (2)化简 (6) ?c∈B, (4)(5)假言推理 (7) cRy∧c∈A∧?c∈B, (2)(6)合取 (8) ?x(xRy∧x∈A∧?x∈B) (7)EG. # 《集合论与图论》第6讲22 定理9(证明(6)) ?(6) (R○S)[A] = R[S[A]]. ?证明:?y, y∈(R○S)[A] ??x( x(R○S)y ∧ x∈A ) ??x( ?z( xSz ∧ zRy ) ∧ x∈A ) ??z( zRy ∧?x( xSz ∧ x∈A ) ) ??z( zRy ∧ z∈S[A]) ? y∈ R[S[A]]. ∴ (R○S)[A] = R[S[A]]. # 《集合论与图论》第6讲23 定理9(讨论) ?讨论: 当R为单根关系时, (3)(4)(5)中等号 成立. (3) R[A∩B] ? R[A]∩R[B]; (4) R[∩A] ?∩{ R[A] | A∈A}; (5) R[A]-R[B] ? R[A-B]; 《集合论与图论》第6讲24 关系表示法 关系的表示方法: ?集合 ?关系矩阵 ?关系图 《集合论与图论》第6讲25 关系矩阵(matrix) ?设A={a 1 ,a 2 ,…,a n }, R?A×A, 则R的关系 矩阵M(R)=(r ij ) n×n , 其中 ?例如, A={a,b,c}, R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, 则 # ? ? ? = 否则,0 ,1 ji ij Rxx r . 000 100 110 )( 2 ? ? ? ? ? ? ? ? ? ? =RM, 000 101 011 )( 1 ? ? ? ? ? ? ? ? ? ? =RM 《集合论与图论》第6讲26 关系矩阵的性质 ?R的集合表达式与R的关系矩阵可以唯一 相互确定 ?M(R -1 ) = (M(R)) T . ( T 表示矩阵转置) ?M(R 1 ○R 2 ) = M(R 2 )?M(R 1 ). (?表示这样 的矩阵“乘法”, 其中加法使用逻辑∨, 乘法 使用逻辑∧. ) 《集合论与图论》第6讲27 例题4 ?例题4: 设A={a,b,c}, R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, 用M(R 1 ), M(R 2 )确定M(R 1 -1 ), M(R 2 -2 ), M(R 1 ○R 1 ), M(R 1 ○R 2 ), M(R 2 ○R 1 ), 从而求出它们的集合表达式. 《集合论与图论》第6讲28 例题4(解) ?R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, ?解: R 1 -1 = {<a,a>,<a,b>,<b,a>,<c,b>} R 2 -1 = {<b,a>,<c,a>,<c,b>} . 000 100 110 )( 2 ? ? ? ? ? ? ? ? ? ? =RM, 000 101 011 )( 1 ? ? ? ? ? ? ? ? ? ? =RM . 011 001 000 )( 1 2 ? ? ? ? ? ? ? ? ? ? = ? RM, 010 001 011 )( 1 1 ? ? ? ? ? ? ? ? ? ? = ? RM 《集合论与图论》第6讲29 例题4(解,续) ?R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, ?解(续): R 1 ○R 1 = {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}. . 000 100 110 )( 2 ? ? ? ? ? ? ? ? ? ? =RM, 000 101 011 )( 1 ? ? ? ? ? ? ? ? ? ? =RM , 000 011 111 000 101 011 000 101 011 )( 11 ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =RRM o 《集合论与图论》第6讲30 例题4(解,续) ?R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, ?解(续): R 1 ○R 2 = {<a,a>,<a,c>}. . 000 100 110 )( 2 ? ? ? ? ? ? ? ? ? ? =RM, 000 101 011 )( 1 ? ? ? ? ? ? ? ? ? ? =RM , 000 000 101 000 101 011 000 100 110 )( 21 ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =RRM o 《集合论与图论》第6讲31 例题4(解,续) ?R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, ?解(续): R 2 ○R 1 = {<a,b>,<a,c>,<b,b>,<b,c>}. # . 000 100 110 )( 2 ? ? ? ? ? ? ? ? ? ? =RM, 000 101 011 )( 1 ? ? ? ? ? ? ? ? ? ? =RM , 000 110 110 000 100 110 000 101 011 )( 12 ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =RRM o 《集合论与图论》第6讲32 关系图(graph) ?设A={a 1 ,a 2 ,…,a n }, R?A×A, 则A中元素 以“○”表示(称为顶点), R中元素以“→”表 示(称为有向边); 若x i Rx j , 则从顶点x i 向顶 点x j 引有向边<x i ,x j >, 这样得到的图称为R 的关系图G(R). ?例如, A={a,b,c}, R 1 ={<a,a>,<a,b>,<b,a>,<b,c>}, R 2 ={<a,b>,<a,c>,<b,c>}, 则 ab c ab c G(R 1 ) G(R 2 ) 《集合论与图论》第6讲33 关系图(举例) R 1 -1 = {<a,a>,<a,b>,<b,a>,<c,b>} R 2 -1 = {<b,a>,<c,a>,<c,b>} ab c G(R 2 -1 ) c G(R 1 -1 ) ab 《集合论与图论》第6讲34 关系图(举例,续) R 1 ○R 1 = {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}. R 1 ○R 2 = {<a,a>,<a,c>}. R 2 ○R 1 = {<a,b>,<a,c>,<b,b>,<b,c>}. a b c G(R 1 ○ R 2 ) c G(R 1 ○R 1 ) ab c G(R 2 ○R 1 ) ab 《集合论与图论》第6讲35 关系矩阵,关系图(讨论) ?当A中元素标定次序后, R?A×A的关系图 G(R)与R的集合表达式可以唯一互相确 定 ?R的集合表达式,关系矩阵,关系图三者均 可以唯一互相确定 ?对于R?A×B, |A|=n,|B|=m,关系矩阵M(R) 是n×m阶的,关系图G(R)中的边都是从A 中元素指向B中元素的. 《集合论与图论》第6讲36 关系性质 ?自反性(reflexivity) ?反自反性(irreflexivity) ?对称性(symmetry) ?反对称性(antisymmetry) ?传递性(transitivity) 《集合论与图论》第6讲37 自反性(reflexivity) ?设R?A×A, 说R是自反的(reflexive),如果 ?x( x∈A → xRx ). ? R是非自反的??x( x∈A ∧?xRx) ?定理10: R是自反的 ? I A ?R ? R -1 是自反的 ? M( R )主对角线上的元素全为1 ? G( R )的每个顶点处均有环. # 《集合论与图论》第6讲38 自反性(举例) 《集合论与图论》第6讲39 反自反性(irreflexivity) ?设R?A×A, 说R是反自反的(irreflexive), 如果 ?x(x∈A→?xRx). ? R是非反自反的??x( x∈A ∧ xRx) ?定理11: R是反自反的 ? I A ∩R=? ? R -1 是反自反的 ? M( R )主对角线上的元素全为0 ? G( R )的每个顶点处均无环. # 《集合论与图论》第6讲40 反自反性(举例) 《集合论与图论》第6讲41 自反,自反性(分类) 自反 反自反 非自反, 非反自反 自反且反 自反? ?上的空关系 《集合论与图论》第6讲42 对称性(symmetry) ?设R?A×A, 说R是对称的(symmetric),如果 ?x?y(x∈A∧y∈A∧xRy→yRx). ? R非对称??x?y(x∈A∧y∈A∧xRy∧?yRx) ?定理12: R是对称的 ? R -1 =R ? R -1 是对称的 ? M( R )是对称的 ? G( R )的任何两个顶点之间若有边, 则必 有两条方向相反的有向边. # 《集合论与图论》第6讲43 对称性(举例) 《集合论与图论》第6讲44 反对称性(antisymmetry) ?设R?A×A, 说R是反对称的(antisymmetric),若 ?x?y(x∈A∧y∈A∧xRy∧yRx→x=y). ? R非反对称??x?y(x∈A∧y∈A∧xRy∧yRx∧x≠y) ?定理13: R是反对称的 ? R -1 ∩R?I A ? R -1 是反对称的 ?在M( R )中, ?i?j(i≠j∧r ij =1→r ji =0) ?在G( R )中, ?x i ?x j (i≠j), 若有有向边 <x i ,x j >, 则必没有<x j ,x i >. # 《集合论与图论》第6讲45 反对称性(举例) 《集合论与图论》第6讲46 对称,反对称(分类) 对称 反对称 非对称, 非反对称 对称且反 对称? 《集合论与图论》第6讲47 传递性(transitivity) ?设R?A×A, 说R是传递的(transitive), 如果 ?x?y?z(x∈A∧y∈A∧z∈A∧xRy∧yRz→xRz). ? R非传递? ?x?y?z(x∈A∧y∈A∧z∈A∧xRy∧yRz∧?xRz) ?定理14: R是传递的 ? R○R?R ? R -1 是传递的 ?在M(R○R)中, ?i?j,若r ij ’ =1,则M( R )中相 应的元素r ij =1. ?在G( R )中, ?x i ?x j ?x k , 若有有向边 <x i ,x j >,<x j ,x k >,则必有有向边<x i ,x k >. # 《集合论与图论》第6讲48 传递性(举例) 《集合论与图论》第6讲49 传递(分类) 非传递 传递 《集合论与图论》第6讲50 举例 ?在N = {0,1,2,…} 上: ?≤={<x,y>|x∈N∧y∈N∧x≤y}自反,反对称,传递 ?≥={<x,y>|x∈N∧y∈N∧x≥y}自反,反对称,传递 ? <={<x,y>|x∈N∧y∈N∧x<y}反自反,反对称,传递 ? >={<x,y>|x∈N∧y∈N∧x>y}反自反,反对称,传递 ? |={<x,y>|x∈N∧y∈N∧x|y}反对称,传递(?0|0) ? I N ={<x,y>|x∈N∧y∈N∧x=y}自反,对称,反对称, 传递 ? E N ={<x,y>|x∈N∧y∈N}=N×N自反,对称,传递. # 《集合论与图论》第6讲51 例5 ?例5: A={a,b,c} R 1 ={<a,a>,<a,b>,<b,c>,<a,c>}, R 2 ={<a,a>,<a,b>,<b,c>,<c,a>}, R 3 ={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>}, R 4 ={<a,a>,<a,b>,<b,a>,<c,c>}, R 5 ={<a,a>,<a,b>,<b,b>,<c,c>}, R 6 ={<a,b>,<b,a>,<b,c>,<a,a>}, 《集合论与图论》第6讲52 例5(续) R 1 ={<a,a>,<a,b>,<b,c>,<a,c>}反对称,传递 R 2 ={<a,a>,<a,b>,<b,c>,<c,a>}反对称 G(R 1 ) a cb G(R 2 ) a cb 《集合论与图论》第6讲53 例5(续) R 3 ={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>}自反, 对称,传递 R 4 ={<a,a>,<a,b>,<b,a>,<c,c>}对称 G(R 3 ) a cb G(R 4 ) a cb 《集合论与图论》第6讲54 例5(续) R 5 ={<a,a>,<a,b>,<b,b>,<c,c>}自反,反对称, 传递 R 6 ={<a,b>,<b,a>,<b,c>,<a,a>}. # G(R 5 ) a cb G(R 6 ) a cb 《集合论与图论》第6讲55 关系运算是否保持关系性质 ?定理15: 设R 1 ,R 2 ?A×A都具有某种性质. √ (3‘) ~R 1 ,~R 2 √√ (3) √R 1 -R 2 ,R 2 -R 1 √ (1) R 1 ○R 2 ,R 2 ○R 1 √ (5) √√√ (2) √R 1 ∩R 2 √ √ 反自反 √ √ 自反 √R 1 ∪R 2 √√ (4) √R 1 -1 ,R 2 -1 传递对称反对称 《集合论与图论》第6讲56 定理15(证明(1)) ?(1) R 1 ,R 2 自反? R 1 ○R 2 自反. ?证明:?x, x∈A ? xR 2 x ∧ xR 1 x ? xR 1 ○R 2 x ∴ R 1 ,R 2 自反? R 1 ○R 2 自反. # 《集合论与图论》第6讲57 定理15(证明(2)) ?(2) R 1 ,R 2 反自反? R 1 ∩R 2 反自反. ?证明: (反证) 若R 1 ○R 2 非反自反, 则 ?x∈A, x(R 1 ∩R 2 )x ? xR 1 x ∧ xR 2 x 与R 1 ,R 2 反自反矛盾! ∴ R 1 ,R 2 反自反? R 1 ∩R 2 反自反. # 《集合论与图论》第6讲58 定理15(证明(3)) ?(3) R 1 ,R 2 对称? R 1 -R 2 对称. ?证明:?x,y∈A, x(R 1 -R 2 )y ? xR 1 y ∧?xR 2 y ? yR 1 x ∧?yR 2 x ? y(R 1 -R 2 )x ∴ R 1 ,R 2 对称? R 1 -R 2 对称. # 《集合论与图论》第6讲59 定理15(证明(3‘)) ?(3‘) R 1 对称? ~R 1 对称. ?证明: ?x,y∈A, x(~R 1 )y ? x(E A -R 1 )y ? xE A y ∧?xR 1 y ? yE A x ∧?yR 1 x ? y(E A -R 1 )x ? y(~R 1 )x ∴ R 1 对称? ~R 1 对称. # 《集合论与图论》第6讲60 定理15(证明(4)) ?(4) R 1 反对称? R 1 -1 反对称. ?证明: (反证) 若R 1 -1 非反对称, 则 ?x,y∈A, xR 1 -1 y ∧ yR 1 -1 x ∧ x≠y ? yR 1 x ∧ xR 1 y ∧ x≠y 与R 1 反对称矛盾! ∴ R 1 反对称? R 1 -1 反对称. # 《集合论与图论》第6讲61 定理15(证明(5)) ?(5) R 1 ,R 2 传递? R 1 ∩R 2 传递. ?证明:?x,y,z∈A, x(R 1 ∩R 2 )y ∧ y(R 1 ∩R 2 )z ? xR 1 y ∧ xR 2 y ∧ yR 1 z ∧ yR 2 z ? xR 1 y ∧ yR 1 z ∧ xR 2 y ∧ yR 2 z ? xR 1 z ∧ xR 2 z ? x(R 1 ∩R 2 )z ∴ R 1 ,R 2 传递? R 1 ∩R 2 传递. # 《集合论与图论》第6讲62 总结 ?关系矩阵, 关系图 ?自反, 反自反, 对称, 反对称, 传递 《集合论与图论》第6讲63 作业(#4) ?p81, 习题二, 15, 16, 17, 22, 23 ?下周一(3月3日)交作业#1,#2,#3,#4