【正文】 =0，而a為極小元素，由極小元素的定義知，a≠0，這就產(chǎn)生了矛盾。證明：（必要性）用反證法。 設(shè)（L，∧，∨，0，1）是一個(gè)布爾代數(shù)，相應(yīng)的部分序關(guān)系為“≤”。任取a∈L，有a+a=（a∧(a)）∨（(a)∧a）=0∨0=0，故L中每個(gè)元素都以自身為逆元素。任取a∈L，有a+0=0+a=（0∧(a)）∨（(0)∧a）=0∨(1∧a)=0∨a=a，故，0是（L,+）的單位元。由∧，∨運(yùn)算滿足交換律，得a+b=(a∧(b))∨((a)∧b) =（b∧(a)）∨（(b)∧a） = b+a,故運(yùn)算+是可交換的。故（L,+）是半群。（1）往證運(yùn)算+滿足結(jié)合律。 設(shè)（L，∧，∨，0，1）是一個(gè)布爾代數(shù)，如果在L上定義二元運(yùn)算+如下：a+b=(a∧(b))∨((a)∧b)證明：（L,+）是一個(gè)交換群。{a}和{b,c}互為余元素，和{a,c}互為余元素，{c}和{a,b}互為余元素。（A）={，{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}。解：（Stone定理）知，若取A={a,b,c}，則8個(gè)元素的布爾代數(shù)必同構(gòu)于（（A）,）。于是，f(x+y)=f(x)∨f(y)= ∨=，故x+y∈L。因此，有f(x)∨=，故f(x)=，即x∈L。對(duì)任意的x∈B，若x≤b，則x+b=b，于是，f(x+b)=f(b) = 。)= f(0) ∧f() 由f是同態(tài)映射= f(0) ∧（f(0)） 由f是同態(tài)映射=，所以，由L的定義知，0∈L。（3）對(duì)于任意的x,y∈L，有x+y∈L。+，ˉ，0，1）到布爾代數(shù)（S，∧，∨，β）的同態(tài)映射，令L=f1()={x|x∈B，f(x)=}，試證明：（1）0∈L。布爾代數(shù)的化簡(jiǎn)問(wèn)題教材中講得比較詳細(xì)，在此不再贅述。正是由于其特殊性，布爾代數(shù)間同態(tài)映射的要求更嚴(yán)格了。綜上，g是L/f到f(L)的格同構(gòu)映射。最后證明g是L/f到f(L)的同態(tài)映射。再證明g是L/f到f(L)的11映射。任取a’,b’∈f(L)，存在a，b∈L，使得a’=f(a),b’=f(b)。故∧，∨滿足交換律。從而，（L/f，∧，∨）是一個(gè)代數(shù)格。這說(shuō)明運(yùn)算∧和∨與等價(jià)類的代表選取無(wú)關(guān)，它們確實(shí)是L/f上的二元代數(shù)運(yùn)算。再由∧的定義[a]∧[b]=[a∧1b]，得[a1]∧[b1]= [a2]∧[b2]。又因f是同態(tài)映射，所以f(a1∧1b1)=f(a1)∧2f(b1)=f(a2)∧2f(b2)=f(a2∧1b2)。對(duì)任意的a1，a2，b1，b2∈L，若[a1]=[a2]，[b1]=[b2]，往證[a1]∧[b1]= [a2]∧[b2]。顯然，是L上的等價(jià)關(guān)系，其等價(jià)類集合就是L/f。（3）令g：[a]→f(a)，[a]∈L/f，則g是L/f到f(L)的格同構(gòu)映射。證明：（1）∧和∨是L/f上的二元代數(shù)運(yùn)算?？紤]商集L/f={[a]|a∈L}，其中[a]={x|x∈L且f(x)=f(a)}。注意證明一個(gè)映射是格同構(gòu)映射，它必須是11映射而且是格同態(tài)映射。綜上，f和g是R與S之間一對(duì)互逆的格同構(gòu)映射。任取x,y∈R，有f(x)+f(y)=(x+b)+(y+b) =(x+y)+b =f(x+y),f(x)f(y)= (x+b)(y+b) = (xy)+b =f(xy)，所以，f是R到S的格同態(tài)映射。（3）往證f是R到S的格同態(tài)映射，g是S到R的格同態(tài)映射。(2)往證f和g都是11映射而且互為逆映射。故ab≤g(y)≤a，由R的定義知，g(y)∈S。任取y∈S，由S的定義知，b≤y≤a+b。因此，（ab）+b≤x+b≤a+b，而（ab）+b=b，f(x)=x+b，故b≤f(x)≤a+b，由S的定義知，f(x)∈S。證明：（1）首先證明f是R到S的映射，g是S到R的映射。設(shè)R={x|x∈L，ab≤x≤a}，S={y|y∈L，b≤y≤a+b}，令f(x)=x+b，x∈R，g(y)=ya，y∈S。因此，（S，≤2）是有界格。因f是滿設(shè)，故對(duì)任意的x’∈S，都有x∈L，使得f(x)=x’。證明：因（L，≤1）是有界格，設(shè)最大元為1，最小元為0。 設(shè)f是格（L，≤1）到格（S，≤2）的滿同態(tài)映射。因此，f是（L，+）到自身的格同態(tài)映射。 設(shè)（L，+）是一分配格，a∈L，設(shè)f(x)=x+a，x∈L，g(x)=xa，x∈L，證明：f和g都是（L，+）到自身的格同態(tài)映射。 格的同態(tài)判斷一映射為格的同態(tài)映射，需注意驗(yàn)證加同態(tài)與乘同態(tài)兩條。由（L，+）是格知，l1l2∈L，l1+l2∈L，因此，f(l1l2)∈f(L)，f(l1+l2)∈f(L)，即，s1∧s2∈f(L)，s1∨s2∈f(L)，故，f(L)對(duì)運(yùn)算∧和∨封閉。任取s1，s2∈f(L)，則有l(wèi)1，l2∈L，滿足f(l1)=s1，f(l2)=s2。 設(shè)f是格（L，+）到格（S，∧，∨）的同態(tài)映射，試證明（L，+）的同態(tài)象是（S，∧，∨）的子格。因此L’對(duì)運(yùn)算亦封閉。證明：根據(jù)（1），有L’對(duì)運(yùn)算+是封閉的。那么稱L’是格L的理想。 設(shè)（L，+）是格，L’是L的非空子集，如果：⑴ 對(duì)于任意的a，b∈L’，有a+b∈L’。同理，ab有余元素a’b’，所以，ab∈L’。證明：設(shè)L中擁有余元素的的各元素構(gòu)成的集合為L(zhǎng)’，對(duì)于任意的a，b∈L’，它們的余元素分別記為a’和b’。 子格的判斷 判斷一個(gè)格中的一個(gè)子集是其格的辦法是根據(jù)格的定義來(lái)進(jìn)行判斷，即證明該子集中任意兩個(gè)元素構(gòu)成的集合的最小上界和最大下界都在該子集中，即運(yùn)算封閉。同理可證b=1。另一方面，因1是L上的最大元，有a≤1。同理可證b=0。另一方面，因0是L上的最小元，有0≤a。 設(shè)（L，0，1）是有界格，相應(yīng)的部分序關(guān)系是≤，證明：對(duì)于a，b∈L，（1）若ab=0，則a=b=0，（2）若ab=1，則a=b=1。對(duì)任意非0、非1的元素y，由全序格中任意兩個(gè)元素可比較大小知，或者有x≤y，或者有y≤x，不妨設(shè)前者成立，則xy=x≠0，因此，x無(wú)余元素。在全序格中任取非0、1的元素x。 證明：若一個(gè)有限的全序格含有不只兩個(gè)元素，則這個(gè)格必定不是有余格。由題設(shè)有界格（L，0，1）含有不止一個(gè)元素知，0=1顯然是矛盾的。證明：我們已經(jīng)知道在有界格中0，1互為余元素。因?yàn)楦鶕?jù)有余格的定義，有余格一定是有界格，而（N，|）顯然不存在上界，因而不可能是有余分配格。因?yàn)橐粋€(gè)元素可能有兩個(gè)以上的余元素。設(shè)L={，{x},{y},{x，y}}，則（L，∩，∪）是一個(gè)格，若令a={x}，b={y}，則a∪b=a和a∪b=b兩者均不成立。因?yàn)槿簦↙，）是格，則和均滿足交換律、結(jié)合律和運(yùn)算的封閉性，所以（L，）和（L，）均為交換半群。⑷ 設(shè)N為正整數(shù)集合，| 為其上的整除關(guān)系，則（N，|）為有余分配格。⑵ 設(shè)（L，）是格，a，b∈L，那么，ab=a和ab=b至少有一個(gè)成立。 主要解題方法 應(yīng)用格的性質(zhì) 這部分習(xí)題要求讀者熟記格及特殊的格的性質(zhì)，并能靈活應(yīng)用。10. 了解格與布爾代數(shù)在計(jì)算機(jī)科學(xué)中的應(yīng)用。掌握最簡(jiǎn)多項(xiàng)式、極簡(jiǎn)多項(xiàng)式的概念。+，ˉ，0n，1n）同構(gòu)；Stone定理。了解如果兩個(gè)有限布爾代數(shù)的維數(shù)相同，則這兩個(gè)代數(shù)同構(gòu)；任意n維布爾代數(shù)（B，掌握布爾代數(shù)的生成、極小項(xiàng)、多項(xiàng)式、多項(xiàng)范式、布爾代數(shù)中一組元素互相獨(dú)立等概念，了解布爾代數(shù)中元素與多項(xiàng)范式的關(guān)系和極小項(xiàng)、基底、極小元間的關(guān)系。7. 掌握可唯一表示布爾代數(shù)中元素的基底的定義及其性質(zhì)。了解電路代數(shù)、集合代數(shù)、命題代數(shù)、開(kāi)關(guān)代數(shù)。了解一個(gè)格為模格的充要條件。了解格的同態(tài)映射一定是保序映射，同構(gòu)映射的逆映射也是同構(gòu)映射等結(jié)論。3. 了解格的其它性質(zhì)，如格的保序性、分配不等式、模不等式等。2. 掌握互相對(duì)偶的兩個(gè)關(guān)系、互相對(duì)偶的兩個(gè)格的定義，了解二者關(guān)系。第八章 格與布爾代數(shù)167。 基本要求1. 掌握半序格、半序子格、代數(shù)格、代數(shù)子格的定義，了解半序格和代數(shù)格的定義是等價(jià)的。掌握格中表達(dá)式、對(duì)偶格中的對(duì)偶表達(dá)式、本格中的對(duì)偶表達(dá)式的定義，掌握并會(huì)應(yīng)用對(duì)偶原理1及對(duì)偶原理2。4. 掌握并會(huì)應(yīng)用格同態(tài)映射、格的自同態(tài)映射、格同構(gòu)映射的定義。5. 掌握有界格、有余格、分配格以及模格的定義以及相關(guān)的結(jié)論。6. 掌握布爾代數(shù)的定義及其16個(gè)性質(zhì)，掌握并會(huì)應(yīng)用Huntington公理來(lái)判定一代數(shù)系統(tǒng)是否為布爾代數(shù)。掌握并會(huì)應(yīng)用布爾代數(shù)的子集是其子代數(shù)的充要條件。掌握極小元的定義及其性質(zhì)。8. 掌握布爾代數(shù)中同態(tài)、同構(gòu)的概念及其相應(yīng)結(jié)論。+，ˉ，0，1）與開(kāi)關(guān)代數(shù)（Bn，9. 掌握電路函數(shù)、布氏式的概念，了解任意一個(gè)電路函數(shù)，都可表為一個(gè)布氏式。掌握兩種得到組成極簡(jiǎn)多項(xiàng)式的極簡(jiǎn)項(xiàng)的方法：Quine方法、Karnaugh圖法，會(huì)應(yīng)用這兩種方法求極簡(jiǎn)項(xiàng)，對(duì)布爾代數(shù)進(jìn)行化簡(jiǎn)。167。 請(qǐng)判斷下面關(guān)于格的命題的真假性⑴ 設(shè)（L，）是格，則（L，）和（L，）均為交換半群。⑶ 設(shè)（L，）是格，a∈L，若a有余元素，那么該余元素是唯一的。解：⑴ 該命題為真命題。⑵ 該命題為假命題。⑶ 該命題為假命題。⑷ 該命題為假命題。 證明：若一個(gè)有界格（L，0，1）含有不只一個(gè)元素，則該有界格中任何一個(gè)元素的余元素必不是它自身。若存在x≠0，x≠1，但x以自身為余元素，則有xx=0， xx=1，而又由于xx=x， xx=x，所以，x=0，x=1，即0=1。因此，若一個(gè)有界格含有不只一個(gè)元素，則任何一個(gè)元素的余元素必不是它自身。證明：因?yàn)槿蜿P(guān)系是特殊的部分序關(guān)系，所以可以定義全序關(guān)系的格，設(shè)為（L，0，1），相應(yīng)的全序關(guān)系為≤。由于x0=0，但x0=x≠1，x1=1，但x1=x≠0，所以0和1均不是x的余元素。即，若一個(gè)有限的全序格含有不只兩個(gè)元素，則其中非0、非1元均無(wú)余元素，故不是有余格。證明：（1）因?yàn)閍≤ab，由題設(shè)ab=0，所以a≤0。由≤的反對(duì)稱性知，a=0。（2）因?yàn)閍b≤a, 由題設(shè)ab=1，所以1≤a。由≤的反對(duì)稱性知，a=1。也可用對(duì)偶原理證。 設(shè)（L，0，1）是有界分配格，證明：L中擁有余元素的的各元素構(gòu)成一個(gè)代數(shù)子格。首先考察