部分赋值一阶逻辑公式的条件求值——NP完全性及在特定情况下的求解  

THE CONDITIONAL EVALUATION OF FIRST ORDER LOGIC EXPRESSIONS PARTIALLY ASSIGNED--NP-COMPLETENESS AND THE SOLUTIONS IN SPECIAL SITUATIONS

作　　者：潘久辉[1] 

机构地区：[1]中南矿冶学院计算机科学系

出　　处：《中南矿冶学院学报》1989年第2期204-211,共8页

摘　　要：部分赋值的一阶逻辑公式的条件求值问题是在关系数据库应用,尤其是在分布式环境下应用中经常遇到的问题。此问题在一般意义下的解是NP完全的。本文首先证明此问题的解存在的充要条件,从而推知其NP完全性。然后给出该问题在一种特定情况下的求解方法。The problem of conditional evaluation of first order logic expressions partially assigned frequently occurs in the context of Relational Database Application, especially in the environment of distributed databases. In general, the solution to this problem is NP-complete. This paper gives sufficient and necessary condition for the existence of the solution to the problem, and thus shows its NP-completeness. And also, the methods of solving the problem in some special situations are proposed.

关 键 词：条件求值问题 公式 情况 赋值 特定 证明 一般 NP完全 一阶逻辑 关系数据库 

分 类 号：G633[文化科学—教育学] TP393[自动化与计算机技术—计算机应用技术]