【正文】 flip) flip(0) = 1 flip(1) = 0 B({yes,no, maybe}， change) change(yes) = no change(no) = yes change(maybe) = maybe C({any}， same) same(any) = any 若有態(tài)射函子 h: BOOLEAN→A 。 若 f: A→B 中 f是單射的且滿足 (101)， 則稱單同態(tài) (monomorphism)。 意即代數(shù) A中某 k目操作op， 若將其 k個(gè)變?cè)扔成涞酱鷶?shù) B中 ， 總可以找到同目的操作 op39。 如果對(duì)任意 op∈ OP， a1，a2， … an∈ A有 : ? f (op (a1， a2， … an)) = op39。 ? 對(duì)于任意 b∈ B都可以找到一個(gè) a∈ A， 使得 b|| =|| f (a)， 則 f稱為滿射 (surjective) 函子 。組合算子服從結(jié)合律。 X為態(tài)射函子 f（ function）的域 (domain)， Y為 f的協(xié)域 (codomain)。 ? 定義 102(子代數(shù) ) 設(shè) (A， OP)是一個(gè)代數(shù) ， (B， OP)也是一代數(shù)且 ?(A， OP)，則稱 (B， OP)是 (A， OP)的子代數(shù)，寫為 (B， OP)≤(A， OP)。同樣若 o是 *， i(a) = 1。 OPi(a1， a2， …a n) = as: A→A(a i， as ∈ A， i = 1‥ n) ? 具體代數(shù) ({true， false}， {∧ ， ∨ ， ? }) //布爾代數(shù) (N， {+， *}) //整數(shù)代數(shù) (S， {gcd， lcm}) //S代數(shù) ? 抽象代數(shù) 只給出一抽象的 A集合和 (組合 )算子 {o}，以及在構(gòu)造中某些必需滿足的公理、定理。代數(shù)語(yǔ)義學(xué)公理規(guī)定算子的組合規(guī)則和約束。把模型的集合看作是代數(shù)結(jié)構(gòu)。 ? 代數(shù)基礎(chǔ) ? 定義 代數(shù)是形如 (A， OP)的對(duì)偶，其中 A是承載子 (carrier)集合， OP代表了操作符的有限集。若 o是 +， A是整數(shù)集， i((a) = 0。 這些“關(guān)系”被抽象為態(tài)射 (morphism)。 C(X,Y)為 X到 Y的態(tài)射 (morphism)集合，也可以寫作 f:X→Y ， f∈ C(X,Y)。 g: Y→Z ，則可利用組合算子 o形成新的態(tài)射 f o g: X→Z 。 ? 定義 104 (單射 ， 滿射 ， 雙射 ) ? 若有態(tài)射函子 f: A→B ， 對(duì)于任意兩對(duì)象 a1， a2∈ A， 且 a1≠a2， 都有 f(a1)≠f(a2)，(f(a1)， f(a2)∈ B)， 則 f稱為單射 (injective)函子 。 ? 定義 105(同態(tài)映射 homomorphism) ? 若態(tài)射函子 f: A→B 是從代數(shù) (A， OP)到 (B， OP， )的映射 。 f(a1)， f(a2)， … f(an)∈ B， n = 0， 1 … k。 ? 同理 。 同態(tài)保持兩代數(shù)結(jié)構(gòu)的相似性 ， 同構(gòu)即兩代數(shù)結(jié)構(gòu)相等 ， 僅管其中值集不相同 。 若有態(tài)射函子 h:BOOLEAN→B 。 同樣有 : h(true) = any， h(false) = any 驗(yàn)證 (101)式 : h(not(true)) = h(flase) = any same(h(true)) = same(any) = any 它們依然同態(tài) ， 但由于非直射 (非一對(duì)一 ),故非同構(gòu) 。 圖 101 態(tài)射的交換圖 程序員在設(shè)計(jì)程序時(shí)如能構(gòu)造抽象代數(shù) ， 把它寫成規(guī)格說明 ， 即 Sp代數(shù) ，再通過中間形式變?yōu)閷?shí)現(xiàn) ， 可以看作是同態(tài)映射變成不同的代數(shù) 。 定義 106(型構(gòu) Singnature) 型構(gòu)是表示操作的符號(hào) (有限或無限 )集 。 對(duì)一于 ∑中的每一函數(shù)符 σ， 均有一求目的函數(shù) : arity(σ): ∑→N arity(zero) = 0 // 不帶參數(shù) zero為常 (函 )數(shù) ， 零目算子 。 定義 109 (∑_項(xiàng) ， ∑_項(xiàng)集 ， 項(xiàng) _代數(shù) ) 若 ∑_代數(shù) (A， ∑A)中承載子集合 A中的每一元素 a i∈ A(i=1， … n)均可用 ∑中的函數(shù)符及其復(fù)合表示 ， 則每一用函數(shù)符號(hào)串表示的項(xiàng)稱為 ∑_項(xiàng) 。 記 ∑_項(xiàng)的集合為 TΣ ， 為滿足上述規(guī)則的最小項(xiàng)集 。 按上述項(xiàng)代數(shù)定義的承載子集合 TΣ是歸納性的 ， 即歸納出常量符號(hào)和 ∑中每個(gè) σ對(duì)這些符號(hào)返復(fù)操作的最小串的集合 。 這就是所謂結(jié)構(gòu)歸納法 。 若 h為雙射的則 ∑_同態(tài) h: A→B 即為同構(gòu) 。 如 A = {true， false， (∧ ， ∨ )}， B = {1， 0， (+*)}。 常量 TΣ項(xiàng)的 iA (t1) … ， iA(tk)已經(jīng)定義 。 此證同態(tài) 。本定理的另一層意圖是試圖說明 TΣ是“最小”的∑_代數(shù)。 這就意味著 TΣ到任何∑_代數(shù)的值都存在著唯一的項(xiàng)映射 。 定理 102 ? 若 ∑_代數(shù)類 C中代數(shù) A， B均為初始代數(shù) ， 則它們必為同構(gòu)的 。 ? 初始代數(shù)只在符號(hào)形式上區(qū)別初始項(xiàng) ， 只要符號(hào)不同就是不同的值 ?！?A)成立 ， 僅當(dāng)對(duì) ∑中每個(gè) k目的 σ， σA(a1， … ， ak)， σA (a139。 全等關(guān)系若以 39。 商化的結(jié)果得到全等類集合 A/R = {[a] R｜ a∈ A}， 且在 A/R上對(duì)∑中的每個(gè) σ可定義以下映射 : ? σA/R([a1] R, … ,[a k] R = [σA(a1， … ， ak)] R ? 其中 σA/R ∈ ∑A/R， []表示 … 的全等類 。 ? 我們最感興趣的是在 項(xiàng)集 TΣ上的 ∑_全等 。 設(shè) C(R)是所有具有 R性質(zhì)的 ∑_代數(shù)類 。 3+5按前述自然數(shù)集上代數(shù) (N， ∑N)是 ∑_代數(shù) ， 但不是字代數(shù) . 定義 1015(泛同構(gòu) Universal Isomorphism) 給定一代數(shù) ， 從它的商代數(shù)出發(fā)可以找到許多同態(tài)映射 ， 直到找出同構(gòu) 。 E(Y)是有變量并以表達(dá)式形式表達(dá)的承載子集合 。字代數(shù)上的某個(gè)全等關(guān)系 。 代數(shù)公理是表征兩個(gè)代數(shù)項(xiàng)全等的等式集合 x = R y(上下文清晰時(shí)略去下標(biāo) R) 即為一簡(jiǎn)單公理 。 C/R2: {0， S0， SS0， … } 為所有項(xiàng)均全等的小代數(shù) 。 每一代數(shù)都是一簡(jiǎn)單數(shù)據(jù)類型的模型 。 帶變量的公理 設(shè)有簡(jiǎn)單型構(gòu) 0: →N S: N → N +: N N →N R5: {x + 0 = x。 例如 : n+m = m+n //指出 39。 本規(guī)格說明并未顯式給出自然數(shù)集 {0， 1， 2， 3， … }， 但已給出同構(gòu)的項(xiàng)集 {0， succ0， succ succ0， … }， 它與以阿拉伯?dāng)?shù)字表示的自然數(shù)集具有完全一致的代數(shù)性質(zhì) 。 ? 代數(shù)間關(guān)系最重要是同態(tài)映射 ， 同構(gòu)是兩代數(shù)有對(duì)等的同態(tài)映射 。 ∑_同態(tài) 、 同構(gòu)指項(xiàng)代數(shù)上的 。 ? 按全等的等價(jià)關(guān)系 R歸類過程稱商化 ， 商化結(jié)果得的值集構(gòu)成商代數(shù) ， 商代數(shù)可以看作是簡(jiǎn)化了的字代數(shù) ， 并包含全等概念 。