[离散数学二元关系课后总结.doc

  1. 1、本文档共7页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[离散数学二元关系课后总结

第四章 二元关系 例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对称。 ⑶证传递性

文档评论(0)

xiayutian80 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档