《离散数学 格与布尔代数ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学 格与布尔代数ppt课件.ppt（87页珍藏版）》请在三一办公上搜索。
1、第七章 格与布尔代数,布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。是偏序集:是A上自反,反对称和传递关系(偏序).偏序集中的元素间的次序可以通过它的Hasse图反映出来.例如A=1,2,3,6,12,24,36,是A上的整除关系其Hasse图如图所示，BA B1.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的最小元:无 最大元:6B如果有最小元(最大元),则是唯一
2、的。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若有下(上)确界，则唯一),7-1 格(Lattice),一.基本概念1.格的定义 是偏序集，如果任何a,bA,使得a,b都有最大下界和最小上界，则称是格。右图的三个偏序集，不是格，因为24,36无最小上界。是格。,这三个偏序集，也都不是格，第一个与第三个是同构的。因为 d和e无下界
3、，也无最小上界；b,c虽有下界，但无最大下界。2,3无最大下界，4,5无最小上界。2.平凡格：所有全序都是格，称之为平凡格。因为全序中任何两个元素x,y，要么xy,要么yx。如果xy，则x,y的最大下界为x，最小上界为y。如果yx，则x,y的最大下界为y，最小上界为 x。即这x,y的最大下界为较小元素，最小上界为较大元素.,3.由格诱导的代数系统设是格,在A上定义二元运算和为:a,bA ab=LUB a,b a,b的最小上界.Least Upper Bound ab=GLB a,b a,b的最大下界.Greatest Lower Bound称是由格诱导的代数系统.(-并,-交)例如右边的格中a
4、b=b ab=a bc=e4.子格：设是格,是由诱导的代数系统。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 此性质由运算和的定义直接得证。
5、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 此性质由运算和的定义直接得证。4.和都满足幂等律。即 aa=a aa=a 证明：由性质1,aaa(再证aaa)又由自反有aa，这说明a是a的上界，而aa是a的最小上界，所以 aa a。最后由反对称得 aa=a。由对偶原理得 a
6、a=a,5.和都满足结合律。即(ab)c=a(bc)，(ab)c=a(bc)证明：先证明(ab)c a(bc)因 a a(bc)，bbc a(bc)所以 aba(bc)又 cbc a(bc)于是有(ab)c a(bc)再证 a(bc)(ab)c 因aab(ab)c；再由bab(ab)c，c(ab)c 所以 bc(ab)c于是有 a(bc)(ab)c最后由反对称得(ab)c=a(bc)类似可证(ab)c=a(bc)。,6.和都满足吸收律。即 a(ab)=a，a(ab)=a。证明：显然有 aa(ab)再证 a(ab)a 因 a a，ab a 所以 a(ab)a最后由反对称得 a(ab)=a，类似可
7、证 a(ab)=a。,7.和不满足分配律。但有分配不等式：a(bc)(ab)(ac)，(ab)(ac)a(bc)。我们先看右图的例子：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)。由对偶原理得 a(bc)(ab)(ac)。即(ab)(ac)a(bc)。,8.ab ab=b ab=a证明：先证明ab ab=a 先证ab ab=a 由 ab，又aa 所以aab 又由ab的定义有aba 由反对称得 ab=a 再证
8、ab=a ab 由 ab=a 则 a=ab b。综上得 ab ab=b 下面证明ab ab=b 先证ab ab=b 由 ab，又bb 所以 ab b 又因为 bab 由反对称得 ab=b 再证 ab=b ab 由 ab=b 因 a ab 所以 ab。综上得 ab ab=b,引理：是代数系统，如果和是满足吸收律的二元运算，则和必满足幂等律。证明：任取a,bA 因为 和满足吸收律。于是有 a(ab)=a-a(ab)=a-。由于上式中的b是任意的，可以令b=ab 并代入式得 a(a(ab)=a 由式得 aa=a同理可证aa=a,定理：设是代数系统，如果和是满足交换律，结合律，和吸收律的二元运算，则A
9、上存在偏序关系，使是一个格，并且该格所诱导的代数系统恰好是。（由代数系统得到格）证明：设在A上定义二元关系 为：对任意a,bA,a b 当且仅当 ab=a（1）先证二元关系 是一个偏序关系（2）再证ab 是 a,b 的下确界（3）然后证a b是 a,b 的上确界见书上238页,四.格的同态与同构,1.定义：设 和是两个格，由它们诱导的代数系统分别是和，如果存在映射 f:A1A2，使得对任何a,bA1，有 f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)则称f是到 的同态映射。也称是 的同态像。如果 f 是双射的，就称f是到，的格同构，也称格 和同构。,例：，A=1,2,3,6,
10、是A上整除关系。，E=a,b它们诱导的代数系统分别是和其中和分别是求两个数的最小公倍数和最大公约数.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 可见它们同构。格同构，它们的哈斯图的形状一定相同。,具有1、2、3个元素的格分别同构于含有一、二、三 个元素的链。具有4个元素的格分别同构于下面两种格形式之一：具有5个素的格分别同构于下面五种格形式之一：,2.格同态的保序性定理：设f是格 到 的同态映射，则对任何a,
11、bA1，如果a1b，则 f(a)2f(b)。证明：令和 是格 和 诱导的代数系统，任取a,bA1，设a1b，则 a1b=a f(a1b)=f(a)即 f(a)2f(b)=f(a)而 f(a)2f(b)2f(b)所以 f(a)2f(b).3.格同构的保序性定理：设两个格为和，f是A1到A2的双射，则f是 到的格同构，当且仅当 对任意a,bA1，a1b f(a)2f(b)证明：令和 是格 和 诱导的代数系统，,1)必要性：已知 f是格 到 的同构映射，（往证：任取a,bA1,a1b f(a)2f(b)）a)先证 a1b f(a)2f(b)任取a,bA1,设a1b，由格同态保序性得 f(a)2 f(
12、b)b)再证f(a)2f(b)a1b 设 f(a)2f(b)，于是有 f(a)=f(a)2f(b)=f(a1b)因f 是双射，所以 a=a1b 所以 a1b 最后得 a1b f(a)2f(b)。,2)充分性：已知，对任意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,又由
13、f:A1A2是双射，必有dA1,使得 f(a)2f(b)=f(d)所以 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(a)2f(b)=f(c)，即 f(a1b)=f(a)2f(b)。b)类似可证 f(a1b)=f(a)2f(b)，所以 f是它们的同构映射。,7-2 几个特殊格,一.分配格 前面我们介绍一般的格，和只满足分配不等式。a(bc)(ab)(ac)，(ab)(ac)a(bc)。下面介绍的是满足分配律的格-分配格。1.定义：是由格诱导的代数系统。如果对a,b,cA，有
14、a(bc)=(ab)(ac)，a(bc)=(ab)(ac)则称是分配格。例：所诱导的代数系统为 所以是分配格。,2.二个重要的五元素非分配格：2(35)=230=2(23)(25)=11=1 c(bd)=ca=c(cb)(cd)=ed=d可见它们都不是分配格。3.分配格的判定：一个格是分配格的充分且必要条件是在该格中没有任何子格与上述两个五元素非分配格之一同构。用此方法可以判定下面两个格不是分配格：,4.分配格的性质1.在一个格中，如果对可分配，则对也可分配。反之亦然。证明：设是由格诱导的代数系统，且对可分配。则任取 a,b,cA，(ab)(ac)=(ab)a)(ab)c)分配=a(ab)c)
15、=a(ac)(bc)吸收、分配=(a(ac)(bc)结合=a(bc)即对也可分配 同理可证:如果对可分配，则对也可分配.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(吸收律),二.有界格,1.格的全上界与全下界1).全上界:设
16、是格，如果存在元素aA对任何xA,xa，则称 a是格的全上界，记作1。(即是A的最大元)定理7-2.4 一个格如果有全上界，则是唯一的。(我们已证明过，最大元如果有，则是唯一的)2).全下界:设是格，如果存在元素aA对任何xA,ax,则称 a是格的全下界,记作0。(即是A的最小元)定理7-2.5 一个格如果有全下界，则是唯一的。从格的图形看：全上界1，就是图的最上边元素(只一个)，全下界0，就是图的最下边元素(只一个)。,2.有界格定义：如果一个格存在全上界1与全下界0，则称此格为有界格。设是有界格，则对任何aA,有 因为a1,所以 a1=a a1=1 0a 所以 a0=0 a0=a 是否所有
17、格都是有界格？所有有限个元素的格都是有界格，而无限个元素的格可能是无界格。例如就既无全上界也无全下界。,三.有补格,回顾：集合的补集，若 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,2.有补格的定义：一个有界格中，如果每个元素都有补元，则称之为有补格。上述有界格中，哪些是有补格？上述有补格中，有些元素的补元不唯一，如(2)中的b，那么什么样的有补
18、格元素的补元唯一呢？有界分配格。请看下面定理：,定理72.6 在有界分配格中，如果元素有补元，则补元是唯一的。证明：设是有界分配格，任取aA，假设a有两个补元b和c，则 ab=0 ab=1 ac=0 ac=1于是有 ab=ac 及 ab=ac由分配格的性质3得 b=c，所以a的补元是唯一的。四.布尔格 如果一个格既是分配格又是有补格，则称之为布尔格。布尔格中每个元素都有唯一补元，元素 a 的补元记作。显然是布尔格。下面介绍由布尔格诱导的代数系统布尔代数。,73 布尔代数 Boolean Algebra,一.定义 由布尔格诱导的代数系统称之为布尔代数。其中 是取补元运算。如果A是有限集合，则称它
19、是有限布尔代数。例如：令BF,T，表示合取，表示析取，表示否定，就是个由右面格所诱导的布尔代数。E=a,b,也是个由右面格所诱导的布尔代数。,二.布尔代数的性质,设布尔代数,任意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 互补律 x=1 x=0 对合律底摩根定律,上述性质都可以由格，分配格，有界格，布尔格得到。下面只证明底摩根定律。所以。类似可证另一个。,
20、三.布尔代数的同构1.定义：令和 是两个布尔代数，如果存在映射 f:B1B2，对任何a,bB1，有 f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)f()=则称f是到 的同态映射。与格同构比较，多了一个关于补运算的同构关系等式。为了引出有限布尔代数的stone 的定理，下面介绍原子的概念。,2.原子 定义1:设设布尔代数,元素aB,a0,对任何元素xB,有xa=a,或 xa=0,则称a是原子。定义2:是布尔格,在的哈斯图中称盖住全下界0的元素为原子。例如：,下面先介绍原子的判定定理7-3.1设是布尔代数，aB,且a0,则a是原子的充分且必要条件是 对任何yB，如果ya,则y=0
21、或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是原子.,定理7-3.2 设a,b是布尔代数中的原子，如果ab,则ab=0,(如果ab0,则 a=b)即 不同两个原子的下确界为0证明:设a和b是B中原子,(由原子定义得:对任何xB 有xa=a,或 xa=
22、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.,定理7-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)=
23、0(1in)则(a b1)(a b2)(a bn)=0 这与a是原子矛盾.所以至少有某个i(1in),使得(a bi)0 因为a和 bi都是原子,由定理7-3.2 得 a=bi.,定理7-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.,定理7-3.5 有限布尔代数中，b=0，当且仅当
24、 bc。例如右图中,2=0 26证明:充分性.已知 bc又 于是因为0是全下界,所以 b=0必要性.已知b=0(往证 bc,即bc=c)bc=(bc)1=(bc)(c)=(b)c=0c=c所以bc=c,即bc,定理7-3.6 设是有限布尔代数，b非0元素，a1,a2 ak是B中满足ajb的所有原子(j=1,2,k),则 ba1a2 ak且除原子次序不同外，上述表达式是唯一的。证明:(1)令a1a2ak c(往证b=c 即证 bc且cb)a).证cb 显然成立,因为每个aib,(j=1,2,k)所以 a1a2akb 即 cb.b).证bc.(由定理7-3.5可知,只要证出 b=0 即可)假设b
25、0,由定理7-3.4得,必存在原子a,使得a b,而b b b 由的传递性得ab,a.因为a是原子,且ab,b0,由题意 a必是a1,a2,ak中之一,于是 aa1a2ak 即 ac,又a,得 ac 所以a0，这与a是原子矛盾.所以只有b=0，所以bc。综上 b=c,即得 ba1a2 ak.(2)证明上式是唯一的.假设还有原子b1,b2,bmB,使得 bb1b2 bm.(下面证b1,b2,bm=a1,a2,.,ak)a).任取bib1,b2,bm,由式得b1,b2,bm中每个bjb(1jm),又 ba1a2 ak 所以 bib 即 bi a1a2 ak,由于bi及每个aj(1jk)都是原子,由
26、定理7-3.3得,a1,a2,.,ak 中必存在一个aj,使得bi=aj 于是bia1,a2,ak 所以b1,b2,bm a1,a2,.,ak类似可以证明 a1,a2,.,ak b1,b2,bm最后得 b1,b2,bm=a1,a2,.,ak所以上述表达式在不考虑原子次序时,形式是唯一的.,定理7-3.7 在布尔代数中，对B中任何原子a和任何非0元素b,ab和a 两式中有且仅有一个成立。证明:假设上述两个式子都成立,即ab和a,则有ab=0,这与 a是原子矛盾.下面证明两个式中必有一个成立.因为aba,而a是原子,所以只能有ab=a 或 ab=0如果ab=0,即,由定理7-3.5得,a,如果ab
27、=a,则 ab.于是这两个式中必有一个成立.,定理7-3.8(Stone定理)设是有限布尔代数，M是B中所有原子构成的集合，则与同构。证明:构造映射 f:BP(M)对于xB 先通过下边例子了解映射 f的形式:,1).先证明f是双射.a).证明f是入射:只有x=0时,才有 f(x)=.任取x1,x2B,x10 x10且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
28、)=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是双射的.,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 如果 M
29、3=显然有 M3 M1M2 如果M3,任取aM3,由f 定义得ax1x2,又因为x1x2x1,x1x2x2,所以 ax1 ax2 由f 定义得af(x1)af(x2)即 aM1 aM2,故 aM1M2,所以 M3 M1M2,再证 M1M2 M3 如果 M1M2=显然有 M1M2 M3 如果 M1M2,任取aM1M2 aM1 aM2所以 a是满足ax1与ax2的原子,ax1x2 由f 定义得,af(x1x2),即 aM3 所以 M1M2 M3 所以 M3=M1M2 即 f(x1 x2)=f(x1)f(x2),b).证明 f(x1 x2)=f(x1)f(x2)=M1M2,令f(x1x2)=M4,即
30、证明 M4=M1M2先证 M4 M1M2 如果 M4=显然有 M4 M1M2 如果M4,任取aM4,由f 定义得ax1x2,则必有ax1,或者 ax2,(因为如果ax1与ax2都不成立,由定理7-3.7得 必有 与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所
31、以M1M2 M4 M4=M1M2与ax2的原子,由f 定义得,即 所以 M1M2 M4 所以 M4=M1M2 即 f(x1 x2)=f(x1)f(x2),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推论2.两个有限布尔代数同构的充分且必要条件是其元
32、素个数相同。,本节重点掌握布尔代数的性质，同构概念，Stone定理及其推论。作业 P260（2）,7-4.布尔表达式,一.布尔表达式概念1.定义：设是布尔代数，其上的布尔表达式递归定义如下：1)B中任何元素是个布尔表达式。2)任何变元x是个布尔表达式。3)如果E1,E2是个布尔表达式,则,(E1E2),(E1E2)也是布尔表达式。4)有限次地应用规则1)2)3)得到的符号串都是布尔表达式。例如令B=0,1,a,b(a),(xy),*表达式的最外层括号可以省略.,2.对布尔表达式赋值：设是布尔代数，含有变元 x1,x2 xn 的布尔表达式记作E(x1,x2,xn),对变元 x1,x2,xn分别用
33、B中元素代替的过程，称之为对布尔表达式赋值。例如 B=0,1,a,b E(x1,x2)=E(a,b)=b一个的布尔表达式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个)得到很多等式.如,E1(x,y)=x(y)E2(x,y)=xy E1(x,y)=
34、x(y)=(xy)(x)=(xy)1=xy=E2(x,y)二.布尔函数设是一个布尔代数，一个从BnB的函数被称为n元布尔函数。含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),可以看成是一个 BnB 的布尔函数.布尔函数有两种表示方法:1.表达式方法:例如B=0,1 是布尔代数，即是表达式表示法.2.函数表法:见下面:,例：B=0,1,2,3，是布尔代数 在其上定义的一个布尔函数f(x,y)的函数表如右图所示:,三.布尔表达式的范式 1.两元素布尔代数的布尔表达式的范式:是两个元素的布尔代数 1).析取范式(1).小项:含有n个变元的小项形式为:其中 例如 都是小项.(2).布尔
35、表达式的析取范式:含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),如果写成如下形式:A1A2.Am(m1)其中每个Ai(1im)都是有n个变元的小项.则称此式是E(x1,x2,xn)的析取范式.例如:,2).合取范式(1).大项:含有n个变元的大项形式为:其中例如 都是大项.(2).布尔表达式的合取范式:含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),如果写成如下形式:A1A2.Am(m1)其中每个Ai(1im)都是有n个变元的大项.则称此式是E(x1,x2,xn)的合取范式.例如:3).析取范式与合取范式的写法:方法1:列真值表 方法2:表达式的等价变换.,方
36、法1.用真值表求析取范式:先介绍小项的性质,以两个变元x1,x2为例 每一组赋值,有且仅有一个小项为1.根据一组赋值,求值为1的小项:如果变元x,被赋值为0,则在此小项中,x以 形式出现;如果变元x,被赋值为1,则在此小项中,x以原形x形式出现.求E(x1,x2,xn)的析取范式:先列出它的真值表,找出表中每个1对应的小项,然后用连接上述小项.,例如,求布尔代数上的布尔表达式 E(x1,x2,x3)=x1(x2)的析取范式.E(x1,x2,x3)=(x1)(x1 x2)(x1 x2x3),方法1.用真值表求合取范式:先介绍大项的性质,以两个变元x1,x2为例 每一组赋值,有且仅有一个大项为0.
37、根据一组赋值,求值为0的大项:如果变元x,被赋值为1,则在此小项中,x以 形式出现;如果变元x,被赋值为0,则在此小项中,x以原形x形式出现.求E(x1,x2,xn)的合取范式:先列出它的真值表,找出表中每个0对应的大项,然后用连接上述大项.,例如,求布尔代数上的布尔表达式 E(x1,x2,x3)=x1(x2)的合取范式.E(x1,x2,x3)=(x1x2x3)(x1x2)(x1 x3)(x1)(x2),方法2.用表达式的等价变换求析取范式:E(x1,x2,x3)=x1(x2)=(x1x2)(x1)=(x1x2(x3)(x1(x2)=(x1x2x3)(x1x2)(x1x2)(x1)=(x1x2
38、x3)(x1x2)(x1)结果与前相同.用表达式的等价变换求合取范式:E(x1,x2,x3)=x1(x2)=(x1(x2)(x3)(x1)x2)=(x1x2x3)(x1x2)(x1 x3)(x1)(x1x2)(x2)=(x1x2 x3)(x1x2)(x1 x3)(x1)(x2),*2.一般布尔代数的布尔表达式的范式:是布尔代数,含有变元 x1,x2,xn 的布尔表达式E(x1,x2,xn),1).小项:是由n个变元和B中元素构成的如下形式,，称为小项.其中 C12.n为B中元素,称之为小项的系数.例如B=0,1,a,b,下面就是E(x1,x2,x3)中的小项:,2).布尔表达式E(x1,x2,
39、.xn)的析取范式:E(x1,x2,xn)是含有变元 x1,x2,xn 的布尔表达式，如果等价的写成如下形式:A1A2.Am(m1)其中每个Ai(1im)都是有n个变元的小项.则称此式是E(x1,x2,xn)的析取范式.定理7-4.1.设是布尔代数,含有变元 x1,x2,xn 的布尔表达式为E(x1,x2,xn),则该布尔表达式可以写成析取范式的形式.,类似地,E(x1,x2,xn)的合取范式为:E(x1,x2,xn)=(x1x2.xn E(0,0,0)(x1x2.xn-1 E(0,0,0,1).(.xnE(1,1,1,0)(.E(1,1,1)其中E(0,0,0),E(0,0,0,1),E(1
40、,1,1,0)和E(1,1,1)就是所谓的“系数”.实际上,求E(x1,x2,xn)的析取或者合取范式时,就是求这些“系数”.下面看一个例子.,已知是布尔代数,其中B=0,a,b,1分别求出下面布尔表达式的析取范式和合取范式.解.先求四个系数:析取范式为:,合取范式为:一般的布尔函数不一定都能写成布尔表达式的形式。例：设 B=0,1,2,3,是布尔代数，在其上定义的一个布尔函数g(x,y)，其函数表如下图所示:证明其不能用一个布尔表达式将其表示。,例：B=0,1,2,3,是布尔代数,在其上定义的一个布尔函数g(x,y),其函数表如右图所示:,证明：用反证法。若g(x,y)能被布尔表达式表示，则
41、其必可写成析取范式的形式,设其为：而 g(1,1)=1,g(1,0)=1,g(0,1)=0,g(0,0)=1所以对于布尔格，其哈斯图为考查 g(3,3)=(22)(32)(33)=203=1,而在表中 g(3,3)=2，矛盾，所以该函数不能用布尔表达式表示。,本节重点掌握内容：布尔表达式定义、析取范式和合取范式的写法。本章内容小结：1.格的概念、格的性质.格的同构.2.分配格的性质、判断.有界格 有补格 布尔格概念性质.3.布尔代数的性质,Stone定理的应用.4.布尔表达式定义,范式的写法.,习 题 课 格与布尔代数,P242(1).(a)不是格，因为d和e没有下确界,也没有上确界.(d)不
42、是格，5和6没有下确界,7和8既没下确界,也没上确界.进一步问,如果是格,哪些是分配格?哪些是有补格?(b)不是分配格,因子集f,g,j,k,h构成的子格如图所示但它是有补格。(c)不是分配格,考察子集l,n,q,r,o构成的子格；也不是有补格。,(2).设是L上的整除关系,下面偏序集中,哪些是格?a)L=1,2,3,4,6,12,b).L=1,2,3,4,6,8,12,14c)L=1,2,3,4,5,6,7,8,9,10,11,12 可见只有(a)是格.,(4).设是一个格,任取a,bA,a也是格.证明:显然B是A的非空子集(因为aab,abb,所以a,bB),只要证明和在B上封闭即可.任取
43、x,yB,由B的构成得axb,ayb,于是由格的性质得,axyb axyb,于是有xyB xyB,说明和在B上封闭,所以也是格.,(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,
44、假设a与b是可比较的.则要么ab,要么ba.于是要么ab=a 要么ab=b.这与abb和aba矛盾.所以a与b是不可比较的.,(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
45、)(bc)(ca)(ab)(bc)(ca).,P248(2).下面哪个是分配格?解:判定一个格是否分配格,看它是否含有五元素的非分配格形式的子格.(a)图好像可以去掉b或e后得到如下图:但它们不是(a)的子格.因de=b bc=eb,e不在子集里.(a)是分配格.(b)也是分配格.(c)不是分配格.,(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
46、(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是同态映射.,P252(1).给出有界格如图a)哪些元素有补元?b)该格是分配格吗?c)该格是有补格吗?解:a)a、c、d、f、g 无补元;b和e互为补元;0和1互为补元.b)不是分配格,因为它含有子格
47、如下图.c)它不是有补格,因为很多元素无补元.(3).证明具有两个或更多个元素的格中 不存在以自身为补元的元素.证明:设是格,且|A|2,假设有aA,使得=aa0,a1,但是有 1=a=aa=a 0=a=aa=a产生矛盾.所以不存在以自身为补元的元素.,(4).在有界分配格中,证明具有补元的那些元素组成一个子格.证明:设是有界分配格,令B=x|A任取a,bB,B,A,A下面证明和在B上封闭,即ab和ab都有补元:所以是的子格.,(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 当且仅当 证明:充分性 已知必要性:已知 xy,P260(2)设是个布尔代数,x,yB,证明:xy 当且仅当.解.必要性.已知 xy,充分性:已知,P269(1).设是上的一个布尔表达式.分别写出它的析取范式与合取范式.方法1.用真值表,方法2.用等价变换的方法.这是析取范式.求它的合取范式可能要麻烦一些.下面求合取范式:,可见与用真值表求的结果相同.,格与布尔代数,到此结束,
