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

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

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