离散数学邱晓红电子教案 第09章.pptVIP

代数结构主讲:艾施荣 第三篇：代数结构目录 第八章 半群、语言和自动机 8.1 半群和语言 8.2 语言和文法 8.3 有限状态机 8.4 有限状态自动机 8.5 语言与自动机的关系 实验八：设计输出状态自动机 第八章 习题 第九章 代数系统 9.1 代数系统的概念 9.2 代数系统的运算及其性质 9.3 群与子群 9.4 同态与同构 9.5 交换群与循环群 置换群 第八章：半群、语言和自动机 主要内容：构成代数系统的基本成分；二元运算性质和特异元素；同类型的与同种的代数系统 、群的定义、实例与术语、群的基本性质；子群的判别定理；陪集的定义及其性质、子群与群的陪集分解 、环与域； 教学要求：理解代数系统、群、环与域的概念，理解同态与同构、交换群与循环群 置换群的区别，理解子群与群的陪集分解 ； 重点：代数系统 、群的定义与性质、子群、陪集与拉格朗日定理、正规子群与商群、群的同态与同构、循环群与置换群 难点：代数系统的运算及其性质、陪集、群的同态与同构等概念的理解； 实践活动：代数系统的基本运算。 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中的一个数。上述这些例子有一个共同的特征，那就是其运算的结果都是在原来的集合中，称那些具有这种特征的运算是封闭的，简称闭运算。相反地，没有这种特征的运算就是不封闭的。 9.2 代数系统的运算及其性质 对于满足结合律的二元运算，在一个只有该种运算的表达式中，可以去掉标记运算顺序的括号。例如，实数集上的加法运算是可结合的，所以表达式（x+y）+（u+v）可简写为x+y+u+v。 9.3 群与子群 9.4 同态与同构* 9.5 交换群与循环群、置换群 9.5.1 交换群 9.5.2 循环群 9.5.3 置换群 9.6 子群与群的陪集分解* 9.7 环与域* * * 离散数学讲义之 9.6 子群与群的陪集分解 9.7 环与域 实验九:代数系统的基本运算 第九章 习题 第十章 格与布尔代数 10.1 格的概念 10.2 分配格、有补格与布尔代数 10.3 分配格 10.4 有补格 10.5 布尔代数与布尔表达式 10.6 数字电路与最小化 实验十：代数系统综合课程设计 第十章 习题