离散数学与-5-3 半群 .pptVIP

第五章 代数结构 5-3 半群 授课人：李朔 Email:chn.nj.ls@ 一、广群与半群 半群是一种特殊的代数系统，在计算机科学领域中，如形式语言，自动机理论等方面，已得到了卓有成效的应用。 定义5-3.1 S, *为一个代数系统，集合S ? ?。*是S上的一个二元运算，如果运算*是封闭的，则称代数系统 S, *为广群。 定义5-3.2 若S, *为广群，且*在S上可结合，，则称S, *为半群。 例如： 1）幂集P（A）上对称差运算构成半群。 2）设Z为整数集，+、-、*是数的加法、减法和乘法，则（Z， +）、（Z，*）都是半群；（Z，-）不是半群。 3）Nk= {0, 1, 2, ?, k-1}上模k加法成半群。 一、广群与半群 例题2 设S = {a,b,c}, S上的一个二元运算的定义如下表所示，验证＜S, △＞是半群。 一、广群与半群 定理5-3.1 设S, *是一个半群，B?S且*在B上封闭，则B, *也是一个半群，通常称为S, *的子半群。 证明：因*在S上可结合，而B?S，且*在B上封闭，故*在B上可结合，故B,*为半群。 例如：?为普通乘法，则[0,1], ?, 0,1都为R,?的子半群。 定理5-3.2 若S, *为半群，且S是有限集，则必有a?S, 使a*a=a。 证明：对任b?S, 由封闭性知 b*b = b2 ? S, b3 = b2*b ? S, 即是说序列 b, b2, b3, …, bi … bj …都为S中元 一、广群与半群 因S有限，故存在ji使 bi = bj 设 P = j-i 则 bj = bp*bi = bi 故 bp*bi*b = bi*b 即 bp*bi+1 = bi+1 对 qi有 bp*bq = bq 由于 p?1 ，故存在k?1使kp ? i 即 bp*bkp = bkp 这是一个递推关系，即 bkp = bp*bkp = bp* (bp*bkp) = … = bkp*bkp 令 bkp = a，即有a*a = a。 *本定理说明有限半群必有幂等元。 二、独异点 定义5-3.3 含有幺元的半群称为独异点。有时独异点也记S,*,e。 例：（?是普通乘法，+是普通加法） R, +, 0，I, ?，I+,?，R, ?都为独异点。 N-{0}, + 为半群，不含幺元0，故不是独异点。 代数系统＜{－1，1}，?＞，＜[－1，1]，?＞，和＜Z , ?＞都是具有幺元1的半群。因此它们都是独异点。 定理5-3.3 设S, *为独异点，则关于*的运算表中任何两行或两列都不同。 证明：设e为幺元。对任a, b?S, a?b a*e = a ? b*e = b 可见a, b所在行不同。 同理 e*a = a ? e*b = b 即a, b所在列也不同。 二、独异点 例：I为整数集，Zm为同余类构成的集合，定义+m, ?m如下： [i], [j] ? Zm [i]+m[j] = [ (i + j) mod m ] [i]?m[j] = [ (i ? j) mod m ] 试证明这两个运算表中任两行，两列互异。 证明：（这仅需证明 Zm , +m , Zm , ?m 都为独异点即可。） 事实上： 1）+m, ?m在Zm上封闭。 2）对任[ i ], [ j ], [ k ]? Zm ([i] +m [j] ) +m [k] = [i] +m ([i] +m [j]) = [(i + j + k ) mod m ] ( [i] ?m [j] ) ?m [k] = [i] ?m ( [i]) ?m [j] ) = [(i ? j ? k ) mod m ] 故+m, ?m都可结合。 二、独异点 3） [0] +m [i]= [i] +m [0] = [i] [1] ?m [i]= [i] ?m [1] = [i] 即[ 0 ]，[ 1 ]分别为+m, ?m的幺元。 因此 Zm , +m , Zm , ?m 都为独异点。由定理5-3.3可知，这两个运算的运算表中任何两行或两列都不相同。 二、独异点 由定理知其运算表任两行，两列互异。在上例中，如果令m=5，则+5和?5的运算表分别如下。（没有两行/列是相同的） 二、独异点 定理5-3.4 S, * 为独异点，若对任a, b?S，且a, b有逆元a-1, b-1, 则 1）(a-1)-1 = a 2）a*b有逆且(a*b)-1 = b-1 * a-1。 证明： 1）因a有逆a-1，故 a * a-1 = a-1* a = e 因此(a-1)-1 = a 2）因 (a * b) * (b-1 *