习题二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是对称的，当且仅当关系矩阵是对称 的，且在关系图上任两个结点若有定向弧线， 则定向弧线必定是成对出现的）(4)反对称关系矩阵 的元素满足：当ij 时 ， 。而关系图中任何两个结点之间的有向弧是单向的 。（即若关系R是反对称的，当且仅当关系矩阵 中以对角线对称的元素不能同时为1，在关系图 上任两个结点的定向弧线不可能成对出现）5.RS=,SR=; R 2=,; S 2=,.6.设 R=,T=,S=,P=,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不是一个传递关系。思考：假设R，S是定义在有限集合A上的满足 下表列标题性质的二元关系，试判断下表行标 题所列二元关系是否具有相应性质。 自反性反自反 对称性 反对称 传递性R-1RSRSR-SR.S思考：假设R，S是定义在有限集合A上的 满足下表列标题性质的二元关系，试判 断下表行标题所列二元关系是否具有相 应性质。8.(3)由定义，于是存在z1,z2,zn-1,满足：R1 R1R2举例说明“ ”成立。设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，即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。再由R的传 递性有R。 反之, 假设只要, R，就有 R。(1)对称性。 设R，由自反性有 R。于是R。 (2)传递性。 设, R。由对 称性有R, 再由假设有R 。12.而由A/R1=A/R2 ,有对任意xA,因为xR1 A/R2 并且x xR1 xR2，所以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上的全部等价关系数 目, 则w 因为En是将n个元素的集合进行划分的方法 数，对任何一个划分来说，b总是在划分的某一个块中，也就是某一个子集中。不妨设 这个子集有k个元素(k=1,n),则在此子集中 的另外k-1个元素将从n-1个元素中选取。然 后对剩下的n-k个元素进行划分。故有16.153512623154 279317.(1) 最(极)大元x1, 无最小元; (2)上界 下界 上确界 下确 界 x2, x3, x4 x1 x4 x1 x4 x3, x4, x5 x1,x3 无 x3 无 x1, x2, x3 x1 x4 x1 x418.(2)题16中的,子集3 ,5无最大元; (3)题16中的,子集2,3,6有下确界 但无最小元; (4)题16中的,子集1 有上界 2,3,6,12,但是无上确界。19.设为全序集, 且|A| = n。因此, B中必有最小元a.故为良序集20.设B是A的非空有限集。若B中不存在极 大(小)元,则对任何xB,则存在yB,使得xy(yx),如此下去,得出 B为无限集.矛盾.故结论成立。21.设B是A上的一个非空有限集,由上题知,B 中至少有一个极大(小)元。又因为全序集,故B的极大(小)元 均唯一, 且就是最大(小)元。