命题知识库演化中的新知识特征（英文）

摘要

逻辑差概念在表征基于逻辑的知识库中起到重要作用，这些知识库持续受到动态变化的影响，它们之间存在实质性差异。这一概念与遗忘密切相关，它在各种逻辑中得到了广泛探讨。针对命题理论的相关符号，提出了3种差概念——逻辑差异、子句差异和素子句差异，以分别捕获逻辑推理、子句推理和素子句推理的差异；研究了它们的性质和计算复杂性。结果表明，涉及逻辑差的各种决策问题在多项式层次结构中比相应的可满足性问题高一个层次，除了2-CNF理论，其相关决策问题是易处理的。随机3-CNF、2-CNF和Horn理论的大量实验结果揭示了子句差和素子句差的一些有趣现象：在随机3-CNF理论和2-CNF理论中，子句和素子句差的子句数量都表现出与它们的可满足性类似的相变特征。然而，在随机Horn理论中，尽管子句差的子句数量表现出与其可满足性类似的相变，但素子句差的子句数量与子句差情形十分不同，这些结果揭示了随机命题知识库演化中其可满足性相变现象的新特征：在相变阈值附近的知识库演变会产生更多的差异。

关键词

逻辑差 / 子句差 / 素子句差 / 计算复杂性 / 相变 / 知识管理