离散数学(刘任任版)第2章答案

1、习题二1.(1). R=,(2). R=,2.设R是定义在集合A上的二元关系。 (1). 设A= ，则R= 既是自反的又是反自反的. (2). 令A=1，2，R=，于是R既不是自反又不是反自反的； (3). 令A=1，2，R=,于是R既是对称又是反对称的； (4). 令A=1,2,3,R=, 于是R既不是对称又不是反对称的。3. 设A=X1,X2 ,Xn，于是定义在A上的二元关系R中的元素来自于下列矩阵： . (1)共有2n2 种定义在A上的不同的二元关系； 说明: |A|=n |AA|=n2 |(AA)|=2n2 (2)共有 种定义在A上的不同的自反关系；说明: A上的自反关系必须满足所有形

2、如的序偶包含在关系中，而形如的序偶有n个。即|AA-|=n2-n 在构造A上的自反关系的时候可以先将所有的放到这些关系中再考虑其他序偶的组合。即|(AA-)|=2n2-n nn 22 (3)共有 种定义在A上的不同的反自反关系；说明: A上的反自反关系必须满足所有形如的序偶不能包含在关系中， 在构造A上的反自反关系的时候可以先将所有的拿出后再考虑其他序偶的组合。即(AA-)=2n2-n nn 22 (4)共有 种定义在A上的不同的对称关系;说明: A上的对称关系必须满足：如果在这个关系中，则也必须在这个关系中。 在构造A上的对称关系的时候可以先将所有的和（其中xy）看成是一个整体。 要考虑的序

3、偶的个数有： n+(n2-n)/2=n(n+1)/2 (+(AA-)/2)=2(n2+n)/2 2/ )1(2/ )1(222nnnnn (5)共有 种定义在A上的不同的反对称， 其中， 。 kmmkkmnC2202) 1( nnm4. (1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈（即若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个结点都有自回路）。 (2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈（即若关系R是反自反的，当且仅当在关系矩阵中，对角线上的所有元素都是0，在关系图上每个结点都没有自回路） 。 (3

4、) 对称关系矩阵为对称矩阵; 而关系图中任何两个结点之间的有向弧是成对出现的, 方向相反。 （即若关系R是对称的，当且仅当关系矩阵是对称的，且在关系图上任两个结点若有定向弧线，则定向弧线必定是成对出现的）反对称关系矩阵 的元素满足： 当ij 时 ， 。 而关系图中任何两个结点之间的有向弧是单向的。（即若关系R是反对称的，当且仅当关系矩阵中以对角线对称的元素不能同时为1，在关系图上任两个结点的定向弧线不可能成对出现）nnijRrM)(0jiijrr5.RS=,SR=;R 2=,;S 2=,.6.设R=,T=,S=,P=,)(,TSRTS于是有3 , 3,3 , 3,2 , 3TRSR3 , 3)

5、()(TRSR因此)()()(TRSRTSR从而,1 , 1,)(PSPTS又1 , 1,1 , 3PT1 , 1)()(PTPS因此)()()(PTPSPTS从而7. (1) 正确。因为对任意xA，有xRx，xSx,所以x(RS)x。故RS是自反的。 (2) 错误。例如，设x,yA，xy,且xRy，ySx，于是x(R S)x。故R S不是反自反的。(3)错误。例如，设对称关系R=,S=,。则RS=故RS不是对称的。(4) 错误。例如，设反对称关系R=,S=,xy。于是，RS=,。故RS不是反对称的。 (5) 错误。例如，设传递关系R=,S=,wv。于是，RS=,，显然， RS不是一个传递关系

6、。思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。自反性反自反 对称性 反对称 传递性R-1RSRSR-SR.S思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。8.0212121)()()() 1 (RRRRRRr)()(020121RRRR)()(022011RRRR)()(21RrRr1212121)()()()2(RRRRRRs)()(121121RRRR)()(122111RRRR)()(21RsRs(3)由定义，,)(,)(22222111RRRtRRR

7、t,)()()(2212121RRRRRRt22221121)()(RRRRRtRt于是)()(222121RRRRnnnRRRRn)(12121 有下证对任意nnRRyx21,任取nRyx1, 不妨设,211212111RRRzzRRRzx于是存在z1,z2,zn-1,满足：R1 R1R2nRRyx)(,21从而举例说明“ ”成立。设于是3 , 2,2 , 1,3 , 2 , 121RRA3 , 2,3 , 1,2 , 1)(21 RRt3 , 1,2 , 1)()(21RtRt9.设R1和R2是集合A上的二元关系。注意到 ，于是0210201)(RRRR0212121)()()() 1 (

8、RRRRRRr0121)(RRR)()(012011RRRR)()(022011RRRR)()(21RrRr1212121)()()()2(RRRRRRs12221111)(,)(RRRsRRRs任取)()()()(12211121RRRRRsRs1212121)()()(,RRRRRRsyx),(,)(21RRyxi若从而,1222RRRyx)()(,122111RRRRyx且则,1111RRRyx)()(21RsRs,)(,)(121RRyxii 若即则),(,21RRxy,21从而且RxyRxy,11111且RRRyx,12212于是RRRyx)()(,122111RRRRyx).()(

9、)(2121RsRsRRs故)()(21RsRs:成立举例说明 ,1 , 2,2 , 1,2 , 121于是设RRA1212121)()()(RRRRRRs而,1,1 , 2,2 , 1)(1111RRRs1 , 2,2 , 1)(1222RRRs,1 , 2,2 , 1)()(,21RsRs因此)()()(2121RsRsRRs故(3)由定义，,)(,)(22222111RRRtRRRtt(R1R2)=(R1R2)(R1R2)2于是 t(R1)t(R2)=(R1R2)(R1R22) (R12R22)(R12R2) ) 下证对任意的n1,有(R1R2)n (R1nR2n)证明:任取(R1R2)

10、n, 则存在n-1个元素z1,z2zn-1满足R1R2, R1R2,R1R2。从而有R1 , R1, R1并且R2 , R2, R2。所以有R1n 并且R2n，即 R1n R2n所以(R1R2)n (R1nR2n)例如：设A=1，2，3，R1=, R2=则t(R1)=, t(R2)=, t(R1)t(R2)=, R1R2= , t(R1R2)= w 10.说法不正确. 这是因为自反性要求对任意的x和x都有关系R, x和y有没有关系R,我们不考虑；但是,我们题目中得出的结论x和x具有关系R,是以对称性为前提条件的,所以我们知道该论述不正确。11.设R是等价关系。若,R，则由R的对称性知, R。再

11、由R的传递性有R。反之, 假设只要, R，就有R。 (1)对称性。 设R，由自反性有R。于是R。 (2)传递性。 设, R。由对称性有R, 再由假设有R。12.2121/,RARARR则显然设21/,RARA设反之121,RyxRR则不妨设若2,Ryx但2211 ,RRRRyxyx于是21RR 故而由A/R1=A/R2 ,有对任意xA,因为xR1 A/R2并且x xR1 xR2，所以xR1=xR2。产生矛盾。13.于是设),5(mod|,yxxyR4 ,3 ,2 ,1 ,0/.19,14,9 ,4, 1,6,11.4.18,13,8 , 3 ,2,7,12.3.17,12,7 ,2, 3,8,

12、13.2.16,11,6 , 1 ,4,9,14.1 .15,10,5 ,0 ,5,10,15.0RRRRRRRRRRBA14.|jijiBABAS证明jiBAS,) 1 (定义知由)()()()(,1 ,1,)2(mjmimljimliiBBAABABAsmjrjiSBASBA和任取SBABABBAAjiBAsjrijisjrjijimjr111,11)()().().()3(故S是X的一个划分15.设 A=1,2, 3,4 , 则A上的等价关系数目即A上的划分的数目共有15个 (1) 最大划分 1,2,3,4 (2) 最小划分 1,2,3,4 (3) 将A分成两个集合S=A1，A2，有两种

13、可能： 2,31,4, , 2,41,3, , 3,41,2, ,31/2|,A|A| (i) 2421即种共有C1,2,34,1,2,4,3, , 1,3,42, 2,3,41, ,4 . 3|A|1,|A| (ii)3421即种共C即种分法故共有元素个则恰有一个集合为个集合分成将,6C,2,3A(4)24 1,2,3,4, 1,3,2,4, 1,4,2,3, 2,3,1,4, 2,4,1,3, 3,4,1,2 .设Ek表示k元集合A上的全部等价关系数目, 则101101nkknnnCkEEEw 因为En是将n个元素的集合进行划分的方法数，对任何一个划分来说，b总是在划分的某一个块中，也就是

14、某一个子集中。不妨设这个子集有k个元素(k=1,n),则在此子集中的另外k-1个元素将从n-1个元素中选取。然后对剩下的n-k个元素进行划分。故有1011011211101nkkknnnnnnnnnECECECECE16.A1,1535A2,12623154 2793A3,17.(1) 最(极)大元x1, 无最小元;(2) 上界 下界 上确界 下确界x2, x3, x4 x1 x4 x1 x4x3, x4, x5 x1,x3 无 x3 无x1, x2, x3 x1 x4 x1 x418.(2)题16中的A1,子集3 ,5无最大元;(3)题16中的A2,子集2,3,6有下确界但无最小元;(4)题16中的A2,子集1 有上界2,3,6,12,但是无上确界。0|,) 1 (mZmZZZZ其中无最小元但为整数集为全序集19. 设为全序集, 且|A| = n。xyyxyxBAB或者均有中的任意两个元素因任取,因此, B中必有最小元a.故为良序集20. 设B是A的非空有限集。若B中不存在极大(小)元,则对任何xB, 则存在yB,使得xy(yx),如此下去,得出B为无限集.矛盾.故结论成立。21. 设B是