《离散数学第二版答案(6-7章)》由会员分享，可在线阅读，更多相关《离散数学第二版答案(6-7章)（45页珍藏版）》请在金锄头文库上搜索。
1、第六章 代数系统6.1第129页1证明：任取，因此，二元运算*是可交换的；任取，因此，运算*是可结合的。该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。2证明：任取，由知，*运算不是可交换的。任取，由，知，*运算是可结合的。任取，可知N中的所有元素都是等幂的。*运算有右么元，任取，知N中的所有元素都是右么元。*运算没有左么元。证明：采用反证法。假定为*运算的左么元，取，由*的运算公式知，由么元的性质知，得，这与相矛盾，因此，*运算没有左么元。3解： 任取因此对于任意的都有，即二元运算*是可交换的。 任取因此对于任意的，都有，即二元运算*是可结合的。 设幺元为，则，即幺元为1.
2、对于所有的元素，都有，所以所有元素都是等幂的。4解：设 设是上的二元运算，则是一个从的映射。求上有多少个二元运算即相当于求这样的映射的个数。由于，映射的个数为，即上有个二元运算。 可交换即设集合，要求上可交换的二元运算的个数，即相当于求映射的个数，其中：具体如下图所示： 此时映射的个数推广到有个元素时，映射的个数 单位元素即幺元，若存在必唯一。设集合，若幺元为1，则有 此时的二元运算的个数相当于求映射的个数，其中： 映射的个数为幺元为2，3，4时同理，因此集合上有个有单位元素的二元运算。推广到有个元素时，具有单位元素的二元运算的个数为。5解：任取 对于任意的都有，故二元运算*是可交换的。若，此
3、时故二元运算*是不可结合的。不存在这样使得任意的都有，因此，二元运算*不含幺元。对于任意的都有，故二元运算*是可交换的。故二元运算*是不可结合的。不存在这样使得任意的都有，因此，二元运算*不含幺元。 因此，二元运算*是不可交换的。故二元运算*是不可结合的。由于二元运算*不是可交换的，所以不存在这样使得任意的都有，因此，二元运算*不含幺元。6设是中的任意元素。由于二元运算*是可结合的，故又对于任意的，若，则故即对于中的任意元素，都有，所以中的 每一个元素都是等幂的。6.2第137页4证明：首先，U和V都只含有一个二元运算，因此是同类型的；第二，的定义域是自然数集合，值域是，是V定义域的子集。第三
4、，验证是否运算的像等于像的运算。任取，分情况讨论：（1） x和y都可以表示成，设，那么，（2） x和y都不能表示成，那么也不能表示成,（3） x可以表示成，y不能表示成，那么也不能表示成,（4） x不可以表示成，y能表示成，那么也不能表示成,可知，无论x和y如何取值，都能够保证。综上所述，是U到V的同态映射。5证明：设，首先，U和V都仅有一个二元运算，因此U和V是同类型的；第二，U和V的定义域大小相同，具备构成双射函数的条件；第三，寻找特异元素，U中么元是a，右零元是c，三个元素都是等幂元；V中么元是3，右零元是1，三个元素都是等幂元。第四，在U和V的定义域之间构造双射函数，使得。把*运算表中
5、的元素都用f下的像点代替，得321321321222111调整表头的顺序为1，2，3，转变为下表123123111222123跟V中运算表完全相同，因此代数系统和是同构的。6.证明：(1) 两个代数系统都只存在一个二元运算，故满足同型。(2) 构造函数，使得fX=X，显然是双射函数。(3) 对于任意的 fXY=XY=XY fXfY=XY故 fXY=fXfY，所以满足运算的像=像的运算。由(1),(2),(3)可知，两代数系统是同构的。7.解：当时，零同态；当时，恒等映射，自同态；当时，；当时，；当时，；当时，自同构。8.证明：的个复数根可表示成：(1) 与都含有一个二元运算，故为同型的。(2)
6、 与定义域大小相同，具备构成双射函数的条件。(3) 构造双射函数对于任意的，因此，。由(1),(2),(3)可知，同构于。9证明：(1) 是代数系统到当的同态映射 又是的子代数(2) 对于，必存在，使得，由于为代数系统到当的同态映射，又是的子代数故对*运算封闭，即对运算满足封闭性。由(1),(2),(3)可知, 为的子代数。6.3第141页1解：解：首先，判断是否是等价关系。任取，由于，因此，是自反的；任取，若，即（），则，因此是对称的；任取，若，则（），（），于是，因此，可知是可传递的。因此，是等价关系。 其次，判断关于*是否满足代换性质。任取，若，即存在某个，满足则于是由于，因此，关于*是
7、满足代换性质。综上所述，是上的同余关系。2.解：（1）对于+运算，在二元运算下，任取，验证下式是否成立取，可知满足，但，即。可知对于运算+，R不满足代换性质。（2）对于运算，在二元运算下，任取，若，则必然满足于是可得。由取值的任意性可知，对于运算，R满足代换性质。3证明：(1) 对于，有 由于对具有代换性质，所以有 由此可知：同理可知：因是等价关系，故是可传递的，所以有所以对具有代换性质。(2) 对具有代换性质，但对不具有代换性质，因4设代数系统，为同余关系。(1)即证：为同余关系证明：为等价关系若对任意 有, 则， ， ， ， 为同余关系所以为同余关系。 (2) 为等价关系若对任意 有, ,
8、 未必有， ， ， ， 因此，可能不满足代换性质所以未必是同余关系。5（1）解：R不是上的同余关系，取则，但是，因此，不满足代换性质。（2）, 当且仅当解：R不是上的同余关系，取，则，但，R不满足可传递性，不是等价关系。（3）解：R不是上的同余关系，取取则，但是，因此，不满足代换性质。（4）解：R不是上的同余关系，取，则，但，即，R不满足对称性，不是等价关系。6.4第143页1.解：（1）设其中，任取下面通过运算表构造*运算（这里仅给出了一个运算表，另一个照推）（2）设其中，任取运算表的构造方法与上同。2.(1) 证明：任取，和*可交换是可交换的。(2) 任取 和*可结合是可结合的。3.012
9、345001234511234502234501334501244501235501234 证明： 与都只有一个二元运算，故为同型的。 与定义域大小相同，具备构成双射函数的条件。 构造双射函数由上图可知，像的运算=运算的像所以与是同构的。6.5第155页1.（1）半群（2）半群（3）半群（4）独异点，么元0（5）不是半群，取a=b=1,c=2，则不满足结合律（6）不是半群，因为|不是二元运算；（7）半群（8）独异点，么元0（9）半群（10）独异点，么元为恒等关系；（11）独异点，么元为a2.（1）二元运算表如下图所示：GCD12346812241111111112121222223113131
10、33412142444612326266812142848121234641212241234681224（2）, 其中。（假定为丛X到X的双射函数）解：X到X有6个双射函数，分别用表示，设 构造运算表如下：第七章 图论6.1第164页1.画出图的图示，指出其中哪些图是简单图。（1）不是简单图。（2）不是简单图。（3）是简单图。2.写出图7-8的抽象数学定义。（1）解：，其中，（2）解：，其中， ， 3.证明：在n阶简单有向图中，完全有向图的边数最多，其边数为。证明：简单有向图是没有自环，没有平行边的有向图，只要两个不同的结点之间才能有边。完全有向图是每个结点的出度和入度都是n-1的简单有向图，也就是每个结点都有到其他所有结点的边，因此，完全有向图的边数最多。在完全有向图中，所有结点的出度之和为n(n-1)，所有结点的入度之和为n(n-1)，设边的个数为m，由握手定理可知，2m= n(n
