离散数学第二版邓辉文编著第一章第二节习题答案 下载本文

已知条件有a1?a2且c1?c2,进而(a1,c1)?(a2,c2),因此h是单射.

任意(b,d)?B?D,则b?B,d?D,由于f是A到B的双射且g是C到D的双射,于是存在a?A,c?C使得f(a)?b,g(c)?d,因此

h(a,c)?(f(a),g(c))?(b,d),所以h是满射.

故h是双射.

13.设f:A?B,g:B?C,h:C?A,若f?g?h?IA,g?h?f?IB,

h?f?g?IC,则f,g,h均可逆,并求出f?1,g?1,h?1.

证 因为恒等映射是双射,多次使用定理6即可得结论.

由于f?g?h?IA,所以f是单射且h是满射. 由于g?h?f?IB,所以g是单射且f是满射. 由于h?f?g?IC,所以h是单射且g是满射. 于是f,g,h是双射,因此f,g,h均可逆.

由于f?g?h?IA,所以f?1?g?h且h?1?f?g,进而g?1?h?f.

14.已知Ackermann函数A:N?N?N的定义为 (1)A(0,n)?n?1,n?0; (2)A(m,0)?A(m?1,1),m?0;

(3)A(m,n)?A(m?1,A(m,n?1)),m?0,n?0. 分别计算A(2,3)和A(3,2).

解 由已知条件有A(0,1)?2,A(1,0)?A(0,1)?2,于是

A(1,1)?A(0,A(1,0))?A(0,2)?2?1?3, A(1,2)?A(0,A(1,1))?A(0,3)?3?1?4,

由此可进一步得出

A(1,n)?n?2, A(2,0)?A(1,1)?3,

A(2,1)?A(1,A(2,0))?A(1,3)?3?2?5,

A(2,2)?A(1,A(2,1))?A(1,5)?5?2?7, A(2,3)?A(1,A(2,2))?A(1,7)?7?2?9.

因此有

A(2,n)?2n?3,

A(3,0)?A(2,1)?2?1?3?5,

A(3,1)?A(2,A(3,0))?A(2,5)?2?5?3?13, A(3,2)?A(2,A(2,2))?A(2,13)?2?13?3?29.

所以有A(2,3)?9,A(3,2)?29.