唐益明，劉曉平

（1. 合肥工業(yè)大學(xué)情感計算與先進智能機器安徽省重點實驗室，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)信息與通信工程博士后科研流動站，安徽 合肥 230009；3. 合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009）

與或非功能樹的無損簡化策略

唐益明1,2,3，劉曉平1,3

（1. 合肥工業(yè)大學(xué)情感計算與先進智能機器安徽省重點實驗室，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)信息與通信工程博士后科研流動站，安徽 合肥 230009；3. 合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009）

對于產(chǎn)品概念設(shè)計中較大規(guī)模的與或非功能樹，常通過邏輯簡化來消減冗余，但邏輯簡化會導(dǎo)致創(chuàng)新能力的損失。為此，面向與或非功能樹，提出了無損簡化的策略。給出了與或非功能樹無損簡化的嚴格定義，建立了與或非功能樹到AND/OR樹的轉(zhuǎn)換方法，針對AND/OR樹證明了若干無損簡化定理，在此基礎(chǔ)上生成了與或非功能樹的無損簡化算法。通過應(yīng)用實例，證明該無損簡化策略可在保證邏輯等價和創(chuàng)新能力不損失的前提下有效縮減計算量，提升創(chuàng)新推理的效率。

計算機應(yīng)用；創(chuàng)新推理；無損簡化；與或非功能樹

產(chǎn)品創(chuàng)新推理是制造業(yè)在市場競爭中取勝的關(guān)鍵，而產(chǎn)品的創(chuàng)新性主要取決于產(chǎn)品設(shè)計的概念設(shè)計階段[1-2]。功能模型是概念設(shè)計的核心處理對象，因此功能模型創(chuàng)新推理是概念設(shè)計中的關(guān)鍵問題[3-4]。目前帶與、或、非分解的功能樹（簡稱為與或非功能樹）是概念設(shè)計中典型的、應(yīng)用極其廣泛的一種功能模型，其中，功能樹簡化與求解是功能樹創(chuàng)新推理的一大核心問題。

文獻[5]提出功能-行為-載體（結(jié)構(gòu)）的域結(jié)構(gòu)模板，并通過功能層、行為層、載體層依次交替出現(xiàn)的與或功能樹來實現(xiàn)。朱龍英[6]在公理化設(shè)計理論的基礎(chǔ)上，將功能域向結(jié)構(gòu)域的曲折映射表示為產(chǎn)品結(jié)構(gòu)樹，其中該樹僅用到“與”分解。張帥[7]構(gòu)建了“需求域-功能域-原理解域循環(huán)映射”的概念設(shè)計模型，其后建立了概念設(shè)計與或樹的形式化表達方法，探討了其求解算法。在文獻[8]中基于相似理論和可拓學(xué)理論，面向與或非功能樹開展對比相似擴展研究。文獻[9]利用擴展功能矩陣的逐步展開與約簡，實現(xiàn)了與或功能樹的求解算法。文獻[10]針對與或非功能樹，提出了基于四值矩陣的功能樹約簡求解算法。文獻[11]通過求解功能集族實現(xiàn)了與或非功能樹的功能求解算法。

對于，功能樹，其實現(xiàn)方案通常采用組合原理來得到[9-10]。創(chuàng)新推理的主要難點在于沖突的檢測、定位與消解[12-14]。對于規(guī)模較大的功能樹，其復(fù)雜性難以讓設(shè)計者理清頭緒，而且其實現(xiàn)方案數(shù)往往較龐大，導(dǎo)致很難準確尋找出最優(yōu)解；同時，也使得設(shè)計者很難迅速發(fā)現(xiàn)并定位沖突所在，更難以消解沖突。那么，如果可以對功能樹進行簡化，消減其中的冗余，使得樹的規(guī)模等價地減小，將會使得這一問題得到極大緩解。

對此可通過布爾代數(shù)或二值命題邏輯理論來進行簡化[15]，但進一步的研究發(fā)現(xiàn)，這種邏輯簡化會帶來解空間的損失。為此，文獻[16]面向與或功能樹，首次提出了無損簡化方法。該方法可在保持邏輯等價和創(chuàng)新能力不損失的前提下有效降低問題的復(fù)雜度，提高概念設(shè)計效率，取得較理想的效果。

相比與或功能樹，與或非功能樹要復(fù)雜得多。具體而言，加入了“非”，就會出現(xiàn)則增加了矛盾原子公式（見后文）的情形；并且，與或非功能樹增加“與非”、“或非”2種門類型。這些導(dǎo)致“與或非”情形下無損簡化的原理、實施過程變得更為復(fù)雜。

為此，本文面向與或非功能樹來研究無損簡化策略。首先給出與或非功能樹的相關(guān)定義，然后嚴格定義了其無損簡化概念，并將與或非功能樹轉(zhuǎn)化為AND/OR樹，在此基礎(chǔ)上證明了與或非功能樹無損簡化的相關(guān)定理，并轉(zhuǎn)化為功能樹無損簡化算法，最后以具體實例驗證了該算法的有效性。

1 與或非功能樹的相關(guān)定義

與或非功能樹可視為二值命題邏輯理論的一種應(yīng)用[10,17]?！芭c”門分解相當(dāng)于“∧”，或門分解相當(dāng)于“∨”，“非”門相當(dāng)于否定運算“'”。對于功能T，若按或門展開為 A1和 A2，則有 T = A1∨ A2，即功能 A1實現(xiàn)或功能 A2實現(xiàn)，則有功能T實現(xiàn)，其余類似可得。對于原子公式集合，令 ()F S為所有公式構(gòu)成的集合。對于 A, B ∈ F( S)，記 SA為A中出現(xiàn)的原子公式的集合，并且用A ≈ B表示A與B邏輯等價。

定義1 對于功能樹中重復(fù)的葉子節(jié)點用一個二值命題邏輯的原子公式表示，稱為基本變量，記為 xi。當(dāng)基本變量 xi對應(yīng)的葉子節(jié)點的需求實現(xiàn)時 xi取1，否則取0。類似地，將功能樹的門節(jié)點用邏輯公式 Gj表示，稱為擴展變量或門變量?；咀兞亢蛿U展變量統(tǒng)稱為樹變量。記頂節(jié)點為 Gi的功能樹為 H( Gi)，記其樹變量的集合為 X( G1)或X，記其基本變量集為或 X '；并記功能樹的門變量的下標集記為 U( Gi)，基本變量的下標集記為 V( Gi)。

定義 2 定義門變量 Gi的所有直接孩子節(jié)點構(gòu)成的集合為門變量 Gi的展開，記為 Γi。如果 Gi的直接孩子節(jié)點中沒有重復(fù)的基本變量節(jié)點，Γi直接為 Gi孩子節(jié)點的集合；如果 Gi的直接孩子節(jié)點中有重復(fù)的基本變量節(jié)點，如有多個xi，則將其依次編號為等歸入 Γi中。類似地定義為展開中的門變量子集，為展開中的基本變量子集，并令其中為中基本變量的非所構(gòu)成的子集，為中基本變量構(gòu)成的子集。

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

定義5 對于功能樹 Η( G1)，對于其中的任一基本變量 xi，記為在 Η( G1)中的出現(xiàn)次數(shù)。

定義6 設(shè) A, B ∈ F( S)， S = {x1, x2,… , xn}，定義A的廣義秩 W( A)為：（1）若 A = xi，則令 W( A) = 1。（2）若 W( A1) =w1,… ,W( An)= wn，則令 W( A1∨…∨ An)= W( A1∧…∧ An)= w1+ … +wn。（3）對于外圍有括號的表達式A，W( A) = w，則令 W( A ')= w。（4）若 B = (A)，則 W( B ) = W( A)+1。（5）對于單獨出現(xiàn)的表達式A，若 A ≠xi,(xi) ,((xi)),…，且 A ≠ B'，則默認為外圍有一重括號，即視為(A) ，此時W( A)表示(A)的廣義秩。其中，單獨出現(xiàn)是相對于 A在其他表達式的一部分而言的（如B = A ∨ xi之類情形則表示A沒有單獨出現(xiàn)，如B = A則表示A單獨出現(xiàn)）。

例1 A1= x1，則 W( A1)=1。A2= x1∧ x2，則 A2屬于單獨出現(xiàn)的情形，有 W( A2) =1+ 1+ 1 =3。A3= (x1∧ x2)'∨ x3，則 W( A3) =3+ 1+ 1 =5。A4= (x1)∧ x2，則 W( A4) = 2+ 1+ 1 = 4。

定義7 對功能樹 Η( G1)，按層次遍歷的順序，僅執(zhí)行對其所有的門節(jié)點的展開操作（即與、或、與非、或非操作，由門的類型而定），得到一個含所有基本變量的唯一的樹表達式，稱為Η( G1)的完備式，記為（或其中，添加括號的方式為：（1）如果為“與門”或“或門”，除了樹的頂節(jié)點不添加括號外，其余門節(jié)點展開必添加括號；（2）如果為“與非門”或“或非門”，其余門節(jié)點展開必添加括號后加“非”。

圖1 功能樹的展開及其邏輯簡化

2 與或非功能樹的無損簡化

2.1 與或非功能樹無損簡化的定義

規(guī)定功能樹 Η( G1)的層數(shù) L (Η ( G1))為樹中節(jié)點層數(shù)的最大值。令 Num( xi)為以 xi為頂節(jié)點的子樹（即 Η( xi)）中節(jié)點的個數(shù)（包括 xi）。不難證明如下命題：

命題 1 設(shè) Η( G1)為一個功能樹，則W (τG1(X ')) = Num( G1)。

命題1刻畫了功能樹的節(jié)點數(shù)與對應(yīng)的完備式的廣義秩之間的關(guān)系，這樣就把功能樹的簡化轉(zhuǎn)化到了對命題公式的處理上了。構(gòu)造偏序關(guān)系， ?A , B ∈ F( S)，定義偏序關(guān)系 A ≤WB，當(dāng)且僅當(dāng)A ≈ B且 W( A) ≤ W( B)。定義A ＜WB當(dāng)且僅當(dāng) A ≤WB且 W( A) ≠ W( B)。

定義 8 對于公式 A ∈ F( S)，若對于B ∈ F( SA)滿足 B ≤WA，則B稱為A的N-簡化。若 B ＜WA，則B稱為A的真N-簡化。注意到這里采用 B ∈ F( SA)的限制，是因為實際的簡化過程中，不可能在簡化時引入原簡化對象外的變量。同時，這里假定所做的簡化均為有意義的，即不會出現(xiàn)簡化后新增出 xi∨ xi之類的無意義簡化現(xiàn)象。

命題邏輯的簡化理論進行N-簡化的過程為

簡化后的廣義秩 = {[(1+ 1)+ 1]}+ {[(1+ 1)+1]} +1= 7，簡化后的樹如圖1(c)。

設(shè) A ∈ F( SA)，對于A的析取范式中出現(xiàn)的xi∧ xi'，稱為矛盾原子公式。原來的原子公式稱為一般原子公式。矛盾原子公式與一般原子公式統(tǒng)稱為廣義原子公式。

創(chuàng)新推理的解是基本變量的組合（采用簡單合取式的形式，如 x1∧ x2∧ … ∧xk即為創(chuàng)新推理的解），而每一個基本變量，就代表問題的一個原子解。因此，一旦損失基本變量，就意味著損失了解決問題的一大批方法；甚至損失了最好的初始解。利用二值命題邏輯理論進行簡化，無論是針對功能樹的簡化，還是求解時的簡化，都會造成設(shè)計解空間的損失。進一步地，如果考慮到與或非的情形，則變得更加復(fù)雜。在沖突方面，對于x ∧?x ，在二值命題邏輯中可以簡化為0，但是這恰恰是物理沖突的情形，因此如果直接簡化，可能帶來無法控制的嚴重后果。為此，從創(chuàng)新概念設(shè)計的特征出發(fā)，原子公式和矛盾原子公式是創(chuàng)新的出發(fā)點，因此需要保證這兩者的不損失。由此，可得到定義9。

定義 9 設(shè) A ∈ F( S)，若 B ∈ F( SA)滿足B ≤WA，且簡化過程滿足：(C1)未執(zhí)行導(dǎo)致矛盾原子公式減少的簡化操作；(C2)原子公式未減少，則B稱為A的無損簡化。其中，若 B ＜WA，則B稱為A的真無損簡化。

對功能樹 Η( G1)，按完備式的生成方法，對功能樹進行自上而下的展開，即對樹表達式進行不斷的迭代（展開），從而得到一系列的樹表達式，最后一個樹表達式即為完備式，即對功能樹的任何操作（即對樹表達式的任何操作），都會在完備式中得到相應(yīng)的體現(xiàn)，兩者等價。因此在以下的處理中，直接對樹表達式進行處理即可。

定義 10 對于功能樹 Η( G1)，其樹函數(shù)為φ，對其中某個節(jié)點或子樹進行了有限次簡化操作，得到了新的功能樹 Η '(G1)，其樹函數(shù)為φ '。功能樹 Η '( G1)稱為 Η( G1)的無損簡化，如果滿足：φ ' = φ（這里表示邏輯等價），N um'( G1)≤Num( G1)，且簡化過程滿足(C1)、(C2)。記為Η' (G1)≤ Η (G1)。其中若 Num'( G1) ＜ Num( G1)，稱 Η '(G1)為 Η( G1)的真無損簡化，記Η '(G1) ＜ Η(G1)。

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

定義12 對功能樹1( )GΗ 中的門2G取非，是指運用De Morgan律，對門2G的每個孩子節(jié)點取非，并且2G的門類型取非，即若2G為與門，轉(zhuǎn)變?yōu)榛蚍情T；若2G 為或門，轉(zhuǎn)變?yōu)榕c非門；若2G為與非門，轉(zhuǎn)變?yōu)榛蜷T，若2G為或非門，轉(zhuǎn)變?yōu)榕c門。記為2'G 。

2.2 與或非功能樹到AND/OR樹的轉(zhuǎn)換

不難證明引理1。其思想在于：僅對功能樹的某個局部（節(jié)點或子樹）進行操作，如果該操作是等價操作，則功能樹前后是等價的；如果局部發(fā)生了無損簡化，則功能樹也隨之發(fā)生了無損簡化。

引理 1 對于功能樹 Η( G1)中的門 G2，對H( G2)進行有限次簡化操作得到功能樹H'( G2)，且 Η( G1)中沒有執(zhí)行對其余部分的操作，得到功能樹 Η '(G1)，則：（1）? φ' = φ分別為 H( G2)、 H'( G2)、 Η( G1)、 Η '( G1)的樹函數(shù)）。（2）H'( G2)≤ H( G2)? Η '( G1)≤ Η( G1)。特別地， H'( G2) ＜ H( G2)? Η '( G1) ＜ Η( G1)。

不難證明以下命題2、定理1：

命題 2 對于功能樹 Η (G1)，（1）若 G1為“與門”（或者“或門”），則存在與或功能樹Η '(G1)，使得 Η '( G1)≤ Η( G1)， Num'( G1)= Num( G1)；（2）若 G1為“與非門”（或者“或非門”），則存在與或功能樹 Η '(G1')，使得Η '( G1')≤ Η( G1)， Num'( G1') = Num( G1)。

為了便于處理，對某節(jié)點 Gi的或展開（這里 xj為基本變量或擴展變量）， Pi= A ∪ B，令：在不致混淆的情況下，可簡記為同理，對某節(jié)點 Gi的與展開則令：簡記為

定理1 （AND/OR樹的生成定理）對于與或功能樹 Η( G1)，有：（1） Η( G1)中存在子樹則僅對H( G2)進行操作后：得到 Η '( G1)，有：H'( G1) ＜ H( G1)。（2） Η( G1)中存在子樹則僅對 H( G2)進行操作后：，得到 Η '( G1)，有：H '( G1)＜ H( G1)。（3）必存在一個 AND/OR樹 Η '( G1)，滿足Η '( G1)≤ Η( G1)。

推論 1 對于功能樹 Η( G1)，必存在一個AND/OR樹 Η '( G1)，滿足 Η '( G1)≤ Η( G1)。

定理 1給出了與或功能樹轉(zhuǎn)化為 AND/OR樹的方法。將定理1的操作稱為功能樹的規(guī)范化操作。

2.3 AND/OR樹的無損簡化定理

以下給出針對 AND/OR樹的無損簡化的若干定理。

定理2 （無損收縮規(guī)則） 對于AND/OR樹Η( G1)，有：（1）Η ( G1)中存在子樹 H( G2)，，則僅對 G2進

僅對 G2進行操作后：

得到 Η '( G1)，有： H'( G1)＜ H( G1)。

證明 （1）考察子樹 H( G2)與 H'( G2)，

例如，功能樹中具有共同父節(jié)點的幾個孩子節(jié)點對應(yīng)同一個基本變量 xi時，則可進行無損收縮。

定理 3 對于 AND/OR樹 Η( G1)中的門G2≠ G1， L( G2) - L( G1) ≡ 0(mod 2)，且P1∩ P2?{i}，i ∈{1,2,3,… ,p,-1,-2 ,… ,- p}，{1,… ,p} ?V( G1)，則對于刪除門 G2下的 xi得到的新功能樹 Η '(G1)，如果該操作不直接導(dǎo)致廣義原子公式的損失，則有 Η '(G1) ＜ Η(G1)。

證明 無妨設(shè) G1是個與門（ G1是或門時可類似證明）。令 k = L( G2) - L( G1)。令 Η( G1)的樹函數(shù)為φ，的樹函數(shù)為φ '。在之間必定存在門節(jié)點序列G其中 G1展開后包含展開后包含展開后包含 G2，并有 L( G1)+1 = L( Gt1)=且分別為“或門、與門、…、或 門 、 與 門 ”。 由 ? j ∈ V( G1)， 有。又未導(dǎo)致矛盾原子公式的減少，因此滿足(C1)、(C2)。又刪除操作必導(dǎo)致節(jié)點的減少，即 Num'( G1)＜Num( G1)。因此要證明 Η '(G1)＜ Η( G1)，只需證明φ ' = φ。

數(shù)學(xué)歸納法。當(dāng) k= 2時，有

現(xiàn)假設(shè) k = 2 × n( n ≥ 1)時按題意情況的兩功能樹的樹函數(shù)相等，則當(dāng) k = 2 × n+ 2時有

考察對應(yīng)樹函數(shù)φ''=[(xi∧Gt3∧SGt2({G t 3 }))的 AND/OR樹 H ''(G1)，令2× n，則根據(jù)假設(shè)有以 G為頂節(jié)點的AND/OR3樹H( G3)，與刪除門 G2下的 xi后得到的AND/OR樹 H'( G3)，有。而且 H ''(G1)中沒有其他的操作，由引理1，得φ '' = φ'。故得φ= φ'。

由歸納法可知， φ= φ'證明完成。故得Η '(G1) ＜ Η(G1)。證畢。

類似地，可以證明定理4、5和6：

定理 4 對于 AND/OR樹 Η( G )中的門

1，則對于刪除以 G 為頂?shù)淖訕涞玫?/p>

2AND/OR樹 Η '(G1)，如果該操作不直接導(dǎo)致廣義原子公式的損失，則有 Η '(G ) ＜ Η(G )。

11

定理5 對于OR-AND交錯樹 Η( G )中的

1，且 P1? {i}，，則對于刪除門下的 x i'得到的新功能樹，如果該操作不直接導(dǎo)致廣義原子公式的損失，則有。

定理6 對于OR-AND交錯樹 Η( G )中的

1門G2≠ G1， L( G2)- L( G1) ≡ 0(mod 2)，且

P1? {i}， P2? {- i }，若對 ? j∈ V( G2)，有：則對于刪除以 G2為頂?shù)淖訕涞玫降男鹿δ軜?Η '(G

1)，如果該操作不直接Η '(G ) ＜ Η(G )導(dǎo)致廣義原子公式的損失，有11。

稱定理 3、4、5、6為無損刪除規(guī)則。以定理3為例。假如功能樹中第2層和第4層出現(xiàn)了同一個基本變量 x i，則在保持無損的前提下，可以將第4層中 xi所對應(yīng)的節(jié)點刪除。

定理7 （無損提取規(guī)則） 對于AND/OR樹Η( G1)中的門 G2，其孩子門節(jié)點中有 G3, G4滿足：，則

（1） G3和 G4中除了外剩下的孩子節(jié)點數(shù)均為1，則對 G2中部分進行如下操作：先產(chǎn)生新的門節(jié)點 G（類型與 G相52異），將均直接作為 G5的孩子節(jié)點；再產(chǎn)生新的門節(jié)點（類型與 G2相同），將原 G3, G4中均刪除，分別得到（門節(jié)點或基本變量節(jié)點），將的孩子節(jié)點、的孩子節(jié)點作為的孩子節(jié)點（若為基本變量節(jié)點，則將作為 G6的孩子節(jié)點），最后將作為的孩子節(jié)點，作為的孩子節(jié)點。得到新的功能樹，有。，且 G3和 G4中除了

（3） 若 n= 2，且 G3和 G4中除了外剩下的孩子節(jié)點數(shù)分別等于1、大于1，則對 G2中 G3, G4部分進行如下操作：先產(chǎn)生新的門節(jié)點 G5（類型與 G2相異），將均直接作為 G5的孩子節(jié)點；再產(chǎn)生新的門節(jié)點G6（類型與 G2相同），將原 G3, G4中均刪除，分別得到 x7, G8，將 x7的孩子節(jié)點（若 x7為基本變量節(jié)點，則將 x7自身作為 G6的孩子節(jié)點）、 G8作為 G6的孩子節(jié)點，最后將 G6作為 G5的孩子節(jié)點， G5作為 G2的孩子節(jié)點。得到新的功能樹 Η '(G1)，有Η '(G1) ＜ Η(G1)。

（4） G3和 G4中除了外剩下的孩子節(jié)點數(shù)分別等于 0、大于 0，如果將子樹H( G4)刪除得到新的功能樹 Η '(G1)，如果該操作不直接導(dǎo)致廣義原子公式的損失，則有Η '(G1) ＜ Η(G1)。

證明 這里僅證明（1）（而（2）、（3）、（4）可類似證明）。無妨令 G2為與門，令執(zhí)行刪除操作后得到的子樹為 H'( G2)。 H( G2)與 H'( G2)的樹函數(shù)分別為則，由題意均為與門節(jié)點 Gk或葉子節(jié)點（基本變量），無妨令為門節(jié)點為門節(jié)點必為與門，若為基本變量可類似證明），則而則對 ?j∈ V( G2)， 若 j? {s1, s2,… ,sn}， 則若 j∈ { s1, s2,…, sn}，則同時，這種操作不會導(dǎo)致矛盾原子公式的減少（這是由于分配律不會減少矛盾原子公式的緣故）。因此，滿足(C1)、(C2)。又則（注意這里中用的本身，，所以這里計數(shù)時要用類似），再由，則（注意中用的Gk1的孩子節(jié)點，所以計數(shù)時要用，則 Num'( G2)- Num( G2) =-n- 2，故Η (G2) ＜ Η'(G2)。由引理1，得 Η( G1)＜Η '(G1)。證畢。

2.4 與或非功能樹的無損簡化算法

算法1為與或非功能樹的無損簡化算法。其中Is_Simplified為布爾型變量（事先設(shè)為true），作為是否執(zhí)行無損簡化操作的控制變量。其大體過程如下：首先將與或非功能樹轉(zhuǎn)化為與或功能樹（僅需執(zhí)行一次，因為后面的操作都不改變與或功能樹的形式），然后執(zhí)行循環(huán)（直至Is_Simplified為false時退出）：將與或功能樹轉(zhuǎn)化為AND/OR樹（即規(guī)范化操作），再依次執(zhí)行無損收縮規(guī)則、無損刪除規(guī)則和無損提取規(guī)則，其中在無損收縮規(guī)則執(zhí)行后需要再次執(zhí)行規(guī)范化操作（注意到無損刪除規(guī)則和無損提取規(guī)則執(zhí)行前后不改變AND/OR樹的形式）。另外，為了減少總循環(huán)的次數(shù)，這里3個無損簡化規(guī)則都執(zhí)行到不能執(zhí)行為止（即各自設(shè)置一個與Is_Simplified類似的控制變量，為 false時才退出）。

算法1 與或非功能樹的無損簡化算法

Step 1 將與或非功能樹轉(zhuǎn)化為與或功能樹（運用命題2）。

Step 2 若Is_Simplified為true，繼續(xù)，否則轉(zhuǎn)Step10。

Step 3 Is_Simplified = false。

Step 4 將與或功能樹轉(zhuǎn)化為 AND/OR樹（即規(guī)范化操作，運用定理1）。

Step 5 執(zhí)行無損收縮規(guī)則，若簡化前后有變化，則令I(lǐng)s_Simplified = true。

Step 6 將與或功能樹轉(zhuǎn)化為AND/OR樹。

Step 7 執(zhí)行無損刪除規(guī)則（對功能樹的每個門節(jié)點執(zhí)行，用廣度遍歷），若簡化前后有變化，則令I(lǐng)s_Simplified = true。

Step 8 執(zhí)行無損提取規(guī)則，若簡化前后有變化，則令I(lǐng)s_Simplified= true。

Step 9 轉(zhuǎn)Step2。

Step 10 結(jié)束。

3 實 例

圖 2為針對磁懸浮列車的概念設(shè)計的子模塊（僅給出部分模塊），利用磁斥的方法進行設(shè)計得到的與或非功能樹。其中節(jié)點數(shù)為 57個，門節(jié)點數(shù)為22個，葉子節(jié)點35個，基本變量17個。每個葉子節(jié)點下方的編號（如X1）為基本變量編號，每個門節(jié)點下方的編號（如G1）為門變量編號。對照算法1，圖3為轉(zhuǎn)化為AND/OR樹后的功能樹。運用本文的方法進行無損簡化后得到圖4（其中M是無損簡化生成的中間節(jié)點）。利用二值命題邏輯理論可得到相應(yīng)邏輯簡化的方法（限于篇幅，這里不作展開），其結(jié)果如圖5所示。

現(xiàn)在考察一下兩者的結(jié)果，如果將圖5轉(zhuǎn)化為析取范式

則直接得到的析取項（即初始解）只有5項。

而對于經(jīng)過無損簡化后的最終功能樹（圖4），

對其進行計算，得

圖2 磁懸浮列車概念設(shè)計的與或非功能樹

圖3 轉(zhuǎn)化為AND/OR樹后的功能樹

直接得析取項(2× 2 + 2+ 1)× 5 = 35（項）。 而且包含邏輯簡化的5項。

圖4 無損簡化后的功能樹

圖5 邏輯簡化后的功能樹

表1中對功能樹的總體簡化情況進行分析，并對邏輯簡化與無損簡化進行了對比。其中，基本變量的冗余程度定義為：葉子節(jié)點樹/基本變量數(shù)。如果為1，表示無冗余。數(shù)值越大，表示冗余程度越高。從中可見邏輯簡化導(dǎo)致基本變量損失的比例高達47.06%，而且也導(dǎo)致了有沖突的初始解（即初始解中含有矛盾原子公式，有35項）的損失。而無損簡化則保持了原功能樹的創(chuàng)新能力。

表1 磁懸浮列車功能樹簡化數(shù)據(jù)比較

4 總 結(jié)

與或非功能樹的簡化既需要考慮基本變量，又需要分析沖突因素（即矛盾原子公式），從而問題變得復(fù)雜得多（而與或功能樹無需考慮矛盾原子公式的情形）。本文研究了與或非功能樹的無損簡化策略。該策略一方面維持了二值命題邏輯意義下的邏輯等價，一方面保持了原功能樹的創(chuàng)新能力，這樣真正地等價縮減了解空間，對于沖突發(fā)現(xiàn)、定位與消解起到有力的推動作用,從而提升了創(chuàng)新推理的效率。

文獻[9-11]探討了功能樹的求解，其間都用到了邏輯簡化理論；同樣地，這種簡化也有可能造成損失，對此該如何進行控制？進一步地，概念設(shè)計是個充滿了殘缺性、模糊性、不確定性[18-21]的過程，怎樣對此進行妥善處理？這些都是將來需要開展的工作重點。

[1] Chen Yong, Liu Zelin, Xie Youbai. A knowledgebased framework for creative conceptual design of multi-disciplinary systems [J]. Computer-Aided Design, 2012, 44(2): 146-153.

[2] Qasim Z, Moatasem M, Dong Yunfeng. Conceptual design architecture modeling and simulation for boost phase ballistic missile defense [J]. CADDM, 2008, 18(1): 47-65.

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

[4] ?lvander J, Lundén B, Gavel H. A computerized optimization framework for the morphological matrix applied to aircraft conceptual design [J]. Computer-Aided Design, 2009, 41(3): 187-196.

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

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

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

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

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

[10] 唐益明, 劉曉平. 功能樹的EFVM求解算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2010, 22(9): 1578-1586.

[11] 唐益明, 劉曉平. 與或非功能樹的功能集族求解方法[J]. 工程圖學(xué)學(xué)報, 2011, 32(1): 143-147.

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

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

[14] 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.

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

[16] 唐益明, 劉曉平. 與或功能樹的無損簡化方法[J].圖學(xué)學(xué)報, 2012, 33(3): 34-40.

[17] Amgoud L, Devred C, Christine M, et al. Algorithms for generating arguments and counterarguments in propositional logic [J]. International Journal of Approximate Reasoning, 2011, 52(6): 672-704.

[18] Yang Wenshan, Tan Wuzheng. A platform for collaborative modeling [J]. CADDM, 2008, 18(2): 39-49.

[19] Tang Yiming, Liu Xiaoping. Differently implicational universal triple I method of (1, 2, 2) type [J]. Computers & Mathematics with Applications, 2010, 59(6): 1965-1984.

[20] 劉曉平, 唐益明, 鄭利平. 復(fù)雜系統(tǒng)與復(fù)雜系統(tǒng)仿真研究綜述[J]. 系統(tǒng)仿真學(xué)報, 2008, 20(23): 6303-6315.

[21] Tang Yiming, Ren Fuji, Chen Yanxiang. Differently implicational α–universal triple I restriction method of (1, 2, 2) type [J]. Journal of Systems Engineering and Electronics, 2012, 23(4): 560-573.

Lossless simplifying strategies of and/or/not function tree

Tang Yiming1,2,3, Liu Xiaoping1,3
( 1. AnHui Province Key Laboratory of Affective Computing and Advanced Intelligent Machine, Hefei University of Technology, Hefei Anhui 230009, China; 2. Information and Communication Engineering Postdoctoral Research Station, Hefei University of Technology, Hefei Anhui 230009, China; 3. School of Computer & Information, Hefei University of Technology, Hefei Anhui 230009, China )

For large-scale and/or/not function trees in product conceptual design, it is usual to use logic simplifying to cut down redundancy; however logic simplifying may result in the loss of innovative ability. Aiming at this problem, the lossless simplifying strategies are proposed for and/or/not function trees. First of all, the strict definition of lossless simplifying of and/or/not function tree is given, and then the converting method from the and/or/not function tree to AND/OR tree is established. Moreover, some lossless simplifying theorems for the AND/OR tree are proved, and based on them the lossless simplifying algorithm of and/or/not function tree is obtained. Lastly, experimental results show that such strategies can effectively reduce computational cost under the condition to ensure logic equivalence and also lossless innovative ability, thus improve the efficiency of innovative reasoning.

computer application; innovative reasoning; lossless simplifying; and/or/not function tree

TP 391.72

A

2095-302X (2013)01-0031-10

2012-01-10；定稿日期：2012-02-20

國家自然科學(xué)基金資助項目（61203077，41076120，61105076，61070124，60890075）中國博士后科學(xué)基金資助項目（2012M521218）；中央高?；究蒲袠I(yè)務(wù)費專項資助項目（2012HGQC0011，2012HGCX0001，2012HGBZ0639）

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

劉曉平（1964-），男，山東濟南人，教授，博士，主要研究方向為建模、仿真與協(xié)同計算。E-mail：lxp@hfut.edu.cn