【文章內(nèi)容簡介】 //此證唯一 如果我們把 TΣ看作程序設(shè)計(jì)語言的語法， ∑_代數(shù) (A， ∑A)看作是語義域或解釋。則本定理說明語言中的每一表達(dá)式或項(xiàng)，在 (A， ∑A)中都對應(yīng)唯一的含義，即在語義域中只有一個(gè)解釋。本定理的另一層意圖是試圖說明 TΣ是“最小”的∑_代數(shù)。 全等類 定義 1011(∑代數(shù)類 ) 具有 ∑操作的代數(shù)集合稱 ∑_代數(shù)類 ， 記為 C。 定義 1012(初始代數(shù) Initial algebra) 若代數(shù)類 C中 ∑_代數(shù) I是初始代數(shù) ， 僅當(dāng)對 C中每一 ∑_代數(shù) J都存在著從 I到 J的唯一 ∑_同態(tài) 。 由定理 101， 項(xiàng)代數(shù) TΣ在所有 ∑_代數(shù)的類中是初始的 。 這就意味著 TΣ到任何∑_代數(shù)的值都存在著唯一的項(xiàng)映射 。 這是很強(qiáng)的概念 。 人們只要標(biāo)識(shí)出某個(gè)有 “ 意義 ” 的 ∑_代數(shù) ， 即可將項(xiàng)映射到該代數(shù)的元素上 。 以此定義項(xiàng)的語義 。 定理 102 ? 若 ∑_代數(shù)類 C中代數(shù) A， B均為初始代數(shù) ， 則它們必為同構(gòu)的 。 ? 證 : 若 A為初始的 ， B為一般 ∑_代數(shù) ， 按定義 1012它們必存在唯一 ∑_同態(tài) i1: A→B 。 同樣 ， 若 B為初始的 ， A為一般 ∑_代數(shù) ， 也存在唯一 ∑同態(tài) i2: B→A 。它們的復(fù)合 ? i1 o i2 = A→A = idA ? 同理 ， i2 o i1 = B→B = idB ? 所以 ， 它們是同構(gòu)的 。 ? 初始代數(shù)只在符號(hào)形式上區(qū)別初始項(xiàng) ， 只要符號(hào)不同就是不同的值 。 例如 ，有 ∑_項(xiàng)代數(shù) ? Bool = {true， flase， not} ? 其項(xiàng)集是 : ? TΣ = {true， not(true)， not(not(true))， … ? false， not(flase)， not(not(flase))， … } ? 事實(shí)上我們知道 (true， not(false)， not(not(true)… }， 和 {false， not(true)，not(not(false))， … } 是語義等價(jià)的兩個(gè)類我們記為 {[true]， [false]}。 ? 定義 1013 (∑_全等 congruence) ? 在 ∑_代數(shù) (A， ∑A)中 ， A上的關(guān)系 R是 ∑_全等關(guān)系 ， 若有 ai， ai39?！?R(0≤i≤k，ai， ai39?！?A)成立 ， 僅當(dāng)對 ∑中每個(gè) k目的 σ， σA(a1， … ， ak)， σA (a139。， … ak39。) ∈ R也成立 。 ? 按上例 ， (ture， not(flase))∈ R， 則有 (not(true)， not(not(false)))∈ R。 全等關(guān)系若以 39。≡39。符號(hào)直接表示兩個(gè)項(xiàng)是全等的 。 以上定義是 : ? 若 ture ≡ not(false)則有 ? not(ture) ≡ not(not(false)) ? 定義 1014 (商代數(shù) Quotient Algebra) ? 對于 ∑_代數(shù) (A， ∑A)中的承載子 a∈ A， 按全等關(guān)系 R歸于 [a] R則稱商化(quotienting)。 商化的結(jié)果得到全等類集合 A/R = {[a] R｜ a∈ A}， 且在 A/R上對∑中的每個(gè) σ可定義以下映射 : ? σA/R([a1] R, … ,[a k] R = [σA(a1， … ， ak)] R ? 其中 σA/R ∈ ∑A/R， []表示 … 的全等類 。 則稱 (A/R， ∑A/R)為商代數(shù) 。 ? 可以推論 : [1] (A/R， ∑A/R)是 ∑_代數(shù) 。 ? [2] 由于存在 A→A/R 直射 ， h(a) = [a] R也是 ∑_同態(tài) 。 ? 我們最感興趣的是在 項(xiàng)集 TΣ上的 ∑_全等 。 如果所有項(xiàng)對偶 t， t39。 R ， 根據(jù) TΣ的初始性有 iA: TΣ→A ， 則 iA(t) = iA(t39。)即 ∑_代數(shù) A也具有等價(jià)關(guān)系 R。 設(shè) C(R)是所有具有 R性質(zhì)的 ∑_代數(shù)類 。 定理 103 (全等的初始性 ) 在具有性質(zhì) R的代數(shù)類中 ∑_代數(shù) TΣ/R是初始代數(shù) 。 泛同構(gòu)映射 給定一操作集 ， 我們可構(gòu)造所有可能的表達(dá)式 ， 也就是對應(yīng)于 ∑的所有可能值集的外延 。 在這個(gè)值集上操作的代數(shù)則稱字代數(shù) 。 3+5按前述自然數(shù)集上代數(shù) (N， ∑N)是 ∑_代數(shù) ， 但不是字代數(shù) . 定義 1015(泛同構(gòu) Universal Isomorphism) 給定一代數(shù) ， 從它的商代數(shù)出發(fā)可以找到許多同態(tài)映射 ， 直到找出同構(gòu) 。則稱為泛同構(gòu) 。 定義 1016(自由字代數(shù) Free word algebra) 自由字代數(shù)是每個(gè)項(xiàng)均可為變量的字代數(shù) 。 因?yàn)榘捶和瑯?gòu)理論 ， 從商代數(shù)尋找同構(gòu) ， 把字代數(shù)因素化要更方便 。 E(Y)是有變量并以表達(dá)式形式表達(dá)的承載子集合 。 例 104 ∑_字代數(shù)的項(xiàng)集 設(shè) Y = {x， y， z}， ∑ = {+， *}對于 ∑_字代數(shù) (E(Y)， ∑)可能的項(xiàng)集是 : {x , y , z , x*y， z+x， x*(y+x*z)， … } 定義 1010(Sp代數(shù) ) 我們稱 (∑0， ∑， E)為 Sp代數(shù) ， 其中 ∑0為常量算子集 ， ∑為算子集 ， E為公理集 。 公理集 E是由 ∑_項(xiàng)表達(dá)的全等關(guān)系 。 代數(shù)規(guī)格說明 數(shù)據(jù)類型可以以下述等價(jià)方式描述 : ? 字代數(shù)上的某個(gè)全等關(guān)系 。 ? 字代數(shù)的某個(gè)商代數(shù) 。 代數(shù)規(guī)格說明中以代數(shù)公理給出全等關(guān)系 。 代數(shù)公理是表征兩個(gè)代數(shù)項(xiàng)全等的等式集合 x = R y(上下文清晰時(shí)略去下標(biāo) R) 即為一簡單公理 。 根據(jù)公理置換型構(gòu)中的操作符 ， 即可生成全等類 。 置換中遵循全等性質(zhì) : 自反性 x = y， y = x或 x≡y(x,y是同一項(xiàng) ) 對稱性 y = R x 傳遞性 x = R y， y = R z 則 x = R z 全等性 若 xi = R yi， 有某操作 σ則 xi≡σ(x1， … ， xm)。 yi≡σ(y1， … ， ym) 0≤i≤n 若有一最簡單型構(gòu) : 0: →N S: N→N 和以下公理集 : R0 = {} R1 = {0 = 0} R2 = {0 = S0} R3 = {0 = SS0} R4 = {S0 = SS0} 由這五個(gè)公理生成的全等類是 : C/R0， R1: {0}， {S0}， {SS0}， … 如果 S的語義是 “ 后繼 ” 則 C/R0， R1為自然數(shù)集 。 C/R2: {0， S0， SS0， … } 為所有項(xiàng)均全等的小代數(shù) 。 C/R3: {0， SS0， SSSS0， … } {S0， SSS0， SSSSS0， … } 可以看做布爾代數(shù)值集 ([true]， [false]}。 C/R4: {0}， {S0， SS0， SSS0， … } 以上 (C/Ri， ∑)都是 ∑_字代數(shù) ， 由于 ∑_全等的關(guān)系不同 ， 同態(tài)映射為自然數(shù) 、 小代數(shù) 、布爾代數(shù) 、 二值代數(shù) 。 也說明 ∑_字代數(shù)的初始性 。 每一代數(shù)都是一簡單數(shù)據(jù)類型