2023年离散数学习题解第一部分集合论部分

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系ﻬ离散数学习题解答习题一(第一章集合）１．列出下述集合的所有元素:１)A={ｘ|x∈Ｎ∧x是偶数∧ｘ＜15}２）B=｛x|x∈N∧４＋ｘ＝3}3）C=｛x|x是十进制的数字｝[解]1）A={2，4，6，８，10,12，14}2）B=3)C={0,１，2，3,4,5，6，7，8，9｝2.用谓词法表达下列集合：１){奇整数集合}2）{小于７的非负整数集合}3）｛3,5,7,１１，13,17,19，２3，29｝[解]１）{nnＩ(mI)(n＝2m+1）};2)｛ｎnIｎ０n<７};3)｛ppＮｐ>2p＜３0(dN)(d1dp（ｋN)(p＝kｄ）)}。３.拟定下列各命题的真假性:1)2）∈3){}4)∈{}5）｛a,ｂ}｛a，b,c，｛a，ｂ,ｃ}}6）{a,b}∈(ａ，ｂ,c,{a，b,c}）7){a，b}{a,ｂ,｛{a，ｂ，｝}}8){a，b}∈{a，b，{{a，b,}}}[解］１)真。由于空集是任意集合的子集;2）假。由于空集不含任何元素；3）真。由于空集是任意集合的子集;4）真。由于是集合{｝的元素；５)真。由于{ａ,b｝是集合{a，b，c,{ａ,b,ｃ}}的子集；6）假。由于{a,b}不是集合{a，b，ｃ，{a，b，ｃ｝}的元素;７)真。由于{a，b}是集合{a，ｂ，｛{a，b}}}的子集;8）假。由于{a,b}不是集合{a，b，｛{a，ｂ}｝}的元素。４.对任意集合A，B,Ｃ，拟定下列命题的真假性：1)假如A∈B∧Ｂ∈Ｃ，则A∈Ｃ。2)假如A∈B∧B∈C,则A∈C。３)假如AB∧B∈Ｃ,则A∈C。[解]1）假。例如A=｛a}，B＝{a，ｂ},C={{a},｛b}}，从而A∈B∧B∈C但A∈Ｃ。2)假。例如A=｛a}，B＝{a,{a}}，C=｛{a｝，｛{a}}｝,从而A∈Ｂ∧B∈C,但、Ａ∈C。３）假。例如A={a},B={ａ,b}，C=｛{a｝，a,b}，从而ACB∧B∈C,但A∈Ｃ。5．对任意集合A,B，Ｃ，拟定下列命题的真假性：1）假如A∈B∧BC,则A∈Ｃ。２)假如Ａ∈B∧ＢC,则AＣ。3）假如AB∧B∈C，则A∈C。３)假如AＢ∧B∈C，则ＡC。[解]1）真。由于BCx(x∈Bｘ∈C)，因此Ａ∈BＡ∈Ｃ。２)假。例如A=｛a｝，Ｂ={{ａ},｛b}｝，C=｛{ａ},{b}，{c｝}从而Ａ∈B∧BC,但AC。3）假。例如A=｛a},B=｛｛a，b}｝，C={｛a,{a,ｂ}},从而ＡB∧B∈C，但AC。4）假。例如Ａ={ａ}，Ｂ=｛{a,ｂ｝｝，C={｛a,b},b},从而AＢ∧B∈C，但AC。6．求下列集合的幂集:1){a，b，ｃ}２){a，｛ｂ,c}}3){｝4）{，｛｝}５）{{ａ，ｂ},{ａ，a，b},{ａ，b，a，b}}[解]1)｛,{a｝，{b}，{c}，{a，b}，{a,c}，｛ｂ,c},{ａ,b，c}}2）{，{ａ｝，{{ｂ,c}}，{a,{a，b}}}3）｛，{}｝4){，｛｝,{{}｝,{，{}}}５）{，{｛a，b}｝}7.给定自然数集合N的下列子集：A＝{１，2,7，８}B={x|x2<５0｝C＝{x|ｘ可以被3整除且0≤ｘ≤3０｝D={x|x=２K，K∈I∧O≤Ｋ≤6}列出下面集合的元素:Ａ∪Ｂ∪C∪DA∩B∩Ｃ∩DB\（A∪C)(Ａ′∩B)∪D[解]由于B={１，2，3，4，5，6,7｝,Ｃ={3，6，9,1２，1５，18,21,24,27,30｝,D={１，2，4,8,16,32,6４，}，故此1)Ａ∪Ｂ∪C∪D=｛1,2,3,4,5，6，7，8，９，12，１５,16,1８，2１,24，2７，30，32，６4｝2）A∩B∩C∩D=３）B＼(A∪C）={４，5｝4）(A′∩B)∪Ｄ={1,2,3,4,5,6,７，8,1６，３2，6４}8.设A、B、Ｃ是集合，证明:1）(Ａ\B）=A\(B\C)2）(A\B)\C＝(Ａ＼C)\(Ｂ＼Ｃ）3)(A＼B）\C=(A＼C)＼Ｂ[证明]1)方法一:（A\B)＼C=(A∩B′)∩C′(差集的定义）=A∩（B′∩C′）（交运算的结合律）=A∩（B∪Ｃ)′（deMorｇaｎ律)=A\（B∪C）（差集的定义)方法二:对任一元素x∈(A＼Ｂ）\C，则xC,同时，x∈A\B，ｘ∈A，xB，所以,x∈Ａ，xB∪C,即x∈A\(B∪C），由此可见（A\B）＼CA＼（Ｂ∪C）。反之，对任一元素x∈Ａ\(B∪Ｃ),则x∈Ａ，且ｘＢ∪C,也就是说xA,xＢ,xＣ。所以x∈(A\B)\C,由此可见A＼(Ｂ∪C）(A\B)\C。因此Ａ\(B＼C)。2)方法一:（A\B）\C＝A\（B∪Ｃ)（根据1))=A\（C∪B）（并运算互换律)＝A\（（C∪B)∩Ⅹ)(0—1律）＝A＼（(Ｃ∪B)∩（Ｃ∪C′）)(０—1律)=A\（Ｃ∪（B∩C′)（分派律)=（A\C）\(B∩C′)(根据1)=(A＼C）\（B∩C)（差集的定义）方法二:对任一元素x∈（A\B）＼C，可知x∈A,xＢ，xC,x∈Ａ\C。又由xＢ，xB\C,x∈(A\C）\(Ｂ\C)＼(Ｂ＼C）。所以（A\B）\Ｃ(Ａ\C）\(B\C)。反之,对任ｘ∈（A＼C）\(B＼C），可知x∈Ａ\C,ｘＢ\C。由ｘ∈A\C,可知x∈A,xＣ。又由于xB\C及xＣ，可知xB。所以,x∈（A\B）\C。因此（A\B)＼C（A＼B）\C。由此可得(A\B）\(B＼C）(Ａ＼Ｂ）\Ｃ。3）方法一：（A＼C）＼C=Ａ\（B∪C)(根据1))＝Ａ＼（C∪Ｂ)（并运算互换律)=(A\C)\Ｂ（根据1））方法二:对任一元素x∈(A\B)\Ｃ，可知x∈A，ｘB，xC。由为x∈A,xＣ,所以,x∈A\C。又由xB，ｘ∈（A\C）＼B。所以，(A＼B)＼C（A\C)\B。同理可证得（A\C）＼B(A\B)＼C。9．设A、B是Ⅹ全集的子集,证明:AＢA′∪B＝ＸＡ∩B′=[解］(采用循环证法）(1)先证ABＡ′∪B＝X；方法一：A′∪B=A′∪(Ａ∪Ｂ)(由于条件AＢ及定理４）=（A′∪A)∪Ｂ（∪的结合律）=(A∪Ａ′）∪B(∪的互换律)＝X∪B(互补律)=Ｘ（零壹律）方法二：ABA∪Ｂ＝B(定理4）B＝Ａ∪B（等号=的对称性）Ａ′∪B=A′∪（A∪B)（两边同时左并上Ａ′）Ａ′∪B==(A′∪A）∪B(∪的结合律）A′∪B=(Ａ∪A′)∪B(∪的互换律）A′∪Ｂ=X∪B（互补律)A′∪B=X(零壹律）方法三：由于A′X且BX，所以根据定理2的3）就有A′∪BＸ;另一方面,由于BA′∪B及根据换质位律可得B′A′A′∪B，因此,由互补律及再次应用定理２的3)，可得X=B∪B′A′∪B，即XA′∪B;所小学生早恋A∩B=A∩Ｃ，但B≠Ｃ。11.设A,Ｂ为集合,给出下列等式成立的充足必要条件：A\B=BA\Ｂ＝B\AA∩Ｂ=A∪BAB=A[解]1）A＼Ｂ=A∩B′，由假设可知A\B=B，即A∩B′＝B。由此可知B＝故此Ｂ=Ｂ∩B′=。由假设可知A=Ａ\=Ａ\Ｂ=Ｂ=。所以当Ａ\Ｂ＝B时有Ａ＝Ｂ＝。反之，当A＝B=时,显然A\B=B。因此A\Ｂ=B的充足必要条件是A＝B=。2)设Ａ＼B≠∈,则有元素ａ∈A\B，那么，a∈A，而由假设A＼B=B\A。所以ａ∈B＼A,从而aA，矛盾。所以Ａ\Ｂ=,故ＡB。另一方面由B\Ａ＝Ａ\B=。可得ＢA。因此当A\B=B\Ａ时,有Ａ=B。反之，当A＝B时,显然A\B=B＼A=因此，A＼Ｂ=Ｂ\Ａ的充要条件是A=Ｂ。3)由于A∪B=A∩B,从而AＡ∪B＝A∩BB,以及ＢA∪B=A∩BA故此A∪B=A∩B,有Ａ=B。根据定理6的1)有A=A，由已知条件AB=A，可得ＡＢ=A。从而由对称差的消去律可得B=。反之，若Ｂ=,则ＡB=A=A。所以AＢ=A的充足必要条件为B=。12.对下列集合,画出其文图:Ａ′∩Ｂ′A\(B∪C)′Ａ∩（B′∪Ｃ）[解]AABBCACBAXX13.用公式表达出下面图中的阴影部分[解]AACBx(A∪B∪C)∪(A∩B∩C)′BCAx(A∩C)\B14.试用成员表法证明1）(AB)C=A（BC）2)（A∪B)∩（Ｂ∪C）AＢ′[解］1）成员表如下ABＣAB(AＢ)ＣBCA（ＢＣ）00０0０000０１0１1１０1０１1110１１１０0０1001１01101１0１0１１0０0１０１１10１０１成员表中运算结果Ｃ及A(BC）的两列状态表白,全集中的每一个体对它俩有相同的从属关系,故(AＢ)Ｃ＝Ａ(ＢC）成员表如下:AＢCA∪B(B∪Ｃ）（B∪C）′（Ａ∪B）∩（B∪Ｃ)′B′Ａ∩B′０00０0１０１00０10100100１0１１0000０1１1１０００01００1０１111１０1１100１11１０1１0000１１111000０成员表中运算结果(A∪B）∩（B∪C)′及Ａ∩Ｂ′的两列状态表白，全集中的每一个体,凡是从属（A∪B）∩(B∪C)′的，都从属A∩Ｂ′,故(A∪Ｂ）∩(B∪Ｃ)′A∩B注：自然数集Ｎ取为{1，2,3，……，n，……}ﻬ习题二（第二章关系)1．设Ａ=｛1,２,3，},B=｛a，b}求1)A×B2)Ｂ×A3）B×B4）2Ｂ×B[解］１）A×B＝{(1，ａ）,（1,b)，（2,a)，（2,a）,(3，a）,(3，b)｝２）B×Ａ={（a，1),（a，2),（a，3）,（b,1),(b，2)，（ｂ,3)}3)Ｂ×B=｛（a,a),(ａ，b）,（b，ａ）,(b,ｂ)}4)2B=｛,{a}，{b｝,{a,ｂ｝}2B×B｛（,{ａ｝），(,b)，({a｝,a），（{a｝,b），（{b}，a),（｛ｂ｝,ｂ)，（｛a,b｝，b）}2.使AA×A成立的集合A存在吗？请阐明理由。[解]一般地说，使AA×A成立的集合Ａ不存在,除非Ａ=。否则A≠，则存在元素x∈Ａ×A,故有ｙ1，y2∈A,使ｘ=（ｙ1,y2），从而y1,y2∈A×A,故此有y1，y2,ｙ3，y４,使y1=(y1,y2）,y2=(y3，ｙ4），……。这说明A中每个元素x,其结构为元组的无穷次嵌套构成,这不也许。我们讨论的元素的结构必须是由元组的有限次嵌套构成。３．证明Ａ×Ｂ＝B×AA＝∨B=∨A=B[证]必要性：即证Ａ×B=Ｂ×AA＝∨B=∨Ａ＝B若A×B=，则Ａ＝或者B=若Ａ×B≠，则A≠且B≠,因此对任何x∈A及任何ｙ∈B就有（x,y）∈Ａ×B,根据A×Ｂ=B×A,可得(x,y)∈B×Ａ,故此可得x∈B,y∈A，因此而得AB且ＢＡ,所以由的反对称性A=Ｂ。充足性：即证A＝∨B=∨A=BA×B=Ｂ×Ａ这是显然的。4．证明(Ａ∩B)×(C∩Ｄ）=(A×C)∩（B×D)[证］证法一:(元素法)对任一(x,y）∈（A∩Ｂ）×(C∩D)有ｘ∈Ａ∩B,ｙ∈Ｃ∩D,于是ｘ∈Ａ,x∈B,ｙ∈Ｃ,y∈D。因而(x,ｙ）∈A×C，且(x,y)∈Ｂ×D,所以(x，y)∈（A×C)∩（B×D)。因而（A∩Ｂ）×（Ｃ∩D)（A×Ｃ）∩（Ｂ×D)另一方面，对任一（x，y）∈(A×C)∩(B×Ｄ），于是有（x,ｙ）∈A×C且（x,y）∈B×Ｄ，因而x∈A,y∈C,x∈By∈D。所以x∈A∩B,y∈（C∩D)。所以(x,y）∈(A∩B)×(Ｃ∩Ｄ)。因而（A×Ｃ）∩（Ｂ×D）（A∩B）×（C∩D)。综合这两个方面有(A∩B）×(C∩D)=(A×Ｃ)∩（Ｂ×D）。证法二:(逻辑法)对任何ｘ,y(ｘ,y)∈(A∩Ｂ）×(C∩D)x∈Ａ∩By∈C∩D(x∈Ax∈B)(y∈Cy∈D)(x∈Ａｙ∈C)（x∈By∈D)(的结合律、互换律)(x，y）∈Ａ×Ｃ（x，y）∈Ｂ×D（x,y）∈（A×C)∩(B×D)由x，y的任意性，可得:(A∩B)×(C∩D)=(A×Ｃ)∩(Ｂ×D）。5.下列各式中哪些成立，哪些不成立？对成立的式子给出证明，对不成立的式子给出反例。１)(Ａ∪B）×(Ｃ∪D)=（A×C)∪(B×D)2）（Ａ\B）×（C＼D）=（Ａ×Ｃ)\(B×D)３）（AB)×（ＣD)=(A×C）（B×D)4)(Ａ\Ｂ）×C=(A×C)\（Ｂ×Ｃ）5）(ＡB）×C=（Ａ×C）（B×C)[解]1)不成立。设Ａ={a},B={ｂ},Ｃ={c｝，Ｄ={ｄ},则(a,－d)∈（Ａ∪Ｂ)×(C∪D），但（a,-d）（A×C）∪（B×Ｄ）。所以（A∪B)×（C∪D)=（A×Ｃ）∪（B×D)不成立。事实上有：（Ａ×C)∪(B×D）（A∪B)×（C）(A∪B）×（C∪D）。2）不成立。设A={a}，B=｛b},C=D＝｛c},则(ａ，c）∈(Ａ×Ｃ)\(Ｂ×D)但（a,c)(A＼B)×(Ｃ\Ｄ）。因而(A\b)×（C\Ｄ)=（A×C)\(B×Ｄ)不成立。事实上有:（A\B）×（Ｃ＼D）(Ａ×C)\（B×Ｄ）。由于A\BA，C\D，故有(A×C)＼（Ｂ×Ｄ)Ａ×Ｃ；又若(x，y)∈（A＼B)×（C\D)故此x∈A\B，从而ｘB,y∈C＼D,从而yD,故此（x，y)B×D综合这两方面,有（A＼B）×(C\D)(Ａ×Ｃ)＼（B×D）。3)不成立。设A={ａ｝，B＝｛b}，C＝｛a}，D={b},则(a，b)∈(AB）×(CD），但（ａ，ｂ)（A×Ｃ）(B×D)。所以（AＢ）×（CD)（A×C）(Ｂ×Ｄ）不成立。又设A={a｝,B＝｛b｝,C=｛ａ},D={c}则(a,c)∈（Ａ×Ｃ）（Ｂ×D)，但（ａ，c)（AB）×（CD）。所以(A×Ｃ)(B×D）（AＢ)×（ＣＤ）不成立。因此(AＢ）×（CＤ)与（Ａ×C）(B×Ｄ)无任何包含关系。总之（AB)×(ＣＤ)=（A×Ｃ）（B×D)不成立。4)成立。证明如下:对任一（x，y)∈(A\B)×C，有ｘ∈A,xB，y∈C于是(ｘ，y)∈A×C,且（x，y）∈（Ａ\B）×C，且(x,y)B×Ｃ(否则x∈B），所以(x，y）∈(A×C）＼(B×C）。因而（A＼B)×C(A×C）＼(Ｂ×C)。又对任一(x，ｙ)∈（A×C)\（B×C)，有(x,y）∈A×C,且（ｘ,y）B×C从而x∈Ａ,y∈C及ｘB。即x∈A\Ｂ,y∈C，故此(x,ｙ）∈(A\B）×C。所以(A×C)＼(B×C)（A×B）×C。因而（A\B)×C=(A×C)\（B×C)。另一种证明方法:(A×B)×C=（Ａ∩B′)×C（差集的定义）=(A×C）∩（Ｂ′×Ｃ）（叉积对交运算的分派律)=（A×C)∩（B×C)′(因（Ｂ×C)′=(B′×C))∩(B×C′）∪(B′×C′）但（A×C）∩(B×C）′=(（Ａ×C)∩（B′×Ｃ)）∪=(A×C)∩（B′×C))=(A×Ｃ）∩(Ｂ′×C）(差集的定义)证法三：（逻辑法)对任何x，y（x,y)∈（Ａ×C）\(Ｂ×C）（x,ｙ)∈A×C(x，y）Ｂ×Ｃ(ｘ∈Ay∈C)(xByC）（x∈Ay∈CxＢ)(x∈Ａy∈ＣyC)(对的分派律）(x∈AｘＢy∈C)(ｘ∈Ａy∈CyC)(的结合律、互换律)(x∈AxＢ)ｙ∈Ｃ(及的零壹律、的结合律)x∈A\Ｂy∈Ｃ(ｘ，ｙ)∈(Ａ＼B)×Ｃ由x，y的任意性,可得：(Ａ＼B)×C=（A×C)\(B×C)。5)成立。证明如下:对任一(x，y）∈(AB)×C，故此x∈AB，ｙ∈C于是x∈A且xB，或者xA且x∈B。因此(x，y)∈（A×C)(B×C）。所以（AＢ)×C（A×Ｃ)（B×C）。对任一（x,y)∈(Ａ×Ｃ)(B×C)。则（x,y）∈A×Ｃ且(ｘ，y)B×C，或者（x,y）A×C且（x,y）Ｂ×C。因此x∈A，yＣ，ｘB，或者x∈B，y∈C,xA。所以ｘ∈A\B，或x∈B\Ａ，并且ｙ∈C，故此x∈AＢ，y∈C。因此(x,y)∈(AB)×C，即(A×C)（Ｂ×Ｃ）（AＢ)×Ｃ。综合两方面、就有(ＡB）×C＝(A×C)（B×C）另一种证明方法：（AB）×C=(（A\B）∪（B\A))×C（对称差的定义)=(（(A\B）×C）((B\A)×Ｃ)（叉积对并运算的分派律)=((Ａ×C）＼(Ｂ×C)∪（B×Ｃ）\（A×C)）(根据4））=（A×C）(B×C)(对称差的定义)6.设Ａ=｛1，2，3}，B＝{a},求出所有由A到B的关系。[解]：R0=，Ｒ1={(1，a）}，R２={(2,ａ）}，Ｒ3=｛（3,a）｝,R4={(1，a），（２,a)},Ｒｓ={（1,ａ），(3，ａ)｝,R6=｛（2,ａ），（３,a）}，R7={（1,a),(2，a），（3,a)}7.设Ａ={1,2，３，4},R1={(1,3)，（2，2）,(3,4)},R２＝｛（１，４),(2，3），（3,4)}，求：R1∪R2，Ｒ１∩Ｒ２,R１\Ｒ２，Ｒ1′,Ɗ（R1），Ɗ（R2），ℛ（R1），ℛ(Ｒ2),Ɗ（R1∪R2),ℛ（R１∩R2）[解］：Ｒ1∪R2={（1,3）,(1，4),（2,2)，（２，3），（3,4)}R1∩R２=｛(3，4)｝R1\R２={(１,３），(2，2)}R1′=(A×A)＼R={（１,1），(1,2），（1，4）,(2，1），(2，３）,(2,4)，(3,1），(3,2)，(3，3）,（４,1）,（４，2），（4,3)，(４,4）｝(R１)={1,2,3}，ℛ(R1）={2，3，４},（Ｒ2）={1，2，3}，ℛ(R2）=｛3,4｝(Ｒ1∪Ｒ２)={１,2，3｝,ℛ（R１∩Ｒ２）=｛4｝8.对任意集合A及上的关系R1和R2，证明1）ℛ（Ｒ1∪Ｒ２）=ℛ(R１)∪ℛ(Ｒ2）2）ℛ(Ｒ1∩R2)⊆ℛ(R１）∩ℛ（R2)[证]1）一方面，由于R１⊆R1∪Ｒ２,R2⊆Ｒ1∪R2，根据定理1,有ℛ（Ｒ１)⊆ℛ（Ｒ１∪R2)，ℛ(R2）⊆ℛ（Ｒ1∪R2)故ℛ(R1）∪ℛ（R２)⊆ℛ(R1∪R2）另一方面，若x∈ℛ(R１∪R２）那么存在着ｙ∈A,使(y，x)∈(Ｒ1∪R2）因此(y，x）∈R１,或者（y,x）∈R2，从而ｘ∈ℛ（Ｒ１)或者ｘ∈ℛ(R２)于是ｘ∈ℛ（R1)∪ℛ（R2)，所以ℛ(R1∪R2)⊆ℛ(R1)∪ℛ（R2）。9.设Ａ有ｎ个元素的有限集合,请指出A上有多少个二元关系?并阐明理由。［解]A上有2n２个元关系。由于叉积A×A有n2个元素，因而A×Ａ有2ｎ2个子集,而每个子集都是A上的一个二元关系。10.定义在整数集合I上的相等关系、“≤”关系、“＜”关系，全域关系，空关系,是否具有表中所指的性质，请用Y（有)或N(元）将结果填在表中。性质关系自反的反自反的对称的反对称的传递的相等关系YＮYYY≤关系YNNＹＹ<关系ＮYＮＹY全域关系YＮYNY空关系ＮYYＹY1１.设Ａ=｛1，２,3,4},定义A上的下列关系R1=｛（1,1）,（１，2)，（３，３)，(3,4）}，R2={（1，２)，(2,1)}R３={(１,1）,(1,2），（2,2),(2,1）,（３,3），（3，4)，(4，3）,（４,４）}R４={（１,2）,(２,４)，(3,3），(4,1)}R5={(1，2）,(1,3),（1,4),(2,3）,（2，４)，（3,4）}R６=A×Ａ，Ｒ7=请给出上述每一个关系的关系图与关系矩陈,并指出它具有的性质。[解］：1002300410023004Ｒ1是反对称的,传递的。2）Ｒ2是反自反的，对称的。3)R3是自反的,对称的,传递的,因此是等价关系。循环的综合这两方面,就有(R1∪R2）=ℛ(R1）∪ℛ(R2)。2）由于R１∩R2⊆R１,Ｒ1∩R2⊆Ｒ2，根据定理１,有ℛ（R1∩R２）⊆ℛ（Ｒ1），ℛ(R1∩R２）⊆R2,所以ℛ（R1∩R2)⊆ℛ（R1）∩ℛ(R2)反方向的包含不成立,反全由第７题可得,那里ℛ(R1∩Ｒ2）＝｛４｝，ℛ（R1）∩ℛ(R2）={2，3，4}∩{3，4}={3,４}因此ℛ（Ｒ1)∩⊈ℛ（R2）⊈(R1∩R2）４）R４是反对称的，循环的。５)R５是反自反的，反对称的,传递的。６)R6是自反的，对称的,传递的,循环的。从而是等价关系。7)R7是反自反的对称的，传递的，循环的，反传递的，反对称的。R7是反自反的对称的，传递的，循环的，反传递的，反对称的。12．设A是A上的关系,证明1)R是自反的当且反当IＡ⊆Ｒ2）R是反自反的当且仅当IA∩Ｒ=3）R是对称的当且反当R＝R是反对称的当且仅当R∩⊆IA５)Ｒ是传递的当且仅当RＲ⊆Ｒ[证]１)必要性若R是自反的,则对任何x∈A,都有（x,x）∈R,但是IＡ={（ｘ,x）|x∈Ａ｝,所以IＡ⊆Ｒ。充足性若ＩA⊆A则由IA={（x,x）|x∈Ａ}，可知对任何ｘ∈A，都有（x,x)∈Ｒ,所以Ｒ是自反的。2）必要性若Ｒ是反自反的,则对任何ｘ∈A，都是（ｘ,x)R，从而(ｘ，ｘ）∈R′,由IA={（x,x)｜x∈Ａ｝可知ＩA⊆R′。于是IA∩R⊆R′∩R=,此外⊆IA∩R,所以ＩA∩R＝。充足性若ＩA∩Ｒ=,则Ｒ是反自反的。否则,不是反自反的,那么应存在某一ｘ０∈Ａ,使得（x0,x０）∈Ｒ。但是（x0，x0)∈IＡ，从而(x0，x０)。这不也许，矛盾。3）必要性，若Ｒ是对称的,则对任何(x,ｙ）∈R,就有（ｙ,x)∈R。于是根据逆关系的定义,可得(x，ｙ)∈,于是Ｒ⊆;对任何（ｘ,y)∈，由逆关系的定义，可得（y,ｘ）∈R。再次运用R的对称性有(y，x)∈R，于是⊆Ｒ;综合两方面，有R＝。充足性若Ｒ=,则对任何(x，ｙ）∈R，由R=可得（x，y）∈。从而由逆关系的定义，可知(y，ｘ)∈R这说明R是对称的。4）必要性若R是反对称的，则对任何(ｘ，y）∈，即有(ｘ,y）∈R及(ｘ，y)∈，从逆关系的定义,就有(ｘ,ｙ）∈R及(y,ｘ)∈Ｒ，因此,运用R的反对称性，可得x=ｙ。于是就有(x，y）=（x，x)∈IA，所以Ｒ∩⊆IA。充足性若R∩⊆IA，则对任何（ｘ,y)∈Ｒ及(y,x）∈R，从逆关系的定义，可得（x,ｙ)∈R及(ｘ,y)∈,也即（x,y）∈R∩，运用R∩=IA可得(x,y）∈IA，于是x=y。所以R是反对称的。5）必要性若R是传递的,则对任何(x，ｙ)ＲоＲ，由复合关系的定义可知，存在着y∈A,使(ｘ,ｙ)∈Ｒ且(y,ｙ)∈Ｒ，从而运用Ｒ的传递性,可知（x，y）∈R。所以RоR⊆R。充足性ＲоR。从而运用RоR⊆R可得（x,ｙ）∈R。所以R是传递的。证法二:1)):对任何x，x∈Ａ(x,x）∈ＩA(IA是幺关系,因此是自反关系)(ｘ,x)∈Ｒ(R是自反关系)所以IAR;)：对任何x∈A,x∈A(x,x)∈IＡ(ＩＡ是幺关系，因此是自反关系）（x,ｘ）∈R（因IAR)所以，R是自反关系;2))一方面ＩAR；另一方面，对任何x，y∈A,若（ｘ，y)∈IＡR(ｘ,y)∈IＡ(x,y)∈Ｒx＝y(x，y)∈R(IA是幺关系，因此是自反关系）（ｘ,x)∈Ｒ则与R是反自反关系，(ｘ，x)Ｒ矛盾。故IAＲ;因此，由包含关系的反对称性,可得IAR=;):对任何x∈A,若（x,x)∈R（x,x)∈IA(x,x)∈R(IA是幺关系，因此是自反关系)（x,ｘ）∈IAR(x,x)∈（因IAR＝)则与空集不含任何元素,(ｘ,x）矛盾。故对任何x∈A，（x,x)R；所以,R是反自反关系；3）)对任何x,ｙ∈A(x,ｙ）∈Ｒ（y,x）∈R(R是对称关系)(ｘ,y)∈所以，R=；):对任何x，ｙ∈A(x,ｙ)∈Ｒ(x,ｙ)∈(R=)(y,ｘ)∈R所以,R是对称的；4)）对任何ｘ,ｙ∈A(x，y)∈R(x,y)∈R(x,y）∈(x,ｙ)∈Ｒ(ｙ，x)∈Rx=y(R是反对称关系)（x,y)∈IA(IＡ是自反关系)所以，ＲＩA;):对任何x,y∈A（x，y)∈Ｒ(x,y）∈（R=）（y,ｘ)∈Ｒ所以,R是对称的;1３．设Ａ、B为有穷集合，R，S⊆A×B,MＲ=(ｘij）ｍ×n,MS=(yｉj）m×n1）为了Ｒ⊆Ｓ，必须且只须ｉj（xij≤yij)2)设MR∪S=(Zij）m×ｎ，那么Zij＝ｘijVyij，I＝１，2……，m，j=1,2,……ｎ.３)设MR∩S=(ｔiｊ）ｍ×n,那么ｔiｊ＝xｉj^yijｉ=1，２,……ｍ；j=1,2,……,n.[证］由于A、B是有穷集合，不妨设A=｛ａ1，a２……,am}，B=｛b1,b２,……,bn}１)必要性若R⊆S，则对任何ｉ∈｛1,２,……，m}，对任何ｊ∈｛1，2，……n}，若（ai,bj）∈R，则R的关系矩阵MＲ=(ｘｉj）m×n中第I行第j列元素ｘij＝1，根据R⊆Ｓ,可得（ai,bj)∈S,从而得Ｓ的关系矩阵MS=(yｉj）m×n中第I行第j列元素yｉj=1,由于是1≤１故此xij≤ｙij；若（aｉ,bj）R,则R的关系矩阵MR=(xｉｊ）m×ｎ中第i行第j列元素ｘiｊ＝0，因此由Ｓ的关系矩阵MＳ=（yｉｊ）m×n中第ｊ列元素yij≥0，可得xij≤yij。总之,有(i）(j)(xｉｊ≤yij)。2）充足性若(ｉ)(ｊ)（xij≤yｉｊ)，则对任何(ai，bj）∈Ｒ,就有R的关系矩阵MR=（ｘij)m×n中第ｉ行第ｊ列元素ｘiｊ=1,由于xij≤yij,所以yij≥1,故此yｉj≥1这说明S的关系矩阵ＭS=(yij）ｍ×n中第i行第j列元素yij为1，因此必有（ai,bj)∈Ｓ,所以R⊆S。2）对任何i∈｛1，2,……,m},对任何j∈{1,2，……，n}若Zｉj=1,则(ａi,bj)∈R∪Ｓ,故此（ａi，bj)∈Ｒ或者（ai,bj）∈S，于是ｘij＝1或者ｙij=1。从而bj)∉S,于是xiｊ=０且yiｊ=0。从而xiｊ∨yij＝0。因而Zij=xij∨ｙij=0;综合上述两种情况,就有zji=xiｊ∨yij，ｉ=1，2，……,m,j=1，２，……n，。3)对任何i∈｛1,2，……m}，对任何j∈{１，2,……，ｎ}。若tiｊ=1,则(ａi，ｂｊ)∈R∩Ｓ,故此（aｉ，bj)∈S且(ａｉ，bj）∈S，于是xｉｊ=１，且yij=1从而xiｊ∧ｙij＝1。因而tij=xij∧ｙiｊ＝1;若ｔij＝0，则(ａi,bj)∉R∩S,故此(ai，bj)∉Ｓ，于是xij＝0或者yij＝0,从而xij∧yiｊ=０。因而tｉj=xiｊ∧yiｊ=0。综合上述两种情况,就有tiｊ＝xｉj∧yiｊ,i=１，2,……,m,j=１,2，……,ｎ。14．设A=｛1,2,3，４},Ｒ1，R２为A上的关系，Ｒ1＝{（１,1）,(１，２)，(２，4）},R２＝｛(１，４），(2，3）,(2，4),(3,2）｝,求R1оR2,Ｒ２оＲ1,R1оR2оR１[解］,1)无论从复合关系图还是从复合关系矩阵都可得R1оR2={（1，3），（1，4）}无论从复合关系图还是从复合关系矩阵都可得R1оR2={（1，3），（1，4）}R1R２2）无论从复合关系图还是从复合关系矩阵都可得R2оR1无论从复合关系图还是从复合关系矩阵都可得R2оR1={（3，4）}R2R13)无论从复合关系图还是从复合关系矩阵都可得R1оR2无论从复合关系图还是从复合关系矩阵都可得R1оR2оR1=4)无论从复合关系图还是从复合关系矩阵都可得R1оR1о={（1，1），（1，2），无论从复合关系图还是从复合关系矩阵都可得R1оR1о={（1，1），（1，2），（1，4）}R1R1R115)设R１，R2，Ｒ3是Ａ上的二元关系，假如R１⊆R２，证明1)R1R3⊆R2R32）R3R1⊆R３Ｒ2[证明]1)对任何（x,y）∈Ｒ1R３，由复合关系之定义,必存在z∈Ａ,使得(x，z)∈R1且（z,ｙ)∈Ｒ3,运用R1⊆R２可知(ｘ,z)∈R2且（ｚ，y）∈Ｒ3,再次运用复合关系之定义，有（ｘ,y）∈R2Ｒ３。所以Ｒ1Ｒ3⊆R2R3。2)对任何(x,y）∈R3R1,由复合关系之定义,必有ｚ∈Ａ，使得（x,z)∈R3且(z，y）∈R1,再由复合关系之定义，有（x，ｙ）∈Ｒ3R2。所以Ｒ３R1⊆R3R2。1６．设A是有限个元素的集合，在A上拟定两个不同的关系R1和R２，使得=R1，=R2ﻩ ﻩ由于,令Ｒ１＝，则R1R１=,故此=Ｒ1＝。令R２=A×A，则=R2R２⊆A×A=Ｒ2,故需证明Ｒ２⊆R2οR２＝。为此,对任何x，y∈A,（ｘ，y)∈A×A＝R2,一定存在着z∈A(至少有z=x或z=ｙ存在),使（x，z）∈A×Ａ＝R2且(z，y)∈A×A=R2，故此（x，ｙ)Ｒ2Ｒ2＝，所以R2⊆R2R2=。于是=R２＝Ａ×A。2）由于A是有限个元素的集合,是不心设A=｛a1,a２，……an}令R1=｛(aｉ,aj）｜ai∈Ａ∧ａj∈A∧|≤ｉ≤n∧|≤ｊ≤n-｜}R2＝{(aｎ,an)∪R１}则Ｒ1R２，即Ｒ1与Ｒ1是不同的关系。我们来证明=R１,＝Ｒ２,(a)先征＝Ｒ1若（ai，aｊ）∈R1，则由Ｒ1的定义必然１≤i≤n,1≤i≤ｎ-1,并且一定存在着1≤ｋ≤ｎ-１（至少有k＝ｊ存在),使（ai,ak）∈Ｒ1且(ak,aj)∈Ｒ１,从而(ａi，aj)∈Ｒ1R1＝。故此R1⊆。若（ai,aｊ)∈=Ｒ1R１，则存在着ｋ，1≤ｋ≤n-1,使（ai，ak）∈R1且（ａｋ，aj）∈R1,于是由R1的定义,必有１≤ｉ≤n，1≤ｊ≤n－1,从而根据R1的定义，有（ａi，ａj)∈R1。故此=Ｒ1综合两个方面,可得=R1。（b）次证＝R２若(ａi,aj)∈R2,则由R２的定义,要么1≤ｉ≤ｎ,1≤ｊ≤ｎ－1,要么Ｉ＝n，j=ｎ若1≤i≤n,1≤j≤n-1,则一定存在着1≤k≤n-１(至少有ｋ=j存在），使（aｉ,ak)∈Ｒ２且(aｋ,aj）∈R2，从而(ai，aj)∈Ｒ２οR2=;若ｉ=n，ｊ=n，则(ai,aｊ）=(an,ａｎ)∈R2,那么（ａn,an）∈Ｒ２,所以（ai，aj）=（aｎ,ａn)∈R2οR２=因此R2=。若(ai,ａj）∈=R2οR2，则存在着ｋ，使(ai,ak)∈Ｒ2且(ak,ai）∈R２,于是由Ｒ２的定义，有k=n或者1≤k≤n-1。若k=n，则由（ai,ak)∈Ｒ2必有I=ｎ,所以无论１≤j≤ｎ-1还是ｊ=n,由R2的定义，有（ai,aj)=(ａｎ，aj）∈R2；若1≤k≤n－1，则由（ai，ａk)∈Ｒ2必有１≤j≤n－１故此(aｉ，aj)∈Ｒ2总之证得=R２,综合两方面,我们证明了=R2。17.设Ｒ是集合A上的反对称关系，｜A｜＝h,指了在R∩的关系矩阵中有多少个非零值？[解]由第12题的4）Ｒ是反对称关系当且反当R∩⊆ＩA，及|Ａ｜=n可知,在R∩的关系矩阵中非零值最多不超过n个。１８．设R1和R2是集合A上的关系，判断下列命题的真假性，并阐明理由。假如R1和Ｒ2都是自反的，那么Ｒ１R2是自反的。假如R1和R２都是反自反的,那未R1R２是反自反的。假如R1和R２都是对称的，那末R1R2是对称的。假如R1和R2都是反对称的，那末R1R２是反对称的。假如Ｒ1和R2都是传递的，那末R１R2是传递的。[解]１)真。由于R1和Ｒ2和R２都是自反的，因而对任何，都有（x，x)∈R１,（x，x）∈R2。因此,对任何ｘ∈A,都有（ｘ,x)∈R1R2。所以R１R2是自反的。２)假。令A={a，ｂ}，R1=｛(ａ,b)｝,Ｒ２={ｂ,a｝。那么Ｒ1Ｒ2={（ａ,ａ）}，它就不是Ａ上的反自反关系。３)假。令A=｛a,b，c｝,R１={（a，b)，（ｂ，a）},R2={（ｂ，c），（c,b)}。那末R1R２＝{（a，c)｝,就不是A的对称关系。4)假。令A＝{a，b，c,d},R1＝{(ａ，c）,(b，c)}Ｒ2＝｛(c,b），（ｄ,a）}易证R1，R2都是反对称关系。但是Ｒ1R2={(a，b）,(b,a）}就不是A上的反对称关系。5）假。令Ａ={a,ｂ,c},R１={(a,c),（b，a)，(b,c）},R2={（c，b）,（ａ,c),(a，b)}，易证R1和R2都是传递关系,但R1R2={（a，b),(b,b），（b,c)}就不是A上的传递关系。1９．设A={1，2，3,4,5},R⊆A×Ａ，R={（1，2）,(２，3),(2，５），(3,4),（4，3),（5，5）}用作图方法矩阵运算的方法求r（R）,ｓ（Ｒ）,t(Ｒ)。[解]1)作图法：R的关系图(Ｒ）的关系图55123412345515143253241Ｓ（R）的关系图t（R）的关系图因此：r（Ｒ)={（1，1），(1，2），(2,２),(2，3）,(2,5），(３,3），（3,４),(4，3),(4，4），(5,５）}s(R)={(１,2）,(２，1）,(2，3)，(2,５）,（3,２),（３,4)，(4，3）,(5，2），(５，５)}t（R）={(1，2）,(1，3）,（1，4）,(1,5),(2，3），（２，4），（2,5），(３,3),（３，４）,（4,3),（4,４)，（5，5）}2）矩阵运算法：Ｍr(Ｒ）=＝MＳ(Ｒ)====ＭRοR=MRＭR=＝=MR=因此r(R)，s(R），t（R）与1)作图法一致。20.设Ｒ⊆A×A，证明1)（R＋)+＋R+2）=R*[证明]1）一方面,由于（R＋)+是R+的传递闭包，所以R+⊆(Ｒ+)+；另一方面,由于R＋是R的传递闭包，故此R+是传递的。由于R+⊆Ｒ+及传递闭包（Ｒ+）+是包含R+的最小传递关系，就有（R＋）＋⊆R+(定理4之３)；所以（R＋)+=Ｒ+。２)一方面，由于（R*）*是R*的自反传递闭包，所以R＊⊆（Ｒ*)*；另一方面,由于R*是R的自反传递闭包，故此R*是自反的传递的。由于R*⊆R*及自反传递闭包(Ｒ＊)*是包含R*的最小自批传递关系,就有(Ｒ*）*⊆R*(定理5的3))。所以(R*)＊＝R*。2１．设A={１，2，３,4},ＲAA,R＝{(1，２）,（2,4)，(3,4)，(4，３)，（3，3）｝１)证明R不是传递的；2)求R1，使 R1⊇R并且R1是传递的；3）是否存在Ｒ2,使Ｒ２⊇R，R２≠Ｒ1并且Ｒ2是传递的。[解]1）由于(1,２)∈R且(2,4）Ｒ但(1,4)∉R，这说明R不是传递的。2)由于Ｒ+是包含R的最小传递关系，所以，取Ｒ1=R+即为所求。现在来R＋R2={(1,４）,(2,3),(3，3),(3,4)，}（4,3)，（4,4）｝R3={（1,3），(2，3）,(2，4)，(3,3），（３,4）,(４,3），（４，4)}R4＝{（1,3)，（１,4），（2,3）,(２，4),（3，3)，（3，4),(４,3)，(４，4）}故此Ｒ１=Ｒ＋=R∪R２∪R3∪R4={（1,2),(１，3),(1，4)，(２,3)，（2，４），(３,3）,（3,4),(4，3）(４，4)}(由于|Ａ|=４有限）其关系图如下：11124311243R的关系图Ｒ1的关系图3)能。由于Ｒ1并非全关系（否则，当R1是全关系时，就找不到了)，所以只要取R2=A×A是A上的全关系就可满足Ｒ2⊇R，R2≠Ｒ，并且全关系R2显然是一个传递关系。22.设A={1，２,3，4……,9},定义A×A上的关系如下：（a,b)Ｒ(c,d)∷a＋d=b＋ｃ证明R是Ａ×A上的等价关系;求［(2,5）］Ｒ；R⊆A×Ａ对吗？请阐明理由。1)[证明]（a）R是自反的对于任何(ａ，b)∈A×A,由于ａ+b=b＋a,所以(a，ｂ）R(a,b）。（b）R是对称的对于任何(ａ，b),(c,d）∈A×A，若(a,b）Ｒ（c，d），则有ａ+ｄ＝b+c从而c+b+a,所以可得（c，d)R（a,b）。(c）R是传递的对于任何（a，ｂ),（ｃ，d），(e，f）∈Ａ×Ａ，若（a,b)R(c,d),且（c,d)Ｒ（e，f），于是有ａ+d＝b+c及ｃ+f=ｄ+e，二式相加有a+f+ｃ+d=ｂ＋e+c+d,两边同时减c+d,可得a+f＝b+e，从而可得(a,b）R（ｅ,f)。综合（a）、(b)、（c)、说明Ｒ是A×A上的等价关系。２）［解]由于{(２,５）}Ｒ={(a，b）｜(a，ｂ)∈A×A(ａ,b）Ｒ（2,5）｝＝{（a,b)|(a，b）∈A×A∧a+5=b+2}=｛(a，ｂ）｜（ａ，b)∈A×A∧ｂ=a+3}=｛(１，4),（2,５，（3,６）,（4,７),（5,8)，(6，9))3)［答]R⊆A×A不对。由于Ｒ是Ａ×A上的关系,所以R⊆（A×A)×(A×A）＝。23．设A是一个非空集合，Ｒ⊆A×A。假如R在A上是对称的,传递的，下面的推导说明R在A上是自反的:对任意的a,b∈A，由于R是对称的,有：ａＲｂbＲa于是aRbaRb∧ｂRa,又运用R是传递的,得：aRb∧ｂRaaRa从而说明R是自反的。上述推导对的吗？请阐明理由。［答]上述推导不正解。推殖民地的谬论误在于假设A的每个元素都由R关联着A的某一别的元素。假如这不是真的，那么对称性的条件的假设就始终是假的,因此结论当然是假的。因而在一个空集上的空关系都是平凡的对称和可传递，但不是自反的。此外关系{（a，a）,(ｂ，b），（a,ｂ),(ｂ,a）}是自反的和传递的,但在集合｛ａ,b,c｝上不是自反的。2４．设Ｒ是集合Ａ上的等价关系,证明也是集合A上的等价关系。[证明]证法一:(a）是自反的对任意的a∈A，由于R是自反的,所以(a,ａ）∈R,再由逆关系的定义有（a，ａ）∈(b）是对称的对任何（a，b)∈由逆关系的定义,有(b,a）∈R，由R的对称性，可得(a，ｂ)∈R，再由逆关系的定义，就有(b，ａ）∈。（c)是传递的对任何(a，ｂ)∈及（b,ｃ）∈,由逆关系的定义，有（b,ａ)∈R及（c,b)∈Ｒ，根据R的传递性，可得（c,ａ）∈R，再次由逆关系的定义，就有(a,c）∈。综合（a）（b)(c)可知是等价关系。证法二:(a）是自反的:对任何a,ａA（a,a）R(R都是自反的）(a，a）所以，是自反的；(ｂ）是对称的:对任何a，bＡ，(a,b）(b，ａ)R(a,ｂ）Ｒ(R是对称的)(ｂ，ａ)所以，是对称的;（c)是传递的:对任何ａ，b，ｃＡ,(a,b)(ｂ,c)((b，a）R(c，b）R((c,b)Ｒ（b,a)R(的互换律）(c,a)R（R是传递的)(a,c)(R是对称的)所以，是对称的；综合(a)、(ｂ)、(ｃ）,可知是Ａ上的等价关系。25.设R1和Ｒ2都是集合A上的等价关系1）证明R1∩R2也是A上的等价关系;2)用例于证明Ｒ1∪R2不一定是A上的等价关系(要尽也许小地选取集合A）。[证]1)证法一：（a)Ｒ1∩R２是自反的对任何a∈A，由于R1,R2都是A上的自反关系,所以(a，a）∈R1（a,a)∈R２,因此（a，ａ）∈Ｒ1∩R2（b)R1∩R2是对称的对任何的(a,b）∈Ｒ1∩Ｒ2，就有（ａ,b）∈R1且（a,b）∈R2,由R1,R２都是A上的对称关系,所以（ａ，ｂ）∈Ｒ１且(b,a)∈R2，所以（ｂ,a)∈Ｒ１∩R2。(c）Ｒ1∩Ｒ２是传递的对任何的（ａ,b）∈R1∩Ｒ2及（b,c)∈R1∩R2，就有(ａ，b）∈R1,（ａ,ｂ）∈R2及(b,c）∈R1,（ｂ,c)∈R2,于是(a,b）∈Ｒ1且（b,ｃ）∈R１及（a,b)∈Ｒ２且(b,ｃ）∈R2由于R1，R２都是Ａ上的传递关系,所以（a,ｃ)∈Ｒ1及(a,c)∈R２，因此(a，c）∈Ｒ1∩R2。综合（ａ)，(b），（c）,可知R1∩Ｒ２是等价关系。证法二：（ａ)Ｒ1∩R2是自反的：对任何a，aA(a,a）R1(ａ,a）Ｒ２(R1，R2都是自反的)(ａ,a)R1Ｒ２所以，R１Ｒ2是自反的；（ｂ）R１∩R2是对称的：对任何a,bA，(a，b)R1R2(ａ,b）R１(a，b）R2(b,a)R1(b,a)R2(R1,R2都是对称的）(b,ａ)Ｒ1R2所以，R1R2是对称的；（c)Ｒ1∩R２是传递的：对任何a，ｂ,cA，(a，b）R1R２（b,c)R1R2((ａ,b)R1(a,b)R2）（(b,c)R1(b,c)R２)（(a,ｂ)R1(b，c)Ｒ１)(（ａ,ｂ)Ｒ2(b，c)R2)(的结合律、互换律）(a,c）R1(a,c)Ｒ2(R1,R2都是传递的)(a,c)R1Ｒ2所以，Ｒ1R２是对称的;综合(ａ）、（ｂ)、(c)，可知R1R2是A上的等价关系。２)两个自反的（对称的)关系的并将是自反的（对称的）,但是，两个传递关系的并却未必是传递的。我们就从破坏传递性出发来构造反例：令R1={（a,a），(b,b),（c，c),（a，b）,（b，ａ)}R2＝{(a,ａ),（b，b）,（ｃ，c）,(b，ｃ），（c，b)}当A={a,ｂ,c}时，R1,Ｒ２显然都是等价关系。但是abcabcabcＲ1∪R2={(a，a）,（b,ｂ），（ｃ，c)，(a,ｂ),(b，a)(b，c)，(c，b)}都不是A上的等价关系,由于R1∪R2不传递：（a,b)∈R1∪R2且(ｂｃ,但（a,c）∉R1∪R２；同样(c,ｂ）∈R１∪R2且（b,ａ)∈R1∪R2,但（c,aabcabcabcR1关系图R２关系图R1∪R2关系图并且|Ａ|不也许再少了。由于任何少于3个元素的集合上的自反，对称关系一定是传递的！２6.设R是A上的等价关系，将A的元素按R的等价类顺序排列,请指出此等价关系R的关系矩阵ＭR有何特性？［解]将A的元素按其上的等价关系Ｒ的等价类顺序排列，这样产生的等价关系Ｒ的关系矩阵MＲ，通过适当的矩阵分块，MＲ的分块矩阵将成为准对角阵，准对角阵的对角线上的每一块都是一个全１方阵，它正好相应于等价关系R的一个等价块。27.设A是n个元素的有限集合，请回答下列问题，并阐明理由。有多少个元素在A上的最大的等价关系中?A上的最大的等价关系的秩是多少?有多少个元素在Ａ上的最小的等价关系中？Ａ上的最小的等价关系的秩是多少?[答]1)A上最大的等价关系是全关系Ｒ1=A×A={（a,ｂ)｜a∈Ａ∧b∈A}因此有ｎ２个元素在A上的最大的等价关系R1中,由于所有n2个二元组都在Ｒ１=A×A中。2）Ａ上的最大的等价关系Ｒ1的秩是1。这是由于A中任何两个元素都有全关系R1=Ａ×A，因此R1的等价块包含了A的所有元素，Ａ的所有元素都在同一个等价块中。3）A上的最小的等价关系是么关系R２=IA={(ａ,a）a∈A｝因此它中有n个元素,即ｎ自反对。4)Ａ上的最小的等价关系的秩是ｎ,由于么关系的每一个元素都自成一个等价块,每一等价块中也只有一个元素。２8．设Ｒ1和R2是非容集合Ａ上的等价关系，对下列各种情况,指出哪些是A上的等价关系；若不是,用例子说明。1)A×A\Ｒ12）R1\R23）4)r(R1\Ｒ２)(R1\R２的自反闭包）5）R1R2[解]1)不是。设A＝{ａ},并且Ｒ1={(a,a）},则R１是A上的等价关系,但A×A\R1={（a,a)\(ａ，a)}=就不是A上的等价关系,由于空关系不是自反的。2)不是。设Ａ={(a，b)}并且R1=｛(ａ,ａ），(b，b)，(a，b),（b，a）}，Ｒ２＝{（a,a),（ｂ，b）},则R1，R2都是Ａ上的等价关系，但是,R１＼R2={(a，b），（ｂ，ａ)｝就不是A上的等价关系，由于R1\R2不自反。3)是。证法一：因R1是等价关系,因而R1是传递的,故此由第１2题之5)有＝R1R１⊆R1。另一方面，结任何(a,b）∈R1，由于R1是自反的，故此（b,b）∈R1,从而由复合关系之定义,有(a,b)∈Ｒ1R１，所以R１⊆，从而=R1，因此由Ｒ1是等价关系，知也是等价关系。证法二：一方面，对任何a，ｂA,（a，b)(ｃＡ）（(ａ,c）R1(ｃ,ｂ)R１)(cＡ）((a,b）R1）(R1是传递的)(a,b)R1(带量词的基本逻辑等价式:(ｘ)pp)所以，Ｒ1；另一方面,对任何a,bA，(a,ｂ)R1（ａ,b）R1(b,ｂ)R1)(Ｒ1是自反的)(a,b)所以，R1;综合这两方面,就有＝R1；４)是。设A={a,ｂ,ｃ｝，Ｒ1={（a,a），(b,b），(c，c),(a，b）,(b，a)，(a，ｃ)(c,a)，（b，c),（ｃ,b)｝。R１={（a，a),（b，b)(c，c)（a，a)(c,a）}，则R1，R２都是A上的等价关系。R１\R2=｛（a，b)，（b,a），（ｂ,c），(c,ｂ)}ｒ（R1＼R2)={(ａ,a)，（b，b)，(c,c),(a,b),（b,a）,（ｂ，ｃ），（c，b)}因此r（Ｒ1\R2）不是A上的等价关系，由于ｒ（R1\Ｒ2)不是传递的,（a，b)∈ｒ(Ｒ1\R2）且（ｂ,ｃ)∈ｒ(Ｒ１\R２),但是（a，c)∉ｒ(R1\Ｒ2)。５)不是。令Ａ＝{ａ,b,ｃ}，R1＝{(a,a)，（b,b），(c，c）,(a,ｂ）,(b,a）},R2={（ａ,ａ)，（b,b），（c，c）,(ａ，b）,(b，a），（b,ｃ），(c,ｂ)，(ａ，c)}不上的等价关系，由于R1R２不对称,（a,c)∈Ｒ1R２，但（c,ａ）∉R1Ｒ２。29．设A={1,2，３，４},请指出A上所有等价关系是多少？并阐明理由。[解]Ａ上的等价关系共有1４个。根据A上的划分与A上的等价关系一一相应的原理,我们只需求出Ａ上有多少个划分就行了。{｛a｝，{b},｛c},{d｝｝型划分,一个;{{a,b｝，{ｃ},｛d}｝型划分，六个;｛{ａ，b，}，{ｃ，ｄ}}型划分，三个;{{a，ｂ,c}，{d}}型划分,四个;｛｛ａ,b，c,d}}型划分，一个。总计:１+６+3+4+１=15。30.设A={1，2,3，4，5,6},拟定Ａ上的等价关系R,使此R能产生划分{｛1，２,3,｝，{4},{5，6}｝123123564R的关系图31．设R是集合A上的关系R是循环∷＝(a∈A)(ｂ∈A)(c∈A）(aRｂ∧bＲcｃRa)证明:Ｒ是自反的和循环的，当且仅当R是等价关系。［证]证法一:必要性若Ｒ是自反的和循环的,我们来证R是等价关系，为此证明(a）R是自反的。必要性条件所给。(b)R是对称的对任何(a，b)∈R，由于R是自反的，所以(b，ｂ）∈Ｒ,再根据R是循环的可得(b，ａ）∈R。(c)Ｒ是传递的对任何（a,b)∈R，(b,c）∈Ｒ,由于R是循环的,所以（c，a)∈R，运用R是对称的,就得到(ａ,c)∈R。充足性若R是等价关系,我们来证R是自反的和循环的。1）Ｒ是自反的。因R是等价关系,故R是自反的。2）Ｒ是循环的对任何（a,b)∈R，(b，ｃ)∈R,由于R是传递的，所以（a,ｃ）∈Ｒ。由于R是对称的，(c，ａ）∈Ｒ。证法二：)：（ａ）R是自反的:已知;（b）R是对称的：对任何a,bA，（ａ,b)R(a，ｂ)R(b,b)R（R是自反的)(ｂ,a)Ｒ（R是循环的)所以,R是对称的;(ｃ）R是传递的：对任何a,ｂ，cA，(a，b)R(b,c)R(ｃ，a）Ｒ(R是循环的）(a,c)R(R是对称的)所以，Ｒ是传递的；综合（ａ）,(b）,（c)可知R是等价关系;):(a）R是自反的：由于Ｒ是等价关系,所以R是自反的;（b)R是循环的：对任何a,b，cＡ，(ａ,b）R(b,c)R（ａ,c)Ｒ(R是传递的）(c,ａ）R（R是对称的)所以,R是循环的;32.设∏1和∏2是非空集合A的划分,说明下面各种情况哪些是Ａ的划分？哪些不是A的划分？哪些也许是Ａ的划分？并阐明理由。１)∏1∪∏２2)∏1∩∏23）∏1\∏２4）(∏１∩（∏2\∏1）)∪∏1[解]1）也许。假如∏1=∏2,则∏1∪∏2是A的划分；假如，∏1≠∏2，则∏1∪∏2不是A的划分；例如A={ａ，b},∏１={{a},{b}｝，∏2＝{{ａ,ｂ}｝，但∏１∪∏2={{a},{ｂ},｛a,ｂ}}就不是A的划分,由于{a}∩{a,b}={ａ}≠,就不是A的划分,由于｛a}∩{a,b｝={a}≠。2)也许。假如∏1=∏2,则∏1∩∏2是A的划分；假如,∏1≠∏２,则∏1∩∏２不是Ａ的划分；例如A=｛a，b}，∏1＝{{a}，{b｝}，∏2={{a，b}},∏1∩∏2=,就不是Ａ的划分。３）也许。假如∏1∩∏２=，则∏１\∏2=∏１是A的划分;假如∏1∩∏2≠,则∏１\∏2不是A的划分；例如A=｛a，ｂ，c},∏1＝{{a},{b},{c}}，∏2={{a｝，{ｂ,c｝},∏1∩∏2={{ａ｝}因此∏１\∏2={｛b},{ｃ}}就不是A的划分。由于{b}∪{c}={b，c}≠Ａ。4)是。由于（∏1∩(∏2\∏1））∪∏1=∪∏1＝∏1,是A的划分。33．对下列集合上的整除关系画出哈斯图,并对３)中的子集{2，3,6}，{２，４，6}，｛４，8,1２｝找出最大元素，最小元素,极大元素，极小元素,上确界,下确界。1){1，２,３,４}2）{2，３,6，１2，24，３6}３){１，2，3,４,5,6,7,8,9,10,11，１2}424213243612623１)的Hassｅ图２）的Hasｓ图在3)的Hasｓe图中可以看出，119121191263105718423）的Hasse图素也为６；极汴元素为2和3；上确界为6;下确界为１；没有最小元素。②｛2，４，６｝的极大元素为4和6；最小素为2；极小元素也为2;上确界为１2;下确界为2；③{4,8，12｝的极大元素为8,12;最小元素为4；极小元素也为４；下确界为４;没有最大元素;没有上确界。性质集合最大元最小元极大元极小元上界下界上确界下确界｛2，３,６}6无62,36,12161{2,4,6｝无24,62121,2１22｛4，8,１2｝无48,12４无1,2,4无４3)3)的特殊元素表65213434．对下面半序集合（A652134［解]Ａ={0，１,2,3，4,5，6}第34题≼＝｛(０,０),(0，1),（0,２），（0，3)，(0,4)，(0,5）,(０，６)，(1，1），92，２0，(２，5），（３,3),(3,5),(4,4），（４，6）,(５,5）,(６,6)｝第34题第34题35.设Ｒ是集合X上的半序关系,ＡＸ,证明R∩(Ａ×A）是A上的半序关系。[证].证法一:令R1=Ｒ∩(A×A),则R１A×A,所以R1是A上的关系,我们只需证明在A上R是自反的，反对称的，传递的即可。(a）Ｒ1是自反的对任何a∈A,由于AX,所以a∈X,由于Ｒ在X上是自反的，故此（a，ａ）∈R；由于ａ∈A,显然(a，a）∈A×Ａ；所以（a,ａ)∈R∩(A×Ａ)，即（a,a）R1。(ｂ)Ｒ1是反对称的对任何（a,ａ)∈R1且（b，a）∈R1,由Ｒ1=R∩(A×Ａ）,故有（a，b)∈Ｒ且（b，a)∈R，以及a，b,c∈Ａ。运用R的传递性，可得(a,c)∈R，运用ａ,c∈A可得（a，c)∈A×A,所以(a，c)∈Ｒ∩(A×A），即(a，c)∈R1。证法二:令R1＝R(ＡA)，由于R（AＡ)AＡ，所以R1AA，因此R1是Ａ上的关系。①Ｒ1是自反的对任何a,ａA(a,a）Ｒ（a,a)ＡA(R是X上的自反关系及ＡX)(a,a)R（AA)(ａ，a)R１(R1的定义)所以，R１是自反的；②Ｒ１是反对称的对任何ａ,bA(a,b)R1（b,a)R1（a,ｂ）Ｒ(AＡ）(b,a)R(AA）(R1的定义)((a，ｂ)R(a,ｂ）ＡＡ)（(b,ａ）R(ｂ，a)AA)(（a，b)R(b,a）R）（(a,b)ＡA(b,a）AＡ)(的结合律、互换律）(（ａ,b)Ｒ（b，ａ)Ｒ)（基本逻辑蕴涵式：pqp）a=b(R是反对称的)所以,R1是反对称的；③Ｒ1是传递的对任何a,b,cA(a,b）R1(b,ｃ)Ｒ１(a,ｂ)R（AA）(ｂ,c)R(AA）(R１的定义)((a,b)R(ａ,b)ＡA)((b,c)R（b,c)AA）(（a,b)R（b,c）R)((a,ｂ)ＡA(b,c)AA)（的结合律、互换律)((a,c)R(a，c)ＡA(R是传递的，全关系AA是传递的)(a,c)R(AA)(a,c)R１(R１的定义)所以，R1是传递的；综合①、②、③，可知R1是A上的半序关系。36．设(Ａ,≼1)和(A，≼2）是两个半序集合，定义Ａ×Ｂ上的关系≼3如下:对于a１,a2∈A,，b2∈Ｂ（a１,ｂ１），(ａ2,b2）∈≼３(a１,a2)∈≼1∧（b1,b2)∈≼２证明≼３是A×Ｂ上的半序关系。[证].证法一：对于任何（ａ,b)∈A×B,就有a∈A及ｂ∈B，从而运用≼１及的自反性，可得(a,a）∈≼１且（b，b）∈≼2因此由≼3的定义,可知(（a,b),(a,ｂ))∈≼３。(b）≼3是反对称的对任何（(a１,b1)，(a２,b2）)∈≼３及((ａ2,ｂ2),（ａ1,b1））∈,由≼3的定义,可知（a1,a2)∈≼1且（ａ2，a1）∈≼１及（b1，b2）∈≼2且（ｂ2，ｂ1)∈≼2运用≼１及≼2的反对称性,可得a1=ａ2及b1=ｂ2,因此（a1，b1)＝(a2，ｂ２）。（ｃ）≼3是传递的对任何（(a1，b1),（ａ2，b2）)∈≼３及（(a2，b２),(ａ3，b3))）∈≼3，由≼3的定义，可知(a１,a2)∈≼1且(ａ2，a3）∈≼1及(b1，b２)∈≼２且(b2，ｂ3）∈≼2。运用≼１及≼2的传递性,可得(a1，a３）∈≼１及(b１,b３）∈≼２。再次运用≼３的定义，可得（（ａ１,b1),（ａ3,b3）)）∈≼3。证法二：①≼3是自反的对任何（a,b),(a,b）ABaＡbB(a,a）≼1(b,ｂ)≼2(≼１,≼２都是自反的)（(ａ,ｂ），(a,ｂ))≼３(≼3的定义)所以,≼3是自反的；②≼３是反对称的对任何(a,b),(ｃ,d)AB(（ａ，ｂ),(c,d)）≼3((c,d),(ａ，b))≼3（(a,c)≼1(b,d)≼2)((ｃ,a)≼1(d,b)≼２)(≼３的定义)((a,c)≼１(c,ａ)≼1)((b,d)≼2(d,b）≼2)(的结合律、互换律)a=cb=d(≼1，≼2都是反对称的)(a,b)＝(c，d)所以,≼3是反对称的;③≼３是传递的对任何(a,b）,(c,d），(ｅ,ｆ)AB((a,b),(c,ｄ))≼3（（c,ｄ）,(e，f))≼3((a，ｃ)≼１(b,d)≼2)((c,e）≼１(d,f)≼2)(≼3的定义）(（a,c)≼１(c,e)≼1)（(b,ｄ)≼2（ｄ,f)≼２）(的结合律、互换律)(ａ，e)≼1(b,f)≼２（≼1，≼2都是反对称的）((a,b）,(e，f))≼3(≼３的定义）所以，≼3是传递的;综合①、②、③,可知≼3是AB上的半序关系。３7．对于非空集合Ａ，是否存在这样的关系R,它即是等价关系又是半序关系？若有,请举出例子。[解]有。只有一种,那就是A上的幺关系IA,它即是等价关系,又是半序关系。证法一:否则,假如有a∈Ａ及b∈A且a≠b，使得（a，b)∈R，那么由R是对我的就将有（ｂ，a）∈R,再由Ｒ是反对称的,就得到ａ=ｂ，矛盾。这个矛盾说明同时为等价关系和半序关系的Ｒ只能是幺关系IＡ。证法二:设R即是一等价关系,又是一半序关系。则一方面,对任何元素ａ,bÎA，(a，b)R(a,ｂ)R(b，a)R(R的对称性)a=b(R的反对称性)(a,b)IA所以，RＩA;另一方面，对任何元素aÎＡ,(a,ａ）IA（a,b）R(R的自反性)所以,ＩAR；综合这两方面,有R＝IＡ。3８．对于下列每一种情况，举出有限集合和无限集合的例子各一个。非空半序集合,其中某些子集没有最大元素;非空半序集合,其中有一子集存在最大下界，但没有最小元素；非空序集合,其中有一子集存在上界,但没有最小上界。1）的（a）的Hasse图{a，b，c}{a1）的（a）的Hasse图{a，b，c}{a，c}{a，b}{b,c}{c}{b}{a}B1=｛{c}，{a,b}}Ｂ２={{b}，{a,c}}等均没有最大元素;(b)半序集（N,≤)的子集B1={x|x＝2n∧n∈N}B2＝｛P｜Ｐ∈N∧Ｐ为素数｝等均没有最大元素；２）(a）令=｛1，2,3,4，9,1４,15}4149231152）（a）的Hasse4149231152）（a）的Hasse图则(A,1)为半序集合，其中子集B＝{4,9，１４，1５}有最大下界１,但没有界小元素。(ｂ)半序集（Ｒ，≤）的子集B=(0,1）＝｛x|x∈R∧o＜ｘ≤1}有最大下界0,但没有最小元素。30423123）的（a）的Hasse图3)（a30423123）的（a）的Hasse图B={2,3}有上界30，42，但没有最小上界。半序集(Q,≤）的子集Ｂ={ｘ|x∈Q∧０＜x=有上界2,等，但无界小上界(若有最小上界,必为，但Q)。３9．指出下面的集合中,哪些是半序集合,线序集合或良序集合？１）(2N，）２)(2{ａ},)3)(2，)[解]结果如下表半序集合线性序集合良序集合(２N,）ＹＮN（2{ａ}，）YYY(2,)YＹY其中:Y—yｅs;Ｎ