如何将一系列数学约束转换为 SAT 或 SMT 问题并得到答案？

Question

我有一组任意的约束。例如：

A, B, C and D are 8-bit integers.

A + B + C + D = 50
(A + B) = 25
(C + D) = 30
A < 10

我可以将其转换为可由 picosat 解决的 SAT 问题（我无法让 minisat 在我的 Mac 上编译），或转换为可由 [=11 解决的 SMT 问题=].为此，我需要：

将这些等式映射到布尔电路中。
将Tseitin变换应用于电路并将其转换为DIMACS格式。

我的问题：

我使用什么工具来转换电路？
电路的文件格式有哪些，常用的有哪些？
我使用什么工具将电路转换为 DIMACS 格式？

Answer 1

概念上

构建电路，然后应用 Tseitin 变换。

您需要将加法运算符和比较运算符表示为布尔逻辑。有一些标准方法可以构建用于二进制补码加法和二进制补码比较的电路。

然后，使用 Tseitin 的转换将其转换为 SAT 实例。

在实践中

使用 SAT 前端将为您进行此转换。 Z3 会为您解决这个问题。 STP 也会如此。（转换有时称为 "bit-blasting"。）

Answer 2

在MiniZinc中，你可以只写一个约束规划模型：

set of int: I8 = 0..255;

var I8: A;
var I8: B;
var I8: C;
var I8: D;

constraint A + B + C + D == 50;

constraint (A + B) = 25;

constraint (C + D) = 30;

constraint A < 10;

solve satisfy;

无法满足示例约束，因为 25 + 30 > 50。

Z3 的 Python 接口将允许以下操作：

from z3 import *
A, B, C, D = Ints('A B C D')
s = Solver()
s.add(A >= 0, A < 256)
s.add(B >= 0, B < 256)
s.add(C >= 0, C < 256)
s.add(A+B+C+D == 50)
s.add((A+B) == 25)
s.add((C+D) == 30)
s.add(A < 10)
print(s.check())
print(s.model())

Answer 3

所以我有一个答案。有一个程序叫做 Sugar: a SAT-based Constraint Solver，它将一系列约束作为 S 表达式，将整个东西转换成 DIMACS 文件，运行s SAT 求解器，然后将 SAT 求解器的结果转换回你的限制的结果。

Sugar 由 Naoyuki Tamura 开发，用于解决数独等数学难题。我发现它使得编写复杂约束和运行它们变得非常简单。

例如，要求 625 的平方根，可以这样做：

(int X 0 625)
(= (* X X) 625)

第一行说X的范围是0到625。第二行说X*X是625。

这可能不像 Z3 那样简单和优雅，但它确实很好用。

如何将一系列数学约束转换为 SAT 或 SMT 问题并得到答案？

How do I convert a series of mathematical constraints into a SAT or a SMT problem and get an answer?

sat-solvers

概念上

在实践中