离散数学 刘任任 课后答案 习题2

1、习 题 二1.确定下列二元关系：（1）（2） 解：(1) (2) 2. 请分别给出满足下列要求的二元关系的例子：（1）既是自反的，又是反自反的；（2）既不是自反的，又不是反自反的；（3）既是对称的，又是反对称的；（4）既不是对称的，又不是反对称的. 解：设是定义在集合上的二元关系。(1) 令，则，于是既是自反又是反自反的；(2) 令，于是既不是自反又不是反自反的；(3) 令，于是既是对称又是反对称的；(4) 令，于是既不是对称又不是反对称的。3. 设集合有个元素，试问：（1）共有多少种定义在上的不同的二元关系？（2）共有多少种定义在上的不同的自反关系？（3）共有多少种定义在上的不同的反自反关系

2、？（4）共有多少种定义在上的不同的对称关系？（5）共有多少种定义在上的不同的反对称关系？解：设，于是(1) 共有种定义在上的不同的二元关系；(2) 共有种定义在上的不同的自反关系；(3) 共有种定义在上的不同的反自反关系；(4) 共有 种定义在上的不同的对称关系；(5) 共有种定义在上的不同的反对称关系，其中，。4. 请分别描述自反关系，反自反关系，对称关系和反对称关系的关系矩阵以及关系图的特征.解：(1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。(2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈。(3) 对称关系矩阵为对称矩阵; 而关系图中任何

3、两个结点之间的有向弧是成对出现的, 方向相反。(4) 反对称关系矩阵的元素满足：当时，。5设，试求及.解： 。6. 试举出使成立的二元关系的实例. 解：设,于是, 有, 因此, 从而, 。又，因此，从而, 。7. 设和是集合上的二元关系. 下面的说法正确吗?请说出理由. （1）若和是自反的，则也是自反的；（2）若和是反自反的，则也是反自反的；（3）若和是对称的，则也是对称的；（4）若和是反对称的，则也是反对称的；（5）若和是传递的，则也是传递的解：(1) 正确。因为对任意，有，所以。故是自反的。(2) 错误。例如，设，且，于是。故不是自反的。(3) 错误。例如，设对称关系。于是，但。故不是对称

4、的。(4) 错误。例如，设反对称关系。于是，。故不是反对称的。(5) 错误。例如，设传递关系。于是， ，但因为，所以，。8设和是集合上的二元关系，试证明：（1）；（2）；（3）并举出使时使的实例. 解：(1) (2) (3) 由定义， 于是，。 下证对任意，有。任取，不妨设。于是，存在 使得从而， 。举例说明“”成立。设，于是，。9设和是集合上的二元关系，试证明：（1）；（2）；（3）并请给出时使和的实例. 解：设是集合上的二元关系。注意到，于是，(1) = = = =(2) , ,。任取，(i) 若 则 且 从而， ；(ii) 若 则 即 从而， 且 于是， 故 。举例说明“”成立。设，于是

5、，而，因此，。（3）证明：因为又设 A= 1, 2, 3 , ，于是， 而，故 .10有人说，“如果集合上的二元关系是对称和传递的，则必是自反的. 因此，等价关系定义中的自反性可以去掉”. 并给出如下证明，如果，由的对称性有，再由的传递性知，且，即是自反的. 你的看法如何?解：说法不正确。 对任意, 对称性并不要求一定有， 因此也就不一定有<y, x>。于是 <x , x>R。11设是集合上的自反关系. 试证明是等价关系当且仅当若，则. 解：设R是等价关系。若 <x, y>, <x, z>R , 则由R的对称性知, <y, x>R。再

6、由R的传递性有<y, z>R。反之, 假设只要<x, y>, <x, z>R, 就有<y, z>R。(1) 对称性。 设< x, y >R，由自反性有<x, x>R。于是<y, x>R。(2) 传递性。 设<x, y>, <y, z>R。 由对称性有<y, x>R, 再由假设有<x, z>R。12设和都是集合上的等价关系，试证明当且仅当. 证明：设 , 则显然 。反之, 设。若 , 则不妨设<x , y> 但<x , y> .于是 , .由

7、划分之定义得知 , 矛盾.。故。13设是定义在整数集Z上的模5同余关系，求Z/R. 解：设 R= <y , x>| xy(mod 5).于是0 =-15,-10,-5,0,5,10,151 =-14,-9,-4,1,6,11,16,2 =-13,-8,-3,2,7,12,17,3 =-12,-7,-2,3,8,13,18,4 =-11,-6,-1,4,9,14,19,A/R = 0 ,1 ,2 ,3 ,4 .14设和是集合的两个划分，令试证明也是的一个划分. 证明: .(1) 由S 定义知, ;(2) 任取和, 1<=i ,j<=r, 1<=j,m<=s .

8、 (3) 故 S 是的一个划分.15定义在4个元素的集合之上的等价关系共有多少个？若呢？解：设A=1,2,3,4,则A上的等价关系数目即A上的划分的数目共有15个.(1) 最大划分 1, 2, 3 ,4 (2) 最小划分 1 ,2, 3 ,4(3) 将A分成两个集合S=, , 共有两种可能：(i) | = | ，共有种, 即1, 2 , 3, 4, 1, 3, 2, 4, 1, 4, 2, 3。(ii) | = 1, | =3, 共种, 即1, 2,3,4, 2, 1,3,4, 3, 1,2,4, 4,1,2,3(4) 将A分成三个集合, 则恰有一个集合为2个元素,故共有种分法，即1, 2,

9、3, 4, 1, 3, 2 ,4, 1, 4, 2 ,3, 2, 3, 1, 4, 2,4, 1, 3, 3,4, 1, 2设 表示可k元集合A上的全部等价关系数目, 则16设，偏序关系为整除. 试分别画出，以及的Hasse图. 12解： 15 54 6 3 5 2 3 27 9 1 3 <A1,> <A2, > <A3, >x1x2x3x4x5图2.317设的Hasse图如图2. 3所示：（1）求的最大（小）元，极大（小）元；（2）分别求和的上（下）界，上（下）确界. 解：(1) 最大元x1, 无最小元;(2) 上界 下界 上确界 下确界x2, x3, x

10、4 x1 x4 x1 x4x3, x4, x5 x1,x3 无 x3 无x1, x2, x3 x1 x4 x1 x418请分别举出满足下列条件的偏序集的实例：（1）为全序集，但的某些非空子集无最小元；（2）不是全序集，的某些非空子集无最大元；（3）的某些非空子集有下确界，但该子集无最小元；（4）的某些非空子集有上界，但该子集无上确界解：(1) <Z ,> 为全序集, Z 整数集,但<,>无最小元 , 其中=;(2)题16中的<A1, >,子集3 ,5无最大元;(3) 题16中的<A2, >,子集2,3,6有下确界但无最小界;(4) 子集a,b,e有上界d, e,但无上确界。19试证明：每一个有限的全序集必是良序集. 证明：设<A, >为全序集, 且|A| = n。任取 ,因B中的任意两个元素x, y均有x<=y或者y<=x。因此, B中必有最小元a.故<A, >为良序集。20设为偏序集. 试证明的每个非空有限子集至少有一个极小元和极大元. 证明：设B是A的