十二章節(jié)格與布爾代數(shù)

1、第十二章 格與布爾代數(shù)12.1 格定義的代數(shù)系統(tǒng)12.2 格的代數(shù)定義 12.3 一些特殊的格12.4 有限布爾代數(shù)的唯一性12.5 布爾函數(shù)和布爾表達(dá)式復(fù)習(xí)：偏序集、格格是一個(gè)偏序集，在這個(gè)偏序集中，每?jī)蓚€(gè)元素有唯一一個(gè)最小上界和唯一一個(gè)最大下界。定義（見(jiàn)第85頁(yè)定義1） 設(shè)A是一個(gè)非空集合， R是A上的一個(gè)二元關(guān)系，若R有自反性、反對(duì)稱(chēng)性、傳遞性，說(shuō)R是A上的一個(gè)偏序關(guān)系。 并稱(chēng)(A，R)是一個(gè)偏序集。 注意： 對(duì)于一個(gè)偏序關(guān)系，往往用記號(hào)“”來(lái)表示。 若(a，b) ，記為a b，讀做“ a小于等于b”。 一個(gè)偏序集，通常用符號(hào)(A，)來(lái)表示。格例 如圖用哈斯圖給出了一個(gè)有5個(gè)元的格。 定

2、義（見(jiàn)第86頁(yè)定義2）A是一個(gè)非空集，(A，)是一個(gè)偏序集，若對(duì)于任意的元素a和b屬于A，在A中存在a和b的最小上界及最大下界，就說(shuō)(A，)是一個(gè)格。a1a2a4a5a3例30610152351右上圖所示的偏序集(D(30)，R)是格。（詳見(jiàn)練習(xí)7.33)例 右下圖所示的偏序集 (1, 2, 3, 4, )不是格。 （詳見(jiàn)第85頁(yè)例1）1234由格定義的代數(shù)系統(tǒng)設(shè)(A，)是一個(gè)格，定義代數(shù)系統(tǒng)（A，）, 其中和是A上的兩個(gè)二元運(yùn)算， 對(duì)于任意的a，bA，ab等于a和b的最小上界，ab等于a和b的最大上界。稱(chēng)（A，）是由格(A，)所定義的代數(shù)系統(tǒng)。 注意：二元運(yùn)算通常稱(chēng)為并運(yùn)算，二元運(yùn)算通常稱(chēng)為

3、交運(yùn)算，因此，a和b的最小上界，也稱(chēng)a和b的并；a和b的最大下界，也稱(chēng)a和b的交。 例設(shè)2A是集合A的冪集，（2A，）是一個(gè)格。因此，它確定了一個(gè)對(duì)應(yīng)的代數(shù)系統(tǒng)：（2A，）。對(duì)于任意的x，yA，由定義知:xy=xy，xy=xy。例設(shè)Z+是正整數(shù)集，是Z+上一個(gè)二元關(guān)系，（Z+，）是一個(gè)格。在格（Z+，）所定義的代數(shù)系統(tǒng)：（Z+，）中，對(duì)于任意的m，nZ+，mn=m和n的最小公倍數(shù)；mn=m和n的最大公約數(shù)。定理1對(duì)于格(A，)中的任意元素a和b，有：a ab (12.1)ab a (12.2)定理2(A，)是一個(gè)格，對(duì)于A中的任意的a、b、c和d，如果 a b, 且 c d，則有：ac bd

4、(12.3)ac bd (12.4)定理3設(shè)(A，)是一個(gè)格， （A，）是格(A，)定義的代數(shù)系統(tǒng)，則對(duì)于任意的a，b，cA，以下算律成立：L1：aa=a，aa=a；（冪等律）L2：ab=ba，ab=ba；（交換律）L3：(ab)c=a(bc)(ab)c=a(bc)；（結(jié)合律）L4：a(ab)=a，a(ab)=a。（吸收律）第十二章 格與布爾代數(shù)12.1 格定義的代數(shù)系統(tǒng)12.2 格的代數(shù)定義 12.3 一些特殊的格12.4 有限布爾代數(shù)的唯一性12.5 布爾函數(shù)和布爾表達(dá)式問(wèn)題 設(shè)（A，）是具有兩個(gè)二元運(yùn)算和的代數(shù)系統(tǒng)，并且和運(yùn)算適合上節(jié)定理3中描述的四個(gè)算律L1、L2、L3與L4。如何設(shè)法

5、利用和運(yùn)算在A中引入一個(gè)偏序關(guān)系，使A關(guān)于這個(gè)偏序關(guān)系構(gòu)成一個(gè)格？問(wèn)題(續(xù))問(wèn)題: ab=a和ab=b是否同時(shí)成立？代數(shù)系統(tǒng)定義的二元關(guān)系定義: 在集合A上定義二元關(guān)系： 對(duì)于任意a，bA，若 ab=a 成立(或ab=b成立) ， 則定義ab。驗(yàn)證: 所定義的二元關(guān)系是偏序關(guān)系自反性反對(duì)稱(chēng)性傳遞性所以, 是A上的偏序關(guān)系，（A，）是一個(gè)偏序集。 驗(yàn)證: 所定義的偏序集是格首先，證明對(duì)于任意的a，bA，ab是a，b的最大下界。可以證明ab是a，b的最小上界?？傊?，由代數(shù)系統(tǒng)(A，)定義的偏序集(A，)是格。格的等價(jià)定義定義1：設(shè)（A，）是一個(gè)代數(shù)系統(tǒng)，和是A上的兩個(gè)封閉的二元運(yùn)算，且滿(mǎn)足算律：對(duì)

6、于任意的a，b，cA，L1：aa=a， aa=a； （冪等律）L2：ab=ba， ab=ba； （交換律）L3：(ab)c=a(bc) (ab)c=a(bc)； （結(jié)合律）L4：a(ab)=a， a(ab)=a。 （吸收律）則說(shuō)（A，）是一個(gè)格。例1 (Z+，)= (Z+，|)Z+是正整數(shù)集，對(duì)于任意的a，b Z+，規(guī)定ab=(a，b)（即a和b的最大公約數(shù)），ab=a，b（即a和b的最小公倍數(shù)）ab和ab是Z+上的兩個(gè)二元運(yùn)算可以證明：(Z+，)是一個(gè)格, 且與格(Z+，|)是一致的。第十二章 格與布爾代數(shù)12.1 格定義的代數(shù)系統(tǒng)12.2 格的代數(shù)定義 12.3 一些特殊的格12.4 有限

7、布爾代數(shù)的唯一性12.5 布爾函數(shù)和布爾表達(dá)式分配格定義1 設(shè)(A，)是一個(gè)格， 若對(duì)于任意a，b，cA，有a(bc)= (ab)(ac)a(bc)= (ab)(ac) 則稱(chēng)(A，)是一個(gè)分配格。例 (2A，)是一個(gè)分配格。泛下界、泛上界定義2 設(shè)(A，)是一個(gè)格，若存在aA，對(duì)于任意bA，a b，則稱(chēng)a為泛下界；若存在eA，對(duì)于任意bA，b e，則稱(chēng)e為泛上界。顯然，泛上界和泛下界若存在必唯一。用0和1分別表示一個(gè)格的泛下界和泛上界。例在左圖中，a是泛下界，b是泛上界。dcbaedbac在右圖中，a是泛下界，e是泛上界。例格(2A，)中，A是泛上界，而是泛下界。A=1,2,31,21,32,

8、3123例在格(Z+，| )中，1是泛下界，沒(méi)有泛上界。補(bǔ)元、有補(bǔ)格設(shè)(A，)是一個(gè)格，0，1 A。設(shè)aA ，若存在bA ，滿(mǎn)足 ab=1，ab=0，則稱(chēng)b為a的補(bǔ)元。一個(gè)格，如果每一個(gè)元素都有補(bǔ)元，則稱(chēng)它為有補(bǔ)格。注意，若a是b的補(bǔ)，那么b也是a的補(bǔ)。定理(分配格的必要條件)在分配格中，如果一個(gè)元素有補(bǔ)元，那么這個(gè)補(bǔ)元是唯一的。布爾格、補(bǔ)運(yùn)算定義：一個(gè)有補(bǔ)的分配格也稱(chēng)為布爾格。設(shè)(A，)是一個(gè)布爾格，因?yàn)閷?duì)于每一個(gè)元素有唯一的補(bǔ)元，能定義A上的一個(gè)一元運(yùn)算，并用“ ”表示，稱(chēng)之為補(bǔ)運(yùn)算。 這樣，對(duì)于A中的每一個(gè)元素a，a是a的補(bǔ)元。布爾代數(shù)(Boolean Algebra)定義： 稱(chēng)一個(gè)布爾

9、格(A，) 所定義代數(shù)系統(tǒng) (A， ) 是一個(gè)布爾代數(shù)。 布爾代數(shù)的例子D=1,2,3,5,6,10,15,30(D, |)30610152351布爾代數(shù)的例子S=21,2,3(S, )1,2,31,21,32,3123德摩根律(A, )是一個(gè)布爾代數(shù)。對(duì)于任意的a，bA，有ab= abab= ab第十二章 格與布爾代數(shù)12.1 格定義的代數(shù)系統(tǒng)12.2 格的代數(shù)定義 12.3 一些特殊的格12.4 有限布爾代數(shù)的唯一性12.5 布爾函數(shù)和布爾表達(dá)式布爾代數(shù)(S)，)S是一個(gè)任意的集合，2S是S的冪集合，(2S，)是一個(gè)格，且是布爾格，記為布爾代數(shù) (S)，)。問(wèn)題：是否所有的布爾代數(shù)都是這樣

10、的形式呢？當(dāng)A是一個(gè)有限集，也就是(A，)是一個(gè)有限布爾代數(shù)時(shí)，這一問(wèn)題的答案是肯定的。第十二章 格與布爾代數(shù)12.1 格定義的代數(shù)系統(tǒng)12.2 格的代數(shù)定義 12.3 一些特殊的格12.4 有限布爾代數(shù)的唯一性12.5 布爾函數(shù)和布爾表達(dá)式問(wèn)題設(shè)(A，)是一個(gè)布爾代數(shù)，n(1)是一個(gè)正整數(shù)，如何表示一個(gè)An到A的函數(shù)(映射)、也就是A上的一個(gè)n元函數(shù)？例 0,1上的一個(gè)3元函數(shù)(a)表12.1布爾表達(dá)式(Boolean Expression)定義：設(shè)(A，)是一個(gè)布爾代數(shù)，其上的一個(gè)布爾表達(dá)式是如下的表達(dá)式：(1) A中的每個(gè)元素是一個(gè)布爾表達(dá)式。(2) 任意的一個(gè)變?cè)且粋€(gè)布爾表達(dá)式。(3) 如果e1和e2是兩個(gè)布爾表達(dá)式，那么，e1，e1e2，e1e2都是布爾表達(dá)式。(4) 所有的布爾表達(dá)式都是有限次的運(yùn)用(1)、(2)、(3)所得。E(x1，x2，xn)一個(gè)含有n個(gè)不同變?cè)牟紶柋磉_(dá)式，通常稱(chēng)為n個(gè)變?cè)牟紶柋磉_(dá)式。通常用E(x1，x2，xn)表達(dá)有n個(gè)變?cè)獂1，xn的一個(gè)布爾表達(dá)式。E(x1，x2，xn) n元函數(shù)不難看出，一個(gè)布爾表達(dá)式E(x1，x2，xn) 就表示了一個(gè)從An到A的一個(gè)函數(shù)。問(wèn)題：n元函數(shù) E(x1，x2，xn) ？是否從An到A的每一個(gè)函數(shù)f都可以