最新离散数学课件第四章二元关系习题.pptx

离散数学课件第四章二元关系习题最新离散数学课件第四章二元关系习题全文共25页，当前为第1页。

2练习１、(79页第３题)R1,R2是集合Ｘ中的关系，试证明：(1)r(R1?R2)=r(R1)?r(R2)(2)s(R1?R2)=s(R1)?s(R2)(3)t(R1?R2)?t(R1)?t(R2)（书上是等号）证明(1)左边=r(R1?R2)=R1?R2?Ix右边=r(R1)?r(R2)=R1?Ix?R2?Ix=R1?R2?Ix(1)式得证。最新离散数学课件第四章二元关系习题全文共25页，当前为第2页。

最新离散数学课件第四章二元关系习题全文共25页，当前为第3页。

最新离散数学课件第四章二元关系习题全文共25页，当前为第4页。

最新离散数学课件第四章二元关系习题全文共25页，当前为第5页。

最新离散数学课件第四章二元关系习题全文共25页，当前为第6页。

最新离散数学课件第四章二元关系习题全文共25页，当前为第7页。

最新离散数学课件第四章二元关系习题全文共25页，当前为第8页。

94.(85页第６题)在等价关系图中，应如何识别等价类？解：关系图中如果有孤立的结点，则它是一个等价类；都不与其它结点相关联的相互联结的两个结点构成一个等价类；都不与其它结点相关联的相互联结的三个结点构成一个等价类；都不与其它结点相关联对角线相关联的四个结点构成一个等价类最新离散数学课件第四章二元关系习题全文共25页，当前为第9页。

10都不与其它结点相关联的正五角星构成一个等价类；都不与其它结点相关联的正六角星构成一个等价类；最新离散数学课件第四章二元关系习题全文共25页，当前为第10页。

11上述图例中，省略了各结点上的自环，用一条无向边代替一对方向相反的有向边．5.(85页第７题)设Ｒ是集合Ｘ中的关系，对于所有的xi,xj和xk属于Ｘ，如果xiＲxj和xjＲxk就有xkＲxi则称Ｒ是循环关系，试证明当且仅当Ｒ是一个等价关系，Ｒ才是自反的和循环的．证明：充分性设Ｒ是等价关系，来证明Ｒ是循环的．(自反性是明显的)最新离散数学课件第四章二元关系习题全文共25页，当前为第11页。

12对任何xi,xj和xk属于Ｘ和xiＲxj，xjＲxk有xiＲxk及xkＲxi(由Ｒ的可传递性和对称性得)即Ｒ是循环的．必要性：设Ｒ是自反的和循环的来证Ｒ是个等价关系．实际上只要证Ｒ是对称的和可传递的即可．对任何xi,xj和xk属于Ｘ和xiＲxj，xjＲxk有xkＲxi及xiＲxi于是有xiＲxk即Ｒ是对称的和可传递的．综上问题得证．最新离散数学课件第四章二元关系习题全文共25页，当前为第12页。

136.(86页第７题)设Ｒ1和R2是集合Ｘ中的等价关系，试证明：当且仅当Ｃ1中的每一个等价类都包含于Ｃ2中的某一个等价类中，才有R1?R2证明：设Ｒ1和R2造成的划分分别是Ｃ1={c11,c12,┅,c1n}Ｃ2={c21,c22,┅,c2m}对任意的c1i∈Ｃ1(i=1,...,n),在Ｃ2中都存在某一个c2j(j=1,2,...,m)并且c1i?c2j最新离散数学课件第四章二元关系习题全文共25页，当前为第13页。

14对于任何x,y∈c1i则x,y∈c2j于是有x,y∈Ｒ1则x,y∈R2即Ｒ1?R2充分性得证．再证必要性：设Ｒ1?R2，于是对任意x,y∈Ｒ1(等价于x,y应属于Ｒ1造成的划分Ｃ1的某一个类c1i中,i=1,2,...n)则x,y∈R2，(等价于x,y一定属于Ｒ2造成的划分Ｃ2的某一个类c2j中,j=1,2,...m)必要性得证．最新离散数学课件第四章二元关系习题全文共25页，当前为第14页。

15７.(86页第９题)设Ｒ1和R2是集合Ｘ中的等价关系，并分别有秩r1和r2，试证明：Ｒ1∩R2也是集合X中的等价关系，它的秩至多是r1r2。而Ｒ1?R2不一定是集合X中的等价关系．证明：首先证明Ｒ1∩R2是等价关系1)(?x)(x∈X→x,x∈R1∩R2)=(?x)(?x∈X∨(x,x∈R1∧x,x∈R2))=(?x)((?x∈X∨x,x∈R1)∧(?x∈X∨x,x∈R2))最新离散数学课件第四章二元关系习题全文共25页，当前为第15页。

16=(?x)(?x∈X∨x,x∈R1)∧(?x)(?x∈X∨x,x∈R2)=T∧T=T利用全称量词对与的可分配性自反性得证．再来证Ｒ1∩R2是对称的用反证法，假设Ｒ1∩R2是不对称的，即(?x)(?y)(x,y∈X∧x,y∈Ｒ1∩R2∧y,x?Ｒ1∩R2)=(?x)(?y)(x,y∈X∧x,y∈Ｒ1∧x,y∈Ｒ2∧(y,x?Ｒ1∨y,x?Ｒ2))最新离