离散数学 第09章 代数系统.ppt

代数结构主讲 艾施荣 2 第三篇 代数结构目录 第八章半群 语言和自动机8 1半群和语言8 2语言和文法8 3有限状态机8 4有限状态自动机8 5语言与自动机的关系实验八 设计输出状态自动机第八章习题第九章代数系统9 1代数系统的概念9 2代数系统的运算及其性质9 3群与子群9 4同态与同构9 5交换群与循环群置换群 9 6子群与群的陪集分解9 7环与域实验九 代数系统的基本运算第九章习题第十章格与布尔代数10 1格的概念10 2分配格 有补格与布尔代数10 3分配格10 4有补格10 5布尔代数与布尔表达式10 6数字电路与最小化实验十 代数系统综合课程设计第十章习题 3 第九章 代数系统 主要内容 构成代数系统的基本成分 二元运算性质和特异元素 同类型的与同种的代数系统 群的定义 实例与术语 群的基本性质 子群的判别定理 陪集的定义及其性质 子群与群的陪集分解 环与域 教学要求 理解代数系统 群 环与域的概念 理解同态与同构 交换群与循环群置换群的区别 理解子群与群的陪集分解 重点 代数系统 群的定义与性质 子群 陪集与拉格朗日定理 正规子群与商群 群的同态与同构 循环群与置换群难点 代数系统的运算及其性质 陪集 群的同态与同构等概念的理解 实践活动 代数系统的基本运算 4 9 1代数系统的概念 在计算机科学中 常用代数系统去描述机器可计算函数 研究运算的复杂性 分析程序设计语言的语义等 由非空集合和该集合上的一个或多个运算所组合的系统 常称为代数系统 有时简称为代数 在研究代数系统之前 首先考察一个非空集合上运算的概念 如将有理数集合Q上的每一个数a的映射成它的整数部分 a 或者将Q上的每一个数a映射成它的相反数 a 这两个映射可以称为集合Q上的一元运算 而在集合Q上 对任意两个数所进行的普通加法和乘法都是集合Q上的二元运算 也可以看作是将Q中的每两个数映射成一个数 至于对集合Q上的任意三个数x x2 x3 代数式x12 x22 x32和x1 x2 x3分别给出了Q上的两个三元运算 它们分别将Q中三个数映射成Q中的一个数 上述这些例子有一个共同的特征 那就是其运算的结果都是在原来的集合中 称那些具有这种特征的运算是封闭的 简称闭运算 相反地 没有这种特征的运算就是不封闭的 5 6 7 8 9 10 11 12 9 2代数系统的运算及其性质 13 14 15 对于满足结合律的二元运算 在一个只有该种运算的表达式中 可以去掉标记运算顺序的括号 例如 实数集上的加法运算是可结合的 所以表达式 x y u v 可简写为x y u v 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 9 3群与子群 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 9 4同态与同构 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 9 5交换群与循环群 置换群 81 9 5 1交换群 82 83 84 85 86 87 9 5 2循环群 88 89 90 91 92 9 5 3置换群 93 94 95 96 97 98 99 100 101 9 6子群与群的陪集分解 102 103 104 105 106 107 108 109 110 111 112