离散数学(二元关系)课后总结
- 格式：doc
- 大小：156.50 KB
- 文档页数：7
第四章二元关系例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)若C≠Φ，,则A⊆B⇔(A⨯C⊆B⨯C) ⇔(C⨯A⊆C⨯B).证明: 必要性：设A⊆B，求证A⨯C⊆B⨯C任取<x,y>∈A⨯C ⇔x∈A∧y∈C⇒x∈B∧y∈C (因A⊆B)⇔<x,y>∈B⨯C 所以, A⨯C⊆B⨯C.充分性：若CΦ≠, 由A⨯C⊆B⨯C 求证A⊆B取C中元素y, 任取x∈A⇒x∈A∧y∈C⇔<x,y>∈A⨯C⇒<x,y>∈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⇔<x,y>∈A×B⇒<x,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⇒ 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 注：对于传递性的理解还不够透彻，如果出题，自己可能会出错！！！1。
2。
。
1。
2。
。
1。
2。
。
1。
2。
。
3 3 3 3 1。
2。
。
1。
2。
。
1。
2。
。
1。
2。
。
3 3 3 3 R 2R 1R 3R 4R 5R 6 R 7 R 8例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*AYNYNY例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, (要证出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 是对称和传递的，当且仅当<a,b>和<a,c>在R 中,则有<b,c>也在R 中。
证明：必要性: 已知R 是对称和传递的。
分析：结论是个蕴含式，即<a,b>∈R ∧ <a,c>∈R ⇒ <b,c>∈R1。
2。
。
1。
2。
。
1。
2。
。
1。
2。
。
3 3 3 3 R 2 R 1 R 3 R 4自反性 反自反性 对称性 反对称性 传递性R 4R 3 R 2R 1可利用“假设前件为真，推出后件为真” 方法证明。
再结合已知条件：R对称、R传递。
设<a,b>∈R 又<a,c>∈R，(要证出<b,c>∈R )因R对称的，故<b,a>∈R，又已知<a,c>∈R 由传递性得<b,c>∈R。
所以有如果<a,b>和<a,c>在R中,则有<b,c>也在R中。
充分性: 已知任意a,b,c∈A，如<a,b>和<a,c>在R中,则有<b,c>也在R中。
先证R对称：分析：即任取a,b∈A 设<a,b>∈R ⇒ <b,a>∈R应有<？,b>∈R ∧ <？,a>∈R ⇒ <b,a>∈R 而已知<a,b>∈R ，那么是否<a,a>∈R ？任取a,b∈A 设<a,b>∈R，(要证出<b,a>∈R )因R是自反的，所以<a,a>∈R，由<a,b>∈R且<a,a>∈R，根据已知条件得<b,a>∈R ，所以R是对称的。
再证R传递：分析：即任取a,b,c∈A 设<a,b>∈R ∧ <b,c>∈R ⇒ <a,c>∈R应有<？,a>∈R ∧ <？,c>∈R ⇒ <a,c>∈R而已知<b,c>∈R ，那么是否<b,a>∈R ？任取a,b,c∈A 设<a,b>∈R，<b,c>∈R。
(要证出<a,c>∈R )由R是对称的，得<b,a>∈R ，由<b,a>∈R且<b,c>∈R，根据已知条件得<a,c>∈R ，所以R是传递的。
例7、给定A={1,2,3},A中关系R和S如下：R={<1,1>,<1,2>,<1,3>,<3,3>}S={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}分别求复合关系RοS，SοR，IAοR, RοIA 。
解：RοS={<1,1>,<1,2>,<1,3>,<3,3>}SοR={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,3>}IA＝{<1,1>,<2,2>,<3,3>}IAοR=RοIA=R例8、设F表示父亲和儿子之间的关系，M表示母亲和儿子之间的关系，S表示儿子和母亲之间的关系，D表示女儿和母亲之间的关系。
问：F ο F，F ο S，D ο（ D ο M）分别表示什么关系？答： F ο F表示祖孙关系。
F ο S表示夫妻关系。
D ο（D ο M）表示外甥女和舅舅之间的关系。
例9、证明若R⊆A×B ，S⊆B×C T⊆C×D则Rο(SοT)=(RοS)οT证明：任取<a,d>∈Rο(SοT)∃⇔b(b∈B∧<a,b>∈R∧<b,d>∈SοT)∃⇔b(b∈B∧<a,b>∈R∧∃c(c∈C∧<b,c>∈S∧<c,d>∈T))∃⇔b∃c(b∈B∧<a,b>∈R∧(c∈C∧<b,c>∈S∧<c,d>∈T))∃⇔c∃b(c∈C∧(b∈B∧<a,b>∈R∧<b,c>∈S∧<c,d>∈T))∃⇔c (c∈C∧∃b(b∈B∧<a,b>∈R∧<b,c>∈S)∧<c,d>∈T)∃⇔c (c∈C∧<a,c>∈(RοS)∧<c,d>∈T)⇔<a,d>∈(RοS)οT所以Rο(SοT)=(RοS)οT例10、R⊆A×B S⊆B×C T⊆B×C⑴Rο(S∪T)=(RοS)∪(RοT)⑵ R ο(S ∩T)⊆(R οS)∩(R οT) 证明⑴ 任取<a,c>∈R ο(S ∪T)⇔ ∃b(b ∈B ∧<a,b>∈R ∧<b,c>∈S ∪T)∃⇔b(b ∈B ∧<a,b>∈R ∧(<b,c>∈S ∨<b,c>∈T))∃⇔b((b ∈B ∧<a,b>∈R ∧<b,c>∈S)∨(b ∈B ∧<a,b>∈R ∧<b,c>∈T)) ∃⇔b(b ∈B ∧<a,b>∈R ∧<b,c>∈S)∨ ∃b(b ∈B ∧<a,b>∈R ∧<b,c>∈T) ⇔<a,c>∈R οS ∨<a,c>∈R οT ⇔<a,c>∈(R οS)∪(R οT)所以R ο (S ∪T)=(R οS)∪(R οT) 证明⑵ 任取<a,c>∈R ο (S ∩T)⇔ ∃b(b ∈B ∧<a,b>∈R ∧<b,c>∈S ∩T)∃⇔b(b ∈B ∧<a,b>∈R ∧(<b,c>∈S ∧<b,c>∈T))∃⇔b((b ∈B ∧<a,b>∈R ∧<b,c>∈S) ∧ (b ∈B ∧<a,b>∈R ∧<b,c>∈T)) ⇒∃b(b ∈B ∧<a,b>∈R ∧<b,c>∈S)∧∃b(b ∈B ∧<a,b>∈R ∧<b,c>∈T) ⇔<a,c>∈R οS ∧<a,c>∈R οT ⇔<a,c>∈(R οS)∩(R οT)所以 R ο (S ∩T)⊆(R οS)∩(R οT) ∃x(A(x)∧B(x)) ⇒∃xA(x)∧∃xB(x) 求传递闭包以及可达矩阵求t(R)的矩阵Warshall 算法：|X|=n, R ⊆X ×X, 令MR=A R2的矩阵为A(2),… Rk 的矩阵为A(k) .故t(R)的矩阵记作MR+=A+A(2) +…+A(k)+…(“+”是逻辑加) ⑴置新矩阵 A :=MR ; ⑵置 i=1;⑶对所有 j ,如果A[j,i] =1 ,则对k=1,2,…,nA[j,k]:=A[j,k]+A[i,k]; /*第j 行+第i 行,送回第j 行*/ ⑷ i 加1;⑸ 如果i ≤n, 则转到步骤⑶，否则停止。
