Optimization Methods in Logic
Optimization Methods in Logic
复制标题
逻辑优化方法
DOI：
10.1017/cbo9780511780448.008
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Hammer
中科院分区：
文献类型：
--
作者：
J. Hooker;Y. Crama;P. Hammer
优化至少可以对布尔逻辑做出两个贡献。它的解决方法可以解决推理和可满足性问题，它的分析风格可以揭示易于处理的布尔问题类别，否则可能会被忽视。将优化与逻辑联系起来的关键是提供逻辑公式、数值解释或语义。语法关注逻辑表达式的结构，语义赋予它们意义。例如，布尔语义学专注于捕捉逻辑命题含义的真值函数。举个例子，函数f（x1，x2）由f（0，1）= 0和f（0，0）= f（1，0）= f（1，1）= 1给出，解释表达式x1 <$x <$2，其中0代表“假”，1代表“真”。布尔函数f并没有说明很多关于x1 <$x <$2的意义，但这是设计的。形式逻辑的重点是研究如何仅仅根据命题的形式进行正确的推理。原子x1和x2的意义是无关紧要的，除了可以是真或假的事实。只有“或”和“非”需要解释以达到形式逻辑的目的，函数f表示它们在表达式x1 <$x <$2中的行为。一般来说，逻辑的解释被选择为尽可能精简，以便只反映逻辑表达式的形式属性。然而，为了解决推理和可满足性问题，赋予逻辑表达式更具体的含义可能是有利的。本章介绍了将0和1解释为实际数值的想法，而不仅仅是作为“假”和“真”的标记。布尔值的真值除了有两个真值之外没有任何意义，但是数字0和1从它们在数学中的作用中获得了额外的意义。例如，它们允许布尔表达式被视为不等式，如当x1 <$x <$2被读作x1 +（1 − x2）≥ 1时。这种策略使得线性和0-1规划等优化技术可用于逻辑推理和可满足性问题。此外，它有助于揭示逻辑问题的结构，并引起人们对更容易解决的问题类别的注意。乔治布尔似乎在他的开创性著作《逻辑的数学分析》中给出了逻辑的数值解释，因为他用
Optimization can make at least two contributions to boolean logic. Its solution methods can address inference and satisfiability problems, and its style of analysis can reveal tractable classes of boolean problems that might otherwise have gone unnoticed. They key to linking optimization with logic is to provide logical formulas a numerical interpretation or semantics. While syntax concerns the structure of logical expressions, semantics gives them meaning. Boolean semantics, for instance, focuses on truth functions that capture the meaning of logical propositions. To take an example, the function f(x1, x2) given by f(0, 1) = 0 and f(0, 0) = f(1, 0) = f(1, 1) = 1 interprets the expression x1 ∨ x̄2, where 0 stands for “false” and 1 for “true.” The Boolean function f does not say a great deal about the meaning of x1 ∨ x̄2, but this is by design. The point of formal logic is to investigate how one can reason correctly based solely on the form of propositions. The meaning of the atoms x1 and x2 is irrelevant, aside from the fact either can be true or false. Only the “or” (∨) and the “not” ( ̄) require interpretation for the purposes of formal logic, and the function f indicates how they behave in the expression x1 ∨ x̄2. In general, interpretations of logic are chosen to be as lean as possible in order to reflect only the formal properties of logical expressions. For purposes of solving inference and satisfiability problems, however, it may be advantageous to give logical expressions a more specific meaning. This chapter presents the idea of interpreting 0 and 1 as actual numerical values rather than simply as markers for “false” and “true.” Boolean truth values signify nothing beyond the fact that there are two of them, but the numbers 0 and 1 derive additional meaning from their role in mathematics. For example, they allow Boolean expressions to be regarded as inequalities, as when x1 ∨ x̄2 is read as x1 + (1 − x2) ≥ 1. This maneuver makes such optimization techniques as linear and 0-1 programming available to logical inference and satisfiability problems. In addition it helps to reveal the structure of logical problems and calls attention to classes of problems that are more easily solved. George Boole seems to give a numerical interpretation of logic in his seminal work, The Mathematical Analysis of Logic, since he notates disjunction and conjunction with