唐益明， 劉曉平

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

與或功能樹(shù)的無(wú)損簡(jiǎn)化方法

唐益明1,2， 劉曉平2

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

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

計(jì)算機(jī)應(yīng)用；概念設(shè)計(jì)；無(wú)損簡(jiǎn)化；與或功能樹(shù)

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

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

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

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

為此，本文提出了無(wú)損簡(jiǎn)化的思想。由于與或非功能樹(shù)的無(wú)損簡(jiǎn)化極其復(fù)雜，因此本文僅針對(duì)與或功能樹(shù)的無(wú)損簡(jiǎn)化問(wèn)題進(jìn)行研究。首先介紹與或功能樹(shù)的基本定義，然后給出了幾個(gè)無(wú)損簡(jiǎn)化定理，并籍此給出與或功能樹(shù)的無(wú)損簡(jiǎn)化算法，最后通過(guò)具體的實(shí)例，驗(yàn)證了該方法的有效性。

1 與或功能樹(shù)的基本定義

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

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

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

例1 圖1為與或功能樹(shù)的一個(gè)示例，其目標(biāo)樹(shù)函數(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 功能樹(shù)示例

2 與或功能樹(shù)的無(wú)損簡(jiǎn)化方法

2.1 無(wú)損簡(jiǎn)化定理

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

定理 1 （無(wú)損收縮簡(jiǎn)化） 以下操作均為無(wú)損簡(jiǎn)化：

1） 如果相鄰兩層門(mén)類型相同，合并這兩個(gè)門(mén)為一個(gè)門(mén)。

2） 在同一個(gè)門(mén)的輸入中，合并相同的基本變量。

3） 如果一個(gè)門(mén)只有一個(gè)輸入，刪除這個(gè)門(mén)，其輸入上移。

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

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

定義 5 定義門(mén)變量 Gi的所有直接孩子節(jié)點(diǎn)序號(hào)構(gòu)成的集合為門(mén)變量 Gi的展開(kāi)，記為 Pi。如果 Gi的直接孩子節(jié)點(diǎn)中沒(méi)有重復(fù)的基本變量節(jié)點(diǎn)，Pi直接為 Gi孩子節(jié)點(diǎn)序號(hào)的集合；如果 Gi的直接孩子節(jié)點(diǎn)中有重復(fù)的基本變量節(jié)點(diǎn)，如有多個(gè) xi，則將其依次編號(hào)為 i(1),i(2)等歸入 Pi中。

例 2 在圖1中，為了區(qū)分，令功能樹(shù)中第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。對(duì)于定義5，需要對(duì)門(mén)節(jié)點(diǎn)重新編號(hào)，比如 G1,G2,G3,G4,G5可依次重新編號(hào)為x7,x8,x9, x10,x11，則對(duì)于 G1，相應(yīng)的P1= {8,9}；對(duì)于 G2，相應(yīng)的 P2= {1,10,2}。

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

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

命題1 對(duì)于與或功能樹(shù) H(G1)，對(duì)其進(jìn)行無(wú)損收縮簡(jiǎn)化后得到 H '(G1)，則 H '(G1)為AND/OR樹(shù)。

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

定理2 （無(wú)損刪除簡(jiǎn)化1） 如果在AND/ OR樹(shù)的某個(gè)門(mén) G1下有基本變量 xi，同時(shí)，在以G1為頂?shù)淖訕?shù)的偶數(shù)層上的某個(gè)門(mén) G2下也有xi，即 L(G2) - L(G1) ≡ 1(mod2)，且 PG1∩PG2?{i}，若對(duì) ?j ∈ V (G2)，有 NG2(xj)＜ NG1(xj)，則在刪除門(mén) G2為頂?shù)淖訕?shù)后，得到的H'(G1)是 H(G1)的無(wú)損簡(jiǎn)化。

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

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

歸納法。當(dāng) k= 1時(shí)，有

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

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

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

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

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

歸納法。當(dāng) k= 2時(shí)，有

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

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

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

定理4 （無(wú)損提取簡(jiǎn)化） 在AND/OR樹(shù)中，相同基本變量處在同一層的若干個(gè)門(mén)中，則將該基本變量提取出來(lái)的操作是無(wú)損簡(jiǎn)化。

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

2.2 與或功能樹(shù)無(wú)損簡(jiǎn)化的算法流程

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

算法1 功能樹(shù)無(wú)損簡(jiǎn)化算法

while (Is_Simplified) {

Is_Simplified = false; pTop = FuncTree->top; //獲得功能樹(shù)的頂門(mén)指針

Simplify_LlContract (pTop); //無(wú)損收縮簡(jiǎn)化

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

while (pTop != NULL) {

if (pTop是門(mén)節(jié)點(diǎn)) pTop加入到隊(duì)列FuncQueue中;

pTop = pTop->nextbrother; }

if (FuncQueue不為空){

m_pGate = FuncQueue的隊(duì)首元素（出隊(duì)）;

if (Simplify_LlDeleteFir (m_pGate)) Is_Simplified = true;

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

Simplify_LlContract (m_pGate); //無(wú)損收縮簡(jiǎn)化

if (Simplify_LlDeleteSec (m_pGate)) Is_Simplified = true; //無(wú)損刪除簡(jiǎn)化2

Simplify_LlContract (m_pGate); //無(wú)損收縮簡(jiǎn)化

If (Simplify_LlExtract (m_pGate)) Is_Simplified = true; //無(wú)損提取簡(jiǎn)化

Simplify_LlContract (m_pGate); //無(wú)損收縮簡(jiǎn)化

pTop = m_pGate->firstchild; }

else

break; }

}

3 實(shí) 例

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

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

圖2 簡(jiǎn)化前的功能樹(shù)

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

圖3 無(wú)損簡(jiǎn)化后的功能樹(shù)

圖4 邏輯簡(jiǎn)化后的功能樹(shù)

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

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

從這個(gè)實(shí)例可見(jiàn)：邏輯簡(jiǎn)化導(dǎo)致基本變量損失的比例高達(dá)27.3%，使得部分設(shè)計(jì)方案丟失，從而削弱了此功能樹(shù)的創(chuàng)新能力。比如，在圖2中的設(shè)計(jì)方案{x1, x3, x11}（關(guān)于如何進(jìn)行功能求解，請(qǐng)參見(jiàn)文獻(xiàn)[8-10]），從φ2(X)可以看出該方案無(wú)法通過(guò)圖4來(lái)得到（因?yàn)閳D4中沒(méi)有出現(xiàn)基本變量x11）。

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

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

4 總 結(jié)

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

[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)映射模型的概念設(shè)計(jì)自動(dòng)化策略研究[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(3): 491-497.

[6] 宋慧軍, 林志航. 公理化設(shè)計(jì)支持的概念設(shè)計(jì)產(chǎn)品模型[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002, 14(7): 632-636.

[7] 朱龍英, 朱如鵬, 劉正塤. 公理化設(shè)計(jì)與DFA集成的產(chǎn)品信息模型[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2004, 16(2): 216-221.

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

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

[10] 劉曉平, 唐益明, 秦 晉, 等. 概念設(shè)計(jì)中基于擴(kuò)展功能矩陣的功能求解方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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的計(jì)算機(jī)輔助創(chuàng)新原型系統(tǒng)的研究與實(shí)現(xiàn)[J]. 工程圖學(xué)學(xué)報(bào), 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] 路 強(qiáng), 劉曉平. 基于布爾代數(shù)的功能樹(shù)簡(jiǎn)化研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61105076，61070124，90920006）

唐益明（1982-），男，安徽無(wú)為人，講師，博士，主要研究方向?yàn)槟：壿?，CAD，情感計(jì)算，仿真與可視化。