标签:   离散数学   第十一章  
文档信息
上传用户 crush     
文档格式 ppt
文档价格 7.3 元
文档大小 1000 KB
文档页数 37 页
相关文档推荐
doc 云南省2020年实验小学一年级语文【下册】期末考试试题 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版(I卷) 含答案
ppt 《抓住特点写具体》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试题C卷 (含答案)
doc 2020年六年级数学【上册】期末考试试题人教版(II卷) 附答案
doc 实验小学二年级数学下学期开学考试试题部编版(I卷) 附答案
doc 2019-2020年高三上学期期中质量检测英语试题 Word版含答案
doc 2019-2020年高三上学期期中质量检测英语试题含答案
doc 山东省重点小学三年级数学【上册】期末考试试卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题豫教版A卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测D卷 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版(I卷) 附答案
doc 2019-2020学年高二英语下学期2月模块诊断试题
doc 山东省重点小学三年级数学【下册】开学摸底考试试卷 (附解析)
doc 山东省重点小学三年级数学【下册】期中摸底考试试卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题部编版(II卷) 附解析
doc 山东省重点小学三年级数学【下册】开学摸底考试试卷 附解析
doc 山东省重点小学三年级数学【下册】期中摸底考试试卷 (附答案)
doc 2020年六年级数学【上册】期末考试试题北师大版 (附解析)
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试卷 含答案
doc 2020年六年级数学【上册】期末考试试题外研版A卷 含答案
doc 实验小学二年级数学下学期开学考试试题豫教版 附答案
doc 云南省2020年实验小学一年级语文【上册】期末考试试题 附答案
doc 云南省2020年实验小学一年级语文【上册】期中考试试题 含答案
ppt 《抒情技巧习题》PPT课件
doc 2020年六年级数学【上册】期末考试试题人教版(II卷) 附解析
doc 云南省2020年实验小学一年级语文【下册】期中考试试卷 附解析
ppt 《把自己推销出去》PPT课件
doc 2019-2020年高三上学期期中质量评估语文试题
doc 广东省重点小学四年级数学下学期期末摸底考试试卷(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题部编版B卷 含答案
doc 2020年六年级数学【上册】期末考试试题北师大版 (含答案)
doc 2020年六年级数学【上册】期末考试试题外研版(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试题外研版 附解析
ppt 《把物当成人来写》PPT课件
doc 实验小学二年级数学下学期开学考试试题西南师大版B卷 附解析
doc 2019-2020年高三上学期期中质量监测化学试题 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版C卷 含答案
doc 云南省2020年实验小学一年级语文【上册】期中考试试卷 附解析
doc 2019-2020年高三上学期期中质量检测化学试题 Word版含答案
doc 2019-2020学年高二英语下学期3月月考试题
doc 2020年六年级数学【上册】期末考试试题外研版 (附解析)
doc 2020年六年级数学【上册】期末考试试题外研版(I卷) 附解析
doc 2020年六年级数学【上册】期末考试试题北师大版 附解析
doc 实验小学二年级数学下学期开学考试试题豫教版B卷 附解析
doc 云南省2020年实验小学一年级语文【下册】期中考试试卷 含答案
doc 2020年六年级数学【上册】期末考试试题北师大版A卷 附答案
ppt 《投保单如何填写》PPT课件
doc 实验小学二年级数学下学期开学考试试题长春版A卷 附解析
doc 云南省2020年实验小学一年级语文【下册】开学考试试题 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 (附答案)
doc 云南省2020年实验小学一年级语文【上册】期末考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题西南师大版(I卷) 含答案
ppt 离散数学第二章谓词逻辑-4-6节
doc 实验小学二年级数学下学期开学考试试题赣南版B卷 附解析
doc 云南省2020年实验小学一年级语文【下册】期末考试试题 附答案
doc 实验小学二年级数学下学期开学考试试题部编版B卷 附答案
doc 实验小学二年级数学下学期开学考试试题豫教版(I卷) 附解析
doc 2019-2020年高三上学期期中质量评估化学试题
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 (附解析)
ppt 《抑郁症发生的原因》PPT课件
doc 云南省2020年实验小学一年级语文【下册】开学考试试卷 附解析
ppt 《把课文认真读几遍》PPT课件
ppt 离散数学第十章基本图类及算法习题答案
doc 2020年六年级数学【上册】期末考试试题外研版(II卷) 附解析
ppt 离散数学第二章谓词逻辑-2-3节
doc 实验小学二年级数学下学期开学考试试题豫教版A卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 (附答案)
ppt 《抒情散文思路》PPT课件
doc 云南省2020年实验小学一年级语文【下册】期中考试试题 含答案
doc 云南省2020年实验小学一年级语文【上册】开学摸底考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题豫教版C卷 附答案
doc 山东省重点小学三年级数学【下册】开学考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题西南师大版C卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习D卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题西南师大版C卷 含答案
doc 2019-2020年高三上学期期中题数学文
doc 云南省2020年实验小学一年级语文【下册】期末考试试卷 附答案
doc 云南省2020年实验小学一年级语文【上册】期末考试试卷 含答案
doc 2019-2020学年高二英语上学期阶段联考试题(二)
doc 山东省重点小学三年级数学【下册】期中摸底考试试题 (含答案)
doc 广东省重点小学四年级数学下学期期末摸底考试试题C卷 附解析
doc 2019-2020年高三上学期期中质量抽测语文试题含答案
doc 实验小学二年级数学下学期开学考试试题赣南版(II卷) 附解析
doc 山东省重点小学三年级数学【下册】开学考试试题 附答案
doc 2020年六年级数学【上册】期末考试试题外研版 含答案
ppt 离散数学讲义第二章命题逻辑
doc 云南省2020年实验小学一年级语文【上册】期中摸底考试试卷 附解析
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 (附答案)
doc 实验小学二年级数学下学期开学考试试题长春版B卷 含答案
doc 实验小学二年级数学下学期开学考试试题西南师大版(II卷) 附答案
doc 2019-2020年高三上学期期中质量抽测语文试题 Word版含答案
doc 实验小学二年级数学下学期开学考试试题赣南版 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 (含答案)
doc 云南省2020年实验小学一年级语文【上册】期中考试试题 附解析
doc 2020年六年级数学【上册】期末考试试题外研版A卷 附解析
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 附答案
ppt 离散数学第二章命题逻辑等值演算
doc 实验小学二年级数学下学期开学考试试题长春版 含答案
doc 云南省2020年实验小学一年级语文【下册】期中考试试题 附解析
doc 2020年六年级数学【上册】期末考试试题外研版B卷 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题C卷 (附答案)
doc 2020年一级建造师《建筑工程管理与实务》综合练习(II卷) 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测(I卷) (附答案)
ppt 离散数学绪论、命题
doc 实验小学二年级数学下学期开学考试试题赣南版A卷 附答案
doc 实验小学二年级数学下学期开学考试试题部编版 附解析
doc 云南省2020年实验小学一年级语文【下册】期末考试试卷 附解析
doc 云南省2020年实验小学一年级语文【上册】期中摸底考试试题 含答案
ppt 《抓特征重文采》PPT课件
doc 云南省2020年实验小学一年级语文【下册】期末考试试题 附解析
doc 云南省2020年实验小学一年级语文【下册】期末摸底考试试卷 附解析
doc 2020年六年级数学【上册】期末考试试题北师大版(II卷) 附答案
doc 实验小学二年级数学下学期开学考试试题豫教版(II卷) 含答案
doc 山东省重点小学三年级数学【下册】期中摸底考试试卷 (附解析)
doc 2020年六年级数学【上册】期末考试试题人教版(I卷) 含答案
ppt 《抓住典型案例》PPT课件
ppt 《抓特征性词语》PPT课件
doc 2019-2020年高三上学期期中质量检测生物试题 Word版含答案
doc 山东省重点小学三年级数学【下册】开学考试试卷 (附答案)
doc 2019-2020年高三上学期期中质量检测历史试题 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测(I卷) (附解析)
doc 实验小学二年级数学下学期开学考试试题部编版 含答案
doc 实验小学二年级数学下学期开学考试试题豫教版 附解析
doc 广东省重点小学四年级数学下学期期末摸底考试试卷(I卷) (附解析)
doc 山东省重点小学三年级数学【下册】开学考试试卷 (含答案)
ppt 《抓常规养习惯》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 含答案
ppt 《抒情的诗现代诗》PPT课件
doc 实验小学二年级数学下学期开学考试试题豫教版B卷 附答案
doc 2020年六年级数学【上册】期末考试试题北师大版(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题西南师大版(I卷) 附答案
doc 云南省2020年实验小学一年级语文【上册】期末摸底考试试题 含答案
doc 实验小学二年级数学下学期开学考试试题部编版A卷 附解析
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 附答案
ppt 离散数学第二章关系
doc 实验小学二年级数学下学期开学考试试题部编版B卷 附解析
doc 2019-2020学年高二英语上学期阶段考试试题二
doc 实验小学二年级数学下学期开学考试试题部编版C卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷(I卷) 附答案
doc 2019-2020年高三上学期期中阶段性测评 化学
doc 2019-2020年高三上学期期中质量检测语文试题(含附加题)含答案
ppt 离散数学第九章代数系统
doc 山东省重点小学三年级数学【上册】期末考试试题 含答案
ppt 《抓准四点六朝古都》PPT课件
doc 实验小学二年级数学下学期开学考试试题部编版A卷 附答案
doc 云南省2020年实验小学一年级语文【下册】期末摸底考试试题 含答案
ppt 《把铁路修到拉萨去》PPT课件
doc 2019-2020年高三上学期期中质量抽测语文试题 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷(II卷) 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习D卷 附解析
doc 云南省2020年实验小学一年级语文【上册】开学考试试题 附解析
doc 2020年六年级数学【上册】期末考试试题北师大版B卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 附答案
doc 实验小学二年级数学下学期开学考试试题豫教版(I卷) 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题豫教版C卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测(I卷) 含答案
doc 云南省2020年实验小学一年级语文【下册】期中摸底考试试题 含答案
doc 云南省2020年实验小学一年级语文【上册】开学摸底考试试题 含答案
ppt 《把目标管理之剑》PPT课件
doc 实验小学二年级数学下学期开学考试试题西南师大版A卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 附解析
ppt 《把课堂还给学生》PPT课件
doc 2019-2020年高三上学期期中题语文
doc 山东省重点小学三年级数学【下册】开学考试试题 附解析
doc 云南省2020年实验小学一年级语文【上册】期中考试试题 附答案
doc 2019-2020年高三上学期期中质量检测理科综合试题 含答案
doc 云南省2020年实验小学一年级语文上学期开学摸底考试试卷 附答案
doc 山东省重点小学三年级数学【下册】开学考试试题 (附答案)
doc 2019-2020学年高二英语上学期第十次双周考试题
doc 山东省重点小学三年级数学【上册】期末考试试卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习(II卷) (附答案)
doc 山东省重点小学三年级数学【下册】开学考试试卷 含答案
ppt 《把路修到拉萨去》PPT课件
doc 2019-2020年高三上学期期中质量监测理综试题 含答案
doc 云南省2020年实验小学一年级语文【下册】开学考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版C卷 附解析
doc 2019-2020学年高二英语上学期第四次月考(12月)试题(含解析)
doc 实验小学二年级数学下学期开学考试试题部编版A卷 含答案
doc 山东省重点小学三年级数学【上册】期末考试试卷 附答案
doc 2019-2020学年高二英语上学期阶段联考试题二
doc 实验小学二年级数学下学期开学考试试题长春版 附解析
doc 云南省2020年实验小学一年级语文【上册】期末摸底考试试卷 附答案
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 (含答案)
doc 2019-2020年高三上学期期中质量检测物理试题
doc 2020年六年级数学【上册】期末考试试题外研版(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题豫教版(II卷) 附答案
doc 2019-2020年高三上学期期中质量检测理科数学试题含答案
doc 2020年一级建造师《建筑工程管理与实务》综合检测(I卷) 附解析
doc 实验小学二年级数学下学期开学考试试题赣南版C卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版B卷 含答案
doc 实验小学二年级数学下学期开学考试试题部编版(II卷) 含答案
doc 山东省重点小学三年级数学【下册】期中摸底考试试卷 含答案
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试题 附解析
doc 2019-2020年高三上学期期中质量抽测英语试题含答案
doc 云南省2020年实验小学一年级语文【下册】开学考试试题 附答案
doc 山东省重点小学三年级数学【下册】期中摸底考试试题 (附答案)
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 (附解析)
doc 2020年一级建造师《建筑工程管理与实务》综合练习(II卷) 含答案

离散数学第十一章

 版权申诉  ppt " "1" "第十一章 格与布尔代数" "主要内容 格的定义及性质 子格 分配格、有补格 布尔代数" "2" "11.1 格的定义与性质 " "定义11.1 设是偏序集,如果x,yS,{x,y}都有最小上 界和最大下界,则称S关于偏序≼作成一个格. 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧," "例1 设n是正整数,Sn是n的正因子的集合. D为整除关系,则 偏序集构成格. x,y∈Sn,x∨y是lcm(x,y),即x与y的 最小公倍数. x∧y是gcd(x,y),即x与y的最大公约数. " "3" "图2" "例2 判断下列偏序集是否构成格,并说明理由. (1) ,其中P(B)是集合B的幂集. (2) ,其中Z是整数集,≤为小于或等于关系. (3) 偏序集的哈斯图分别在下图给出. " "实例 " "(1) 幂集格. x,y∈P(B),x∨y就是x∪y,x∧y就是x∩y. (2) 是格. x,y∈Z,x∨y = max(x,y),x∧y = min(x,y), (3) 都不是格. 可以找到两个结点缺少最大下界或最小上界" "4" "实例:子群格" "例3 设G是群,L(G)是G 的所有子群的集合. 即 L(G) = { H | H≤G }, 对任意的H1, H2∈L(G),H1∩H2是G 的子群,是由 H1∪H2生成的子群(即包含着H1∪H2的最小子群). 在L(G)上定义包含关系,则L(G)关于包含关系构成一个 格,称为G的子群格. 在 L(G)中, H1∧H2 就是 H1∩H2 H1∨H2 就是 " "5" "格的性质:对偶原理" "定义11.2 设 f 是含有格中元素以及符号 =,≼ ,≽ ,∨和∧的命题. 令 f*是将 f 中的≼替换成≽,≽替换成≼,∨替换成∧,∧替换成∨ 所得到的命题. 称 f* 为 f 的对偶命题. 例如, 在格中令 f 是 (a∨b)∧c≼c, f*是 (a∧b)∨c≽c ." "格的对偶原理 设 f 是含有格中元素以及符号=,≼,≽,∨和∧等的命题. 若 f 对 一切格为真, 则 f 的对偶命题 f*也对一切格为真. 例如, 如果对一切格L都有 a,b∈L, a∧b≼a,那么对一切格L 都有 a,b∈L, a∨b≽a 注意:对偶是相互的,即 ( f*)*= f" "6" "格的性质:算律" "定理11.1 设是格, 则运算∨和∧适合交换律、结合律、 幂等律和吸收律, 即 (1) a,b∈L 有 a∨b = b∨a, a∧b = b∧a (2) a,b,c∈L 有 (a∨b)∨c = a∨(b∨c), (a∧b)∧c = a∧(b∧c) (3) a∈L 有  a∨a = a, a∧a = a (4) a,b∈L 有  a∨(a∧b) = a, a∧(a∨b) = a " "7" "证明" "(1) a∨b是{ a, b }的最小上界, b∨a是{ b, a }的最小上界. 由于 { a, b } = { b, a }, 所以 a∨b = b∨a. 由对偶原理, a∧b = b∧a. " "(2) 由最小上界的定义有  (a∨b)∨c≽a∨b≽a (1)  (a∨b)∨c≽a∨b≽b  (2)  (a∨b)∨c≽c   (3) 由式(2)和(3)有 (a∨b)∨c≽b∨c   (4) 由式(1)和(4)有 (a∨b)∨c≽a∨(b∨c) 同理可证 (a∨b)∨c≼a∨(b∨c) 根据反对称性 (a∨b)∨c = a∨(b∨c) 由对偶原理, (a∧b)∧c = a∧(b∧c)" "8" "证明" "(3) 显然 a ≼ a∨a, 又由 a ≼ a 可得 a∨a ≼a. 根据反对称性有a∨a = a . 由对偶原理, a∧a = a 得证. (4) 显然  a∨(a∧b)≽ a (5) 由 a ≼a, a∧b ≼ a 可得 a∨(a∧b) ≼a (6) 由式(5)和(6) 可得 a∨(a∧b) = a, 根据对偶原理, a∧(a∨b) = a " "9" "格的性质:序与运算的关系" "定理11.2 设L是格, 则a,b∈L有 a ≼ b  a∧b = a  a∨b = b" "证 (1) 先证 a ≼ b  a∧b = a 由 a ≼ a 和 a ≼ b 可知 a 是{ a,b }的下界, 故 a ≼ a∧b. 显然有a∧b ≼ a. 由反对称性得 a∧b = a. (2) 再证 a∧b = a  a∨b = b 根据吸收律有 b = b∨(b∧a) 由 a∧b = a 和上面的等式得 b = b∨a, 即 a∨b = b. (3) 最后证 a∨b = b  a≼b 由 a ≼ a∨b 得 a ≼ a∨b = b " "10" "格的性质:保序" "定理11.3 设L是格, a,b,c,d∈L,若a ≼ b 且 c ≼ d, 则 a∧c ≼ b∧d, a∨c ≼ b∨d" "例4 设L是格, 证明a,b,c∈L有 a∨(b∧c) ≼ (a∨b)∧(a∨c)." "证 a∧c ≼ a ≼ b, a∧c ≼ c ≼ d 因此 a∧c ≼ b∧d. 同理可证 a∨c ≼ b∨d " "证 由 a ≼ a, b∧c ≼ b 得 a∨(b∧c) ≼ a∨b 由 a ≼a, b∧c ≼ c 得 a∨(b∧c) ≼ a∨c 从而得到a∨(b∧c) ≼ (a∨b)∧(a∨c) 注意:一般说来, 格中的∨和∧运算不满足分配律. " "11" "格作为代数系统的定义" "定理11.4 设是具有两个二元运算的代数系统, 若对于 ∗和◦运算适合交换律、结合律、吸收律, 则可以适当定义S中 的偏序 ≼,使得 构成格, 且a,b∈S 有 a∧b = a∗b, a∨b = a◦b. 证明省略. 根据定理11.4, 可以给出格的另一个等价定义. " "定义11.3 设是代数系统, ∗和◦是二元运算, 如果 ∗和◦满足交换律、结合律和吸收律, 则构成格." "12" "子格及其判别法" "定义11.4 设是格, S是L的非空子集, 若S关于L中的运算∧和∨仍构成格, 则称S是L的子格. " "例5 设格L如图所示. 令 S1={a, e, f, g}, S2={a, b, e, g} S1不是L的子格, 因为e, fS1 但 e∧f = cS1. S2是L的子格. " "13" "11.2 分配格、有补格与布尔代数 " "定义11.5 设是格, 若a,b,c∈L,有  a∧(b∨c) = (a∧b)∨(a∧c)   a∨(b∧c) = (a∨b)∧(a∨c) 则称L为分配格. 注意:可以证明以上两个条件互为充分必要条件" "L1 和 L2 是分配格, L3 和 L4不是分配格. 称 L3为钻石格, L4为五角格." "实例" "14" "分配格的判别及性质" "定理11.5 设L是格, 则L是分配格当且仅当L不含有与钻石格 或五角格同构的子格. 证明省略. 推论 (1) 小于五元的格都是分配格. (2) 任何一条链都是分配格.  例6 说明图中的格是否为分配格, 为什么?" "解 都不是分配格. { a,b,c,d,e }是L1的子格, 同构于钻石格 { a,b,c,e,f }是L2的子格, 同构于五角格; { a,c,b,e,f } 是L3的子格 同构于钻石格. " "15" "有界格的定义" "定义11.6 设L是格, (1) 若存在a∈L使得x∈L有 a ≼ x, 则称a为L的全下界 (2) 若存在b∈L使得x∈L有 x ≼ b, 则称b为L的全上界  说明: 格L若存在全下界或全上界, 一定是惟一的. 一般将格L的全下界记为0, 全上界记为1. 定义11.7 设L是格,若L存在全下界和全上界, 则称L 为有界 格, 一般将有界格L记为. " "16" " " "定理11.6 设是有界格, 则a∈L有 a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1" "注意: 有限格L={a1,a2,…,an}是有界格, a1∧a2∧…∧an是L的全下界, a1∨a2∨…∨an是L的全上界. 0是关于∧运算的零元,∨运算的单位元;1是关于∨运算的零元,∧运算的单位元. 对于涉及到有界格的命题, 如果其中含有全下界0或全上界1, 在求该命题的对偶命题时, 必须将0替换成1, 而将1替换成0." "有界格的性质" "17" "有界格中的补元及实例" "定义11.8 设是有界格, a∈L, 若存在b∈L 使得  a∧b = 0 和 a∨b = 1 成立, 则称b是a的补元. 注意:若b是a的补元, 那么a也是b的补元. a和b互为补元. " "例7 考虑下图中的格. 针对不同的元素,求出所有的补元." "18" "解答" "(1) L1中 a 与 c 互为补元, 其中 a 为全下界, c为全上界, b 没有 补元. (2) L2中 a 与 d 互为补元, 其中 a 为全下界, d 为全上界, b与 c 也互为补元. (3) L3中a 与 e 互为补元, 其中 a 为全下界, e 为全上界, b 的补 元是 c 和 d ; c 的补元是 b 和 d ; d 的补元是 b 和 c ; b, c, d 每个元素都有两个补元.  (4) L4中 a 与 e 互为补元, 其中 a 为全下界, e 为全上界, b 的补 元是 c 和 d ; c 的补元是 b ; d 的补元是 b . " "19" "有界分配格的补元惟一性" "定理11.7 设是有界分配格. 若L中元素 a 存在 补元, 则存在惟一的补元. 证 假设 c 是 a 的补元, 则有   a∨c = 1, a∧c = 0, 又知 b 是 a 的补元, 故   a∨b = 1, a∧b = 0  从而得到 a∨c = a∨b, a∧c = a∧b, 由于L是分配格, b = c. " "" "注意: 在任何有界格中, 全下界0与全上界1互补. 对于一般元素, 可能存在补元, 也可能不存在补元. 如果存在补元, 可能是惟一的, 也可能是多个补元. 对于有界分配格, 如果元素存在补元, 一定是惟一的. " "20" "图9" "有补格的定义" "定义11.9 设是有界格, 若L中所有元素都有补 元存在, 则称L为有补格. 例如, 图中的L2, L3和L4是有补格, L1不是有补格. " "21" "布尔代数的定义与实例" "定义11.10 如果一个格是有补分配格, 则称它为布尔格或布 尔代数. 布尔代数标记为, 为求补运算. " "例8 设 S110 = {1, 2, 5, 10, 11, 22, 55, 110}是110的正因子集合,gcd表示求最大公约数的运算,lcm表示求最小公倍数的运算,问是否构成布尔代数?为什么?" "解 (1) 不难验证S110关于gcd 和 lcm 运算构成格. (略) (2) 验证分配律 x, y, z∈S110 有  gcd(x, lcm(y, z)) = lcm(gcd(x, y), gcd(x, z)) (3) 验证它是有补格, 1作为S110中的全下界, 110为全上界,  1和110互为补元, 2和55互为补元, 5和22互为补元, 10和 11互为补元, 从而证明了为布尔代数. " "22" "实例" "例9 设B为任意集合, 证明B的幂集格 构成布尔代数, 称为集合代数. 证 (1) P(B)关于∩和∪构成格, 因为∩和∪运算满足交换律, 结合律和吸收律. (2) 由于∩和∪互相可分配, 因此P(B)是分配格. (3) 全下界是空集, 全上界是B. (4) 根据绝对补的定义, 取全集为B,  x∈P(B), ~x是x的补元. 从而证明P(B)是有补分配格, 即布尔代数. " "23" "布尔代数的性质" "定理11.8 设是布尔代数, 则 (1) a∈B, (a) = a . (2) a,b∈B, (a∧b) = a∨b, (a∨b) = a∧b (德摩根律)" "证 (1) (a)是a的补元, a也是a的补元. 由补元惟一性得(a)=a. (2) 对任意a, b∈B有   (a∧b)∨(a∨b) = (a∨a∨b)∧(b∨a∨b)  = (1∨b)∧(a∨1) = 1∧1 = 1,  (a∧b)∧(a∨b) = (a∧b∧a)∨(a∧b∧b)  = (0∧b)∨(a∧0) = 0∨0 = 0 a∨b是a∧b的补元, 根据补元惟一性有(a∧b) = a∨b, 同理 可证 (a∨b) = a∧b. 注意:德摩根律对有限个元素也是正确的. " "24" "布尔代数作为代数系统的定义" "定义11.11 设是代数系统, ∗和◦是二元运算. 若∗和◦运 算满足: (1) 交换律, 即a,b∈B有a∗b = b∗a, a◦b = b◦a (2) 分配律, 即a,b,c∈B有 a∗(b◦c) = (a∗b)◦(a∗c),  a◦(b∗c) = (a◦b) ∗ (a◦c)  (3) 同一律, 即存在0,1∈B, 使得a∈B有a ∗1 = a, a◦0 = a (4) 补元律, 即a∈B, 存在 a∈B 使得 a ∗a = 0, a◦a = 1 则称 是一个布尔代数. 可以证明,布尔代数的两种定义是等价的. " "25" "有限布尔代数的结构" "定义11.12 设 L 是格, 0∈L, 若b∈L有 0 ≺ b ≼ a  b = a, 则 称 a 是 L 中的原子. " "实例:(1) L是正整数 n 的全体正因子关于整除关系构成的 格, 则L的原子恰为n的全体素因子. (2) 若L是B的幂集, 则L的原子就是B中元素构成的单元集 (3) 图中L1的原子是a, L2的原子是a, b, c, L3的原子是a 和 b" "26" "有限布尔代数的表示定理" "定理11.9 (有限布尔代数的表示定理) 设B是有限布尔代数, A是B的全体原子构成的集合, 则B同构 于A的幂集代数P(A)." "实例: (1) S110关于gcd, lcm运算构成的布尔代数. 它的原子是 2, 5和11, 因此原子的集合A = {2,5,11}. 幂集 P(A) = {,{2},{5},{11},{2,5},{2,11},{5,11},{2,5,11}}. 幂集代数是< P(A),∩,∪,~, , A>. 只要令 f: S110→P(A), f(1) = , f(2) = {2}, f(5) = {5}, f(11) = {11}, f(10) = {2,5}, f(22) = {2, 11}, f(55) = {5, 11}, f(110) = A, 那么 f 就是从S110到幂集P(A)的同构映射. " "27" "推论" "推论1 任何有限布尔代数的基数为2n, n∈N. 证 设B是有限布尔代数, A是B的所有原子构成的集合, 且 |A| = n, n∈N. 由定理得 B  P(A), 而 |P(A)| = 2n, 所以 |B| = 2n. 推论2 任何等势的有限布尔代数都是同构的. (证明省略) 结论 : 有限布尔代数的基数都是2的幂, 对于任何自然数n, 仅存在一个2n元的布尔代数. " "28" "图11" "实例" "下图给出了 1 元, 2 元, 4 元和 8 元的布尔代数. " "29" "第十一章 习题课" "主要内容 格的两个等价定义 格的性质 子格 特殊格:分配格、有界格、有补格、布尔代数 基本要求 能够判别给定偏序集或者代数系统是否构成格 能够确定一个命题的对偶命题 能够证明格中的等式和不等式 能判别格L的子集S是否构成子格 能够判别给定的格是否为分配格、有补格 能够判别布尔代数并证明布尔代数中的等式 " "30" "练习1" "1.(1) 证明格中的命题, 即 (a∧b)∨b = b (2) 证明 (a∧b)∨(c∧d)≼(a∨c)∧(b∨d)" "(1) (a∧b)∨b是a∧b与b的最小上界, 根据最小上界的定义 有(a∧b)∨b≽b . b是a∧b与b的上界, 故有(a∧b)∨b≼b. 由于 偏序的反对称性, 等式得证. " "(2) a∧b≼a≼a∨c, a∧b≼b≼b∨d, 所以 (a∧b)≼(a∨c)∧(b∨d), 同理 (c∧d)≼(a∨c)∧(b∨d). 从而得到 (a∧b)∨(c∧d)≼(a∨c)∧(b∨d) " "31" "解" "2.求图中格的所有子格." "1元子格:{ a },{ b },{ c },{ d },{ e }; 2元子格:{ a, b },{ a, c },{ a, d }, { a, e },{ b, c },{ b, d }, { b, e },{ c, e },{ d, e }; 3元子格:{ a, b, c },{ a, b, d }, { a, b, e },{ a, c, e }, { a, d, e },{ b, c, e }, { b, d, e }; 4元子格:{ a, b, c, e },{ a, b, d, e }, { b, c, d, e }; 5元子格: { a, b, c, d, e }" "练习2" "32" "图13" "3.判别下述格L是否为分配格. " "L1不是分配格, 因为它含有与钻石格同构的子格. L2和L3不是分配格, 因为它们含有与五角格同构的子格." "练习3" "33" "图12" "4.针对下图,求出每个格的补元并说明它们是否为有补格" "L1中, a与h互为补元, 其他元素没补元. L2中, a与g互为补元. b的补元为c, d, f;c的补元为b, d, e, f;d的补元为b, c, e;e的补元为c, d, f;f的补元为b, c, e. L3中, a与h互为补元, b的补元为d;c的补元为d;d的补元为b, c, g;g的补元为d. L2与L3是有补格." "练习4" "34" "5.对于以下各题给定的集合和运算判断它们是哪一类代数 系统(半群、独异点、群、环、域、格、布尔代数), 并说 明理由. (1) S1 = {1, 1/2, 2, 1/3, 3, 1/4, 4}, ∗为普通乘法. (2) S2 = {a1, a2, ..., an}, ai, aj∈S2, ai∘aj = ai, 这里的 n 为给定 正整数, n>1. (3) S3 = {0, 1},∗为普通乘法. (4) S4 = {1, 2, 3, 6}, x,y∈S4, x∘y与x∗y分别表示 x 与 y 的最小公倍数和最大公约数. (5) S5 = {0, 1}, ∗为模2加法, ∘为模2乘法. " "练习5" "35" "解: " "解答" "(1) 不是代数系统, 因为乘法不封闭, 例如4∗4=16. (2) 是半群但不是独异点, 因为∗运算满足结合律, 但是没有单 位元. (3) 是独异点但不是群. 因为∗运算满足结合律, 单位元是1, 可 是0没有乘法逆元. (4) 是格, 也是布尔代数. 因为这两个运算满足交换律和分配 律;求最小公倍数运算的单位元是1, 求最大公约数运算 的单位元是6, 满足同一律;两个运算满足补元律. (5) 是域. 对于模 n 的环Zn, 当n为素数时构成域. " "36" "证 (2) 由 反之也对.下面证 明它们都等价于a≤b. 由 得 即 a≤b, 又由 a≤b 得 " "" "" "6.设是布尔代数, 证明对于B中任意元素 a,b" "练习6" "" "37" "练习7" "7. 判断下述代数系统是否为格?是不是布尔代数? (1) S = {1, 3, 4, 12}; 任给 x, y∈S, x∘y = lcm(x,y), x∗y = gcd(x,y), 其中 lcm 是求最小公倍数, gcd 是求最大公约数. (2) S = {0, 1, 2}; ∘是模3加法, ∗是模3乘法 (3) S = {0, ..., n}, 其中n≥2; 任给 x, y∈S, x∘y = max(x,y), x∗y = min(x,y) " "(1) 是布尔代数. (2) 不是格. (3) 是格, 但不是布尔代数.








































 版权投诉/申诉   非法内容举报    本页不提供全部页面预览,未展示部分请购买并下载后观看使用