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

唐益明，劉曉平

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

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

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

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

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

計算機應用；創新推理；無損簡化；與或非功能樹

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

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

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

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

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

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

1 與或非功能樹的相關定義

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

定義1 對于功能樹中重復的葉子節點用一個二值命題邏輯的原子公式表示，稱為基本變量，記為 xi。當基本變量 xi對應的葉子節點的需求實現時 xi取1，否則取0。類似地，將功能樹的門節點用邏輯公式 Gj表示，稱為擴展變量或門變量。基本變量和擴展變量統稱為樹變量。記頂節點為 Gi的功能樹為 H( Gi)，記其樹變量的集合為 X( G1)或X，記其基本變量集為或 X '；并記功能樹的門變量的下標集記為 U( Gi)，基本變量的下標集記為 V( Gi)。

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

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

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

定義6 設 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）對于單獨出現的表達式A，若 A ≠xi,(xi) ,((xi)),…，且 A ≠ B'，則默認為外圍有一重括號，即視為(A) ，此時W( A)表示(A)的廣義秩。其中，單獨出現是相對于 A在其他表達式的一部分而言的（如B = A ∨ xi之類情形則表示A沒有單獨出現，如B = A則表示A單獨出現）。

例1 A1= x1，則 W( A1)=1。A2= x1∧ x2，則 A2屬于單獨出現的情形，有 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)，按層次遍歷的順序，僅執行對其所有的門節點的展開操作（即與、或、與非、或非操作，由門的類型而定），得到一個含所有基本變量的唯一的樹表達式，稱為Η( G1)的完備式，記為（或其中，添加括號的方式為：（1）如果為“與門”或“或門”，除了樹的頂節點不添加括號外，其余門節點展開必添加括號；（2）如果為“與非門”或“或非門”，其余門節點展開必添加括號后加“非”。

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

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

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

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

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

命題1刻畫了功能樹的節點數與對應的完備式的廣義秩之間的關系，這樣就把功能樹的簡化轉化到了對命題公式的處理上了。構造偏序關系， ?A , B ∈ F( S)，定義偏序關系 A ≤WB，當且僅當A ≈ B且 W( A) ≤ W( B)。定義A ＜WB當且僅當 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∨ xi之類的無意義簡化現象。

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

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

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

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

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

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

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

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

定義12 對功能樹1( )GΗ 中的門2G取非，是指運用De Morgan律，對門2G的每個孩子節點取非，并且2G的門類型取非，即若2G為與門，轉變為或非門；若2G 為或門，轉變為與非門；若2G為與非門，轉變為或門，若2G為或非門，轉變為與門。記為2'G 。

2.2 與或非功能樹到AND/OR樹的轉換

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

引理 1 對于功能樹 Η( G1)中的門 G2，對H( G2)進行有限次簡化操作得到功能樹H'( G2)，且 Η( G1)中沒有執行對其余部分的操作，得到功能樹 Η '(G1)，則：（1）? φ' = φ分別為 H( G2)、 H'( G2)、 Η( G1)、 Η '( G1)的樹函數）。（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)。

為了便于處理，對某節點 Gi的或展開（這里 xj為基本變量或擴展變量）， Pi= A ∪ B，令：在不致混淆的情況下，可簡記為同理，對某節點 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給出了與或功能樹轉化為 AND/OR樹的方法。將定理1的操作稱為功能樹的規范化操作。

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

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

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

僅對 G2進行操作后：

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

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

例如，功能樹中具有共同父節點的幾個孩子節點對應同一個基本變量 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)，如果該操作不直接導致廣義原子公式的損失，則有 Η '(G1) ＜ Η(G1)。

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

數學歸納法。當 k= 2時，有

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

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

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

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

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

1，則對于刪除以 G 為頂的子樹得到

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

11

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

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

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

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

P1? {i}， P2? {- i }，若對 ? j∈ V( G2)，有：則對于刪除以 G2為頂的子樹得到的新功能樹 Η '(G

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

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

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

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

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

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

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

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

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

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

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

Step 2 若Is_Simplified為true，繼續，否則轉Step10。

Step 3 Is_Simplified = false。

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

Step 5 執行無損收縮規則，若簡化前后有變化，則令Is_Simplified = true。

Step 6 將與或功能樹轉化為AND/OR樹。

Step 7 執行無損刪除規則（對功能樹的每個門節點執行，用廣度遍歷），若簡化前后有變化，則令Is_Simplified = true。

Step 8 執行無損提取規則，若簡化前后有變化，則令Is_Simplified= true。

Step 9 轉Step2。

Step 10 結束。

3 實 例

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

現在考察一下兩者的結果，如果將圖5轉化為析取范式

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

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

對其進行計算，得

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

圖3 轉化為AND/OR樹后的功能樹

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

圖4 無損簡化后的功能樹

圖5 邏輯簡化后的功能樹

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

表1 磁懸浮列車功能樹簡化數據比較

4 總 結

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

文獻[9-11]探討了功能樹的求解，其間都用到了邏輯簡化理論；同樣地，這種簡化也有可能造成損失，對此該如何進行控制？進一步地，概念設計是個充滿了殘缺性、模糊性、不確定性[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] 宋慧軍, 林志航. 公理化設計支持的概念設計產品模型[J]. 計算機輔助設計與圖形學學報, 2002, 14(7): 632-636.

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

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

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

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

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

[11] 唐益明, 劉曉平. 與或非功能樹的功能集族求解方法[J]. 工程圖學學報, 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的計算機輔助創新原型系統的研究與實現[J]. 工程圖學學報, 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] 路 強, 劉曉平. 基于布爾代數的功能樹簡化研究[J].合肥工業大學學報(自然科學版), 2009, 32(7): 1025-1029.

[16] 唐益明, 劉曉平. 與或功能樹的無損簡化方法[J].圖學學報, 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] 劉曉平, 唐益明, 鄭利平. 復雜系統與復雜系統仿真研究綜述[J]. 系統仿真學報, 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

國家自然科學基金資助項目（61203077，41076120，61105076，61070124，60890075）中國博士后科學基金資助項目（2012M521218）；中央高校基本科研業務費專項資助項目（2012HGQC0011，2012HGCX0001，2012HGBZ0639）

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

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