离散数学总复习spring.ppt

b) R∩S是等价关系. 证明：1. 证明R∩S的自反性 方法1 用自反定义证：任取 x∈A, (证出x,x∈R∩S) 因R和S都自反，所以有x,x∈R，x,x∈S，于是有 x,x∈R∩S，所以R∩S也自反。 方法2 用恒等关系IA证：(证出IA ?R) 因R和S都自反，所以 IA ?R ，IA ?S，所以IA ?R∩S 所以R∩S也自反。 方法3 用自反闭包证： (证出r(R∩S)=R∩S, 即 (R∩S)∪IA= R∩S) 因R和S都自反，所以r(R)=R, r(S)=S, r(R∩S)=(R∩S)∪IA= (R∪IA)∩(S∪IA) =r(R)∩r(S)=R∩S 所以R∩S也自反。 2.证明R∩S的对称性： 方法1 用对称定义证： 任取 x,y∈A,设x,y∈R∩S, (证出 y,x∈R∩S.) 则x,y∈R，x,y∈S，因为R和S对称，所以有 y,x∈R，y,x∈S，于是y,x∈R∩S。∴R∩S对称。 方法2 用求逆关系证：(证出 (R∩S)c=R∩S.) 因为R和S对称，所以有Rc=R， Sc=S，而 (R∩S)c=Rc∩Sc= R∩S ， ∴R∩S对称。 方法3 用对称闭包证： (证出 s(R∩S)=R∩S, ) 因为R和S对称，所以s(R)=R,s(S)=S s(R∩S)= (R∩S)∪(R∩S)c =(R∩S)∪(Rc∩Sc) =(R∪Rc)∩(R∪Sc)∩(S∪Sc)∩(S∪Rc) =(s(R)∩(R∪Sc))∩(s(S)∩(S∪Rc)) =(R∩(R∪Sc))∩(S∩(S∪Rc))=R∩S (吸收律) ∴R∩S对称。 3.证明R∩S的传递性： 方法1 用传递定义证：任取 x,y,z∈A, 设x,y∈R∩S,y,z∈R∩S, (证出x,z∈R∩S) x,y∈R∩S∧y,z∈R∩S ? x,y∈R∧x,y∈S∧y,z∈R∧y,z∈S ? (x,y∈R∧y,z∈R)∧(x,y∈S ∧y,z∈S) ? x,z∈R∧x,z∈S （因为R、S传递） ? x,z∈R∩S 所以R∩S传递。 所以R∩S是A上等价关系. e)证明. R2是等价关系. 方法1.如果R自反和传递,则R2 =R, 所以 R2也是等价关系. 方法2.①证R2自反: 任取a∈A,因为R自反,所以a,a∈R,根据关系的复合得, a,a∈R R, 即a,a∈R2,所以R2自反。 ②证R2对称: (R2)c=(Rc)2=R2 (由R对称得Rc=R) ∴R2对称 ③证R2传递: 任取a,b,c∈A,设有a,b∈R2,b,c∈R2, 根据关系的复合得, (?d∈A∧a,d∈R∧d,b∈R)∧(?e∈A∧b,e∈R∧e,c∈R) , 由于R传递,所以有a,b∈R,b,c∈R, ∴a,c∈R2 所以R2传递。 最后得R2是等价关系。 g). R是A上等价关系,则Rc也是A上等价关系. 证明1) 证Rc自反。 因为任取x∈A,因R自反，所以x,x∈R,∴ x,x∈ Rc 2) R对称，证Rc也对称。 因为R对称，所以Rc =R ∴ Rc也对称。 3) R传递，证Rc也传递。 方法1 .任取x,y,z∈A, 且有x,y∈Rc ,y,z∈Rc, 于是 y,x∈R ,z,y∈R，因R传递，∴z,x∈R,于是有 x,z∈Rc，∴ Rc传递。 方法2. t(Rc)=Rc∪(Rc)2∪(Rc)3∪… = Rc∪(R2)c∪(R3)c∪…= (R∪R2∪R3∪…)c = (t(R))c=Rc 所以Rc传递。 所以Rc是A上等价关系. 练习2.五.设X={1,2,3} Y={1,2}, 在X的幂集P(X)上定义二元关系R如下: 对于任何A,B∈P(X), ARB 当且仅当 A?Y=B?Y 1.画出关系R的有向图. 2.R是等价关系吗?如果是,请写出商集P(X)/R. 如果不是请说明原因 解.1.关系R的有向图. 2. 从R有向图看出R有自反,对称和传递性,故是等价关系 P(X)/R={{?,{1},{2},{1,2}},{{3},{1,3},{2,3},{1,2,3}}} ?{1,3} ?{1,2,3} {2,3}? {3}? ?? ?{1} {2}? ?{1,2} 五.偏序关系判断,会画Hasse图,会求一个子集的极小 (大)元,最小(大)元,上界与下界,最小上界及最大下界. 1. 定义：R是A上自反、反对称和传递的关系，则称R 是A上的偏序关系。并称A,R是偏序集。 2. x与y是可比较的：A,≤是偏序集，x,y∈A，如果要 么x≤y,要么y≤x, 则称x与y是可比较的。 3