資源描述：
《離散數(shù)學(xué)格與布爾代數(shù).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第11章格與布爾代數(shù)離散數(shù)學(xué)中國地質(zhì)大學(xué)本科生課程本章內(nèi)容11.1格的定義與性質(zhì)11.2分配格、有補(bǔ)格與布爾代數(shù)本章總結(jié)作業(yè)11.1格的定義與性質(zhì)定義11.1設(shè)是偏序集，如果?x,y∈S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序≤作成一個格(lattice)。說明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運(yùn)算∨和∧。x∨y：表示x與y的最小上界x∧y：表示x和y的最大下界。本章出現(xiàn)的∨和∧符號只代表格中的運(yùn)算，而不再有其它的含義。格的實例例1
2、1.1設(shè)n是正整數(shù)，Sn是n的正因子的集合。D為整除關(guān)系，則偏序集構(gòu)成格。?x,y∈Sn，x∨y是lcm(x,y)，即x與y的最小公倍數(shù)。x∧y是gcd(x,y)，即x與y的最大公約數(shù)。下圖給出了格，和。例11.2例11.2判斷下列偏序集是否構(gòu)成格,并說明理由。(1)，其中P(B)是集合B的冪集。(2)，其中Z是整數(shù)集,≤為小于或等于關(guān)系。(3)偏序集的哈斯圖分別在下圖給出。例11.2解答(1)是格。?x,y∈P(B)，x∨y就是
3、x∪y，x∧y就是x∩y。由于∪和∩運(yùn)算在P(B)上是封閉的，所以x∪y，x∩y∈P(B)。稱,為B的冪集格。(2)是格。?x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它們都是整數(shù)。(3)都不是格。(a)中的{a,b}沒有最大下界。(b)中的{b,d}有兩個上界c和e,但沒有最小上界。(c)中的{b,c}有三個上界d,e,f,但沒有最小上界。(d)中的{a,g}沒有最大下界。例11.3例11.3設(shè)G是群，L(G)是G的所有子群的集合。即L(G)＝{H
4、H≤G}對任意的H
5、1,H2∈L(G)，H1∩H2也是G的子群，而是由H1∪H2生成的子群（即包含著H1∪H2的最小的子群）。在L(G)上定義包含關(guān)系?，則L(G)關(guān)于包含關(guān)系構(gòu)成一個格，稱為G的子群格。易見在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是。對偶原理定義11.2設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。令f*是將f中的≤替換成≥，≥替換成≤，∨替換成∧，∧替換成∨所得到的命題。稱f*為f的對偶命題。例如在格中令f是(a∨b)∧c≤c，則f*是(a∧b)∨c≥c。格的
6、對偶原理設(shè)f是含有格中元素以及符號＝、≤、≥、∨和∧的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。例如對一切格L都有?a,b∈L，a∧b≤a(因為a和b的交是a的一個下界)那么對一切格L都有?a,b∈L，a∨b≥a說明許多格的性質(zhì)都是互為對偶命題的。有了格的對偶原理，在證明格的性質(zhì)時， 只須證明其中的一個命題即可。格的運(yùn)算性質(zhì)定理11.1設(shè)是格，則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律，即(1)交換律?a,b∈L有a∨b＝b∨aa∧b＝b∧a(2)結(jié)合律?a,b,c∈L有(a
7、∨b)∨c＝a∨(b∨c)(a∧b)∧c＝a∧(b∧c)(3)冪等律?a∈L有a∨a＝aa∧a＝a(4)吸收律?a,b∈L有a∨(a∧b)＝aa∧(a∨b)＝a定理11.1(1)a∨b和b∨a分別是{a,b}和{b,a}的最小上界。由于{a,b}＝{b,a}，所以a∨b＝b∨a。由對偶原理，a∧b＝b∧a得證。(2)由最小上界的定義有(a∨b)∨c≥a∨b≥a(13.1)(a∨b)∨c≥a∨b≥b(13.2)(a∨b)∨c≥c(13.3)由式13.2和13.3有(a∨b)∨c
8、≥b∨c(13.4)再由式13.1和13.4有(a∨b)∨c≥a∨(b∨c)同理可證(a∨b)∨c≤a∨(b∨c)根據(jù)偏序關(guān)系的反對稱性有(a∨b)∨c＝a∨(b∨c)由對偶原理，(a∧b)∧c＝a∧(b∧c)得證。定理11.1(3)顯然a≤a∨a,又由a≤a可得a∨a≤a。根據(jù)反對稱性有a∨a＝a，由對偶原理，a∧a＝a得證。(4)顯然a∨(a∧b)≥a(13.5)又由a≤a，a∧b≤a可得a∨(a∧b)≤a(13.6)由式13.5和13.6可得a∨(a∧b)＝a，根據(jù)對偶原理，a∧(a∨b)＝a得證
9、。定理11.2定理11.2設(shè)是具有兩個二元運(yùn)算的代數(shù)系統(tǒng)，若對于*和?運(yùn)算適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義S中的偏序≤，使得構(gòu)成一個格，且a,b∈S有a∧b＝a*b，a∨b＝a?b。思路(1)證明在S中*和?運(yùn)算都適合冪等律。(2)在S上定義二元關(guān)系R，并證明R為偏序關(guān)系。(3)證明構(gòu)成格。說明通過規(guī)定運(yùn)算及其基本性質(zhì)可以給出格的定義。定理11.2?a∈S，由吸收律得(1)證明在S中
