自考离散数学第4章

1、离散数学,第四章 代数结构,主要内容 4.1代数系统 4.2半群与独异点 4.3群与子群 4.4环与域 4.5格与子格 4.6分配格与有补格 4.7布尔代数,4.1 代数系统,世界上各种事物的作用，实际上都可以看作是运算。 定义4.1.1 设A，B为任意集合，一个从An到B的映射，称为集合A上的一个n元运算。如果B A，则称该n元运算是封闭的。 在n元运算中，经常遇到的是二元运算。而且在A上对该运算是封闭的。 例：整数集合上的加法、减法、乘法是Z上的二元运算。 例：设A为任意集合，则U,，-、 为A的幂集P(A)上的二元运算。 定义4.1.2 一个非空集合A，连同若干个定义在该集合上的运算f1

2、,f2,f3,.,fk所组成的系统，就称为一个代数系统，记作,4.1 代数系统,例:设R为实数集f：RnR， ，有f()=x3,则f是R上的n元运算，它也就是求一个n维向量的第三个分量的运算，这个n元运算也可以用算符*描述：*(x1,x2,.,xn)=x3. 习惯上对于二元运算，则把运算符置于两个运算元素之间，即把*(x1x2)写为：x1*x2 对于一元运算常以算符 表示，可写成：x或 x 当集合A为有穷集时，A上的一元运算和二元运算，可以用运算表给出。 例：设B=1,2,P(B)上二元运算 和的运算表：,4.1 代数系统,定义4.1.3 设A为任意非空集合，*是集合A上二元运算。 封闭性：对

3、任意a，b A，若有a*b A,则称运算*关于集合是封闭的。 结合律：对任意a，b，c A，若有a*(b*c)=(a*b)*c,则称运算*在集合A上是可结合的，或称运算*在A上满足结合律。 交换律：对任意a，b A，若有a*b=b*a,则称运算*在集合A上是可交换的，或称运算*在A上满足交换律。 幂等率：若对 a A，有a*a=a,则称运算*在A上是幂等的，或称运算*在A上满足幂等律。 分配律：若对任意a，b，c A，若有a(b*c)=(ab)*(ac)和(b*c)a=(ba)*(ca),则称运算对*在集合A上是可分配的，或称运算对*在A上满足分配律。 吸收律：若和*满足交换律且有：任意a，b

4、 A，并有a(a*b)=a,a*(ab)=a,则称运算对*在集合A上是可吸收的，或称运算对*在A上满足吸收律。,4.1 代数系统,例：实数集R上有二元运算，对所有x，y R，定义xy=x+y-2xy，可以验证 运算是可交换的、可结合、幂等的吗？ 解：可交换、可结合、但不是幂等的。 例：实数R上的乘法对加法是可分配的，但加法对乘法不满足分配律。加法和乘法在实数集上分别是可交换、可结合的。 例：集合B上的幂集P(B)上的U和是互相可分配的，并且满足吸收律。,4.1 代数系统,4.1 代数系统,定义4.1.4 设*为集合A上二元运算，若存在eL A（或er A），使得对于任意x A，都有eL*x=x

5、（x*er=x）,则称eL（或er）是A中关于*运算的左（或右）幺元（或单位元）。 如果A中一个元素e，它既是左幺元，又是右幺元，则称e是A中关于运算*的幺元。 例：设集合A=a,b,c,d,在A上定义两个运算*和 ，如表所示： 解：b,d是A中关于*运算的左幺元，而a是A中关于 运算的右幺元。,4.1 代数系统,定义4.1.5 设*为集合A上二元运算，若有一个元素OL A（或Or A），使得对于任意x A，都有OL*x=OL（x*Or=Or）,则称OL（或Or）是A中关于*运算的左（或右）零元。 如果A中一个元素O，它既是左零元，又是右零元，则称O是A中关于运算*的零元。 例：设有代数系统,

6、其中I是整数集合，“”是普通乘法，则对于任意x I均有0 x=x0=0，所以0是关于运算的零元。 定理4.1.1 设*是集合A上的二元运算，且在A中有关于运算*的左幺元eL和右幺元er，则eL=er=e，且A中幺元是唯一的。 定理4.1.2 设*是定义在集合A上的二元运算，在A中有关于运算*的左零元OL和右零元Or，则OL=Or=O，且A中零元是唯一的。 定理4.1.3 设有代数系统中，A的元素个数多于1，若其存在关于运算*的单位元e和零元O，则eO。,4.1 代数系统,定义4.1.6 设代数系统中，e是关于*运算的单位元，若对A中某个元素a，存在A的一个元素b，使得b*a=e,则称b是a的左

7、逆元；a*b=e,则称b是a的右逆元。如果一个元素b，它既是a的左逆元，又是a的右逆元，则称b是a的一个逆元，记作b-1 例：设A=a,b,c,d，*为A上的二元运算， 可以看出a为单位元。由a*a=a,b*c=a,c*b=a,d*b=a, 故a有逆元a；b有左逆元c，d；c有左逆元b；b有右逆元c；c有右逆元b；d有右逆元b。其中b是c的逆元，c是b的逆元。 一个元素的左逆元不一定等于它的右逆元，而且一个元素可以有左（右）逆元而没有右（左）逆元。一个元素的左右逆元也不一定是唯一的。,4.1 代数系统,4.1 代数系统,4.1 代数系统,4.1 代数系统,定理4.1.4 设代数系统,这里*定义

8、在A上的二元运算，A中存在幺元e，且每一个元素都有左逆元。如果*是可结合运算，那么这个代数系统中，任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元是唯一的。 在上面提到的一些代数系统中，存在一些特定元素，它对该系统的一元或二元运算起着重要作用，如二元运算的单位元和零元等，称这些元素为特异元素或代数常数。 有时为了强调这些特异元素的存在，也把它写入代数系统中，例如：中，为了强调+运算的单位元O，可将记为. 定义4.1.7 如果两个代数系统中运算的个数相同，对应运算的元数也相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。 例：V1=,V2

9、=,称V1和V2是同类型的代数系统。,4.1 代数系统,定义4.1.8 设V=是代数系统，B S，且B对f1,f2,.,fk都是封闭的，B和S还含有相同的代数常数，则称是V的子代数系统，简称子代数。 例：是的子代数，又如是的子代数，因为N对+运算是封闭的，且它们都含有相同的代数常数。,4.2 半群与独异点,定义4.2.1 设*是集合S的上的二元运算，若运算*是封闭的，并且*是可结合的，则称这个代数系统为半群。 这个定义包括两点，即对任意a，b，c S， （1）a*b S （2）a*(b*c)=(a*b)*c 例：设S=a,b，*是S上的二元运算：a*b=b*b=b,a*a=b*a=a，试判断是

10、否为半群。 解：a*b=b*b=b S,a*a=b*a=a S，所以*在S上是封闭的。又设任意a,b,c S有，a*(b*c)=a*(c*c)=a*c=c,c=b*c=(a*b)*c,所以*在S上是可结合的。所以为半群。,4.2 半群与独异点,定理4.2.1 设为一个半群，B S，且运算*在B上是封闭的，那么也是一个半群，通常称是半群的子半群。 定义4.2.2 若半群中存在一个幺元，则称为独异点。（或含幺半群） 定理4.2.2 设是独异点，对于a，b S，且a，b均有逆元，则： (1)(a-1)-1=a (2)若a*b有逆元，则(a*b)-1=b-1*a-1,4.2 半群与独异点,4.3 群与

11、子群,定义4.3.1 设为一个代数系统，其中G是非空集合，*是G上一个二元运算， 如果*是封闭的； 运算*是可结合的； 存在幺元e； 对于每一个元素x G，存在它的逆元x-1； 则称是一个群。,4.3 群与子群,4.3 群与子群,定义4.3.2 设为一个群，如果G是有限集合，则称是有限群。G中元素的个数通常称为有限群的阶数，记为|G|。 定义4.3.3 若群G中，只含有一个元素，即G=e,|G|=1,则称G为平凡群。 例：设G=e,a,b,c,运算*如表所示： 验证是一个群。 解：*运算容易验证是可结合的，e是G中的单位元，对任意x G，x-1=x。G关于*运算，构成一个群，这个群称作Klei

12、n四元群。,4.3 群与子群,定义4.3.4 设为一个群，若运算*在G上满足交换律，则称G为交换群或Abel群。 定义4.3.5 设为一个群，若a G，使得ak=e成立的最小正整数k称为a的阶，记作|a|。 例：Klein四元群中，该群的阶数|G|=4,但是|e|=1，|a|=|b|=|c|=2,4.3 群与子群,4.3 群与子群,4.3 群与子群,定理4.3.1 设为一个群，任意a,b G，有： (a-1)-1=a (ab)-1=b-1a-1 anam=an+m (an)m=anm 若G为Abel群，(ab)n=anbn,n Z,4.3 群与子群,4.3 群与子群,定义4.3.6 在代数系统

13、中，如果存在a G，有a*a=a,称a为幂等元。 定理4.3.2 在群中，除幺元e外不可能有任何别的幂等元。 证明：因为e*e=e,所以e是幂等元。 现设a G，ae，且a*a=a,则有a=e*a=(a-1*a)*a=a-1*(a*a)=a-1*a=e 与题设的ae矛盾。 定理4.3.3 对|G|1的群中不可能有零元。 证明：设为群，若|G|=1,它的唯一元素视作幺元，同时为零元。 设|G|1，且群有零元O,对群中任何元素x G，都有x*O=O*x=Oe,所以零元O就不存在逆元，与为群相矛盾。,4.3 群与子群,4.3 群与子群,定理4.3.4 设为一个群，对于a,b G.必存在唯一的x G，

14、使a*x=b。 证明：因为为一个群，对于任一a G，必有逆元a-1，令x=a-1*b, 则a*x=a*(a-1*b)=(a*a-1)*b=e*b=b 若另有一解x1，满足a*x1=b,则a-1*(a*x1)=a-1*b,即x1=a-1*b,故x=x1 定义4.3.7 设为群，若在G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称该群为循环群，元素a称为循环群G的生成元。 在循环群中,G的阶为有限时，称为有限循环群，否则称为无限循环群。,4.3 群与子群,例：群,中G=a,b,c,d,e，其运算表如下，证明它是循环群。 因为a=a,b=a2,c=a3.d=a4,e=a5，生成元为a； 因

15、为b=b,d=b2,a=b3.c=b4,e=b5，生成元为b； 因为c=c,a=c2,d=c3.b=c4,e=c5，生成元为c； 因为d=d,c=d2,b=d3.a=d4,e=d5，生成元为d； 上例说明，一个循环群的生成元可以不止一个，即不是唯一的。,4.3 群与子群,4.3 群与子群,定义4.3.8 设为一个群，S是G的非空子集，如果也构成群，则称是的一个子群，记作SG 定理4.3.5 设为群，H是G的非空子集，则HG，iff 任意a,b H,有a*b H 任意a H ,有a-1 H 定理4.3.6 设为群，H是G的非空子集，则HG，iff 任意a,b H,则a*b-1 H 证明：必要性显

16、然。 现证充分性：因为H非空，故必有b H,按已知条件，则有b*b-1 H,即e H.任取a H，由e H，a H，则有e*a-1=a-1 H,任取a，b H。类似上面的证明有b-1 H，故由条件得：a*(b-1)-1 H,H G,即a*b G,故H是G的子群。,4.3 群与子群,定理4.3.6 设为群，H是G的有穷非空子集，则HG，iff 任意a,b H,则a*b H 例：设为群，C=a|a G，且对任意x G有a*x=x*a,C亦称为CentG。求证：C G 证明：CentG，因为eG CentG， 对于任意a，b CentG,对任意x G有a*x=x*a,b*x=x*b, 故(a*b-1

17、)*x=a*(b-1*x)=a*(x-1*b)-1=a*(b*x-1)-1=a*(x*b-1)=(a*x)*b-1 =(x*a)*b-1=x*(a*b-1) 因此a*b-1 CentG,故C G,4.3 群与子群,4.4 环与域,定义4.4.1 设是一个代数系统，如果满足 是阿贝尔群； 是半群； 运算*对于运算+是可分配的； 则称是环。 例：,都是环。,4.4 环与域,定义4.4.2 设是环，对于a,b R,a0,b0,但ab=0，则称a是R中的一个左零因子，b是R中的右零因子；若一个元素既是左零因子，又是右零因子，则称它是一个零因子。 例：模6的整数环中，3 4=0 定义4.4.3 设R是一

18、个环，对于任意的a,b R，若ab=0，则a=0或b=0，就称R是一个无零因子环。 定义4.4.4 设是环，如果设可交换的，则称是可交换环。 定义4.4.5 设是一个代数系统，若满足： 是阿贝尔群； 是可交换独异点，且无零因子 运算*对+是可分配的。 称是整环。,4.4 环与域,定义4.4.6 设是一个环，且|R|2， R有幺元； 每个非零元有逆元； 则称这个环为除环。 如果一个除环可交换时，称之为域。 当为域时，及是阿贝尔群。,4.4 环与域,4.5 格与子格,定义4.5.1 设是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称为格。 定义4.5.3 设是一个格，如果在A上定义两个二元运算和，使得对任意a,b A,ab等于a和b的最小上界，ab等于a和b的最大下界。称为格所诱导的代数系统。,4.5 格与子格,定义4.5.5 设是格，S是L的非空子集，若S关于运算和是封闭的，则称是格L的子格。 例：设是一个格，S=a,b,c,d,e,f,g,h，如图。取S1=a,b,d,f，