离散数学习题解第二部分(代数系统)

1离散数学习题解第二部分代数系统习题四第四章代数系统1．设I为整数集合。判断下面的二元关系是否是I上的二元运算a）+={（x，y），z|x，y，zI且z=x+y}b）－={（（x，y），z）|x，y，zI且z=x－y}c）×={（（x，y），z）|x，y，zI且z=x×y}d）/={（（x，y），z）|x，y，zI且z=x/y}e）R={（（x，y），z）|x，y，zI且z=xy}f）={（（x，y），z）|x，y，zI且z=yx}g）min={（（x，y），z）|x，y，zI且z=max（x，y）}h）min={（（x，y），z）|x，y，zI且z=min（x，y）}i）GCD={（（x，y），z）|x，y，zI且z=GCD（x，y）}j）LCM={（（x，y），z）|x，y，z∈I且z=LCM（x，y）}[解]a）是。由于两个整数之和仍为整数，且结果唯一，故知+：I2→I是I上的一个二元运算。b）是。由于两个整数之差仍为整数，且结果唯一，故知一：I2→I是I上的一个二元运算。c）是。由于两个整数这积仍为整数，且结果唯一，故知x：I2→I是I上的一个二元运算。d）不是：例如若x=5，y=6，则z=x/y=5/6I；当y=0时z=x|y=x/0无定义。e）不是。例如若x=2，y=-2，则z=xy=2–2=221=I41；若x=y=0，则z=xy=0，则z=I2x；g）是。由于两个整数中最大者仍为整数，且结果唯一。故知max：I2→I是I上的一个二元运算。2h）是。由于两个整数中最小者仍为整数，且结果唯一。故知min：I2→I是I上的一个二元运算。i）是。由于两个整数的最大公约数仍为整数，且结果唯一。故知GCD：I2→I是I上的一个二元运算。j）是。由于两个整数的最小公倍数仍为整数，且结果唯一。故知LCD：I2→I是I上的一个二元运算。注：两个整数a和b的最大公约数GCD（a，b）定义为同时除尽a和b的正整数中最大的一个；两个数a数b的最小公倍数LCM（a，b）定义为同时是a和b的正倍数中最小的一个。2．设X={x|x=2n，n∈N}问普通数的加法是否是X上的二元运算？普通数的乘法呢？[答]普通的加法运算不是X是X上的二元运算，因为存在着x1=2∈X，x2=22∈X，使x1+x2=2+22=6X。普通的乘法运算是X上的二元运算，因为对于任意的x1=1n2X，x2=2n2X，这里n1，n2N，都有x1·x2=1n2·2n2=21nn2X（因为n1+n2∈N）。3．设X，*是代数系统，*是X上的二元运算，若有元素el∈X，使Xx，有el*x=x，则称el是关于*的左幺元。若有元素erX，使Xx，有x*el=x，则称er是关于*的右幺元。a)试举出公含有左幺的代数系统的例子。b)试举出仅含有左幺的代数系统的例子。c)证明：在代数系统中，若关于*有左幺元和右幺元，则左幺元等于右幺元。[解]：a)构造代数系统X，如下：令X={a，b，c，d}，*：X×→X→X，其运算表如下：*abcdadabcbabcdcabccdabcd则此代数系统含有左幺元b，d，但不含右幺元。b)构造代数系统X，*如下：3令X={1，2，3，4}*：X×→X→X，其运算表如下：*123411243221343341244423则此代数系统含有右幺元1，但不含左幺元。c)[证]因为代数系统X，*关于*运算存在着左、右幺元，ei，er∈X则el=el*er=er∈4．设X，*是代数系统，*是X上的二元运算。若有元素Ol∈X，使x∈X，有Ol*x=Ol是关于*的左零元。若有元素Or∈X，使x∈X，有x*Or=Or，则称Or是关于*的右零元。a)试举出公含有左零元的代数系统的例子。b)试举出仅含有左零元的代数系统的例子。c)证明：在代数系统中，若关于*有左零元和右右零元，则左零元等于右零元。[解]a)构造代数系统X，*如下：令X={a，b，c}，*：X×X→X，其运算表如下：*abcaaaabbbbcbca则a和b都是左零元，但没有右零元。b)构造代数系统X，*如下：令X={1，2，3}，*：X×→X→X，其运算表如下：*1234123323133123则3是右零元，但没有左零元。c)[证]因为代数系统X，*关于*运算存在着左、右零元，Ol，Or∈X，则Ol=Ol*Or=Or5．当给出一个代数系统的二元运算表时，如何从表上判断这个二元运算是否满足结合律，是否满足交换律，是否有幺元，是否有零元，每个元素是否有逆元。[答]在一个代数系统X，*中，1）运算*满足结合律，当且仅当在运算表中，对任何x，y∈X，x行每个元素与y的*积对应的等于x与y列每个元素的*积。2）运算*满足交换律，当且仅当运算表关于主对角线是对称的。3）运算*有幺元，当且仅当存在一元素，它所对应的行和列依次与运算表的行和列相一致。4）运算*有零元，当且仅存在一元素，它所对应的行和列中每个元素都是蛇自己。5）若运算*有幺元，X中每个元素x有逆元，当且仅当存在一元素y∈Y，使得x所在行，y所在列的想元素以及y所在行，x所在列的元素都是幺元。6．设X，*是代数系统，*是X上的二元运算，e是关于*的幺元。对于X中的元素x，若存在y∈X，使得y*x=e，则称y是x的左逆元。若存在z∈X，使得x*z=e，则称z是x的右逆元。指出下表中各元素的左、右逆元的情况。*abcdeaabcdebbdacdccababddacdceedace5[解]a是幺元；b的左逆元和右逆元都是c；即b和c互为逆元；d的左逆元是c而左逆元是b；b有两个左逆元c和d；e的右逆元是c，但e没有左逆元；c有两个左逆元b和e有两个右逆元b，d。7．设X，*是代数系统，*是X上的二元运算。x，y∈X，有x*y=x。问*是否满足结合律，是否满足交换律，是否有幺元，是否有零元，每个元素是否有逆元。[解]a)*运算满足结合律因为对任何x，y，z∈X，都有x*（y*z）=x*y=x=x*y=（x*y）*zb)*运算不满足交换律因为对于二个元素x，y∈X，有x*y=x，而y*x=y。所以当X包含多于一个元素时，能使x≠y，从而x*y≠y*x。c)没有幺元因为若有幺元e∈X存在，则对任何x∈X，应有e*x*e，但是e*x=e，x*e=x，于是推得x=e，当X中包含多于一个元素时，就会有x≠e，矛盾。d)没有零元，仿c)保证。e)对于每个元素都没有逆元。因为没有幺元存在。并且若存在一个元素a∈X，使得对每个元素x∈X，都有一个元素y∈X，使y*x=x*y=a，则有y=x=a，当X中包含多一个元素时，这将不总是成立的（只在x=a，且a具有幂等性时才成立）8．设N，*是代数系统，*是N上的二元运算，x，y∈N，x*y=LCM（x，y）。问*是否满足结合律，是否满足交换律，是否有幺元，是否有零元，每个元素是否有逆元。[解]a)*运算满足结合律因为，对于任何x，y，z∈N，（x*y）*z=LCM(（x*y），z)=LCM(LCM（x，y），z)=LCM(（x，y，z）=LCM(（x，（y*z）=LCM(（x*y），z)=x*(y*z)注：关于LCM（LCM（x，y），z）=LCM（x，y，z）我们可证明如下：设C1=LCM（x，y，z），d=LCM（x，y），从而C1=LCM（d，z），C2=LCM（x，y，z），因此只需证C1=C2即可，为此6由于C2=LCM（x，y，z），故此x|C2，y|C2，z|C2，因此由d=LCM（x，y）及x|C2，y|C2，从d2的最小性有d≤C2于是d|C2（否则C2=kd+r，0＜r＜d，由于x|d，y|d及x|C2，y|C2，故有x|r，y|r，这与d=LCM（x，y）的最小性矛盾）。即d|C2且z|C2故此由C1=LCM（d，z）的最小性，可知C1≤C2。另一方面，由C1=LCM（d，z）知d|C1，z|C1，又由d=LCM（x，y）知x|d，y|d，y|d，因此有x|C1，y|C1，并且z|C1。因而C2=LCM（x，y，z）的最小性可知C2≤C1。所以，C1=C2。同理可证LCM（x，LCM（y，z））=LCM（x，y，z）。b)*运算满足交换律因为对于任何x，y∈N，x*y=LCM（x，y）=LCM（y，x）=y*x（c）*运算有幺元1∈N。因为，对于任何x∈N，x*1=LCM（x，1）=x=LCM（1，x）=1*x（d）*运算没有零元。因为0N。（e）对于每个元素x∈X，若x≠1，则对每个元素y∈N，都有x*y=y*x=LCM（x，y）≥x≠1，故此没有逆元素。9．设X，*是代数系统，*是X上的二元运算。X是X中的任一元素，若有x*x=x，则称x是幂等元．．．。若*是可结合的，且x，yX，当x*y=y*x时，有x=y。证明：X中每个元素都是幂等元。[证]对于任何x∈X，令xi=x*x，xj=x，于是xi*xj=（x*x）*x=x*（x*x）（结合律）=xj*xi从而由所给性质，有xi=xj，即x*x=x。因此，由x的任意性，可知X中每个元素都是幂等元。10．设X，，是代数系统，和分别是X上的两上二元运算。若x∈X，7有xy=x。证明关于是可分配的。[证]对于任何x，y，z∈Xx（yz）=xy=（xy）（yz）（yz）x=yx=（yx）（zx）因此代数系统X，，中关于是可分配的。11．设X，，是代数系统，和分别是X上的两上二元运算。e1和e2分别是关于和的幺元，且对于满足分配律，对于满足分配律。证明：x∈X，有xx=x，xx=x[证]x=xe2（e2为的幺元）=x（e2e1）（e1为幺元）=x[e2（e1e2）]（e2为幺元）=x[（e2e1）（e2e2）]（对的分配律）=x[（e2（e2e2））（e1为幺元）=x（e2e2）（e2为幺元）=（xe2）（xe2）（对分配律）=xx（e2为幺元）x=xe1（e1为的幺元）=x（e1e2）（e2为幺元）=x[e1（e1e2）]（e2为幺元）=x[（e1e1）（e1e2）]（对的分配律）=x[（e1e1）e1]（e2为幺元）=x（e1e1）（e1为幺元）=（xe1）（xe1）（对分配律）=xx（e1为幺元）12．设X={a，b，c，d}，和分别是X上的两个二元运算，其运算表如下：算表如下：AbcdaAaaabAbabcAaccdAbcdabcdaabcDbbbdDccdcDddddD8取S1={b，d}，S2{a，d}，S3={b，c}，问S1，，，S2，，，S3，，，分别是X，，的子代数系统吗？为什么？[解]13．设X，**是X上的二元运算。若a，b，c∈X，有a*a=a且（a*b）*（c*d）=（a*c）*（b*d）证明：a*（b*c）=（a*b）*（a*c）[证]对任何a，b，c∈X，a*（b*c）=（a*a）*（b*c）（幂等性a*a=a）=(（a*b）*（a*c）=（（a*b）*（c*d））=（a*c）*（b*d）利用)14．设X，*是代数系统，*是X上的二元运算，R是X上的等价关系。若a，b，c，d∈X当（a，b）∈R且（c，d）∈R时，有（a*c，b*d）∈R，则称R是X上关于*的同余关系，称R产生的等价类是关于*的同余类。考察代数系统I，+，I是整数集合，十是整数加法。问以下的元关系是Ibcbbacaccaadabbcbbdcdccaadababaaababcaadab因此S3，，是X，，的子代数。因，在S3={b，d}内封闭。bdbbdddd因此S2，，是X，，的子代数。因，在S2={b，d}内封闭。bdbbddddbdbbbdbd9上的关于十的同余关系吗