8 智能系统学报 第9卷 法等是常用的转换方法。 知识编译算法SPL-KCER将任意给定的可能性知识 Wu等42]利用破坏性方法直接把扩展规则方法 库编译成EPPCCCL理论，然后利用上述的可能性 推广到模态逻辑中，提出了模态系统K中的破坏性 扩展规则方法可以在多项式时间内完成推理。与可 扩展规则方法DMKER(destructive extension rule in 能性归结方法相比，该方法在有些情况下具有独特 modal logic K),该方法将利用化简规则进行简化和 的优势，当待编译的可能性知识库本身就是一个 利用扩展规则判定不可满足性结合在一起，交替进 EPPCCCL理论，新方法编译后的结果就是它本身， 行。DMKER算法能够快速地证明模态系统K中的 而可能性归结方法的结果一般为指数级别的。 所有公理和四类标准的benchmark问题。该方法继 3.5多值逻辑 承了扩展规则方法的优点，当存在较多的互补公式 经典逻辑对知识的表示能力是有限的，多值逻 时，模态逻辑推理的效率明显提高。此外，Wu等) 辑具有更强的表达能力。在许多领域中，不仅需要 分别将关系转换方法、函数转换方法与扩展规则方 布尔变量，而且需要多值变量来表示实体的一些属 法相结合，提出了关系扩展规则方法MRER(modal 性，直接向经典的命题公式中加入多值变量可能会 relational extension rule)、连续模态逻辑中的函数扩 增加原始问题的求解难度，笔者将扩展规则推广到 展规则方法MFER(modal functional extension rule) 多值逻辑中，提出了一种基于扩展规则的多值推理 和非连续模态逻辑的广义函数扩展规则方法GM- 方法[6。这里关注的是标记逻辑，因为任意一个多 FER(general modal functional extension rule)o 值逻辑知识库，都可以找到一个与之等价的标记逻 3.4可能性逻辑 辑知识库，反之亦然。文中定义了标记扩展规则以 可能性逻辑是适用于给定知识中含有不确定因 及最大项的概念，并且利用容斥原理来计算给定标 素或者给定知识不完全一致的情况下进行知识表示 记子句集所扩展出的最大项个数来判定标记子句集 和推理的逻辑。在可能性逻辑中，最主要和最基本 的可满足性。在此基础上定义了标记EPCCL(s 的推理规则是基于Dubois和Prade提出的可能性归 EPCCL)理论，即对于一个带有标记文字的子句集， 结原理[]。笔者将扩展规则方法引入到可能性逻 其中每一对子句都含有互补文字，或者是互补的布 辑中)，定义了可能性包含规则和可能性扩展规 尔文字，或者是互补的标记文字，并且证明s-EPCCL 则，并且提出了基于可能性扩展规则的推理方法，即 理论是在标记可满足可控制类和标记蕴含可控制类 利用可能性扩展规则计算可能性知识库Σ的不一 中，因此，s-EPCCL理论可以作为多值逻辑知识编译 致程度。该方法的基本思想是：首先按照可能性子 的目标语言。笔者提出了一种基于扩展规则的多值 句的权值α对可能性知识库Σ，中的子句从小到大 知识编译方法，该方法首先利用SKCER算法将标记 进行排序，然后顺次考虑Σ的不同α截集Σ。，利用 知识库编译成一个与之等价的s-EPCCL理论，然后 公式ER算法判断Σ的可满足性：如果∑，不可满 利用上述基于扩展规则的多值推理方法可以在多项 足，则三的不一致程度为α，否则继续考虑下一截 式时间内回答查询。 集。与命题逻辑中的扩展规则方法ER类似，对于 4 互补因子较高的问题可能性扩展规则方法效率较 待解决的问题 高，而对于互补因子较低的问题可能性归结方法的 扩展规则方法以其独特的优势使之成为自动推 效率较高，因此，可能性扩展规则方法可以看作是任 理的重要方法之一，目前还存在一些未解决的问题， 何可能性归结方法的补方法。 值得研究人员进一步探讨。 进一步，笔者扩展了经典逻辑的蕴含可控制类 1)如何利用扩展规则方法求解隐蔽集。 和可满足可控制类的概念，定义了可能性蕴含可控 隐蔽集是SAT问题的一个重要结构，与求解难 制类和不一致性程度计算可控制类。在可能性扩展 度有很大的关系，隐蔽集的选择使得剩下的问题能 规则的基础上，笔者提出了EPPCCCL(each pair of 在多项式时间内求解。由于利用扩展规则方法和 possibilistic clauses contains complementary literals) EPCCL理论是可以在多项式时间内判定可满足性 论，即任意2个可能性子句的经典投影都含有互补 的，如何求解隐蔽集使得剩下的问题都是EPCCL理 对的可能性子句集，证明了该理论是在最优化形式 论，是需要进一步研究的问题。 蕴含可控制类和不一致性程度计算可控制类中的， 2)如何选择ER算法的子句C使之与骨架集 可以作为可能性知识编译的目标语言，并且给出了 相对应。 一种可能性知识编译方法。该方法首先利用可能性 骨架集也是SAT问题中的一个重要结构，它是法等是常用的转换方法。 Ｗｕ 等［４２］利用破坏性方法直接把扩展规则方法 推广到模态逻辑中，提出了模态系统 Ｋ 中的破坏性 扩展规则方法 ＤＭＫＥＲ（ ｄｅｓｔｒｕｃｔｉｖｅ ｅｘｔｅｎｓｉｏｎ ｒｕｌｅ ｉｎ ｍｏｄａｌ ｌｏｇｉｃ Ｋ），该方法将利用化简规则进行简化和 利用扩展规则判定不可满足性结合在一起，交替进 行。 ＤＭＫＥＲ 算法能够快速地证明模态系统 Ｋ 中的 所有公理和四类标准的 ｂｅｎｃｈｍａｒｋ 问题。 该方法继 承了扩展规则方法的优点，当存在较多的互补公式 时，模态逻辑推理的效率明显提高。 此外，Ｗｕ 等［４３］ 分别将关系转换方法、函数转换方法与扩展规则方 法相结合，提出了关系扩展规则方法 ＭＲＥＲ（ｍｏｄａｌ ｒｅｌａｔｉｏｎａｌ ｅｘｔｅｎｓｉｏｎ ｒｕｌｅ）、连续模态逻辑中的函数扩 展规则方法 ＭＦＥＲ（ｍｏｄａｌ ｆｕｎｃｔｉｏｎａｌ ｅｘｔｅｎｓｉｏｎ ｒｕｌｅ） 和非连续模态逻辑的广义函数扩展规则方法 ＧＭ⁃ ＦＥＲ（ｇｅｎｅｒａｌ ｍｏｄａｌ ｆｕｎｃｔｉｏｎａｌ ｅｘｔｅｎｓｉｏｎ ｒｕｌｅ）。 ３．４ 可能性逻辑 可能性逻辑是适用于给定知识中含有不确定因 素或者给定知识不完全一致的情况下进行知识表示 和推理的逻辑。 在可能性逻辑中，最主要和最基本 的推理规则是基于 Ｄｕｂｏｉｓ 和 Ｐｒａｄｅ 提出的可能性归 结原理［４４］ 。 笔者将扩展规则方法引入到可能性逻 辑中［４５］ ，定义了可能性包含规则和可能性扩展规 则，并且提出了基于可能性扩展规则的推理方法，即 利用可能性扩展规则计算可能性知识库 Σ 的不一 致程度。 该方法的基本思想是：首先按照可能性子 句的权值 α 对可能性知识库 Σｐ中的子句从小到大 进行排序，然后顺次考虑 Σｐ的不同 α 截集 Σα ，利用 公式 ＥＲ 算法判断 Σα 的可满足性：如果 Σα 不可满 足，则 Σｐ的不一致程度为 α，否则继续考虑下一截 集。 与命题逻辑中的扩展规则方法 ＥＲ 类似，对于 互补因子较高的问题可能性扩展规则方法效率较 高，而对于互补因子较低的问题可能性归结方法的 效率较高，因此，可能性扩展规则方法可以看作是任 何可能性归结方法的补方法。 进一步，笔者扩展了经典逻辑的蕴含可控制类 和可满足可控制类的概念，定义了可能性蕴含可控 制类和不一致性程度计算可控制类。 在可能性扩展 规则的基础上，笔者提出了 ＥＰＰＣＣＣＬ（ ｅａｃｈ ｐａｉｒ ｏｆ ｐｏｓｓｉｂｉｌｉｓｔｉｃ ｃｌａｕｓｅｓ ｃｏｎｔａｉｎｓ ｃｏｍｐｌｅｍｅｎｔａｒｙ ｌｉｔｅｒａｌｓ）理 论，即任意 ２ 个可能性子句的经典投影都含有互补 对的可能性子句集，证明了该理论是在最优化形式 蕴含可控制类和不一致性程度计算可控制类中的， 可以作为可能性知识编译的目标语言，并且给出了 一种可能性知识编译方法。 该方法首先利用可能性 知识编译算法 ＳＰＬ⁃ＫＣＥＲ 将任意给定的可能性知识 库编译成 ＥＰＰＣＣＣＬ 理论，然后利用上述的可能性 扩展规则方法可以在多项式时间内完成推理。 与可 能性归结方法相比，该方法在有些情况下具有独特 的优势，当待编译的可能性知识库本身就是一个 ＥＰＰＣＣＣＬ 理论，新方法编译后的结果就是它本身， 而可能性归结方法的结果一般为指数级别的。 ３．５ 多值逻辑 经典逻辑对知识的表示能力是有限的，多值逻 辑具有更强的表达能力。 在许多领域中，不仅需要 布尔变量，而且需要多值变量来表示实体的一些属 性，直接向经典的命题公式中加入多值变量可能会 增加原始问题的求解难度，笔者将扩展规则推广到 多值逻辑中，提出了一种基于扩展规则的多值推理 方法［４６］ 。 这里关注的是标记逻辑，因为任意一个多 值逻辑知识库，都可以找到一个与之等价的标记逻 辑知识库，反之亦然。 文中定义了标记扩展规则以 及最大项的概念，并且利用容斥原理来计算给定标 记子句集所扩展出的最大项个数来判定标记子句集 的可满足性。 在此基础上定义了标记 ＥＰＣＣＬ （ ｓ⁃ ＥＰＣＣＬ）理论，即对于一个带有标记文字的子句集， 其中每一对子句都含有互补文字，或者是互补的布 尔文字，或者是互补的标记文字，并且证明 ｓ⁃ＥＰＣＣＬ 理论是在标记可满足可控制类和标记蕴含可控制类 中，因此，ｓ⁃ＥＰＣＣＬ 理论可以作为多值逻辑知识编译 的目标语言。 笔者提出了一种基于扩展规则的多值 知识编译方法，该方法首先利用 ＳＫＣＥＲ 算法将标记 知识库编译成一个与之等价的 ｓ⁃ＥＰＣＣＬ 理论，然后 利用上述基于扩展规则的多值推理方法可以在多项 式时间内回答查询。 ４ 待解决的问题 扩展规则方法以其独特的优势使之成为自动推 理的重要方法之一，目前还存在一些未解决的问题， 值得研究人员进一步探讨。 １）如何利用扩展规则方法求解隐蔽集。 隐蔽集是 ＳＡＴ 问题的一个重要结构，与求解难 度有很大的关系，隐蔽集的选择使得剩下的问题能 在多项式时间内求解。 由于利用扩展规则方法和 ＥＰＣＣＬ 理论是可以在多项式时间内判定可满足性 的，如何求解隐蔽集使得剩下的问题都是 ＥＰＣＣＬ 理 论，是需要进一步研究的问题。 ２）如何选择 ＩＥＲ 算法的子句 Ｃ 使之与骨架集 相对应。 骨架集也是 ＳＡＴ 问题中的一个重要结构，它是 ·８· 智 能 系 统 学 报 第 ９ 卷