离散(30).ppt

3.6 等价关系与划分,3.6.1 等价关系的概念 3.6.2 等价类与商集 3.6.3 划分的概念 3.6.4 划分一一对应等价关系,3.6.1 等价关系的概念,定义3.6.1设A为任意集合，R为A上的关系，若R是自反、对称和传递关系，则称R为A上的等价关系(equivalence relation)3.5.5 举 例,例3.6.1(1)父子关系(2)同学关系(3)朋友关系(4)老乡关系(5)师生关系,解 设A为人类集合R＝{︱x,y∈A,x与y是父子}S＝{︱x,y∈A,x与y是同学}P＝{︱x,y∈A,x与y是朋友}Q＝{︱x,y∈A,x与y是老乡}T＝{︱x,y∈A,x与y是师生},3.5.5 举 例,例3.6.2(1)等于关系(2)大于关系(3)小于关系(4)不大于关系(5)不小于关系,解 设R为实数集A＝{︱x,y∈R,x＝y}S＝{︱x,y∈R,x>y}P＝{︱x,y∈R,x︱x,y∈R,x≤y}T＝{︱x,y∈R,x≥y},3.5.5 举 例,例3.6.3(1)全等关系(2)相似关系,解 设A为平面三角形集合R＝{︱x,y∈A,x≌y}S＝{︱x,y∈A,x∽y},3.6.1 等价关系的概念,例3.6.4 设I为整数集，I上的模3同余关系(congruence relation)R＝{︱x,y∈I,x≡y(mod3)}则R为I上的等价关系 x≡y(mod3)x－y＝3k(k∈I) x与y模3相等 x＝y(mod3)x＝ 的余数 x与y模3互余,3.6.1 等价关系的概念,证明(1)任取a∈Ia－a＝0＝3×0a≡a(mod3)∈R (2)设∈Ra≡b(mod 3)a－b＝3kb－a＝3(—k),b≡a(mod 3)∈R (3)设∈R,∈Ra≡b(mod3),b≡c(mod3)a－b＝3k,b－c＝3ta－c＝3(k＋t)a≡c(mod3)∈R,3.6.2 等价类与商集,定义3.6.2 设R为集合A上的等价关系，a∈A，a确定的关于R的等价类(equivalence class)[a]R ＝{x︱x∈A,∈R} ∈R 集合A关于R的商集(quotient set)A／R＝{[a]R︱a∈A},,3.6.2 等价类与商集,[1]R＝{x︱x∈A,∈R}＝{1} [2]R＝{x︱x∈A,∈R}＝{2,3} [3]R＝{2,3} [4]R＝{4},A／R ＝{[1]R,[2]R,[3]R,[4]R} ＝{{1},{2,3},{4}},例3.6.5设A＝{1,2,3,4}，A上的等价关系R＝{,,,,,},3.6.2 等价类与商集,[1]S＝{x︱x∈A,∈S}＝{1,2}[2]S＝{x︱x∈A,∈S}＝{1,2} [3]S＝{3} [4]S＝{4},A／S＝{[1]S,[2]S,[3]S,[4]S}＝{{1,2},{3},{4}},例3.6.6 设A＝{1,2,3,4}，A上的等价关系S＝{,,,,,},3.6.2 等价类与商集,例3.6.7 模3同余类 模3同余关系的等价类解[0]＝{x︱x∈I,x≡0(mod 3)}＝{x︱x∈I,x－0＝3k,k∈I}＝{…,－6,－3,0,3,6,…}[1]＝{x︱x∈I,x－1＝3k,k∈I}＝{…,－5,－2,1,4,7,…}[2]＝{x︱x∈I,x－2＝3k,k∈I}＝{…,－4,－1,2,5,8,…},3.6.2 等价类与商集,同时…＝[－6]＝[－3]＝[0]＝[3]＝[6]＝……＝[－5]＝[－2]＝[1]＝[4]＝[7]＝……＝[－4]＝[－1]＝[2]＝[5]＝[8]＝…一般地，模k同余类为[0]＝{x︱x∈I,x－0＝kn,n∈I}[1]＝{x︱x∈I,x－1＝kn,n∈I}……[k－1]＝{x︱x∈I,x－(k－1)＝kn,n∈I},3.6.2 等价类与商集,定理3.6.1设R为A上的等价关系，对a,b∈A，[a]R＝[b]R  aRb。

证明 [a]R＝[b]R任取 x∈[a]R＝[b]R则 aRx且xRb又R传递关系 aRb,aRb任取x∈[a]R，则xRa又aRb，R传递关系所以xRb于是x∈[b]R从而[a]R [b]R同理[b]R [a]R[a]R＝[b]R,3.6.2 等价类与商集,定理3.6.2设R为A上的等价关系，对a,b∈A，[a]R∩[b]R＝  a b证明[a]R∩[b]R＝假设aRb,则[a]R＝ [b]R又a∈[a]R且b∈ [b]R故[a]R∩[b]R≠ 矛盾a b,a b假设[a]R∩[b]R≠设x∈[a]R且x∈[b]R则aRx且xRb又R传递关系于是aRb，矛盾即[a]R∩[b]R＝,3.6.3 划分的概念,定义3.6.3设非空集合A，若S＝{S1,S2,…,Sn}满足:(1)Si A，Si≠ (i＝1,2,…,n)(2)Si∩Si＝ (i≠j，i,j＝1,2,…,n)(3)S1∪S2∪…∪Sn＝A则称集合S为集合A的划分(partition)，其中Si(i＝1,2,…,n)称为该划分的块(block) A的最大划分 最小划分,3.6.3 划分的概念,例3.6.8设A＝{1,2,3,4} 则 S＝{{1,2,3,4}}B＝{{1,2},{3,4}} C＝{{1,3},{2,4}}D＝{{1,4},{2,3}} E＝{{1},{2,3,4}}F＝{{2},{1,3,4}} G＝{{3},{1,2,4}},H＝{{4},{1,2,3}}I＝{{1},{2},{3,4}}J＝{{1},{3},{2,4}} K＝{{1},{4},{2,3}}L＝{{2},{3},{1,4}} M＝{{2},{4},{1,3}}N＝{{3},{4},{1,2}}P＝{{1},{2},{3},{4}},3.6.4 划分一一对应等价关系,例3.6.9 设A ＝{1,2,3,4,5} 划分S＝{{1},{2,3},{4,5}} 等价关系R＝{,,,,,,,,} [1]＝{1} [2]＝[3]＝{2,3} [4]＝[5]＝{4,5},,,3.6.4 划分一一对应等价关系,定理3.6.3集合A的划分S＝{S1,S2,…,Sn}确定A上的一个等价关系R＝(S1×S1)∪(S2×S2)∪…∪(Sn×Sn),3.6.4 划分一一对应等价关系,证明(1)任取a∈AS1∪S2∪…∪Sn＝A Si a∈Si ∈Si×Si RaRa(2)设aRbSi ∈Si×Si ∈Si×Si RbRa,(3)设aRb且bRcSi与Sj使∈Si×Si且∈Sj×Sj 因Si∩Sj＝ ，故Si＝Sj于是a,c∈Si从而∈Si×Si R 即aRc,3.6.4 划分一一对应等价关系,定理3.6.3 集合A上的等价关系R确定A的一个划分S＝A／R。

3.6.4 划分一一对应等价关系,证明 商集A／R＝{[a]R︱a∈A}(1)[a]R∈A／R[a]R A [a]R≠ (2) ＝A(3)[a]R,[b]R∈A／R且[a]R≠[b]R [a]R∩[b]R ＝,3.6.4 划分一一对应等价关系,例3.6.10 设A＝{1,2,3}，确定A上的全部等价关系解 集合A的划分一一对应集合A上的等价关系划分 等价关系A＝{{1,2,3}} P＝A×AB＝{{1},{2,3}} Q＝{,,,,}C＝{{2},{1,3}} R＝{,,,,}D＝{{3},{1,2}} S＝{,,,,}E＝{{1},{2},{3}} T＝IA,作 业,课后作业134－135面题(1)，题(4)－(8),。