《格与布尔代数.pdf》由会员分享，可在线阅读，更多相关《格与布尔代数.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1/10 授课时间 第 十三周 第 1/2 次课 授课章节 6.2 环合域 任课教师 及职称 唐新华 讲师 教学方法 与手段 板书和电子课件结合 课时安排 2 课时 使用教材和 主要参考书 1、教材：耿素云等，离散数学，清华大学出版社，2008 2.参考书 左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006 教学与目的要求：1、判别给定代数系统是否为环、交换环、含幺环、无零因子环、整环和域；2、了解环的运算性质,能进行环中的运算；3、能判别环的子集是否为子环；4、能判别映射是环 R1 到 R2 的同态映射。教学重点、难点:重点：环的定义及其运算规则、子环、交换环、含幺环、无零因子环、整
2、环。难点：环的同态、整环和域 教学内容:6.3 格与布尔代数 一、本节主要内容 格的定义与实例 格的性质 对偶原理 交换律、结合律、幂等律、吸收律 格的等价定义 子格 格的同构 特殊的格：分配格、有界格、有补格、布尔格 二、教学内容 格的定义 定义 设是偏序集，如果x,yS，x,y都有 最小上界和最大下界，则称 S 关于偏序构成一个格。由于最小上界和最大下界的惟一性，可以把求x,y 的最小上界和最大下界看成 x 与 y 的二元运算和，即 xy 和 xy 分别表示 x 与 y 的最小上界和 最大下界.2/10 注意：这里出现的和符号只代表格中的运算，而不再有其他的含义.格的实例 例 设 n 是正
3、整数，Sn 是 n 的正因子的集合.D 为 整除关系，则偏序集构成格.x,ySn，xy 是 lcm(x,y)，即 x 与 y 的最小公倍数.xy 是 gcd(x,y)，即 x 与 y 的最大公约数.下图给出了格，和.格的实例（续）3/10 例 判断下列偏序集是否构成格，并说明理由.(1)，其中 P(B)是集合 B 的幂集.(2)，其中 Z 是整数集，为小于等于关系.(3)偏序集的哈斯图分别在下图给出.格的性质：对偶原理 定义 设 f 是含有格中元素以及符号=,和的 命题.令 f*是将 f 中的替换成,替换成,替换成,替换成所得到的命题.称 f*为 f 的对偶命题.例如,在格中：f 是(ab)c
4、c,f*是(ab)cc.格的对偶原理：设 f 是含格中元素以及符号=,和等的命题.若 f 对一切格为真,则 f 的对偶命题 f*也对一切格为真.例如,若对一切格 L 都有 a,bL,aba，那么对一 切格 L 都有 a,bL,aba 格的性质：算律 定理 设是格,则运算和适合交换律、结 合律、幂等律和吸收律,即(1)a,bL 有 ab=ba,ab=ba(2)a,b,cL 有 (ab)c=a(bc),(ab)c=a(bc)(3)aL 有 aa=a,aa=a(4)a,bL 有 a(ab)=a,a(ab)=a 算律的证明 证 (1)交换律.ab 是 a,b 的最小上界 ba 是 b,a的最小上界 a
5、,b =b,a ab=ba.由对偶原理,ab=ba 得证.算律的证明（续）(2)结合律.由最小上界的定义有 (ab)caba (I)(ab)cabb (II)(ab)cc (III)由式(II)和(III)有 (ab)cbc (IV)由式(I)和(IV)有 (ab)ca(bc).同理可证 (ab)c a(bc).根据偏序的反对称性得到 4/10 (ab)c=a(bc).由对偶原理,(ab)c=a(bc)得证.算律的证明（续）(3)幂等律.显然 a aa,又由 a a 得 aa a.由反对称性 aa=a.用对偶原理,aa=a 得证.(4)吸收律.显然有 a(ab)a (V)由 a a,ab a
6、可得 a(ab)a (VI)由式(V)和(VI)可得 a(ab)=a 根据对偶原理,a(ab)=a 得证.格作为代数系统的定义 定理 设是具有两个二元运算的代数系统,若对于和运算适合交换律、结合律、吸收律,则 可以适当定义 S 中的偏序,使得构成格,且 a,bS 有 ab=ab,ab=a b.根据定理,可以给出格的另一个等价定义.定义 设是代数系统,和 是二元运算,如果 和 运算满足交换律、结合律和吸收律,则 构成格.子格的定义及判别 定义 设是格,S 是 L 的非空子集,若 S 关于 L 中运算和仍构成格,则称 S 是 L 的子格.例 设格 L 如图所示.令 S1=a,e,f,g,S2=a,
7、b,e,g S1 不是 L 的子格,S2 是 L 的子格.因为对于 e,fS1，efS1.5/10 格同态 定义 设 L1 和 L2 是格,f:L1L2,若a,bL1 有 f(ab)=f(a)f(b),f(ab)=f(a)f(b)成立,则称 f 为格 L1 到 L2 的同态映射,简称格同态.分配格定义 定义 设是格,若a,b,cL,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称 L 为分配格.注意：以上条件互为充分必要条件 这两个等式中只要有一条成立，另一条一定成立.在证明 L 为分配格时,只须证明其中的一个等式即可.分配格的定义（续）6/10 分配格的判定及其性质 定理 设
8、 L 是格,则 L 是分配格当且仅当 L 不含有 与钻石格或五角格同构的子格.证明省略.定理 格 L 是分配格当且仅当 a,b,cL,ab=ac 且 ab=ac b=c.推论 (1)小于五元的格都是分配格.(2)任何一条链都是分配格.分配格的判定（续）7/10 解 L1,L2 和 L3 都不是分配格.a,b,c,d,e 是 L1 的子格,并且同构于钻石格；a,b,c,e,f 是 L2 的子格,并且同构于五角格；a,c,b,e,f 是 L3 的子格,也同构于钻石格.全上界与全下界 定义 设 L 是格,若存在 aL 使得 xL 有 a x,则称 a 为 L 的全 下界；若存在 bL 使得 xL 有
9、 x b,则称 b 为 L 的全 上界.说明：格 L 若存在全下界或全上界,一定是惟一的.一般将格 L 的全下界记为 0,全上界记为 1.有界格定义及其性质 定义 设 L 是格,若 L 存在全下界和全上界,则称 L 为 有界格,全下界记为 0，全上界记为 1.有界格 L 记为 .注意：有限格 L=a1,a2,an是有界格,a1a2 an 是 L 的全下界,a1a2an 是全上界.0 是关于运算的零元,运算的单位元.1 是关于 运算的零元,运算的单位元.对于涉及有界格的命题,如果其中含有全下界 0 或全 上界 1,求其对偶命题时,必须将 0 与 1 互换.补元的定义 定义 设是有界格,aL,若存
10、在 bL 使得 ab=0 和 ab=1 成立,则称 b 是 a 的补元.注意：若 b 是 a 的补元,那么 a 也是 b 的补元.a 和 b 互为补元.实例:求补元 8/10 有界分配格中补元惟一性 定理 设是有界分配格.若 L 中元素 a 存在补元,则存在惟一的补元.证 假设 b,c 是 a 的补元,则有 ac=1,ac=0,ab=1,ab=0 从而得到 ac=ab,ac=ab,由于 L 是分配格,b=c.有补格的定义 定义 设是有界格,若 L 中所有元素都 有补元存在,则称 L 为有补格.例如,下图中的 L2,L3 和 L4 是有补格,L1 不是有补格.布尔代数的定义 定义 9/10 如果
11、一个格是有补分配格,则称它为布尔格或布尔 代数.在布尔代数中，如果一个元素存在补元,则是惟一 的.可以把求补元的运算看作是布尔代数中的一元 运算.布尔代数标记为,其中为求补 运算 布尔代数的实例 例 设 S110=1,2,5,10,11,22,55,110 是 110 的正 因子集合.gcd 表示求最大公约数的运算 lcm 表示求最小公倍数的运算.则 是否构成布尔代数？布尔代数的等价定义 定义 设是代数系统,和是二元运算.若 和运算满足交换律、结合律、幂等律、吸收律,即(1)a,bB 有ab=ba,ab=ba (2)a,b,cB 有 a(bc)=(ab)(ac),a(bc)=(ab)(ac)(
12、3)即存在 0,1B,使得aB 有 a1=a,a0=a (4)aB,存在 aB 使得 aa=0,aa=1 则称是一个布尔代数.可以证明，布尔代数的两种定义是等价的.布尔代数的性质 定理 设是布尔代数,则 (1)aB,(a)=a.(2)a,bB,(ab)=ab,(ab)=ab（德摩根律）注意：德摩根律对有限个元素也是正确的.证明 证(1)(a)是 a的补元.a 是 a 的补元.由补元惟一性得(a)=a.(2)对任意 a,bB 有 (ab)(ab)=(aab)(bab)=(1b)(a1)=11=1,(ab)(ab)=(aba)(abb)=(0b)(a0)=00=0.所以 ab是 ab 的补元,根据补元惟一性可得 (ab)=ab.同理可证(ab)=ab.有限布尔代数的表示定理 定理 设 L 是有限布尔代数，则 L 含有 2n 个元素 10/10(nN)，且 L 与 同构，其中 S 是 一个 n 元集合.结论：含有 2n 个元素的布尔代数在同构意义下只有 一个.复习思考题、作业题：6.11 12 12 14 下次课预习要点：习题和 6.4 例题分析 实施情况及教学效果分析:院系部审核意见:院系部负责人签字 年 月 日