解决命题逻辑规则集中的特定组合（SAT Solver）
Solve specific combination in propositional logic rule set (SAT Solver)
在汽车行业，当您购买汽车时，有数千种不同的组件可供选择。并非每个组件都是可组合的，因此对于每辆汽车，存在许多以命题逻辑表达的规则。在我的例子中，每辆车都有 2000 到 4000 条规则。
它们看起来像这样：
- A → B ∨ C ∨ D
- C → ¬F
- F∧G→D
- ...
其中“∧”="and"/“∨”="or"/“¬”="not"/“→”="implication".
借助工具 "limboole" (http://fmv.jku.at/limboole/)，我能够将命题逻辑表达式转换为合取范式 (CNF)。如果我必须使用 SAT 求解器，这是必需的。
现在，我想检查规则集中特定组件的可构建性可行性。例如，对于以下每个表达式或组合，我想检查它们在规则集中是否可行。
- (A) ∧ (B)
- (A) ∧ (C ∨ F)
- (B∨G)
- ...
我的问题是如何解决这个问题。我之前问过类似的问题（Tool to solve propositional logic / boolean expressions (SAT Solver?)），但关注点不同，现在又卡住了。或者我只是不明白。
一个选项是使用规则集的 ALLSAT 方法计算所有解决方案。然后我可以检查每个组合是否是任何解决方案的一部分。如果是，我可以推导出这个具体的组合是可行的。
另一种选择是，我将组合添加到规则集中，然后 运行 一个普通的 SAT 求解器。但是我必须为我要检查的每个表达式执行此操作。
您认为解决此问题的最优雅或最简单的方法是什么？
我所知道的最好的方法是使用 "incremental solving under assumptions" 技术。它的动机与您遇到的相同问题有关：具有一些共同子公式的多个 SAT 实例（CNF 公式）。
形式上，您在 CNF 中有一些核心布尔公式 C。并且您有一组假设 {A_i}, i=1..n，其中 A_i 也是 CNF 中的布尔公式。
在第 0 步，您向求解器提供您的核心公式 C。它试图解决它，告诉你一个结果并保存它的状态（我们称这个状态为 core-state）。如果公式 C 可满足，则在步骤 i 中，您向求解器提供假设 A_i，它会从 核心状态 继续执行。实际上，它试图求解公式 C ∧ A_i 但不是从头开始。
你可以很容易地找到一堆与这个主题相关的论文，那里有很多信息。此外，您可以检查您最喜欢的 SAT 求解器是否支持此技术。
在汽车行业，当您购买汽车时，有数千种不同的组件可供选择。并非每个组件都是可组合的，因此对于每辆汽车，存在许多以命题逻辑表达的规则。在我的例子中，每辆车都有 2000 到 4000 条规则。
它们看起来像这样：
- A → B ∨ C ∨ D
- C → ¬F
- F∧G→D
- ...
其中“∧”="and"/“∨”="or"/“¬”="not"/“→”="implication".
借助工具 "limboole" (http://fmv.jku.at/limboole/)，我能够将命题逻辑表达式转换为合取范式 (CNF)。如果我必须使用 SAT 求解器，这是必需的。
现在，我想检查规则集中特定组件的可构建性可行性。例如，对于以下每个表达式或组合，我想检查它们在规则集中是否可行。
- (A) ∧ (B)
- (A) ∧ (C ∨ F)
- (B∨G)
- ...
我的问题是如何解决这个问题。我之前问过类似的问题（Tool to solve propositional logic / boolean expressions (SAT Solver?)），但关注点不同，现在又卡住了。或者我只是不明白。
一个选项是使用规则集的 ALLSAT 方法计算所有解决方案。然后我可以检查每个组合是否是任何解决方案的一部分。如果是，我可以推导出这个具体的组合是可行的。
另一种选择是，我将组合添加到规则集中，然后 运行 一个普通的 SAT 求解器。但是我必须为我要检查的每个表达式执行此操作。
您认为解决此问题的最优雅或最简单的方法是什么？
我所知道的最好的方法是使用 "incremental solving under assumptions" 技术。它的动机与您遇到的相同问题有关：具有一些共同子公式的多个 SAT 实例（CNF 公式）。
形式上，您在 CNF 中有一些核心布尔公式 C。并且您有一组假设 {A_i}, i=1..n，其中 A_i 也是 CNF 中的布尔公式。
在第 0 步，您向求解器提供您的核心公式 C。它试图解决它，告诉你一个结果并保存它的状态（我们称这个状态为 core-state）。如果公式 C 可满足，则在步骤 i 中，您向求解器提供假设 A_i，它会从 核心状态 继续执行。实际上，它试图求解公式 C ∧ A_i 但不是从头开始。
你可以很容易地找到一堆与这个主题相关的论文，那里有很多信息。此外，您可以检查您最喜欢的 SAT 求解器是否支持此技术。