东南大学：《离散数学》课程教学资源（PPT课件讲稿）第十一章 格与布尔代数（主讲：周德宇）

第十一章:格与布尔代数 格的定义与性质 分配格、有补格与布尔代数 东南大学计算机科学与工程学院 离散数学 与布尔代数

格的定义与性质 分配格、有补格与布尔代数 第十一章: 格与布尔代数

代数系统回顾 代数系统:非空集合S和集合上k个一元或二元运灬,坻 所组成的系统记为V= 集合中的元素 代数系统的载体 运算的规律 单位元 对集合s满足封闭性·交换律 上、下界 结合律 零元 幂等率 E逆元 分配律 东南大学计算机科学与工程学院 离散数学 与布尔代数

代数系统：非空集合S和集合上k个一元或二元运算f1 ,…,fk 所组成的系统. 记为 V= 非空集合S 运算f1 ,…,fk 交换律 结合律 幂等率 分配律 … … 运算的规律 单位元 上、下界 零元 逆元 … … 集合中的元素

代数系由来 16世纪,四次以下方程根式解问题得以解决 关于五次方程的解法,全世界摸索了300年 阿贝尔给出了五次方程没有根式解的证明 关于五次以上方程求解是否有一般性判定? 伽罗瓦对代数运算进行抽象,提出“置换群” 将解方程与N个文字的对称群对应 N次方程可解充要条件:伽罗瓦群为可解群■ 100间不同数学家采用相同思路解决各自问题 十世纪三十年代,将这种思想概括为代数结构 东南大学计算机科学与工程学院 离散数学 与布尔代数

埃瓦里斯特·伽罗华 1811-1832 “父亲是我的一切”（福兮祸所伏） 中学二年级因体格不强壮留级（祸兮福所倚） “伽罗华只宜在数学的尖端领域中工作” 参加数学竞赛，论文被傅立叶评价为“不知所云” 参加学术交流，论文被柯西“丢失” 为“爱情”选择“自杀”（政治阴谋） “我没有时间，我没有时间” “请雅可比或高斯公开提出他们的意见，不是对 这些定理的正确性，而是对它们的重要性。我希望 以后会有人发现，辨读这一堆写得很潦草的东西， 对他们是有益的。满怀激情地拥抱你。E·伽罗华。” （14年后被人读懂） 阿贝尔 1802-1829 出身挪威贫苦家庭靠朋友资助完成学业 提出“五次方程不可解”的证明，被高斯扔进废 纸堆（困扰世界300年的问题） 开创椭圆函数，触碰学霸利益，成果被封锁 一生穷困潦倒，身患肺炎却无钱医治，吐血而亡 当今与诺贝尔奖齐名的数学奖项——阿贝尔奖 16世纪，四次以下方程根式解问题得以解决 关于五次方程的解法，全世界摸索了300年 阿贝尔给出了五次方程没有根式解的证明 关于五次以上方程求解是否有一般性判定？ 伽罗瓦对代数运算进行抽象，提出“置换群” 将解方程与N个文字的对称群对应 N次方程可解充要条件：伽罗瓦群为可解群 100年间不同数学家采用相同思路解决各自问题 二十世纪三十年代，将这种思想概括为代数结构

为什么研“代数系统 PERIODIC TABLE OF THE ELEMENTS a s AsiPs cIAr 求 回四回回回 @四如mpc ThPauNpPuAmCmBx EsEm Ma NoEr EL CENTRO DEL CAMPO LA DELANTERA 东南大学计算机科学与工程学院 离散数学 与布尔代数

逻与集合 析取 并集∪ 两个中的任意一个成立 两个中的任意一个属于 取∧ 交集∩ 两个同时成立 同时属于两个 否定 补集 对一个不成立 仅属于其中一个 东南大学计算机科学与工程学院 离散数学 与布尔代数

析取 ∨ 两个中的任意一个成立 并集 ∪ 两个中的任意一个属于 合取 ∧ 两个同时成立 交集 ∩ 同时属于两个 否定 对一个不成立 补集 - 仅属于其中一个

引言一“格”的由来 格 Lattice Theory <The Mathematical analysis of Logic》1848 《 Modern Algebra》1930 《 Lattice Theory》1937 《 The Laws of Thought》1854 ·乔治·布尔 范德瓦尔登 ·约翰冯诺依曼 皮匠的儿子 哥廷根最后的大师 ·各种奠基人 ·自学成才者 抽象代数奠基人 各种大师 数学老师 计算几何奠基人 传说不是人类 差分法发明人 数学史大师 死于癌症 ·暴雨后坚持上课 影响世界的作者 ·死于肺炎 只带40个博士 1815-1864 1903-1996 1903-1957 东南大学计算机科学与工程学院 离散数学 与布尔代数

格 Lattice Theory • 乔治·布尔 • 皮匠的儿子 • 自学成才者 • 数学老师 • 差分法发明人 • 暴雨后坚持上课 • 死于肺炎 《The Mathematical Analysis of Logic》1848 《The Laws of Thought》 1854 1815-1864 1903-1996 • 范德瓦尔登 • 哥廷根最后的大师 • 抽象代数奠基人 • 计算几何奠基人 • 数学史大师 • 影响世界的作者 • 只带40个博士 《Modern Algebra》 1930 1903-1957 • 约翰·冯·诺依曼 • 各种奠基人 • 各种大师 • 传说不是人类 • 死于癌症 《Lattice Theory》 1937

引言“格的内涵 Lattice Theory 格子结构 直观感觉:不同单元格的位置关系—上、下、左、右 抽象思维:集合中不同元素的序关系 将比较作为一种元素间的运算+∪∧ 东南大学计算机科学与工程学院 离散数学 与布尔代数

Lattice Theory 格子结构 直观感觉：不同单元格的位置关系——上、下、左、右 抽象思维：集合中不同元素的序关系

引言一格”的定位 对推理和思维的抽象 格 逻辑 与、、一禅 对逻辑中运算的抽象 布尔代数 代数结构 对布尔代数中运算规律的抽象 代数结构中的格 -集合 东南大学计算机科学与工程学院 离散数学 与布尔代数

对推理和思维的抽象 逻辑 对逻辑中运算的抽象 布尔代数 对布尔代数中运算规律的抽象 代数结构中的格

的羽 前定义 自反、反对称、传递 定义1:设是偏序集,如果X,y∈S,{,y都有最小 上界和最大下界,则称S关于偏序≤作成一个格。 两个二元运算:最小上界最大下界入 伙,y}存在上界z意味着同时满足x≤z和y≤z两个条件,即z与x和y均具 有可比性 伙,y存在最小上界意味着k,y所有的上界之间具有可比性 {,y存在最小上界z未必意味着x与y之间具有可比性」 最大下界情况类似 东南大学计算机科学与工程学院 离散数学 与布尔代数

定义1：设是偏序集，如果x，y S，{x，y}都有最小 上界和最大下界，则称S关于偏序 ≼ 作成一个格。 两个二元运算：最小上界∨ 最大下界∧ {x，y}存在上界z意味着同时满足x ≼z和y ≼z两个条件，即z与x和y均具 有可比性 {x，y}存在最小上界z未必意味着x与y之间具有可比性 {x，y}存在最小上界意味着{x，y}所有的上界之间具有可比性 最大下界情况类似

例子 凤姐≤芙蓉≤春春≤志玲 凤姐ⅴ芙蓉≡芙蓉 凤姐∧春春=凤姐 芙蓉ⅴ志玲〓志玲 春春∧志玲≡春春 选美比赛名次 自我评价排名 东南大学计算机科学与工程学院 离散数学 与布尔代数

选美比赛名次 凤姐 ≼ 芙蓉 ≼ 春春 ≼ 志玲 凤姐 ∨ 芙蓉 = 芙蓉 凤姐 ∧ 春春 = 凤姐 芙蓉 ∨ 志玲 = 志玲 春春 ∧ 志玲 = 春春 。。。 。。。 自我评价排名