离散数学-代数系统.ppt

代数系统 内容提要在集合上可以定义若干个运算由这些运算而组成的系统在计算机科学中应用广泛主要内容 运算及其性质 群 环 域 格代数和布尔代数等 代数系统 集合上的运算对于集合A中任意元素x的一种映射F x 一元运算任意n个元素x1 x2 xn 一种映射F x1 x2 xn n元运算例如 自然数集合上定义的普通加法 乘法等 都是二元运算 比较 集合之间定义的运算和集合上定义的运算 代数系统 代数系统的引入设f1 f2 fk是在非空集合A上定义的运算 这些运算与集合组成一个代数系统 记作 当运算只有一种时 通常写作 而运算f通常表示成 等 代数系统 封闭性与唯一性 是集合A上的一个二元运算 如果对于任意的x y A 都有x y A 则称 在集合A上是封闭的 是集合A上的一个二元运算 如果对于任意的x y A x y都是A中的唯一元素 则称 在集合A上是唯一的 代数系统 交换律与结合律交换律 是集合A上的一个二元运算 如果对于任意的x y A 都有x y y x 则称 是可交换的 结合律 是集合A上的一个二元运算 如果对于任意的x y z A 都有 x y z x y z 则称 是可结合的 代数系统 分配律设 是集合A上的两个二元运算 如果对于任意的x y z A 都有x y z x y x z y z x y x z x 则称运算 对于运算 是可分配的 代数系统 吸收律设 是集合A上的两个可交换的二元运算 如果对于任意的x y z A 都有x x y xx x y x则称运算 和 满足吸收律 代数系统 等幂性 是集合A上的一个二元运算 如果对于任意的x A 都有x x x 则称运算 是等幂的 代数系统 运算表 是定义在集合A上的二元运算 A是有限集 A x1 x2 xn 那么对于任意的xi xj A xi xj的结果放在以xi为行 xj为列所组成的一个表格内 例如 代数系统 单位元 幺元 左幺元 是集合A上的一个二元运算 如果A中存在一个元素el 对于任意的x A 都有el x x 则称el为A中关于运算 的左幺元 右幺元 是集合A上的一个二元运算 如果A中存在一个元素er 对于任意的x A 都有x er x 则称er为A中关于运算 的右幺元 如果A中存在一个元素e既是左幺元又是右幺元 则称e是A中关于运算 的幺元 显然 对于任意的x A 都有e x x e x 代数系统 幺元的性质如果左 右幺元都存在 那么它们必相等 而且就是幺元 幺元是唯一的 代数系统 零元左零元 是集合A上的一个二元运算 如果A中存在一个元素 l 对于任意的x A 都有 l x l 则称 l为A中关于运算 的左零元 右零元 是集合A上的一个二元运算 如果A中存在一个元素 r 对于任意的x A 都有x r r 则称 r为A中关于运算 的右零元 如果A中存在一个元素 既是左零元又是右零元 则称 是A中关于运算 的零元 显然 对于任意的x A 都有 x x 代数系统 零元的性质如果左 右零元都存在 那么它们必相等 而且就是零元 零元是唯一的 注意 如果幺元和零元均存在 那么它们必不相等 代数系统 逆元左逆元 A 是一个代数系统 e是A中关于运算 的幺元 对于A中的元素a 存在A中的某个元素b 使得b a e 则称b为a的左逆元 右逆元 A 是一个代数系统 e是A中关于运算 的幺元 对于A中的元素a 存在A中的某个元素b 使得a b e 则称b为a的右逆元 如果存在一个元素b 既是左逆元又是右逆元 那么b是a的逆元 记作a 1 代数系统 逆元的性质逆元是相互的 即b是a的逆元 则a也是b的逆元 左 右逆元不一定相等 逆元不一定唯一 代数系统 运算表的作用运算 的封闭性和唯一性运算 的可交换性运算 的等幂性存在零元存在幺元存在逆元 代数系统 半群一个代数系统 S S是非空集合 是S上的一个二元运算 如果 1 运算 是封闭的 2 运算 是可结合的 则称 S 是半群 代数系统 独异点含有幺元的半群为独异点 设 S 是独异点 则它的运算表中任何两行或两列都是不相同的 代数系统 群一个代数系统 G G是非空集合 是G上的一个二元运算 如果 1 运算 是封闭的 2 运算 是可结合的 3 存在幺元e 4 对于G中的每一个元素x 都存在它的逆元x 1 则称 G 是一个群 代数系统 有限群与无限群 G 是一个群 如果G是有限集 那么称 G 是有限群 G 为该群的阶数 如果G是无限集 那么称 G 是无限群 代数系统 群的性质群中每个元素都存在逆元且唯一群中没有零元群的运算表中没有两行或两列是相同的群中除了幺元之外没有等幂元 代数系统 群方程的解设 G 是一个群 对于a b G 存在唯一的x G 使得a x b或x a b 当a x b时 显然x a 1 b 当x a b时 显然x b a 1 代数系统 群的消去律设 G 是一个群 对于任意的a b c G 如果有a b a c或者b a c a 则必有b c 代数系统 子群设 G 是一个群 S是G的非空子集 如果 S 也构成群 则称 S 是 G 的一个子群 特别地 如果 S 1 显然这个元素就是幺元 或者S G 则称 S 是 G 的平凡子群 代数系统 子群的性质群 G 的幺元必是子群 S 的幺元 对于G的任何非空有限子集S 如果 在S上也封闭 那么 S 必定是一个子群 代数系统 交换群 Abel群 如果群 G 中运算 是可交换的 则称该群为交换群 即a b b a或 a b a b a a b b 代数系统 循环群设 G 为群 若在G中存在一个元素a 使得G中的任意元素都由a的幂组成 则称该群为循环群 元素a为该循环群的生成元 记为 注意 任何循环群都是可交换群 代数系统 有限循环群设 G 是一个循环群 G是有限集 a是生成元 那么G可表示为G e a a2 an 1 G n 其中e是幺元 an e 而n是使an e的最小正整数 称为元素a的阶 代数系统 群的积集与逆集设 G 是群 A B是G的非空子集 记AB a b a A b B 称为群 G 在子集A B上的积 A 1 a 1 a A 称为群 G 关于子集A的逆 代数系统 陪集设 H 是群 G 的一个子群 a G 则积集 a H称为由a所确定的H在G中的左陪集 记为aH 设 H 是群 G 的一个子群 a G 则积集H a 称为由a所确定的H在G中的右陪集 记为Ha 元素a是陪集合aH或Ha的代表元素 代数系统 拉格朗日定理设 H 是群 G 的一个子群 那么 1 R a b a G b G a 1 b H 是G中的一个等价关系 而且由R所确定的等价类 a R aH 2 如果G是有限集 G n H m 则m n m整除n 代数系统 具有两个二元运算的代数系统回忆 半群 独异点 群 一个二元运算的代数系统两个二元运算组合起来记作 A 通常称 为加法 为乘法 研究两个二元运算之间的关系 代数系统 环设 A 是一个代数系统 如果满足 1 A 是可交换群 Abel群 2 A 是半群 3 运算 对于运算 是可分配的 则称 A 是环 代数系统 环的性质设 A 是一个环 则对任意的a b c A 有 1 a a 加法的幺元是乘法的零元 2 a b a b a b 3 a b a b 4 a b c a b a c 5 b c a b a c a其中 是加法幺元 a是a的加法逆元 并记a b 为a b 代数系统 交换环与含幺环根据半群 A 的性质来定义特殊的环 设 A 是一个环 如果 A 是可交换的 则称 A 是一个交换环 如果 A 含有幺元 则称 A 是一个含幺环 代数系统 整环设 A 是一个可交换的含幺环 且 A 无零因子 即对任意的a b A a b均不是零元 那么a b也不是零元 则称 A 是一个整环 代数系统 整环的消去律设 A 是一个整环 对于任意的a b c A c c a c b 则必有a b 代数系统 域设 A 是一个代数系统 如果满足 1 A 是Abel群 2 A 是Abel群 3 运算 对运算 是可分配的 则称 A 是域 代数系统 域与整环域一定是整环整环不一定是域有限整环一定是域 代数系统 格回忆 偏序集的概念设 A 是一个偏序集 如果A中任意两个元素都有最小上界和最大下界 则称 A 是格 代数系统 格代数设 A 是一个格 如果在A上定义两个二元运算 和 使得对于任意的a b A a b等于a和b的最小上界 a b等于a和b的最大下界 那么就称 A 为由格 A 所诱导的代数系统 简称格代数 而二元运算 和 分别称为格代数的并运算与交运算 代数系统 思考 S 是一个格 任意两个元素S1 S2 其最小上界为S1 S2 最大下界为S1 S2 则 S 是由格 S 所诱导的格代数 代数系统 子格设 A 是一个格 由格 A 所诱导的代数系统为 A 设B是A的非空子集 如果A中的这两个运算 和 关于B是封闭的 则称 B 是 A 的一个子格 子格必定是格 子集所组成的格不一定是子格 代数系统 偏序集的对偶设 A 是一个偏序集 在A上定义一个二元关系 R 使得a Rb当且仅当b a 那么 A R 也是一个偏序集 且称 A R 是 A 的对偶 注意 对偶是相互的 它们的Hasse图互相颠倒 代数系统 格的对偶设 A 是一个格 在A上定义一个二元关系 R 使得a Rb当且仅当b a 那么 A R 也是一个格 且称 A R 是 A 的对偶 两者互为对偶 代数系统 格代数的对偶原理设 A R 是 A 的对偶格 R是 的逆关系 由 A R 所诱导的格代数 A R 是由 A 所诱导的格代数 A 的对偶格代数 所以通常记 R为 代数系统 偏序关系与格代数运算的性质 1 a a b b a b a b a a b b 2 如果a b c d 那么a c b d a c b d 3 如果b c 那么a b a c a b a c 代数系统 格代数的性质 1 交换律a b b a a b b a 2 结合律a b c a b c a b c a b c 3 幂等律a a a a a a 4 吸收律a a b a a a b a 代数系统 分配格设 A 是由格 A 所诱导的代数系统 如果对任意的a b c A 满足a b c a b a c a b c a b a c 则称 A 是分配格 代数系统 分配格分配运算的等价性设 A 是分配格 分配条件a b c a b a c 和a b c a b a c 是等价的 代数系统 链与分配格每个链是分配格 思考 全序集呢 代数系统 分配格的消去律设 A 是一个分配格 那么对于任意的a b c A 如果有a b a c a b a c 那么b c 代数系统 全上界和全下界设 A 是一个格 如果存在元素a A 对于任意元素x A 都有a x 则称a为格 A 的全下界 记为0 设 A 是一个格 如果存在元素a A 对于任意元素x A 都有x a 则称a为格 A 的全上界 记为1 全下界和全上界都是唯一的 代数系统 有界格如果一个格中存在全下界和全上界 则称此格为有界格 在有界格 A 中 必有a 1 1 a 0 a a 1 a a 0 0 注意 0是运算 的幺元 也是运算 的零元 1是运算 的幺元 也是运算 的零元 代数系统 补元与有补格设 A 是一个有界格 对于A中的一个元素a 如果存在b A 使得a b 1和a b 0 则称元素b是元素a的补元 试比较 格的补元和群的逆元的区别设 A 是一个有界格 如果A中每个元素都有补元 则称 A 是有补格 代数系统 有补分配格设 A 既是有补格又是分配格 则称它是有补分配格 设 A 是一个有补分配格 那么A中任意元素a都有唯一的补元 记为 a 代数系统 布尔代数一个有补分配格称为布尔格 由布尔格 A 所诱导的一个代数系统 A 称为布尔代数 其中 是一元求补运算 代数系统 布尔代数的性质 a a a b a b a b a b 代数系统 有限布尔代数具有有限个元素的布尔代数称为有限布尔代数 设 A 是一个有限布尔代数 若b是A中的任意非零元素 即不是全下界0 而a1 a2 ak是A中满足aj b的所有原子 则b a1 a2 ak 且这样的表达是唯一的 注 原子a是能盖住0的元素 代数系统 有限布