《电子科大离散数学内部教学课件第12章代数系统》由会员分享，可在线阅读，更多相关《电子科大离散数学内部教学课件第12章代数系统（78页珍藏版）》请在金锄头文库上搜索。
1、离 散 数 学,电子科技大学,计算机科学与工程学院 示 范 性 软 件 学 院,2019年8月6日星期二,2019/8/6,第五篇 代数系统,由于数学和其他科学的发展，人们需要对若干不是数的事物，用类似普通计算的方法进行相似的计算。如矩阵、向量等。 研究代数系统的学科称为“近世代数”或“抽象代数”。,2019/8/6,第五篇 代数系统内容,2019/8/6,第十二章 代数系统,2019/8/6,12.1 本章学习要求,2019/8/6,代数运算,定义12.2.1 设A, B, C是非空集合，从AB到C的一个映射（或函数） ：ABC称为一个AB到C的二元代数运算，简称二元运算。,称自然数集合N上
2、的加法“+”为运算，这是因为给定两个自然数a, b, 由加法“+”，可以得到唯一的自然数c = a + b。 加法“+” 是映射吗？ N上的加法运算“+”本质上是一个NNN的映射,2019/8/6,代数运算,一个二元运算就是一个特殊的映射 ，该映射能够对aA和b B进行运算 ，得到C中的一个元c , 即 (a, b)c 。 中缀方法表示为 a bc,2019/8/6,例12.2.1,判别下面的映射或表是否是二元运算： （1）设A = 0, 1, B = 1, 2, C = 奇, 偶，定义映射: ABC，其中 (0, 1) = 奇， (0, 2) = 偶， (1, 1) = 偶， (1, 2)
3、= 奇。 分析 “”是一个AB到C的映射，因此，按定义12.2.1，则“”是一个AB到C的运算。,2019/8/6,例12.2.1（续）,（2）一架自动售货机，能接受五角和一元硬币，而所对应的商品是纯净水、矿泉水、橘子水，当人们投入上述硬币中的任何两枚时，自动售货机供应出相应的商品(右表)。,2019/8/6,例12.2.1（续）,分析 设集合A = 五角，一元，集合C = 纯净水，矿泉水，橘子水，则表12.2.1实质上是AAC的映射，也就是AA到C的一个运算“”。 解 (1)、(2)中定义的映射是二元运算。,2019/8/6,运算表,当集合A和B有限时，一个AB到C的代数运算，可以借用一个表
4、，称为运算表（乘法表 ）来说明。 设“”是AAC的运算，A = a1, a2, , an, B = b1, b2, , bm,则运算“”可用下表说明。,2019/8/6,定义12.2.2,设A1, A2, , An，A是非空集合，A1A2An到A的一个映射(或函数) ：A1A2AnA称为一个A1A2An到A的n元代数运算，简称n元运算。当n = 1时，称为一元运算。,2019/8/6,1元代数运算表,当元素有限时，一元运算也可以用运算表来说明。 设“”是A到A的一元运算，其中A = a1, a2, , an，则一元运算“”可以用右表说明。,2019/8/6,代数运算：封闭性,定义12.2.3
5、如果“”是AA到A的二元运算，则称运算“”对集合A是封闭的，或者称“”是A上的二元运算。 定义12.2.4 设“”是一个A1A2An到A的n元代数运算，如果A1A2AnA，则称代数运算“”对集合A是封闭的，或者称是A上的n元代数运算。,2019/8/6,说 明,一般通常用大写的英文字母表示集合，用符号“+”、“-”、“*”、“/”、“”、“”、“”、“”、“”、“”、“”、“”、“”、“+”、“”、“”等抽象的符号来表示一个抽象的运算。,2019/8/6,定义12.2.5,设A是非空集合，1, 2, , m分别是定义在A上k1, k2, km元封闭运算，ki是正整数，i = 1, 2, , m
6、。称集合A和1, 2, , m所组成的系统称为代数系统，简称代数，记为。 当A是有限集合时，该代数系统称为有限代数系统，否则称为无限代数系统,注意：判断集合A和其上的代数运算是否是代数系统，关键是判断两点：一是集合A非空，二是这些运算关于A是否满足封闭性。,2019/8/6,例子,(1) R上的“+”、“”运算； 解 构成一个代数系统R，+，； (2) p（S）上的“”、“”、“”运算； 解 构成代数系统,称集合代数； (3) 含有n个命题变元的命题集合A与A上的“”、“”、“”运算； 解 构成代数系统A，称之为命题代数。,2019/8/6,同类型代数系统,定义12.2.6 设和是两个代数系统
7、，若“oi”和“i”都是ki元运算，i = 1, 2, , m，则称这两个代数同类型。 如：代数系统Z，+,Z，,R，+,p（S），,p（S），都是同类型的代数系统。 代数系统I，+，、R，+，、 p（S），都是同类型的代数系统。,2019/8/6,子代数,定义12.2.7 设是代数系统，如果： （1）BA并且B ； （2）1, 2, , m都是B上的封闭运算。 则也是一个代数系统，称之为的子代数系统，简称子代数。又若B A，则称是的真子代数。,2019/8/6,子代数,子代数是抽象代数学中一个非常重要的概念，通过研究子代数的结构和性质，可以得到原代数系统的某些重要性质。 如在群论中，通过研究
8、子群可得群的某些性质。,注意：在后面章节中，将会学习半群、群、格、布尔代数等典型的代数系统。将子代数的概念应用到这些典型的代数系统，就会得到子半群、子群、子格、子布尔代数。因此，若没有必要，后面不再赘述某些典型代数系统中子代数的定义。,2019/8/6,例12.2.4,在代数系统中，令 Q = 5z | z Z， 证明是的子代数。 分析 根据定义，只需证明两点： （1）Q是非空子集；（2） “+”对集合Q封闭。 显然，集合Q非空。对任意的5z1，5z2Q，有 5z1 + 5z2 = 5(z1 + z2)Q， 因此“+”对集合Q封闭。 证明 略。,2019/8/6,12.3.1 二元运算律,例1
9、2.3.1 设“+”是定义在自然数集合N上的普通加法运算，试回忆N上的加法运算“+”满足哪些运算性质？ 分析 对 a, b, cN，有 (a + b) + c = a + (b + c)，即结合律成立； a + b = b + a，即交换律成立； x, yN，如果a + x = b + y，则x = y， 即消去律成立； 0N，0 + 0 = 0，即0是幂等元，但其他自然数不是幂等元，即不满足幂等律。,2019/8/6,结合律与交换律,定义12.3.1 设是二元代数系统，如果对任意的a, b, cA，都有 (a*b) *ca* (b*c) 则称“*”在A上是可结合的，或称满足结合律。 定义12
10、.3.2 设是二元代数系统，如果对任意的a, bA，都有 a * bb * a 则称“”在A上是可交换的，或称满足交换律。,2019/8/6,消去律,定义12.3.3 设是二元代数系统，元素aA， （1）对任意x, yA，都有 如果a x = a y，那么x = y， 则称a在A中关于“”是左可消去元； （2）对任意x, yA，都有 如果x a = y a，那么x = y， 则称a在A中关于“”是右可消去元；,2019/8/6,消去律（续）,（3）如果a既是A左可消去元又是右可消去元，则称a是A的可消去元； （4）若A中所有元素都是可消去元，则称“”在A上可消去，或称“”满足消去律。,2019
11、/8/6,幂等律,定义12.3.4 设是二元代数系统，若元素aA，满足 aa = a， 则称a是A中关于“”的一个幂等元，简称a为幂等元。若A中的每一个元素都是幂等元，则称“”在A中是幂等的，或称“”满足幂等律。,2019/8/6,幂等律,设“”是集合A上的二元运算，aA，则aaA，aaaA，,由此，可以归纳定义a的正整数幂方： a1 = a，a2 = aa，a3 = a2a，an = an1a， 对任意的正整数n，m，有以下等式： an am = an+m， （an）m = anm。,2019/8/6,分配律,定义12.3.5 ：设“”、“”是集合A上的二元运算，是一个代数系统， 对a,b,
12、cS，有 （1）a(b*c)=(ab)*(ac)， 则称运算“”对“*”在S上满足左分配律(或第一分配律)； （2) (b*c) a=(ba)*(ca)， 则称运算“”对“*”在S 上满足右分配律(或第二分配律) ； （3) 如果“”对“*”既满足左分配律又满足右分配律，则称”对“*”在S上满足分配律。,2019/8/6,吸收律,定义12.3.6 设“”、“”是集合A上的二元运算，是一个代数系统，如果对任意的x, yA，都有 x (x y) = x， x (x y) = x， 则称“”和“”满足吸收律,2019/8/6,特殊元,在代数系统中，有些元素有特殊性质，叫特殊元 。 例如在代数系统，其
13、中N是自然数，“”是普通加法，0 N ，并且对任意的自然数x N ，有 x0x0x,2019/8/6,幺元（单位元）,定义12.3.7 设是二元代数系统， （1）若存在eA，对任意aA，都有 a e = e a = a， 则称e是A中关于运算“”的一个幺元（单位元） （2）若存在elA，使得对任意aA，都有 el a = a， 则称el是A中关于运算“”的一个左幺元（左单位元） （3）若存在erA，使得对任意aA，都有 a er = a， 称er是A中关于运算“”的一个右幺元（右单位元）,2019/8/6,例12.3.5,下列代数系统是否存在幺元(左幺元或右幺元)，如果存在计算之。 （1），R
14、是实数集，“+”是加法运算； （2），R+是正实数集，“+”是加法运算； （3），其中P (AA)表示集合A上的所有二元关系集合，运算“”表示关系的复合； （4），其中A = a, b, c，二元运算“”,“”,“”如表12.3.2、表12.3.3和表12.3.4分别所示。,是一样的。,2019/8/6,例12.3.5（续）,分析 可以直接通过定义计算幺元，即首先假设幺元存在，然后计算之，最后验证所计算的元是否是幺元。,2019/8/6,例12.3.5（续）,（1）设x是的幺元，则由定义，对任意的aR，有 x + a = a， 让a = 1，有x + 1 = 1，则x = 0，xR。 这说明，
15、如果的幺元存在，那么幺元必是0。 对任意的aR，0 + a = a + 0 = a，即验证可得，0是的幺元。,2019/8/6,例12.3.5（续）,（2）设x是的幺元，对任意的aR+，有 x + a = a， 让a = 1，有x + 1 = 1，则x = 0，但0 R+。 这说明不存在幺元。同理，左、右幺元也不存在。,2019/8/6,例12.3.5（续）,（3）设X是的幺元，对任意的YP(AA)，有 XY = Y， 不妨令Y = IA，则XIA = IA，又XIA = X，因此X = IA。 这说明，如果的幺元存在，则幺元必是IA。 对任意的YP(AA)， IAY = Y IA = Y， 即验证可得IA是的幺元。,2019/8/6,例12.3.5（续）,（4）由于给出了运算表，因此可以根据运算表直接观察可得。 解（1）中的幺元是0； （2）中无幺元； （3）中的幺元是恒等关系IA； （4）中关于运算“”有左幺元a和b，但无右幺元，因此无幺元，关于运算“”无左幺元，但有右幺元b和c，因此无幺元；关于运算“”有幺元a。,2019/8/6,结论,（1）计算幺元可根据定义直接进行，即首先
