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

《离散数学(二元关系)课后总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章二元关系例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´A={<0,0>,<0,1>,<1,0>,<1,1>}可见A×B≠B×A例2、关于笛卡尔乘积的几个证明1）如果A、B都是有限集，且

2、A

3、=m,

4、B

5、=n，则

6、A´B

7、=mn.证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。2)A´Φ=Φ´B=Φ3)´对∪和∩满足分配律。设A,B,C是任意集合，则⑴A´(

8、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)证明⑴：任取ÎA´(B∪C)ÛxÎAÙyÎB∪CÛxÎAÙ(yÎB∨yÎC)Û(xÎAÙyÎB)∨(xÎAÙyÎC)ÛÎA´B∨ÎA´CÛÎ(A´B)∪(A´C)所以⑴式成立。4)若C¹F，,则AÍBÛ(A´CÍB´C)Û(C´AÍC´B).证明:必要性：设AÍB，求证A´CÍB´C任取ÎA´CÛxÎAÙyÎC

9、ÞxÎBÙyÎC(因AÍB)ÛÎB´C所以,A´CÍB´C.充分性：若CF¹,由A´CÍB´C求证AÍB取C中元素y,任取xÎAÞxÎAÙyÎCÛÎA´CÞÎB´C(由A´CÍB´C)ÛxÎBÙyÎCÞ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ÛÎA×BÞÎC×D(

10、由A´BÍC´D)ÛxÎCÙyÎD所以,AÍC∧BÍD.其次,由AÍC，BÍD.证明A´BÍC´D任取ÎA×BÎA×BÛxÎAÙyÎBÞxÎCÙyÎD(由AÍC，BÍD)ÛÎC×D所以,A´BÍC´D证毕.7例3、令A={1,2,3}给定A上八个关系如下：1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。1。2。。3333R2R1R3R4R5R6R7R8可见这八个关系中R1、R3、R4是自反的。R2、R5、R8、均是反自反关系。R3、R4、R6、R8均是对称

11、关系。R1、R2、R4、R5、R8均是反对称关系。R4、R8既是对称也是反对称的。有些关系既不是对称也不是反对称的：如R7。R1、R3、R4、R5、R8均是传递的关系。性质判定:从关系的有向图从关系的矩阵自反性每个结点都有环主对角线全是1反自反性每个结点都无环主对角线全是0对称性不同结点间如果有边,则有方向相反的两条边.是以对角线为对称的矩阵反对称性不同结点间,最多有一条边.以主对角线为对称的位置不会同时为1传递性如果有边,,则也有边.或者定义的前件为假.如果aij=1,且ajk=1,

12、则aik=1注：对于传递性的理解还不够透彻，如果出题，自己可能会出错！！！71。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性对称性反对称性传递性R4R3R2R1例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表示“否”，填下表。自反性反自反性对称性反对称性传递性RNNNYYS

13、YNYNYTNNNYNΦNYYYYA*AYNYNY例5、令I是整数集合，I上关系R定义为：R={

14、x-y可被3整除}，求证R是自反、对称和传递的。证明：⑴证自反性：任取x∈I,(要证出ÎR)因x-x=0,0可被3整除,所以有∈R,故R自反。⑵证对称性：任取x,y∈I,设∈R,(要证出ÎR)由R定义得x-y可被3整除,即x-y=3n(n∈I)，y-x=-(x-y)=-3n=3(-n),因-n∈I,∴∈R,所以R对称。⑶证传递性:任取x,y,z∈I,设xRy,

15、yRz,(要证出xRz)由R定义得x-y=3m,y-z=3n(m.n∈I)x-z=(x-y)+(y-z)=3m+3n=3(m+n),因m+n∈I,所以xRz,所以R传递。证毕例6、设R是集合A上的一个自反关系,求证：R是对称和传递的，当且仅当和在R中,则有也在R中。证明：必要性:已知R是对称和传递的。分析：结论是个蕴含式，即