唐益明， 劉曉平

（1. 合肥工業(yè)大學信息與通訊工程博士后科研流動站，安徽 合肥 230009；2. 合肥工業(yè)大學計算機與信息學院，安徽 合肥 230009）

與或功能樹的無損簡化方法

唐益明1,2， 劉曉平2

（1. 合肥工業(yè)大學信息與通訊工程博士后科研流動站，安徽 合肥 230009；2. 合肥工業(yè)大學計算機與信息學院，安徽 合肥 230009）

當前概念設計中較大規(guī)模功能樹存在解空間龐大、沖突定位困難的問題，對此提出基于與或功能樹的無損簡化方法。證明了無損收縮簡化、無損刪除簡化、無損提取簡化的相關定理，并籍此給出與或功能樹的無損簡化算法。最后通過實例，證明該算法可在保持邏輯等價和創(chuàng)新能力不損失的前提下有效降低問題的復雜度，從而提高了概念設計的效率。

計算機應用；概念設計；無損簡化；與或功能樹

產品設計是一個復雜的創(chuàng)造性生產過程，其中概念設計是產品設計過程中最初的也是最具創(chuàng)造性的階段[1-2]。而“功能”這個概念貫穿概念設計的各個階段，它是概念設計的最基本元素[3-4]。一般概念設計主要可以劃分成兩個階段：第一，功能分析，確定某個抽象層次的功能，分解功能，建立功能樹和功能結構，這里往往也涉及功能樹的優(yōu)化（比如簡化）問題；第二，功能求解，對每個分功能進行求解，得到分功能原理解，并組合形成設計方案。

與或非功能樹是一種應用廣泛的功能分析方法。文獻[5]中建立了需求域-功能域-原理解域循環(huán)映射的概念設計模型，并提出了概念設計與/或樹形式化表達方法。文獻[6]中將行為域引入到公理化設計，采用功能-行為-載體（結構）的域結構模板，并通過功能層、行為層、載體層交替出現(xiàn)的與或功能樹來實現(xiàn)。文獻[7]中提到基于公理化設計，將功能域向結構域的曲折映射表示為產品結構樹，只是該樹僅涉及到“與”分解。作者在文獻[8]中針對與或功能樹，基于布爾代數(shù)理論提出了一種基于功能集族的功能求解方法。文獻[9]基于相似理論和可拓學理論，針對與、或、非分解的功能樹進行相似擴展研究。

功能樹的方案數(shù)通常通過組合原理來獲得[10]。但對于規(guī)模較大的功能樹，其結構的復雜性就難以讓設計者理清頭緒，而且其功能的實現(xiàn)方案數(shù)往往較龐大，導致很難準確尋找出最優(yōu)解；同時，作為概念設計的本質，創(chuàng)新推理的主要難點在于沖突的檢測、定位與消解[11-13]。但對于規(guī)模較大的功能樹，組合求解所得到的龐大解空間，使得設計者很難迅速發(fā)現(xiàn)并定位沖突所在，更難以消解沖突。因此，如果能對功能樹進行簡化，將其中的冗余去除，使得樹的規(guī)模等價地減小，將會使得這一系列問題得到極大緩解。為此，作者在文獻[14]中利用布爾表達式和功能樹的特點，提出了基于布爾代數(shù)理論的與或功能樹的邏輯簡化策略。

但是，經過更深一步的研究，作者發(fā)現(xiàn)：利用布爾代數(shù)理論進行邏輯簡化會造成設計解空間的損失。具體而言，創(chuàng)新推理的設計解可以用簡單合取式[15]的形式來表示（如x1∧ x2∧ … ∧xk），而每一個布爾變量，就代表問題的一個原子解。因此，一旦損失布爾變量，就意味著損失了解決問題的一大批方法；甚至損失了最好的解。利用布爾代數(shù)來對功能樹進行邏輯簡化，有可能會造成解空間的損失。

為此，本文提出了無損簡化的思想。由于與或非功能樹的無損簡化極其復雜，因此本文僅針對與或功能樹的無損簡化問題進行研究。首先介紹與或功能樹的基本定義，然后給出了幾個無損簡化定理，并籍此給出與或功能樹的無損簡化算法，最后通過具體的實例，驗證了該方法的有效性。

1 與或功能樹的基本定義

與或功能樹可視為布爾代數(shù)理論的一種應用[11]?！芭c”門分解相當于“∧”，“或”門分解相當于“∨”。對于功能T，若按或門展開為 A1和A2，則有 T = A1∨ A2，即功能 A1或 A2實現(xiàn)，則有功能T實現(xiàn)，其余類似可得。為了方便，頂節(jié)點為 G1的與或功能樹記為 H(G1)。

定義1 對于與或功能樹 H(G1)中重復的葉子節(jié)點，稱其為基本變量，記為 xi。當基本變量 xi對應葉子節(jié)點的需求實現(xiàn)時 xi取1，否則取0。類似地，將功能樹中門節(jié)點用 Gj表示，稱為擴展變量?；咀兞亢蛿U展變量統(tǒng)稱為樹變量。H(G1)中出現(xiàn)的所有基本變量下標的集合，記為V(G1)。

定義 2 定義布爾函數(shù) φ( X) = φ(x1,…, xn,G1,… ,Gp)為與或功能樹 H(G1)的樹函數(shù)（ n,p分別為樹的基本變量數(shù)和擴展變量數(shù)），若功能樹對應總需求實現(xiàn)時φ ( X)取 1，否則取0。如果樹函數(shù)僅含有基本變量，則稱為目標樹函數(shù)。對功能樹自上而下，通過與、或展開，直至葉子節(jié)點，可得目標樹函數(shù)。

例1 圖1為與或功能樹的一個示例，其目標樹函數(shù)φ (X ) = φ(x1,…,x6,G1,…,G5)=G1= G2∨G3=(x1∧G4∧x2)∨(x4∧ G5)=[x1∧(x1∨x3)∧x2]∨[x4∧ (x5∨ x6)]。并且 V(G1)= {1,2,… , 6}。

圖1 功能樹示例

2 與或功能樹的無損簡化方法

2.1 無損簡化定理

定義3 設與或功能樹 H(G1)相應的V(G1)= {1,2,… ,n}，對 H(G1)基于布爾代數(shù)理論進行邏輯簡化后得到 H '(G1)，如果 H '(G1)對應的基本變量集合為 {x1,x2,… ,xn}，則稱此邏輯簡化為無損簡化。也稱 H'(G1)是 H(G1)的無損簡化。

定理 1 （無損收縮簡化） 以下操作均為無損簡化：

1） 如果相鄰兩層門類型相同，合并這兩個門為一個門。

2） 在同一個門的輸入中，合并相同的基本變量。

3） 如果一個門只有一個輸入，刪除這個門，其輸入上移。

證 明 第一，由 xi∨ (xj∨ xk)=xi∨xj∨xk，xi∧ (xj∧ xk)= xi∧ xj∧ xk，以及定義3，可得結論成立（此時基本變量集合顯然未發(fā)生變化）。第二，由 xi∨ xi= xi，xi∧ xi= xi，以及定義3，可知結論成立。第三，從功能樹的分解角度來看，不妨設為“與分解”，則父節(jié)點僅擴展為一個子節(jié)點，顯然父節(jié)點的邏輯狀態(tài)與子節(jié)點相同，此時刪除該門，并將輸入上移，對功能樹的邏輯結構沒有本質影響。由定義3，可得結論成立。證畢。

定義4 將功能樹的某節(jié)點 xi所在的層數(shù)記為L(xi)。規(guī)定頂節(jié)點 xi的層數(shù)為 L(xi)=1，且對于 xi的直接孩子節(jié)點 xj，有 L(xj) = L(xi)+1。依次類推，形成各層的層數(shù)。

定義 5 定義門變量 Gi的所有直接孩子節(jié)點序號構成的集合為門變量 Gi的展開，記為 Pi。如果 Gi的直接孩子節(jié)點中沒有重復的基本變量節(jié)點，Pi直接為 Gi孩子節(jié)點序號的集合；如果 Gi的直接孩子節(jié)點中有重復的基本變量節(jié)點，如有多個 xi，則將其依次編號為 i(1),i(2)等歸入 Pi中。

例 2 在圖1中，為了區(qū)分，令功能樹中第3層出現(xiàn)的 x1為 x1(1)，而第4層的 x1為 x1(2)。則L(G1)=1，L (G2) = L(G3)= 2，L (x1(1)) =L(G4) = L(x2)= 3。對于定義5，需要對門節(jié)點重新編號，比如 G1,G2,G3,G4,G5可依次重新編號為x7,x8,x9, x10,x11，則對于 G1，相應的P1= {8,9}；對于 G2，相應的 P2= {1,10,2}。

定義6 如果與或功能樹滿足如下特征：門的類型隔層相同，分別為“與—或—與—或—…”，或者為“或—與—或—與—…”，則稱為AND/OR樹。其中，按樹的頂節(jié)點為與門、或門，分別稱為AND-OR交錯樹、OR-AND交錯樹。

由定理1不難得到以下命題：

命題1 對于與或功能樹 H(G1)，對其進行無損收縮簡化后得到 H '(G1)，則 H '(G1)為AND/OR樹。

對于與或功能樹 H(G1)，對于其中的任一基本變量 xi,記 NG1(xi)為基本變量 xi的出現(xiàn)次數(shù)。

定理2 （無損刪除簡化1） 如果在AND/ OR樹的某個門 G1下有基本變量 xi，同時，在以G1為頂?shù)淖訕涞呐紨?shù)層上的某個門 G2下也有xi，即 L(G2) - L(G1) ≡ 1(mod2)，且 PG1∩PG2?{i}，若對 ?j ∈ V (G2)，有 NG2(xj)＜ NG1(xj)，則在刪除門 G2為頂?shù)淖訕浜螅玫降腍'(G1)是 H(G1)的無損簡化。

證 明 無妨設 H(G1)是AND-OR交錯樹，即 G1是個與門，令 k=L(G2) -L(G1)≡1(mod2)。為了方便，對某節(jié)點 Gi的或展開，可將 Pi對應的節(jié)點拆成兩個部分A和B，即 A∪B ={xj| j∈Pi}，令不致混淆時，可簡記為 TGi。同理，對 Gi的與展開令，簡記為 SGi。設 G1,Gt1,Gt2,…,Gtk-1,G2為展開后含 xi的自上而下的門序列，且

顯然，Gt1,Gt2,Gt3,…,Gtk-1,G2分別為或門、與門、或門、與門、…、與門、或門。

歸納法。當 k= 1時，有

注意到對 ?j∈ V(G2)，有NG2(xj) ＜ NG1(xj)，則在刪除門 G2為頂?shù)淖訕浜螅玫降?H '(G1)中的基本變量集合不變，由定義3可知結論成立?，F(xiàn)假設 k= L(G2) - L(G1)=2 ×n -1(n ≥1)時定理成立。則當 k = 2 × n+ 1時，有

現(xiàn)令 G3=xi∧ Gt3∧ SGt2({Gt3})，由于G3是Gt3的父節(jié)點，則有 L(G3) = L(Gt3)-1 = L(Gt2)，則L(G3)- L(G2)= 2 × n -1。則由假設，此時定理得證。至此，由歸納法可知，整個定理證明完成。證畢。

定理3 （無損刪除簡化2） 如果在AND/OR樹的某個門 G1下有基本變量 xi，同時，在以G1為頂?shù)淖訕涞钠鏀?shù)層上的某個門 G2下也有xi，即 L(G2)- L(G1) ≡ 0(mod2)，且 PG1∩PG2?{i}，則在刪除門 G2的孩子節(jié)點 xi后，得到的 H'(G1)是 H(G1)的無損簡化。

證 明 無妨設 H(G1)是AND-OR交錯樹，即 G1是個與門，令 k= L(G2)- L(G1)≡0 (mod2)。相關假設類似于定理 2。設G1,Gt1,Gt2,…,Gtk-1,G2為展開后含 xi的自上而下的門序列，并且

顯然，Gt1,Gt2,Gt3,…,Gtk-1,G2分別為或門、與門、或門、…、或門、與門。

歸納法。當 k= 2時，有

考察式(1)展開的全過程，注意到其中有且僅有一處吸收操作，其子操作為： xi∧ G2= xi∧(xi∧ SG2({xi} )) =xi∧ (SG2({xi}))，顯然刪除門G2的子節(jié)點 xi，對功能樹的邏輯結構沒有本質影響，并且基本變量集合未發(fā)生變化，由定義3可得此時定理得證。

現(xiàn)假設 k= L(G2)- L(G1)=2 ×n(n ≥1)時定理成立。則當 k=2 ×n+ 2(n ≥ 1)時，有

現(xiàn)令 G3=xi∧ Gt3∧ SGt2({Gt3})，由于G3是Gt3的父節(jié)點，則有 L(G3) = L(Gt3)-1 = L(Gt2)，則L(G3)- L(G2)= 2× n 。則由假設，定理得證。至此，由歸納法可知，整個定理證明完成。證畢。

定理4 （無損提取簡化） 在AND/OR樹中，相同基本變量處在同一層的若干個門中，則將該基本變量提取出來的操作是無損簡化。

證 明 令共同的幾個基本變量的下標集為P，無妨令 P= {1,2,… ,n}。再設展開后得到這幾個基本變量的門節(jié)點下標集為Q= {1,2,… ,m}。令這幾個門的父節(jié)點為G，無妨G為與門，則由AND/OR樹的特點可知G1,G2,… ,Gm均 為 或 門 。 那 么 ， 可 得由定義 3可得結論成立。證畢。

2.2 與或功能樹無損簡化的算法流程

以下給出與或功能樹無損簡化算法的偽代碼，見算法1。其大體思想為：首先將功能樹的各個門節(jié)點存儲在隊列FuncQueue之中，其次針對 FuncQueue中門節(jié)點對應的子樹，利用定理1～定理4依次進行無損簡化，其中在執(zhí)行無損刪除簡化或無損提取簡化前要先執(zhí)行無損收縮簡化（以保證此時功能樹為AND/OR樹）。在算法1中，Is_Simplified先設為true，隊列FuncQueue則先設為空。

算法1 功能樹無損簡化算法

while (Is_Simplified) {

Is_Simplified = false; pTop = FuncTree->top; //獲得功能樹的頂門指針

Simplify_LlContract (pTop); //無損收縮簡化

while (1) { //直接執(zhí)行循環(huán)，通過后面的break來結束循環(huán)

while (pTop != NULL) {

if (pTop是門節(jié)點) pTop加入到隊列FuncQueue中;

pTop = pTop->nextbrother; }

if (FuncQueue不為空){

m_pGate = FuncQueue的隊首元素（出隊）;

if (Simplify_LlDeleteFir (m_pGate)) Is_Simplified = true;

//無損刪除簡化1（如果執(zhí)行了刪除操作，則改變Is_Simplified的狀態(tài)，以下均類似）

Simplify_LlContract (m_pGate); //無損收縮簡化

if (Simplify_LlDeleteSec (m_pGate)) Is_Simplified = true; //無損刪除簡化2

Simplify_LlContract (m_pGate); //無損收縮簡化

If (Simplify_LlExtract (m_pGate)) Is_Simplified = true; //無損提取簡化

Simplify_LlContract (m_pGate); //無損收縮簡化

pTop = m_pGate->firstchild; }

else

break; }

}

3 實 例

圖2為一個磁懸浮列車概念設計的與或功能樹（僅其中磁斥部分），其中ix表示基本變量。運用本文的方法進行無損簡化后得到圖3，按文獻[14]中的邏輯簡化方法得到圖4。簡化數(shù)據(jù)如表1所示，其中基本變量的冗余程度定義為葉子節(jié)點數(shù)/基本變量數(shù)。

現(xiàn)在分析一下最后得到的結果，對于圖3所示的功能樹，其樹函數(shù)等價于（得到的方案數(shù)為7項）

圖2 簡化前的功能樹

對于圖4所示的功能樹，其樹函數(shù)等價于（得到的方案數(shù)為5項）

圖3 無損簡化后的功能樹

圖4 邏輯簡化后的功能樹

表1 與或功能樹簡化數(shù)據(jù)比較

從當前創(chuàng)新推理的兩大主要理論——TRIZ和可拓學出發(fā)，可得到創(chuàng)新推理具有如下特征[12-13]：一是創(chuàng)新推理的本質在于對沖突（或矛盾）的處理，而那些不存在沖突的問題，或采用折衷的方法解決問題就不是創(chuàng)新；二是利用基本變量及其之間的關系進行創(chuàng)新推理，進行問題和解的轉化，最終得到滿足問題的解。因此，沖突和基本變量在創(chuàng)新推理中處于核心地位。在與或功能樹中，主要考慮基本變量的要素。而沖突往往需要在與或非功能樹中才能得到清晰表達，這將在以后進一步研究。

從這個實例可見：邏輯簡化導致基本變量損失的比例高達27.3%，使得部分設計方案丟失，從而削弱了此功能樹的創(chuàng)新能力。比如，在圖2中的設計方案{x1, x3, x11}（關于如何進行功能求解，請參見文獻[8-10]），從φ2(X)可以看出該方案無法通過圖4來得到（因為圖4中沒有出現(xiàn)基本變量x11）。

但是，無損簡化保留了所有的基本變量，使得原功能樹的創(chuàng)新能力得以無損失的保留。比如同樣對于圖2中方案{x1, x3, x11}，在圖3中就可得到（從φ1

(X)可知）。從而無損簡化在保持邏輯等價和創(chuàng)新能力不損失的前提下有效降低了問題的復雜度，對于提高概念設計的效率有著直接的推動作用。

4 總 結

針對當前概念設計中較大規(guī)模功能樹存在的問題，提出與或功能樹的無損簡化方法。該方法可在保持邏輯等價和創(chuàng)新能力不損失的情況下對功能樹進行簡化，能夠有效縮減解空間，對于沖突發(fā)現(xiàn)與定位起到積極的推動作用，從而提高了概念設計的效率。本文的研究僅針對與或功能樹，而對于與或非功能樹，其既需要考慮基本變量，又需要分析沖突因素，從而使問題變得極其復雜。進一步地，文獻[8-10]等在功能求解的同時，都伴隨著簡化的因素；這里的簡化是否也存在損失的問題；若存在，則又如何避免損失？這些問題都將成為以后的工作重點。

[1] Shai O, Reich Y, Rubin D. Creative conceptual design: extending the scope by infused design [J]. Computer-Aided Design, 2009, 41(3): 117-135.

[2] Hsu W, Irene M Y W. Current research in the conceptual design of mechanical products [J]. Computer-Aided Design, 1998, 30(5): 377-389.

[3] Stone R, Wood K. Development of a functional basis for design [J]. Journal of Mechanical Design, 2000, 122(4): 359-370.

[4] Chakrabarti A, Thomas P B. A scheme for functional reasoning in conceptual design [J]. Design Studies, 2001, 22(6): 493–517.

[5] 張 帥, 馮培恩, 潘雙夏, 等. 基于循環(huán)映射模型的概念設計自動化策略研究[J]. 計算機輔助設計與圖形學學報, 2005, 17(3): 491-497.

[6] 宋慧軍, 林志航. 公理化設計支持的概念設計產品模型[J]. 計算機輔助設計與圖形學學報, 2002, 14(7): 632-636.

[7] 朱龍英, 朱如鵬, 劉正塤. 公理化設計與DFA集成的產品信息模型[J]. 計算機輔助設計與圖形學學報, 2004, 16(2): 216-221.

[8] 秦 晉, 劉曉平. 基于功能集族的功能求解方法[J].工程圖學學報, 2008, 29(5): 12-17.

[9] 劉曉平, 陸勁挺, 唐益明. 基于可拓學的對比相似功能樹擴展方法[J]. 工程圖學學報, 2009, 30(1): 153-159.

[10] 劉曉平, 唐益明, 秦 晉, 等. 概念設計中基于擴展功能矩陣的功能求解方法[J]. 計算機輔助設計與圖形學學報, 2007, 19(12): 1610-1617.

[11] Tang Yiming, Liu Xiaoping. Task partition for function tree according to innovative functional reasoning [C]//Proceedings of CSCWD 2008, China, 2008: 189-195.

[12] 劉曉平, 唐益明, 秦 晉. 基于TRIZ的計算機輔助創(chuàng)新原型系統(tǒng)的研究與實現(xiàn)[J]. 工程圖學學報, 2007, 28(6): 6-11.

[13] Liu Xiaoping, Qin Jin, Tang Yiming. An innovative function-tree building method based on similarity theory and extension theory[C]//Proceeding of CAID&CD’06, Hangzhou, China, 2006: 199-204.

[14] 路 強, 劉曉平. 基于布爾代數(shù)的功能樹簡化研究[J].合肥工業(yè)大學學報(自然科學版), 2009, 32(7): 1025-1029.

[15] Gaur D R, Krishnamurti R. Self-duality of bounded monotone boolean functions and related problems [J]. Discrete Applied Mathematics, 2008, 156(10): 1598-1605.

A lossless simplifying method of and/or function tree

Tang Yiming1,2, Liu Xiaoping2
( 1. Information and Communication Engineering Postdoctoral Research Station, Hefei University of Technology, Hefei Anhui 230009, China; 2. School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China )

Aiming at huge solving space and difficult conflict-orienting for large-scale function tree in conceptual design, a lossless simplifying method of and/or function tree is proposed. Some lossless simplifying theorems related to contract, deleting and extracting are proved, and then the lossless simplifying algorithm of and/or function tree is given based on these theorems. Finally, experimental results show that the algorithm can effectively reduce complexity holding logic equivalence and lossless innovative ability, and improve the efficiency of conceptual design.

computer application; conceptual design; lossless simplifying; and/or function tree

TP 391.72

A

2095-302X (2012)03-0034-07

2010-05-05

國家自然科學基金資助項目（61105076，61070124，90920006）

唐益明（1982-），男，安徽無為人，講師，博士，主要研究方向為模糊邏輯，CAD，情感計算，仿真與可視化。