【正文】 ? 求積代數(shù) 12 ,GG? ? ??商代數(shù)和積代數(shù) 解： 1 2 1 2 1 2 31 1 1 2 1 3 2 1 2 2 2 3{ , } { , , }{ , , , , , , , , , , , }G G a a b b ba b a b a b a b a b a b? ? ?? ? ? ? ? ? ? ? ? ? ? ? ?對(duì)任意的 ， ,ijab?? 12,ija b G G??? ? ? ?, , * ,i j i j i i j ja b a b a a b b? ? ? ?? ? ? ? ? ? ? ? ?第六章 代數(shù)系統(tǒng) ? ? ? ? ? 定義：設(shè) S,*是一個(gè)代數(shù)系統(tǒng)， *是 S上的二元運(yùn)算；若 *是可結(jié)合的，則 S,*稱為一個(gè) 半群 。 定義： 如果 S,*是一個(gè)半群，并且關(guān)于 *運(yùn)算有單位元 e，則稱 S,*為 獨(dú)異點(diǎn) 或 含幺半群 ，記作S,*,e 。 例： N,+,0,N,?,1,I,+,0,R,?,1,Nn,?n,1 都是獨(dú)異點(diǎn)，其中 n為正整數(shù)。 設(shè) Σ 是非空有限字母表，則 Σ *,?, ε 是獨(dú)異點(diǎn)，而 Σ +, ?不是獨(dú)異點(diǎn)，其中 ε是空串。 ,??? ?典型代數(shù)系統(tǒng) 例： 如果獨(dú)異點(diǎn) G,?的每個(gè)元素關(guān)于 ?都是可逆的，則稱 G,?為群。 設(shè) A為任意非空集合， PA是 A到 A的所有雙射函數(shù)的集合，于是 PA,?構(gòu)成一個(gè)群，其中 ?是函數(shù)的復(fù)合運(yùn)算，稱 PA,?為對(duì)稱群，稱 PA,?的子群為 A的變換群。 例如， A={1,2,3}，由 A到 A的所有雙射函數(shù)為3!=6個(gè)，它們是 123456{ 1 , 1 , 2 , 2 , 3 , 3 }{ 1 , 1 , 2 , 3 , 3 , 2 }{ 1 , 3 , 2 , 2 , 3 , 1 }{ 1 , 2 , 2 , 1 , 3 , 3 }{ 1 , 2 , 2 , 3 , 3 , 1 }{ 1 , 3 , 2 , 1 , 3 , 2 }ffffff? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?典型代數(shù)系統(tǒng) ?在 PA上的運(yùn)算表如下： 可以看出 f1是幺元， f2的逆元是 f2， f3的逆元是f3， f4的逆元是 f4， f5的逆元是 f6， f6的逆元是 f5，并且 {f1,f2}, ?， {f1,f3}, ?， {f1,f4}, ? 和 {f1,f5,f6}, ?都是 PA, ?的子群，所以它們都是變換群。 典型代數(shù)系統(tǒng) 能否對(duì)一個(gè)抽象的代數(shù)系統(tǒng)進(jìn)行研究，而這種代數(shù)系統(tǒng)具有像命題代數(shù)、集合代數(shù)等一些具體代數(shù)系統(tǒng)所具有的最本質(zhì)的特征。 這種抽象的代數(shù)系統(tǒng)就是由布爾（ Boole）于 1854年建立的布爾代數(shù)。實(shí)際上，還存在著比布爾代數(shù)更一般的代數(shù)系統(tǒng)，那就是格。 定義：設(shè) L,≤是偏序集，對(duì)于任意的 a,b∈ L，{a,b}均有上確界和下確界，則稱 L,≤ 為格。 典型代數(shù)系統(tǒng) 通常 a*b用表示 {a,b}的下確界 ,也就是 a*b=inf{a,b}，稱為 a,b的積。用 a⊕ b表示 {a,b}的上確界，記a⊕ b=sup{a,b}，稱為 a和 b的和，因?yàn)槠蚣偷娜魏畏强兆蛹纳?、下確界若存在，必唯一。所以 *和⊕ 可以看作是集合 L上的兩個(gè)代數(shù)運(yùn)算。于是代數(shù)系統(tǒng) L,*,⊕ 是一個(gè)格。 每個(gè)全序結(jié)構(gòu)都是格。但是，不是所有的偏序結(jié)構(gòu)都是格。 典型代數(shù)系統(tǒng) {a},,{c}是格，而 nhcuj7d3{e}{f}是偏序集，但不是格。 典型代數(shù)系統(tǒng) 例：設(shè) D是 I+上的整除關(guān)系，亦即，對(duì)任意的 a,b∈ I+，aDb，當(dāng)且僅當(dāng) a整除 b。于是 I+,D是一個(gè)格，其中a*b=a和 b的最大公因子， a⊕ b=a和 b的最小公倍數(shù)。 *和 ⊕ 的基本性質(zhì)： 等冪律 ,a a a a a a? ? ? ?交換律 ,a b b a a b b a? ? ? ? ? ?結(jié)合律 ( ) ( ) a b c a b c? ? ? ? ?( ) ( )a b c a b c? ? ? ? ?吸收律 ( ) , ( )a a b a a a b a? ? ? ? ? ?典型代數(shù)系統(tǒng) 設(shè) L,*,⊕ 是格，則在格中每對(duì)元素都有上、下確界，設(shè) S={a1,a2,? ,an}是 L的有限子集，則 S應(yīng)有上確界和下確界。一般地，可以把 S的下確界和上確界表示成 121121inf ( )sup ( )ninininiS a a a aS a a a a??? ? ? ? ? ????? ? ? ? ? ??? ?典型代數(shù)系統(tǒng) 定義：有最大元素和最小元素的格稱為 有界格 。通常把有界格的最大元素和最小元素分別記為 1和 0，并稱它們?yōu)楦竦慕纭? 顯然， L,*,⊕ 有限格是有界格，并且 ，其中 L={a1,a2,? ,an} ,常把有界格記為 L,*,⊕ ,0,1。對(duì)于任意的 a∈ L,a≤1且 0≤a，因此有 1 10 * , 1nniii iaa? ?? ? ?0 , 11 1 , 0 0a a a aaa? ? ? ?? ? ? ?典型代數(shù)系統(tǒng) 設(shè)是 L,*,⊕ ,0,1有界格， a,b∈ L，如果 a*b=0且a⊕ b=1，則稱 b為 a的補(bǔ)元，記為 b=a39。如果 L中每個(gè)元素都有補(bǔ)元，則稱 L,*,⊕ ,0,1為有補(bǔ)格。 補(bǔ)元的定義是相互的。一個(gè)元素可以有補(bǔ)元，也可以沒(méi)有補(bǔ)元，如果有補(bǔ)元，可以有一個(gè)補(bǔ)元，也可以有多個(gè)補(bǔ)元。 典型代數(shù)系統(tǒng) bc a01在左圖的格中， a和 b均為 c的補(bǔ)元， a和 b的補(bǔ)元均為 c。1和 0互為補(bǔ)元，且唯一。 典型代數(shù)系統(tǒng) 定義： 設(shè) L,*,⊕ 是一個(gè)格，如果 *對(duì) ⊕ 是可分配的，并且 ⊕ 對(duì) *也是可分配的，則稱 L,*,⊕ 是 分配格 。 要判斷一個(gè)格是不是分配格，只須檢驗(yàn)一個(gè)分配律即可，因?yàn)樵诜峙涓竦亩x中，兩個(gè)分配律是互為對(duì)偶的，故對(duì)偶原理適用于分配格。 ba c01 a b c10均不是分配格 典型代數(shù)系統(tǒng) ? 一個(gè)格是分配格，當(dāng)且僅當(dāng)它沒(méi)有子格同構(gòu)于這兩個(gè)五元素格之一。 典型代數(shù)系統(tǒng) 定義： 一個(gè)有補(bǔ)分配格稱為一個(gè) 布爾代數(shù) 。 一般用 B,*,⊕ , 39。,0,1表示布爾代數(shù)。其中 B,*,⊕ 是格 ,39。是一元的求補(bǔ)運(yùn)算， 0和 1為最小元素和最大元素。 例：設(shè) B={0， 1}， B上的運(yùn)算 *， ⊕ 和 ?如下表定義： B,*,⊕ , 39。,0,1是最簡(jiǎn)單的布爾代數(shù)，稱為 電路代數(shù) 。 典型代數(shù)系統(tǒng) 例：設(shè) S是非空集合，不難證明 ρ(S), ? , ? ,~,Φ,S 是布爾代數(shù)，稱為集合代數(shù)。其中任何 A?S的補(bǔ)元為～ A=SA。 ρ(S)中的偏序關(guān)系是 ? 。如果 S有 n個(gè)元素，則 ρ(S)有 2n個(gè)元素，布爾代數(shù)的圖是一個(gè) n維立方體。 例： 用 S表示含有 n個(gè)原子的合式公式的集合，代數(shù)系統(tǒng) S, ∧ , ∨ , ┐,F,T是布爾代數(shù)，稱為命題代數(shù)。其中 ∧ , ∨ 和 ┐分別是合取、析取和否定， F和 T分別是一個(gè)永假式和永真式，并且把等價(jià)的合式公式看成是相等的，對(duì)應(yīng)的偏序關(guān)系是蘊(yùn)含 。 ?典型代數(shù)系統(tǒng) 定義 : 令 Bn={0,1}n,對(duì)任意 a=a1,a2,? ,an, b=b1,b2,? ,bn∈ Bn定義 1 1 2 21 1 2 212, , , , , , ,nnnnna b a b a b a ba b a b a b a ba a a a? ? ? ? ? ??? ? ?? ? ? ? ? ??? ? ?? ? ? ? ? ??? ? ?這里 ∧ , ∨ 和 ┐是 {0,1}上的邏輯運(yùn)算。代數(shù)系統(tǒng) Bn,*,⊕ , 39。,0n,1n是布爾代數(shù)。其中 0n和 1n分別是成員都為 0和成員都為 1的 n元序偶。這個(gè)代數(shù)被稱為開(kāi)關(guān)代數(shù)。