离散数学及其应用 教学课件 ppt 作者 魏雪丽 第6章 格与布尔代数

第六章 格与布尔代数,6.1 格的概念及性质(Lattices & Theirs Properties ) 6.2 分配格（distributive lattices） 6.3 有补格(complemented Lattices) 6.4 布尔代数(Boolean algebra ) 6.5 布尔表达式(Boolean representative ),6.1 格的概念及性质（Lattices & theirs properties ）,6.1.1 格的概念（Lattices） 6.1.2 格的性质（The properties of lattices）,6.1 格的概念及性质(Lattices & theirs properties),本章将讨论另外两种代数系统格与布尔代数，它们与群、环、域的基本不同之处是：格与布尔代数的基集都是一个偏序集。这一序关系的建立及其与代数运算之间的关系是介绍的要点。格是具有两个二元运算的代数系统，它是一个特殊的偏序集，而布尔代数则是一个特殊的格。,在第三章，对偏序集的任一子集可引入上确界（最小上界）和下确界（最大下界）的概念，但并非每个子集都有上确界或下确界，例如在图6.1.1中哈斯图所示的偏序集里，24，36没有上确界，2，3没有下确界。然而有一些偏序集却有这样一个共同特征,即任意两个元素都有上、下确界(不妨把a，b的上(下)确界称为元素a，b的上(下)确界)。例如图6.1.2中哈斯图所示的偏序集。,6.1.1 格的概念（lattices） 1. 格的概念（lattices）,图6.1.1,6.1.1 格的概念（lattices）,图6.1.2,我们把具有这种性质的偏序集称为格。,6.1.1 格的概念（lattices）,定义6.1.1 如果偏序集L，中的任何两个元素都 有上确界和下确界,则称偏序集 L，为格（lattice）。 【例6.1.1】设n是一正整数,Sn是n的所有正因子的集合。例 如S6=1,2,3,6,S8=1,2,4,8, “|”是整除关系,则Sn, |是 格,因为 x,y Sn, LUBx,y= x与y的最小公倍数=LCMx,y, GLBx,y= x与y的最大公约数=GCDx,y。 例如S8, |,S6, |,S30, |的哈斯图如图6.1.2(a),(b),(c)所 示。,6.1.1 格的概念（lattices）,图 6.1.3,【例6.1.2】图6.1.3中的偏序集都不是格,因为图中a,b无上确界。,6.1.1 格的概念（lattices）,虽然偏序集合的任何子集的上确界、下确界并不一定都存在，但存在，则必唯一，而格的定义保证了任意两个元素的上确界、下确界的存在性。因此我们通常用ab表示a，b的上确界，用ab表示a，b的下确界，即 ab=LUBa,b（Least upper bound）, ab=GLBa,b(Greatest lower bound),6.1.1 格的概念（lattices）,和分别称为并（join）和交（meet）运算。 由于对任何a，b，ab及ab都是L中确定的成员，因此,均为L上的二元运算。这样我们便有如下定义: 定义6.1.2 设L，是一个格, 和分别为L上的并和交运算,则称代数系统L, 为由格L， 所诱导的代数系统。,6.1.1 格的概念（lattices）,【例6.1.3】 （1）对任意集合S，偏序集 ，为格， 其中并、交运算即为集合的并、交运算，即 BCBC BCBC 和在 上封闭,这里B,C , ，所诱导的代数系统为 ， , 。,6.1.1 格的概念（lattices）,【例6.1.3】 （2）设L为命题公式集合，逻辑蕴涵关系“”为L上的偏序关系（指定逻辑等价关系“ ”为相等关系），那么，L,为格，对任何命题公式A，B，AB=AB，AB=AB（等式右边的，为析取与合取逻辑运算符）,因此由 L,所诱导的代数系统为 L ， ， 。,6.1.1 格的概念（lattices）,（3）设Z+表示正整数集，“|”表示Z+上整除关系，那么 Z+ ，|为格，其中并、交运算即为求两正整数最小公倍数和最大公约数的运算，即 mnLCM（m,n） mnGCD(m,n）, 由 Z+ ，|所诱导的代数系统为 Z+ ， ， 。 （4）任一全序集A， 是一个格。因为 a,b A， 由A,所诱导的代数系统为 A ， 。,6.1.1 格的概念（lattices）,2.子格 若偏序集L，是格,非空集合B L,显然B, 也是一个偏序集,我们自然会问, B, 是否是格? 若B, 是格,是否对任意的a,bB,有 为此我们考察下面的例子。 【例6.1.4】设A，是一个格(如图6.1.4), 取 Bi, 的哈斯图如图6.1.4,图 6.1.4,显然偏序集 B1, 不是格,而 B2, , B5, 都构成格，但是在 B2, 中 B2关于“”不封闭。在 B5, 中 B5关于“”也不封闭。,6.1.1 格的概念（lattices）,而在 B3, 和 B4, 中, 显然对任意的 a,b B3或B4, 均有 即B3, B4关于A中的代数运算“”和“” 是封闭的。我们称 B3, 和 B4, 为 A, 的子格。,6.1.1 格的概念（lattices）,定义6.1.3 设L, 是一个格， L, 诱导的 代数系统为L, , , B为L的非空集合, 若B关于 L, , 中的运算和封闭,则称B, 是 L, 的子格。 【例6.1.5】Z+，|是一个格,其并、交运算即为求两正整数最小公倍数和最大公约数的运算，即 abLCM（a,b） abGCD(a,b）, Z2=2n |n Z+,则 Z2 ，|也是偏序集，且Z2关于Z+中的和 封闭，故 Z2 ，|是Z+，|的子格。,6.1.1 格的概念（lattices）,图 6.1.5,【例6.1.6】 设L, 是一个格，其中L=a,b,c,d,e,其哈斯图如图6.1.5所示。S1=a,b,c,d，S2=a,b,c,e,则S1, 是L, 的一个子格，S2, 不是L, 的一个子格，因为bc=dS2， S2, 不是格。 注意：子格必是格。而格的某个 子集构成格，却不一定是子格。,6.1.1 格的概念（lattices）,6.1.2 格的性质（The properties of lattices） 1.格对偶原理 给定一个偏序集合L, ,若将L, 中的小于等于关系换成大于等于关系，即对于L中任何两个元素a,b, 定义 ab的充分必要条件是ba(恰是的逆关系),则L, 也是偏序集。我们把偏序集L, 和L, 称为是相互对偶的。并且它们所对应的哈斯图是互为颠倒的。可以证明， 若L，是格， 则L，也是一个格， 我们说这两个格互为对偶。且L，的并、交运算r,r对任意a,bL满足 arb=ab arb=ab,若将格(L，)中一个命题P中的符号、 、 分别用、 代替，则得到一个新的命题P*，我们将这个新的命题P*称为原命题P的对偶命题。显然这两个命题互为对偶。于是，我们有下列对偶原理。 定理6.1.1 如果命题P对任意格都为真，则其对偶命题P*对任意格也为真。,6.1.2 格的性质（The properties of lattices）,2. 格的性质 现在我们深入地讨论格的性质。 定理6.1.2 设L,是一个格，那么对L中任何元素a,b,c,d, 有 （1） aab，bab aba，abb （2）若ab，cd，则acbd，acbd。 特别地, 若ca, cb, 则cab, 若ac , bc , 则abc 。 （3）若ab，则acbc，acbc。 性质（2），（3）称为格的保序性。,（4）aa=a，aaa (幂等律) （5）ab=ba, ab=ba （交换律） （6）a(bc)=(ab)c, a(bc)=(ab)c (结合律) （7）a(ab)=a, a(ab)=a (吸收律) （8）ab当且仅当ab=a当且仅当ab=b。,6.1.2 格的性质（The properties of lattices）,证明: （1）因为ab是a的一个上界，所以aab；同理有bab。由对偶原理可得aba，abb。 （2）由题设知ab，cd，由（1） 有bbd，dbd，于是由的传递性有 abd，cbd。 这说明bd是a和c的一个上界，而ac是a和c的最小上界，所以，必有 acbd 同理可证acbd。 （3）将（2）中的d换成c即可得证。,（4）由自反性可得aa，所以a是a的一个上界，因为aa是a与a的最小上界，因此aaa。 由（1）可知aaa。 由的反对称性，所以aa=a。利用对偶原理可得aaa。 （5）由（1）可知aab , bab ,即ab 是b和a的上界,所以 baab，同理可证abba，故 ab=ba。 同理可证 ab=ba 。,（6）由下确界定义知 a（bc）bcb (6.1.1) a（bc）a (6.1.2) a（bc）bcc (6.1.3) 由式(6.1.1)、(6.1.2)得 a（bc）ab (6.1.4) 由式(6.1.3)、(6.1.4)得 a（bc）(ab)c (6.1.5) ,6.1.2 格的性质（The properties of lattices）,同理可证 (ab)ca(bc) （6.1.6） 由的反对称性和式(6.1.5)、(6.1.6)，所以 a(bc)=(ab)c。利用对偶原理可得 a(bc)=(ab)c。 （7）由定理6.1.2的（1）可知a(ab)a；另一方面，由于aa，aab，所以aa(ab)，因此有a(ab)=a。 同理可证 a(ab)=a。,6.1.2 格的性质（The properties of lattices）,（8）首先设ab，因为aa,所以aab，而由定理6.1.2的（1）可知 aba。因此有ab=a。 再设a=ab，则ab=(ab)b=b（由吸收律），即ab=b。 最后，设bab，则由aab可得ab。 因此，（8）中3个命题的等价性得证。,6.1.2 格的性质（The properties of lattices）,【例6.1.7】（1）对任意非空集合S，格 ，所诱导的代数系统为 , , ，其中 , 都是可交换的、可结合的、幂等的、吸收的 。 由定理6.1.2可知，格是带有两个二元运算的代数系统，它的两个运算有上述(4)-(7)四个性质，那么具有上述四条性质的代数系统L,是否是格？回答是肯定的。为了解决这个问题，我们先给出下述引理。,6.1.2 格的性质（The properties of lattic