Logic Programming with Pseudo-Boolean Constraints
Logic Programming with Pseudo-Boolean Constraints
复制标题
具有伪布尔约束的逻辑编程
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
A. Bockmayr
中科院分区：
文献类型：
--
作者：
A. Bockmayr
布尔限制在各种约束逻辑编程语言中起着重要作用。在本文中，我们考虑了伪树状的约束，即伪树状功能之间的方程式和不平等。假圆形函数是布尔变量的整数值函数，因此是布尔函数的概括。伪树一个功能发生在许多应用领域，尤其是在操作研究中的问题中。与逻辑的一个有趣的联系是，命题逻辑中的推论问题可以转化为线性伪树状优化问题。更一般而言，伪树状约束可以看作是结合约束逻辑编程中两个最重要领域的特定方式：算术和布尔代数。在本文中，我们定义了一个新的约束逻辑编程语言CLP（PB），用于使用伪树状约束来进行逻辑进程。该语言是一般约束逻辑编程语言方案CLP（X）的实例，并继承了所有典型的语义属性。我们表明，任何伪树状约束都有最通用的解决方案，并提供可变的消除算法，用于伪树状统一和无约束的伪树状优化。两种算法都包含Buttner和Simonis的众所周知的布尔统一算法。
Boolean constraints play an important role in various constraint logic programming languages. In this paper we consider pseudo-Boolean constraints, that is equations and inequalities between pseudo-Boolean functions. A pseudoBoolean function is an integer-valued function of Boolean variables and thus a generalization of a Boolean function. Pseudo-Boolean functions occur in many application areas, in particular in problems from operations research. An interesting connection to logic is that inference problems in propositional logic can be translated into linear pseudo-Boolean optimization problems. More generally, pseudo-Boolean constraints can be seen as a particular way of combining two of the most important domains in constraint logic programming: arithmetic and Boolean algebra. In this paper we define a new constraint logic programming language CLP(PB) for logic progamming with pseudo-Boolean constraints. The language is an instance of the general constraint logic programming language scheme CLP(X) and inherits all the typical semantic properties. We show that any pseudo-Boolean constraint has a most general solution and give variable elimination algorithms for pseudo-Boolean unification and unconstrained pseudo-Boolean optimization. Both algorithms subsume the wellknown Boolean unification algorithm of Buttner and Simonis.