离散数学教案 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组
离散数学教案 1 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组
离散数学教案 代数结构 一、学习目的与要求 本章从一般代数系统的引入出发，研究一些特殊的代数系统中运算的性质。通过 本章的学习使学生了界代数系统的结构与性质。 二、知识点 1.代数系统的引入，运算的性质：封闭性、结合性、分配性、交换性： 2,主要的代数系统：广群、半群、独异点、群、子群：代数系统之间的关系： 3.交换群和循环群： 4.陪集、拉格朗日定理： 5.同态映射、同构映射： 6.环、同态象、域。 三、要求 1.识记 运算的封闭性、交换性、结合性，么元、零元、逆元、等幂元的识别。 2.领会 广群、半群、独异点、群、子群：代数系统之间的关系，主要的性质定理及其证 明。 四、主要内容 第5章代数结构概念及性质 5.1代数结构的定义与例 在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运 算这个概念是代数结构中不可缺少的基本概念。 定义5.1.1S是个非空集合且函数f∈S 或f:S”→S,则称f为一个n元运算。其中n是自然数，称为运算的元数或阶 当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等。 注意，元运算是个闭运算，因为经运算后产生的象仍在同一个集合中。封闭性 表明了元运算与一般函数的区别之处。此外，有些运算存在么元或零元，它在运算 中起着特殊的作用，称它为S中的特异元或常数。 运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和 2
离散数学教案 2 代数结构 一、学习目的与要求 本章从一般代数系统的引入出发，研究一些特殊的代数系统中运算的性质。通过 本章的学习使学生了界代数系统的结构与性质。 二、知识点 1．代数系统的引入，运算的性质：封闭性、结合性、分配性、交换性； 2．主要的代数系统：广群、半群、独异点、群、子群；代数系统之间的关系； 3．交换群和循环群； 4．陪集、拉格朗日定理； 5．同态映射、同构映射； 6．环、同态象、域。 三、要求 1．识记 运算的封闭性、交换性、结合性，幺元、零元、逆元、等幂元的识别。 2．领会 广群、半群、独异点、群、子群；代数系统之间的关系，主要的性质定理及其证 明。 四、主要内容 第 5 章 代数结构概念及性质 5.1 代数结构的定义与例 在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运 算这个概念是代数结构中不可缺少的基本概念。 定义 5.1.1 S 是个非空集合且函数 n s f S 或 f:Sn →S，则称 f 为一个 n 元运算。其中 n 是自然数，称为运算的元数或阶。 当 n=1 时，称 f 为一元运算，当 n=2 时，称 f 为二元运算，等等。 注意，n 元运算是个闭运算，因为经运算后产生的象仍在同一个集合中。封闭性 表明了 n 元运算与一般函数的区别之处。此外，有些运算存在幺元或零元，它在运算 中起着特殊的作用，称它为 S 中的特异元或常数。 运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和
离散数学教案 析取是谓词集合上的二元运算：在集合论中，并与交是集合上的二元运算：在整数算 术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。 在下面讲座的代数结构中，主要限于一元和二元运算，将用’、或一等符号表 示一元运算符：用⊕、⑧、⊙、O、A、∩、U等表示二元运算符，一元运算符常 常习惯于前置、顶置或肩置，如k、x':而二元运算符习惯于前置、中置或后置， 如：+xy,xy,Xy+。 有了集合上运算的概念后，便可定义代数结构了。 定义5.1.2设S是个非空集合且f是S上的ni元运算，其中i=1,2,.,m。 由S及f1,f2,.,fm组成的结构，称为代数结构，记作<S,f1,f2,.,fm>。 此外，集合S的基数即|S引定义代数结构的基数。如果S是有限集合，则说代数结构 是有限代数结构：否则便说是无穷代数结构。 有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义： 定义5.1.3设两个代数结构<S,f1,f2,.,fm>和<T,g1,g2,gm>,如果fi 和gi(1≤i≤m)具有相同的元数，则称这两个代数结构是同类型的： 可见，判定两个代数结构是否同类型，主要是对其运算进行考察。 此外，有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数 结构的概念。 定义5.1.4设<S,f1,f2,.,fm>是一代数结构且非空集TcS在运算f1,f2,., fm作用下是封闭的，且T含有与S中相同的特异元，则称<T,f1,f2,.,f>为代 数结构<S,f1,f2,.,fm>的子代数。记为<T,f1,.><S,f1,.>。 在结束本节时，声明记号<S,f1,f2,···,fm>即为一代数结构，除特别指明外， 运算符f1,f2,···,fm均为二元运算。根据需要对S及f1,f2,···,fm可置不同 的集合符和运算符。 5.2代数结构的基本性质 所谓代数结构的性质即是结构中任何运算所具有的性质。 1.结合律 给定S,⊙>，则运算“⊙”满足结合律或“⊙”是可结合的，即 (x)(付y)(付z)(x,y,z∈S一(x⊙y)⊙z=x⊙⊙z)
离散数学教案 3 析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算 术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。 在下面讲座的代数结构中，主要限于一元和二元运算，将用’、或ˉ等符号表 示一元运算符；用、、⊙、○、、、∩、∪等表示二元运算符，一元运算符常 常习惯于前置、顶置或肩置，如x、x’；而二元运算符习惯于前置、中置或后置， 如：+xy，x+y，xy+。 有了集合上运算的概念后，便可定义代数结构了。 定义 5.1.2 设 S 是个非空集合且 fi是 S 上的 ni 元运算，其中 i=1，2，.，m。 由 S 及 f1，f2，.，fm 组成的结构，称为代数结构，记作<S，f1，f2，.，fm>。 此外，集合 S 的基数即|S|定义代数结构的基数。如果 S 是有限集合，则说代数结构 是有限代数结构；否则便说是无穷代数结构。 有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义： 定义 5.1.3 设两个代数结构<S，f1，f2，.，fm>和<T，g1，g2，.，gm>，如果 fi 和 gi(1≤i≤m)具有相同的元数，则称这两个代数结构是同类型的。 可见，判定两个代数结构是否同类型，主要是对其运算进行考察。 此外，有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数 结构的概念。 定义 5.1.4 设<S，f1，f2，.，fm>是一代数结构且非空集 TS 在运算 f1，f2，.， fm 作用下是封闭的，且 T 含有与 S 中相同的特异元，则称<T，f1，f2，.，fm>为代 数结构<S，f1，f2，.，fm>的子代数。记为<T，f1，.><S，f1，.>。 在结束本节时，声明记号<S,f1,f2,···,fm>即为一代数结构，除特别指明外， 运算符 f1,f2,···,fm 均为二元运算。根据需要对 S 及 f1,f2,···,fm 可置不同 的集合符和运算符。 5.2 代数结构的基本性质 所谓代数结构的性质即是结构中任何运算所具有的性质。 1.结合律 给 定 <S ， ⊙ > ，则运算 “ ⊙ ” 满足结合律或 “ ⊙ ” 是可结合的，即 (x)(y)(z)(x，y，z∈S→(x⊙y)⊙z=x⊙(y⊙z))
离散数学教案 2.交换律 给定<S,⊙>，则运算“⊙”满足交换律或“⊙”是可交换的，即(x)(y)(x, y∈S→x⊙y=y⊙x)。 可见，如果一代数结构中的运算⊙是可结合和可交换的，那么，在计算l⊙a2 ⊙···⊙aO=am。称am为a的m次幂，m称a的指数。下面给出am的归纳定义： 设有<S,⊙>且aeS,对于m∈I+,其中I+表示正整数集合，可有： (1)a'=a (2)a=a⊙a 由此利用归纳法不难证明指数定律： (1）a⊙a"=aa (2)(a)=a" 这里，m,neI+。 类似地定义某代数结构中的负幂和给出负指数定律 3.分配律 一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。 给定<S,⊙，O>,则运算⊙对于O满足左分配律，或者⊙对于O是可左分配的，即 (x)(y)(z)(x,y,z∈S-→x⊙(yOz)=(y⊙x)O(x⊙z)。 运算⊙对于O满足右分配律或⊙对于O是可右分配的，即（付x)(y)(付2）(x,y, z∈S→(yOz)⊙x=(y⊙x)O(z⊙x) 类似地可定义O对于⊙是满足左或右分配律。 若⊙对于O既满足左分配律又满足右分配律，则称⊙对于O满足分配律或是可分 配的。同样可定义O对于⊙满足分配律。 由定义不难证明下面定理： 定理5.2.1给定<S,⊙，O>且⊙是可交换的。如果⊙对于O满足左或右分配 律，则⊙对于O满足分配律。 例5.2.3给定<B,⊙，O>,其中={0,1}。表5.2.1分别定义了运算⊙和O,问 运算⊙对于O是可分配的吗？O对于⊙呢？ 形如表5.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表 头元素及复合元素四部分组成。当集合S的基数很小，特别限于几个时，代数结构中 4
离散数学教案 4 2.交换律 给定<S，⊙>，则运算“⊙”满足交换律或“⊙”是可交换的，即( x)( y)(x， y∈S→x⊙y=y⊙x)。 可见，如果一代数结构中的运算⊙是可结合和可交换的，那么，在计算 a1⊙a2 ⊙···⊙a0=am。称 am 为 a 的 m 次幂，m 称 a 的指数。下面给出 am 的归纳定义： 设有<S，⊙>且 aS，对于 mI+，其中 I+表示正整数集合，可有： (1) a1 =a (2)am+1 =a m⊙a 由此利用归纳法不难证明指数定律： (1)am⊙a n =a m+n (2)(am ) n =a mn 这里，m,nI+。 类似地定义某代数结构中的负幂和给出负指数定律。 3.分配律 一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。 给定<S，⊙，○>，则运算⊙对于○满足左分配律，或者⊙对于○是可左分配的，即 (x)(y)(z)(x，y，z∈S→x⊙(y○z))=(y⊙x)○(x⊙z))。 运算⊙对于○满足右分配律或⊙对于○是可右分配的，即(x)(y)(z)(x，y， z∈S→(y○z)⊙x=(y⊙x)○(z⊙x)) 类似地可定义○对于⊙是满足左或右分配律。 若⊙对于○既满足左分配律又满足右分配律，则称⊙对于○满足分配律或是可分 配的。同样可定义○对于⊙满足分配律。 由定义不难证明下面定理： 定理 5.2.1 给定<S，⊙，○>且⊙是可交换的。如果⊙对于○满足左或右分配 律，则⊙对于○满足分配律。 例 5.2.3 给定<B,⊙,○>，其中 B={0,1}。表 5.2.1 分别定义了运算⊙和○，问 运算⊙对于○是可分配的吗？○对于⊙呢？ 形如表 5.2.1 的表常常被称为运算表或复合表，它由运算符、行表头元素、列表 头元素及复合元素四部分组成。当集合 S 的基数很小，特别限于几个时，代数结构中
离散数学教案 运算常常用这种表给出。其优点简明直观，一目了然。 解可以验证⊙对于O是可分配的，但O对于⊙并非如此。因为 10(0⊙1)≠(1O0)⊙(101) 4.吸收律 给定<S,⊙，O>,则 ⊙对于O满足左吸收律：=（付x)(付y)(x,y∈S一x⊙(xOy)=x) ⊙对于O满足右吸收律：=（付x)(y)(x,y∈S→(xOy)⊙x=x) 若⊙对于℃既满足左吸收律又满足右吸收律，则称⊙对于O满足吸收律或可吸收 的。 O对于⊙满足左、右吸收律和吸收律类似地定义。 若⊙对于O是可吸收的且O对于⊙也是可吸收的，则⊙和O是互为吸收的或⊙和 O同时满足吸收律。 5.等幂律与等幂元 给定<S,⊙>，则 “⊙”是等幂的或“⊙”满足等幂律：=(x)(x∈S→x⊙x=x) 给定<S,⊙>且x∈S,则 x是关于“⊙”的等幂元：=x⊙x=x 于是，不难证明下面定理： 定理5.2.2若x是<S,⊙>中关于⊙的等幂元，对于任意正整数n,则x=x。 6.么元或单位元 给定<S,⊙>且el,er,eeS,则 el为关于⊙的左么元：=(x)(x∈S→el⊙x=x) er为关于⊙的右么元：=(x)(x∈S→x⊙er=x) 若e既为⊙的左么元又为⊙的右么元，称e为关于⊙的么元。亦可定义如下： e为关于⊙的么元：=(x)(x∈S→e⊙x=x⊙e=x)。 定理5.2.3给定<S,⊙>且el和er分别关于⊙的左、右么元，则el=er=e且 么元e唯一。 7.零元
离散数学教案 5 运算常常用这种表给出。其优点简明直观，一目了然。 解 可以验证⊙对于○是可分配的，但○对于⊙并非如此。因为 1○(0⊙1)(1○0)⊙(1○1) 4.吸收律 给定<S，⊙，○>，则 ⊙对于○满足左吸收律:=(x)(y)(x，y∈S→x⊙(x○y)=x) ⊙对于○满足右吸收律:=(x)(y)(x，y∈S→(x○y)⊙x=x) 若⊙对于 c 既满足左吸收律又满足右吸收律，则称⊙对于○满足吸收律或可吸收 的。 ○对于⊙满足左、右吸收律和吸收律类似地定义。 若⊙对于○是可吸收的且○对于⊙也是可吸收的，则⊙和○是互为吸收的或⊙和 ○同时满足吸收律。 5.等幂律与等幂元 给定<S，⊙>，则 “⊙”是等幂的或“⊙”满足等幂律:=( x)(x∈S→x⊙x=x) 给定<S，⊙>且 x∈S，则 x 是关于“⊙”的等幂元:=x⊙x=x 于是，不难证明下面定理： 定理 5.2.2 若 x 是<S，⊙>中关于⊙的等幂元，对于任意正整数 n，则 x n =x。 6.幺元或单位元 给定<S，⊙>且 el，er，e∈S，则 el 为关于⊙的左幺元:=( x)(x∈S→el⊙x=x) er 为关于⊙的右幺元:=( x)(x∈S→x⊙er=x) 若 e 既为⊙的左幺元又为⊙的右幺元，称 e 为关于⊙的幺元。亦可定义如下： e 为关于⊙的幺元:=( x)(x∈S→e⊙x=x⊙e=x)。 定理 5.2.3 给定<S，⊙>且 el 和 er 分别关于⊙的左、右幺元，则 el=er=e 且 幺元 e 唯一。 7.零元