多值邏輯電路的研究進展

多值邏輯電路的研究進展

1值邏輯電路的提出1921年，美國邏輯學(xué)者r.f.首次提出了一種完整的多值邏輯序列系統(tǒng)，該系統(tǒng)具有完整的功能，自20世紀70年代初以來，多值邏輯的研究已引起國際計算機學(xué)術(shù)界的關(guān)注。但多值邏輯在電子科學(xué)技術(shù)和計算機科學(xué)技術(shù)中的應(yīng)用,目前還遠沒有二值邏輯那么普遍,這是由于多值邏輯電路的復(fù)雜性和電路實現(xiàn)的困難性。然而,自然界中許多事物之間存在著多值的邏輯問題,例如電機的狀態(tài)有“正傳”、“停止”和“反轉(zhuǎn)”,一個系統(tǒng)的狀態(tài)有“正?！?、“異?！焙汀肮收稀?選舉投票有“同意”、“棄權(quán)”和“反對”等。多值邏輯的各種狀態(tài)可以用不同的電壓或電流來表示,也可以用DNA分子的各種狀態(tài)來表示。1994年,美國南加州大學(xué)的Adleman博士通過DNA的生化實驗,解決了有向圖的哈密爾頓路問題(HPP),開創(chuàng)了DNA分子計算的新紀元。目前,人們在研究NP-完全問題的DNA計算模型的同時,也在開始探索新的潛在的應(yīng)用。構(gòu)建基于DNA分子的邏輯電路就是其中一個研究方向。例如2004年,劉文斌等提出了一個基于吡啶二聚物的誘導(dǎo)發(fā)夾結(jié)構(gòu)的邏輯“與非”門的DNA計算模型。本文通過一種特定發(fā)夾結(jié)構(gòu)的DNA分子來表示三值邏輯值,并完成三值邏輯“與”和“或”的邏輯運算和輸出過程。數(shù)學(xué)上已經(jīng)證明,任何一個布爾電路都可以在多項式時間轉(zhuǎn)化為標準的層狀結(jié)構(gòu),并且同一層中的邏輯門均為相同形式,“與”陣列和“或”陣列是常用的邏輯陣列。衡量布爾電路規(guī)模通常的兩個指標為:電路中所包含的邏輯門的數(shù)目和電路中邏輯門的層數(shù),對于多值邏輯電路也是一樣的。圖1給出了一個由與門(AND)和或門(OR)組成的3層邏輯電路的示意圖。顯然,由于DNA分子巨大的并行性,用DNA分子來構(gòu)成多值邏輯的陣列電路是有顯著意義的。2值邏輯“與”和“或”邏輯運算三值邏輯是最簡單的多值邏輯,也是最重要的多值邏輯系統(tǒng),通過三值邏輯系統(tǒng)可以更深入地了解多值邏輯系統(tǒng)的理論與應(yīng)用。多值邏輯理論體系眾多,目前主要有Post代數(shù)、Vranesic-Lee-Smith代數(shù)、Allen-Givone代數(shù)、模代數(shù)、T門算子代數(shù)和對稱三值代數(shù)等。下面討論三值邏輯的“與”和“或”邏輯運算。設(shè)L={0,1,2}是三值邏輯的值集合,x,y∈L,定義:(1)“與”運算(取小)x∧y=min(x,y)(2)“或”運算(取大)x∨y=max(x,y)三值邏輯的“與”和“或”運算結(jié)果見真值表1和真值表2。3“發(fā)夾”的應(yīng)用發(fā)夾結(jié)構(gòu)是一種在DNA分子或RNA分子中經(jīng)常出現(xiàn)的二級結(jié)構(gòu),當(dāng)DNA分子或RNA分子上存在相互互補的序列,在適當(dāng)?shù)臈l件下它們就會雜交從而形成發(fā)夾結(jié)構(gòu)。盡管在DNA計算中我們希望盡量避免“發(fā)夾”結(jié)構(gòu)的產(chǎn)生,但是通過精心設(shè)計的發(fā)夾結(jié)構(gòu)卻有很多特殊的應(yīng)用,如文的與非門計算模型,文的可滿足問題的計算模型。此外,由于“發(fā)夾”具有結(jié)構(gòu)簡單,易于控制等優(yōu)點,已經(jīng)廣泛地應(yīng)用于生物傳感器和分子的自組裝等方面。多發(fā)夾結(jié)構(gòu)如圖2所示,由兩條不完全匹配的DNA鏈部分雜交,從而形成多發(fā)夾結(jié)構(gòu)。兩條DNA鏈分別由五部分組成,短鏈由“A,B,C,D,E”組成,長鏈由“A’,B’,C’,D’,E’”組成。其中“A,C,E”和“A’,C’,E’”完全匹配,“B,D”和“B’,D’”不匹配,“B’,D’”的長度比“B,D”長,“B,D”和“B’,D’”之間有足夠大的移位距離。為了保證三值邏輯電路的實現(xiàn),長鏈和短鏈的五個部分分別設(shè)計不同的長度。其中,“A,A’,B”部分最短,都為5mer,“B’,D”為10mer,“C,C’”為15mer,“D’”為20mer,“E,E’”為25mer。當(dāng)長鏈和短鏈的末端一起固定在表面上,兩條DNA鏈就會形成如圖2的雙發(fā)夾結(jié)構(gòu),其中“B’”部分形成的發(fā)夾叫小發(fā)夾,“D’”部分形成的發(fā)夾叫大發(fā)夾。4三個值邏輯電路中的dna分子的實現(xiàn)4.1單個大發(fā)夾階段20d要實現(xiàn)多值邏輯運算,首先要確定多值邏輯值的表示方法。圖3是用DNA分子的多發(fā)夾結(jié)構(gòu)的三種狀態(tài)表示三值邏輯值。具體的表示方法如下:(1)當(dāng)固定在表面上的長短雙鏈的“A,C,E”和“A’,C’,E’”雜交形成氫鍵而相對固定,而“B,D”和“B’,D’”不匹配無法雜交,形成兩個大小發(fā)夾,此時表示邏輯值“0”;(2)表面上的長短雙鏈處于大小發(fā)夾狀態(tài)時,溶液中加入“B’”的補鏈“ˉB′B′ˉˉˉˉ”,經(jīng)適當(dāng)加熱解鏈操作和退火操作,此時“B’”和“ˉB′B′ˉˉˉˉ”雜交形成雙鏈,由于“B’”和“ˉB′B′ˉˉˉˉ”雜交的化學(xué)自由能變化要遠大于“A”和“A’”雜交的化學(xué)自由能變化,因此“B’”和“ˉB′B′ˉˉˉˉ”雜交時就將“A”和“A’”解鏈。另外,由于“C,E”和“C’,E’”雜交的化學(xué)自由能變化要大于“B’”和“ˉB′B′ˉˉˉˉ”雜交的化學(xué)自由能變化,因此“C,E”和“C’,E’”不會解鏈,仍然以雜交形式存在。這樣就形成了單個大發(fā)夾,此時表示邏輯值“1”;(3)長短雙鏈處于大小發(fā)夾狀態(tài)或單大發(fā)夾狀態(tài)時,加入“B’,D’”的補鏈“ˉB′?ˉD′B′ˉˉˉˉ?D′ˉˉˉˉ”,經(jīng)解鏈和退火后,“B’,D’”和“ˉB′?ˉD′B′ˉˉˉˉ?D′ˉˉˉˉ”分別雜交形成雙鏈,而且有足夠大的化學(xué)自由能變化來解開“A,C”和“A’,C’”雙鏈結(jié)構(gòu),但“E”和“E’”仍然雜交。此時大小發(fā)夾均不存在,用來表示邏輯值“2”。4.2“和”和“或”的操作1.發(fā)夾中,把“或”邏輯關(guān)系轉(zhuǎn)化為雙發(fā)面,保證執(zhí)法力度,并將其作為保證一個照表面質(zhì)量表。請看“或”運算中的一個輸入變量X,X=x,x∈{0,1,2},邏輯變量X的取值由4.1節(jié)中圖3的方法來表示,運算結(jié)果F=X∨Y的邏輯值也同樣表示。另一個輸入變量Y,Y=y,y∈{0,1,2},變量Y邏輯值用各種補鏈來表示,定義為:(1)溶液中加入“B’,D’”的補鏈“ˉB′?ˉD′B′ˉˉˉˉ?D′ˉˉˉˉ”,表示邏輯值“2”;(2)僅加入“B’”的補鏈“ˉB′B′ˉˉˉˉ”,表示邏輯值“1”;(3)溶液中不加入任何DNA鏈,表示邏輯值“0”。這樣,“或”邏輯運算X∨Y就容易實現(xiàn),對照表2“或”運算真值表,運算操作如下:(1)當(dāng)X=0時,固定在表面上的長短雙鏈呈雙發(fā)夾狀態(tài),溶液中加入“ˉB′?ˉD′”(Y=2),經(jīng)適當(dāng)解鏈操作和退火操作,大小發(fā)夾都被打開,運算結(jié)果表示為邏輯值“2”,從而實現(xiàn)0∨2=2。當(dāng)往雙發(fā)夾狀態(tài)(X=0)的溶液中加入“ˉB′”(Y=1),經(jīng)解鏈和退火后,小發(fā)夾被打開,大發(fā)夾不變,運算結(jié)果表示為邏輯值“1”,從而實現(xiàn)0∨1=1,見圖4。如果初始溶液中不加入任何DNA鏈,經(jīng)解鏈和退火后,顯然長短雙鏈仍呈雙發(fā)夾狀態(tài),從而實現(xiàn)0∨0=0;(2)當(dāng)X=1時,表面上的長短雙鏈呈單大發(fā)夾狀態(tài),如果往溶液中加入“ˉB′?ˉD′”(Y=2),經(jīng)解鏈和退火后大發(fā)夾被打開,運算結(jié)果表示為邏輯值“2”,實現(xiàn)1∨2=2。如果溶液中加入“ˉB′”(Y=1)或者不加入任何DNA鏈,經(jīng)解鏈和退火后,長短雙鏈狀態(tài)不會改變,實現(xiàn)1∨1=1和1∨0=1,見圖5;(3)當(dāng)X=2時,長短雙鏈在溶液中均不存在大小發(fā)夾,無論往溶液中加入“ˉB′?ˉD′”(Y=2)、“ˉB′”(Y=1)或不加入任何東西(Y=0),長短雙鏈狀態(tài)不會因解鏈和退火操作而改變,即實現(xiàn)2∨2=2、2∨1=2和2∨0=2。2.大小雙發(fā)夾組合“與”運算中的輸入變量X和運算結(jié)果的邏輯值F=X∧Y同樣由4.1節(jié)中圖3的方法來表示。輸入變量Y邏輯值定義為:(1)溶液中加入“B’,D’”段的DNA鏈,表示邏輯值“0”;(2)僅加入“D’”段的DNA鏈,表示邏輯值“1”;(3)溶液中不加入任何DNA鏈,表示邏輯值“2”。這樣,邏輯運算x∧y同樣有如下操作如下:(1)當(dāng)X=2時,在表面上的長短雙鏈無發(fā)夾狀態(tài),如果溶液中加入“B’,D’”段的DNA鏈(Y=0),經(jīng)加熱解鏈,“B’,D’”和“ˉB′?ˉD′”形成的雙鏈也解開。然而在退火操作過程中,解鏈的“ˉB′?ˉD′”段DNA鏈與加入的“B’,D’”段DNA鏈相互匹配而雜交形成獨立的雙鏈,游離于溶液中。同時,固定在表面的長鏈失去了與“,”段DNA鏈雜交的機會,于是和附近表面的短鏈雜交,形成大小發(fā)夾狀,從而實現(xiàn)2∧0=0。如果溶液中加入“D’”(Y=1),經(jīng)加熱解鏈后,在退火操作過程中,解鏈的“ˉD′”段DNA鏈與加入的“D’”段DNA鏈雜交形成游離的雙鏈。同時,固定在表面的長鏈失去了與“ˉD′”段DNA鏈雜交的機會,但仍和“ˉB′”段DNA鏈雜交,于是在和附近表面的短鏈雜交時,就形成單大發(fā)夾狀,實現(xiàn)2∧1,見圖6。顯然,如果溶液中不加入任何DNA鏈,則解鏈退火后,表面上的長短雙鏈仍處于無發(fā)夾狀態(tài),從而實現(xiàn)2∧2=2;(2)當(dāng)X=1時,表面上的長短雙鏈呈單大發(fā)夾狀態(tài),如果溶液中加入“B’,D’”段的DNA鏈(Y=0),經(jīng)加熱解鏈,大發(fā)夾打開,同時“B’”和“ˉB′”形成的雙鏈也解開,然而在退火操作過程中,解鏈的“ˉB′”段與加入的“B’”段DNA鏈雜交形成游離的雙鏈。同時,固定在表面的長鏈失去了與“ˉB′”段DNA鏈雜交的機會,而溶液中也無“ˉD′”段DNA鏈,于是和附近表面的短鏈雜交,形成大小發(fā)夾狀,從而實現(xiàn)1∧0=0。如果溶液中加入“D’”(Y=1),經(jīng)加熱解鏈后,在退火操作過程中,解鏈的“ˉB′”段仍和固定在表面的長鏈“B’”段雜交,表面上的長短雙鏈雜交后,呈單大發(fā)夾狀態(tài)仍形成單大發(fā)夾狀,實現(xiàn)1∧1=1,見圖7。顯然,如果溶液中不加入任何DNA鏈,則解鏈退火后,表面上的長短雙鏈仍保持原來狀態(tài),從而實現(xiàn)1∧2=1;(3)當(dāng)X=0時,表面上的長短雙鏈呈大小雙發(fā)夾狀態(tài),無論往溶液中加入“B’,D’”(Y=0)、“D’”(Y=1)或不加入任何東西(Y=2),因為溶液無“ˉB′?ˉD′”段DNA鏈,表面上的長短雙鏈狀態(tài)解鏈和退火操作仍形成大小雙發(fā)夾結(jié)構(gòu),即實現(xiàn)0∧2=0、0∧1=0和0∧0=0。為了避免“與”運算的生物操作中的雜交競爭,保證解鏈后的補鏈“ˉB′?ˉD′”要優(yōu)先與表示變量Y的“B’,D’”段DNA鏈雜交,需要在解鏈后將表面和溶液暫時分離,使溶液中只剩下補鏈“ˉB′?ˉD′”,然后往溶液中加入表示變量Y的“B’,D’”段DNA鏈,使補鏈“ˉB′?ˉD′”與其優(yōu)先雜交,然后再將表面浸入溶液中,使沒雜交的補鏈“ˉB′?ˉD′”與固定在表面上長鏈的“B’,D’”段雜交。3.值邏輯電路模型的建立運算結(jié)果的輸出非常關(guān)鍵,不僅表示本級邏輯電路的輸出信息,而且也是用于下一級邏輯電路的輸入信息。上述邏輯電路運算結(jié)果的輸出很簡單,加熱表面上的長短雙鏈使之解鏈,游離出的“ˉB′?ˉD′”段DNA鏈就是運算結(jié)果的輸出。顯然,運算結(jié)果輸出邏輯值表示同“或”運算的輸入變量Y的表示是一樣的,也就是說,運算結(jié)果的輸出可以直接作為下一級“或門”電路的輸入。但是對于“與門”輸入電路,運算結(jié)果的輸出需要一次雜交移除(求補)轉(zhuǎn)化后才能作為輸入信號。比較運算結(jié)果和“與”運算的輸入信號Y的DNA編碼表示,可知運算結(jié)果和“或”運算輸入信號Y均由長鏈“B’,D’”的補鏈“ˉB′?ˉD′”來表示,“與”運算輸入信號Y由長鏈“B’,D’”段DNA鏈來表示,兩者的表示剛好互補?？梢?運算結(jié)果輸出可以正確地傳遞給下一級門電路信號Y的輸入。那么,運算結(jié)果又是如何傳遞給下一級門電路信號X的輸入是我們要解決的問題。這里只需要增加一次“或”運算X=0∨F即可,邏輯值“0”是非常容易實現(xiàn)的,就是初始化的狀態(tài)。不難發(fā)現(xiàn),如果下一級運算是“或”運算,則傳遞給輸入信號X和Y的溶液可以直接混合,無需單獨進行輸入信號X的傳遞過程。所以,用多發(fā)夾結(jié)構(gòu)的DNA分子表示的多值邏輯電路,采用“與-或”邏輯結(jié)構(gòu),是最簡單的,不僅“與”門運算結(jié)果的輸出無需求補轉(zhuǎn)化,而且“或”門的所有輸入信號都可以同時傳遞。本文首次給出了一個基于DNA分子計算的三值邏輯電路模型,闡述了“與”、“或”運算的生物實