1、离 散 数 学计算机学院 软件与理论教研室（ 313）Email:Tel： 4994019 808Discrete Mathematics* 1第 三 部 分代代 数数 结结 构构Algbra StructuresDate 2第四章 代数结构 之 知识背景n 代数结构 是近世代数或抽象代数学研究的基本问题，近世代数或抽象代数学是在初等代数学的基础上产生和发展起来的 .n 始于 19世纪初 , 形成于 20世纪 30年代 .n 杰出数学家：p 阿贝尔 (N.H.Abell)(挪威 )p 伽罗瓦 (E.Galois)(法国 )p 德 摩根 (A.De Morgan)(英国 )p 布尔 (G.Boo
2、le)(英国 )p 范德瓦尔登 (B.L.Van DerWaerden)(荷兰 )n 范德瓦尔登 于 1930年和 1931年分别 出版了 近世代数学 一卷和二卷 ,标志着抽象代数的成熟 .Date 3课程定位n 从事计算机应用开发的研究人员 的 基本数学工具 .n 应用领域：p 可计算性与计算的复杂性 .p 软件规范 .p 编码理论等方面 .n 学习目标：p 了解代数结构的构成 与 一般性质 .n 如二元运算和一元运算、运算律、特异元素等 .p 掌握几个 典型的代数系统如 群 、 环 、 域 .p 格与布尔代数 .Date 44.1 二元运算与运算律n 一个代数系统 由集合和集合上的 运算
3、构成 .定义 4.1.1 设 A是非空集合函数 f:A2A称为 A上的二元运算 ,这时也称 A对对 f封闭封闭 当 f:AA时称 f为一元运算 .n 例 4.1.1 设有自然数 N,整数 I,有理数 Q集合 ,则 数的加法、减法和乘法是 I、 N和和 Q上的二元运算吗？ 求一个数的负数是 Q上的一元运算吗？ 数的除法是 Q 0上的二元运算吗？ 求一个数的倒数是 Q 0上的一元运算吗？Date 5运算的一般化与特异元素注意：p A对 f封闭 ,是指经运算后产生的结果 ,即运算像 ,仍然是集合 A中的元素.p 有些运算存在 幺元 或 零元 , 它们在运算中起着特殊的作用 ,称之为 A中的 特异元素
4、 (代数常元 ).v 在数系加法运算下代数常元是 0(称幺元 ).v 在乘法运算下代数常元是 1(称幺元 ).v 在乘法运算下 0(称零元 )是另一意义下的常元 .p 定义 4.1.1中的 运算定义在一般集合上 ,是 数系运算的 扩展或 一般化.p 非数集上运算的例子很多 : 命题逻辑中 ,否定是命题集合上的一元运算 ,合取和析取是二元运算 . 在集合论中 ,取补是幂集集合上的一元运算 ,并与交是二元运算 .Date 6代数系统及其表示定义 4.1.2 设 A是一个 非空非空 集合 .f1, f2, fk是在 A上定义的 k个运算 .由 A和这些运算一起所构成的系统称为一个 代数系统 ,简称为
5、代数 .记为 ,其中 A称为 载体 .运算 f1, f2, fk要按其元数递减排列 .p下面讨论的代数系统中一元运算符一般前置 ,顶置或肩置 ,如 x, ,x 等 .二元运算符则要中置 ,如： x*y, xy , xy, xy 等 .p表示载体为 A( ),且有两个二元运算 *,和一个一元运算 的代数系统 .p如果一个代数系统的 载体是有限集 , 则 称 为 有限代数 ;否则称 无限代数 .xDate 7代数系统的运算表定义例 4.1.2 设 S=a,b,c,S上的二元运算可以用下述运算表定义 .表中位于 x行和 y列交叉点的元素是 x y的值 .p 有时 ,要考察两个或多个代数的结构 ,要通
6、过是否同类 型而进行分类 .p判定两个代数结构是否同类型 ,主要对其运算进行考察.*abca b ca b cb c ac a bDate 8代数系统的分类与子代数定义 4.1.3 设 和 是两个代数 , 如果运算 fi和 gi( 1 i m)具有 相同的元数 ,则称这 两个代数是同类型的 .z有时还需要在代数系统载体的 某个子集某个子集 上讨论其性质 ,这就是子代数结构的概念 . 定义 4.1.4 设 是一个代数 ,且非空集TS,如果 T在运算 f1, f2, fm下都封闭， 则称代数 为代数 的 子代数 .Date 9积代数及与子代数z一个代数的最大子代数是？z如果一个代数存在 诸如诸如 0,1的常元素的常元素 ,则这样的特异元则这样的特异元素构成该代数的最小子代数素构成该代数的最小子代数 .定义 4.1.5设 和 是同类型的两个代数系统 ,称为 和 的积代数 .如果 ,A 1A 2,都有 =.J显然积代数是代数系统 .Date 10
