湘潭大学 刘任任版 离散数学课后习题答案 习题2

习题1•确定下列二兀关系：］(IA=&,2,3lB=务,3,51R=vx,y|x,yeAB°uAxBA=^0,1,2,3,4,5,6,8}R={x,=2yAxA分析：本题主要运用知识为集合的交、关系以及笛卡尔积的定义。解：(1)R={<1,1>,<1,3>,<3,1>,<3,3>}R={<1,0>,<2,1>,<4,2>,<&3>}2•请分别给出满足下列要求的二元关系的例子：(1)既是自反的，又是反自反的；既不是自反的，又不是反自反的；(3)既是对称的，又是反对称的；(4)既不是对称的，又不是反对称的•分析本题主要考察关系的5个性质(自反性、反自反性、对称性、反对称性、传递性)。解：设R是定义在集合A上的二元关系。令A=0，则R=0，于是R既是自反又是反自反的；令A={1,2},R={<1,1>}，于是R既不是自反又不是反自反的；令A={1,2},R={<1,1>,<2,2>}，于是R既是对称又是反对称的；令A={1,2,3},R={<1,2>,<2,1>,<1,3>}，于是R既不是对称又不是反对称的。3.设集合A有n个元素，试问：共有多少种定义在A上的不同的二元关系？共有多少种定义在A上的不同的自反关系？共有多少种定义在A上的不同的反自反关系？共有多少种定义在A上的不同的对称关系？共有多少种定义在A上的不同的反对称关系？分析：本题主要考察知识为二元关系的自反性、反自反性、对称性、反对称性所对应的关系矩阵之性质，本题可以在做完第四题(根据满足某个性质的关系之关系矩阵)之后再来考虑。解：设|A|=n，于是共有2n种定义在A上的不同的二元关系；共有2n-n种定义在A上的不同的自反关系；共有2n-n种定义在A上的不同的反自反关系；共有2n-2n(n-1)/2=2n(n+1)/2种定义在A上的不同的对称关系；共有2n£Ck*2m-k=2n•3m种定义在A上的不同的反对称关系，其中，m=—m2k=04•请分别描述自反关系，反自反关系，对称关系和反对称关系的关系矩阵以及关系图的特征分析：本题主要是根据自反关系、反对称关系、对称关系和反对称关系之定义来确定关系矩阵以及关系图。解：(1)自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。(2)反自反关系矩阵的主对角线上元素全为0;而关系图中每个结点上均无圈。

对称关系矩阵为对称矩阵;而关系图中任何两个结点之间的有向弧是成对出现的方向相反。5．当°丰j时，『二°。2,3；：,；2,4；,32；J试求R-S,S-R,R2,⑷反对称关系矩阵Mr=5．当°丰j时，『二°。2,3；：,；2,4；,32；J试求R-S,S-R,R2,及S2.分析主要考察关系的复合运算之定义。解：R•S={<1,4>,<1,3>},S•R={<3,4>}R2={<1,1>,<1,2>,<1,4>},S2={<2,2>,<3,4>,<3,3>}。6.试举出使R-(SnT)u(R-S)n(R-T)(snt)•pu(s-p)n6*p)成立的二元关系R,S,T,P的实例.分析本题主要说明关系的复合与关系的交运算不满足分配率。解：设R={<3,1>,<3,2>},T={<1,3>,<3,2>},S={<1,2>,<2,3>},P={<2,1>,<3,1>},于是，有SnT=0,R-(SnT)=0,R-S二{<3,2>,<3,3>},R-T={<3,3>},R-(R-(SnT)u(R-S)n(R-T)。T-P={<3,1>,<1,1>}，因此,(SnT)-Pu(S-P)n(T-P)。(R-S)n(R-T)={<3,3>}丰0从而,又，(SnT)-P=0,S-P={<1,1>},(S-P)n(T-P)={<1,1>}H0，从而,7.设R和S是集合A上的二元关系.下面的说法正确吗?请说出理由.若R和S是自反的，则R-S也是自反的；若R和S是反自反的，则R-S也是反自反的；若R和S是对称的，则R*S也是对称的；⑷若R和S是反对称的，则R-S也是反对称的；(5)若R和S是传递的，则R-S也是传递的分析本题主要是考察两个满足同一种性质的关系之复合运算是否保该性质，是的可以根据定义给出证明，不正确请给出反例，一般如果正确相对容易证明，不正确给出反例相对较难。解：⑴正确。因为对任意xgA，有xR,xSx,所以x(R-S)x。故R-S是自反的。(2)错误。例如，设x,ygA,x丰y，且xRy,ySx,于是x(R-S)x。故R-S不是自反的。⑶错误。例如，设对称关系R={<x,z>,<z,x>},S={<z,y>,<y,z>}。于是，<x,y>gR-S，但<y,x>《R-S。故R-S不是对称的。错误。例如，设反对称关系R={<x,z>,<y,w>},S={<z,y>,<w,x>},x丰y。于是，<x,y>,<y,x>gR-S。故R-S不是反对称的。错误。例如，设传递关系R={<x,w>,<y,v>},S={<w,y>,<v,z>},w丰v。于是，x(R-S)y,y(R-S)z，但因为w丰v，所以，<x,z>gR-S。8•设R1和R2是集合A上的二元关系，试证明:

(1)r(RUR)=r(R)Ur(R)；⑵s(RUR)=s(R)Us(R)；⑶t(R；UR；Lt(R；)Ut(R2)并举出使＞1时使t(RUR)二t(R)Ut(R)的实例.1212分析：(1)本小题根据自反闭包的定义，它一个关系R的自反闭包应该包含R0，然后根据(RuR)o=R0oR0即可证得。(2)本小题根据对称闭包的定义，它一个关系R的对称闭1212包应该包含R-1，然后根据(RoR)-1二R-1uR-1即可证得。(3)由于传递闭包的特殊性，1212它不满足类似与(1)(2)的情形，所以要进行相对麻烦的证明，主要运用集合的包含关系的证明方法。解：⑴r(RoR)二(RoR)o(RoR)oR2R2)o(R10oR20)R10)o(R2oR20)=(R1o=(R1o二r(RJor(R2)(2)s(R1oR2(2)s(R1oR2)=(R1oR2)o(R1oR2)-1=(R1oR2)o(R1-1oR2-1)oR1-1)o(R2oR2-1)=s(R])os(R2)(3)由定义，t(R])=R]oRfo…,于是，t(R2)=R2oR2o…，t(R]oR2)=(R]oR2)o(R]t(R])=R]oRfo…,于是，t(R])ot(R2)=R]oR]2o・・・oR2oR22o・・・=(R]oR2)o(R]2oR22)o…。下证对任意n>1，有R]noR2nu(R]oR2)n。任取<x,y>eR]noRJ，不妨设<x,y>eR]n。于是，存在z],z2,…znga,使得<x,Z[>gR[匸R[oR2,<Z[,z2>gR[匸R[oR2,…，<z.,z>gR.匸R.oR2,<z,y>g111212112n-1n112n从而，<x,y>g(R]oR2)n。举例说明“u”成立。设A={1,2,3},R]={<1,2>},R2={<2,3>}，于是，tt(R1oR2)二{<1,2>,<1,3>,<2,3>}二t(R])ot(R2)二{<1,2>,<1,3>}9.设R和R2是集合A上的二元关系，试证明：(1)r(RA卞)=r(R)Ar(R)；⑵s(RAR)us(R)As(R)；(3)t(RAR)ut(R)At(R)并请给出IA>1时使s(RAR)us(R)As(R)和t(RAR)ut(R)At(R)的实例.12121212分析：(1)本题主要是根据自反关系的定义得到一个特殊的等式R]o=R20=(R]cR2)0进行变换，只要想到这个等式，下面的工作就比较容易做。(2)本题主要是根据对称关系的定义及定理的定义及定理2.2.6得到如下三个公式：s(R]cR2)=(R]cR2)o(R]cR2)-1,R2oR2-]s(R])=R]oR]-i,s(R2)=s(R])cs(R2)=(R]oR]-1)c(R2oR2-]R2oR2-]方法就可得到结论。(3)本小题根据传递闭包的定义及定理2.2.6得t(R)=RoR2o…，t(R)=RoR2o…，t(RcR)=(RcR)o(RcR)2o…,]]]222]2]2]2有了上面三个等式以及集合之间包含关系证明方法可得结论。解：设的和R2是集合a上的二元关系。注意到R]0=R20=(R1cR2)0，于是，r(R1cR2)=(R1cR2)o(R1cR2)0=(R1cR2)oR10=(R1oR10)c(R2oR10)=(R1oR10)c(R2oR20)=t(R1)ct(R2)s(R1cR2)=(R1cR2)o(R1cR2)-1,s(R1)=R1oR1-1,s(R2)=R2oR2-1,s(R])cs(R2)=(R]oR]-1)c(R2oR2-1)。任取x,y>es(R]cRJ=(R1cRJo(R、cRJ-1，若<x,y>e(R]cR)则<x,y>eR1cR1oR1-1,且x,y>eR2cR2oR2-1,从而，x,y>e(R]oR]-])c(R2oR2-1=s(R])cs(R2)；若<x,y>e(R]cR2)-1,则<y,x>g(R]cR2),即y,x>eR],且<y,x>eR2,从而，x,y>eR]-1cR]oR]-1,且<x,y>eR2-1cR2oR2-1,于是，x,y>e(R]oR]-])c(R2oR2-]=s(R])cs(R2)故s(R]cR2)cs(R])cs(R2)。举例说明“u”成立。={<1,2>,<2,1>},)us(R])cs(R2)。证明：因为t(R1)=R1oR20…,t(R2)=r2or；o…，t(RcR)=(RcR)o(RcR)20…，121212于是t(R)ct(R)=(R0R20…)c(R0R2o…)=o(RicRm)121122皿112设A={1,2},={<1,2>,<2,1>},)us(R])cs(R2)。证明：因为t(R1)=R1oR20…,t(R2)=r2or；o…，t(RcR)=(RcR)o(RcR)20…，121212于是t(R)ct(R)=(R0R20…)c(R0R2o…)=o(RicRm)121122皿112V<x,y>et(RnR)=(RnR)u(RnR)2u…，121212则存在i,有<x,y>((RnR》也就有z,z，…,z使得<x,z>eRnR,TOC\o"1-5"\h\z1212i112<x,z>eRnR，…,<x,z>eRnR，因为RnR匸R且212i12121RnR匸R，所以就有<x,z>eR,<x,z>eR，…,<x,z>eR,1221121i1所以有<x,y>eRi同时也有<x,z>eR,<x,z>eR，…,<x,z>eR,11222i2所以也有<x,y>eR/就有<x,y>wRjnR/，即(RnR)匸RjnR/,2121212又因为Ri1nRi2匸u(RinRm2),所以结论成立。1212l,m>1又设A={1,2,3},叫={<1,2>,<2,3>},R2={<1,3>},于是，rnr=0,t(rnr)=0,而，1212t(R)={<1,2>,<2,3>,<1,3>},1t(R)=R={<1,3>},22t(R)nt(R)={<1,3>}12故t(RnR)Ut(R)nt(R).121210.有人说，“如果集合a上的二元关系R是对称和传递的，则R必是自反的.因此，等价关系定义中的自反性可以去掉”.并给出如下证明，如果{x,y；eR,由R的对称性有]y,x；eR,再由R的传递性知，■:x,x]eR且「y,y：eR，即R是自反的.你的看法如何？分析：本题主要是没有弄明白对称和传递都是满足一定前提条件的，而自反关系则是A中每个元素都必须满足这个条件。解：说法不正确。对任意xeA，对称性并不要求一定有<x,y>eR,因此也就不一定有<y,x>。于是<x,xR。例如：设A={1，2,3},R={<1,2>,<2,1>,<1,1>}，则R是对称和传递的，但是R不是自反的，因为R中不包含<2,2>,<3,3>，这是因为R如果是自反的必须包含R0。11.设R是集合A上的自反关系.试证明R是等价关系当且仅当若：；x,y：,：：x,zeR，则::y,z；eR.分析：本题主要是利用等价关系中自反性、对称性、传递性的定义来证明。44解：设R是等价关系。若vx,y>,<x,z>wR,则由R的对称性知,<y,x>wR。再由R的传递性有vy,z>wR。反之，假设只要vx,y>,vx,z>wR,就有vy,z>wR。对称性。设vx,y>wR,由自反性有vx,x>wR。于是vy,x>wR。传递性。设vx,y>,vy,z>wR。由对称性有vy,x>wR,再由假设有vx,z>wR。设R和R都是集合A上的等价关系，试证明R=R当且仅当A/R=A/R.121212分析：本题主要是根据等价类的定义及性质可以得到。证明：设R=R,则显然A/R=A/R。1212反之，设A/R=A/R。若R丰R,则不妨设vx,y>wR但vx,y>纟R.121212于是[x]二[y],[x]主[y].R1R1R2R2由划分之定义得知A/R丰A/R,矛盾.。故R=R。1212设R二fx,y；|x三y(mod5甘是定义在整数集Z上的模5同余关系，求Z/R.分析：本题主要是等价类的定义及性质可以得到。解：设R={vy,x>lx=y(mod5)}.于是[0]={...-15,-10,-5,0,5,10,15...}R={.・・-14,-9,-4,1,6,11,16,・・・}R={.・・-13,-8,-3,2,7,12,17,・・・}R={•••-12,-7,-2,3,8,13,18,・..}R={・・・-11,-6,-1,4,9,14,19,・・.}RA/R={[0],[1],[2],[3],[4]}.RRRRR设A=^A,A，…,A}和B={B,B，…,R}是集合X的两个划分，令12r12s

S兀nB|anB工0,1<i<r,1<j<s}ijij试证明S也是X的一个划分.证明：本题主要是根据划分的定义以及集合的性质可以得到证明：•/S二{AnBIAnB鼻0}.iiii(1)由S定义知，AnB鼻0；ii⑵任取AnBgS和AnBgS,1<=i,jv=r,1v=j,mv=s.TOC\o"1-5"\h\ziilm（anb）n（anb）二（ana）n（bnb）=0n0=0iilmimjm（3）x=xnx=（au....ua）n（bu...ub）=U（anb）=U（Anb）=smijij11<<ij11<<ij,<js<r1<j<sa.nb.主0ij故S是x的一个划分.15.定义在4个元素的集合A之上的等价关系共有多少个？若|A|=n呢？分析：本题是根据等价关系与划分的一一对应关系，利用划分来处理，由特殊推到一般。有几种证明方法。解：设A={1,2,3,4},则A上的等价关系数目即A上的划分的数目共有15个.最大划分{{1},{2},{3},{4}}最小划分{{1,2,3,4}}将A分成两个集合S={q,A2},共有两种可能：⑴|A|=|A|，共有1/2C2=3种，即124{{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}}。(ii)|A|=1,|A|=3,共C3=4种，即124{{1},{2,3,4}},{{2},{1,3,4}},{{3},{1,2,4},{{4},{1,2,3}}将A分成三个集合，则恰有一个集合为2个元素，故共有C2=6种分法，即

{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4},{2},{3}},{{2,3},{1},{4}},{{2,4,{1},{3}},{{3,4},{1},{2}}}设E表示可k元集合A上的全部等价关系数目,则kE=£E,•Cn-1-knkn-1<k=0E=10本公式还有下面一个推导方法：解:设f(n,k)表示将n个元素分成k块的划分数。则f(n,1)=f(n,n)=1,设n>1,且1<k<n,设b是A的某个元素，若{b}组成一个块，则有f(n-1,k-1)种方法能将A\{b}分成k-1块，另一方面，A\{b}分成块的每个划分允许b被接纳到一块中，有k种方法，因此我们有f(n,k)=f(n-1,k-1)+kf(n-1,k).16.设A=&5，15}A=b，2,3,6，12}A=&9,27,54},偏序关系<为整除.试分别画出1,23解：（A］，-），（A2,，以及解：（A］，-），（A2,，以及（A3,-）的Hasse图.<A1,<>27<A2,<>图2.317．{x,x,x,x,x1234517．{x,x,x,x,x12345的Hasse图如图2.3所示：（1）求A的最大（小）元，极大（.小）｛元；I（2）分别求tx,x,xJ，lx,x,x［和lx,x,x［的上（下）界，上（下）确界.234345123分析：本题主要是根据极大（小）元，最大（小）元，上（下）界，上（下）确界的定义进行