格与布尔代数课件.ppt

格与布尔代数,布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。是偏序集:是A上自反,反对称和传递关系(偏序).偏序集中的元素间的次序可以通过它的Hasse图反映出来. 例如A=1,2,3,6,12,24,36, 是A上整除关系其Hasse图如图所示，BA B,1,1. B的极小元与极大元 y是B的极小元yBx(xBxy) y是B的极大元yBx(xByx) 例如2,3,6的极小元:2,3 极大元:6,2. B的最小元与最大元 y是B的最小元yBx(xByx) y是B的最大元yBx(xBxy) 2,3,6的最小元:无 最大元: 6 B如果有最小元(最大元), 则是唯一的。3. B的下界与上界 y是B的下界yAx(xByx) y是B的上界yAx(xBxy) 2,3,6的下界:1 上界: 6,12,24,364. B的最大下界(下确界)与最小上界(上确界) y是B的最大下界(下确界)：B的所有下界x,有xy。 y是B的最小上界(上确界)：B的所有上界x,有yx。 2,3,6下确界:1 上确界:6 (B若有下(上)确界,则唯一),2,1 格 (Lattice),一 . 基本概念1. 格的定义 是偏序集，如果任何a,bA,使得a,b都有最大下界和最小上界，则称是格。 右图三个偏序集,哪个是格？,3,不是格，因为24,36无最小上界。和是格。再看下面三个偏序集，哪个是格？,第一个与第三个是同构的。因为 d和e无下界，也无最小上界；b,c虽有下界，但无最大下界。 第二个图：2,3无最大下界，4,5无最小上界。 这三个偏序集，都不是格，2. 平凡格：所有全序都是格，称之为平凡格。 因为全序中任何两个元素x,y，要么xy, 要么yx。 如果xy，则x,y的最大下界为x，最小上界为y。 如果yx，则x,y的最大下界为y，最小上界为 x 。即这x,y的最大下界为较小元素，最小上界为较大元素.,4,3. 由格诱导的代数系统设是格,在A上定义二元运算和为:a,bAab=LUB a,b, a,b的最小上界.Least Upper Boundab=GLB a,b, a,b的最大下界.Greatest Lower Bound称是由格诱导的代数系统. (-并,-交) 例如右边的格中ab=b ab=a bc=e,5,4. 子格：设是格, 是由诱导的代数系统。B是A的非空子集，如果和在B上封闭，则称是的子格。,是的子格。而不是. 因bc=dB, (判定子格：看去掉的元素是否影响封闭),二. 格的对偶原理 设是格，的逆关系记作，也是偏序关系。所以也是格，的Hasse图是将的Hasse图颠倒180即可。 格的对偶原理：设P是对任何格都为真的命题，如果将P中的换成，换成，换成，就得到命题P , 称P为P的对偶命题，则P对任何格也是为真的命题。 例如：P: aba P: aba a,b的最大下界a a,b的最小上界a三. 格的性质 是由格诱导的代数系统。a,b,c,dA1. aab bab aba abb 此性质由运算和的定义直接得证。,6,2.如果ab，cd，则 acbd，acbd。证明：如果ab，又bbd, 由传递性得abd, 类似由cd， dbd，由传递性得cbd,这说明bd是a,c的上界，而ac是a,c的最小上界，所以acbd。 类似可证 acbd。推论：在一个格中，任何 a,b,cA，如果bc，则 abac，abac。 此性质称为格的保序性。3. 和都满足交换律。即 ab=ba，ab=ba。 此性质由运算和的定义直接得证。,7,4. 和都满足幂等律。即 aa=a aa=a 证明：由性质1 得 aaa (再证aaa) 由自反得aa, 这说明a是a的上界，而aa是a的最小上界，所以 aa a。最后由反对称得 aa=a 。 由对偶原理得 aa=a 5. 和都满足结合律。即 (ab)c =a(bc) ， (ab)c =a(bc) 。 证明：先证明(ab)c a(bc) a a(bc) bbc a(bc) (ab) a(bc) cbc a(bc) (ab)c a(bc) 同理可证 a(bc)(ab)c 最后由反对称得 (ab)c =a(bc) 类似可证 (ab)c =a(bc) 。,8,6. 和都满足吸收律。即 a( ab) =a， a(ab) =a。证明：显然有 aa( ab) .再证 a( ab) a a a ab a a( ab) a最后由反对称得 a( ab) =a， 类似可证 a(ab) =a。7. 是代数系统，如果和是满足吸收律的二元运算，则和必满足幂等律。证明：任取a,bA 和是满足吸收律。有 a( ab) =a - a(ab) =a -。由于上式中的b是任意的，可以令b=ab 并代入式得 a(a(ab) =a 由式得 aa=a 同理可证aa=a,9,8. 和不满足分配律。但有分配不等式： a(bc) (ab)(ac) ， (ab)(ac) a(bc) 。我们先看右图的例子：,10,d(be)=dc=d (db)(de) =ae=e de 即 d(be) (db)(de) 证明： aab aac a (ab)(ac) bcb ab bcc ac bc (ab)(ac) 于是有 a(bc) (ab)(ac) 类似可证(ab)(ac) a(bc) 。,*9. ab ab=b ab=a证明：教材 P239 已证 ab ab=a 这里从略。下面证明 ab ab=b 先证ab ab=b 设 ab，又bb ab b 又 bab 由反对称得 ab=b 再证 ab=b ab 已知 ab=b a ab ab。 最后得 ab ab=b 这是个很重要的定理，在以后用到此结论证明ab 。,11,四.格的同态与同构,1.定义：设 和是两个格，由它们诱导的代数系统分别是和 ，如果存在映射f:A1A2 使得对任何a,bA1, f(a1b)=f(a)2f(b) f(a1b)=f(a)2f(b)则称f是到 的同态映射。也称是 的同态像。如果 f 是双射的，就称f是到 ，的格同构，也称格 和同构。,12,例如, A=1,2,3,6, 是A上整除关系。 , E=a,b它们诱导的代数系统分别是和。其中和分别是求两个数的最小公倍数和最大公约数.,13,f(23)=f(6)=a,b f(2)f(3)=ab=a,b f(23)=f(1)= f(2)f(3)=ab= f(26)=f(6)=a,b f(2)f(6)=aa,b=a,b f(26)=f(2)=a f(2)f(6)=aa,b=a可见它们同构。格同构，它们的图的形状一定相同。,2. 格同态的保序性定理：设f是格 到 的同态映射，则对任何a,bA1,如果a1b, 则 f(a)2f(b).证明：令和 是格 和 诱导的代数系统，任取a,bA1,设a1b, 则 a1b=a f(a1b)=f(a) 而f(a1b)= f(a)2f(b)，所以 f(a)2f(b)=f(a) ， 所以 f(a)2f(b).3. 格同构的保序性定理：设双射f是格 到 的同构映射， 当且仅当 对任何a,bA1, 若 a1b f (a)2f(b).证明：令和 是格 和 诱导的代数系统，,14,1).充分性：已知，任取a,bA1, 若a1b f (a)2f(b). ( 应证出 f(a1b)=f(a)2f(b) f(a1b)=f(a)2f(b) )a) 先证 f(a1b)=f(a)2f(b) 令a1b=c c1a , c1b , 由已知得 f(c)2f(a) 和f(c)2f(b). 所以 f(c)2f(a)2f(b)- 再证 f(a)2f(b)2 f(c) ： 由于f(a),f(b)A2 , 又2的封闭性得 f(a)2f(b)A2 , 又由f:A1A2是满射，必有dA1, 使得 f(d)=f(a)2f(b)所以 f(d)2f(a) , f(d)2f(b) .由已知条件得： d1a, d1b d1a1b=c , d1c ,于是得 f(d)2f(c) , 即f(a)2f(b)2 f(c) -由得 f(c)=f(a)2f(b)即 f(a1b)=f(a)2f(b) 。b)类似可证 f(a1b)=f(a)2f(b) 所以 f是它们的同构映射.,15,2).必要性：已知 f是格 到 的同构映射， （证出：任取a,bA1, 若a1b f (a)2f(b) ）a) 先证 a1b f (a)2f(b) 任取a,bA1,设a1b ，由格同态保序性得 f(a)2 f(b) b)再证f (a)2f(b) a1b 设 f (a)2f(b)， f(a)=f(a)2f(b)=f(a1b)f 是入射， a=a1b 所以 a1b 由a),b)最后得 a1b f (a)2f(b) 。定理证毕。 由格的同构得如下结论： 具有一、二、三个元素的格分别同构于含有一、二、三个元素的链。,16,具有四个元素的格分别同构于下面两种格形式之一：,17,具有五个元素的格分别同构于下面五种格形式之一：,作业 P242 (1) (2) (4) (7),2 几个特殊格,一. 分配格 前面我们介绍一般的格，和只满足分配不等式。 a(bc) (ab)(ac) ， (ab)(ac) a(bc) 。 下面介绍的是满足分配律的格-分配格。1. 定义： 是由格诱导的代数系统。如果对a,b,cA，有 a(bc) =(ab)(ac) ， a(bc)= (ab)(ac)则称是分配格。 例 是分配格。,18,2. 二个重要的五元素非分配格： 2(35)=230=2(23)(25)=11=1 c(bd)=ca=c(cb)(cd)=ed=d可见它们都不是分配格。3.分配格的判定：见书 P245 一个格是分配格的充分且必要条件是在该格中没有任何子格与上述两个五元素非分配格之一同构。 用此方法可以判定下面两个格不是分配格：,19,4. 分配格的性质1). 定理 2.1. 在格中，如果对可分配，则对也可分配。反之亦然。证明：设是由格诱导的代数系统。且对可分配。任取a,b,cA， a(bc)= (ab)(ac)而 (ab)(ac) = (ab)a)(ab)c) (分配)=a(ab)c)=a(ac)(bc) (吸收、分配) = (a(ac)(bc) (结合)= a(bc) (吸收) 同理可证: 如果对可分配，则对也可分配.2). 定理 2.2. 所有链均为分配格。证明：显然任何链都不会含有与五元素非分配格之一同构的子格，所以链必是分配格。,20,3). 定理 2.3 . 设是分配格，对任何a,b,cA, 如果有 ab=ac 及 ab=ac 则必有 b=c .证明：任取a,b,cA, 设有 ab=ac 及 ab=ac b=b(ab) (吸收律) =b(ac) (代换) =(ba)(bc) (分配) =(ab)(bc) (交换) =(ac)(bc) (代换) = (ab)c (分配) = (ac)c (代换) =c (吸收律),21,二. 有界格,1. 格的全上界与全下界1).全上界:设是格，如果存在元素aA对任何xA, xa, 则称 a是格的全上界,记作1。(即是A的最大元)定理 2.4 一个格如果有全上界，则是唯一的。 (我们已证明过，如果有最大元，则是唯一的)2).全下界:设是格，如果存在元素aA对任何xA, ax, 则称 a是格的全下界,记作0。(即是A的最小元)定理 2.5 一个格如果有全下界，则是唯一的。从格的图形看：全上界1，就是图的最上边元素(只一个).全下界0，就是图的最下边元素(只一个)。,22,2. 有界格定义：如果一个格存在全上界1与全下界0，则称此格为有界格。 设是有界格，则对任何aA, 有 因为a1, a1=a a1=1 0a a0=0 a0=a由此看出：对于 来说 1是么元，0是零元。 对于 来说 0是么元，1是零元。 思考题： 是否所有格都是有界格？ 所有有限个元素的格都是有界格。 而无限个元素的格可能是无界格。 例如就是既无全上界也无全下界。,23,三. 有补格,回顾：集合的补集， 若 AB=E AB= 则 A=B，B=A 如E=a,b E= =E a=b, b=a1. 元素的补元： 设是个有界格，aA, 如果存在 bA, 使得 ab=1 ab=0 则称a与b互为补元。 例：右边的格中 a的补元：c, e b的补元： 无 c的补元：a,d d的补元：c e的补元：a 0 的补元：1 1的补元：0,24,2. 有补格的定义： 一个有界格中，如果每个元素都有补元，则称之为有补格。 下述有界格中，哪些是有补格？,25,上述有补格中，有些元素的补元不唯一，如(2)中的b, 那么什么样的有补格元素的补元唯一呢？ 就是有界分配格. 请看下面定理：,定理 2.6 在有界分配格中，如果元素有补元，则补元是唯一的。证明：设是有界分配格，任取aA, 假设a有两个补元b和c，则 ab=0 ab=1 ac=0 ac=1于是有， ab= ac ab=ac由分配格的定理 2.3得 b=c a的补元是唯一的。四. 布尔格 如果一个格既是分配格又是有补格，则称之为布尔格。,26,布尔格中每个元素都有唯一补元，元素a的补元记作 。,显然是布尔格。 下面介绍由布尔格诱导的代数系统布尔代数。作业 P248 (2) (5) P252 (1) (3) (6),3 布尔代数 Boolean Algebra,一. 定义 由布尔格诱导的代数系统称之 为布尔代数。其中 是“取补元”运算。 如果B是有限集合，则称它是有限布尔代数。例如：令BF,T，表示合取，表示析取， 表示否定, 就是个布尔代数。如上图所示。,27, 也是个布尔代数。如右图所示。,二. 布尔代数的性质,设布尔代数, 任意x,y,zB, 有交换律 xy=yx xy=yx结合律 x(yz)=(xy)z x(yz)=(xy)z 幂等律 xx=x xx=x 吸收律 x(xy)=x x(xy)=x分配律 x(yz)=(xy)(xz) x(yz)=(xy)(xz)同一律 x0=x x1=x 零律 x1=1 x0=0,28,互补律 x =1 x =0,对合律,底摩根定律,上述性质都可以由格，分配格,有界格，布尔格得到。下面只证明底摩根定律。,29,所以,，类似可证另一个。,三. 布尔代数的同构1. 定义：令和 是两个布尔代数，如果存在双射f:B1B2 ,对任何a,bB1 , 有 f(a1b)=f(a)2f(b) f(a1b)=f(a)2f(b),30,则称f是到 的同构映射。 与格同构比较，多了一个关于补运算的同构关系等式。 为了引出有限布尔代数的元素个数的定理，下面介绍原子的概念。,2. 原子 定义1: 设是布尔代数, 元素aB, a0, 对任何元素xB, 有xa=a, 或 xa=0, 则称a是原子。 定义2:是布尔格,在的哈斯图中称盖住全下界0的元素为原子。 例如：,31,原子的判定：定理 3.1设是布尔代数，aB,且a0,则a是原子的充分且必要条件是 对任何yB，如果ya, 则y=0或y=a。证明:必要性.设a 是原子, 且对任何yB，有ya (证出y=0或y=a), 由原子定义得 ya=a, 或 ya=0, 而由ya 得 ya=y, 所以有y=0或y=a.充分性. 已知对任何yB，如果ya, 则y=0或y=a。(证出a是原子, 即证出对任何xB 有xa=a, 或 xa=0,), 任取xB, 令y=xa , 因xaa, 所以ya , 由已知条件得 y=0 或 y=a , 即有 xa=a, 或 xa=0, 所以a是原子.,32,定理 3.2 设a,b是布尔代数中的原子，如果ab, 则ab=0, (如果ab0, 则 a=b) 证明:设a和b是B中原子, (由原子定义得: 对任何xB 有xa=a, 或 xa=0,) 因为a是原子，而bB，所以 ba=ab=a，或者 ba=ab=0, 于是: 如果ab0，必有 ab=a 。类似地， b是原子, 而aB, 所以ab=b, 或 ab=0, 此结论等价于: 如果ab0,必有 ab=b, 最后得 a=b. 所以得出, 如果ab0, 则 a=b. 或者得出，如果 ab, 则ab=0 .,33,定理 3.3 设a,b1,b2 bn是 布尔代数中的原子，则ab1b2bn的充分且必要条件为 对于某个i(1in), 有a=bi.证明:充分性显然成立, 因为对于某个i(1in)，有a=bi ,必有 ab1b2bn必要性, 已知 ab1b2bn ,则 a(b1b2bn)=a (a b1 )(a b2) (a bn)=a 如果每个(a bi)=0 (1in) 则 (a b1 )(a b2) (a bn)=0 于是得a=0,这与a是原子矛盾。所以至少有某个i (1in), 使得(a bi)0 ，因为a和 bi都是原子, 由定理 7.2 得 a=bi .,34,定理 3.4 设b是有限布尔代数中的 非0元素,则必存在原子a，使得ab.证明: 1).如果b是原子, 则 令b=a , 则 ab.2).如果b不是原子, 则必存在 b1B 使得0 b1b, 如果b1不是原子, 则必存在 b2B 使得 0b2 b1b,如此下去, 由于B是有限集合, 上述过程经过有限步后而最终结束, 最后得到原子bk ,使得 0bk b2 b1b 令 bk=a, 于是ab.例如，右图中每个非0元素x，都存在原子a，使得ax.,35,36,定理 3.5 有限布尔代数中，b =0，当且仅当 bc。,例如 右图中,2 =1(全下界0) 26,又 于是,因为0是全下界, 所以 b =0,必要性. 已知 b =0 (证出bc, 即bc=c),bc=(bc)1=(bc)( c )=(b )c,证明: 充分性.已知 bc,=0c=c,所以bc=c, 即bc,定理 3.6 设是有限布尔代数，b非0元素，a1,a2 ak是B中满足ajb的所有原子(j=1,2,k), 则 ba1a2 ak且除原子次序不同外，上述表达式是唯一的。,37,b).证bc. (由定理 4.5可知, 只要证出 b =0 即可),假设b 0 , 由定理 3.4得, 必存在原子a, 使得,a b , 而b b b 由的传递性得,ab, a . 因为a是原子, 且ab, b0, 由题意得a必是,a1,a2 , ak中之一, 由定理 3.3得aa1a2ak 即,ac；又a , 得 ac 所以a0 与a是原子矛盾.,所以必有b =0 所以 bc。 最后得 b=c,证明:(1)令a1a2ak c (证出b=c 即证 bc且cb) a).证cb 显然成立, 因为每个aib, (j=1,2,k) 所以 a1a2akb 即 cb .,即得 ba1a2 ak .(2)证明上式是唯一的.假设还有原子b1,b2 , bmB,使得 bb1b2 bm . (下面证b1,b2,bm=a1,a2,.,ak)a). 任取bib1,b2,bm , 由式得b1,b2,bm中每个bj有bjb (1jm) ,所以bib，又 ba1a2 ak所以 bi a1a2 ak ,由于bi及每个aj (1jk)都是原子, 由定理 3.3得, a1,a2,.,ak 中必存在一个aj ,使得bi =aj 于是bia1,a2,ak 所以b1,b2,bm a1,a2,.,akb).类似可以证明 a1,a2,.,ak b1,b2,bm最后得 b1,b2,bm=a1,a2,.,ak所以上述表达式在不考虑原子次序时, 形式是唯一的.,38,定理 3.7 在布尔代数中，对B中任何原子a,39,和任何非0元素b, ab和a 两式中有且仅有一个成立。,证明:假设上述两个式子都成立, 即ab和a , 则有,ab =0 , 这与 a是原子矛盾.,下面证明两个式中必有一个成立. 因为aba , 而a是原子, 所以只能有ab=a 或 ab=0,如果ab=0 , 即 , 由定理 3.5得, a ,如果ab=a , 则 ab. 于是这两个式中必有一个成立.,定理 3.8 (Stone钻石定理)设是有限布尔代数,M是B中所有原子构成的集合，则与同构。证明:构造映射 f: BP(M) 对于xB,40,先通过下边例子了解映射 f的形式:,1).先证明f是双射. a).证明f是入射: 只有x=0时, 才有 f(0)=. 任取x1, x2B, x10 x20且x1x2 , 由定理3-7.6得, x1, x2可以写成如下形式: x1= a1a2ak 其中原子ai x1 (1 i k) x2= b1b2bm 其中原子bj x2 (1j m)因为每个非0元素写成上述表达式的形式是唯一的, 又因为x1x2 , 所以 a1,a2,.,akb1,b2,bm. 由f 定义得f(x1)=a1,a2,.,ak f(x2)=b1,b2,bm 故f(x1)f(x2) f入射. b). 证明f 满射: 任取M1P(M)如果M1为, 则f(0)= M1 ,如果M1, 令M1=a1,a2,.,ak , 由的封闭性得, 必存在xB , 使得a1a2ak =x, 显然每个aix (1ik) ,故f(x)= M1, 所以f 是满射的. 最后由a)b)得 f是双射的.,41,2).证明f满足三个同构关系式. 任取x1, x2B, 因为f是双射, 必有M1, M2P(M),使得 f(x1)=M1, f(x2)=M2,a). 证明f(x1x2 )=f(x1)f(x2)=M1M2, 令f(x1x2 )=M3 , 即证明 M3 = M1M2 先证 M3 M1M2 如果 M3 = 显然有 M3 M1M2 如果M3, 任取aM3, 即 af(x1x2 )由f 定义得ax1x2 ,又因为x1x2x1, x1x2x2 , 所以 ax1 ax2 由f 定义得af(x1) af(x2) 即 aM1 aM2 ,故 aM1M2, 所以 M3 M1M2,42,再证 M1M2 M3 如果 M1M2= 显然有 M1M2 M3 如果 M1M2, 任取aM1M2 aM1 aM2即 af(x1), af(x2)，于是 a是满足ax1与ax2的原子, 所以 ax1x2 ，由f 定义得, af(x1x2), 即 aM3 故 M1M2 M3 。所以 M3 = M1M2 即 f(x1 x2 )=f(x1)f(x2),43,b).证明 f(x1 x2 )=f(x1)f(x2)=M1M2, 令f(x1x2 )=M4 , 即证明 M4 = M1M2先证 M4 M1M2 如果 M4 = 显然有 M4 M1M2 如果M4, 任取aM4, af(x1x2 )由f 定义得ax1x2 ,则必有 ax1, 或者 ax2 , (因为如果ax1与ax2都不成立, 由定理 3.7得 必有,44,与a是原子矛盾, 所以有 ax1 或 a x2)由f 定义得 af(x1) 即aM1 或af(x2) 即 aM2于是有 aM1 M2, 所以 M4 M1M2,再证 M1M2 M4 如果 M1M2 = 显然有 M1M2 M4 如果 M1M2, 任取aM1M2 aM1 或者 aM2如果aM1 则 ax1 ax1x1x2 af(x1x2), aM4 如果aM2 则 ax2 ax2x1x2 af(x1x2), aM4所以M1M2 M4 最后得 M4 = M1M2即 f(x1 x2 )=f(x1)f(x2),45,46,3).证明,于是有 x1x2=1 x1x2=0 f(x1x2)=M f(x1x2)= f(x1x2)=f(x1)f(x2)= M1M2 =M f(x1x2)=f(x1)f(x2)= M1M2 =,所以 M2 =M1 即,综上所述 由1).2).3)得 f(x1x2 )=f(x1)f(x2) f(x1x2)=f(x1)f(x2),所以 与同构。,推论1. 任何有限布尔代数的元素个数为2n (n=1,2,3,) 因为|P(M)|= 2n 其中|M|=n推论2. 两个有限布尔代数同构的充分且必要条件是元素个数相同。,47,48,本节重点掌握布尔代数的性质，同构概念，Stone定理及其推论。 作业 P260 （2）,4.布尔表达式,此内容在开关理论，逻辑设计中有着广泛的应用。一. 布尔表达式概念1.定义：设是布尔代数，其上的布尔表达式递归定义如下：1)B中任何元素是个布尔表达式。2)任何变元x是个布尔表达式.,49,是布尔表达式。4)有限次地应用规则1)-3),得到的符号串都是布尔表达式.,*表达式的最外层括号可以省略.,2.对布尔表达式赋值：设是布尔代数，含有变元 x1,x2 xn 的布尔表达式记作E(x1,x2,xn), 对变元 x1,x2,xn分别用B中元素代替的过程，称之为对布尔表达式赋值。例如 B=0,1,a,b,50,一个的布尔表达式E(x1,x2,xn), 经过赋值以后，就得到一个值(即是B中一个元素)。3.两个布尔表达式相等:设是布尔代数，含有变元 x1,x2,xn 的两个布尔表达式E1(x1,x2,xn)和E2(x1,x2, xn),如果不论对变元x1,x2 xn分别用B中任何元素赋值,都使得E1和E2的值相同,则称这两个表达式相等,记作 E1(x1,x2,xn)=E2(x1,x2,xn),我们可以通过布尔代数的性质(10个)得到很多等式.,51,如 E1(x,y)=x(y ) E2(x,y)= xy E1(x,y)=x(y )= (xy)(x )=(xy)1 = xy = E2(x,y),二. 布尔函数设是布尔代数，含有变元 x1,x2,xn 的布尔表达式记作E(x1,x2,xn),也可以看成是一个函数E:BnB,称之为布尔函数. 布尔函数有两种表示方法: 1. 代数法: 例如 B=0,1 是布尔代数，,即是表达式表示法. 2. 真值表法: 见下面:,的真值表如下:,52,三. 布尔表达式的范式 1. 有两个元素的布尔代数的布尔表达式的范式: 是两个元素的布尔代数 1). 析取范式(相当于命题公式的主析取范式),53,(1).小项: 含有n个变元的小项形式为:,其中,例如,都是小项.,(2).布尔表达式的析取范式: 含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),如果写成如下形式: A1A2.Am (m1) , 其中每个Ai (1im)都是有n个变元的小项. 则称此式是E(x1,x2,xn)的析取范式. 例如:,2). 合取范式(相当于命题公式的主合取范式) (1). 大项:含有n个变元的大项形式为:,54,其中,例如,都是大项.,(2).布尔表达式的合取范式:含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),如果写成如下形式: A1A2. Am (m1)其中每个Ai (1im)都是有n个变元的大项. 则称此式是E(x1,x2,xn)的合取范式. 例如:,3). 析取范式与合取范式的写法: 方法1:列真值表 方法2:表达式的等价变换.,55,方法1. 用真值表求析取范式: 先介绍小项的性质, 以两个变元x1,x2为例,每一组赋值有且仅有一个小项为1.根据一组赋值,求值为1的小项: 如果变元x,被赋值为0,则,在此小项中, x以 形式出现; 如果变元x,被赋值为1,则在,此小项中, x以原形x形式出现. 求E(x1,x2,xn)的析取范式:先列出它的真值表,找出表中每个1对应的小项,然后用连接上述小项.,例如,求布尔代数上的布尔表达式,56,方法1. 用真值表求合取范式: 先介绍大项的性质, 以两个变元x1,x2为例,57,每一组赋值有且仅有一个大项为0.根据一组赋值,求值为0的大项: 如果变元x被赋值为1, 则,在此大项中, x以 形式出现; 如果变元x被赋值为0, 则在,此大项中, x以原形x形式出现. 求E(x1,x2,xn)的合取范式:先列出它的真值表,找出表中每个0对应的大项,然后用连接上述大项.,例如,求布尔代数上的布尔表达式,58,方法2. 用表达式的等价变换求析取范式:,59,结果与前相同.用表达式的等价变换求合取范式:,4). 应用：在楼梯处安装一个电灯，在楼下(楼上)有开关X(Y) ，都可以控制此灯，使得有人上搂(或下搂) 按动开关X(Y) 灯就亮，上楼(或下楼) 完毕按动Y(X)开关后灯就灭。请设计控制此灯的电路。解：令L为灯，X和Y为开关，这是双,60,开关逻辑、定义为： XY XY,开关的控制过程如下:,61,2. 一般的布尔代数的布尔表达式的范式: 是布尔代数,含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn), 1). 小项: 是由n个变元和B中元素构成的如下形式,称为小项.,62,其中,C12.n为B中元素, 我们称之为小项的系数. 例如 B=0,1,a,b, 下面就是E(x1,x2,x3)中的小项:,2). 布尔表达式E(x1,x2,.xn)的析取范式: 含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),如果写成如下形式: A1A2.Am (m1)其中每个Ai (1im)都是有n个变元的小项. 则称此式是E(x1,x2,xn)的析取范式.,定理 4.1. 设是布尔代数,含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn), 则可以写成析取范式形式.证明:令E(xi=a) =E(x1,x2,.,xi-1,a,xi+1,xn) 先通过对|E|归纳证明如下结论成立:,63,先用下面例子理解上边式子的含义。 并验证结论成立.,这里|E|为E(x1,x2,xn)的长度, 即其中所含有的B中元素个数、 运算符号个数、变元个数的总和(含重复计数).例如,类似根据指 派求小项,(1). 如果|E|=1 则 E=a (aB) ,或者 E=xj, (xj是个变量) 如果E=a 则E(xi=0)=E(xi=1)=a,64,所以|E|=1时, 结论成立.,如果E= xj, 若 xj=xi ,显然 E(xi=0)=0，E(xi=1)=1 ，,若 xj xi, 则 E(xi=0)=E(xi=1)= xj ,(2).假设|E|n 时, 结论成立. 即,65,(3).当|E|=n+1时, 分下面三种情况讨论: 如果E=E1E2 则|E1|n, |E2|n , 由(2)假设得,如果E=E1E2 则|E1|n, |E2|n , 由(2)假设得,66,如果,67,定理得证. 通过反复应用此定理, 就可以将E(x1,x2,xn)写析取范式形式.,68,69,其中E(0,0,0), E(0,0,0,1) , E(1,1,1,0) 和 E(1,1,1)就是所谓的“系数”. 实际上, 求E(x1,x2,xn)的析取或者合取范式时, 就是求这些“系数”. 下面看一个例子.,3) 合取范式：类似地，先用归纳法证明：,例.已知是布尔代数, 其中B=0,a,b,1分别求出下面布尔表达式的析取范式和合取范式.,70,解. 先求四个系数:,析取范式为:,合取范式为:,71,本节重点掌握内容：布尔表达式定义、析取范式和合取范式的写法。作业：P269 (1),本章内容小结：1. 格的概念、格的性质. 格的同构.2. 分配格的性质、判断. 有界格 有补格 布尔格概念性质.3. 布尔代数的性质, Stone定理的应用.4. 布尔表达式定义,范式的写法.,72,下面上第七章的习题课,73,习题课,P242 (1). 下面图哪些是格？,74,(a)不是格 因为d和e没有下确界,也没有上确界.(d)不是格5和6没有下确界,7和8既没下确界,也没上确界.进一步问,如果是格,哪些是分配格?哪些是有补格?(b)不是分配格,因去掉结点i后的子格如图所示,但它是有补格. (c)不是分配格(去m,p),不是有补格.,(2). 设是L上的整除关系,下面偏序集中,哪些是格? a) L=1,2,3,4,6,12, b) L=1,2,3,4,6,8,12,14 c) L=1,2,3,4,5,6,7,8,9,10,11,12 解. 画出Hasse图如下:,75,可见只有(a)是格.,(4).设是一个格,任取a,bA,a也是格.证明:显然B是A的非空子集, (因为aab,abb,所以a,bB), 只要证明和在B上封闭即可. 任取x,yB, 由B的构成得axb,ayb, 于是由格的性质得,axyb axyb, 于是有 xyB ,xyB , 说明和在B上封闭 . 所以也是格.,76,(7).设a,b是格中的两个元素,证明: a). ab=b 当且仅当ab=a. b). abb和aba,当且仅当 a与b是不可比较的.证明:a)充分性: 已知ab=a b=b(ba)= b(ab) =ba=ab 必要性:已知ab=b , a=a(ab)=abb)充分性:已知a与b是不可比较的. 因abb, aba, 如果ab=b, 则有ba, 如果ab=a, 则有ab,都与a与b是不可比较的矛盾. 所以有: abb abb,于是有 abb aba aba,于是有 aba 必要性:已知abb和aba, 假设a与b是可比较的.则要么ab,要么ba. 于是要么ab=a 要么ab=b. 这与abb和aba矛盾.所以a与b是不可比较的.,77,(9).证明格中成立: a) (ab)(cd)(ac)(bd) b) (ab)(bc)(ca)(ab)(bc)(ca)证明:a) (ab)a(ac) (ab)(ac) (cd)c(ac) (cd)(ac) (ab)(cd)(ac) 同理 (ab)(bd) (cd)(bd) (ab)(cd)(bd) (ab)(cd)(ac)(bd)b) (ab)(ab), (ab)(bc) ,(ab)(ca) (ab)(ab)(bc)(ca) 同理有 (bc)(ab)(bc)(ca) (ca)(ab)(bc)(ca) 最后得(ab)(bc)(ca)(ab)(bc)(ca).,78,P248(2).下面哪个是分配格?,79,解:判定一个格是否分配格,看它是否含有五元素的非分配格形式的子格.(a)图好像可以去掉b或c后得到如下图:,但它们不是(a)的子格.因de=b bc=eb,e不在子集里. (a)是分配格.,(b)也是分配格.,(c)不是分配格.,(5).设是分配格,a,bA, 且ab, 证明 f(x)=(xa)b 是一个从A到B的同态映射. 其中 B=x|xA且axb证明:先证 f 是从A到B的映射:任取xA, 由f的定义得f(x)=(xa)b) 显然 (xa)bb而 (xa)b=(xb)(ab)=(xb)a (因ab ab=a) a(xa)bb 即af(x)b f(x)B . dom f=A. 又由于和的定义知(xb)a是唯一的.即f(x)是唯一的. 所以f 是从A到B的映射.再证f 满足同态等式:任取x1,x2A, f(x1x2)=(x1x2)a)b=(x1a)(x2a)b=(x1a)b)(x2a)b) =f(x1)f(x2) f(x1x2)=(x1x2)a)b=(x1a)(x2a)b=(x1a)b)(x2a)b) =f(x1)f(x2) f 是同态映射.,80,P252(1). 给出有界格如图 a)哪些元素有补元? b)该格是分配格吗? c)该格是有补格吗?解:a) a、c、d、f、g 无补元 ; b和e互为补元 ; 0和1互为补元. b) 不是分配格, 因为它含有子格如下图.,81,c) 它不是有补格,因为很多元素无补元.(3).证明具有两个或更多个元素的格中 不存在以自身为补元的元素.,(4). 在有界分配格中,证明具有补元的那些元素组成一个子格.,82,所以是的子格.,(6).设是有界格, 对于任何x,yA, 证明 a). xy=0 , 则 x=y=0 b). xy=1, 则 x=y=1 证明: a) x=x(xy)=x0=0 y=y(yx)=y0=0 b) x=x(xy)=x1=1 y=y(yx)=y1=1P260(2).设是布尔代数，x,yS, 证明: xy 当且仅当,83,证明: 充分性 已知,必要性: 已知 xy,P269(1).设是上的一个布尔表达式.分别写出它的析取范式与合取范式.方法1.用真值表,84,方法2. 用等价变换的方法.,85,这是析取范式. 求它的合取范式可能要麻烦一些.下面求合取范式:,86,可见与用真值