离散数学下课件代数系统.ppt

1 离散数学 吉林大学计算机科学与技术学院智能信息处理教研室卢欣华luxh 2 古典代数与近世代数 古典代数的研究对象 方程以方程根的计算与分布为其研究中心 近世代数的研究对象 代数系统古典代数的发展过程导致了群的概念的提出 发展成了近世代数 3 古典代数的发展过程 一元一次方程公元前1700年一元二次方程公元前几世纪根式求解古巴比伦 古印度一元三次方程我国 在公元七世纪一般的近似解法唐朝数学家王孝通 缉古算经 西方 16世纪意大利数学家卡丹公式 4 古典代数的发展过程 一元四次方程FerrariL 费尔拉里 化为求一个三次方程和两个二次方程的根一元五次方程失败 欧拉 1707 1783 范德蒙德 鲁菲尼 高斯等 5 拉格朗日 Lagrange 在1770年猜测 这样的求根公式不存在 1824年 挪威数学家阿贝尔 Abel 证明了拉格朗日的看法 但是虽然没有通用公式 有些特殊的五次方程有求根公式 那么自然会问 如何判定一个给定的五次方程是否有这样的求根公式 阿贝尔去世 1829年 26岁 前一直在竭尽全力地研究这个问题 6 在这一时期 碰巧还有一位年轻人也在勤奋地钻研这个问题 而且最终取得了成功 他就是伽罗华 Galois 可是这位年轻人获得的非凡成果 在他因决斗去世11年后才开始得到数学界的承认 7 伽罗华1811年10月降生于巴黎近郊 14岁那年因考试不及格而重上三年级 15岁参加声望很高的巴黎高等工科大学的入学考试时 伽罗华失败了 不得不进入较普通的师范学校 就是在这所学校 伽罗华写出了他的第一篇关于连分数的数学论文 显示了他的能力 17岁 他的下两篇关于多项式方程的论文遭到法国科学院的拒绝 更遭的是 两篇论文手稿还莫名其妙地被丢失了 8 1829年7月 他在巴黎高等工科大学的入学考试中再次失败 怀着沮丧之情 伽罗华于1830年初又向科学院提交了另一篇论文 这次是为竞争一项数学大奖 科学院秘书傅立叶 Fourier 将其手稿拿回家去审读 不料在写出评审报告前去世了 此文再也没有找到 9 三失手稿 加之考巴黎高等工科大学两度失败 伽罗华遂对科学界产生排斥情绪 变成了学生激进分子 被学校开除 担任私人辅导教师谋生 但他的数学研究工作依然相当活跃 在这一时期写出了最著名的论文 关于方程可根式求解的条件 并于1831年1月送交科学院 到3月 科学院方面仍杳无音讯 于是他写信给院长打听他的文章的下落 结果又如石沉大海 10 他放弃了一切希望 参加了国民卫队 在那里和他在数学界一样运气不佳 他刚加入不久 卫队即遭控告阴谋造反而被解散 在1831年5月10日进行的一次抗议聚宴上 伽罗华手中举着出鞘的刀提议为国王干杯 这一手势被同伙们解释成是要国王的命 第2天他就被捕了 后来被判无罪 并于6月15日获释 11 7月4日 他终于打听到他给科学院的那篇论文的命运 因 无法理解 而遭拒绝 审稿人是著名的数学家泊松 Poisson 7月14日他又遭逮捕并被判了六个月监禁 因为他在公共场所身着已被解散的国民卫队的制服 在获释不久 他陷入了与斯特凡妮小姐的恋情 这导致了他的早亡 这次恋爱事件不知何故引出了一场决斗 12 1832年5月29日 决斗的前夜 伽罗华写了封很长的信给他的朋友舍瓦利耶 A Chevalier 其中大致描述了他的数学理论 从而给数学界留下了唯一一份它将蒙受何等损失的提要 在第二天的决斗中 离25步远用手枪射击 伽罗华的胃部中弹 24小时后去世 享年不足21岁 伽罗华留给世界的最核心的概念是 置换 群 他成了群论以至近世代数的创始人 13 Galois 1811 1832 近世代数的创始人 Born 25Oct1811inBourgLaReine nearParis FranceDied 31May1832inParis France 14 近世代数的特点 抽象代数系统 群环域格布尔代数 离散数学II 15 第六章群与环 16 6 1代数系统 代数运算的定义代数运算的性质代数系统的定义 17 设S是一个非空集合 称S S到S的一个映射f为S的一个二元代数运算 即 对于S中任意两个元素a b 通过f 唯一确定S中一个元素c f a b c 常记为a b c 注 代数运算是闭运算 该运算具有很强的抽象性 不限于 意义很广泛 类似地 可定义S的n元代数运算 Sn到S的映射 1 代数运算的定义 18 例 S a b 则S S a a a b b a b b 映射f为 a a a a b a b a b b b bf称为S的一个二元代数运算 有f a a af a b af b a bf b b b也可表示为 a a a a b a b a b b b b 19 加法和乘法是自然数集N上的二元代数运算 减法和除法不是N上的二元代数运算 加法 减法 乘法都是整数集Z上的二元代数运算 除法不是Z上的二元代数运算 乘法 除法是非零实数集R 上的二元代数运算 加法和减法不是R 上的二元代数运算 例 20 矩阵加法和乘法是n阶实矩阵集合上的二元代数运算 设S是一个非空集合 S 是S的幂集 则 是 S 上的二元代数运算 都是真值集合 0 1 上的二元代数运算 例 例 S a b S a b a b 21 设 是集合S上的二元代数运算 如果对于任意a b S a b b a都成立 则称运算 满足交换律 例 设Q为有理数集合 对任意a b Q 定义Q上的运算 如下 a b a b a b 则 是Q上的二元代数运算 且满足交换律 a b a b a b b a b a b a 2 代数运算的性质 交换律 22 设 是集合S上的二元代数运算 如果对于任意a b c S a b c a b c 都成立 则称运算 满足结合律 例 设A是一个非空集合 对任意a b A 定义A上的运算 如下 a b b 则 是A上的二元代数运算 且满足结合律 a b c b c ca b c a c c 2 代数运算的性质 结合律 23 设 是集合S上的二元代数运算 a是S中的元素 如果a a a 则称a是关于运算 的幂等元 如果S中每个元素都是关于 的幂等元 则称运算 满足等幂律 结论 若a是关于运算 的幂等元 则对于任意正整数n an a 2 代数运算的性质 等幂律 24 设 和 是集合S上的两个二元代数运算 如果对于任意a b c S a b c a b a c b c a b a c a 都成立 则称运算 对 满足分配律 注意 未必满足交换律 所以一个等式成立 另一个未必成立 2 代数运算的性质 分配律 25 例 设A 二元运算 定义如下 问分配律成立否 运算 对运算 满足分配律 因为 x y z x y x z y z x y x z x 证 当x x y z x y x z 当x x y z y z x y x z y z 运算 对运算 不可分配 证 26 设 和 是集合S上的两个二元代数运算 如果对于任意a b S a a b a a a b a 都成立 则称运算 和 满足吸收律 例 定义自然数集合N上的运算 和 如下 对于任意a b N 有a b max a b a b min a b 则 和 是N上的二元代数运算 且满足吸收律 a a b max a min a b aa a b min a max a b a 2 代数运算的性质 吸收律 27 设 是集合S上的二元代数运算 如果S中存在元素 使得对于S中任意元素a 都有a a 则称 是S上关于运算 的零元 设 是集合S上的二元代数运算 对于S中任意三个元素a b c 其中a不等于零元 如果有 1 若a b a c 则b c 2 若b a c a 则b c 就称 满足消去律 2 代数运算的性质 消去律 28 n阶实矩阵集合上的加法满足消去律 但乘法不满足消去律 因为 但 例 29 整数集Z上的加法 乘法都满足结合律和交换律 乘法对加法满足分配律 但加法对乘法不满足分配律 减法不满足结合律 也不满足交换律 都不满足等幂律 也不满足吸收律 n阶实矩阵集合上的加法满足结合律 也满足交换律 乘法满足结合律 但不满足交换律 它们都不满足等幂律 也不满足吸收律 例 a b c a b c 例 5 2 1 5 2 1 a b c a c b c 例 3 4 2 3 2 4 2 30 设 S 是非空集合S的幂集 则 S 上的交运算 并运算 都满足结合律 交换律 对 对 都满足分配律 它们都满足等幂律 也满足吸收律 但 不满足消去律 例 对任意A B C S 结合律 A B C A B C A B C A B C 交换律 A B B A A B B A 分配律 A B C A B A C B C A B A C A A B C A B A C B C A B A C A 等幂律 A A A A A A 吸收律 A A B A A A B A 消去律 A B A C 未必有B C A B A C 未必有B C 31 设S是一个非空集合 f1 fm是S上的若干代数运算 把S及其运算f1 fm看成一个整体来看 叫做一个代数系统 记为 S f1 fm 3 代数系统的定义 32 设S是一个非空集合 S 是S的幂集 则 S 为代数系统 设 是真值集合 0 1 上的合取与析取运算 则 0 1 是代数系统 例 33 设Z为整数集 Z0为偶数集 N为自然数集 是数的加法和乘法 则 Z Z Z Z0 Z0 Z0 N N N 都是代数系统 设 分别表示求最大公约数和求最小公倍数的运算 那么 Z Z0 N 都是代数系统 例