2023年离散数学西安交大版习题解第一部分集合论部分

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系ﻬ离散数学习题解答习题一(第一章集合)１.列出下述集合的所有元素:１）A={x｜x∈Ｎ∧x是偶数∧x＜15｝２)B＝{x|x∈N∧4+x=３}3）C={ｘ|ｘ是十进制的数字｝[解]1)A={2,4，6，８,１0，12,1４}２)B=3)C={0,1，2，3，４,5,6，７，8，9}2.用谓词法表达下列集合：1){奇整数集合}2){小于7的非负整数集合}3）｛3，5，7，11,13，17,19,23,２9}［解]1)｛nｎI（mI）（ｎ=2m+1)｝;2)｛ｎｎIn0ｎ<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},{b},{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},{b},{c｝，{a,ｂ},{a,ｃ｝,{b,c},｛a，ｂ，c｝}2)｛,{a｝，{{b，ｃ}｝,{ａ,{a，b}}}3)｛，{}}4）{，{｝,{{}｝，{,{}}}5){，｛{a,ｂ}}｝7．给定自然数集合Ｎ的下列子集:Ａ={１,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.设Ａ、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′）(交运算的结合律）=A∩（B∪C)′(dｅＭorgan律)=A\（Ｂ∪Ｃ)(差集的定义）方法二：对任一元素x∈(A＼Ｂ）＼C,则xC,同时,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)(根据1)）=A＼（Ｃ∪Ｂ)（并运算互换律）=A＼（（Ｃ∪B)∩Ⅹ）(０—1律)=A\（（Ｃ∪B）∩（Ｃ∪C′）)(０—１律）=Ａ＼（C∪(B∩C′）（分派律)=（Ａ\Ｃ）\(Ｂ∩C′)（根据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\（Ｂ∪Ｃ）(根据1)）=A\(Ｃ∪Ｂ）(并运算互换律）=（A＼Ｃ)\Ｂ（根据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.设A、Ｂ是Ⅹ全集的子集,证明:ＡBA′∪B=XA∩B′＝[解](采用循环证法）（1)先证ABA′∪Ｂ=Ｘ；方法一：A′∪B=A′∪(A∪Ｂ)（由于条件ＡB及定理４）=(Ａ′∪A)∪Ｂ(∪的结合律)=(A∪A′)∪Ｂ(∪的互换律）=X∪B（互补律）=X（零壹律）方法二:ABA∪B=B（定理4)Ｂ＝Ａ∪B(等号=的对称性）A′∪B＝A′∪（A∪Ｂ）（两边同时左并上Ａ′)A′∪B=＝(A′∪A)∪B（∪的结合律)A′∪B=(A∪Ａ′）∪B（∪的互换律）A′∪B=X∪B（互补律）A′∪B=X（零壹律）方法三:由于A′X且BX,所以根据定理2的３）就有Ａ′∪BＸ；另一方面,由于BA′∪B及根据换质位律可得B′A′A′∪B，因此,由互补律及再次应用定理2的3），可得X=B∪B′A′∪B，即ＸA′∪B；所以,A′∪B=X。(2)次证A′∪Ｂ=XＡ∩Ｂ′=；A′∪Ｂ=X(A′∪B)′＝X′（两边同时取补运算′）(A′)′∩B′=X′(ｄeMorgan律）A∩B′=X′（反身律）A∩B′=X′（零壹律)(3)再证Ａ∩B′＝AB;方法一：A=A∩X(零壹律）=A∩（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(零壹律)AB（定理4的２））1０.对于任意集合Ａ,B，C，下列各式是否成立,为什么?A∪B=A∪CB=CA∩Ｂ＝A∩CB=Ｃ［解]1）不一定。例如：Ａ={a},B={a，b｝，Ｃ={b}。显然有Ａ∪Ｂ＝A∪C,但Ｂ≠C。2)不一定。例如：A={a}，B={a,b},C={b,c}。显然有A∩B=Ａ∩C，但Ｂ≠C。１1.设A，B为集合,给出下列等式成立的充足必要条件：A＼B=ＢA＼B=B\AA∩B=Ａ∪BAＢ=Ａ[解］１）Ａ\Ｂ＝A∩B′,由假设可知A＼Ｂ=B，即A∩B′=Ｂ。由此可知Ｂ＝故此B=B∩Ｂ′=。由假设可知A=A\＝Ａ\B=B=。所以当A\B＝B时有A=Ｂ=。反之，当A=B=时,显然Ａ\Ｂ=B。因此A\Ｂ=B的充足必要条件是A=B=。2)设A\B≠∈，则有元素a∈A＼Ｂ，那么，a∈A，而由假设A＼B=Ｂ\A。所以a∈B\A，从而aA,矛盾。所以A\B=，故ＡB。另一方面由B＼Ａ=A\B=。可得ＢA。因此当A\B=B＼A时，有A=B。反之,当Ａ=B时，显然A\B=B＼A=因此,A＼B=B\A的充要条件是A=Ｂ。３）由于A∪B=A∩Ｂ,从而AA∪B=A∩BB，以及ＢＡ∪Ｂ＝A∩BA故此A∪B=A∩B,有A＝Ｂ。根据定理6的1）有A=A,由已知条件AB＝Ａ，可得AＢ＝Ａ。从而由对称差的消去律可得Ｂ=。反之,若B＝,则ＡB=A=Ａ。所以ＡＢ=A的充足必要条件为Ｂ＝。1２.对下列集合,画出其文图:A′∩B′A\（B∪C)′A∩（B′∪Ｃ）[解］AABBCACBAXX1３．用公式表达出下面图中的阴影部分[解]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０１０１成员表中运算结果Ｃ及Ａ(BC）的两列状态表白,全集中的每一个体对它俩有相同的从属关系，故（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成员表中运算结果(A∪B)∩(B∪C）′及A∩B′的两列状态表白,全集中的每一个体,凡是从属（A∪B)∩（B∪Ｃ)′的，都从属A∩B′,故(A∪B)∩（Ｂ∪C）′A∩B注:自然数集Ｎ取为{１,2，３,……,n,……}

习题二(第二章关系)１.设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中每个元素x，其结构为元组的无穷次嵌套构成，这不也许。我们讨论的元素的结构必须是由元组的有限次嵌套构成。３.证明A×B=B×AA=∨B=∨A=Ｂ［证]必要性：即证A×Ｂ=B×AA=∨B=∨A=B若A×B＝,则A＝或者Ｂ＝若A×Ｂ≠,则A≠且B≠，因此对任何ｘ∈A及任何y∈B就有（x,y)∈Ａ×B，根据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)。综合这两个方面有(Ａ∩Ｂ)×(C∩D)=（A×Ｃ）∩(B×Ｄ)。证法二：（逻辑法）对任何x,y(x,y)∈(A∩B)×(C∩Ｄ)ｘ∈A∩Ｂy∈C∩D(ｘ∈Ax∈Ｂ）(y∈Ｃy∈D)(ｘ∈Aｙ∈C)(x∈By∈D)(的结合律、互换律)（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）不成立。设A={ａ},B＝｛b}，C={c｝,D={d}，则(a，-ｄ)∈（Ａ∪B）×（C∪Ｄ)，但（a，－d)(A×C)∪（B×D)。所以(A∪B)×（C∪D)=（A×C)∪(B×D)不成立。事实上有：(Ａ×C)∪(Ｂ×Ｄ)(A∪B)×（C)（A∪B)×（Ｃ∪D)。2)不成立。设Ａ=｛a},B＝{b｝，C=D={c},则（ａ，c）∈（A×C)\(B×D）但（a,c）（Ａ\B)×（C\D)。因而（A\b）×（C\D)=(Ａ×C）\（Ｂ×Ｄ）不成立。事实上有:(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）不成立。设A=｛ａ}，B={ｂ},C={ａ｝，D＝{b},则（a,b)∈(AＢ）×(CD)，但(a，ｂ)(A×C）(B×D）。所以(ＡB)×（CD）（Ａ×Ｃ）(B×D）不成立。又设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)无任何包含关系。总之（AB）×(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)(叉积对交运算的分派律）=(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)（的结合律、互换律)(x∈ＡxＢ)y∈C(及的零壹律、的结合律)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）（（Ｂ\Ａ）×Ｃ）（叉积对并运算的分派律）=(（A×C）＼（B×Ｃ）∪（B×C)\（A×Ｃ）)(根据4）)=(Ａ×Ｃ）（Ｂ×Ｃ）（对称差的定义）6.设Ａ={1，2，3}，B={a}，求出所有由A到B的关系。[解］: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．设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及上的关系R1和R２，证明1）ℛ(R1∪R2）=ℛ（R1）∪ℛ(R2）2）ℛ（R１∩R2)⊆ℛ(R1)∩ℛ(R2)[证]1)一方面,由于Ｒ1⊆R1∪R2，R２⊆R1∪R２，根据定理１，有ℛ（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１.设A={1,2,3,4｝,定义A上的下列关系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=请给出上述每一个关系的关系图与关系矩陈,并指出它具有的性质。[解]：1002300410023004R1是反对称的,传递的。2)R２是反自反的,对称的。3)R3是自反的,对称的，传递的，因此是等价关系。循环的综合这两方面，就有(R1∪Ｒ２)=ℛ（R1）∪ℛ(R2)。2）由于R1∩R２⊆R1,R1∩R2⊆R2，根据定理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.设Ａ有n个元素的有限集合,请指出A上有多少个二元关系?并阐明理由。[解]A上有２ｎ2个元关系。由于叉积A×A有n２个元素,因而A×A有２ｎ2个子集，而每个子集都是A上的一个二元关系。10．定义在整数集合I上的相等关系、“≤”关系、“<”关系，全域关系，空关系，是否具有表中所指的性质，请用Y(有）或Ｎ(元）将结果填在表中。性质关系自反的反自反的对称的反对称的传递的相等关系YNYYY≤关系ＹＮNＹY<关系NＹＮYＹ全域关系ＹNYＮY空关系NYYYＹ4)R4是反对称的,循环的。5）Ｒ5是反自反的,反对称的，传递的。６）R6是自反的,对称的,传递的,循环的。从而是等价关系。７）R7是反自反的对称的，传递的，循环的，反传递的，反对称的。R7是反自反的对称的，传递的，循环的，反传递的，反对称的。12．设Ａ是Ａ上的关系,证明1)R是自反的当且反当IA⊆Ｒ2）R是反自反的当且仅当IＡ∩R＝3）R是对称的当且反当Ｒ=R是反对称的当且仅当Ｒ∩⊆IＡ5)R是传递的当且仅当ＲＲ⊆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是反自反的。否则，不是反自反的,那么应存在某一x０∈A,使得(ｘ0，x0）∈R。但是(x０，ｘ0）∈ＩA，从而（x0,x０)。这不也许,矛盾。３)必要性,若R是对称的，则对任何（x，y)∈R,就有（y,x)∈R。于是根据逆关系的定义,可得（x,y）∈，于是Ｒ⊆；对任何(x,y）∈,由逆关系的定义,可得(y，x)∈R。再次运用R的对称性有（y，ｘ)∈R，于是⊆R;综合两方面，有R＝。充足性若R=，则对任何(ｘ,y)∈Ｒ，由Ｒ=可得（ｘ，y)∈。从而由逆关系的定义，可知（ｙ，x）∈R这说明R是对称的。4）必要性若R是反对称的，则对任何(x,ｙ）∈，即有(x,y)∈R及(x，y）∈,从逆关系的定义,就有（ｘ，y）∈R及（y，x)∈R，因此,运用Ｒ的反对称性,可得ｘ=y。于是就有(x,y）=（x，x)∈ＩA,所以Ｒ∩⊆IA。充足性若R∩⊆IA，则对任何（x,y)∈R及(ｙ，x）∈R，从逆关系的定义，可得（ｘ,y）∈Ｒ及（x,ｙ）∈，也即（x，y）∈R∩,运用R∩=IA可得(ｘ，y）∈ＩA,于是ｘ=y。所以R是反对称的。5)必要性若Ｒ是传递的，则对任何(x，y）RоR，由复合关系的定义可知，存在着y∈A，使(x，ｙ）∈Ｒ且(y,y）∈R,从而运用R的传递性,可知(ｘ，y）∈Ｒ。所以RоR⊆R。充足性RоR。从而运用RоＲ⊆R可得(x，y)∈R。所以R是传递的。证法二：１)）:对任何ｘ,x∈A(x,x)∈IA(ＩA是幺关系,因此是自反关系)（x,x)∈Ｒ（R是自反关系)所以IAR；):对任何x∈Ａ,ｘ∈Ａ（x,x)∈ＩA(ＩA是幺关系,因此是自反关系)（x,ｘ)∈Ｒ(因IAＲ)所以,Ｒ是自反关系;２）)一方面IAR;另一方面，对任何ｘ，ｙ∈A，若（x,y）∈IＡR(x,y)∈IA（x,y)∈Rx＝y(x，y)∈Ｒ(IＡ是幺关系,因此是自反关系)（ｘ,x)∈R则与R是反自反关系，(ｘ,x)Ｒ矛盾。故IAR；因此，由包含关系的反对称性,可得IAＲ=；）：对任何x∈A，若(x,x）∈Ｒ(x，x）∈IA（x,x)∈R(IA是幺关系,因此是自反关系)（ｘ，x)∈IAR(ｘ,x)∈（因ＩAR=)则与空集不含任何元素，（x,x)矛盾。故对任何ｘ∈A，(x，x)Ｒ；所以，R是反自反关系；3)）对任何x，y∈Ａ（x,ｙ)∈R(y,ｘ)∈Ｒ（Ｒ是对称关系)(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(R是反对称关系)（x,y)∈IA(IA是自反关系)所以，ＲIＡ；):对任何ｘ,y∈Ａ（x,y）∈R(x,y）∈(R=）（y,x）∈R所以,R是对称的；13.设A、B为有穷集合，Ｒ,Ｓ⊆A×B,MR=(ｘiｊ）m×n,MS＝(yij)m×n1）为了R⊆S，必须且只须ｉj(xiｊ≤yij)2)设MＲ∪Ｓ=(Zij)m×n，那么Zij＝xｉjVyiｊ，I=１,2……，m，ｊ＝1，２，……n．3)设MR∩Ｓ＝（tij)ｍ×ｎ，那么tｉj=xｉj^yｉji＝1,2，……ｍ；j=1，2,……，n.[证］由于A、B是有穷集合，不妨设A={a1，a2……,am｝，B={ｂ１，b2,……,bｎ}1)必要性若Ｒ⊆S,则对任何i∈{1,2，……，m}，对任何j∈{１，2，……ｎ}，若(ａi，bj)∈R，则R的关系矩阵MＲ=(xij）m×ｎ中第I行第ｊ列元素xij=1，根据R⊆Ｓ，可得(aｉ,ｂj）∈S,从而得S的关系矩阵MS=(yij)m×n中第Ｉ行第j列元素yiｊ＝1,由于是1≤1故此ｘｉj≤yij;若（ai,bj）R，则Ｒ的关系矩阵MR=(xｉj)ｍ×ｎ中第i行第ｊ列元素xｉj=0,因此由S的关系矩阵MS=(yij)m×ｎ中第j列元素yiｊ≥0,可得ｘij≤yｉj。总之,有（i）（j）（xij≤yiｊ）。2）充足性若(ｉ)(ｊ)（xij≤ｙij），则对任何(aｉ，bj）∈R，就有R的关系矩阵ＭＲ=(xｉｊ）m×n中第ｉ行第ｊ列元素xij=１,由于xｉｊ≤yiｊ，所以yij≥１,故此yij≥1这说明Ｓ的关系矩阵ＭＳ＝（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．设A={１,2,3，4},R１，R２为A上的关系，R1={(１，1），（１，2),(2，4)},R2＝{（1，4）,(2,3)，（2，4），(3，２）},求R１оR2，Ｒ2оR1，R1оＲ２оR1［解］，1)无论从复合关系图还是从复合关系矩阵都可得R1оR2={（1，3），（1，4）}无论从复合关系图还是从复合关系矩阵都可得R1оR2={（1，3），（1，4）}R1R22）无论从复合关系图还是从复合关系矩阵都可得R2оR1无论从复合关系图还是从复合关系矩阵都可得R2оR1={（3，4）}Ｒ2Ｒ13）无论从复合关系图还是从复合关系矩阵都可得R1оR2无论从复合关系图还是从复合关系矩阵都可得R1оR2оR1=４）无论从复合关系图还是从复合关系矩阵都可得R1оR1о={（1，1），（1，2），无论从复合关系图还是从复合关系矩阵都可得R1оR1о={（1，1），（1，2），（1，4）}R1R1R115)设R1，R2，R3是A上的二元关系,假如Ｒ1⊆R２，证明1）Ｒ1Ｒ3⊆R２R32)R3R1⊆R3R2[证明]1）对任何(ｘ,y)∈R1Ｒ３,由复合关系之定义，必存在z∈A，使得（x,z)∈R１且（ｚ，y)∈R3，运用R1⊆R2可知（ｘ,z）∈Ｒ2且(z，y)∈R３，再次运用复合关系之定义，有(x,y）∈Ｒ２R3。所以Ｒ1R３⊆R2R3。２）对任何(x,y）∈Ｒ3R１,由复合关系之定义,必有z∈A，使得（x,z）∈Ｒ3且(z,y)∈Ｒ1,再由复合关系之定义,有（x,y）∈R3Ｒ2。所以R3R１⊆R3R2。１6．设Ａ是有限个元素的集合,在Ａ上拟定两个不同的关系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是有限个元素的集合，是不心设A＝{a1，a2,……an｝令R１={（ai，aj)|aｉ∈A∧aｊ∈A∧|≤i≤ｎ∧|≤j≤n-｜}R2={（an,an）∪R１}则Ｒ１R２,即Ｒ１与Ｒ１是不同的关系。我们来证明＝R１,=Ｒ2,（a）先征＝R１若（ai,aｊ)∈R1,则由R1的定义必然1≤i≤n,1≤i≤n－1，并且一定存在着1≤k≤n-１(至少有k＝j存在),使（ａｉ,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，从而根据Ｒ1的定义，有（ａi,ａj）∈R1。故此＝Ｒ１综合两个方面，可得=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．设Ｒ是集合A上的反对称关系,|A｜＝ｈ,指了在R∩的关系矩阵中有多少个非零值？[解]由第12题的4）R是反对称关系当且反当R∩⊆IA,及|Ａ|=n可知,在R∩的关系矩阵中非零值最多不超过ｎ个。18．设R１和R２是集合A上的关系，判断下列命题的真假性,并阐明理由。假如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={a，b}，R1={（a,b）｝，R2={b，a}。那么Ｒ1R2={(a,ａ）},它就不是A上的反自反关系。３）假。令A＝｛a,b,c｝,R1=｛(a，b),（b，a）｝，R2={(b，ｃ)，（ｃ，b）}。那末R1Ｒ2＝{(a，ｃ）},就不是A的对称关系。4)假。令Ａ={a，b,ｃ,ｄ},R１={(a，c),(b,c）｝R2=｛(c，b)，(d，a）}易证R1，Ｒ2都是反对称关系。但是R１R２={(ａ，b)，（b，a）｝就不是A上的反对称关系。５)假。令A={ａ，ｂ，c}，R1＝{(a,c），（b,ａ），（b,c)}，R2={（c，ｂ），（a，ｃ），（a，b）}，易证R1和R2都是传递关系,但R1R2={（a，b）,（b,ｂ)，(ｂ,c）｝就不是A上的传递关系。19．设Ａ={1,2，3，４,5}，R⊆A×A,R={（1，2)，(２,3)，（2,5),（３，4），(4，3),（５,5）}用作图方法矩阵运算的方法求ｒ（R)，ｓ(R），t（R)。[解]1)作图法：Ｒ的关系图(R)的关系图55123412345515143253241Ｓ(Ｒ）的关系图t(R)的关系图因此: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,４）,(５，５)}２)矩阵运算法:Mr(R）=＝MＳ（R)＝===MＲοＲ=MRＭＲ＝==MＲ=因此r（R),ｓ(R），t（R)与1)作图法一致。20.设R⊆A×A，证明１)(Ｒ＋)++R+2）=R*[证明]1）一方面，由于(Ｒ+）+是R+的传递闭包,所以R+⊆（R+)+;另一方面，由于Ｒ+是Ｒ的传递闭包，故此R+是传递的。由于Ｒ+⊆Ｒ+及传递闭包（R＋)+是包含Ｒ+的最小传递关系，就有（Ｒ+）+⊆R+(定理4之3)；所以(R＋)+=R+。2）一方面,由于(R*)*是R＊的自反传递闭包，所以R＊⊆（R*)*；另一方面，由于R*是R的自反传递闭包，故此R*是自反的传递的。由于Ｒ*⊆R*及自反传递闭包（R＊）＊是包含R*的最小自批传递关系，就有（R＊)＊⊆R*（定理5的3))。所以（R*）*＝R＊。2１.设Ａ={１，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的最小传递关系,所以,取R1＝Ｒ+即为所求。现在来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|=４有限）其关系图如下：11124311243R的关系图R1的关系图3）能。由于R1并非全关系（否则，当R１是全关系时,就找不到了），所以只要取R2=A×A是Ａ上的全关系就可满足R２⊇R,R2≠Ｒ，并且全关系R2显然是一个传递关系。22．设A=｛1,2，3，4……，9},定义A×A上的关系如下：（a，b)Ｒ（c，d）∷a+ｄ=b+c证明R是Ａ×A上的等价关系；求[（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，两边同时减c+d,可得a＋f=b+e，从而可得(a，b)Ｒ（e，f)。综合（a）、(b)、(c)、说明Ｒ是Ａ×A上的等价关系。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上的关系,所以R⊆(A×Ａ)×(A×A)＝。２3.设A是一个非空集合，R⊆A×Ａ。假如R在Ａ上是对称的，传递的,下面的推导说明Ｒ在A上是自反的：对任意的a，b∈A，由于R是对称的,有:aRbｂRa于是aRbaRｂ∧bRa，又运用Ｒ是传递的,得:aＲb∧bRaａRa从而说明R是自反的。上述推导对的吗？请阐明理由。［答]上述推导不正解。推殖民地的谬论误在于假设Ａ的每个元素都由R关联着A的某一别的元素。假如这不是真的，那么对称性的条件的假设就始终是假的，因此结论当然是假的。因而在一个空集上的空关系都是平凡的对称和可传递，但不是自反的。此外关系｛(a,a)，(b，b)，（a,b),（b,a）}是自反的和传递的，但在集合{ａ,b，c｝上不是自反的。24．设R是集合A上的等价关系，证明也是集合A上的等价关系。[证明]证法一：(a）是自反的对任意的a∈A,由于Ｒ是自反的，所以(a，a）∈R,再由逆关系的定义有(ａ，a)∈（b）是对称的对任何（a，b）∈由逆关系的定义,有(b,a)∈R,由R的对称性,可得（a，b）∈Ｒ，再由逆关系的定义,就有（b，a)∈。（c）是传递的对任何(a,b）∈及(ｂ,c）∈,由逆关系的定义,有（b，ａ)∈Ｒ及(c，ｂ）∈Ｒ,根据R的传递性,可得（ｃ，a)∈R,再次由逆关系的定义，就有(ａ,c）∈。综合（ａ）(b）(c)可知是等价关系。证法二：（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上的等价关系。25．设R1和R2都是集合A上的等价关系１）证明R１∩R2也是A上的等价关系；2)用例于证明Ｒ１∪R２不一定是A上的等价关系（要尽也许小地选取集合Ａ）。[证]1）证法一:（ａ）R１∩Ｒ2是自反的对任何a∈A，由于Ｒ１，R2都是A上的自反关系，所以(a，ａ）∈R1（a,a)∈Ｒ2，因此(ａ,a)∈R1∩R2(b)Ｒ1∩R2是对称的对任何的(a，b）∈R１∩R2，就有（a,ｂ)∈R１且(a,b)∈R2,由Ｒ１，R2都是A上的对称关系,所以(ａ,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都是Ａ上的传递关系，所以（a，c）∈R1及（ａ，c)∈R2，因此（ａ,ｃ)∈R１∩R２。综合（a）,（b)，(ｃ）,可知R1∩R2是等价关系。证法二:(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)(的结合律、互换律)(a,c）R1(a,c)R2(R1,Ｒ２都是传递的)（a,c)R１R２所以,Ｒ1R2是对称的；综合（a）、（b）、(c），可知R1R2是Ａ上的等价关系。2)两个自反的（对称的)关系的并将是自反的(对称的）,但是，两个传递关系的并却未必是传递的。我们就从破坏传递性出发来构造反例:令R１={(a，ａ）,(b，b），(c,c）,(ａ,b)，(b,a)}R2＝{(a，a)，(b，b）,(ｃ,c），（b，c）,(c，b)}当A＝{ａ，b，c}时,R1,R２显然都是等价关系。但是abcabcabcＲ1∪Ｒ2＝{(a,a),（b,b),（c，c）,(a，b),（ｂ,a)（b,c），（ｃ，b)}都不是A上的等价关系，由于R１∪R2不传递：（a，ｂ)∈R1∪R2且(bc,但(a,c)∉Ｒ1∪R２;同样(c，b)∈R1∪R2且（ｂ,a)∈R１∪Ｒ2，但（c，aabcabcabcR1关系图R2关系图R1∪Ｒ２关系图并且|A|不也许再少了。由于任何少于3个元素的集合上的自反,对称关系一定是传递的！2６．设R是A上的等价关系,将A的元素按R的等价类顺序排列，请指出此等价关系R的关系矩阵MR有何特性？［解]将A的元素按其上的等价关系R的等价类顺序排列,这样产生的等价关系R的关系矩阵MR,通过适当的矩阵分块,ＭR的分块矩阵将成为准对角阵,准对角阵的对角线上的每一块都是一个全1方阵，它正好相应于等价关系R的一个等价块。27．设A是ｎ个元素的有限集合,请回答下列问题,并阐明理由。有多少个元素在Ａ上的最大的等价关系中?A上的最大的等价关系的秩是多少?有多少个元素在Ａ上的最小的等价关系中?Ａ上的最小的等价关系的秩是多少？[答］1)A上最大的等价关系是全关系R1＝A×A={（a,ｂ)|a∈Ａ∧b∈A}因此有ｎ２个元素在A上的最大的等价关系R1中，由于所有n2个二元组都在R1=A×A中。２）A上的最大的等价关系R１的秩是1。这是由于A中任何两个元素都有全关系R１=Ａ×A,因此Ｒ1的等价块包含了A的所有元素，A的所有元素都在同一个等价块中。３）Ａ上的最小的等价关系是么关系R2=IA=｛（a，a)a∈A}因此它中有n个元素,即n自反对。４）Ａ上的最小的等价关系的秩是n，由于么关系的每一个元素都自成一个等价块，每一等价块中也只有一个元素。28．设R1和R２是非容集合A上的等价关系,对下列各种情况,指出哪些是A上的等价关系;若不是，用例子说明。1)Ａ×A\R12）R1\R23)4)ｒ（R１＼R2)（Ｒ1\R2的自反闭包）５)Ｒ1R２[解]１)不是。设A={a},并且Ｒ1={（a,a）}，则R1是A上的等价关系,但A×A\Ｒ1={(a,a)＼（a,a）}=就不是Ａ上的等价关系,由于空关系不是自反的。2）不是。设A=｛(a,ｂ)}并且R1={（a，ａ)，（ｂ，b）,(a,ｂ），(b，a）}，R2={(a,a），(b,b)｝，则R1,R2都是Ａ上的等价关系,但是，R１\R2=｛(a,ｂ),（ｂ，a）｝就不是Ａ上的等价关系，由于R１\R２不自反。3)是。证法一：因R1是等价关系，因而R1是传递的，故此由第１2题之５)有＝Ｒ１R1⊆R1。另一方面，结任何（a,b)∈Ｒ1,由于Ｒ1是自反的，故此(b，b）∈R１，从而由复合关系之定义，有(ａ，b)∈R1R1,所以Ｒ１⊆,从而=R1，因此由R1是等价关系，知也是等价关系。证法二：一方面,对任何a,bA,(a,b)(cA)((a,c)Ｒ1(c,b)R1）(cＡ)((a,b)R1)（R1是传递的)（a,ｂ）R1(带量词的基本逻辑等价式:（x)pp）所以，R1;另一方面,对任何ａ，bA,（a,b)R1(ａ,b)R１(b,ｂ)R1)(R1是自反的）(a,b)所以，R1；综合这两方面，就有=R1;4）是。设Ａ={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上的等价关系。Ｒ1\R2={(a,b)，（b，a)，(b,c),(c，ｂ)｝ｒ（R1\Ｒ2)=｛(a,ａ)，（b,ｂ）,（c，c）,(a，ｂ)，（ｂ,a)，（ｂ,c),（ｃ，b）}因此r(Ｒ１\R2)不是A上的等价关系,由于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，ｃ)}不上的等价关系，由于R1R２不对称，（a,c)∈R１R２,但（c，a)∉R1R２。29．设A＝｛１，2，３,４}，请指出A上所有等价关系是多少？并阐明理由。[解］Ａ上的等价关系共有14个。根据A上的划分与Ａ上的等价关系一一相应的原理,我们只需求出Ａ上有多少个划分就行了。{{ａ}，{ｂ}，{c}，{d}}型划分，一个；｛｛a，ｂ},{c}，{d｝｝型划分，六个；{{a,b，｝，{c,d}}型划分,三个;{{a，ｂ，c}，{d}}型划分，四个;{{a,b,c,d｝}型划分,一个。总计：1+6+3+４+1＝1５。3０．设A={１,2，3，４，５，６｝,拟定A上的等价关系R，使此R能产生划分{{1，２,3,},{4},{5,6}}123123564R的关系图３1．设R是集合A上的关系R是循环∷=(ａ∈A）(ｂ∈A）(c∈Ａ）（aRｂ∧bＲcｃＲa）证明:R是自反的和循环的,当且仅当R是等价关系。[证]证法一:必要性若Ｒ是自反的和循环的，我们来证Ｒ是等价关系,为此证明(a)R是自反的。必要性条件所给。(b）R是对称的对任何(a,b)∈R,由于Ｒ是自反的，所以（b，b）∈R,再根据R是循环的可得（b,a)∈R。（ｃ)R是传递的对任何（a，b）∈R,（b,c)∈R，由于R是循环的,所以（c，a)∈R，运用R是对称的,就得到（a,c)∈R。充足性若Ｒ是等价关系,我们来证Ｒ是自反的和循环的。1）R是自反的。因R是等价关系,故R是自反的。2)R是循环的对任何（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是循环的)所以，Ｒ是对称的；（c)Ｒ是传递的：对任何a，b，cＡ，（ａ,ｂ)R(b,ｃ)R(c,ａ)Ｒ(Ｒ是循环的)（a,c)R(R是对称的)所以,R是传递的；综合（a)，（ｂ)，(c）可知Ｒ是等价关系；)：(a)R是自反的：由于R是等价关系，所以R是自反的;(b)R是循环的：对任何ａ，ｂ，cA,(a，ｂ）Ｒ（ｂ,ｃ)Ｒ(a,c)R(R是传递的)(c，a)R(R是对称的)所以,R是循环的;3２.设∏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},{b}，｛ａ,ｂ}｝就不是A的划分，由于｛a｝∩{ａ,b}＝{ａ}≠,就不是A的划分，由于{a｝∩{a,b}={a}≠。２）也许。假如∏１＝∏2,则∏1∩∏2是A的划分；假如，∏1≠∏2，则∏1∩∏2不是A的划分；例如A=｛a，b},∏１={{a｝，{b}}，∏2＝{{a，ｂ}},∏1∩∏２=,就不是A的划分。3)也许。假如∏1∩∏2=,则∏1\∏2=∏1是Ａ的划分；假如∏１∩∏２≠,则∏1\∏2不是A的划分；例如A={ａ，ｂ,c｝,∏１={{a},{b},{ｃ}},∏２=｛｛a}，{ｂ，c}}，∏1∩∏2=｛{a｝}因此∏1\∏2={{b}，{c}}就不是A的划分。由于{b}∪{c}=｛b,c}≠A。4)是。由于（∏１∩（∏2＼∏1））∪∏1＝∪∏1＝∏1,是A的划分。33．对下列集合上的整除关系画出哈斯图，并对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；没有最大元素;没有上确界。性质集合最大元最小元极大元极小元上界下界上确界下确界{２,３,６}６无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.设Ｒ是集合X上的半序关系，AＸ,证明R∩(A×A）是A上的半序关系。[证].证法一：令R１=R∩(A×A),则R1A×A,所以R1是A上的关系,我们只需证明在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。运用Ｒ的传递性，可得(a，ｃ)∈Ｒ,运用a,c∈A可得(a，c）∈A×Ａ,所以（a,c)∈Ｒ∩(Ａ×A）,即（a，c）∈Ｒ１。证法二:令R1=R(ＡA）,由于R(AA)AA,所以R1AA,因此Ｒ1是A上的关系。①R１是自反的对任何a，ａA(a，ａ)R（ａ,ａ)AA(R是Ｘ上的自反关系及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）(的结合律、互换律)((a,b)Ｒ（b,a)R)(基本逻辑蕴涵式:ｐｑ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)(的结合律、互换律)((a,ｃ)R（ａ,c)ＡA（R是传递的，全关系AA是传递的)(ａ,c)R(AＡ)（a,ｃ)R1(R１的定义）所以,R1是传递的;综合①、②、③,可知R1是A上的半序关系。36．设（A，≼１）和（A,≼2)是两个半序集合,定义Ａ×B上的关系≼3如下:对于a1,ａ2∈A,,b2∈B（ａ1,b1）,(ａ2，ｂ2）∈≼3(a１,a2)∈≼1∧(b1，ｂ2)∈≼2证明≼3是A×B上的半序关系。［证].证法一:对于任何(ａ，b)∈A×B,就有a∈A及ｂ∈B,从而运用≼１及的自反性,可得（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运用≼１及≼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。运用≼1及≼２的传递性,可得（a1,ａ3）∈≼1及(b１，b3)∈≼2。再次运用≼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)(的结合律、互换律)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)(的结合律、互换律)（a，e)≼１(b,f）≼２(≼１，≼2都是反对称的)((ａ,b),(ｅ,ｆ)）≼3(≼3的定义）所以,≼３是传递的；综合①、②、③，可知≼3是AB上的半序关系。３7．对于非空集合A，是否存在这样的关系R,它即是等价关系又是半序关系?若有，请举出例子。［解]有。只有一种,那就是A上的幺关系IA，它即是等价关系，又是半序关系。证法一:否则,假如有a∈Ａ及b∈Ａ且ａ≠ｂ,使得(a,b)∈R,那么由R是对我的就将有(ｂ，a）∈R,再由Ｒ是反对称的,