离散数学第四章4.pptVIP

第六章 几个典型的代数系统 半群与群 6.1 半群与群 3 群的定义 例1 例2 4 群的分类 5 群 的 性 质 6 元素的阶 7 子群的定义与判别定理 例4 x的生成子群 8 特殊的群 (3) 轮换及其乘法 (4) 6.3 格与布尔代数 4 格中∨和∧两种运算的性质 5 格的第二定义 6 一些特殊的格 3) 有补格 4)布尔格(或称布尔代数) ： 格与布尔代数 1 若?在G上成立结合律,则称V为半群。 2 若?在G上成立结合律, 且有单位元，则称V为独异点（含幺半群）。 设V=(G,?)是一个代数系统, ?是G上的二元运算, 如：〈Z+, +〉, 〈N, +〉, 〈Z,+〉 如： 〈N, +〉, 〈Z,+〉 若?在G上成立结合律, 有单位元,且 G中每个元素存在逆元 则称〈G,*〉为群。 常见的群：〈Z, +〉,〈Q, +〉,〈R, +〉,〈Zn, ⊕〉 群 独异点 半群 代数系统 e a b c c a e c b b b c e a a c b a e e c b a e * 称为Klein四元群. 设G={e,a,b,c}运算*表如下，判断G,*的类型. 设R上定义*运算为x*y=x+y-2,验证R,*构成群. 无限群： 有无限多个元素的群； 注：仅由单位元构成的群称为平凡群. 即 {e} 有限群：元素个数为有限个的群；其元素个数称为G的阶，记为|G|. ?a,b?G,方程a*x=b和x*a=b,在G中存在唯一解； 群中适合消去律； 元素的幂的定义： x0=e, xn+1=xn?x, x-1=x的逆元 使xk=e成立的最小正整数k称为x的阶. 例3 (模n的剩余类加法群) 求Z6, ?中各个元素的阶. 1) 设(G,*)是群,H?G,若H,*构成群,则称H为G的子群。记作H≤G。 2) 判别定理 设(G,*)是群 ,非空集合 H?G, ?x,y?H, 均有x* y-1?H (1)如果a, b?H,则a*b?H; (2)若a?H,则a-1?H . H≤G ? H≤G ? 有限集合H≤G ? ?x,y?H, 均有x* y?H 求Klein四元群的所有子群. e a b c c a e c b b b c e a a c b a e e c b a e * 平凡子群 非平凡子群 x={xk| k?Z} 例5 求Z, +中元素0，1，3的生成子群 1） 如果(G,*)中的二元运算是可交换的,则称(G,*)是交换群, 又称Abel群。 2）设(G,*)是群,如果存在一个元素a∈G,使G＝｛ak｜k∈Z｝,则称G为循环群,a是G的生成元,并记作G＝〈a〉。 S={1,2,3,…,n}到自身的双射称为n元置换,记为?，可表示为 注：S上的双射即置换的个数共n!个,S上置换的全体记作Sn 例 设f=(15342), g=(125)(34) 求f?g, g ?f, f-1, g-1 设M是非空集合,有n个元素,M上所有置换的集合关于置换的乘法(函数的复合运算)构成一个群,称为n元对称群， 例题: S3是3元对称群。 它的任何子群称为n元置换群。 1 设(L,≤)是一个偏序集,如果?a,b?L, {a,b}存在最大下界和最小上界,则称(L,≤)是格(L关于偏序≤构成格)。 设 x∧y 表示 x∨y 表示 X与y的最大下界. X与y的最小上界. 显然 x∧y ≤ x ≤ x∨y x∧y ≤ y ≤ x∨y 2 设f是含有格中元素以及符号=,≤,≥，∨和∧的公式，令f*是将f中的符号分别替换成=， ≥ ,≤, ∧与∨所得到的公式，则称f*为f的对偶命题。 3 对偶原理：f* ? f 设〈L, ≤〉为格，则运算∨和∧适合 （1） 交换律 （2） 结合律 （3）幂等律 （4）吸收律 通过代数格〈 L ， *， ? 〉可以构成偏序格〈 L ，≤〉，且?a, b ?L有a∧b=a*b, a∨b=a ? b. 注： 设〈 L ， *， ? 〉是代数系统，*，?是L中的两个二元运算，并满足交换律、结合律和吸收律 ，则〈 L ， *， ? 〉构成一个格（或称代数格）. 1) 若 ?a,b,c?L,有 a∧(b∨c)= ( a∧b ) ∨ ( a∧c) 则称L为分配格. 2) 若 ?a,?b?L, a≤b则称a为L的全下界, 记为0; 设〈L,∧, ∨ 〉为格， 若 ?a,?b?L, b≤ a则称a为L的全上界, 记为1; 具有全下界和全上界的格称为有界格. 注：常记为L, ∧, ∨ ,0,1