锐客网

  1. 首页 > it技术 > >

【Discrete|代数系统


主要内容
1. 函数 f：S×S→S 和 f：S→S 分别定义了S上的二元和一元运算。
2. 使用算符表示二元和一元运算有两种表示法：解析公式与运算表。
3. 二元运算的算律（交换律、结合律、幂等律、分配律和吸收律）及其判别方法。
4. 二元运算的单位元、零元和逆元的定义及其唯一性。
5.
 构成代数系统的基本成分：非空集合、集合上若干个封闭的二元和一元运算、代数常数。
6.
 具有相同构成成分的是同类型的代数系统，不仅构成成分相同而且运算性质相同则是同种的代数系统。
7.
 代数系统的非空子集关于原系统中的所有运算和代数常数封闭，则构成子代数。
学习要求
1. 能够判定某个运算是否为给定集合上的二元或一元运算。
2. 能够求出给定二元或一元运算的结果。通过给定解析公式求出相应的运算表。
3. 能指出给定运算所满足的算律（交换律、结合律、幂等律、分配律和吸收律）。
4. 能求出给定运算的单位元、零元和所有可逆元素的逆元。
5.
 判断给定集合和运算能否构成代数系统。
6.
 了解同类型和同种代数系统的概念
7.
 了解子代数的基本概念
二元运算及其性质
二元运算与一元运算的定义
二元运算的定义与实例
定义10.1 设S为集合,函数f：S×S→S称为S上的二元运算,简称为二元运算。
例如f：N×N→N,f()=x+y就是自然数集合N上的二元运算,即普通的加法运算。普通的减法不是自然数集合N上的二元运算,因为两个自然数相减可能得到负数,而负数不是自然数。这时也称N对减法运算不封闭。验证一个运算是否为集合S上的二元运算主要考虑两点：
(1)S中任何两个元素都可以进行这种运算,且运算的结果是唯一的。
(2)S中任何两个元素的运算结果都属于S,即S对该运算是封闭的。例如实数集合R上不可以定义除法运算,因为0∈R,而0不能做除数。但在R*=R－{0}上就可以定义除法运算了,因为x,y∈R*,都有x/y∈R*。
二元与一元运算的表示

1．算符
可以用、*、·、、 等符号表示二元或一元运算,称为算符。对于二元运算,如果x与y运算得到z,记做xy=z；对于一元运算，x的运算结果记作x.

2．表示二元或一元运算的方法---解析公式和运算表

表示二元或一元运算的方法有两种：解析公式和运算表。
所谓解析公式就是使用算符和表达式给出参与运算的元素和运算结果之间的映射规则。
二元运算的性质

主要算律
定义10.3 设为S上的二元运算,
(1)如果对于任意的x,y∈S,有xy=yx,则称运算在S上满足交换律。
(2)如果对于任意的x,y,z∈S有(xy)z=x(yz),则称运算在S上满足结合律。
(3)如果对于任意的x∈S有xx=x,则称运算在S上满足幂等律。
定义10.4 设和*为S上两个不同的二元运算,
(1)如果对于任意的x,y,z∈S有(x*y)z=(xz)*(yz)和z(x*y)=(zx)*(zy),则称运算对*运算满足分配律。
(2)如果和*都可交换,并且对于任意的x,y∈S有x(x*y)=x和x*(xy)=x,则称和*运算满足吸收律。
代数系统
代数系统的定义与实例
定义10.6 非空集合S和S上k个一元或二元运算f 1,f 2,…f k组成的系统称为一个 代数系统,简称 代数,记做1,f 2,…f k>。

例如,,都是代数系统,其中+和·分别表示普通加法和乘法。是代数系统,其中＋和·分别表示n阶(n≥2)实矩阵的加法和乘法。是代数系统,其中Zn＝{0,1,…,n-1},和分别表示模n的加法和乘法,对于x,y∈Zn,xy=(x＋y)modn,xy=(xy)modn；也是代数系统,其中含有两个二元运算∪和∩以及一个一元运算~。
在某些代数系统中存在着一些特定的元素,它们对于系统的一元或二元运算起着重要的作用,例如二元运算的单位元和零元。在定义代数系统的时候,如果把含有这样的特定元素也作为系统的性质,比如规定系统的二元运算必须含有单位元，这时称这些元素为该代数系统的特异元素或代数常数。有时为了强调某个代数系统是含有代数常数的系统,也可以把这些代数常数列到系统的表达式中,例如中的+运算有单位元0,为了强调0的存在,可以将记做。又如中的∪和∩运算存在单位元和S,当规定和S是该系统的代数常数时,也可将它记为。当然,在不发生混淆的情况下为了叙述的简便也常用集合的名字来标记代数系统,例如上述代数系统可以简记为Z和P(S)。 子代数系统


定义10.8设V=1,f2,…fk>是代数系统,B是S的非空子集,如果B对f1,f2,…fk 都是封闭的,且B和S含有相同的代数常数,则称是V的子代数系统,简称子代数。有时将子代数系统简记为B。
例如N是的子代数,因为N对加法运算＋是封闭的。N也是的子代数,因为N对加法运算＋是封闭的,且N中含有代数常数0。N-{0}是的子代数,但不是的子代数,因为的代数常数0N－{0}。
从子代数定义不难看出,子代数和原代数不仅具有相同的构成成分,是同类型的代数系统,而且对应的二元运算都具有相同的运算性质。因为任何二元运算的性质如果在原代数上成立,那么在它的子集上显然也是成立的。在这个意义上讲,子代数在许多方面与原代数非常相似,不过可能小一些就是了。
对于任何代数系统V=1,f2,…fk>,其子代数一定存在。最大的在代数就是V本身。如果令V中所有代数常数构成的集合是B,且B对V中所有的运算都是封闭的,则B就构成了V的最小的子代数。这种最大和最小的子代数称为V的平凡的子代数。若B是S的真子集,则B构成的子代数称为V的真子代数。 例10.9设V=,令 nZ={nz|z∈Z},n为自然数,则nZ是V的子代数。
证： 任取nZ中的两个元素nz1,nz2(z1,z2∈Z),则有nz1+nz2=n(z1+z2)∈nZ
即 nZ对+运算是封闭的。又0=n·0∈nZ 所以nZ是V的子代数。
当n=1和0时,nZ是V的平凡的子代数,其它的都是V的非平凡的真子代数。

习题【【Discrete|代数系统】
1、列出以下运算的运算表：
(1) A={1,2,}，x∈A，x是x的倒数，即x=.
(2) A={1,2,3,4},x,y∈A有xy=max(x,y),max(x,y)是x和y之中较大的数。
2、判断下列集合对所给的二元运算是否封闭：
(1) 整数集合Z和普通的减法运算
(2) 非零整数集合Z*和普通的除法运算
(3) 全体n×n实矩阵集合Mn(R)和矩阵加法及乘法运算，其中n≥2
(4) 全体n×n实可逆矩阵集合关于矩阵加法和乘法运算，其中n≥2
(5) 正实数集合R+和运算，其中运算定义为：
ａ,ｂ∈R+,ab=ab-a-b
(6) n∈Z+,nZ={nz|z∈Z}.nZ关于普通的加法和乘法运算。
(7) A={a1,a2,...,an},n≥2.运算定义如下：ai,aj∈A,aiaj=ai.
(8) S={2x-1|x∈Z+}关于普通的加法和乘法运算。
(9) S={0,1},S关于普通的加法和乘法运算。
(10)S={x|x=2n,n∈Z+}，S关于普通的加法和乘法运算。
3、对于上题中封闭的二元运算判断是否适合交换律、结合律和分配律。
4、对习题2中封闭的二元运算找出它的单位元，零元和所有可逆元素的逆元。
5、S=Q×Q,Q为有理数集，*为S上的二元运算，,∈S有
*=
(1) *运算在S上是否可交换，可结合？是否为幂等的？
(2) *运算是否有单位元，零元？如果有，请指出，并求S中所有可逆元素的逆元。
6、R为实数集，定义以下六个函数f1,...,f6.x,y∈R有
f1()=x+y,f2()=x-y,
f3()=x·y,f4()=max(x,y),
f5()=min(x,y),f6()=|x-y|
(1) 指出哪些函数是R上的二元运算。
(2) 对所有R上的二元运算说明是否为可交换、可结合、幂等的。
(3) 求所有R上二元运算的单位元、零元以及每一个可逆元素的逆元。
7、令S={a,b},上有四个二元运算：*,,·和,分别由表10.8确定。
表10.8

(1) 这四个运算中哪些运算满足交换律、结合律、幂等律
(2) 求每个运算的单位元、零元及所有可逆元素的逆元。
8、设S={1,2,...,10},问下面定义的运算能否与S构成代数系统?如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。
(1) x*y=gcd(x,y),gcd(x,y)是x与y的最大公约数。
(2) x*y=lcm(x,y),lcm(x,y)是x与y的最小公倍数。
(3) x*y=大于等于x和y的最小整数。
(4) x*y=质数p的个数，其中x≤p≤y.
9、下面各集合都是N的子集，它们能否构成代数系统V=的子代数：
(1) {x|x∈N∧x可以被16整除}
(2) {x|x∈N∧x与8互质}
(3) {x|x∈N∧x是40的因子}
(4) {x|x∈N∧x是30的倍数}
10、设V=，其中+和·分别代表普通加法和乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？
(1) S1={2n|n∈Z}
(2) S2={2n＋1|n∈Z}
(3) S3={－1，0，1}
11、设V1=<{1,2,3},,1>,其中xy表示取x和y之中较大的数。V2=<{5,6},*,6>,其中x*y表示取x和y之中较小的数。求出V1和V2的所有子代数。指出哪些是平凡子代数，哪些是真子代数。


关于Discrete Mathematics更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.



    推荐阅读


    上一篇：Java|Java NIO详解

    下一篇：删库不必跑路！详解|删库不必跑路！详解 MySQL 数据恢复