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