離散數(shù)學 格.ppt

1、7.2 格論,集合代數(shù)：（(S)，）,對A,B,C(S)，運算，滿足： 等冪律 AA = A， AA = A， 交換律 AB = BA， AB = BA， 結合律 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，）,對A,B,CS，運算，滿足： 等冪律 AA = A， AA = A， ， 交換律 AB = BA，AB = BA 結合律 A（BC）=（AB）C， A（BC） = （AB）C 分配律 A(BC)=(AB

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

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

4、，）是格， 則稱（S，）是格（L，）的子格。,格的性質(zhì)：,1、格滿足冪等律: aa=a，a+a=a；Th7.3 2、格的子代數(shù)也是格；Th7.4 3、格滿足對偶律； 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。 即， 運算亦滿足等冪律。,定義（對偶式）,定義：在格（L，+ ）的任一公式中，出現(xiàn)，+處分別用+，替換后所得到的公式稱為該公式的對偶式。 如: (1) a+b+c 與 abc (2)