哈工大《离散数学》教科书习题答案

因此共有n!种排列

对每个n-循环置换,均有n种排列,因此

n!n-循环置换的个数为?(n?1)!个

nP70习题

3. 找一个既不满足交换律又不满足结合律的二元运算

解:n维向量空间中向量的叉积运算。 4. 给出一个三元运算的例子

解:求三个正整数的最大公因数。

5. 设A?{a,b,c,d},A上的代数运算“?”如表所示。代数运算“?”是否满足交换律?结合律?“?”有单位元吗?

解:不满足交换律,因为运算表不对称。d?c?a,c?d?d,d?c?c?d。也不

(b?b)?c?a?c?c满足结合律,b?(b?c)?b?a?b

(b?b)?c?b?(b?c)单位为a o a b c d a a b c d b b a a c c c a b a d d c d b 6.设N?{1,2,3,?},?m,n?N,m?n?nlog10m。

那么“?”是N上的代数运算吗?为什么? 解:当m=1时,log10m?0,nlog10m?0,0?N

因此“?”不是N上的代数运算。

7. 设“?”是X上的代数运算,则应该怎样定义“?”的逆运算?回忆一下,逆运算通常比原运算“难算”,这是为什么?例如,积分比微分难,减法比加法难,除法比乘法难,开方比幂方运算难。

解:“?”的逆运算可以这样定义:一个从X到X?X?X???X?Xn的映射 “?”称为X上的n元运算的逆运算

“?”的逆运算的象集所在的集合X?X?X???X的元素的个数是X的元素个数的mn?1倍(设X?m),因而逆运算的个数很多,因此得到其中的一种就较困难,故逆运算较难算。

29

第三章 关 系

P86习题

1.给出一个既不是自反的又不是反自反的二元关系?

解:设X?(a,b,c),R是X上的一个二元关系且R?{(a,a),(a,b)}即可。 2.是否存在一个同时不满足自反性,对称性,反对称性,传递性和反自反性的二元关系?

解:存在。

设X?{a,b,c},R是X上的二元关系R?{(a,a),(a,c),(a,b),(c,a)}。 3.设R,S是X上的二元关系,下列命题哪些成立:

a)若R与S是自反的,则R?S,R?S分别也是自反的。 b) 若R与S是对称的,则R?S,R?S分别对称的 c) 若R与S是传递的,则R?S也是传递的 d) 若R与S不是自反的,则R?S也不是自反的 e) 若R与S是反自反的,则R?S,R?S也是反自反的 f) 若R是自反的,则Rc也是反自反的。

g) 若R与S是传递的,则R\\S是传递的 答案:真真真假真真假

4.实数集合上的“小于”关系?是否市反自反的?集合X的幂集上的“真包含”关系?是否是反自反的?为什么?

证:实数集合上的“小于”关系?是反自反的;

集合X的幂集上的“真包含”关系?也是反自反的。

5.设R、S是X上的二元关系。证明:

(1)(R?1)?1?R;(2)(R?S)?1?R?1?S?1

(3)(R?S)?1?R?1?S?1;(4)若R?S,则R?1?S?1

证:(1)?(x,y)?(R?1)?1,则(y,x)?R?1,即(x,y)?R,因此(R?1)?1?R。 反之,?(x,y)?R,则(y,x)?R?1,即(x,y)?(R?1)?1,因此R?(R?1)?1。 从而(R?1)?1?R

(2)?(x,y)?(R?S)?1,则(y,x)?R?S,

30

即(y,x)?R或(y,x)?S。于是(x,y)?R?1或(x,y)?S?1, 即(x,y)?R?1?S?1,因而(R?S)?1?R?1?S?1。 反之,?(x,y)?R?1?S?1,则(x,y)?R?1或(x,y)?R?1。 于是(y,x)?R或(y,x)?S,即(y,x)?R?S。 从而(x,y)?(R?S)?1,因此,R?1?S?1?(R?S)?1。 故(R?S)?1?R?1?S?1

(3)?(x,y)?(R?S)?1,则(y,x)?R?S。于是(y,x)?R且(y,x)?S, 从而(x,y)?R?1且(x,y)?S?1,即(x,y)?R?1?S?1 因此(R?S)?1?R?1?S?1

反之,设(x,y)?R?1?S?1,则(x,y)?R?1且(x,y)?S?1 于是(y,x)?R且(y,x)?S,即(y,x)?R?S。 从而(x,y)?(R?S)?1,因此R?1?S?1?(R?S)?1 故R?1?S?1?(R?S)?1

(4)?(x,y)?R?1,则(y,x)?R

因为R?S,所以(y,x)?S,于是(x,y)?S?1 因而R?1?S?1

6.设R是X上的二元关系,证明:R?R?1是对称的二元关系。

证1:(R?R?1)?1?R?1?(R?1)?1,故R?R?1是对称的。

证2:则(x,y)?R或(x,y)?R?1,即(y,x)?R?1或(y,x)?R。 ?(x,y)?R?R?1,于是(y,x)?R?R?1,因此R?R?1是对称的。

9.有人说:“若R是X上的二元关系,只要R是对称的和传递的,则R必是自反的。”他的证明如下:若xRy,则由R的对称性便知有yRx。于是由xRy和yRx以及R的传递性即得xRx。所以,R是自反的。他的推论错在什么地方?这个结论是否对呢?

31

解:若R??,则R是对称的,传递的,反自反的。

若R??,只有?x?X使得xRx,才能说R是自反的。此人只是说明了X中的部分元素满足了xRx,因而是错误的。

所以这个结论不对。

P92习题

1.“父子“关系的平方是什么关系?

解:“父子“关系的平方是”祖孙“关系

2.设X={1,2,3,4},R={(1,2),(2,2),(3,4)},S={(2,3),(3,1),(4,2)}

试求:R?S,S?R,R2,S2,R?(S?R),(R?S)?R。 解:

R?S?{(1,3),(2,3),(3,2)}S?R?{(2,4),(3,2),(4,2)} R?{(1,2),(2,2)} S2?{(2,1),(4,3)}2

R?(S?R)?R?{((2,4),(3,2),(4,2)} ?{(1,4),(2,4),(3,2)}(R?S)?R={(1,3),(2,3),(3,2)}?R ={(1,4),(2,4),(3,2)}

3.设R与S为X上的任两个集合,下列命题哪些为真?

a)若R,S都是自反的,则R?S也是自反的。 b)若R,S都是对称的,则R?S也是对称的。 c)若R,S都是反自反的,则R?S也是反自反的。 d)若R,S都是反对称的,则R?S也是反对称的。 e)若R,S都是传递的,则R?S也是传递的。 答案:真假假假假

4.设R1是A到B,R2和R3是B到C的二元关系,则一般情况下

R1?(R2\\R3)?(R1?R2)\\(R1?R3)。但有人声称等号成立,他的证明如下:设则?b?X,使得(a,b)?R1且(b,c)?R2\\R3。于是(b,c)?R2且(a,c)?R1?(R2\\R3),

(b,c)?R3。从而(a,c)?R1?R2且(b,c)?R1?R3,所以(a,c)?(R1?R2)\\(R1?R3),即R1?(R2\\R3)?(R1?R2)\\(R1?R3)。同理可证相反的包含关系成立,故等式成立,这个证明错在什么地方?

解:由(a,c)?R1,(b,c)?R2且(b,c)?R3,只能得到(a,b)?R1?R2。但(a,c)?R1?R3不一定成立。

例如(a,a)?R1,(a,c)?R3时,(a,c)?(R1?R3)

32

联系客服:779662525#qq.com(#替换为@)