12
• 对于任何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) • 必要性得证．
•
(i≠j)
•
5
• 3.(85页第２题） • 把n个元素的集合划分为两个类，共有多
少种不同的分法？ • 解：２个元素的有１种分法： • 即Ｃ1＝{{a1}, {a2}},即2(2-1)-1 • 3个元素的有３种分法： • 即Ｃ1＝{{a1}, {a2 ,a3}} • Ｃ2＝{{a2}, {a1 ,a3}} • Ｃ3＝{{a3}, {a1 ,a2}}即2(３-1)-1
14
• =(∀x)(¬x∈X∨<x,x>∈R1)∧ (∀x)(¬x∈X∨<x,x>∈R2)
• 证明：因为Ａ1⊆Ａ
•
Ａ2⊆Ａ
•
┄
4
•
• Ａn⊆Ａ
• 于是有Ａ1∩B⊆Ａ∩B
•
Ａ2 ∩B ⊆Ａ∩B
•
┄
•Hale Waihona Puke Ａn ∩B ⊆Ａ∩B• 并且Ａ1∩BＡ2∩B ┄ Ａn ∩B
• =(Ａ1 Ａ2 ┄ Ａn) ∩B
• = A∩B.
• 对任何(Ａi∩B) ∩(Ａj∩B)=(Ａi∩Ａj) ∩B=Φ∩B= Φ
8
• 都不与其它结点相关联的正五角星构成一 个等价类；
• •
• 都不与其它结点相关联的正六角星构成一 个等价类；
•
9
• 上述图例中，省略了各结点上的自环，用 一条无向边代替一对方向相反的有向边．
• 5.(85页第７题) • 设Ｒ是集合Ｘ中的关系，对于所有的xi,xj
和xk属于Ｘ，如果xiＲxj和xjＲxk就有xkＲxi • 则称Ｒ是循环关系，试证明当且仅当Ｒ是
2
• 证(3)t(R1R2)⊇t(R1) t(R2)
• t(R1R2)=(R1R2) (R1R2)2 ┄ (R1R2)n • 而(R1R2)2= (R1R2)o (R1R2)
• =((R1R2)oR1) ((R1R2)oR2)
• •
=
R12R2oR1┅ R1oR2R22⊇R12
练习
• １、(79页第３题)
• R1,R2是集合Ｘ中的关系，试证明： • (1)r(R1R2)=r(R1) r(R2) • (2)s(R1R2)=s(R1) s(R2) • (3)t(R1R2)⊇t(R1) t(R2)（书上是等号） • 证明(1)左边=r(R1R2)
•
=R1R2 Ix
一个等价关系，Ｒ才是自反的和循环的． • 证明：充分性设Ｒ是等价关系，来证明Ｒ
是循环的．(自反性是明显的)
10
• 对任何xi,xj和xk属于Ｘ和xiＲxj ，xjＲxk有 • xiＲxk及xkＲxi(由Ｒ的可传递性和对称性得) • 即Ｒ是循环的．
• 必要性：设Ｒ是自反的和循环的来证Ｒ是 个等价关系．实际上只要证Ｒ是对称的和 可传递的即可．
• 对任何xi,xj和xk属于Ｘ和xiＲxj ，xjＲxk有 • xkＲxi及xiＲxi于是有xiＲxk即Ｒ是对称的和
可传递的．
• 综上问题得证．
11
• 6.(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
有2(n-1)-1种
7
• 4.(85页第６题) • 在等价关系图中，应如何识别等价类？ • 解：关系图中如果有孤立的结点，则它是
一个等价类；
• 都不与其它结点相关联的相互联结的两个 结点构成一个等价类；
• 都不与其它结点相关联的相互联结的三个 结点构成一个等价类；
• 都不与其它结点相关联对角线相关联的四 个结点构成一个等价类
6
• 4个元素的有７种： • 即Ｃ1＝{{a1}, {a2 ,a3 ,a4}} • Ｃ2＝{{a2}, {a1 ,a3 ,a4}} • Ｃ3＝{{a3}, {a1 ,a2, a4}} • Ｃ4＝{{a4}, {a1 ,a2 ,a3 }} • Ｃ5＝{{a1,a2}, {a3 ,a4}} • Ｃ6＝{{a1,a3}, {a2, a4}} • Ｃ7＝{{a1,a4}, {a2 ,a3 }} 即2(4-1)-1 • 一般具有n个元素的集合分成两堆的分法
• 右边= r(R1) r(R2)
• =R1 Ix R2 Ix
• =R1R2 Ix • (1)式得证。
1
• 证(2)左边=s(R1R2) • =(R1R2) (R1 R2) 〜 • = R1R2 R1〜 R2〜 • = (R1 R1〜) (R2 R2〜) • =s(R1) s(R2) • (2)得证。
R22
• (R1R2)n ⊇R1n R2n • 于是有(R1R2) (R1R2)2 ┅ (R1R2)n ⊇
R1 R12┅ R1n R2 R22
3
• R22┅ R2n • 即t(R1R2)⊇t(R1) t(R2) • (3)得证．
• ２、(85页第１题)
• 设｛Ａ1,Ａ2, ┄,Ａn｝是集合Ａ的划分，试 证明：｛Ａ1∩Ｂ，Ａ2∩Ｂ, ┄,Ａn ∩Ｂ｝是 集合Ａ ∩Ｂ的划分．
13
• ７.(86页第９题) • 设Ｒ1和R2是集合Ｘ中的等价关系，并分别
有秩r1和r2，试证明：Ｒ1∩R2也是集合X中 的等价关系，它的秩至多是r1r2。而 • Ｒ1R2不一定是集合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))