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

习题二,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上的自反关系必须满足所有形如的序偶包含在关系中，而形如的序偶有n个。即|AA-|=n2-n在构造A上的自反关系的时候可以先将所有的放到这些关系中再考虑其他序偶的组合。即|(AA-)|=2n2-n,(3)共有种定义在A上的不同的反自反关系；说明:A上的反自反关系必须满足所有形如的序偶不能包含在关系中，在构造A上的反自反关系的时候可以先将所有的拿出后再考虑其他序偶的组合。即(AA-)=2n2-n,(4)共有种定义在A上的不同的对称关系;说明:A上的对称关系必须满足：如果在这个关系中，则也必须在这个关系中。在构造A上的对称关系的时候可以先将所有的和（其中xy）看成是一个整体。要考虑的序偶的个数有：n+(n2-n)/2=n(n+1)/2(+(AA-)/2)=2(n2+n)/2,(5)共有种定义在A上的不同的反对称，其中，。,4.,(1)自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈（即若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个结点都有自回路）。(2)反自反关系矩阵的主对角线上元素全为0;而关系图中每个结点上均无圈（即若关系R是反自反的，当且仅当在关系矩阵中，对角线上的所有元素都是0，在关系图上每个结点都没有自回路）。,(3)对称关系矩阵为对称矩阵;而关系图中任何两个结点之间的有向弧是成对出现的,方向相反。（即若关系R是对称的，当且仅当关系矩阵是对称的，且在关系图上任两个结点若有定向弧线，则定向弧线必定是成对出现的）反对称关系矩阵的元素满足：当ij时，。而关系图中任何两个结点之间的有向弧是单向的。（即若关系R是反对称的，当且仅当关系矩阵中以对角线对称的元素不能同时为1，在关系图上任两个结点的定向弧线不可能成对出现）,5.,RS=,SR=;R2=,;S2=,.,6.,设R=,T=,S=,P=,7.,(1)正确。因为对任意xA，有xRx，xSx,所以x(RS)x。故RS是自反的。(2)错误。例如，设x,yA，xy,且xRy，ySx，于是x(RS)x。故RS不是反自反的。,(3)错误。例如，设对称关系R=,S=,。则RS=,故RS不是对称的。,(4)错误。例如，设反对称关系R=,S=,xy。于是，RS=,。故RS不是反对称的。(5)错误。例如，设传递关系R=,S=,wv。于是，RS=,，显然，RS不是一个传递关系。,思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。,思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。,8.,(3)由定义，,于是存在z1,z2,zn-1,满足：,R1R1R2,举例说明“”成立。设,9.,设R1和R2是集合A上的二元关系。注意到,(3)由定义，,t(R1R2)=(R1R2)(R1R2)2于是t(R1)t(R2)=(R1R2)(R1R22)(R12R22)(R12R2)下证对任意的n1,有(R1R2)n(R1nR2n)证明:任取(R1R2)n,则存在n-1个元素z1,z2zn-1满足R1R2,R1R2,R1R2。从而有R1,R1,R1并且R2,R2,R2。,所以有R1n并且R2n，即R1nR2n所以(R1R2)n(R1nR2n)例如：设A=1，2，3，R1=,R2=则t(R1)=,t(R2)=,t(R1)t(R2)=,R1R2=,t(R1R2)=,10.说法不正确.这是因为自反性要求对任意的x和x都有关系R,x和y有没有关系R,我们不考虑；但是,我们题目中得出的结论x和x具有关系R,是以对称性为前提条件的,所以我们知道该论述不正确。,11.,设R是等价关系。若,R，则由R的对称性知,R。再由R的传递性有R。反之,假设只要,R，就有R。(1)对称性。设R，由自反性有R。于是R。(2)传递性。设,R。由对称性有R,再由假设有R。,12.,而由A/R1=A/R2,有对任意xA,因为xR1A/R2并且xxR1xR2，所以xR1=xR2。产生矛盾。,13.,14.,故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，有两种可能：,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上的全部等价关系数目,则,因为En是将n个元素的集合进行划分的方法数，对任何一个划分来说，b总是在划分的某一个块中，也就是某一个子集中。不妨设这个子集有k个元素(k=1,n),则在此子集中的另外k-1个元素将从n-1个元素中选取。然后对剩下的n-k个元素进行划分。故有,16.,15,3,5,12,6,2,3,1,54,27,9,3,17.,(1)最(极)大元x1,无最小元;(2)上界下界上确界下确界x2,x3,x4x1x4x1x4x3,x4,x5x1,x3无x3无x1,x2,x3x1x4x1x4,18.,(2)题16中的,子集3,5无最大元;(3)题16中的,子集2,3,6有下确界但无最小元;(4)题16中的,子集1有上界2,3,6,12,但是无上确界。,19.,设为全序集,且|A|=n。,因此,B中必有最小元a.故为良序集,20.,设B是A的