離散數(shù)學(xué) 格.ppt

1、7.2 格論,集合代數(shù)：（(S)，）,對(duì)A,B,C(S)，運(yùn)算，滿足： 等冪律 AA = A， AA = A， 交換律 AB = BA， AB = BA， 結(jié)合律 A（BC） = （AB）C， A（BC） = （AB）C， 分配律 A（BC） =（AB）（AC）， A（BC）=（AB）（AC）， 吸收律 A（AB）=A， A（AB）=A， De Morgan定律:,命題代數(shù)（最后一篇）（S，）,對(duì)A,B,CS，運(yùn)算，滿足： 等冪律 AA = A， AA = A， ， 交換律 AB = BA，AB = BA 結(jié)合律 A（BC）=（AB）C， A（BC） = （AB）C 分配律 A(BC)=(AB

2、)(AC)， A（BC） = （AB） （AC） 吸收律 A(AB)=A，A（AB）=A， 若引進(jìn)否定的概念，有De Morgan定律: (AB )= AB, (AB )= AB,7.2.1 格,定義(代數(shù)格):,定義： 設(shè)L是一個(gè)非空集合，+是L上兩個(gè) 二元代數(shù)運(yùn)算，如果這兩種運(yùn)算對(duì)于L中元 素滿足： （1）交換律：ab=ba，a+b=b+a。 （2）結(jié)合律：a（bc）=（ab）c， a+（b+c）=（a+b）+c。 （3）吸收律：a（a+b）=a， a +（ab）=a。 則稱(chēng)此代數(shù)系統(tǒng)（L，+）為一個(gè)代數(shù)格。,定義（偏序格） 定義： 給出一個(gè)偏序集（L，）, 如果對(duì)于任意a，bL，L的子集

3、a，b 在L中都有一個(gè)下確界(記為infa，b) 和一個(gè)上確界（記為supa，b），則 稱(chēng)（L，）為一個(gè)格。,例. S是任意一個(gè)集合，(S)是S的冪集合， 則，偏序集(S)，)是一個(gè)格，記 (S)，)。 因?yàn)閷?duì)A,B(S)， supA,B=AB(S),infA,B=AB(S) 例. 設(shè)Z+是所有正整數(shù)集合，D是Z+中的“整除關(guān)系”，對(duì)任意a，bZ+，aDb當(dāng)且僅當(dāng)a整除b，于是，（Z+，D）是一個(gè)格。 supa，b=lcm(a，b)(最小公倍數(shù))Z+， infa,b= gcd(a，b)（最大公因數(shù)）Z+ 。 注：不是所有的偏序集都是格。,定義（子格）,定義： 設(shè)（L，）是格，S L， 如果（S

4、，）是格， 則稱(chēng)（S，）是格（L，）的子格。,格的性質(zhì)：,1、格滿足冪等律: aa=a，a+a=a；Th7.3 2、格的子代數(shù)也是格；Th7.4 3、格滿足對(duì)偶律； 4、代數(shù)格必為偏序格。,注: 任取L中元素a，由，+滿足吸收律知， a（a+a）=a， a +（aa）=a。 故 aa=a（a+（aa）， a+a=a+（a（a +a）。 又由，+ 滿足吸收律知，上面兩式的等式右 端都等于a。因此， aa = a， a + a = a。 即， 運(yùn)算亦滿足等冪律。,定義（對(duì)偶式）,定義：在格（L，+ ）的任一公式中，出現(xiàn)，+處分別用+，替換后所得到的公式稱(chēng)為該公式的對(duì)偶式。 如: (1) a+b+c 與 abc (2)