离散数学与 关系3 .ppt

* 《集合论与图论》第7讲 * 定理22 定理22: 设 R?A?A 且 A??, 则 r( R ) = R?IA; 证明: (1) R ? R?IA; (2) IA?R?IA ? R?IA自反 ? r( R )?R?IA; (3) R?r( R ) ? r( R )自反 ? R?r( R ) ? IA? r( R ) ? R?IA ?r( R ) ? r( R ) = R?IA. * 《集合论与图论》第7讲 * 定理23 定理23: 设 R?A?A 且 A??, 则 s( R ) = R?R-1; 证明: (1) R ? R?R-1; (2) (R?R-1)-1=R?R-1 ? R?R-1对称 ? s( R )?R?R-1; (3) R?s( R ) ? s( R )对称 ? R?s( R ) ? R-1?s( R ) ? R?R-1?s( R ) ? s( R ) = R?R-1. * 《集合论与图论》第7讲 * 定理24 定理24: 设 R?A?A 且 A??, 则 t( R ) = R?R2?R3?…; 证明: (1) R ? R?R2?R3?…; (2) (R?R2?R3?…)2 = R2?R3?… ? R?R2?R3?… ? R?R2?R3?…传递 ? t( R )?R?R2?R3?…; (3) R?t( R ) ? t( R )传递 ? R?t( R )?R2?t( R )?R3?t( R )?… ? R?R2?R3?… ? t( R ) ? t( R ) = R?R2?R3?…. * 《集合论与图论》第7讲 * 定理24的推论 推论: 设 R?A?A 且 0|A|?, 则?l ?N, 使得 t( R ) = R?R2?R3?…?Rl ; 证明: 由定理16知 ?s,t?N, 使得 Rs = Rt. 由定理18知 R,R2,R3,…?{ R0,R1,…,Rt-1 }. 取l =t-1, 由定理24知 t( R ) = R?R2?R3?…. = R?R2?R3?…?Rl ? t( R ) = R?R2?R3?…?Rl . # * 《集合论与图论》第7讲 * 例8 例8: 设 A = { a,b,c,d }, R = { a,b,b,a,b,c,c,d }. 求 r( R ), s( R ), t( R ). 解: a b c d * 《集合论与图论》第7讲 * 例8(续) 解(续): a b c d a b c d a b c d * 《集合论与图论》第7讲 * 例8(续2) 解(续2): a b c d * 《集合论与图论》第7讲 * 例8(续3) 解(续3): a b c d * 《集合论与图论》第7讲 * 例8(续4) 解(续4): a b c d a b c d # * 《集合论与图论》第7讲 * 闭包运算是否保持关系性质? 问题: (1) R自反 ? s( R ), t( R )自反 ? (2) R对称 ? r( R ), t( R )对称 ? (3) R传递 ? s( R ), r( R )传递 ? * 《集合论与图论》第7讲 * 定理25 定理25: 设R?A?A且A??,则 (1) R自反 ? s( R )和t( R )自反; (2) R对称 ? r( R )和t( R )对称; (3) R传递 ? r( R )传递; 证明: (1) IA ? R?R-1 = s( R ) ? s( R )自反. IA ? R?R2?R3?… = t( R ) ? t( R )自反. * 《集合论与图论》第7讲 * 定理25(证明(2)) (2) R对称 ? r( R )和t( R )对称; 证明: (2) r( R )-1 =(IA?R)-1 =IA-1?R-1 =IA?R-1 =IA?R= r( R ) ? r( R )对称. t( R )-1 = (R?R2?R3?…)-1 = R-1?(R2)-1?(R3)-1?… = R-1?(R-1)2?(R-1)3?… ( (F○G)-1=G-1○F-1 ) = R?R2?R3?…=t( R ), ? t( R )对称. * 《集合论与图论》第7讲 * 定理25(证明(3)) (2) R传递 ? r( R )传递; 证明: (2) r( R )○r( R ) = (IA?R)○(IA?R) = (IA○IA)?(IA○R)?(R○IA)?(R○R) ? IA?R?R?R =IA?R= r( R ) ?