离散数学习题答案-2015(4)

小整数m和n(m < n)

16

答：R = R；简要说明如下：本关系图分为两个部分，R = R1 ∪ R2,因为 R1。R2 = R2。

222nnn35

R1 = ?, 所以R = R1 ∪ R2 ,同理R = R1 ∪ R2 ,又因为 I1 = R1,I2=R2 ；3，5

15 151516

的最小公倍数为15，所以I = R,所以R = I o R = R o R = R

13、设R是集合A上的二元关系，证明：

n

（1）IA = IA

证明：因为单位关系的关系矩阵为单位矩阵，而复合运算就是矩阵的乘法，根据单位矩阵的

n

性质，IA = IA

（2）IA o R=R oIA =R

证明：同上，因为单位矩阵左乘、右乘一个矩阵，结果不变；所以IA o R=R oIA =R

n23n

（3）(R∪IA)=IA∪R∪R∪R?∪R

证明：根据书中并集关系复合的定理（4.2），展开，并利用上述1，2的结论，及可得证（严格可用归纳法）

15、写出第12题中关系图对应的关系矩阵，并利用warshall算法求这个关系的传递闭包 解：

?0??0?1??0MR???0?0??0?0?

100001000000000100000000000 0100000010000000001000??0?0??0??0?0??1?0??Mt(R)?1??1?1??0???0?0??0?0?111011100001000100010001001111001111 0011110011110??0?0??1??1?1??1?1??

习题五

1、设 A = {(a,b)| a,b ? N}，定义A上的一个二元关系 R = {((a,b),(c,d)) | ad = bc } 证明：R 是 A 上的等价关系

证明：

（自反性）因为 对任意（a,b）? A, 都有：ab = ba, 既(（a,b）,(a,b)) ? R，所以R是自反的

（对称性）如果（（a,b）,(c,d)）? R ,那么ad = bc, 所以 cb = ad,既（（c,d）,(a,b)）?R, 所以R是对称的 （传递性）如果（（a,b）,(c,d)）? R, ((c,d),(e,f)) ? R, 那么 ad = bc ,cf = ed ,因此，adcf = bced (注：如果 0 ? N 中)， 那么af = eb, 所以（（a,b）,(e,f)）? R,R具有传递性

综上所证，R是A上的等价关系

3、集合 A = {1，2，3，4}的一个分化为 S0={{1,2,4},{3}},求由S0导出的A上的一个等价关系R

解：等价关系R = {1，2，4}×{1，2，4}∪{3}×{3} = {（1，1），（2，2），（4，4），（1，2），（1，4），（2，1），（2，4），（4，1）,(4,2),(3,3)}

4、试确定在4个元素的集合上可以定义的等价关系数目 解：

在此集合上可以确定的4分划个数为：1

在此集合上可以确定的3分划个数为：c(4,2) = 6

在此集合上可以确定的2分划个数为：c(4,1) + c(4,2) /2 = 7 在此集合上可以确定的1分划个数为：c(4,4) = 1

所以共可定义15个等价关系

6、设R是非空集合A上的一个二元关系，具有对称性和传递性。证明：如果对每一个x?A，存在y?A使xRy，那么，R是A上的等价关系

证明：因为对每一个x?A，存在y?A使xRy，由于R是对称的，所以yRx；又因为R是传递的，当xRy 并且 yRx，那么xRx。所以R是自反的。综上所述，R是自反的，对称的和传递的，因此R是A上的等价关系

8、设A是由54的正因子构成的集合，“|”表示整除。画出偏序集对应的Hasse图

解：先求出偏序集，然后求处相应的cover，然后画出Hasse图 A={1，2，3，6，9，18，27，54}

COVER(|)={(1,2), (1,3), (2,6), (3,6), (3,9),(6,18), (9,18), (9,27), (18,54), (27,54)}

最大元：54 最小元：1

有4个包含元素最多的全序子集: L1={54,27,9,3,1} L1={54,18,9,3,1} L1={54,18,6,3,1} L1={54,18,6,2,1}

54 18 6 2 1

3 9 27

9、设A={a,b,c},画出偏序集合对应的Hasse图。试比较本题与上题Hasse图的异同 解：

{a,b,c} {a,b} {a} {a,c} {b} ?

{b,c} {c}

两图的相同点 ： 都有最大（小）元 不同点：最大线序一个为5，一个为4

11、设R是集合A上的一个等价关系。现在在等价类之间定义一个新关系S使得R的任何等价类[a]和[b]满足[a]S[b] ?aRb，判别S是一个什么关系

解:根据题目信息，猜测是等价关系，说明如下：

（1） 因为对任意的a?A，aRa成立（R是A上的等价关系，是自反的），所以[a] S [a],S

是自反的

（2） 假设[a] S [b]成立，那么aRb；因为R是对称的，所以bRa,因此[b] S [a]成立，

所以S是对称的

（3） 假设[a]S[b],[b]S[c]成立，则aRb,bRc，因为R是传递的，所以aRc成立，因此[a]S[c]

成立，所以S是传递的

综上所述，S是等价类集合上的等价关系

习题六

1、设A={1，2，3，4}，B=A×A,确定下述集合是否为A到B的全函数或部分函数

（1）{（1，（2，3）），（2，（2，2）），（3，（1，3）），（4，（4，3））} 答：根据本书全函数的定义，这是从A到B的全函数 （2）{（1，（1，2）），（1，（2，3）），（3，（2，4））}}

答：根据本书函数的定义，每个原像只能有一个像，所以此定义不是A到B的函数 （3）{（1，（3，3）），（2，（3，3）），（3，（2，1）），（4，（4，1））} 答：根据本书全函数的定义，这是从A到B的全函数

2、判别以下关系中哪些是全函数

（1）{（n1,n2）|n1,n2 ?N,0<2n1-n2<5}

答：此关系不满足全函数的定义，因为（3，5），（3，4），（3，3），（3，2），（3，1）都属于此关系，但它违反了本书函数是单值的定义

（2）{（n1,n2）|n1,n2 ?N,n1是n2的正因子个数}

答：如果N集合中不包含0，那么此关系是全函数，因为任意一个自然数按正因子个数的定义，都有确切的值，因此是全函数

（3）{（S1,S2）|S1,S2 ?{a,b,c,d} 且S1∩S2=?}

答：此关系不满足全函数的定义，因为（?，{a}）,( ?,{b})等属于此关系，但它违反了本书函数是单值的定义

（4）{（a,b）|a,b ? N,gcd(a,b)=3}

答：此关系不满足全函数的定义，因为就1，2而言，3不是他们的因数；同时推论开，所有不是3的质数，3都不是他们的因数，因此他们就没有像，所以不是全函数

2

（5）{（x,y）|x,y ? Z,y=x}

答：此关系是全函数，因为任意一个整数，都能求到唯一的平方数。所以按定义是全函数

7、确定下列映射是否单射、满射或双射：

（1） f1: N→R,f1(n)=lnn

答：如果0不属于N,那么这是一个单射函数，因为任意一个自然数都可以求其自然对数，同时ln是单调函数，所以是单射函数。但是并非任意一个实数其原像都是自然数，所以不是满射

（2） f2:N→N,f2(n)为不超过n的素数数目

答：这是一个满射函数，但不是单射。因为f(3)=f(4)=3,及不超过3，4的素数都是1，2，3，个数为3；同时因为自然数中的素数有无穷多，所以对任意一个自然数m，都能找到从第m个素数起到第m+1个素数（但不包括第m+1个素数）的所有自然数，其函数值都等于m，所以是满射，但不是单射（注：7是第5个素数，11是第6个素数，所以f(7)=f(8)=f(9)=f(10)=5）

n2

（3） f3:N×N→N,f3(n1,n2)=(n1+1)

答：这既不是单射，也不是满射（与0是否属于N无关，以下说明以0不属于N而言）；因为任意两个自然数，都能求到此函数值，所以是全函数。因为f(1,2)=f(3,1)=4,所以不是

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学习题答案-2015(4)在线全文阅读。