离散数学第六章群.pptVIP

第六章? 代数 这里“代数”二字不是我们中学阶段所学的代数，那里的代数是指用字母代替数字。这里的代数是代数系统或代数结构的简称。主要内容是群、环、域，由于它们极其抽象和现代科学思想的含量高，所以也把这些代数内容称为抽象代数或近世代数，当然，它的源头既不十分深奥也不十分抽象，只是算术中实数范围四则运算或线性代数与微积分当中一些具体集合之上的特殊运算的共性，但当它准确地概括了这些古典的，大部分是初等的运算的本质之后，则获得了一种神奇的抽象力量，被广泛 而有效地应用于数学科学内部各分支和物理学、化学等物质科学时，尤其突出的是它用于离散数学的方方面面之后，收到了令人惊喜的成果！例如用群的理论解决各种记数问题，用域的理论解决区组设计等等，在计算机和信息科学的有关部分，如形式语言和自动机、数据安全、编码等学科有关的部分有重要的作用。 6.2? 子代数 定义：设A,*为代数，S?A，若?a,b∈S，有a*b∈S，则称S,*为A,*的子代数。 例5：设E为偶数集合，则 E,+是I,+的一个子代数。?????设M为奇数集合，则 M,?是I,?的一个子代数， 但M,+不是I,+的一个子代数。 例6：R，+与R+，?同构。 定理：设A,*、B,⊙都是代数,A和B同态,若A,*满足交换(结合)律,则B,⊙也满足交换(结合)律. 6.4 同余关系 ?? I,+是代数，整数模3的关系E是等价关系，?? 记[0]={3k}， [1]={3k+1}， [2]={3k+2}，k为整数。?? 1 E 4，2 E 5，有(1+2) E(4+5)，?? ?a,b,c,d∈I， 若a E b,c E d,有(a+c) E(b+d)。 ?? 例8：自然数集N上的关系R：????? xRy当且仅当存在m∈I，使得x=2m * y证：? ?x∈N，x=20 * x， ∴ xRx，R自反， 若xRy，x=2m * y，y=2-m * x，yRx，R对称， 若xRy，yRz，x=2m * y，y=2n * z，x=2m+n * z，xRz，R传递。?? ∴ R是N上的等价关系。?? 1R2，3R3，但(1+3)与(2+3)不满足关系R， ∴R不是N,+上的同余关系。 6.5? 商代数和积代数 商代数 ? 定义：若E是A,*上的同余关系，? A/E={[a]?a∈A} 在A/E上定义运算?，? ?[a],[b]∈A/E，[a]?[b]=[a*b] 称A/E，?为A,*关于同余关系E的商代数。 定理：若E是A,*上的同余关系，则A,*与商代数A/E，? 满同态。 定理：若f是A,*到B,# 的满同态映射,则A/Ef,?与B,# 同构。 证明：作映射h：A/Ef?B????? [a]?f(a) 即h([a])=f(a) 积代数 定义：设A,*和B，#是两个代数，在A?B上定义运算??? ?a,b,c,d∈A?B， a,b?c,d=a*c, b#d???? 称A?B,?为 A,*和B，#的积代数。 P182例 6.6 半群和独异点 定义：设S,*为代数，若S,*满足结合律，则称S,*为半群。 例9：I,+，I, ?都是半群。 设E为偶数集，E,+，E, ?都是半群。 代数I,-不是半群。 （2）a的象的逆元等于a的逆元的象 证明： ?a∈A，a*a-1=a-1*a=e，???????? f(a*a-1)=f(a-1*a)=f(e)=e‘???????? f(a)?f(a-1)=f(a-1)?f(a)=e’??? ∴(f(a))-1=f(a-1) 。 考察一阶群、二阶群、三阶群、四阶群、五阶群、六阶群，P.191.? 正规子群和商群 定义：设H,*是群G,*的子群， ? a∈G， 若aH=Ha,则称H,*是群G,*的正规子群。 例6 P.200. 定义：设H,*是群G,*的正规子群， ? a，b∈G， 定义aH⊙bH=(a*b)H， 记G/H={aH | ?a∈G}， 则称群 G/H ,⊙为群G,*关于正规子群H,*的商群。 可以证明 H为群 G/H ,⊙的幺元， （aH）-1 = a-1H . 习题课 注： 以下习题中 |a| 表示元素a的阶。 习题课 主要内容 ： 1.函数 f：S×S→S 和 f：S→S 分别定义了S上的二元和一元运算。 2.?使用算符表示二元和一元运算有两种表示法：解析公式与运算表。 3.?二元运算的算律（交换律、结合律、幂等律、分