当前位置：文档之家 › 离散数学习题解第二部分(代数系统)

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

  • 格式：doc
  • 大小：593.50 KB
  • 文档页数：49

离散数学习题解 第二部分 代数系统习题四 第四章代数系统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=x y} 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 ）是。

由于两个整数之和仍为整数，且结果唯一，故知+：I 2→I 是I 上的一个二元运算。

b ）是。

由于两个整数之差仍为整数，且结果唯一，故知一：I 2→I 是I 上的一个二元运算。

c ）是。

由于两个整数这积仍为整数，且结果唯一，故知x ：I 2→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=x y=2 –2=221=I 41∉；若x=y=0，则z=x y=0，则z=I 2x ∉=χ；g ）是。

由于两个整数中最大者仍为整数，且结果唯一。

故知max ：I 2→I 是I 上的一个二元运算。

h ）是。

由于两个整数中最小者仍为整数，且结果唯一。

故知min ：I 2→I 是I 上的一个二元运算。

i ）是。

由于两个整数的最大公约数仍为整数，且结果唯一。

故知GCD ：I 2→I 是I 上的一个二元运算。

j ）是。

由于两个整数的最小公倍数仍为整数，且结果唯一。

故知LCD ：I 2→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 上的二元运算，因为存在着x 1=2∈X ，x 2=22∈X ，使x 1+x 2=2+22=6∉X 。

普通的乘法运算是X 上的二元运算，因为对于任意的x 1=1n 2∉X ，x 2=2n 2∉X ，这里n 1，n 2∉N ，都有x 1²x 2=1n 2²2n 2=∈+=21n n 2X （因为n 1+n 2∈N ）。

3．设<X ，* >是代数系统，*是X 上的二元运算，若有元素e l ∈X ，使X x ∈∀，有e l *x=x ，则称e l 是关于*的左幺元。

若有元素e r X ，使X x ∈∀，有x * e l =x ，则称e r 是关于*的右幺元。

a) 试举出公含有左幺的代数系统的例子。

b) 试举出仅含有左幺的代数系统的例子。

c) 证明：在代数系统中，若关于*有左幺元和右幺元，则左幺元等于右幺元。

[解] ：a) 构造代数系统<X ，>如下：令X={a ，b ，c ，d}，*：X ³→X →X ，其运算表如下：则此代数系统含有左幺元b ，d ，但不含右幺元。

b) 构造代数系统<X ，* >如下：令X={1，2，3，4} *：X³→X→X，其运算表如下：则此代数系统含有右幺元1，但不含左幺元。

c) [证] 因为代数系统<X，*>关于*运算存在着左、右幺元，e i，e r∈X 则e l = e l * e r = e r∈4．设<X，*>是代数系统，*是X上的二元运算。

若有元素O l∈X，使∀x∈X，有O l*x=O l 是关于*的左零元。

若有元素O r∈X，使∀x∈X，有x*O r=O r，则称O r是关于*的右零元。

a) 试举出公含有左零元的代数系统的例子。

b) 试举出仅含有左零元的代数系统的例子。

c) 证明：在代数系统中，若关于*有左零元和右右零元，则左零元等于右零元。

[解] a) 构造代数系统<X，*>如下：令X={a，b，c}，*：X³X→X，其运算表如下：则a和b都是左零元，但没有右零元。

b) 构造代数系统<X，*>如下：令X={1，2，3}，*：X³→X→X，其运算表如下：则3是右零元，但没有左零元。

c) [证] 因为代数系统<X，*>关于*运算存在着左、右零元，O l，O r∈X，则O l=O l*O r=O r5．当给出一个代数系统的二元运算表时，如何从表上判断这个二元运算是否满足结合律，是否满足交换律，是否有幺元，是否有零元，每个元素是否有逆元。

[答] 在一个代数系统<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的右逆元。

指出下表中各元素的左、右逆元的情况。

[解] 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即可，为此由于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，y X，当x*y=y*x时，有x=y。

证明：X中每个元素都是幂等元。

[证] 对于任何x∈X，令x i=x*x，x j=x，于是x i*x j=（x*x）*x=x*（x*x）（结合律）=x j*x i从而由怕给性质，有x i=x j，即x*x=x。

因此，由x的任意性，可知X中每个元素都是幂等元。

10．设<X，⊕，⊗>是代素系统，⊕和⊗分别是X上的两上二元运算。

若∀x∈X，有x⊕y=x。

证明⊗关于⊕是可分配的。

[证] 对于任何x，y，z∈Xx⊗（y⊕z）=x⊗y=（x⊗y）⊕=（y⊕z）⊗x=y⊗x=（y⊗x）（z⊗x）因此代数系统<X，⊕，⊗>中⊗关于⊕是可分配的。

11．设<X，⊕，⊗>是代数系统，⊕和⊗分别是X上的两上二元运算。

e1和e2分别是关于⊗和⊕的幺元，且⊕对于⊗满足分配律，⊗对于⊕满足分配律。

合集下载

《离散数学》试题带答案(二)

《离散数学》试题带答案(二)

《离散数学》试题带答案试卷九试题与答案一、 填空 30% （每空 3分）1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。

2、 集合A={Φ,{Φ}}的幂集P (A) = 。

3、 设A={1，2，3，4}，A 上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图。

4、 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则B A ⋃= 。

B A = 。

5、 设|A|=3，则A 上有 个二元关系。

6、 A={1，2，3}上关系R= 时，R 既是对称的又是反对称的。

7、 偏序集><≤R A ,的哈斯图为，则≤R = 。

8、 设|X|=n ，|Y|=m 则（1）从X 到Y 有 个不同的函数。

（2）当n , m 满足 时，存在双射有 个不同的双射。

9、 2是有理数的真值为 。

10、Q ：我将去上海，R ：我有时间，公式)()(Q R R Q →∧→的自然语言为 。

11、公式)()(Q P P Q ∧⌝∧→的 主合取范式是 。

12、 若} ,, , {21m S S S S =是集合A 的一个分划，则它应满足 。

二、 选择 20% （每小题 2分）1、 设全集为I ，下列相等的集合是（ ）。

A 、} |{是偶数或奇数x x A =；B 、)}2( |{y x I y y x B =∧∈∃=；C 、)}12( |{+=∧∈∃=y x I y y x C ；D 、},4,4,3,3,2,2,1,1,0|{ ----=x D 。

2、 设S={N ，Q ，R}，下列命题正确的是（ ）。

A 、S S N N ∈∈∈2 ,2则； B 、S N S Q Q N ⊂∈⊂则 ,； C 、R N R Q Q N ⊂⊂⊂则 ,； D 、S N S N ⋂⊂Φ⊂Φ⊂Φ则 ,。

离散数学第四版课后答案(第2章)

离散数学第四版课后答案(第2章)

离散数学课后答案第2章习题解答2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x(是鸟F:)x(会飞翔.G:)xx命题符号化为xFx→∀.))G((x)((2)令x(为人.xF:)(爱吃糖G:)xx命题符号化为GxFx→⌝∀(x))()(或者xFx⌝∧∃(xG))(()(3)令xF:)(为人.xG:)(爱看小说.xx命题符号化为xF∃.Gx∧(x()))((4) x(为人.xF:)G:)(爱看电视.xx命题符号化为Fx⌝⌝∃.x∧(x))()G(分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。

（1）-（4）中的)(x F 都是特性谓词。

2° 初学者经常犯的错误是，将类似于（1）中的命题符号化为))()((x G x F x ∧∀即用合取联结词取代蕴含联结词，这是万万不可的。

将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。

”因而符号化应该使用联结词→而不能使用∧。

若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。

”这显然改变了原命题的意义。

3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。

2.2 (1)d (a),(b),(c)中均符号化为)(x xF ∀其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。

（2） 在)(),(),(c b a 中均符号化为)(x xG ∃其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。

（3）在)(),(),(c b a 中均符号化为)xH∃(x其中.1(ba中均为假命题，在(c)中为真H此命题在)(),xx5:)(=命题。

分析 1°命题的真值与个体域有关。

离散数学第二版答案(6-7章)

离散数学第二版答案(6-7章)

离散数学第二版答案(6-7章)LT第六章 代数系统6.1第129页1． 证明：任取,x y I ∈，(,)*(,)g y x y x y x yx x y xy g x y ==+-=+-=，因此，二元运算*是可交换的； 任取,,x y z I ∈，(,(,))*(*)*()()g x g y z x y z x y z yz x y z yz x y z yz x y z xy xz yz xyz==+-=++--+-=++---+((,),)(*)*()*()(,(,))g g x y z x y z x y xy zx y xy z x y xy z x y z xy xz yz xyz g x g y z ==+-=+-+-+-=++---+=因此，运算*是可结合的。

该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。

2．证明：任取,,x y N x y ∈≠，由*,*x y x y x y x ==≠知，**y x x y ≠，*运算不是可交换的。

任取,,x y z N ∈，由(*)**x y z x z x ==，*(*)*x y z x y x ==知，(*)**(*)x y z x y z =，*运算是可结合的。

任取x N ∈，*x x x =，可知N 中的所有元素都是等幂的。

*运算有右么元，任取,x y N ∈，*x y x =，知N 中的所有元素都是右么元。

*运算没有左么元。

证明：采用反证法。

假定e 为*运算的左么元，取,b N b e ∈≠，由*的运算公式知*e b e =，由么元的性质知，*e b b =，得e b =，这与b e ≠相矛盾，因此，*运算没有左么元。

3．解： ① 任取y x I y x ≠∈,,的最小公倍数和y x y x =*的最小公倍数和的最小公倍数和y x x y x y ==*因此对于任意的y x I y x ≠∈,,都有x y y x **=，即二元运算*是可交换的。

math-chap5-5.离散数学_代数系统

math-chap5-5.离散数学_代数系统


庄伯金 bjzhuang@
14
同态与同构

定义：设两代数系统V1=<A,*>和V2=<B,•>，如果 存在映射f:A→B，对任意的x,y∈A，有 f(x*y)=f(x)•f(y)，则称f是V1到V2的同态映射，简 称同态，记为<A,*>∼<B,•>。

若f为满射，则称f为满同态； 若f为单射，则称f为单一同态； 若f为双射，则称f为同构，记作<A,*>≌<B,•>。
庄伯金 bjzhuang@
12
子代数系统

定义：设有代数系统<A,*1,*2,...,*k>，B是A的非 空子集。如果A上的每个运算都在B上是封闭的，且A 与B含有相同的代数常数，则称代数系统 <B,*1,*2,...,*k>为代数系统<A,*1,*2,...,*k>的 子代数系统，或称代数B为代数A的子代数。
庄伯金 bjzhuang@
10
逆元

定理：设•为A上的可结合二元运算，A中存在幺元e 且每个元素都有左逆元，则在A中，每个元素的左逆 元也是该元素的右逆元，且每个元素的逆元唯一。
庄伯金 bjzhuang@
11
代数系统


定义：由非空集合A以及A上的运算*1,*2,...,*n所组 成的系统称为一个代数系统，记作 <A,*1,*2,...,*n>。 定义：如果两个代数系统中运算的个数相同，对应运 算的元数也相同，且代数常数的个数也相同，则称这 两个代数系统具有相同的构成成分，也称它们是同类 型的代数系统。
庄伯金 bjzhuang@
6
单位元