离散数学(元关系)课后总结.doc

第四章 二元关系 例1 设A={0,1}，B={a,b}，求A′B ， B′A，A′A 。 解： A′B={0,a,0,b,1,a,1,b} B′A={a,0,b,0,a,1,b,1} A′A={0,0,0,1,1,0,1,1} 可见 A×B≠B×A 例2、关于笛卡尔乘积的几个证明 1）如果A、B都是有限集，且|A|=m, |B|=n，则 |A′B |=mn. 证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。 2) A′Φ=Φ′B=Φ 3) ′对∪和∩满足分配律。 设A,B,C是任意集合，则 ⑴ A′(B∪C)= (A′B)∪(A′C)； ⑵ A′(B∩C)= (A′B)∩(A′C)； ⑶ (A∪B)′C= (A′C)∪(B′C)； ⑷ (A∩B)′C= (A′C)∩(B′C) 证明 ⑴ ：任取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) 所以⑴式成立。 4)若C1?，,则AíB?(A′CíB′C) ?(C′AíC′B). 证明: 必要性：设AíB，求证 A′CíB′C 任取x,y?A′C ?x?Aùy?CTx?Bùy?C (因AíB) ?x,y?B′C 所以, A′CíB′C. 充分性： 若CF1, 由A′CíB′C 求证 AíB 取C中元素y, 任取 x?ATx?Aùy?C?x,y?A′C Tx,y?B′C (由A′CíB′C ) ?x?Bùy?CT x?B 所以, AíB. 所以 AíB?(A′CíB′C) 类似可以证明 AíB ?(C′AíC′B). 5) 设A、B、C、D为非空集合，则 A′BíC′D?AíC∧BíD. 证明: 首先,由A′BíC′D 证明AíC∧BíD. 任取x?A，任取y?B，所以 x?Aùy?B ?x,y?A×B Tx,y?C×D (由A′BíC′D ) ?x?Cùy?D 所以, AíC∧BíD. 其次, 由AíC，BíD. 证明A′BíC′D 任取x,y?A×B x,y?A×B ? x?Aùy?B T x?Cùy?D (由AíC，BíD) ?x,y?C×D 所以, A′BíC′D 证毕. 例3、令A={1,2,3}给定A上八个关系如下： 可见这八个关系中R1、R3、R4是自反的。R2、R5、 R8、均是反自反关系。R3、R4、 R6 、 R8均是对称关系。R1、R2、R4、R5、R8均是反对称关系。R4、R8既是对称也是反对称的。有些关系既不是对称也不是反对称的：如R7 。R1、R3、R4、R5、R8均是传递的关系。 性质判定: 从关系的有向图 从关系的矩阵 自反性 每个结点都有环 主对角线全是1 反自反性 每个结点都无环 主对角线全是0 对称性 不同结点间如果有边,则有方向相反的两条边. 是以对角线为对称的矩阵 反对称性 不同结点间,最多有一条边. 以主对角线为对称的位置不会同时为1 传递性 如果有边a,b,b,c,则也有边a,c. 或者定义的前件为假. 如果aij=1,且ajk=1,则aik=1 注：对于传递性的理解还不够透彻，如果出题，自己可能会出错！！！ 例4、A={1,2,3},给定A中五个关系如下： R={1,1,1,2,1,3,3,3} S={1,1,1,2,2,1,2,2,3,3} T={1,1,1,2,2,2,2,3} Φ A×A 判断它们的性质：Y表示“是”，N表示“否”，填下表。 自反性 反自反性 对称性 反对称性 传递性 R N N N Y Y S Y N Y N Y T N N N Y N Φ N Y Y Y Y A*A Y N Y N Y 例5、令I是整数集合，I上关系R定义为：R={x,y|x-y可被3整除}，求证R是自反、对称和传递的。 证明：⑴证自反性：任取x∈I, (要证出x,x?R ) 因 x-x=0, 0可被3整除,所以有x,x∈R, 故R自反。 ⑵证对称性：任取x,y∈I,设x,y∈R, (要证出 y,x?R ) 由R定义得 x-y可被3整除, 即x-y=3n(n∈I)， y-x=-(x-y)=-3n=3(-n), 因-n∈I, ∴y,x∈R, 所以R对称。 ⑶证传递性:任取x,y,z∈I,设xRy, yRz,