离散数学离散数学 (5).pdf

《离散数学离散数学 (5).pdf》由会员分享，可在线阅读，更多相关《离散数学离散数学 (5).pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Group theory群理论内容回顾：1、代数系统 2、7种性质：封闭性，交换律，结合律，分配律，消去律，吸收律，等幂律；3、4个特出元素：单位元，逆元，零元，幂等律；4、满同态映射下两个系统之间具有“6类保持”.代数系统代数系统半群半群含幺半群含幺半群群（环，域）群（环，域）群群,环环,域域格与布尔代数格与布尔代数Chapter 5群群 Group theory5.1 半群5 5.1 1.1 1半群的定义半群的定义定义：定义：设设 是一个代数系统，如果是一个代数系统，如果*运算满足运算满足结合律，则称结合律，则称 是一个半群。是一个半群。举例：举例：,，半群，半群,不能构成半群，运算不满足

2、结合律不能构成半群，运算不满足结合律5.1 半群举例：举例：，n是大于等于是大于等于1的正整数。的正整数。),(nMR举例：举例：，S非空集合，非空集合，是集合的对称差。是集合的对称差。P(S)幂集幂集以上系统都可以组成半群。以上系统都可以组成半群。举例：举例：，n是大于等于是大于等于1的正整数。的正整数。),(nMR)(nMR实系数方阵实系数方阵举例：举例：，A非空集合非空集合,是函数的复合运算。是函数的复合运算。AAAA所有函数所有函数5.1 半群例：假设例：假设S=a,b,c，在在S上定义运算上定义运算，如如运算表给出运算表给出。证明证明是半群是半群。b a c a b c c b a

3、c b a c b a 验证验证运算是可结合的。(a b)c=a c=c，a (b c)=a c=c所以(a b)c=a (b c)(b a)c=b (a c)。等所以 运算满足结合律，是半群是半群5.1 半群例：例：，在在N上定义运算上定义运算，如下：如下：a b=a+b+a*b,证明证明 是半群；是半群；定义定义如下：如下：a b=a+b-a*b,如何如何？(a b)c=(a b)+c+(a b)*c=(a+b+a*b)+c+(a+b+a*b)*c=a+b+c+a*b+a*c+b*c+a*b*ca (b c)=a+(b c)+a*(b c)=a+(b+c+b*c)+a*(b+c+b*c)=

4、a+b+c+a*b+a*c+b*c+a*b*c封闭性不一定满足a (b c)=？满足结合律 a (b c)=(a b)c5.1 半群5 5.1 1.1 1半群的定义半群的定义定义：定义：假设假设 是一个半群，是一个半群，aS，n 是正整数，则是正整数，则an表示表示 n 个个 a 的计算结果，即的计算结果，即 an=a*a*a对任意的正整数对任意的正整数 m,n，am*an=am+n，(am)n=amn5.1 半群5.1.2交换半群定义：如果半群如果半群 中的中的*运算满足交换律，则运算满足交换律，则称称 为交换半群。为交换半群。在交换半群在交换半群 中，若中，若a,bS，n 是任是任意正整数

5、，则意正整数，则(a*b)n=an*bn5.1 半群5 5.1 1.3 3 独异点独异点（含幺半群含幺半群）定义：假设假设 是一个半群，如果是一个半群，如果 中有中有单位元单位元e，则称则称 是独异点，或含幺半群。是独异点，或含幺半群。,是是独异点吗？独异点吗？,是是独异点吗？独异点吗？都可以构成都可以构成独异点（含幺半群）独异点（含幺半群）+的单位元是的单位元是0，的单位元是的单位元是1都不能构成都不能构成独异点（含幺半群），没有独异点（含幺半群），没有单位元单位元下列各代数系统是否可以构成独异点（含幺半群）？下列各代数系统是否可以构成独异点（含幺半群）？举例举例1：，n是大于等于是大于等于

6、1的正整数。的正整数。),(nMR举例举例2：，n是大于等于是大于等于1的正整数。的正整数。),(nMR举例举例3：，A非空集合，非空集合，是函数的复合运算。是函数的复合运算。AA构成构成独异点，单位元是“零矩阵”独异点，单位元是“零矩阵”构成构成独异点，单位元是“单位矩阵独异点，单位元是“单位矩阵”构成构成独异点，单位元是“恒等函数独异点，单位元是“恒等函数”，IA5.1 半群5 5.1 1.3 3 独异点独异点（含幺半群含幺半群）定理：定理：假设假设 是独异点，如果是独异点，如果a,bS，并且，并且 a,b 有有逆元逆元 a-1,b-1存在，则：存在，则：（1）(a-1)-1=a；（2）(

7、a*b)-1=b-1*a-1。证明：是独异点，单位元一定存在是独异点，单位元一定存在e S，a-1*a=a*a-1=e；所以有(a-1)-1=a(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=a*a-1=e所以(a*b)-1=b-1*a-15.1 半群5 5.1 1.4 4 子半群子半群定义：假设假设 是一个半群，若是一个半群，若 TS，且在且在*运运算下也构成半群，则称算下也构成半群，则称 是是 的子半群。的子半群。假设假设A=a,b，是一个含幺半群是一个含幺半群。a,b a,b b a a b a b a b a b a,b 若若B=a 则则P(B)P(A)并且

8、并且构成半群，是构成半群，是的子的子半群。半群。还有否？还有否？若若B=b,则则P(B)P(A)5 5.1 1.4 4 子半群子半群5.1 半群5 5.1 1.4 4 子半群子半群定义：定义：设设 是含幺半群，若是含幺半群，若 是它的子半是它的子半群，并且群，并且 的单位元的单位元 e 也是也是 单位元，单位元，则称则称 是是 的子含幺半群。的子含幺半群。5.1 半群例：设例：设是可交换的含幺半群是可交换的含幺半群，T=a|aS，且且a*a=a，则则是是的子含幺半群的子含幺半群。解：解：(1)封闭 对a,bT a*a=a,b*b=b,(a*b)*(a*b)=a*b*a*b=a*a*b*b=a*b a*b T(2)可结合*本来就是可结合的(3)单位元与S是同一个 e*e=e;eT 是是的子含幺半群的子含幺半群 代数系统，代数系统，(1)半群；半群；(2)幺半群幺半群(独异点独异点)；(3)子半群；子半群；(4)子含幺半群子含幺半群小结