离散 习题课第三章学习资料

习题课例设是一个集合，求1X|x|=n,上的二元关系有多少？（〃）

1.X2上的自反的二元关系有多少？

2.X上的反自反的二元关系有多少？

3.X解因为把所有的反自反的二元关系的每个都加上对角线上的序对，就变成了自反的关系，因此，自反的与反自反的个数一样多即2上的对称的二元关系有多少？

4.X22n2+n〃士，故共有丁个对称的关系=1+=22222ir-n上的反对称的二元关系有多少？（丁・〃）

5.X32上既是自反的也是反自反的二元关系的个数；（个）

6.X0上既不是自反的也不是反自反的二元关系有多少？（一（））

7.X22-2解解可用容斥原理来计算设表示所有自反关系构成的集合，表示所有反自反关系构成的集合，则B CB\=|c|=2n2~no而5m,故忸uq=iM+|q,从而c cSnC|=|5|-|5UC|=|s|-|B|-|C|92，o o=2n~_2n~n-2n~~n=,r T~n=T~n（Z,）2-22-2于是，既不是自反的，也不是反自反关系共有（）个242-2自反的且对称的关系有多少？［此结果与“反自反的且对称的关系有多

8.少？”是一样多］即有（对角线上全去掉）2y自反的或对称的关系有多少？

9.解设表示自反关系的集合，表示对称关系的集合，则自反或对称关系B C/+〃n2-n的集合为\BUC\=\B\+\C\-\BHC\=〃丁丁2f+2-2上既是反自反的也是反对称的二元关系的个数为；

10.X3^证⑴自反性A,有所以,即是上的自反关系I Va,ZG a+E=4+,a,R A⑵对称性A,若a,bRc,d,则故c+d=aVa,Z,c,J GQ+b=c+d,+b,所以即是上的对称关系c,dRa,Z,R A传递性若且则a+b=c+d^c3Va,b,c,d,e,/eA,a,bRc,d c,dRe,/,+d=e+f,即所以故是上的传递关系a+b=e+/,a,ZRe,/,R A由⑴，可知，是上的等价关系2,3R A首先求出人=乂$的全部元素，然后找出所有元素对应的等价类即可在求II5等价类时，记住以下几条性质a[a]；若[a]=[b]1G2a,ZeR,JlJR R Ro因为A=S xS={1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,13,2,3,3,3,4,4,1,4,2,4,3,4,4}[1,1],={1,1},[1,2].={2,1,1,2}=[2,1],[1,3]R={1,3,3,1,2,2}=[3,1]R=[2,2k[1,4]R={1,4,4,1,2,3,3,2}=[4,1]R=[2,3]R=[3,2]R卜={[2,42,4,3,3,4,2}=[4,2],=[3,3],也={[3,4,3,3,4}=[4,3],[4,4],={4,4}所以，%={收，y]R Uy eA}={

[14],,[1,2].,卜尺,小,及}[1,3,[1,4],,[2,4][3,4[4,4例设《是上的等价关系，凡是上的等价关系关系满足13A5R斗,//区，力，％飞且必，为£R2O%2£不/》旧乂神宠当且仅当国马卜舄且匹小此一证明是上的等价关系R4xB解自反性有yeB；因为用和分别为和上的自反关系，1Vx”x8,x,A B所以，故，因此是X,XER],y,y£x,y,x,y£R R自反性的；（）对称性（）（）若（（玉,％）（々，%）），则（，）2V x,^,^,^e Ax5,e R X%21122］，（）氏；因为《和分别为和上的对称关系，所以有（，）与，eR%,%62A B%2%16（％，必），从而（（%，》），（，）），因此是对称性的；6%22%1%6k R（）传递性（］）（，），（，）义若（（％，）（，））尺且3V%,y,%2%%3%”5,1%,%2,26则有（玉，％）为，（％，％），（％，％），（，）；2££%23£N%%^^因为为和%分别为和上的传递关系，所以有（国％）为，（%,必）《，从而A5,36（（王,%）,（%，））〃，因此是传递性的3%6H综上可知是上的等价关系R AxB例设是自然数集合，定义上的二元关系14N NR（）是偶数},贝R={%,y|%eN,y eN,x+y lj（）证明是一个等价关系；1R（）求关系的等价类；2R证（）自反性%+%是偶数，所以有％因此是自反的；1A%R对称性若即是偶数，贝仃+%是偶数，所以有（）因此是对称x+y y,x cR R的；传递性若（）即是偶数，是偶数，则％+（）（）y,z eR,X+y y+z z=%+y+y+z-2y是偶数，所以有（）因此是传递的%,z eR R综上可知是等价关系R为偶数;X设,f:N TN,/%=则/所诱导的等价关系就是3RX为奇数（）关系的等价类有［，［（…}2R0}={0,2,4,…}={1,3,5,例设上的二元关系定义为:151={1,2,3,4}*{1,2,3,4},A R〃-u-v,x,yR,u=证明是上的等价关系；.确定由对集合的划分LR A2R A证,首先证明是上的等价关系1R A⑴自反性ye A，因为x-y=x-y，故，即是自反的Vx,x,yKx y,R⑵A,若,有,贝〃一Vx,e x,-y=-u Llu=x-y,从而〃,即是对称的vR%,y,R⑶若〃〃即x-y=u-v，u-v\=\p-q\Vx,y,“,u,p,q£A,x,yH,u,#Rp,q,9得卜一引=加一同，从而故是传递的x,yRp,g,R由⑴、、可知，是上的等价关系23R A由定理知，由的等价类可确定对集合的划分划分中的元素分别为元素

2.R A的等价类，它们是[1,1],={1,1,2,2,3,3,4,4},[1,2={1,2,2,1,2,3,3,2,3,4,4,3}[1,3],={1,3,3,1,4,2,2,4},[1,4],={1,4,4,1}即集合的划分乃={卜A[1,1],,[1,2,[1,3],,[1,4k}o习题课例非空集合上存在二元关系使得既是上的等价关系又是上的偏序关1A R,R A A系吗？解存在上的恒等关系就满足A例在人=和上定义的整除关系画出2{1,2,3,4,6,8,12,24}B={2,3,4,8,9,10,11}图，指出最大小元，极大小元Hasse•9•3•1!b解如图所示1a最大元最小元；241极大无极小无；241如图所示1b最大兀无极大兀；8,9,10,11最小元无极大元2,3,11元素既是极大元又是极小元11例设偏序集的关系图如图所示3AW2a⑴画出的图Hasse⑵设求的上界集合和上确界；下界集合和下确界B={b,c},B CD解的图如图所示

1.A,W Hasse8b设则中无任意元素“大于”也同时“大于故

1.8=b},A b,c,，此时，无上确界，而下确界C=D={d},do例设集合，占,%，%}上的偏序关系如图所示则4A=Z

9.求出的最大小元，极大小元2Aa.求出{々，/，“，{曰，%，/}」%，々，*^}的上界、卜界、上确界和下确界3工5九4图2解.最大元最小元无1X1,极大元斗，极小元x,x

452.^A={X,X,X},则234上界%,下界％；上确界不下确界％44令吕二优用心},则上界西,％，下界无;上确界匕，下确界无；3令C9则={x x,x1923上界再，下界/；上确界斗，下确界/例设集合上的关系定义如下5A={a,Z,c,d,e},AR={a,〃e,b,b,b,c,a,d,,c,则S,e,c,c,c,e,d,d,d,e,e,e}□写出的关系矩阵；1R验证是偏序集；2A,H并画出图3Hasse若上的关系如下R4A={Q,Q,Q,/,Q,c,Q,d,Q,e,S,O,S,c,S,e,e｝，则又如何c,c,c,d,ge,3,d,d,e,e,解所对应的关系矩阵为练为:1R11练=

011010100001、000110由关系矩阵可知:2对角线上的所有元素全为故是自反的;图101,R0+50,故是反对称的;R111101101010%=01=B R00010000对应的关系矩阵纥为:R22因此是传递的R综上可知故是上的偏序关系,从而是偏序集A AA,R对应的图如图所示33H Hasse10011014R的关系矩阵为B R=0011100011因为伍c,deR,但b,deR,故不是传递的,CER,R因此，不是上的偏序关系R A实际上，也可通过计算后的关系矩阵来说明:、[1111101111故不是传递的R”2=0011，1B RR

210001、0000b因此不是上的偏序关系R A证明每个由川+个实数组成的数列卬,外,…，〃中必有一个长至少为1乙1n+1的不减子序列，或有一个长至少为的不增子序列n+1H+1证不妨设个数是互不相同的于是，这/+]个数构成的集合且/+1A,2在上定义二元关系“0”如下|A|=H+1O Aa当且仅当aa且j□j%i ji j其中W是实数间的通常的小于或等于关系显然，二元关系0是自反的，传递的设〃.且0%,则.,a.a,q0J JiJJ且注/,ji,从而%=%,i=j所以，0是反对称的因此0是上的偏A序关系，（）是偏序集A,0由推论可知，中或有长至少为八+的链或有长至少为〃+的反链中A11A长至少为“+的链，就是序列,外,…的长至少为〃+的不减（在0下）的子工1q12一〃+11序列而的长至少为〃+的反链，实际上就构成了力,出，，〃的不增子A1・・・2I序歹U14n+1设反链中元素按下标递增顺序排列成%…，%+1（%，2…V；+1）因％”,而好心，所以/《%，故于是便有:4J=l,2,……A・・o+1412例设是实数集，令为到的所有映射所构成的集合若定7R X[0,1]R fgeX,义（，）（）（）/g eSoV%e[0[],/%-g%20,证明（）是偏序关系；（）是全序关系吗？1S2S分析证明是偏序关系，首先搞清是定义在什么集合上，中的元素是什S SS么形式；然后再按偏序关系的定义分别证明的自反性，反对称性，传递性；证S明这三个性质，可以直接采用按定义方法证明显然是定义在以映射S作为元素的集合上，因此，中的序对是以映射作为元素的/:[0,1]fR S证明（）证明是偏序关系1S自反性则都有/%—〃%=，即WcX,VXG[0,1],0上既是对称的也是反对称的关系个数；

11.X一+〃n2-n上既不是对称的也不是反对称的关系个数;丁-丁+

12.X2/_223解上既是对称的也是反对称的关系，故有〃X Rq/x2解设表示对称、表示反对称，则A B既不是对称的也不是反对称的二元关系为:n2+n72，广一〃\AcnBc\=\S\-\A\jB\=\S\-\A\-\B\+\AC\B\=犷2-2丁3例设有集合|川求上具有反自反且反对称性的二元关系的数目，并写出计2A,=3,A算过程解不妨设勿={〃,©,将看作一个抽屉，看作S,Q S,c,c,b一个抽屉，,看作一个抽屉若要获得具有反对称性且反自反性的关系，C,C,4其中的元素只能在三个抽屉中取且每个抽屉中至多取一个元素,分几种情况:一个也不取,有；种取法1C=l只取一个元素，有种取法22=6取二个元素，有《种取法322=12取三个元素，有种取法42222=8故具有反自反性且反对称性的二元关系数目共有个1+6+12+8=27若|川=〃，结果又为多少？n2-n,每个抽屉有种选择，故共有2个33例设是的募集俯⑴,上的二元关34={1,2,3},AA2={2},{3},{1,2},{1,3},{2,3},{1,2,3}}系且〃〃}，则不满足下列哪些性质？为什么？R={/l nbwR自反性；反自反性；对称性；反对称性；传递性12345〃〃等价于〃的=aCb手IQ a,b e R=aCb手!°R={/I解⑴自反性因为人，但，，所以么°与故不是自反的£2n=R反自反性2因为，，故故不是反自反的{1}G2{l}p|{l}={l}w{1},{1}CR,R对称性3，若则犬，所以，故％、£〃，从而是对称的Vx,y£2x,ywR,yPlxw R反对称性4令则故且％但所以从而不是1={1,2},={1,3},x,y£Rx£R,xwy,x,y wy,x,R反对称的传递性5令则有％⑴且，故且X={1},y={l,2},z={2},Dy=W yriz={2}W x,y£R，但=，故乏所以不是传递的y,z£R xPlzx,z H,R习题课co例1证明R QR*=R*oR=R+,其中R*=R°U*UR2U・・・=|JR/=0证/*；R=RoR°U*UWU…=RUR2UR3J..=£R=R+同理可证R%R=R+例［书上做为定理出现］设、是上的二元关系，则2R SX，是空关系10+=R+y=R+2证因为是传递的，故R+R++=R+3HUS+=R+US+证因为卫且卫故卫且卫，从而RUS R RUS S,RUS+R+,/US+5+RUS+2KUS+例如图所示给出下图中每个关系的自反、对称和传递闭包35a bc图5自反闭包1对称闭包2传递闭包3例设是集合上的反对称关系，则一定是反对称的吗？4R AtR证在上不一定是反对称的tR A例〃氏={」,,©,〃汝标的传递闭包为A={,b,c,d},33,tR=,{a,b,3,c,c,d,d,a,c,a,d,d,c,d,d,c,a,b,d,d,b,b,a,c,ba,a,b,b,c,c是全关系，故不是反对称的而是对称的tR tR例举例说明与确实不相等5sQR“sR解:设-={在上定义小于关系“”，则1,2,3,…},N不等关系W”；s%=$=而（（＜）），（）全关系r s=w=因此的确不相等例（成）是否存在（冈=）上的一个二元关系使得RR,…,R两两不相等7X R,解:存在令乂=｛〃｝｛（）（）〃）｝即可1,2,3/-,,=1,2,2,3,…,5—1,例证明如果是对称的，则也是对称的8RR+证证（）00，则七%使得（羽丁）£即于是存在1V x,y£R+=U6EN,m—1/=1个元素%,%，・・,，Ki，使得（不,%）£尺（％,为）£,（y〃.9ym-\£R,（y〃［一］,2）*”°y由的对称性有（〃_”氏”也_，几_）凡，（，），（，％）于是R y,12£…%%£R XeR0000（）从而（乂）即是对称的y,x w/r,x£|jR R+=|JRi=l z=l习题课例设是整数集/上的关系，/成〃定义为/=,则1R（）证明是等价关系；1R（）确定的等价类2R证（）因为有加加故加即是自反的12=2,Rm,R\fm,n I,若mR,即加之二/,则几机因此几机，即是对称的G2=2,R RI,若mR几,nRk,即加？=/且〃？=/，故〃［之二左之，即加秋，所以e R是传递的由此可知是/上的等价关系R（）因为心=亿一讣,所以的等价类有｛⑼［］⑵…｝2Viw/,RR,1R,q例设是上的一个自反关系，证明是等价关系o若（〃力）£氏且2R A R（）则，）［书上习题］Q,C£R,S C£R证是上的等价关系nR A若（）且（）由的对称性有）且（）再由的Q,Z£R G,c£R,R S,Q£R Q,c£A,R传递性有）S,C£R是自反的，故有（〃,〃）£=RX/Q£AR若（a,b）e R,由（〃,〃）£有〃）£所以是对称的R,S,R,R若（力）且（）由的对称性有:4ER ACER,R）且（）R，故由题意得（）R,所以是传递S,Q e R b,c ea,c e R因此，是上的等价关系R A不是等价关系（因为不传递）例.令A上的两个关系如图所不，它们是否是等价关系3A={1,2,3},3例设飞，是上的等价关系，则也是上的等价关系吗44A解兄不一定是的等价关系因为凡不一定具有传递性U ARU价关系举例设伽={〃,©，〃〃仇〃},={,,A,Z,c,c,a,6,〃}，则={,,S,,c,c,S,c,c,氏，S，〃，，a,b,c,c,b}R]U2={3c C,a,b,H因为且但（〃，）与，故不满足传递性，即为不一定是上的等c NUU11%A价关系例设乂…川,“工”是上如下的二元关系:（）（）5={1,2,SqXxX SV i,Z,/£S,左,/当且仅当j=k+loi,j=i+证明（）二等价关系；（）求等价类数12证（）等价关系显然;1等价类数为〃22-1只能取，故等价类数有九-个i+j2,3,…2n,21例设是上的对称和传递的关系若对中每个弘使得证明6R AA a,cA,q,bcR,R是上的等价关系A证使得a,b wR由的对称性有b,a eR再由的Va GA,3Z GA,RR传递性有〃由的任意性可知，是上的自反关系，故是上的等Q,WR aR AR A价关系例设是集合上的一个自反的和传递的关系；是上的一个关系，使得7R AT A且》,“证明是上的等价关系e T=a,5eReRT A证因为是上的自反关系，所以有故由的定义有即是1R AT a,qcT,T A上的自反关系若由题设且显然，b,aeT,即是上的对称2a,bwT,Q/GR3,QGR T A关系若且》,由题设可知a,b R,b,awR且b,cwR,3a,wT cwT,ec,beR由传递性得且故所以是上的传递关系R a,ccR c,aeR,a,ccT,T A由即得是上的等价关系1,2,3TA例设是上的一个二元关系，设孔使得且8R A5={5,164,a,ceR证明；若是上的等价关系，则也是上的等价关系；c,6eR}R AS A证证明若是等价关系，则也是等价关系R S自反性1因为是自反的，所以有根据的定义，有所以是自R VaeA,3,aeR Sa,acS,S反的；对称性2若a,beS,则五使得且因为是对称的，所以eA,Q,C wR c,b wRR瓦且根据的定义有所以是对称的；ceR c,aeR,S9,ae S,S传递性:3若b,ceS,则使得且因为是传递的，Q,beS,mdeA,a,d eR d,eRR所以aScR且也使得且因为是传递的，所以b,ceR°eA,6,eeR e,cwR R根据的定义有a,c SSeo所以是传递的S由可知是等价关系1,2,3S例设｛』是集合的划分，若，94,4A4PI3W IWiWn,证明｛、｝是集合的划分48,403/4845n证因为｛A，4，・・,，a』是集合A的划分，故A=UH，4口40,，iwj但/=

1、n n，AHB=IJA n8=uanB\i=l7i=l当时，iwj4ngnAng=当时，i=j4ngn4n3=anB所以｛｝是的划分APB,4ns…,408AAB例设凡和R.是集合x上的等价关系，和g是由R、和所诱导产生的划分，证明10q当且仅当的每个划分块都包含在的某个划分块中，氏口艮G G分析只要理解等价关系和划分的概念以及它们之间的一一对应关系，就很容易证明证令划分｛｛综二,…,％…｝q=4,4,…2=充分性若用之场,则的每个划分块都包含在的某个划分块中于是a G即.为中任一划分块，所以在人中任取一个元素因为是VA,eq,4q OEAAG X的划分且，所以存在£使得£巨于是皿£儿，有〃力£,又因为与之〃4£X2,，所以2根据划分的定义有人所以屋w a,由的任意性知，的每一划分块都包含在的某一划分块中4G2必要性若的每个划分块都包含在的某个划分块中，则C,C2\f（a,b）eR\,则，在的同一划分块中根据题设，必有,匕在的同G G一划分块中，故（,/）「尺因此鸟口号2例（；是上的二元关系，ll R3^X={l,2,3},y={l,2},S={/:Xf V}M5若，（）（）证明=是上的等价关系；求等价类W geS,/=g o/m/=/,.g,5证因为所以到的映射共有个，如图所示/xfy,x y82（）等价关系显然1金=}，［人卜他/小人//}，［九卜二㈤[f]={g\If=Ig}，故2R mm所以等价类集合为{卜,［f］，［力}o2R例设并设在上定义关系为:125={1,2,3,4},A=SxS,A Ra,bRc,d a+b=c+d e7证明（）是等价关系；（）计算出1R2A/R。