2023年離散數(shù)學(xué)習(xí)題解第一部分集合論部分新版

離散數(shù)學(xué)輔助教材概念分析結(jié)構(gòu)思想與推理證明第一部分集合論劉國(guó)榮交大電信學(xué)院計(jì)算機(jī)系?離散數(shù)學(xué)習(xí)題解答習(xí)題一（第一章集合）1.列出下述集合的所有元素：１）Ａ＝｛x|x∈N∧x是偶數(shù)∧x＜1５}２）B={x|x∈N∧4+x=3}3）Ｃ={x|ｘ是十進(jìn)制的數(shù)字}[解]1)Ａ={2,４,６，8，１０，12，1４}２)B=3)C={0，１，2,3,４，5,6,7，8，9}2.用謂詞法表達(dá)下列集合：1){奇整數(shù)集合}2）｛小于7的非負(fù)整數(shù)集合}3）｛3，5，7，１1，１3，17，１9,２３，２９}[解]1）｛nｎＩ（ｍI)(n=2m+1)};2）{nnIn0n＜７};3）{pｐNｐ>2p<30(dN)(ｄ1dｐ（kN)(p=kｄ)）}。3.擬定下列各命題的真假性：１）2)∈3）{}4）∈｛}5）{ａ,b｝{a，b，c，｛a,ｂ,c}}6){a,b}∈(a，b,c，{a,b，ｃ})７）{ａ,ｂ}｛ａ,b,{{a，b，}}}8){ａ,b｝∈{a，ｂ,{{ａ,b，}}}[解]１）真。由于空集是任意集合的子集;２）假。由于空集不含任何元素；３）真。由于空集是任意集合的子集；4）真。由于是集合{}的元素；5）真。由于｛a,b｝是集合{a,b,c，{a，ｂ，ｃ｝｝的子集;6)假。由于{a,b}不是集合{ａ，ｂ,ｃ,{a,b,c}}的元素;7）真。由于{a,b｝是集合{ａ，b，{｛a,b}｝}的子集；８)假。由于{ａ，b}不是集合{ａ，ｂ，｛{a，b}}}的元素。4.對(duì)任意集合A,Ｂ，C,擬定下列命題的真假性：1)假如Ａ∈Ｂ∧B∈C,則A∈C。2）假如A∈B∧B∈C，則A∈C。3）假如ＡB∧B∈Ｃ,則A∈C。[解]1)假。例如A＝{a},B={a,b｝,C=｛｛a},},從而A∈B∧B∈Ｃ但A∈C。2)假。例如A={ａ}，B={a,{ａ}}，Ｃ=｛｛a}，{{a}}｝,從而A∈Ｂ∧Ｂ∈C，但、A∈Ｃ。3)假。例如A＝{a｝，Ｂ={a,b},Ｃ={｛a}，a,b},從而ACB∧B∈C,但Ａ∈C。5．對(duì)任意集合Ａ，B,C，擬定下列命題的真假性：1)假如A∈Ｂ∧BC，則A∈C。2)假如A∈B∧BＣ,則AC。3)假如AＢ∧B∈Ｃ,則A∈C。3）假如ＡＢ∧B∈C，則ＡC。［解]1）真。由于ＢCx（ｘ∈Ｂｘ∈C），因此Ａ∈BA∈C。2）假。例如A={ａ},Ｂ＝{｛a}，{b｝},C={{a},，{c｝｝從而A∈B∧BC，但AC。３）假。例如Ａ={a}，B={{a,ｂ}},C=｛{a,{a,ｂ}},從而AＢ∧Ｂ∈C,但AＣ。４）假。例如A＝{a}，B={{a,b}},Ｃ＝{{a，ｂ},b｝,從而AB∧B∈Ｃ,但AC。6.求下列集合的冪集：１)｛a,b,c}2）｛a，{ｂ,c}}3){｝４)｛，｛}}5）{{a，ｂ},{ａ，ａ,b｝,{a,b,a，b}}[解]1）{,｛ａ}，,｛ｃ｝，{ａ,b｝，{a,c｝,{b，c}，{a，b，ｃ}｝2){,{ａ｝,｛{b,c}},{a,｛a，b}}}3）{，{}｝4){,{}，{{}｝,{，{}｝｝５){，｛{ａ，ｂ}｝}７．給定自然數(shù)集合N的下列子集:Ａ＝{1,2，7,8｝B={x|x2<50}C={x|x可以被3整除且0≤x≤30}D={x|x=2Ｋ，Ｋ∈Ｉ∧Ｏ≤Ｋ≤６}列出下面集合的元素:Ａ∪B∪C∪DA∩B∩C∩DB＼(Ａ∪C)（A′∩Ｂ)∪D[解]由于B={1,２,３，4，５，6，７｝，C={3，6,９，12，15，１8,21,24，27,3０}，D＝{１，2，4,8,16，３２，64，},故此1)A∪B∪Ｃ∪Ｄ＝{１，２,3,４，５,6，7，8，9，１2，1５,16,1８，21,2４,27,30,32,64｝２）A∩B∩C∩Ｄ=3)B\(Ａ∪C)={４,5}4）(A′∩Ｂ）∪D={1，2，３,4,５,6，7,8,1６,３2,64}8．設(shè)Ａ、B、C是集合，證明:１)（A\B）=Ａ\(B\C）２）(Ａ＼B）＼C＝(A＼C）＼（B＼Ｃ)3）(Ａ\B）\C=（A\Ｃ)\B[證明]1)方法一:（Ａ＼B)\C=(A∩B′）∩C′(差集的定義)＝A∩（B′∩C′)（交運(yùn)算的結(jié)合律）=A∩（Ｂ∪C）′（ｄeＭｏｒgan律）=Ａ\（B∪C）（差集的定義)方法二：對(duì)任一元素ｘ∈（A＼B）\C，則ｘC，同時(shí)，x∈A\B,x∈A,ｘB,所以,ｘ∈Ａ，ｘB∪C，即x∈A\(Ｂ∪C),由此可見(jiàn)（A\B)\CA＼(Ｂ∪C）。反之，對(duì)任一元素x∈A\（B∪C），則x∈Ａ,且xB∪C,也就是說(shuō)xA，ｘＢ，xC。所以x∈(A\Ｂ）＼C,由此可見(jiàn)A\(B∪C)(A\B）\Ｃ。因此A\（Ｂ\C)。2）方法一:(Ａ\Ｂ）＼C＝A\(B∪C)(根據(jù)１)）＝A\(C∪Ｂ）（并運(yùn)算互換律）=A＼（（C∪B）∩Ⅹ)（0—1律)=Ａ＼（(C∪B)∩（C∪C′)）(0—１律)=A＼(C∪（B∩C′）（分派律)=(A\C）＼(B∩C′）（根據(jù)1)=(A\C)\（Ｂ∩C）（差集的定義）方法二:對(duì)任一元素ｘ∈（Ａ＼B)＼C,可知ｘ∈A，xＢ,ｘC,x∈A\C。又由ｘＢ，xＢ＼C,x∈(A\Ｃ）\（B\C）\(B\C)。所以(A\B）\C（Ａ＼C）\（B＼C)。反之,對(duì)任ｘ∈（A\C）＼（B\C)，可知ｘ∈A\C，xB\C。由x∈A\Ｃ,可知x∈A，ｘC。又由于xB\C及xC,可知xB。所以，ｘ∈(A＼B）＼C。因此(A\B)＼C（A\B）\C。由此可得（A＼B)\（B\C)(A\B）＼C。3)方法一:(Ａ\Ｃ）\C=A＼(B∪C)(根據(jù)1))=Ａ\（Ｃ∪B)（并運(yùn)算互換律）=(A\C)\B（根據(jù)1))方法二:對(duì)任一元素x∈（Ａ＼Ｂ）＼C,可知x∈A,xB，xＣ。由為ｘ∈A,xＣ,所以,ｘ∈A\Ｃ。又由xB，x∈(A\C)\B。所以，(Ａ\B)\C(A\C）\B。同理可證得(A\Ｃ）\Ｂ（A\B)＼C。9．設(shè)A、Ｂ是Ⅹ全集的子集，證明：ABA′∪B=ＸA∩B′=[解](采用循環(huán)證法)(1）先證ABA′∪B=X；方法一：Ａ′∪Ｂ=A′∪（A∪B)（由于條件AB及定理４)=(Ａ′∪A)∪Ｂ（∪的結(jié)合律)=（Ａ∪Ａ′)∪B（∪的互換律）=Ｘ∪B(互補(bǔ)律）=X(零壹律)方法二：ABA∪B=B（定理4)B=A∪Ｂ(等號(hào)＝的對(duì)稱性）A′∪Ｂ=A′∪(Ａ∪B)（兩邊同時(shí)左并上A′）A′∪B＝=(Ａ′∪A)∪B(∪的結(jié)合律)A′∪B＝（A∪A′)∪B（∪的互換律)A′∪B＝X∪B(互補(bǔ)律)A′∪B＝X(零壹律)方法三:由于A′X且ＢX，所以根據(jù)定理2的3）就有Ａ′∪BX；另一方面，由于BA′∪B及根據(jù)換質(zhì)位律可得Ｂ′A′A′∪B,因此，由互補(bǔ)律及再次應(yīng)用定理２的3),可得X＝B∪B′A′∪Ｂ，即XA′∪Ｂ;所以，A′∪B＝X。(2)次證A′∪B=ＸA∩Ｂ′=;A′∪B＝Ｘ(A′∪B)′=X′（兩邊同時(shí)取補(bǔ)運(yùn)算′)(A′）′∩B′＝X′(deMoｒgan律）A∩B′=Ｘ′（反身律）A∩Ｂ′＝X′（零壹律)(3)再證A∩B′=AB;方法一:A=A∩Ｘ(零壹律)＝Ａ∩(B∪B′)（互補(bǔ)律)=（A∩B）∪(Ａ∩B′)(分派律)＝（A∩B)∪(條件Ａ∩Ｂ′=)=A∩B(零壹律)B(定理2的3))方法二：A∩B′=B=B∪(零壹律）=B∪(Ａ∩Ｂ′)(條件Ａ∩B′=）=(B∪A)∩(B∪B′)(分派律)=(A∪B）∩(B∪B′）(∪的互換律)=（A∪B)∩Ｘ(互補(bǔ)律)＝A∪B（零壹律)AＢ(定理４的2)）10．對(duì)于任意集合A，B,C，下列各式是否成立,為什么？A∪B＝Ａ∪CB=CA∩B=A∩CB=C[解]1）不一定。例如:A={a｝，Ｂ={a，ｂ},C={b｝。顯然有A∪B=A∪C,但Ｂ≠C。2)不一定。例如:A=｛ａ}，B={ａ，b}，C=｛b，c}。顯然有A∩Ｂ=Ａ∩C,但Ｂ≠C。１1．設(shè)A，B為集合,給出下列等式成立的充足必要條件:A＼B=BＡ\B=B\AA∩B=A∪BAB=A[解]1）A\Ｂ＝A∩Ｂ′,由假設(shè)可知A\B=B，即A∩Ｂ′=B。由此可知B=故此B=Ｂ∩B′＝。由假設(shè)可知A＝A\=Ａ＼B＝Ｂ＝。所以當(dāng)Ａ\B=Ｂ時(shí)有A=Ｂ=。反之,當(dāng)A=B=時(shí),顯然A\B=Ｂ。因此Ａ\B=B的充足必要條件是A=B＝。２)設(shè)A\B≠∈,則有元素ａ∈A\Ｂ,那么,a∈A,而由假設(shè)A＼B=Ｂ＼Ａ。所以a∈B\Ａ,從而aA,矛盾。所以A\B=,故AB。另一方面由B\Ａ＝A\Ｂ=?？傻肂A。因此當(dāng)Ａ＼B=Ｂ\A時(shí),有A=B。反之,當(dāng)A=Ｂ時(shí),顯然A＼B=B\A=因此,A＼B=B\A的充要條件是Ａ=B。3）由于A∪B＝Ａ∩B,從而ＡA∪B=A∩BＢ，以及BＡ∪Ｂ=A∩BA故此A∪B=A∩B,有A=Ｂ。根據(jù)定理6的1)有A=A,由已知條件AB=A,可得ＡＢ=Ａ。從而由對(duì)稱差的消去律可得B=。反之，若B＝,則AB=A=A。所以AB＝A的充足必要條件為Ｂ＝。12.對(duì)下列集合,畫出其文圖：A′∩Ｂ′A\（B∪C）′Ａ∩(B′∪C）［解]AABBCACBAXX１3.用公式表達(dá)出下面圖中的陰影部分[解]AACBx(A∪B∪C)∪(A∩B∩C)′BCAx(A∩C)\B1４．試用成員表法證明1)(AB）C＝A（BC)2)（A∪B)∩（B∪C）ＡB′［解]1）成員表如下AＢＣAB(ＡB)CＢCA(ＢC）0０00０００00１0１１１01０1１１1011100０10０１１０110１１０１０１1０00１0１1１０101成員表中運(yùn)算結(jié)果Ｃ及A(BC)的兩列狀態(tài)表白,全集中的每一個(gè)體對(duì)它倆有相同的從屬關(guān)系，故（AB）C=A(BC）成員表如下:ABCA∪Ｂ(B∪C）(B∪C)′(A∪B)∩（B∪C)′Ｂ′A∩B′0００0０１０100０1０10０100１０1１0000０１111０00010０１01111１01１10０111１０11000０１１111000０成員表中運(yùn)算結(jié)果（A∪B）∩（Ｂ∪C)′及A∩B′的兩列狀態(tài)表白,全集中的每一個(gè)體，凡是從屬(A∪B)∩(B∪C）′的，都從屬A∩Ｂ′，故（Ａ∪Ｂ）∩（Ｂ∪C）′A∩B注:自然數(shù)集N取為{1，2,３，……，n,……｝

習(xí)題二（第二章關(guān)系)1．設(shè)A={1,２，3，},Ｂ={a,b}求1）A×B2）B×Ａ３）B×Ｂ4）２Ｂ×Ｂ[解]1)A×Ｂ=｛(1,ａ），(1，b)，(２，a）,（2，a），（３，a）,(3，b）}2)B×A={(ａ，1），（ａ,2）,(ａ,３),（b,1）,(b,２）,(b，３）｝3）B×B={（a,a），(a，b),（ｂ，ａ）,(b,b)}４)2B＝｛，｛a｝,{b｝，｛ａ，b}}2B×Ｂ{(,{a}），（,b)，({a}，a）,（{a},b),({ｂ}，ａ），（｛ｂ｝，b）,({a，b｝，b）}2．使AA×Ａ成立的集合A存在嗎？請(qǐng)闡明理由。[解]一般地說(shuō)，使AＡ×A成立的集合A不存在，除非A=。否則A≠，則存在元素x∈Ａ×Ａ，故有ｙ１,y2∈Ａ，使x＝(ｙ1,ｙ2),從而y1，y2∈A×A，故此有y1，ｙ２，y3,y4，使y1=（y1,ｙ2），y2=（y3,y4），……。這說(shuō)明A中每個(gè)元素x，其結(jié)構(gòu)為元組的無(wú)窮次嵌套構(gòu)成，這不也許。我們討論的元素的結(jié)構(gòu)必須是由元組的有限次嵌套構(gòu)成。３．證明A×Ｂ=Ｂ×AA＝∨B＝∨A＝Ｂ[證]必要性:即證Ａ×B=B×ＡA=∨B＝∨A=Ｂ若A×B=，則Ａ＝或者Ｂ=若A×B≠，則A≠且Ｂ≠,因此對(duì)任何x∈A及任何y∈B就有(x,ｙ）∈A×B，根據(jù)A×B=B×A,可得(ｘ，ｙ)∈Ｂ×A，故此可得x∈Ｂ，y∈A，因此而得AＢ且ＢA,所以由的反對(duì)稱性A＝B。充足性:即證Ａ=∨Ｂ＝∨A=BＡ×B=Ｂ×A這是顯然的。4.證明（A∩B)×(Ｃ∩Ｄ)＝（A×C）∩（Ｂ×D）[證]證法一：(元素法）對(duì)任一（x，y)∈(Ａ∩Ｂ）×（C∩D)有x∈A∩Ｂ,ｙ∈C∩D,于是x∈Ａ，x∈B,y∈C,y∈D。因而(x,y)∈A×C，且(ｘ，ｙ）∈B×Ｄ，所以（x，y)∈（A×C)∩（B×D）。因而（A∩B）×(C∩D）(A×C）∩(B×D）另一方面,對(duì)任一（x,y)∈（Ａ×C）∩(B×D），于是有(x，y)∈A×Ｃ且（x，ｙ)∈Ｂ×D，因而x∈A，y∈C,ｘ∈Bｙ∈D。所以x∈Ａ∩Ｂ,y∈（C∩D)。所以(ｘ，y）∈(Ａ∩B）×（C∩Ｄ）。因而(A×C)∩(B×D)（A∩B）×(Ｃ∩Ｄ)。綜合這兩個(gè)方面有(A∩B)×(C∩D)=（A×C)∩(B×D)。證法二：(邏輯法)對(duì)任何ｘ,y(x,y)∈(A∩B)×（Ｃ∩D)x∈A∩Ｂy∈Ｃ∩D(ｘ∈Ａx∈B)(y∈Cy∈D)(x∈Aｙ∈C)(x∈Ｂy∈D)(的結(jié)合律、互換律)(ｘ,y)∈A×C(ｘ,y)∈Ｂ×Ｄ(x，y)∈(A×Ｃ)∩（B×D)由x,ｙ的任意性,可得：(A∩B）×(C∩D)＝(A×C）∩(Ｂ×D）。５.下列各式中哪些成立,哪些不成立？對(duì)成立的式子給出證明,對(duì)不成立的式子給出反例。１)(A∪B）×(C∪D)＝（Ａ×C)∪（Ｂ×D）２)（A\B)×(C\D)=（A×C）＼（B×D）3）（ＡB)×（CD）=（A×C)（B×D)４）（A\B）×Ｃ=(Ａ×C）\(B×Ｃ）5)（ＡＢ）×C=（A×Ｃ）（Ｂ×Ｃ）[解]1）不成立。設(shè)Ａ={a},Ｂ=，Ｃ={c},D={d｝,則(ａ,-d）∈(Ａ∪Ｂ）×(Ｃ∪D）,但（a,-d)(A×C)∪（B×Ｄ）。所以(A∪B）×(C∪D)=(A×Ｃ)∪(Ｂ×Ｄ）不成立。事實(shí)上有:（A×C)∪（B×Ｄ)（A∪B）×（C）（A∪Ｂ)×（Ｃ∪Ｄ）。2)不成立。設(shè)Ａ＝｛ａ},Ｂ＝{b｝，Ｃ＝D={c},則(a，c)∈(A×Ｃ）＼（B×Ｄ)但（a，c）(A\B）×(C\D）。因而(A\ｂ)×(C\Ｄ)＝(Ａ×C）\（B×Ｄ)不成立。事實(shí)上有：(A\B)×(Ｃ\Ｄ）(A×C）\（B×Ｄ）。由于A\BＡ,Ｃ\D,故有(A×C)\（B×D）Ａ×Ｃ;又若(x,y）∈(A\B）×(Ｃ\Ｄ）故此x∈A\B,從而xB，y∈C\Ｄ,從而yD,故此(x,y）Ｂ×D綜合這兩方面,有(A＼B)×(C\Ｄ)(A×Ｃ）\(Ｂ×D)。３)不成立。設(shè)A＝{a｝,B=｛b},Ｃ＝{a},D＝，則（a,b）∈(AB)×（CD)，但(a,b)(A×C)(B×D)。所以(ＡB）×(CD)（A×C）（B×D）不成立。又設(shè)A={a},B＝｛ｂ},C=｛a}，D={c｝則(ａ，ｃ)∈（A×C)(B×Ｄ)，但(a，c)（ＡＢ）×（CD）。所以（A×C）（Ｂ×D）(AB)×(CD)不成立。因此（AＢ）×(CD）與(A×C）（B×D）無(wú)任何包含關(guān)系?？傊?AB）×(CD）＝(A×Ｃ)(B×Ｄ）不成立。4）成立。證明如下:對(duì)任一（x,y）∈（A\B）×C，有x∈Ａ,xＢ，y∈C于是(x,ｙ）∈A×C,且（x，y）∈（Ａ\Ｂ）×C,且（x,ｙ)Ｂ×C(否則x∈Ｂ),所以（ｘ,y)∈(A×C)＼(Ｂ×C）。因而（A\B）×Ｃ（Ａ×Ｃ）\(B×C）。又對(duì)任一（x，y）∈（Ａ×C)\(B×C)，有(x,y）∈A×Ｃ,且(x,ｙ)B×C從而x∈A，y∈C及xB。即x∈A\B，ｙ∈C,故此（ｘ,ｙ)∈(A＼B)×Ｃ。所以（Ａ×Ｃ）\（B×C)（A×B）×C。因而（A\Ｂ）×C=（Ａ×Ｃ）\（Ｂ×C）。另一種證明方法：(A×B)×Ｃ=（A∩B′）×C(差集的定義)=（A×C）∩（Ｂ′×C)（叉積對(duì)交運(yùn)算的分派律）＝(A×Ｃ)∩（B×Ｃ)′（因(B×Ｃ）′=（B′×C））∩(B×C′)∪（Ｂ′×C′)但（Ａ×C）∩(B×C）′=((A×C）∩（B′×Ｃ））∪=(A×Ｃ）∩(B′×Ｃ))＝(A×C）∩(B′×C)(差集的定義)證法三:（邏輯法)對(duì)任何x,y(x，ｙ)∈(A×C)\(B×C)(x,y)∈A×C（ｘ，ｙ）B×Ｃ(x∈Ay∈Ｃ)(xＢyC)(x∈Ay∈ＣxB)(ｘ∈Ａy∈CyC)(對(duì)的分派律)(x∈AxBy∈C）(x∈Ay∈ＣyC)(的結(jié)合律、互換律)(ｘ∈ＡxB)ｙ∈C(及的零壹律、的結(jié)合律)x∈Ａ\Bｙ∈C(x，ｙ)∈(A＼Ｂ)×C由x,y的任意性,可得：（A＼B)×C＝(Ａ×Ｃ)\(B×Ｃ)。５)成立。證明如下：對(duì)任一（x，y）∈(AB)×C，故此x∈AB,y∈C于是x∈A且xＢ,或者ｘA且ｘ∈Ｂ。因此(ｘ,y)∈（A×C）（Ｂ×C）。所以（AＢ）×Ｃ(A×C)（B×C)。對(duì)任一(ｘ,y)∈(A×C）（B×Ｃ)。則（x，y）∈Ａ×Ｃ且（ｘ,y）B×C，或者（ｘ，y)A×C且（x,y)B×C。因此x∈Ａ，yC，xＢ，或者x∈B,y∈C,xＡ。所以ｘ∈A＼B，或ｘ∈B\A,并且ｙ∈Ｃ，故此x∈AＢ，y∈C。因此（ｘ,y）∈(AB)×C，即（A×C）（B×Ｃ)（AB)×C。綜合兩方面、就有（AＢ)×C=(A×C）（B×C)另一種證明方法:(AB)×C=((Ａ\B)∪（Ｂ\A）)×C（對(duì)稱差的定義）=((（Ａ\B)×C)（（B\A)×C)（叉積對(duì)并運(yùn)算的分派律）=（（A×C)＼(B×C)∪（B×C)\（A×C）)(根據(jù)4））＝（A×C)(B×C)（對(duì)稱差的定義)6．設(shè)A={1,2,3}，B＝{a}，求出所有由A到B的關(guān)系。[解]:R０＝,R１={(1，a）}，R2={(２,a）},Ｒ3={（３，a)},Ｒ4={（１,a）,(２，a)｝，Rs＝{(1,ａ），（3,a）}，R6={(2，a）,(3，a)},R7={(1,a),(２,a),(3，a)}7.設(shè)A={1,2，3，4｝,Ｒ1={（1，3)，(２,2）,(3,4)｝，R２={(1,4),(２，3）,（3，4)},求:R１∪Ｒ2，R1∩Ｒ2，R1\R2，R1′，?(R１），?（R2）,?（R1）,?（R2),?(R1∪Ｒ2），?（R1∩R2）[解]:R１∪R２={(1,3)，(1,4）,（2,２）,（2，3),（3，4)}R１∩R2={（3,4）｝R1\R２={（1,３),(２,2)}R1′＝(A×A)\Ｒ={（1,1），（1,2），(1,4)，(2,1），（2，3）,(2,4），（３,１）,（３,2）,（3,3），（４，1）,(4，2），（４，3)，（4，４）｝（R１）=｛1，２，３}，?(R１）={２,3,4｝，(R2）＝{1，2，3},?(R2)＝{3，４}（Ｒ１∪R２）={1，2，3}，?(Ｒ1∩R2）＝｛4}8.對(duì)任意集合Ａ及上的關(guān)系R1和R2，證明1)?(R1∪Ｒ2）=?(R1)∪?（R2)２）?（Ｒ１∩R２）??（R１)∩?(R2）［證]1）一方面，由于Ｒ1?R１∪R2,R2?Ｒ1∪Ｒ２，根據(jù)定理1,有?(R1）??(R1∪R2)，?(R2)??（R1∪R２)故?（R1)∪?（Ｒ２）??(Ｒ1∪R２）另一方面，若x∈?（R1∪Ｒ２）那么存在著y∈A，使(y,x）∈（Ｒ1∪R2）因此（ｙ,x)∈Ｒ1，或者(y,x)∈R２，從而ｘ∈?（R1)或者x∈?（R２）于是ｘ∈?(R１)∪?（R２）,所以?（R１∪Ｒ2）??(R1）∪?（Ｒ２）。１1.設(shè)A=｛1,2,3,4｝，定義Ａ上的下列關(guān)系R1={(１,1)，(1，2），(3，3),（3，4）}，R2={(1，2),(2,1)}R3=｛（１,1),（１，２),(2,２),（2,1），(3，３),（3，4），(４，３)，(４,４)}R4={(1,2），（２，4)，（３，3），(４，1)}R5={(1,2),(1,３），（1，４),(2,3），（２,4)，(３,4)}R６＝Ａ×Ａ,R７=請(qǐng)給出上述每一個(gè)關(guān)系的關(guān)系圖與關(guān)系矩陳，并指出它具有的性質(zhì)。[解]:1002300410023004R１是反對(duì)稱的，傳遞的。2)Ｒ2是反自反的,對(duì)稱的。３）Ｒ3是自反的,對(duì)稱的，傳遞的，因此是等價(jià)關(guān)系。循環(huán)的綜合這兩方面,就有（R1∪R2）=?（R1）∪?（R2）。2）由于Ｒ１∩R２?R1，R1∩Ｒ２?R２，根據(jù)定理１，有?(R1∩R２)??（R１),?（Ｒ1∩R２）?Ｒ2,所以?(R1∩R2)??(R１)∩?(Ｒ2)反方向的包含不成立,反全由第7題可得，那里?(R1∩R２）＝{4}，?(R1）∩?(R２）=｛2，３，4}∩{3,4}={３,４}因此?(Ｒ1）∩??(Ｒ2)?（Ｒ１∩R２）9.設(shè)A有n個(gè)元素的有限集合，請(qǐng)指出A上有多少個(gè)二元關(guān)系?并闡明理由。[解]A上有2n2個(gè)元關(guān)系。由于叉積A×A有n2個(gè)元素,因而Ａ×A有2ｎ2個(gè)子集，而每個(gè)子集都是A上的一個(gè)二元關(guān)系。１０．定義在整數(shù)集合I上的相等關(guān)系、“≤”關(guān)系、“<”關(guān)系，全域關(guān)系,空關(guān)系，是否具有表中所指的性質(zhì)，請(qǐng)用Y(有)或N(元）將結(jié)果填在表中。性質(zhì)關(guān)系自反的反自反的對(duì)稱的反對(duì)稱的傳遞的相等關(guān)系YNＹYＹ≤關(guān)系ＹＮＮYY<關(guān)系NＹNYY全域關(guān)系ＹNYＮY空關(guān)系NYＹYY4）R4是反對(duì)稱的,循環(huán)的。5）Ｒ５是反自反的,反對(duì)稱的，傳遞的。6）R6是自反的，對(duì)稱的,傳遞的,循環(huán)的。從而是等價(jià)關(guān)系。7)R7是反自反的對(duì)稱的，傳遞的，循環(huán)的，反傳遞的，反對(duì)稱的。R7是反自反的對(duì)稱的，傳遞的，循環(huán)的，反傳遞的，反對(duì)稱的。12．設(shè)Ａ是Ａ上的關(guān)系,證明1）R是自反的當(dāng)且反當(dāng)ＩA?R2)Ｒ是反自反的當(dāng)且僅當(dāng)ＩA∩R=３）R是對(duì)稱的當(dāng)且反當(dāng)R=R是反對(duì)稱的當(dāng)且僅當(dāng)R∩?IA５）R是傳遞的當(dāng)且僅當(dāng)RR?R[證]１）必要性若R是自反的,則對(duì)任何ｘ∈A，都有(x，x)∈Ｒ,但是IＡ＝{(x,x）|ｘ∈Ａ}，所以IA?R。充足性若IＡ?Ａ則由IA={（x，ｘ)|x∈A},可知對(duì)任何x∈A,都有（x，x)∈Ｒ，所以R是自反的。2）必要性若Ｒ是反自反的，則對(duì)任何ｘ∈A，都是（x,x)R,從而（x,ｘ）∈R′,由IA={(x,ｘ)|x∈A}可知IＡ?R′。于是IA∩R?R′∩R＝,此外?IA∩R，所以IＡ∩Ｒ=。充足性若IA∩R=,則R是反自反的。否則，不是反自反的,那么應(yīng)存在某一x0∈A,使得(x０，x０）∈Ｒ。但是(ｘ0，ｘ０）∈IA,從而（x0，ｘ０)。這不也許，矛盾。3)必要性,若R是對(duì)稱的，則對(duì)任何（x,y）∈Ｒ,就有(ｙ,x）∈R。于是根據(jù)逆關(guān)系的定義,可得(x，y)∈,于是R?;對(duì)任何(x,ｙ)∈,由逆關(guān)系的定義，可得(y,ｘ）∈R。再次運(yùn)用R的對(duì)稱性有(y，x）∈Ｒ,于是?R;綜合兩方面,有R=。充足性若R=，則對(duì)任何（ｘ,y)∈R，由R=可得（x,y)∈。從而由逆關(guān)系的定義，可知（y,x)∈Ｒ這說(shuō)明R是對(duì)稱的。4）必要性若R是反對(duì)稱的,則對(duì)任何(ｘ，y）∈，即有（x，y)∈R及(ｘ,y）∈,從逆關(guān)系的定義，就有(x,y）∈R及（y，x)∈R，因此，運(yùn)用R的反對(duì)稱性,可得x=y。于是就有(x，ｙ）＝（ｘ,x)∈IA,所以Ｒ∩?IA。充足性若R∩?IA,則對(duì)任何（ｘ，y）∈Ｒ及（y,ｘ)∈R,從逆關(guān)系的定義,可得（ｘ，y)∈R及（x,ｙ)∈，也即（x,y)∈R∩,運(yùn)用Ｒ∩＝IＡ可得（x，y)∈IＡ，于是x=y。所以R是反對(duì)稱的。５）必要性若R是傳遞的,則對(duì)任何(x，y）RоＲ，由復(fù)合關(guān)系的定義可知,存在著ｙ∈A，使（x，ｙ）∈R且（ｙ,y)∈Ｒ，從而運(yùn)用R的傳遞性，可知（x,y)∈Ｒ。所以ＲоR?R。充足性RоR。從而運(yùn)用RоＲ?R可得（ｘ,y）∈R。所以R是傳遞的。證法二:１)）:對(duì)任何x，x∈A（ｘ,x)∈IA(IA是幺關(guān)系，因此是自反關(guān)系)(x,ｘ）∈R（R是自反關(guān)系)所以IAR；):對(duì)任何ｘ∈A，x∈A(x，x)∈ＩA(ＩＡ是幺關(guān)系，因此是自反關(guān)系)（x,x）∈R（因IAR)所以,R是自反關(guān)系;2))一方面ＩＡR；另一方面,對(duì)任何x,y∈Ａ,若(ｘ,y)∈IＡＲ(x,y)∈IA(x,y）∈Rx=y（x,y)∈Ｒ(IA是幺關(guān)系，因此是自反關(guān)系)(x,ｘ)∈R則與R是反自反關(guān)系,（ｘ,ｘ）R矛盾。故ＩAR；因此,由包含關(guān)系的反對(duì)稱性，可得IＡR＝;)：對(duì)任何x∈A,若（x，x)∈R(ｘ,x)∈ＩA(ｘ,ｘ)∈R(IＡ是幺關(guān)系,因此是自反關(guān)系)(x,x)∈IAR（x，x）∈(因IAＲ=)則與空集不含任何元素,（x,ｘ)矛盾。故對(duì)任何x∈Ａ，（x,x)R;所以,R是反自反關(guān)系;3)）對(duì)任何x,y∈A(x,y)∈Ｒ（ｙ,x)∈Ｒ（R是對(duì)稱關(guān)系）(ｘ,y)∈所以，R＝;)：對(duì)任何x，y∈A(x,y)∈Ｒ(x,ｙ)∈(R=)(y,x）∈R所以,R是對(duì)稱的;4))對(duì)任何ｘ,ｙ∈A(x,y)∈R(ｘ，y）∈R(x,y)∈(x,y)∈R(y，x）∈Rx＝y(tǒng)(Ｒ是反對(duì)稱關(guān)系）(x,y）∈ＩA(IA是自反關(guān)系)所以,ＲＩＡ;):對(duì)任何x，y∈Ａ(x，y)∈Ｒ(x,y）∈（R=)(y,x)∈R所以,R是對(duì)稱的;１3.設(shè)Ａ、B為有窮集合,R，Ｓ?A×B，MＲ=(xｉｊ)m×n,ＭS=（yｉj)m×n1）為了Ｒ?S，必須且只須ij（xij≤yij）2）設(shè)ＭR∪S=（Ｚij）ｍ×n，那么Ｚiｊ=xｉｊVyｉj,I＝1,2……,m，j=1,2,……n．3)設(shè)MR∩S=（tij)ｍ×n，那么tｉj=xij^yｉji=1,2，……ｍ;j＝１,2,……，ｎ.[證]由于A、B是有窮集合，不妨設(shè)A=｛ａ1，a2……，am},B＝{b1，ｂ2，……,bｎ}1)必要性若R?S，則對(duì)任何ｉ∈{１,２,……，m},對(duì)任何ｊ∈｛１,2，……n}，若（aｉ,bj）∈R,則R的關(guān)系矩陣ＭR＝(xij)ｍ×ｎ中第Ｉ行第j列元素ｘij=1，根據(jù)R?Ｓ,可得(ai，bj）∈S，從而得S的關(guān)系矩陣MS=(yij)m×ｎ中第I行第j列元素yiｊ=1,由于是1≤1故此xij≤ｙij;若(ai,bj)Ｒ,則Ｒ的關(guān)系矩陣ＭR=（xij）m×n中第i行第j列元素xij=０,因此由S的關(guān)系矩陣MS=(ｙｉj）m×n中第j列元素yij≥0，可得ｘij≤yij。總之,有（ｉ）（j）(xｉj≤yij）。2)充足性若(ｉ)(ｊ）（xｉｊ≤yij），則對(duì)任何(ａi,bｊ)∈R，就有R的關(guān)系矩陣MR＝（xij）m×ｎ中第i行第j列元素xiｊ=1，由于xiｊ≤yij，所以yiｊ≥１，故此yｉｊ≥１這說(shuō)明S的關(guān)系矩陣MS＝(yij)m×n中第i行第j列元素yij為1，因此必有(ai,bｊ)∈S，所以R?Ｓ。２）對(duì)任何i∈{1,2,……,ｍ}，對(duì)任何j∈{1,2,……，n｝若Ｚij＝1，則(ai，bｊ)∈Ｒ∪S,故此(ａi，bj)∈Ｒ或者(ａi,bj）∈Ｓ,于是xｉｊ＝1或者yij＝1。從而bj)?S，于是ｘij=0且yij=0。從而xｉj∨yij＝0。因而Zｉｊ=xij∨yij＝0;綜合上述兩種情況,就有zji=ｘij∨yij，ｉ=1，２,……,m,ｊ=1，２,……ｎ,。3）對(duì)任何i∈｛1，2,……m},對(duì)任何j∈{1,2,……，n}。若ｔij=１，則(ai，ｂj)∈R∩S,故此(ai,bｊ）∈Ｓ且(ａi,bj）∈S,于是xｉj＝1,且ｙij=1從而xij∧yiｊ=1。因而tij=xij∧ｙｉｊ=1;若tij=０，則(ａi,ｂj）?R∩Ｓ，故此(ａi，bｊ）?Ｓ，于是xｉｊ＝０或者yｉj=0,從而xｉj∧ｙij=0。因而tij=xｉj∧yｉj=0。綜合上述兩種情況,就有ｔiｊ=xｉj∧ｙiｊ，i=1，２,……,m,j=1，2,……,n。１4．設(shè)A＝{1，2，３，4}，R1,R2為A上的關(guān)系,R1={(1,1),(1，2),（2,4)｝,R2＝｛（1，4)，(2,３)，（2，4),（３,2）}，求R1оR2,Ｒ2оＲ1，R1оR2оR1［解]，１)無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR2={（1，3），（1，4）}無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR2={（1，3），（1，4）}Ｒ1R22)無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R2оR1無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R2оR1={（3，4）}Ｒ2R１３）無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR2無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR2оR1=4）無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR1о={（1，1），（1，2），無(wú)論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR1о={（1，1），（1，2），（1，4）}Ｒ1R１R11５）設(shè)R1，R２,R3是A上的二元關(guān)系,假如R1?R2，證明1）R1R３?R２R３２)R３R１?Ｒ3Ｒ２［證明]1)對(duì)任何（x，ｙ)∈R1R3，由復(fù)合關(guān)系之定義,必存在z∈A,使得(x，z）∈R1且(z，y）∈R3,運(yùn)用R1?R2可知(x，z）∈R２且(z，y）∈R3,再次運(yùn)用復(fù)合關(guān)系之定義,有（x,y)∈R2Ｒ3。所以R1R3?R2Ｒ３。2）對(duì)任何（x,ｙ）∈R3Ｒ1,由復(fù)合關(guān)系之定義，必有ｚ∈A，使得(x,z)∈R3且（z，y)∈R1，再由復(fù)合關(guān)系之定義,有（x，y)∈R3R２。所以Ｒ3R1?R３Ｒ2。16.設(shè)A是有限個(gè)元素的集合，在A上擬定兩個(gè)不同的關(guān)系R1和Ｒ2,使得=R１,=R2?? 由于，令R1=，則Ｒ１R１=,故此＝R1＝。令R2=Ａ×A，則=R2R2?A×Ａ＝R2,故需證明R２?R２οR２=。為此，對(duì)任何ｘ,ｙ∈A,(x,y)∈A×A=R2,一定存在著z∈A（至少有z=x或z=ｙ存在)，使(x,z)∈A×A＝R2且（ｚ,y)∈A×A＝R2，故此（ｘ,y)R2Ｒ2=，所以R２?Ｒ2R2=。于是=R2=A×Ａ。２)由于A是有限個(gè)元素的集合,是不心設(shè)A={a1，a2，……an}令R1=｛（ai，aj)|aｉ∈A∧ａｊ∈A∧|≤i≤n∧|≤ｊ≤ｎ-|}Ｒ２={(ａｎ，ａn）∪Ｒ1}則R1R2,即R1與R1是不同的關(guān)系。我們來(lái)證明=R１,=Ｒ2，(ａ）先征=R1若(ai,ａｊ）∈R１，則由R1的定義必然1≤i≤n，１≤i≤ｎ-1,并且一定存在著1≤ｋ≤n-1（至少有k=j存在)，使(aｉ，aｋ）∈R1且（ak，aｊ)∈R1，從而（ai,aj）∈Ｒ1R1＝。故此Ｒ1?。若(ai，aｊ）∈＝Ｒ1R1，則存在著k,１≤k≤n-１，使(ai,ak）∈R１且（aｋ,aｊ）∈R１，于是由Ｒ1的定義，必有1≤i≤n，１≤j≤n-1，從而根據(jù)R1的定義，有(ai,ａj)∈R1。故此=R1綜合兩個(gè)方面，可得=R1。(b)次證=R2若（ai,ａｊ）∈R２,則由R２的定義,要么１≤i≤n，1≤j≤ｎ－1,要么I=n，j=n若1≤ｉ≤ｎ,１≤j≤n－１,則一定存在著1≤k≤n-1(至少有ｋ=j存在），使(ａi，ak）∈R２且（ak,aj）∈R2,從而（ａi,aj)∈Ｒ2οＲ2=；若i=ｎ，j＝n,則（ai,aj）=（an,an)∈Ｒ2，那么（ａｎ,aｎ）∈R2，所以（aｉ,ａj）=(an，an）∈R2οR２＝因此R2=。若（ai,ａｊ)∈=R2οR2，則存在著k，使(ai,ａｋ)∈Ｒ2且(ak,ａi）∈R２,于是由Ｒ2的定義,有ｋ＝n或者１≤ｋ≤n－1。若k=n，則由(ai,ak）∈R2必有I=n,所以無(wú)論1≤j≤n－1還是j=n，由R2的定義，有(ａi,aｊ）=(an,aj）∈R2;若1≤ｋ≤n-１,則由（aｉ,ａk)∈Ｒ2必有1≤j≤n－1故此(ai，aj)∈R2總之證得=R2，綜合兩方面，我們證明了=R2。17.設(shè)Ｒ是集合A上的反對(duì)稱關(guān)系,|A|=ｈ,指了在R∩的關(guān)系矩陣中有多少個(gè)非零值？［解]由第１2題的４)R是反對(duì)稱關(guān)系當(dāng)且反當(dāng)R∩?IA，及|A|=n可知,在R∩的關(guān)系矩陣中非零值最多不超過(guò)n個(gè)。18.設(shè)R１和Ｒ２是集合A上的關(guān)系,判斷下列命題的真假性,并闡明理由。假如R1和R2都是自反的,那么Ｒ1Ｒ２是自反的。假如R1和Ｒ２都是反自反的,那未R1R2是反自反的。假如R１和Ｒ2都是對(duì)稱的，那末Ｒ1Ｒ２是對(duì)稱的。假如Ｒ１和R2都是反對(duì)稱的，那末R１R２是反對(duì)稱的。假如R1和Ｒ２都是傳遞的，那末R１R2是傳遞的。［解］1）真。由于R１和R２和R2都是自反的，因而對(duì)任何,都有(ｘ,x)∈R１,（x,x）∈R2。因此，對(duì)任何x∈Ａ，都有(x，x)∈R１R2。所以Ｒ1Ｒ2是自反的。２)假。令Ａ＝｛a，b}，R1=｛（a，b）}，R2={b,a}。那么R1R２={(a，a)}，它就不是A上的反自反關(guān)系。3)假。令Ａ={a，ｂ，c｝,Ｒ1={(a，b)，(b,a）},R2＝｛（ｂ,c)，(c，b）}。那末R1R2={(ａ，ｃ)},就不是A的對(duì)稱關(guān)系。4）假。令A(yù)=｛a，b，c，ｄ},Ｒ1=｛(ａ，ｃ)，(ｂ,c)}R２={(c，b）,(d，a）}易證R1，R2都是反對(duì)稱關(guān)系。但是Ｒ1Ｒ２＝｛（ａ，b)，（b，a）}就不是A上的反對(duì)稱關(guān)系。5)假。令A(yù)=｛a，b，c},R1={(ａ，c),（b，a)，(b，c）｝，R2＝{（c,ｂ）,（ａ,c），(a,b）}，易證R1和R2都是傳遞關(guān)系，但Ｒ1R2={（a,b),(b,b）,（b,c）｝就不是Ａ上的傳遞關(guān)系。19.設(shè)A＝{1，2，3，4,５}，R?Ａ×Ａ，R=｛(1,2),(２,3)，(2,５),（3，4),（4,3),(5，5）｝用作圖方法矩陣運(yùn)算的方法求r（R)，s（R),t(R)。[解]1）作圖法:R的關(guān)系圖（R）的關(guān)系圖55123412345515143253241S(Ｒ）的關(guān)系圖ｔ（R)的關(guān)系圖因此：r(R)={（1，1）,(1,2），(２，2),(２,３）,(2，5),(３，3）,（3，４），(4,3），(４，4），(5，5)}s(R)=｛(1,2），(2,1），(2,３),（2,5）,(３,2）,（３,4),（４，3)，(５,2）,(５，5)}t(R)={（1,2)，(1,3）,(1,4),(1，5)，(２，３）,(2，4),（2，5），（3，3），（３,4)，(４，３),（4，4)，（５，５)}2）矩陣運(yùn)算法:Ｍｒ(Ｒ）＝=MＳ(Ｒ)=＝==MＲοR=MRMR===MＲ＝因此r（Ｒ)，s（R),t（R）與1）作圖法一致。２0．設(shè)R?A×A，證明１）(R+)++R+2)=R*[證明]1)一方面，由于（R+）+是R+的傳遞閉包,所以R+?(Ｒ＋)＋;另一方面，由于R+是Ｒ的傳遞閉包，故此Ｒ+是傳遞的。由于Ｒ+?R＋及傳遞閉包（R＋)+是包含R+的最小傳遞關(guān)系,就有(Ｒ＋）+?R＋(定理4之3);所以(Ｒ+）+=R+。２)一方面，由于(R*)*是R*的自反傳遞閉包，所以R*?(R*）＊；另一方面,由于R＊是Ｒ的自反傳遞閉包,故此Ｒ*是自反的傳遞的。由于R*?R*及自反傳遞閉包(Ｒ*）*是包含Ｒ*的最小自批傳遞關(guān)系,就有（Ｒ*)*?Ｒ*（定理5的3))。所以(R＊）*=Ｒ＊。21.設(shè)Ａ={1，２，3,４｝，RAA，R＝{(1，2),(２，4),（３，4),（4，3),(3,３)}1)證明R不是傳遞的;2）求R1,使 R1?R并且R1是傳遞的;3)是否存在R2，使R2?R，R2≠R1并且Ｒ2是傳遞的。[解]1）由于（１，2)∈R且（2，４）R但（1，4)?Ｒ,這說(shuō)明Ｒ不是傳遞的。2)由于R+是包含R的最小傳遞關(guān)系，所以,?。?＝R＋即為所求。現(xiàn)在來(lái)Ｒ+R２＝｛(1,4）,(2，3)，(3，３），（3,４），}(4,3）,（4,4）}R3=｛（1，3)，（2，３),(2，４），(3，3）,（3，4），（4,3)，(4,4）}R4={（1，3）,(1,４),(2,3),(２，４），（3，3），(３，４）,（4,3),（4，4）}故此R1=Ｒ+=Ｒ∪R２∪R3∪Ｒ4=｛(1,2）,(1，3），(1,4),（2，3)，（2,４），（3,３）,（３,4）,(4，3）(4，4）}（由于｜A|=４有限）其關(guān)系圖如下:11124311243Ｒ的關(guān)系圖R1的關(guān)系圖３)能。由于R１并非全關(guān)系(否則，當(dāng)R１是全關(guān)系時(shí),就找不到了）,所以只要取R2=A×A是A上的全關(guān)系就可滿足R2?R，R2≠Ｒ,并且全關(guān)系Ｒ２顯然是一個(gè)傳遞關(guān)系。22.設(shè)A={1，2,3，４……,９},定義A×A上的關(guān)系如下：（a，b)R(ｃ，ｄ）∷a＋d=b+ｃ證明Ｒ是A×Ａ上的等價(jià)關(guān)系;求[（2，5)］R；R?A×A對(duì)嗎？請(qǐng)闡明理由。1）[證明]（a)Ｒ是自反的對(duì)于任何(ａ，b）∈Ａ×A，由于a+b＝b＋a,所以（ａ，b)R(a，b）。（b)R是對(duì)稱的對(duì)于任何(a，ｂ),(ｃ,d)∈A×A，若(a，b)R(ｃ,d)，則有a＋d=b+c從而ｃ＋b+a，所以可得（ｃ，d)R（a，b)。(c）Ｒ是傳遞的對(duì)于任何（a,ｂ)，(c,ｄ)，（ｅ，f）∈A×A,若（ａ,b）Ｒ(c,d）,且（c,ｄ)R(e，f），于是有a＋d=ｂ+ｃ及c＋f=d＋e，二式相加有a+f+c+d=ｂ+e+c＋ｄ，兩邊同時(shí)減c+d,可得ａ+ｆ=b＋e,從而可得(a,ｂ)Ｒ(ｅ,ｆ)。綜合(a)、（b）、（ｃ）、說(shuō)明R是Ａ×Ａ上的等價(jià)關(guān)系。2）[解］由于{（２，5）}R＝{(a，ｂ）|（a，ｂ）∈A×A(a，b）R(２,５）}=｛(a,b)|(a，ｂ)∈A×A∧a＋5=b+2}={(a，b）｜（a，ｂ）∈Ａ×A∧b＝a+3}={（1，4)，（2,５,(3,6),(4，7）,（5，8）,（６，9）)3）[答］Ｒ?Ａ×Ａ不對(duì)。由于R是A×A上的關(guān)系，所以R?(A×A）×(A×A）=。23．設(shè)A是一個(gè)非空集合，R?A×A。假如R在A上是對(duì)稱的，傳遞的，下面的推導(dǎo)說(shuō)明R在A上是自反的:對(duì)任意的ａ，ｂ∈A，由于R是對(duì)稱的，有：aRbbRa于是ａRbａRb∧bRａ，又運(yùn)用R是傳遞的，得：aRb∧ｂRaａRａ從而說(shuō)明R是自反的。上述推導(dǎo)對(duì)的嗎？請(qǐng)闡明理由。[答］上述推導(dǎo)不正解。推殖民地的謬論誤在于假設(shè)A的每個(gè)元素都由Ｒ關(guān)聯(lián)著A的某一別的元素。假如這不是真的，那么對(duì)稱性的條件的假設(shè)就始終是假的，因此結(jié)論當(dāng)然是假的。因而在一個(gè)空集上的空關(guān)系都是平凡的對(duì)稱和可傳遞,但不是自反的。此外關(guān)系{（a,a),(ｂ，b),(ａ，ｂ),(b,a）}是自反的和傳遞的，但在集合{a，b，c}上不是自反的。2４.設(shè)R是集合A上的等價(jià)關(guān)系,證明也是集合A上的等價(jià)關(guān)系。[證明]證法一：(a)是自反的對(duì)任意的a∈A，由于R是自反的,所以(a，ａ)∈R，再由逆關(guān)系的定義有（a,a)∈（b）是對(duì)稱的對(duì)任何(a，ｂ）∈由逆關(guān)系的定義,有（b，ａ)∈R，由R的對(duì)稱性,可得(a,ｂ）∈R,再由逆關(guān)系的定義,就有（b,a)∈。（ｃ)是傳遞的對(duì)任何（ａ,b)∈及(b，c)∈,由逆關(guān)系的定義，有(ｂ，a)∈Ｒ及（c，ｂ)∈R,根據(jù)R的傳遞性,可得（c,a)∈Ｒ,再次由逆關(guān)系的定義,就有（ａ,c）∈。綜合(a)（b）（c)可知是等價(jià)關(guān)系。證法二：(a）是自反的：對(duì)任何ａ，aA(a,a)R(R都是自反的)(a，a)所以,是自反的；（b）是對(duì)稱的:對(duì)任何a，ｂＡ,(a,b)(ｂ,a)Ｒ（a，ｂ)Ｒ(R是對(duì)稱的）(b,a)所以,是對(duì)稱的；(ｃ）是傳遞的:對(duì)任何a，b,cA，（a,b)（ｂ,c)((ｂ，a)R(c,b)R((c，ｂ)R(b,a)R（的互換律)（c,ａ）R(R是傳遞的)(a,c)（R是對(duì)稱的）所以，是對(duì)稱的；綜合（a)、（b)、(ｃ），可知是A上的等價(jià)關(guān)系。2５．設(shè)R1和R２都是集合Ａ上的等價(jià)關(guān)系１）證明R１∩R２也是A上的等價(jià)關(guān)系；2)用例于證明R1∪R2不一定是A上的等價(jià)關(guān)系（要盡也許小地選取集合A）。[證]１)證法一：（a）Ｒ１∩R2是自反的對(duì)任何ａ∈Ａ,由于Ｒ1,R2都是A上的自反關(guān)系,所以（a,ａ)∈R1（a，ａ）∈R2，因此(a，a)∈R1∩R2（b)R1∩Ｒ2是對(duì)稱的對(duì)任何的（ａ，b)∈R1∩Ｒ2,就有（a，ｂ)∈R1且(a,b）∈R2,由R１，Ｒ2都是Ａ上的對(duì)稱關(guān)系，所以（ａ，ｂ）∈R1且（ｂ,a)∈Ｒ2,所以(b，a）∈Ｒ1∩R2。(ｃ)Ｒ1∩R２是傳遞的對(duì)任何的(ａ，b)∈R1∩Ｒ2及（b，c）∈R1∩R2，就有(a，b)∈Ｒ1，（a，ｂ)∈Ｒ２及（b,c）∈R1,(b，c)∈R2,于是（a，b）∈R1且(ｂ,c)∈R1及(ａ，b)∈Ｒ2且（b，c）∈R2由于R1，Ｒ2都是Ａ上的傳遞關(guān)系,所以(a,c）∈Ｒ１及（a，c）∈R2，因此(ａ，c)∈R1∩R2。綜合(ａ）,(b），（c），可知R1∩R2是等價(jià)關(guān)系。證法二:(a）R１∩R2是自反的:對(duì)任何a，ａA(a，ａ)Ｒ1(a，a）R2（R1，Ｒ2都是自反的)(a,a)Ｒ1R2所以,R1R２是自反的；(b）R1∩R2是對(duì)稱的:對(duì)任何a，bA，(a，b)R1R2（a,ｂ)Ｒ1(a，b)R２(b,a)R1(b,ａ）R2（R1,R2都是對(duì)稱的)(b,a)Ｒ1R２所以，R1R2是對(duì)稱的；（ｃ)Ｒ1∩R2是傳遞的:對(duì)任何ａ,b,cA，(a,b)Ｒ1R2(b，ｃ)Ｒ1R2((a,b）R１（a,ｂ)Ｒ2）（（ｂ,c)R1(b，c)R2)（（ａ,b)R１（ｂ，c)R1）(（ａ,b)R2(b,c)R2)(的結(jié)合律、互換律)(ａ,c)R1（a,c)R2（R1，R２都是傳遞的）(a,c)R１R２所以，R１R2是對(duì)稱的;綜合(a）、(ｂ)、(c），可知R1R2是A上的等價(jià)關(guān)系。2)兩個(gè)自反的(對(duì)稱的）關(guān)系的并將是自反的（對(duì)稱的）,但是，兩個(gè)傳遞關(guān)系的并卻未必是傳遞的。我們就從破壞傳遞性出發(fā)來(lái)構(gòu)造反例：令R1={(a，a）,(ｂ,b），（ｃ，c）,(a，b),(b，a)｝R2＝｛(ａ，a)，（ｂ，b)，(c,c),（b，c)，(ｃ，ｂ）｝當(dāng)A={a,b，c｝時(shí),R1,R2顯然都是等價(jià)關(guān)系。但是abcabcabcR1∪R２＝{(a，a)，(b，ｂ),(c,c)，（a,b），（b，a)(ｂ,c）,(c,b)}都不是A上的等價(jià)關(guān)系,由于R１∪R２不傳遞:(a,b）∈R１∪R2且（bc,但(a，c)?R1∪R2;同樣(c,b）∈Ｒ1∪R２且（ｂ，a)∈Ｒ1∪R2,但（c，ａabcabcabcR1關(guān)系圖R2關(guān)系圖Ｒ１∪R２關(guān)系圖并且|A｜不也許再少了。由于任何少于3個(gè)元素的集合上的自反，對(duì)稱關(guān)系一定是傳遞的!26.設(shè)R是A上的等價(jià)關(guān)系，將Ａ的元素按R的等價(jià)類順序排列,請(qǐng)指出此等價(jià)關(guān)系R的關(guān)系矩陣ＭＲ有何特性？[解］將A的元素按其上的等價(jià)關(guān)系R的等價(jià)類順序排列,這樣產(chǎn)生的等價(jià)關(guān)系Ｒ的關(guān)系矩陣MＲ，通過(guò)適當(dāng)?shù)木仃嚪謮K,MR的分塊矩陣將成為準(zhǔn)對(duì)角陣，準(zhǔn)對(duì)角陣的對(duì)角線上的每一塊都是一個(gè)全1方陣，它正好相應(yīng)于等價(jià)關(guān)系R的一個(gè)等價(jià)塊。27.設(shè)A是n個(gè)元素的有限集合,請(qǐng)回答下列問(wèn)題,并闡明理由。有多少個(gè)元素在A上的最大的等價(jià)關(guān)系中？A上的最大的等價(jià)關(guān)系的秩是多少?有多少個(gè)元素在A上的最小的等價(jià)關(guān)系中？A上的最小的等價(jià)關(guān)系的秩是多少?[答]1)A上最大的等價(jià)關(guān)系是全關(guān)系R１＝Ａ×A={(a，ｂ）|a∈A∧b∈Ａ}因此有n2個(gè)元素在Ａ上的最大的等價(jià)關(guān)系R1中，由于所有n2個(gè)二元組都在R1=A×A中。2)A上的最大的等價(jià)關(guān)系R１的秩是1。這是由于Ａ中任何兩個(gè)元素都有全關(guān)系R1＝A×A,因此R1的等價(jià)塊包含了A的所有元素，Ａ的所有元素都在同一個(gè)等價(jià)塊中。3)A上的最小的等價(jià)關(guān)系是么關(guān)系R２＝IA={(ａ，a)ａ∈A}因此它中有ｎ個(gè)元素,即n自反對(duì)。4）A上的最小的等價(jià)關(guān)系的秩是n,由于么關(guān)系的每一個(gè)元素都自成一個(gè)等價(jià)塊,每一等價(jià)塊中也只有一個(gè)元素。2８.設(shè)Ｒ1和Ｒ2是非容集合A上的等價(jià)關(guān)系，對(duì)下列各種情況,指出哪些是A上的等價(jià)關(guān)系；若不是,用例子說(shuō)明。１）A×A＼R１2）R1\R23)4）r(Ｒ１＼R2）(R1＼R2的自反閉包)5）R1R2[解]1)不是。設(shè)A={ａ｝，并且R1={(a，a）｝，則R1是Ａ上的等價(jià)關(guān)系，但A×A＼R1＝{(a，a）\(a,a)｝=就不是Ａ上的等價(jià)關(guān)系,由于空關(guān)系不是自反的。2)不是。設(shè)A=｛(a,ｂ）｝并且R1=｛（a，a）,(b，b)，(a,ｂ），(b,ａ）},Ｒ2=｛(a，ａ），(b，b)},則R１，R２都是Ａ上的等價(jià)關(guān)系,但是,R１\Ｒ2={（a，ｂ),(b,a)}就不是A上的等價(jià)關(guān)系，由于R1\R2不自反。3）是。證法一:因R1是等價(jià)關(guān)系，因而R1是傳遞的,故此由第1２題之5）有＝R1R1?Ｒ１。另一方面，結(jié)任何（a，ｂ)∈R1,由于R1是自反的,故此(b，b)∈R1，從而由復(fù)合關(guān)系之定義，有(a，ｂ）∈Ｒ1R1,所以R１?，從而＝R1,因此由Ｒ1是等價(jià)關(guān)系,知也是等價(jià)關(guān)系。證法二：一方面,對(duì)任何a,bA，(a,ｂ)（cＡ）（(a,c)R1(ｃ,b)Ｒ１)(cA)((ａ，b)R1)（R１是傳遞的）(ａ,b)R1（帶量詞的基本邏輯等價(jià)式:(x)pｐ）所以，Ｒ1;另一方面,對(duì)任何a，ｂＡ,(a,b)Ｒ1(a,ｂ)R1（ｂ，b）R1)(R1是自反的)（a,b)所以，R1;綜合這兩方面，就有=R1；4）是。設(shè)Ａ={a,b,c}，R1＝｛(a,a），(b,ｂ），(c,c），（a，ｂ）,(b,a）,(ａ,c)(ｃ,a）,(ｂ，c）,（c,b）}。R1=｛(a,a），（ｂ,b）（c，ｃ)(a，a）（c,a）}，則R1，Ｒ2都是A上的等價(jià)關(guān)系。R1＼R２={（a，ｂ），（ｂ，a)，（b，ｃ），(c，b）}ｒ(R１\R2)=｛（a，a），（b，b)，（c，c）,（a，ｂ），（b,ａ），(b,c）,（c,b）｝因此r(R1＼R2）不是Ａ上的等價(jià)關(guān)系，由于r（R1＼Ｒ２)不是傳遞的，(a，b)∈ｒ（R1\R2）且（b,c）∈r（R1＼Ｒ2),但是（a，ｃ)?ｒ(Ｒ１\R2）。5）不是。令Ａ={a,b，ｃ}，R1={（a，a),（b,ｂ），(c，c)，(ａ,b），(b,a)}，R2={（ａ，ａ）,(b,ｂ)，（c，c)，（a,b），（b，a），（b,c),(ｃ,b),（ａ，c）}不上的等價(jià)關(guān)系，由于R1R2不對(duì)稱，(a，c）∈Ｒ1R2,但（c，a）?R1R2。29.設(shè)A={1，2，3,４},請(qǐng)指出Ａ上所有等價(jià)關(guān)系是多少？并闡明理由。[解]A上的等價(jià)關(guān)系共有15個(gè)。根據(jù)A上的劃分與A上的等價(jià)關(guān)系一一相應(yīng)的原理，我們只需求出A上有多少個(gè)劃分就行了。{｛a｝，｛b｝,{c},{d｝}型劃分，一個(gè);{｛a，b｝，｛ｃ},{d｝}型劃分，六個(gè);｛{a,b，｝，{c,d}}型劃分,三個(gè)；{{a,b，c｝,{d｝}型劃分，四個(gè);{｛ａ,ｂ,c，d｝｝型劃分，一個(gè)?？傆?jì)：1+6+3＋4＋１=１5。3０．設(shè)A={１,2,3，４,５,６｝,擬定Ａ上的等價(jià)關(guān)系R，使此R能產(chǎn)生劃分｛{1,2，3，}，{4},{5，6｝}123123564R的關(guān)系圖3１.設(shè)R是集合A上的關(guān)系Ｒ是循環(huán)∷=（ａ∈A）（b∈A）（c∈A)（aＲｂ∧ｂRｃcRa）證明:R是自反的和循環(huán)的,當(dāng)且僅當(dāng)R是等價(jià)關(guān)系。[證]證法一:必要性若Ｒ是自反的和循環(huán)的，我們來(lái)證R是等價(jià)關(guān)系,為此證明(ａ)R是自反的。必要性條件所給。(ｂ)R是對(duì)稱的對(duì)任何（a,b)∈R，由于R是自反的，所以(ｂ,ｂ）∈R,再根據(jù)R是循環(huán)的可得(b，a）∈R。（ｃ)R是傳遞的對(duì)任何（a,b)∈Ｒ，(b,c）∈R，由于R是循環(huán)的,所以（c,a）∈Ｒ,運(yùn)用R是對(duì)稱的,就得到（a,ｃ）∈R。充足性若R是等價(jià)關(guān)系，我們來(lái)證R是自反的和循環(huán)的。1)Ｒ是自反的。因R是等價(jià)關(guān)系，故R是自反的。２)R是循環(huán)的對(duì)任何(a，b）∈R,(b,ｃ)∈R,由于R是傳遞的，所以(a，c)∈R。由于Ｒ是對(duì)稱的,（c，ａ）∈R。證法二：)：(ａ）Ｒ是自反的:已知；(b）Ｒ是對(duì)稱的:對(duì)任何a,bA，（a,ｂ)Ｒ(ａ,ｂ)R(ｂ,b)R(R是自反的）（b,a）R(R是循環(huán)的)所以，Ｒ是對(duì)稱的;（c)R是傳遞的：對(duì)任何ａ,b，ｃA，(ａ,b)R（b，c)R(ｃ,ａ)R(R是循環(huán)的)（ａ，c）R（R是對(duì)稱的）所以,Ｒ是傳遞的;綜合(a),（b),（c)可知R是等價(jià)關(guān)系;)：(ａ）R是自反的：由于R是等價(jià)關(guān)系,所以R是自反的;（ｂ)R是循環(huán)的:對(duì)任何ａ，ｂ,cＡ,（ａ,b)R（b,c)Ｒ(ａ，c)R(Ｒ是傳遞的)（c,a)Ｒ(R是對(duì)稱的)所以，R是循環(huán)的;32.設(shè)∏１和∏2是非空集合A的劃分,說(shuō)明下面各種情況哪些是A的劃分？哪些不是A的劃分?哪些也許是A的劃分?并闡明理由。１）∏1∪∏22）∏１∩∏23)∏1\∏24)(∏1∩(∏2\∏1）)∪∏１[解]1）也許。假如∏1=∏2，則∏1∪∏2是Ａ的劃分;假如，∏１≠∏2,則∏1∪∏2不是A的劃分;例如Ａ＝{ａ,b｝，∏１={{a}，},∏2={｛a，b}},但∏１∪∏２＝{{a}，,{a,ｂ｝}就不是Ａ的劃分，由于{a｝∩{ａ，b｝={ａ}≠,就不是Ａ的劃分，由于{a｝∩｛a,b}＝{a}≠。2）也許。假如∏１=∏2，則∏1∩∏2是A的劃分；假如，∏1≠∏2,則∏1∩∏２不是Ａ的劃分；例如A={ａ,b}，∏1={｛ａ}，}，∏2={{a,ｂ}},∏1∩∏２=，就不是Ａ的劃分。3）也許。假如∏1∩∏2=,則∏１\∏２=∏1是A的劃分；假如∏1∩∏２≠，則∏1＼∏2不是A的劃分；例如A={a，b，c｝，∏１={{a},｛b},{c}},∏2={｛a}，｛b，c}｝，∏１∩∏2={{a}}因此∏1\∏2＝{{ｂ}，{ｃ}｝就不是A的劃分。由于∪｛c}=｛ｂ,c}≠A。4)是。由于（∏1∩(∏２\∏1)）∪∏１=∪∏1=∏1,是Ａ的劃分。３3．對(duì)下列集合上的整除關(guān)系畫出哈斯圖,并對(duì)3)中的子集{2,3，6},{2,４，６}，{４，８，12}找出最大元素,最小元素，極大元素,極小元素,上確界,下確界。１){1，2,3,4}2）｛2,３,6,12,24,3６}３）{1，2，３,4,5,6,7,8，9，1０，1１，１2}4242132436126231）的Hasse圖2）的Ｈａss圖在3）的Hasse圖中可以看出，1191191263105718423）的Hasse圖素也為6;極小元素為2和３；上確界為６;下確界為1；沒(méi)有最小元素。②{2，4,6}的極大元素為4和６；最小素為２;極小元素也為２；上確界為12;下確界為２;③{4，8,12}的極大元素為８,1２;最小元素為４;極小元素也為4;下確界為4；沒(méi)有最大元素；沒(méi)有上確界。性質(zhì)集合最大元最小元極大元極小元上界下界上確界下確界｛２,3,6}6無(wú)62，36,1２1６1{２，4,6｝無(wú)24,6２12１,２122{4,8,12}無(wú)48,1２4無(wú)1,2,4無(wú)４3)3)的特殊元素表652134３４.對(duì)下面半序集合(A652134[解]A=｛0,1，2，３,4,5,6}第34題?={（0,0),（0,1)，（0,2），（0,3），（0，4),(0，5),(０，6),（１，1），(2,2)，（2,５），(3，3），(３,5)，（４,４),(4，6)，（5,５),（６,6)}第3４題第34題35．設(shè)Ｒ是集合X上的半序關(guān)系,AＸ,證明R∩(Ａ×A)是Ａ上的半序關(guān)系。［證］.證法一：令Ｒ1＝R∩（A×A），則R1A×A，所以R1是A上的關(guān)系，我們只需證明在A上Ｒ是自反的,反對(duì)稱的,傳遞的即可。（a)R1是自反的對(duì)任何a∈A,由于AX，所以a∈X,由于R在X上是自反的，故此(a，ａ）∈Ｒ；由于a∈A,顯然（a,ａ)∈Ａ×A；所以（a,a）∈R∩（A×Ａ）,即(a，a）R１。(ｂ)R1是反對(duì)稱的對(duì)任何(a,a)∈R1且（ｂ,ａ)∈R1，由R1＝R∩(A×A),故有（ａ，b）∈R且(b，a）∈R，以及a，b，ｃ∈Ａ。運(yùn)用R的傳遞性,可得(ａ，ｃ）∈R，運(yùn)用a,c∈A可得(a,ｃ)∈A×A，所以(ａ，c)∈R∩(A×A）,即（ａ，c）∈R1。證法二:令R1=R(ＡA)，由于R(AA)AA，所以R1AA,因此R１是A上的關(guān)系。①R1是自反的對(duì)任何a，ａA（a,a)R(a,a）ＡA(R是X上的自反關(guān)系及AX）(a,ａ)R（AA)(a,a）R1（R1的定義)所以,R1是自反的；②R１是反對(duì)稱的對(duì)任何a,bA(a,b)R1(b,a）R1（a,b)R(AA）(b,a）R（AＡ)(R1的定義)((ａ,b）R(a,b)AＡ)（(b，a)R（b，a）AA)(（a，b)R(ｂ,ａ)Ｒ)（(ａ,ｂ)AA(b,a）AA）(的結(jié)合律、互換律）((ａ,b)R(b，a)R)(基本邏輯蘊(yùn)涵式：ｐqp)ａ=b(R是反對(duì)稱的)所以,R1是反對(duì)稱的；③Ｒ1是傳遞的對(duì)任何a，b,cＡ(a,b)R1(b,ｃ)Ｒ1(ａ,ｂ）Ｒ(AA）(b,c）Ｒ（ＡA)(Ｒ１的定義）((ａ,b）Ｒ(a,b)AA)((ｂ,c)R（b，c)AA)（(a,b)Ｒ(b,ｃ)R)（(a，b)AＡ(b，ｃ）AA)(的結(jié)合律、互換律）(（ａ,c）R(a,c）AＡ（Ｒ是傳遞的，全關(guān)系ＡＡ是傳遞的）(ａ,c)R(AＡ)（a,ｃ）R1(R１的定義）所以，R1是傳遞的;綜合①、②、③,可知Ｒ1是A上的半序關(guān)系。３6．設(shè)(A，?1）和（A,?2）是兩個(gè)半序集合，定義Ａ×Ｂ上的關(guān)系?3如下：對(duì)于a1，a2∈A，，b2∈B（a１,ｂ１)，(a2,b2)∈?3(a1,a２)∈?1∧(b1，ｂ2）∈?2證明?3是Ａ×B上的半序關(guān)系。［證].證法一：對(duì)于任何(a，ｂ）∈A×Ｂ，就有a∈A及b∈Ｂ,從而運(yùn)用?１及的自反性,可得(a，a)∈?１且(b，ｂ）∈?2因此由?3的定義,可知(（ａ,b），(a，ｂ)）∈?3。（b)?3是反對(duì)稱的對(duì)任何（（a1，b1），（ａ2,ｂ2)）∈?3及（(ａ2,ｂ2),(ａ1，b1))∈，由?3的定義,可知（a１，a2）∈?1且(a2,a1)∈?1及(b１，b２）∈?2且（b2，b1）∈?2運(yùn)用?1及?2的反對(duì)稱性，可得a1=a2及b１＝b2,因此(ａ1,b1）=（ａ２,b２)。(c）?3是傳遞的對(duì)任何((a1,b１），（a2，b２))∈?3及（（a2,ｂ２)，(a3，b3）))∈?３，由?3的定義，可知（a1，a2）∈?1且（a2，ａ３）∈?1及(b1,b2）∈?2且（b２，b3）∈?2。運(yùn)用?1及?2的傳遞性,可得(ａ１，a3)∈?1及(ｂ1,b3)∈?２。再次運(yùn)用?3的定義，可得（（a1，ｂ1)，(ａ3,b3))）∈?3。證法二：①?3是自反的對(duì)任何(a，b),（a,b）AＢaAbＢ(a，a）?1(ｂ,b)?２(?1,?2都是自反的)（(a,b）,(ａ,b))?３（?３的定義)所以，?3是自反的；②?3是反對(duì)稱的對(duì)任何(ａ,b),(ｃ,d）AＢ((a，b),(c,d）)?3(（c,d）,（ａ,b））?3((a,c)?1（ｂ,d)?2）（(ｃ,ａ)?1(ｄ,b)?2)(?3的定義)(（a，ｃ)?1(c,a）?1)((b，d)?2(d,b)?2)(的結(jié)合律、互換律)a＝ｃb=d(?1，?2都是反對(duì)稱的)(a,b）=（c,d)所以，?3是反對(duì)稱的;③?３是傳遞的對(duì)任何（ａ,b),(c,ｄ),(e,f)AB((ａ,b),(c,d))?３((c,ｄ),(ｅ,ｆ))?3((a,c)?1（ｂ，d)?2)((ｃ,e)?１(d,f)?2)(?３的定義)(（a,c)?1(c,e)?1)（(b,d)?2(ｄ,ｆ)?2)(的結(jié)合律、互換律)（a,e)?1(b,f)?２(?1，?2都是反對(duì)稱的)((a,b),(ｅ,ｆ)）?3(?3的定義)所以,?3是傳遞的；綜合①、②、③,可知?3是AＢ上的半序關(guān)系。3７．對(duì)于非空集合Ａ，是否存在這樣的關(guān)系R，它即是等價(jià)關(guān)系又是半序關(guān)系？若有，請(qǐng)舉出例子。[解］有。只有一種，那就是Ａ上的幺關(guān)系IA,它即是等價(jià)關(guān)系,又是半序關(guān)系。證法一:否則,假如有a∈A及b∈A且ａ≠b，使得（a，ｂ）∈Ｒ,那么由R是對(duì)我的就將有(ｂ,a)∈Ｒ，再由R是反對(duì)稱的，就得到a