离散数学离散数学 (15).pdf

《离散数学离散数学 (15).pdf》由会员分享，可在线阅读，更多相关《离散数学离散数学 (15).pdf（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Computer Science&Technology0Computer Science&Technology1李姓王张姓Computer Science&Technology2abcComputer Science&Technology3)7,10(),4,10(),1,10(),10,10(),6,9(),3,9(),9,9(),5,8(),2,8(),8,8(),10,7(),4,7(),7,7(),9,6(),3,6)(6,6(),8,5(),2,5(),5,5(),10,4(),7,4(),1,4(),4,4(),9,3(),6,3(),3,3(),8,2(),5,2(),2,2()

2、,10,1)(7,1(),4,1(),1,1(3RComputer Science&Technology4Computer Science&Technology5Computer Science&Technology6Computer Science&Technology7)6,6(),5,5(),4,4(),6,3(),3,3(),6,2(),4,2(),2,2(),6,1(),5,1(),4,1(),3,1(),2,1(),1,1(R 100000010000001000100100101010111111Computer Science&Technology8Computer Scien

3、ce&Technology9Computer Science&Technology10Computer Science&Technology11)7,10(),4,10(),1,10(),10,10(),6,9(),3,9(),9,9(),5,8(),2,8(),8,8(),10,7(),4,7(),7,7(),9,6(),3,6)(6,6(),8,5(),2,5(),5,5(),10,4(),7,4(),1,4(),4,4(),9,3(),6,3(),3,3(),8,2(),5,2(),2,2(),10,1)(7,1(),4,1(),1,1(3Ra=s|(a,s)R 1=1,4,7,10 4

4、=7=10=1,4,7,10 3=6=9=3,6,9 2=5=8=2,5,8 Computer Science&Technology1204=,8,4,0,4,8,14=,7,3,1,5,9,24=,6,2,2,6,10,34=,5,1,3,7,11,Computer Science&Technology1305=,10,5,0,5,10,15=,9,4,1,6,11,25=,8,3,2,7,12,35=,7,2,3,8,13,45=,6,1,4,9,14,Computer Science&Technology14整数集Z分为三类 04，14，24，34整数集Z分为三类 05，15，25，35

5、，45Computer Science&Technology15Computer Science&Technology16/Computer Science&Technology17Computer Science&Technology18这个性质说明:彼此等价的元素属于同一个等价类。Computer Science&Technology19/这个性质说明:彼此不等价的元素是属于不同的等价类，且这些等价类之间无公共元素。Computer Science&Technology20JiiCComputer Science&Technology21Computer Science&Technolog

6、y22例例7：A=1,2,3,10 R3=(a,b)|(a-b)/3Z 整数1=4=7=10=1,4,7,10 3=6=9=3,6,9 2=5=8=2,5,8 A/R3=1,2,3=1,4,7,10,2,5,8,3,6,91 2 3=1,2,3,10 1 2=,2 3=,1 3=Computer Science&Technology23Computer Science&Technology24例8 设A=0,1,2,7，R=|x,y A,且x y(mod 4)，则A 在R下的商集是A/R0,4,1,5,2,6,3,7。Computer Science&Technology25设R是非空集合A上

7、的等价关系,则等价类的集合aR|a A构成A的一个划分。（要满足三点）aR=AAaComputer Science&Technology26分析(1)由R产生的等价类都是A的非空子集；(定义及定理(1)(2)不同的等价类之间相交为空；(定理(4)(3)所有等价类的并集就是A。因此所有等价类的集合，即商集A/R，就是A的一个划分，称为由R所诱导的划分。Computer Science&Technology27证明：由定理 1等价类性质可知:对任意的a A,aR非空,且对任意两个等价类aR,bR,或者aR=bR 或者aRbR=。任意a A,显然由aR A,再有集合的并得aR A（1）;Aa又对任意

8、c A,有c cR,而cR aR,Aa因此c aR,即A aR（2）AaAa由（1）（2）所以aR=AAaComputer Science&Technology28Computer Science&Technology29),(),(),(),(),(),(）（）（）,（332211ddccbbabbaaaddccbabaCCCCCCR例如例如：A=a,b,c,d,S=a,b,c,d),(),(),(,),(),(),(),(),(）,（）,（cddcddccbbabbaaadcdcbabaRComputer Science&Technology30例例9：A=a,b,c,d,S1=a,b,c

9、,d,S2=a,b,c,d),(),(),(),)(,)(,)(,(),(),(),(),(),(),(),(),(),(,11cdbdaddcbcacdbcbabdacabaddccbbaadcbadcbaCCR因为S2=a,b,c,d不是A的划分，所以不存在相应的等价关系。Computer Science&Technology31Computer Science&Technology32证明 A/R1=aR1|aA,A/R2=aR2|aA。必要性:若R1=R2,对任意aA,则 aR1=x|xA,aR1x=x|xA,aR2x=aR2所以 aR1|aA=aR2|aA,即A/R1=A/R2充分性:设A/R1=A/R2 即aR1|aA=aR2|aA,对任意aR1A/R1,必存在cR2A/R2,使得aR1=cR2所以 a,bR1 aaR1baR1 acR2 bcR2 a,bR2所以R1 R2类似地有R2 R1,即R1=R2证明 设R1和R2是非空集合A上的等价关系,则R1=R2的充要条件是A/R1=A/R2Computer Science&Technology33