與或非功能樹(shù)的無(wú)損簡(jiǎn)化策略

唐益明，劉曉平

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

與或非功能樹(shù)的無(wú)損簡(jiǎn)化策略

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

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

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

計(jì)算機(jī)應(yīng)用；創(chuàng)新推理；無(wú)損簡(jiǎn)化；與或非功能樹(shù)

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

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

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

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

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

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

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

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

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

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

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

定義5 對(duì)于功能樹(shù) Η( G1)，對(duì)于其中的任一基本變量 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）對(duì)于外圍有括號(hào)的表達(dá)式A，W( A) = w，則令 W( A ')= w。（4）若 B = (A)，則 W( B ) = W( A)+1。（5）對(duì)于單獨(dú)出現(xiàn)的表達(dá)式A，若 A ≠xi,(xi) ,((xi)),…，且 A ≠ B'，則默認(rèn)為外圍有一重括號(hào)，即視為(A) ，此時(shí)W( A)表示(A)的廣義秩。其中，單獨(dú)出現(xiàn)是相對(duì)于 A在其他表達(dá)式的一部分而言的（如B = A ∨ xi之類(lèi)情形則表示A沒(méi)有單獨(dú)出現(xiàn)，如B = A則表示A單獨(dú)出現(xiàn)）。

例1 A1= x1，則 W( A1)=1。A2= x1∧ x2，則 A2屬于單獨(dú)出現(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 對(duì)功能樹(shù) Η( G1)，按層次遍歷的順序，僅執(zhí)行對(duì)其所有的門(mén)節(jié)點(diǎn)的展開(kāi)操作（即與、或、與非、或非操作，由門(mén)的類(lèi)型而定），得到一個(gè)含所有基本變量的唯一的樹(shù)表達(dá)式，稱(chēng)為Η( G1)的完備式，記為（或其中，添加括號(hào)的方式為：（1）如果為“與門(mén)”或“或門(mén)”，除了樹(shù)的頂節(jié)點(diǎn)不添加括號(hào)外，其余門(mén)節(jié)點(diǎn)展開(kāi)必添加括號(hào)；（2）如果為“與非門(mén)”或“或非門(mén)”，其余門(mén)節(jié)點(diǎn)展開(kāi)必添加括號(hào)后加“非”。

圖1 功能樹(shù)的展開(kāi)及其邏輯簡(jiǎn)化

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

2.1 與或非功能樹(shù)無(wú)損簡(jiǎn)化的定義

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

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

命題1刻畫(huà)了功能樹(shù)的節(jié)點(diǎn)數(shù)與對(duì)應(yīng)的完備式的廣義秩之間的關(guān)系，這樣就把功能樹(shù)的簡(jiǎn)化轉(zhuǎn)化到了對(duì)命題公式的處理上了。構(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 對(duì)于公式 A ∈ F( S)，若對(duì)于B ∈ F( SA)滿(mǎn)足 B ≤WA，則B稱(chēng)為A的N-簡(jiǎn)化。若 B ＜WA，則B稱(chēng)為A的真N-簡(jiǎn)化。注意到這里采用 B ∈ F( SA)的限制，是因?yàn)閷?shí)際的簡(jiǎn)化過(guò)程中，不可能在簡(jiǎn)化時(shí)引入原簡(jiǎn)化對(duì)象外的變量。同時(shí)，這里假定所做的簡(jiǎn)化均為有意義的，即不會(huì)出現(xiàn)簡(jiǎn)化后新增出 xi∨ xi之類(lèi)的無(wú)意義簡(jiǎn)化現(xiàn)象。

命題邏輯的簡(jiǎn)化理論進(jìn)行N-簡(jiǎn)化的過(guò)程為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

推論 1 對(duì)于功能樹(shù) Η( G1)，必存在一個(gè)AND/OR樹(shù) Η '( G1)，滿(mǎn)足 Η '( G1)≤ Η( G1)。

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

2.3 AND/OR樹(shù)的無(wú)損簡(jiǎn)化定理

以下給出針對(duì) AND/OR樹(shù)的無(wú)損簡(jiǎn)化的若干定理。

定理2 （無(wú)損收縮規(guī)則） 對(duì)于A(yíng)ND/OR樹(shù)Η( G1)，有：（1）Η ( G1)中存在子樹(shù) H( G2)，，則僅對(duì) G2進(jìn)

僅對(duì) G2進(jìn)行操作后：

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

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

例如，功能樹(shù)中具有共同父節(jié)點(diǎn)的幾個(gè)孩子節(jié)點(diǎn)對(duì)應(yīng)同一個(gè)基本變量 xi時(shí)，則可進(jìn)行無(wú)損收縮。

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

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

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

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

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

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

類(lèi)似地，可以證明定理4、5和6：

定理 4 對(duì)于 AND/OR樹(shù) Η( G )中的門(mén)

1，則對(duì)于刪除以 G 為頂?shù)淖訕?shù)得到

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

11

定理5 對(duì)于OR-AND交錯(cuò)樹(shù) Η( G )中的

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

定理6 對(duì)于OR-AND交錯(cuò)樹(shù) Η( G )中的

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

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

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

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

定理7 （無(wú)損提取規(guī)則） 對(duì)于A(yíng)ND/OR樹(shù)Η( G1)中的門(mén) G2，其孩子門(mén)節(jié)點(diǎn)中有 G3, G4滿(mǎn)足：，則

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

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

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

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

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

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

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

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

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

Step 3 Is_Simplified = false。

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

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

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

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

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

Step 9 轉(zhuǎn)Step2。

Step 10 結(jié)束。

3 實(shí) 例

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

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

則直接得到的析取項(xiàng)（即初始解）只有5項(xiàng)。

而對(duì)于經(jīng)過(guò)無(wú)損簡(jiǎn)化后的最終功能樹(shù)（圖4），

對(duì)其進(jìn)行計(jì)算，得

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

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

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

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

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

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

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

4 總 結(jié)

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

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

[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è)計(jì)支持的概念設(shè)計(jì)產(chǎn)品模型[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002, 14(7): 632-636.

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

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

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

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

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

[11] 唐益明, 劉曉平. 與或非功能樹(shù)的功能集族求解方法[J]. 工程圖學(xué)學(xué)報(bào), 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ì)算機(jī)輔助創(chuàng)新原型系統(tǒng)的研究與實(shí)現(xiàn)[J]. 工程圖學(xué)學(xué)報(bào), 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] 路 強(qiáng), 劉曉平. 基于布爾代數(shù)的功能樹(shù)簡(jiǎn)化研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 32(7): 1025-1029.

[16] 唐益明, 劉曉平. 與或功能樹(shù)的無(wú)損簡(jiǎn)化方法[J].圖學(xué)學(xué)報(bào), 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é)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61203077，41076120，61105076，61070124，60890075）中國(guó)博士后科學(xué)基金資助項(xiàng)目（2012M521218）；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資助項(xiàng)目（2012HGQC0011，2012HGCX0001，2012HGBZ0639）

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

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