第九章代数系统
9.1 二元运算及其性质
一、二元运算与一元运算的定义
1.二元运算的定义与实例
定义9.1 设S为集合,函数f:S×S→S称为S上的二元运算,简称为二元运算。 验证一个运算是否为集合S上的二元运算主要考虑两点:
(1)S中任何两个元素都可以进行这种运算,且运算的结果是唯一的。
(2)S中任何两个元素的运算结果都属于S,即S对该运算是封闭的。
例9.1
(1) 自然数集合N上的加法和乘法是N上的二元运算,但减法和除法不是。
(2) 整数集合Z上的加法、减法和乘法都是Z上的二元运算,而除法不是。
(3) 非零实数集R*上的乘法和除法都是R*上的二元运算,而加法和减法不是,因为两个非零实数相加或相减可能得0.
(4) 设M n(R)表示所有n阶(n≥2)实矩阵的集合,即
则矩阵加法和乘法都是M n(R)上的二元运算。
(5) S为任意集合,则∪、∩、-、为S的幂集P(S)上的二元运算,这里∪和∩是初级并和初级交。
(6) S为集合,S S为S上的所有函数的集合,则函数的集合运算为S S上的二元运算。
2.一元运算的定义与实例
定义9.2设S为集合,函数f:S→S称为S上的一个一元运算,简称为一元运算。例9.2
(1) 求一个数的相反数是整数集合Z,有理数集合Q和实数集合R上的一元运算。
(2) 求一个数的倒数是非零有理数集合Q*,非零实数集合R*上的一元运算。
(3) 求一个复数的共轭复数是复数集合C上的一元运算。
S 可以用x
x. x,y 3*4=3,(-5)*0.2=-5,0*
a a a a i a 1
潍坊学院计算机系(院)讲稿专用纸
例9.4设S={1,2},给出P(S)上的运算~和的运算表,其中全集为S.
解:所求的运算表如表9.3和表9.4.
表9.3 表9.4
三.二元运算的性质
1.主要算律
定义9.3 设为S上的二元运算,
(1)如果对于任意的x,y∈S,有x y=y x,则称运算在S上满足交换律。
(2)如果对于任意的x,y,z∈S有(x y)z=x(y z),则称运算在S上满足结合律。
(3)如果对于任意的x∈S有x x=x,则称运算在S上满足幂等律。
定义9.4设和*为S上两个不同的二元运算,
(1)如果对于任意的x,y,z∈S有(x*y)z=(x z)*(y z)和z(x*y)=(z
x)*(z y),则称运算对*运算满足分配律。
(2)如果和*都可交换,并且对于任意的x,y∈S有x(x*y)=x和x*(x y)=x,则称和*运算满足吸收律。
例9.5 表9.5和9.6给出了某些常见代数运算的性质,其中Z、Q、R分别代表整数集、有理数集、实数集,M n(R)表示n(n≥2)阶实矩阵的集合,A A是所有从A到A的函数的集合。
表9.5
表9.6
2.特异元素:单位元、零元和逆元
定义9.5设为S上的二元运算,
(1) 如果存在e l(或e r)∈S,使得对任意x∈S都有e1x=x (或x e r=x),则称e1(或e r)是S中关于运算的左(或右)单位元。若e∈S关于运算既是左单位元又是右单位元,则称e为S上关于运算的单位元。单位元也叫做幺元。
(2) 如果存在θl(或θr)∈S,使得对任意x∈S都有θl x=θl (或xθr=θr),则称θl(或θr)是S中关于运算的左(或右)零元。若S关于运算既是左零元又是右零元,则称θ为S上关于运算的零元。
(3) 令e为S中关于运算的单位元.对于x∈S,如果存在y l(或y r)∈S使得y l x=e(或x y r=e),则称y l(或y r)是x的左逆元(或右逆元)。若y∈S既是x的左逆元又是x的右逆元,则称y为x的逆元。如果x的逆元存在,就称x是可逆的。例9.6针对例9.5的集合和运算,表9.7给出了相关运算的特异元素。
表9.7
关于单位元、零元与逆元有下述的唯一性定理。
定理9.1设为S上的二元运算,e l和e r分别为S中关于运算的左和右单位元,则e l=e r=e为S上关于运算的唯一的单位元。
证:e l = e l e r (e r为右单位元)
e l e r = e r (e l为左单位元)
所以e l=e r,将这个单位元记作e。假设e'也是S中的单位元,则有e'=e e'=e。唯一性得证。
类似地可以证明关于零元的唯一性定理。
定理9.2设为S上可结合的二元运算,e为该运算的单位元,对于x∈S如果存在左逆元y l和右逆元y r,则有y l = y r= y,且y是x的唯一的逆元。
证:由y l x = e 和x y r = e 得
y l = y l e = y l(x y r) = (y l x)y r = e y r = y r
令y l = y r = y,则y是x的逆元。假若y'∈S也是x的逆元,则
y'= y' e = y'(x y) = (y'x)y = e y = y
所以y是x唯一的逆元。
由定理9.2可知,对于可结合的二元运算,可逆元素x只有唯一的逆元,通常把它记作x-1。
用反证法可以证明,单位元与零元是不同的,除非集合S只有一个元素。在这种情况下,这个唯一的元素既是单位元也是零元。
9.2 代数系统
定义9.6 非空集合S 和S 上k 个一元或二元运算f 1,f 2,…,f k 组成的系统称为一个代数系统,简称为代数,记为。
例如:
可以将代数常数放到系统的表达式中,可以用集合的名字标记一个代数系统。
定义9.7 如果两个代数系统中运算的个数相同,对应运算的元数相同,且代数常数的个数也相同,则称这两个代数系统具有相同的构成成分,也称它们是同类型的代数系统。 V 1=
V 2=
同类型的代数系统不一定具有相同的运算性质。
定义9.8 设V=是代数系统,B ?S, 如果B 对f 1,f 2,…,f k 都是封闭的,且B 和S 含有相同的代数常数,则称是V 的子代数系统,简称子代数。
N 是
最大子代数是V 本身,最小子代数是V 的所有代数常数构成的集合。 最大子代数和最小子代数称为V 的平凡子代数。 例9.7 设V=
nZ={nz|z ∈Z}, n 为自然数, 证明nZ 是V 的子代数。
定义9.9 设V 1=,V 2=是同类型的代数系统,?和*为二元运算,在集
合A ×B 上如下定义二元运算﹒, ? , ∈ A ×B, 有
记作V 1×V 2。这时也称V 1和V 2
为V 的因子代数。 定理9.3 设V 1=和V 2=是同类型的代数系统,V 1×V 2 =< A ×B,﹒>是它们的积代数。
(1)如果?和*运算是可交换(可结合、幂等)的,那么﹒运算也是可交
换(可结合、幂等)的;
(2)如果e1和e2(θ1和θ2)分别为?和*运算的单位元(零元),那么< e1,e2 >(< θ1,θ2 >)也是﹒运算的单位元(零元);
(3)如果x和y分别为?和*运算的可逆元素,那么
9.3 代数系统的同态与同构
定义9.10 设V1=和V2=是同类型的代数系统, f: A→B,且?x,y ∈A有f(x?y)= f(x)* f(y),则称f是V1到V2的同态映射,简称同态。
根据同态映射的性质可以将同态分为单同态、满同态和同构。即:若f是
单射的,则称为单同态;若是满射,则称为满同态,这时也称V2是V1的同态像,记作V1~V2;若是双射的,则称为同构,也称代数系统V1同构于V2,记作V1≌V2。
若同态映射f是V到V的,则称f为自同态。类似的可以定义满自同态,单自同态和自同构。
设f是V1=到V2=的同态映射,那么f具有许多良好的性质。
首先,如果?运算具有交换律、结合律、幂等律等,那么在同态像f(V1)中,*运算也具有相同的算律(注意,消去律可能例外)。
此外,同态映射f恰好把V1的单位元e1映到V2的单位元e2,即f(e1)=e2。同样对于零元和逆元也有f(θ1)=θ2,f(x-1)= f(x)-1。
上述关于同态映射的定义可以推广到具有有限多个运算的代数系统。
例9.8 判断下面给出的映射f是否是同态映射,如果是判断它们是单同态、满同态还是同构。
(1)设V1=
f: Z→ Z n,f(x)=(x)mod n
(2)设V1=
f: R→ R*,f(x)=e x
(3)设V=
f a: Z→ Z,f a(x)=ax
.设G为群,若x∈G有x2=e,证明G为交换群。 .设G为群,证明e为G中唯一的幂等元。 .证明4阶群必含2阶元。 设A={a+bi|a,b∈Z,i2=-1},证明A关于复数的加法和乘法构成环,称为高斯整数环。 .(1) 设R 1,R 2 是环,证明R 1 与R 2 的直积R 1 ×R 2 也是环。 (2) 若R 1和R 2 为交换环和含幺环,证明R 1 ×R 2 也是交换环和含幺环。 . 判断下列集合和给定运算是否构成环、整环和域,如果不能构成,说明理由。 (1) A={a+bi|a,b∈Z},其中i2=-1,运算为复数的加法和乘法。 (2) A={-1,0,1},运算为普通加法和乘法。 (3) A=M 2 (Z),2阶整数矩阵的集合,运算为矩阵加法和乘法。 (4) A是非零有理数集合Q*,运算为普通加法和乘法。 .设G是非阿贝尔群,证明G中存在元素a和b,a≠b,且ab=ba. .设H是群G的子群,x∈G,令 xHx-1={xhx-1|h∈H}, 证明xHx-1是G的子群,称为H的共轭子群。 .设
第14章代数系统 14.1 代数系统 1.集合A={1,2,3,4}, * 是A 上的二元运算,定义为 a * b = a ·b - b ,试写出*的运算表。 2.< Z 5,5⊕>是代数系统,其中Z 5 ={0,1,2,3,4},运算5⊕是模5加法,试写出5⊕的运算表。 3.设A={1,2,3,4,5},A 上二元运算*定义 a * b = min(a,b), 其中min(a,b)是求a 和b 的最小值,写出*的运算表。 4.< Z 3,3?>是代数系统,其中Z 3 = {0,1,2},运算3?是模3乘法,试写出3?的运算表,并求(23?2)3?2和23?(23?2)的值。
9.设Z+是所有正整数的集合,Z+上的二元运算*定义为a*b = gcd(a,b), 其中gcd(a,b)表示a和b的最大公约数。写出代数系统< Z+, * >幺元和零元(如果存在的话)。 10.设是代数系统,其中A={a,b,c,d}, 运算*由下表给出,请指出中的幺元,零元和各元素的逆元(如果存在的话)。 11.请构造一个代数系统,除幺元外,每个元素都没有逆元。
第一章,0命题逻辑 素数 = 质数,合数有因子 和或假必真同为真 (p→q)∧(q←→r),(p∧q)∧┐r,p∧(q∧┐r)等都是合式公式,而pq→r,(p→(r→q)等不是合式公式。 若公式A是单个的命题变项,则称A为0层合式 (┐p∧q)→r,(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表,并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011,其余7个赋值都是成真赋值 第二章,命题逻辑等值演算 (1)双重否定律??A?A (2)等幂律 A∧A?A ; A∨A?A (3)交换律 A∧B?B∧A ; A∨B?B∨A (4)结合律(A∧B)∧C?A∧(B∧C);(A∨B)∨C?A∨(B∨C) (5)分配律(A∧B)∨C?(A∨C)∧(B∨C);(A∨B)∧C?(A∧C)∨(B∧C)(6)德·摩根律?(A∨B)??A∧?B ;?(A∧B)??A∨?B (7)吸收律 A∨(A∧B)?A;A∧(A∨B)?A (8)零一律 A∨1?1 ; A∧0?0 (9)同一律 A∨0?A ; A∧1?A (10)排中律 A∨?A?1 (11)矛盾律 A∧?A?0
(12)蕴涵等值式 A→B??A∨B (13)假言易位 A→B??B→?A (14)等价等值式 A?B?(A→B)∧(B→A) (15)等价否定等值式 A?B??A??B??B??A (16)归缪式(A→B)∧(A→?B)??A (p∧┐q)∨(┐q∧┐r)∨p (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真,∨大假】 ∧成真小写 【例】 (p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) (*) = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下: ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q)
第三部分:代数系统 1.在代数系统,S *中,若一个元素的逆元是唯一的,其运算*必定可结合。( ) 2.每一个有限整环一定是域,反之也对。( ) 3.任何循环群必定是阿贝尔群,反之亦真。( ) 4.设(),A ∧∨是布尔代数,则(),A ∧∨一定为有补分配格。( ) 5.设Q 为有理数集,Q 上运算*定义为max(,)a b a b *=,则 ,Q * 是半群。( ) 6.阶数为偶数的有限群中,周期为2的元素的个数一定为偶数。( ) 7.群中可以有零元(对阶数大于一的群)。( ) 8.循环群一定是阿贝尔群。( ) 9.每一个链都是分配格。( ) 1. 对自然数集合N ,哪种运算不是可结合的,运算定义为任,a b N ∈ ( ) A. min(,)a b a b *= B. 2a b a b *=+ C. 3a b a b *=+- D. a b a b *=+ (mod 3) 2. 任意具有多个等幂元的半群,它 ( ) A. 不能构成群 B. 不一定能构成群 C. 不能构成交换群 D. 能构成交换群 3. 循环群33,Z +的生成元为[][]1,2,它们的周期为 ( ) A. 5 B. 6 C. 3 D. 9 4. 设是环,则下列正确的是 ( ) A. 是交换群 B. 是加法群 C. 对*是可分配的 D. *对 是可分配的 5. 下面集合哪个关于减法运算是封闭的 ( ) A. N B. {2|}x x I ∈ C. {21|}x x I +∈ D. {x |x 是质数} 6. 具有如下定义的代数系统,G ?*?,哪个不构成群 ( ) A. G={1,10},*是模11乘 B. G={1,3,4,5,9},*是模11乘 C. G =Q(有理数集),*是普通加法 D. G =Q(有理数集),*是普通乘法 7. 设G ={23|,m n m n I *∈},*为普通乘法.则代数系统,G ?*?的么元为 ( ) A.不存在 B. e =0023? C. e =2×3 D. e =1123--? 8. 任意具有多个等幂元的半群,它( A ) A. 不能构成群 B. 不一定能构成群 C. 必能构成群 D. 能构成交换群 9. 在自然数集N 上,下面哪个运算是可结合的,对任意a ,b N ∈ ( ) A. a b a b *=- B. max(,)a b a b *= C. 5a b a b *=+ D. ||a b a b *=-
第五章 方程求解 1 代数方程(组)求解 1.1 常用求解工具—solve 求解代数方程或代数方程组, 使用Maple 中的solve 函数. 求解关于x 的方程eqn=0的命令格式为: solve(eqn, x); 求解关于变量组vars 的方程组eqns 的命令为: solve(eqns, vars); > eqn:=(x^2+x+2)*(x-1); := eqn () + + x 2x 2() - x 1 > solve(eqn,x); ,,1- + 1212I 7- - 1212 I 7 当然, solve 也可以求解含有未知参数的方程: > eqn:=2*x^2-5*a*x=1; := eqn = - 2x 25a x 1 > solve(eqn,x); , + 5a 14 + 25a 28 - 5a 1 + 25a 28 solve 函数的第一个参数是有待求解的方程或方程的集合, 当然也可以是单个表达式或者表达式的集合, 如下例: > solve(a+ln(x-3)-ln(x),x); 3e a - + 1e a 对于第二个参数, Maple 的标准形式是未知变量或者变量集合, 当其被省略时, 函数indets 自动获取未知变量. 但当方程中含有参数时, 则会出现一些意想不到的情况: > solve(a+ln(x-3)-ln(x));
{}, = x x = a - + ()ln - x 3()ln x 很多情况下, 我们知道一类方程或方程组有解, 但却没有解决这类方程的一般解法, 或者说没有解析解. 比如, 一般的五次或五次以上的多项式, 其解不能写成解析表达式. Maple 具备用所有一般算法尝试所遇到的问题, 在找不到解的时候, Maple 会用RootOf 给出形式解. > x^7-2*x^6-4*x^5-x^3+x^2+6*x+4; - - - + + + x 72x 64x 5x 3x 26x 4 > solve(%); + 15 - 15()RootOf , - - _Z 5_Z 1 = index 1()RootOf , - - _Z 5_Z 1 = index 2()RootOf , - - _Z 5_Z 1 = index 3,,,,, ()RootOf , - - _Z 5_Z 1 = index 4()RootOf , - - _Z 5_Z 1 = index 5, > solve(cos(x)=x,x); ()RootOf - _Z ()cos _Z 对于方程组解的个数可用nops 命令获得, 如: > eqns:={seq(x[i]^2=x[i],i=1..7)}; := eqns {},,,,,, = x 12x 1 = x 22x 2 = x 32x 3 = x 42x 4 = x 52x 5 = x 62x 6 = x 72 x 7 > nops({solve(eqns)}); 128 但是, 有时候, Maple 甚至对一些“显而易见”的结果置之不理, 如: > solve(sin(x)=3*x/Pi,x); ()RootOf - 3_Z ()sin _Z π 此方程的解为0 ,6 π±, 但Maple 却对这个超越方程无能为力, 即便使用allvalues 求解也只有下述结果: > allvalues(%); ()RootOf , - 3_Z ()sin _Z π0. 另外一个问题是, Maple 在求解方程之前,会对所有的方程或表达式进行化简, 而不管表达式的类型, 由此而产生一些低级的错误: > (x-1)^2/(x^2-1); () - x 12 - x 21 > solve(%); 1
第六章代数系统 1. 填空题:f是X上的n元运算的定义是()。 2. 判断正误,并说明原因:自然数集合N上的减法运算“-”是个封闭的运算。 3. 判断正误,并说明原因:实数集合R上的除法运算“?”是个封闭的运算。 4.填空题:代数系统的定义是:()。 5. 填空题:*是X上的二元运算,*具有交换性,则它的运算表的特征是()。 6.填空题:*是X上的二元运算,*具有幂等性,则它的运算表的特征是()。 7. 简答题:*是X上的二元运算,*具有幺元,如何在它的运算表上判定哪个元素是幺元? 8. 简答题:*是X上的二元运算,*具有零元,如何在它的运算表上判定哪个元素是零元? 9. 简答题:*是X上的二元运算,*具有幺元,如何判定哪个元素是元素x的逆元? 10 令N4={0,1,2,3},N4上定义运算+4: 任何x,y∈N4 , x+4 y=(x+y)(mod 4) 。例如2+43=(2+3)(mod 4) =5(mod 4)=1 请列出
14. 填空题:E是全集,E={a,b},E的幂集P(E)上的对称差运算?的幺元是()。零元是()。有逆元的元素是()。它们的逆元分别是()。 15. 填空题:对于自然数集合N上的加法运算“+”,13=()。 16. 填空题:你所知道的满足吸收律的运算有()。 17. 填空题:你所知道的具有零元的运算有(),其零元是()。 18. 设?是X上的二元运算,如果有左幺元e L∈X,也有右幺元e R∈X,则e L= e R =e ,且幺元e 是唯一的。 19. 设?是X上的二元运算,如果有左零元θL∈X,也有右零元θR∈X,则θL=θR =θ,且零元θ是唯一的。 20. 设?是X上有幺元e且可结合的二元运算,如果x∈X,x的左、右逆元都存在,则x的左、右逆元必相等。且x的逆元是唯一的。 21. 设?是X上且可结合的二元运算,如a∈X,且a-1∈X,则a是可消去的,即任取x,y∈X,设有a?x=a?y 则x=y。 22. 对于实数集合R,给出运算如下:+是加法、—是减法、·是乘法、max是两个数中取最大的、min是两个数中取最小的、|x-y|是x与y差的绝对值。判 N”。 23. 设R是实数集合,在R上定义二元运算* 如下:任取x,y∈R, x*y=xy-2x-2y+6
一、填空 1.下列集合中, 对普通加法和普通乘法都封闭。 ( ) (A ){}1,0 (B ){}2,1 (C ){}N n n ∈2 (D ){} N n n ∈2 2、在自然数集N 上,下面哪种运算是可结合的? ( ) (A )b a - (B )),max(b a (C )b a 2+ (D )b a - 3、有理数集Q 关于下列哪个运算能构成代数系统? ( ) (A )b a b a =* (B )()1ln 22++=*b a b a (C )()b a b a +=*sin (D )ab b a b a -+=* 4、下列运算中,哪种运算关于整数集I 不能构成半群? ( ) (A )()b a b a ,max =* (B )b b a =* (C )ab b a 2=* (D )b a b a -=* 5.设代数系统?A ,·?,则( )成立. A .如果?A ,·?是群,则?A ,·?是阿贝尔群 B .如果?A ,·?是阿贝尔群,则?A ,·?是循环群 C .如果?A ,·?是循环群,则?A ,·?是阿贝尔群 D .如果?A ,·?是阿贝尔群,则?A ,·?必不是循环群 6.设?L ,∧∨,?是格,?L ,≤?是由这个格诱导的偏序集,则( )不成立. A .对任意a L b a ,,∈≤b b a b =∨? B .∧∨对是可分配 C .∧∨,都满足幂等律 D .?L,≤?的每对元素都有最小上界与最大下界 7.在下列四个哈斯图表示的偏序集中( )是格.
8. 已知偏序集的哈斯图,如图所示,是格的为( ) 9. 6阶有限群的任何子群一定不是()。 (A) 2阶(B) 3 阶(C) 4 阶(D) 6 阶 10. 下列哪个偏序集构成有界格() (1) (N,≤)(2) (Z,≥) (3) ({2,3,4,6,12},|(整除关系))(4) (P(A),?) 11. 下面代数系统中(G、*)中()不是群 A、G为整数集合*为加法 B、G为偶数集合*为加法 C、G为有理数集合*为加法 D、G为有理数集合*为乘法 12. 设
第九章环与域 ?9.1 环:两个二元运算的代数结构 ?1.环的概念 ?定义9.1:,
9.2 整环和域 ?定义9.5:R是环,令,若为阿 贝尔群,则称
代数发展简史 一门科学的历史是那门科学中最宝贵的一部分,因为科学只能给我们知识, 而历史却能给我们智慧。 傅鹰 数学的历史是重要的,它是文明史的有价值的组成部分, 人类的进步和科学思想是一致的。 F. Cajori 0、引言 数学发展到现在,已经成为科学世界中拥有100多个主要分支学科的庞大的“共和国”。大体说来,数学中研究数的部分属于代数学的范畴;研究形的部分,属于几何学的范筹;沟通形与数且涉及极限运算的部分,属于分析学的范围。这三大类数学构成了整个数学的本体与核心。在这一核心的周围,由于数学通过数与形这两个概念,与其它科学互相渗透,而出现了许多边缘学科和交叉学科。在此简要介绍代数学的有关历史发展情况。 “代数”(algebra)一词最初来源于公元9世纪阿拉伯数学家、天文学家阿尔·花拉子米(al-Khowārizmī,约780-850)一本著作的名称,书名的阿拉伯文是‘ilm al-jabr wa’l muqabalah,直译应为《还原与对消的科学》.al-jabr 意为“还原”,这里指把负项移到方程另一端“还原”为正项;muqabalah 意即“对消”或“化简”,指方程两端可以消去相同的项或合并同类项.在翻译中把“al-jabr”译为拉丁文“aljebra”,拉丁文“aljebra”一词后来被许多国家采用,英文译作“algebra”。
阿布·贾法尔·穆罕默德·伊本·穆萨·阿尔—花拉子米的传记材料,很少流传下来.一般认为他生于花拉子模[Khwarizm,位于阿姆河下游,今乌兹别克境内的希瓦城(Хива)附近],故以花拉子米为姓.另一说他生于巴格达附近的库特鲁伯利(Qut-rubbullī).祖先是花拉子模人.花拉子米是拜火教徒的后裔,早年在家乡接受初等教育,后到中亚细亚古城默夫(Мерв)继续深造,并到过阿富汗、印度等地游学,不久成为远近闻名的科学家.东部地区的总督马蒙(al-Ma’mūn,公元786—833年)曾在默夫召见过花拉子米.公元813年,马蒙成为阿拔斯王朝的哈利发后,聘请花拉子米到首都巴格达工作.公元830年,马蒙在巴格达创办了著名的“智慧馆”(Bayt al-Hikmah,是自公元前3世纪亚历山大博物馆之后最重要的学术机关),花拉子米是智慧馆学术工作的主要领导人之一.马蒙去世后,花拉子米在后继的哈利发统治下仍留在巴格达工作,直至去世.花拉子米生活和工作的时期,是阿拉伯帝国的政治局势日渐安定、经济发展、文化生活繁荣昌盛的时期. 花拉子米科学研究的范围十分广泛,包括数学、天文学、历史学和地理学等领域.他撰写了许多重要的科学著作.在数学方面,花拉子米编著了两部传世之作:《代数学》和《印度的计算术》. 1859年,我国数学家李善兰首次把“algebra”译成“代数”。后来清代学者华蘅芳和英国人傅兰雅合译英国瓦里斯的《代数学》,卷首有“代数之法,无论何数,皆可以任何记号代之”,亦即:代数,就是运用文字符号来代替数字的一种数学方法。
《离散数学》代数系统 1.以下集合和运算是否构成代数系统?如果构成,说明该系统是否满足结合律、交换律?求出该运算的幺元、零元和所有 可逆元素的逆元. 1)P(B)关于对称差运算⊕,其中P(B)为幂集. 构成代数系统;满足结合律、交换律;幺元φ;无零元;逆元为自身。 2)A={a,b,c},*运算如下表所示:构成代数系统;满足结合律、交换律;无幺元;无逆元;零元b. 2.设集合A={a,b},那么(1)在A上可以定义多少不同的二元运算?(2)在A上可以定义多少不同的具有交换律的二元 运算?24个不同的二元运算;23个不同的具有交换律的二元运算 3.设A={1,2},B是A上的等价关系的集合. 1)列出B的元素. 2元集合上只有2种划分,因此只有2个等价关系,即B={I A,E A} 2)给出代数系统V=的运算表. 3)求出V的幺元、零元和所有可逆元素的逆元. 幺元E A、零元I A;只有E A可逆,其逆元为E A. 4)说明V是否为半群、独异点和群?V是为半群、独异点,不是群 4.设A={a,b,c},构造A上的二元运算*,使得a*b=c,c*b=b,且*运算满足幂等律、交换律. 1)给出关于*运算的一个运算表. 其中表中?位置可以是a、b、c。 2)*运算是否满足结合律,为什么?不满足结合律;a*(b*b)=c≠(a*b)*b=b 5.设是半群,且*是可交换的. 证明:如果S中有元素a,b,使得a*a=a和b*b=b,则(a*b)*(a*b)=a*b. (a*b)*(a*b) = a*(b*a)*b 结合律 = a*( a*b)*b 交换律 = (a* a)*(b*b) = a*b. 7.设
第五章代数系统的一般性质 代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知,在许多实际问题的研究中都离不开数学模型,而构造数学模型就要用到某种数学结构,而近世代数研究的中心问题是代数系统的结构:半群、群、格与布尔代数等等。近世代数的基本概念、方法和结果已成为计算机科学与工程领域中研究人员的基本工具。在研究形式语言与自动机理论、编码理论、关系数据库理论、抽象数据类型理论中,在描述机器可计算的函数、研究计算复杂性、刻画抽象数据结构、研究程序设计学中的语义学、设计逻辑电路中有着十分广泛的应用。 5.1 代数运算及其性质 5.1.1代数运算的定义 定义5.1.1 设S是一个非空集合, (1)函数f:S→S,称为一个S上的一个一元运算。 (2)函数f:S?S→S,称为一个S上的一个二元运算。 记号: f(x,y)=z, xfy=z x y=z (3)函数f:S?S?…?S →S,称为一个S上的一个n元运算。 [例5.1.1](1)数理逻辑中的联结词;集合论中的并运算、交运算和补运算;整数集中的加法、减法和乘法运算都是相应集合上的运算. (2)但Z中的除法不是一个二元运算。 (3) 在Z商定义x*y=x+y-2,则*是一个二元运算。 当S是有限集时,S上的一元、二元运算可用运算表来定义。 定义5.1.2 设 是集合S上的n元运算,S是S的一个非空子集。若对?x1,x2,…,x n∈S,有 (x 1,x 2,…,x n)∈S,则称S关于运算 是封闭的。 [例5.1.2]实数集关于数的普通除法是封闭的,整数集关于数的普通加法不是封闭的。
5.1.2代数运算的性质 定义5.1.3 设*是集合S上的二元运算。若?x,y∈S,x*y=y*x, 则称运算*满足交换律(或称*是可交换的)。 定义5.1.4 设*是集合S上的二元运算。若?x,y,z∈S,(x*y)*z = x*(y*z),则称运算*满足结合律(或称*是可结合的)。 定义5.1.5 设*是集合S上的二元运算。若?x∈S,x*x = x,则称运算*满足幂等律。定义5.1.8 设*和 是集合S上的二元运算。若?x,y,z∈S, x*(y z)=(x*y) x*z), (y z)*x =(y*x) (z*x), 则称*关于 满足分配律。 定义5.1.9设*和 是集合S上的二元运算。若?x,y∈S, x*(x y)=x x (x*y)=x 则称*关于 满足分配律。 [例5.1.3]R上的加法和乘法运算是可交换的,也是可结合的;但减法却是不可交换和 不可结合的;乘法关于加法是可分配的,但加法关于乘法则是不可分配的。任一集合的幂集 上的并和交运算是可交换和可结合的,并且它们是相互可分配的。 注:若运算*是可结合的,则有时我们简称*为乘法,而把x*y简记为xy,称为x 与y的积。 5.1.3特殊元素:单位元、零元、逆元 定义5.1.10 设*是集合S上的二元运算。 (1)若e l∈S,使得?x∈S,有e l*x=x,则称e l是关于运算*的左单位元(左么元); (2)若e r∈S,使得?x∈S,有x*e r=x,则称e r是关于运算*的右单位元(右么元); (3)若e∈S,使得?x∈S,有e*x=x*e=x,则称e是关于运算*的单位元(么元)。 定理5.1.3 设*是集合S上的二元运算,且e l,e r分别为关于运算*的左和右么元,则
第六章集合代数 1. 集合,相等,(真)包含,子集,空集,全集,幂集 2. 交,并,(相对和绝对)补,对称差,广义交,广义并 3. 文氏图,有穷集计数问题 4. 集合恒等式(等幂律,交换律,结合律,分配律,德·摩根律,吸收律,零律,同一 律,排中律,矛盾律,余补律,双重否定律,补交转换律等) 学习要求 1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示 2. 熟练掌握集合的交、并、(相对和绝对)补、对称差、广义交、广义并的定义及其性 质 3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法 4. 牢记基本的集合恒等式(等幂律、交换律、结合律、分配律、德·摩根律、收律、零 律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律) 5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式
6.1 集合的基本概念 一.集合的表示 集合是不能精确定义的基本概念。直观地说,把一些事物汇集到一起组成一个整体就叫集合,而这些事物就是这个集合的元素或成员。例如: 方程x2-1=0的实数解集合; 26个英文字母的集合; 坐标平面上所有点的集合; …… 集合通常用大写的英文字母来标记,例如自然数集合N(在离散数学中认为0也是自然数),整数集合Z,有理数集合Q,实数集合R,复数集合C等。 表示一个集合的方法有两种:列元素法和谓词表示法,前一种方法是列出集合的所有元素,元素之间用逗号隔开,并把它们用花括号括起来。例如 A={a,b,c,…,z} Z={0,±1,±2,…} 都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性,例如集合 B={x|x∈R∧x2-1=0} 表示方程x2-1=0的实数解集。许多集合可以用两种方法来表示,如B也可以写成{-1,1}。但是有些集合不可以用列元素法表示,如实数集合。 集合的元素是彼此不同的,如果同一个元素在集合中多次出现应该认为是一个元素,如{1,1,2,2,3}={1,2,3} 集合的元素是无序的,如 {1,2,3}={3,1,2} 在本书所采用的体系中规定集合的元素都是集合。 元素和集合之间的关系是隶属关系,即属于或不属于,属于记作∈,不属于记作,例如 A={a,{b,c},d,{{d}}} 这里a∈A,{b,c}∈A,d∈A,{{d}}∈A,但b A,{d} A. b和{d}是A的元素的元素。可以用一种树形图来表示这种隶属关系,该图分层构成,每个层上的结点都表示一个集合,它的儿子就是它的元素。上述集合A的树形图如图6.1所示。图中的a,b,c,d也是集合,由于所讨论的问题与a,b,c,d的元素无关,所以没有列出它们的元素。鉴于集合的元素都是集合这一规定,隶属关系可以看作是处在不同层次上的集合之间的关系。
代数系统 一、选择题: 1、下列正整数集的子集在普通加法运算下封闭的是( D ) A 、{30x x ≤} B 、{x x 与30互质} C 、{x x 是30的因子} D 、{x x 是30的倍数} 2、设S={1,2,…,10 },则下面定义的运算*关于S 非封闭的有( D ) A 、x*y=max(x ,y) B 、x*y=min(x ,y) C 、x*y=取其最大公约数 D 、x*y= 取其最小公倍数 3、设集合A 的幂集为()A ρ,-?I U 、、、为集合的交、并、差、笛卡尔乘积运算,则下列系统中是代数系统的为( D ) A 、()A ρI , B 、()A ρU , C 、(),A ρ- D 、(),A ρ? 4、在自然数集上定义的下列四种运算,其中满足结合律的是(C ) A 、a b a b *=- B 、||a b a b *=- C 、max{,}a b a b *= D 、2a b a b *=+ 5、设Z +为正整数集,*表示求两数的最小公倍数,对代数系统*A Z +=,,有( A ) A 、1是么元,无零元 B 、1是零元,无么元 C 、无零元,无么元 D 、无等幂元 6、设非空有限集S 的幂集为()S ρ ,对代数系统()A S ρ=I ,,有( B ) A 、Φ是么元,S 是零元 B 、Φ是零元,S 是么元 C 、唯一等幂元 D 、无等幂元 7、在有理数集Q 上定义的二元运算*: xy y x y x -+=*,则Q 中元素满足( C ) A 、都有逆元 B 、只有唯一逆元 C 、1x ≠时,有逆元 D 、都无逆元 8、设R 是实数集合,“?”为普通乘法,则代数系统
5.2 设S=Q×Q,其中Q为有理数集合。定义S上的二元运算*, ?,是[D]. (3)的幺元是[D]. (4)[E]. 供选择的答案 A、B:① <3,10>; ②<3,8>; ③ <-5,1>. C:④可交换的;⑤可结合的;⑥不是可交换的,也不是可结 合的. D:⑦ <1,0>;⑧ <0,1>. E:⑨只有唯一的逆元;⑩ a≠0时,元素有逆元。 答案:A=①;B=③;C=⑤;D=⑦;E=⑩ 5.3 R为实数集,定义以下6个函数f1 , f2 , ……,f6 , ?x,y ∈R 有 f1(
可结合的,D个是有幺元的,E个是有零元的。 供选择的答案 A、B、C、D、E:①0;②1;③2;④3;⑤4;⑥5;⑦6. 解:f1(
第九章代数系统 9.1 二元运算及其性质 一、二元运算与一元运算的定义 1.二元运算的定义与实例 定义9.1 设S为集合,函数f:S×S→S称为S上的二元运算,简称为二元运算。 验证一个运算是否为集合S上的二元运算主要考虑两点: (1)S中任何两个元素都可以进行这种运算,且运算的结果是唯一的。 (2)S中任何两个元素的运算结果都属于S,即S对该运算是封闭的。 例9.1 (1) 自然数集合N上的加法和乘法是N上的二元运算,但减法和除法不是。 (2) 整数集合Z上的加法、减法和乘法都是Z上的二元运算,而除法不是。 (3) 非零实数集R*上的乘法和除法都是R*上的二元运算,而加法和减法不是,因为两个非零实数相加或相减可能得0. (4) 设M n(R)表示所有n阶(n≥2)实矩阵的集合,即 则矩阵加法和乘法都是M n(R)上的二元运算。 (5) S为任意集合,则∪、∩、-、为S的幂集P(S)上的二元运算,这里∪和∩是初级并和初级交。 (6) S为集合,S S为S上的所有函数的集合,则函数的集合运算为S S上的二元运算。 2.一元运算的定义与实例 定义9.2设S为集合,函数f:S→S称为S上的一个一元运算,简称为一元运算。例9.2 (1) 求一个数的相反数是整数集合Z,有理数集合Q和实数集合R上的一元运算。 (2) 求一个数的倒数是非零有理数集合Q*,非零实数集合R*上的一元运算。 (3) 求一个复数的共轭复数是复数集合C上的一元运算。
S 可以用x x. x,y 3*4=3,(-5)*0.2=-5,0* a a a a i a 1
潍坊学院计算机系(院)讲稿专用纸 例9.4设S={1,2},给出P(S)上的运算~和的运算表,其中全集为S. 解:所求的运算表如表9.3和表9.4. 表9.3 表9.4 三.二元运算的性质 1.主要算律 定义9.3 设为S上的二元运算, (1)如果对于任意的x,y∈S,有x y=y x,则称运算在S上满足交换律。 (2)如果对于任意的x,y,z∈S有(x y)z=x(y z),则称运算在S上满足结合律。 (3)如果对于任意的x∈S有x x=x,则称运算在S上满足幂等律。 定义9.4设和*为S上两个不同的二元运算, (1)如果对于任意的x,y,z∈S有(x*y)z=(x z)*(y z)和z(x*y)=(z x)*(z y),则称运算对*运算满足分配律。 (2)如果和*都可交换,并且对于任意的x,y∈S有x(x*y)=x和x*(x y)=x,则称和*运算满足吸收律。 例9.5 表9.5和9.6给出了某些常见代数运算的性质,其中Z、Q、R分别代表整数集、有理数集、实数集,M n(R)表示n(n≥2)阶实矩阵的集合,A A是所有从A到A的函数的集合。 表9.5
第六章 几个典型的代数系统 本章讨论几类重要的代数结构:半群、群、环、域、格与布尔代数等.我们先讨论最简 单的半群. 6.1 半群 6.1.1半群的概念 定义6.1.1 设是代数结构,若?是可结合的二元运算,即: ?a ,b ,c ∈S ,(a ?b)?c=a ?(b ?c) 则称为半群; 定义6.1.2 设的运算?满足交换律,则称是可交换半群。 [例6.1.1] (1)是半群,T 为S 的非空子集。若T 关于运 算?封闭,则称的子半群。 定义6.1.5 设是独异点,T 为S 的非空子集。若T 关于运算?封闭,且e ∈T , 则称的子独异点。 [例6.1.2] , V 2=是两个半群,V 1与V 2的积代数V 1?V 2 = 其中S=S 1?S 2,,,,,2211><>*>=<><21212211,,,y y x x y x y x