与或非功能树的无损简化策略

唐益明，刘晓平

（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