内蒙古大学离散数学--代数结构课件.ppt

离 散 数 学 计算机学院 软件与理论教研室（313）Email:cslq@imu.edu.cn Tel：4994019－808 第四章 代数结构之知识背景 代数结构是近世代数或抽象代数学研究的基本问题， 近世代数或抽象代数学是在初等代数学的基础上产生 和发展起来的. 始于19世纪初, 形成于20世纪30年代. 杰出数学家： 阿贝尔(N.H.Abell)(挪威) 伽罗瓦(E.Galois)(法国) 德·摩根(A.De Morgan)(英国) 布尔(G.Boole)(英国) 范德瓦尔登(B.L.Van DerWaerden)(荷兰) 范德瓦尔登于1930年和1931年分别出版了《近世代数 学》一卷和二卷,标志着抽象代数的成熟. 课程定位 从事计算机应用开发的研究人员的基本数学工具. 应用领域： 可计算性与计算的复杂性. 软件规范. 编码理论等方面. 学习目标： 了解代数结构的构成与一般性质. 如二元运算和一元运算、运算律、特异元素等. 掌握几个典型的代数系统如群、环、域. 格与布尔代数 . 4.1 二元运算与运算律 一个代数系统由集合和集合上的运算构成. 定义4.1.1 设A是非空集合 函数f:A2?A称为A上的二元运算,这时也称A对f封闭 当f:A?A时称f为一元运算. 例4.1.1 设有自然数N,整数I,有理数Q集合,则 ① 数的加法、减法和乘法是I、N和Q上的二元运算吗？ ② 求一个数的负数是Q上的一元运算吗？ ③ 数的除法是Q–{0}上的二元运算吗？ ④ 求一个数的倒数是Q–{0}上的一元运算吗？ 运算的一般化与特异元素 注意： A对f封闭,是指经运算后产生的结果,即运算像,仍然是集合A中的元素. 有些运算存在幺元或零元, 它们在运算中起着特殊的作用,称之为A 中的特异元素(代数常元). 在数系加法运算下代数常元是0(称幺元). 在乘法运算下代数常元是1(称幺元). 在乘法运算下0(称零元)是另一意义下的常元. 定义4.1.1中的运算定义在一般集合上,是数系运算的扩展或一般化. 非数集上运算的例子很多: ①命题逻辑中,否定是命题集合上的一元运算,合取和析取是二元运算. ②在集合论中,取补是幂集集合上的一元运算,并与交是二元运算. 代数系统及其表示 定义4.1.2 设A是一个非空集合. f1, f2,…, fk是在A上定义的k个运算. 由A和这些运算一起所构成的系统 称为一个代数系统,简称为代数. 记为A, f1, f2,…, fk,其中A称为载体. 运算f1, f2,…, fk要按其元数递减排列. 下面讨论的代数系统中 一元运算符一般前置,顶置或肩置,如?x, ,x’等. 二元运算符则要中置,如：x*y, x·y, x?y, x÷y等. A,*,·,ˉ表示载体为A(≠φ),且有两个二元运算*,·和 一个一元运算ˉ的代数系统. 如果一个代数系统的载体是有限集, 则称为有限代数; 否则称无限代数. 代数系统的运算表定义 例4.1.2 设S={a,b,c}, S上的二元运算＊可以用下述运算表定义. 表中位于x行和y列交叉点的元素是x＊y的值. 代数系统的分类与子代数 定义4.1.3 设S,f1,f2,…,fm和T, g1, g2,…, gm是 两个代数, 如果运算fi和gi( 1≤i≤m)具有 相同的元数,则称这两个代数是同类型的. 有时还需要在代数系统载体的某个子集上讨论其性质, 这就是子代数结构的概念. 定义4.1.4 设S,f1,f2,…,fm 是一个代数,且非空集 T?S,如果T在运算f1, f2,…, fm下都封闭， 则称代数T,f1, f2,…,fm为代数S, f1, f2,…, fm的子代数. 积代数及与子代数 一个代数的最大子代数是？ 如果一个代数存在诸如0,1的常元素,则这样的特异元 素构成该代数的最小子代数. 定义4.1.5设A1,*和A2,·是同类型的两个代数系统,称 A1×A2,⊕为A1,*和A2,·的积代数. 如果?a1,b1,a2,b2∈A1×A2, 都有a1,b1⊕a2,b2=a1* a2,b1·b2. 显然积代数是代数系统. 积代数及与子代数 例4.1.3 ①代数Q,+,×,–,0,1和I,+,×,–,0,1 都是R,+,×,–,0,1的子代数 并且是真子代数(Q