變值配置函數空間整體編碼族的2維對稱性

鄭智捷

(云南大學軟件學院信息安全系,云南昆明650091)

在0-1域中,利用邏輯變量和函數模型進行開關代數分析、設計、描述、優化,以及超大規模集成電路設計和邏輯門陣列實現,通過卡諾圖,合取范式,析取范式等方法獲得邏輯函數表示[1-4]已有一系列的規范標準[1-8]。這類數理邏輯工具為現代信息和知識產業建立起堅實基礎,為先進的電腦和網絡技術大規模普及發展做出了實質貢獻[1-13]。從形式化邏輯發展的角度,0-1邏輯體系奠定的數理邏輯基礎[1-6],推動了當今世界先進科學技術發展的輝煌成就[1-13]。

在復雜性科學[16-20]中元胞自動機模型[16-23]利用邏輯函數遞歸處理方法,對動態圖像變化模式進行深入探討。在Wolfram開創的“新一代科學”系列研究[24-26]中,除了按照順序編號觀察遞歸函數的復雜動態特性之外,研究焦點在探尋單個函數反復迭代操作下可能出現的不同圖像變化輸出模式[16-27]。

離散邏輯函數空間的隨機組合帶來非規范特性,不同的表示結構對應的變換空間具有內蘊的非數值化特征和巨大組合數目。對整體邏輯配置函數空間進行研究是一類高難度系統探索性問題[16-21,28-32]。

由于缺乏合適的基本原理、模型方法和輔助工具,整體化變換群結構和組織的特性有待于深入研究。利用文獻[40-44]中對規則化平面格黑白圖像基礎和應用研究,提出基本的組織原理和方法。利用多變量0-1序列,從整體編碼角度針對變值體系結構等價性和對稱性方面進行分析[38-39]。

利用廣義和文王等編碼系列,形成高維系統分析工具框架,對多變量函數群集提供展示環境。

論文第一章給出基礎定義和變值基元的不變特征,第二章對n元邏輯變量建立配置函數空間,引入兩類擴展算符：向量化置換運算和互補運算模式。定義了廣義編碼結構和2維編碼表示系列。在第三章和第四章中,應用基元向量結構和變值編碼系列,對單個和兩個0-1變量的邏輯函數空間進行展示;在第五章中總結所建立的模型和方法。

1 基本定義

1.1 N元0-1序列

令 x=xn-1…xi…x0,0≤i＜n為n元 0-1變量,記 k為指定的關聯位置0≤k＜n,輸出變量y,n變量函數f,y=f(x),xi,y∈B2={0,1},x∈B={0,1}n

例如：X=01101110,Y=11000111為長度為 N=8的1維0-1序列。最右側為第0位,最左側為第7位。

1.2 在邏輯變換中的變值特性

令n元變量序列中的第k個位置為關聯位置,在N元序列中,該位置為當前位j,所選定的位置在后繼處理中有特殊重要性。

對任意的邏輯變量,在選定了函數之后關聯位置形成Xj→Yj點-點對應位置關系。即該模式由當前輸入狀態和函數輸出狀態之間建立的關系。

由于關聯位置1-1對應取值為 0-1,輸入/輸出值共有 4類基元變化模式：A：0→0,B：0→1,C：1→0,D：1→1 4類模式,利用變值基元可以建立起更為靈活的表達方式。

例如：邏輯代數的標準范式最大項(1點：B和D類)和最小項(0點：A和C類)傳統邏輯析取及合取范式函數是通過選擇最大項(1點)或者最小項(0點)集合來決定[1-6],4類變值基元模式以更為豐富的表達形式構成函數方程。

從元胞自動機的角度,當前的輸入狀態和輸出狀態是相互關聯的。該類關系決定變化基元本身在函數空間中的內蘊特性。

在4類變值模式中,第B和C類對應變值群集;而A和D類對應不變值群集。

2 n元變量狀態空間和配置函數空間

N長0-1序列在環轉連接下,利用給定位置k的n元變量模式進行操作。

2.1 n元變量和基元狀態

令N長0-1序列為環狀結構,以忽略序列邊界效應,對任意的整數 n,k;0≤k＜n,0＜n≤N,n為變量數目,k為關聯點距離最右位的偏移量。隨著關聯點位置的變動,n元變量在環上對應移動。

輸入輸出變量的關聯狀態：

n個輸入變量形成一個狀態,每個變量取值為0-1,共有2n個狀態形成狀態空間。

可區分的狀態空間在表1中示意。

表1 基元向量及其狀態編號

n變元獨立取值,共有2n可區分狀態,每個狀態編號 I數值的0-1取值對應著一個給定的n元狀態向量。第I個基元向量,在系統中2n基元向量形成基元向量空間。

函數空間及表示向量

記J=J2n-1…Jj…J0,0≤j＜2n,Jj∈B2,為長度為2n位的函數向量,每個函數向量 J確定一個邏輯函數,共有向量構成函數空間在表2中示意。

表2 函數向量及其函數編號

2.2 順序編碼-邵雍-Leibniz編碼

在公元11世紀,邵雍首先提出按二叉樹形成的順序排列黑白圖像表示方法[33-37]。在公元17世紀,Leibniz使用0-1序列將樹狀黑白圖像模式表示成二進制算術表示[15,32]。

定義2.2.1：邵雍-Leibniz編碼(SL碼)為函數表中按二進制編號順序排列的序列

證明：按照二進制計數的模式,在每個編號向量中1值對應最大項,0值對應最小項。所選擇的編號值集合和函數形成1-1對應關系。

2.3 1維編碼-廣義編碼和配置函數空間

記Ωm為m元對稱置換群結構。

令P為置換算符,

定理2.3.1：在置換算符P的作用下,所有的可區分的2n!置換函數向量組成一個邏輯函數向量置換群空間。

證明：置換算符作用在特征向量上,向量共有2n不同位置,第0個位置有2n種選擇,…,第 j位置有2n-j種選擇,…,第2n-2位置有2種選擇,第2n-1位置僅有1種選擇方式。可能的總數目為各個位置選擇數目的乘積。

對每個基元向量的位置可以選擇原來的值,或者為相反的值。定義互補運算Q,在向量的模式下,令Q為一個2n長0-1向量,P(J)Q=P(J2n-1)Q2n-1…P(Jj)Qj…P(J0)Q0

為方便描述,在P和Q兩類算符作用下形成的空間稱為配置函數空間,一個選定的P和Q算符確定一個配置函數,每個配置函數包含按廣義編碼排列的個函數。

定義2.3.2：廣義編碼(G碼)是由P和Q算符對2n位長向量J作用后,形成的配置編碼模式。

定理2.3.3：在P和Q兩類算符作用下,廣義編碼P(J)Q所包含的可區分配置函數數目為

證明：對每個互補運算j,Qj有兩種選擇,Q的選擇總數為;對置換算符基元向量在P算符的作用下形成2n!置換群,總數目為二者的乘積。

廣義編碼配置函數的數目為n元邏輯互補空間的算符數目與2n個基元置換對稱群算符數目的乘積。

2.4 二維編碼

廣義編碼,在P,Q變換下所形成的編號還是22n向量的一個置換,在配置函數變換空間中存在置換,將其重排為與SL編碼對應的順序編號模式。

為方便地描述2維結構,

令P(J)Q=P〈J1|J0〉Q形成二維編碼。

公元前13世紀,周文王(姬昌)首先引入了非對稱排列,將八卦圖示表示為兩個置換群集[33-37]。用文王命名這類形成二維表示的編碼結構。

定義2.4.1：文王碼(W 碼)為滿足 P(J)Q=P〈J1|J0〉Q條件,形成的通用型二維編碼。

定理2.4.2：文王編碼等價于廣義編碼,文王編碼提供一個2維平面框架顯示選定的配置函數中各個函數的相對位置。

證明：每個廣義編碼的編號能寫為〈J1|J0〉文王編碼的標準形式,在表3中每個邏輯函數在配置函數表示空間中有一個確定的位置,

表3 2維展示框架

通過文王碼的兩個子編號,將函數集展示在2維平面上。

表4 n=1廣義編碼和文王編碼序列

二維廣義編碼排列為：

如何才能激發學生學習的愿望，教師在設計練習時要充分考慮兒童的心理特點，教師結合學生已有知識盡量使練習設計新穎，生動有趣，只有有趣的練習，才能調動學生做練習的積極性。

序3 0 1 1 0序2 2 3序1 3 2序0 2 3 3 2 0 1 1 0序7 0 2 2 0序6 1 3序5 3 1序4 1 3 3 1 0 2 2 0

8個二維表不同函數排列：

序3 0 ˉxˉx 0序2 x 1序1 1 x序0 x 1 1 x 0 ˉxˉx 0序7 0 x x 0序6ˉx 1序5 1 ˉx序4ˉx 1 1 ˉx 0 x x 0

置換和互補運算不會改變函數本身,但將不同的配置函數排列成可區分的結構。這樣不變特性為整體分析提供分析比較圖式。

2.5 伏羲編碼和共軛編碼

公元前45世紀,伏羲排出對稱編排的八卦模式[33-37],用伏羲命名這類配對的對稱編碼。

定義2.5.1：對2維文王編碼,如果?j1-2n-1=j0,0≤j0＜2n-1,2n-1≤j1＜2n同時Ij1=ˉIj0,即兩個相差2n-1的基元按照配對的模式排列互為互補向量表示,則該類編碼為伏羲編碼(F碼),也稱為廣義共軛編碼(GC碼)。

如果還有更強地約束基元配對,則形成另一類編碼。

定義2.5.2：在伏羲編碼系列中,如果對?Ij0∈IJ0,對基元特定的位置i,,(或者?Ii=1),0≤i＜2n-1,則該類編碼為共軛編碼(C碼)。

在配對條件下的兩種編碼有如下定理。

定理2.5.4：對n元變量結構,C碼的數目是8×(2n-1)!

證明：基元向量互補算符Q共有4種可能性。由于置換算符P前一半的基元同后一半的基元有配對要求,同時對基元特定的位置i,?Ii∈Ij0&Ii=0,(或者?Ii=1)0≤i＜n,一共有!組合。兩類算符相互獨立,編碼總數為兩者數目的乘積。

2.6 幾種編碼方案比較

為了比較不同的編碼系列,在表5中列出主要編碼和計算公式。以判斷編碼的整體特性。

表5 不同編碼計算公式比較

在單個變元的條件下,8個G-W碼序列也是F-GC碼和C碼序列。

隨著變元數目超幾何級數增長,詳細研究只可能針個例,不能進行窮舉性遍歷。

在下面的章節中,研究單變量和雙變量的配置函數空間展示分布情況。

3 單變量和雙變量的表示結構

3.1 基本模式

對單變量函數,

單元函數為1-1變換關系,按照公式

對輸入變量在輸入向量上求值,得到函數的輸出序列。

對雙變量函數,將首尾銜接成環狀,由于變換的非對稱性有兩種變換模式：

類型A：

或者

類型B：

或者

3.2 單變量配置函數空間

從邏輯代數的角度,單變量函數是最基本的函數。函數空間表示如下：令 x為邏輯變量x∈{0,1}

在一元邏輯函數空間中有4個函數,編號為0-3。在單變量下,各類編碼都是相同的,考察SL碼和C碼的編號排列。

3.3 單變量函數的SL編碼和C編碼表示

對單變量函數,用如下的規則構造其表示空間：

(1)將狀態空間分為兩個集合：0,1;

(2)按照選擇及不選擇,在函數空間中建立關系;

(3)在狀態集合1,0上,互補10,01集合在〈J1|J0〉模式中標記為編號;

(4)記 f(〈J1|J0〉|x)的基本結構〈J1|J0〉為選擇的變值函數表示：

y=f x x ˉx 10 01 〈J1|J0〉 C碼編號 等價函數 SL碼編號f0(x)=f00(x)0 0 1 0 〈1|0〉 2 0 0 f1(x)=f01(x)0 1 1 1 〈1|1〉 3 ˉx 1 f2(x)=f10(x)1 0 0 0 〈0|0〉 0 x 2 f3(x)=f11(x)1 1 0 1 〈0|1〉 1 1 3

其他函數的等價特性關系,亦能通過選擇集合驗證。

3.4 共軛表示的定理和推論

從3.3節中可以看到,利用最大項或者最小項組合所構成的函數,與通過變值基元構成的函數是相互等價的。兩個配置函數空間具有同樣的大小,不同的編號和函數可以相互比較。

從基元變換群的角度,基元狀態形成變值基元。這樣的描述特征有利于克服經典系統適合表達靜態組合特性而缺乏動態描述功能的局限。

利用對應關系,得到等價性定理。

定理3.4.1：單變量邏輯函數空間和單變量變值函數空間的可區分函數總數為221=4。在兩個結構中的4個函數1-1對應。

證明：利用4個函數的對應關系,等價性成立。

在結構中形成的4個頂點有明確地意義。

推論3.4.2：在變值表示中,4個函數有如下的變換意義,

(1)f(〈0|1〉|x)保持{1}點狀態不變,轉化{0}點為1。對應邏輯代數的1函數;

(2)f(〈0|0〉|x)保持原有的值不變。對應原函數 x;

(3)f(〈1|1〉|x)將{0}點轉化為1值,同時將{1}點轉化為0值。對應邏輯代數的非函數ˉx;

(4)f(〈1|0〉|x)保持{0}點狀態不變,轉化{1}點為0值。對應0值函數。

證明：對1元邏輯函數,只有上述4種情況。

推論3.4.3：1元函數的函數空間同變值函數空間同構。

證明：在兩個結構中任意函數明確的1-1對應。

應用例子

對給定的0-1序列 X=01101110,8位長的二進制序列,1元共軛函數空間生成如下4種輸出序列：

4 雙變量的表示結構

對任意n變量,狀態數目為2n,函數空間數目為。在雙變量函數空間中共有16個函數。

4.1 A型雙變量表示

對A型模式,序列X,下列關系成立：

f x 0 1 z 0 1

雙變量 x,z一共有4種狀態組合：

16個函數的不同編碼在表6中示意。

對雙變量函數,用如下的規則表示：

(1)將zx的狀態空間根據x點取值為0或者1分為兩個集合：{0,2},{3,1};

(2)狀態集0：3;2：1是共軛對;

(3)由1(0)點狀態決定J1(J0)的集合;

(4)選擇狀態為1,不選擇為0,建立對應關系;

(5)〈J1|J0〉為變值表示：f(〈J1|J0〉|zx)

表6 1維排列SL C(類型A),F,G,W 各類表示

二維展示：

SL碼順序排列 SL碼函數分布

二維碼排列 F碼函數分布＜0,0＞ ＜0,1＞ ＜0,2＞ ＜0,3＞ x z+x ˉzx ˉzx+zˉx＜1,0＞ ＜1,1＞ ＜1,2＞ ＜1,3＞ zx z 0 zˉx＜2,0＞ ＜2,1＞ ＜2,2＞ ＜2,3＞ ˉz+x 1 ˉz ˉz+ˉx＜3,0＞ ＜3,1＞ ＜3,2＞ ＜3,3＞ zx+ˉzˉx z+ˉx ˉzˉx ˉx W碼函數分布 C碼函數分布x ˉz+x z+x 1 x z+x ˉz+x 1 zx zx+ˉzˉx z z+ˉx zx z zx+ˉzˉx z+ˉxˉzx ˉz ˉz x+zˉx ˉz+ˉx ˉzx ˉzx+zˉx ˉz ˉz+ˉx 0ˉzˉx zˉx ˉx 0 zˉx ˉzˉx ˉx

將得到的結果,總結為定理形式。

定理4.1.1：對多元變量等價變值函數集表示,SL編碼不同于C編碼的排列模式。

證明：觀察SL碼的基元向量,當變元數目大于1時。按順序排列的前一半和后一半向量通常不會滿足廣義共軛條件。

定理4.1.2：對任意的F編碼,按主對角線劃分,對應編號的函數為成對共軛函數。

證明：在F編碼條件下,任意選擇的編號〈J1|J0〉其在對角線另一側的編號是〈J0|J1〉。該編號是原向量集的共軛變量集合。

觀察上面例子中的F碼和C碼的函數分布,函數對滿足成對共軛關系。

定理4.1.3：對任意的C編碼,除了主對角線的共軛對稱性之外,4個頂點為：0,x,ˉx,1

證明：在上述4種情況中,x什么都不變自然保持輸入變元原狀態直接輸出;1函數將0點變為1,輸出1向量;0函數轉化1點為0,輸出0向量;ˉx把0點變為1,同時 1點變為0,輸出為原值求反。

4頂點不變性是C類編碼特有的空間結構特征。

定理4.1.4：在文王編碼中如果基元向量集無成對匹配,則其對應函數分布一般不出現共軛對稱效應。

證明：由于編碼規則的約束,非成對匹配形成非對稱排列。但可能在一些團體組合模式下以個例顯現共軛對稱性,定理的結論對大部分情況能夠成立。

觀察前面G碼的例子,盡管大多數函數對非共軛對稱,但是兩個頂點函數(0和1)仍保持共軛對稱。

5 結論

對多變量條件下利用傳統東方邏輯結構建立起現代化變值邏輯變換體系。利用變值基元向量,建立了整體編碼模型和系列化編碼展示結構。

定理4.1.1-4.1.4總結論文的主要結果。在新的編碼系列中,文王編碼具有通用二維結構。伏羲編碼在配置函數空間中形成共軛函數對。而共軛編碼,特有的四元極值頂點將其他的編號約束在內。

由于文王編碼系列具有超幾何級數增長的趨式,下一步的工作將集中在對較少量變元(2-4)的變換結構進行實際的模擬處理和窮舉型計算。同時應用該理論體系處理數學/物理的基礎悖論問題,為實際應用現代東方邏輯系統：變值邏輯體系開辟道路。

致謝：感謝已故的恩師高慶獅院士,高先生早在30年前就指導作者在對稱置換群上構造并行算法。感謝陳濤先生利用分層結構化模型建立的現代中醫輔助診斷系統,應用傳統中醫理論形成現代化成果激勵作者重返基礎邏輯研究前沿。感謝云南省特色專業建設基金和云南省軟件工程重點實驗室信息安全專項基金支持。

[1]楊炳儒.布爾代數及其泛化結構[M].北京：科學出版社,2008.

[2]S P Vingron.Switching Theory：Insight Through Predicate Logic[M].Springer,2004.

[3]秦軍南.開關理論與邏輯設計[M].北京：人民教育出版社,1980.

[4]Saburo Muroga.Logic Design and Switching Theory[M].Wiley-Interscience Publication,1979.

[5]A Kandel,Samuel C Lee.Fuzzy Switching and Automata：Theory and Applications[M].Crane Russak&Company Inc,1979.

[6]Samuel C Lee.Modern Switching Theory and Digital Design[M].Prentice-Hall Inc,1978.

[7]F H Edwards.The Principles of Switching Circuits[M].MIT Press,1973.

[8]霍書全.多值邏輯的方法和理論[M].北京：科學出版社,2009.

[9]石純一.數理邏輯與集合論(第二版)[M].北京：清華大學出版社,2000.

[10]胡世華,陸鐘萬.數理邏輯基礎[M].北京：科學出版社,1981.

[11]金岳霖.形式邏輯[M].北京：人民出版社,1979.

[12]數理邏輯論文選：第一集,1958.

[13]A B Rosser,A R Turquette.Many-valued Logics[M].North-Holland Publishing Company,1952.

[14]桑靖宇.萊布尼茲與現象學[M].北京：中國社會科學出版社,2009.

[15]閻莉.整體論視域中的科學模型觀[M].北京：科學出版社,2008.

[16]雷功炎.數學模型八講[M].北京：北京大學出版社,2008.

[17]宣慧玉,張發.復雜系統仿真及其應用[M].北京：清華大學出版社,2008.

[18]李士勇.非線性科學與復雜性科學[M].哈爾濱：哈爾濱工業大學出版社,2006.

[19]涂序彥,尹怡欣.人工生命及應用[M].北京：北京郵電大學出版社,2004.

[20]H Umeo,S Morishita,K Nishinari.Cellular Automata[M].Springer,2008.

[21]江志松.122號初等元胞自動機的復雜性分析[J].科學通報,2000,45(18)：2007-2012.

[22]D Griffeath,C Moor.New Constructions in Cellular Automata[C].Santa Fe Institute Studies in the Sciences of Complexity,2003.

[23]A Ilachinski.Cellular Automata-A Discrete Universe[M].World Scientific,2001.

[24]S Wolfram.A New Kind of Science[EB/OL].http：//www.wolframscience.com,2002.

[25]S Wolfram.Cellular Automata and Complexity.Addison-Wesley,1994.

[26]S Wolfram.Theory and Applications of Cellular Automata.World Scientific,1986.

[27]李元香.格子氣體自動機[M].北京：清華大學出版社,1994.

[28]金日光.模糊群子論[M].哈爾濱：黑龍江科學技術出版社,1985.

[29]Wiktor Marek etc.Elements of Logic and Foundations of Mathematics in Problems[M].PWN-Polish Scientific Publishers,1982.

[30]A Thayse.Boolean Calculus of Differences[M].Springer-Verlag,1981.

[31]J Fogarty.Invariant Theory[M].W.A.Benjamin,Inc.,1969.

[32]Paul Benacerraf and Hilary Putnam[M].Philosophy of Mathematics Prentice-Hall Inc.,1964.

[33]互子.易道中互-易經體系[M].廣州：花城出版社,2009.

[34]徐芹庭.易圖源流[M].廣州：中國書店,2008.

[35]黃宗羲.易學象數論[M].北京：九州出版社,2007.

[36]張一方.中華歷代易學家傳[M].北京：北京藝術與科學電子出版社,2007.

[37]施維.周易八卦圖解[M].成都：巴蜀書店,2005.

[38]Zheng Jeffrey,Zheng Chris,Kunii T L.A Framework of Variant-Logic Construction for Cellular Automata,Cellular Automata-Innovative Modelling for Science and Engineering[M].InTech Press,2011：325-352.

[39]Zheng Jeffrey,Zheng Chris.A framework to express variant and invariant functional spaces for binary logic[J].Frontiers of Electrical and Electronic Engineering in China,2010,5(2)：163-172.

[40]Z J Zheng.Conjugate Visualisation of Global Complex Behaviour[J].Complexity International,1996,(3).

[41]Z J Zheng,C H C Leung.Visualising Global Behaviour of 1D Cellular Automata Image Sequences in 2D Maps[J].Physica A,1996,233：785-800.

[42]Z J Zheng.Conjugate Transformation of Regular Plan Lattices for Binary Images[D].PhD Thesis,Monash University,1994.

[43]Z J Zheng,A J Maeder.The Elementary Equation of the Conjugate Transformation for Hexagonal Grid[J].Modeling in Computer Graphics,1993：21-42.

[44]Z J Zheng,A J Maeder.The Conjugate Classification of the Kernel Form of the Hexagonal Grid[J].Modern Geometric Computing for Visualization,1992：73-89.