使用 Z3 SMT 解决谓词演算问题
Solving predicate calculus problems with Z3 SMT
我想使用 Z3 来解决用原子（符号）、集合、谓词和一阶逻辑最自然地表达的问题。例如（在伪代码中）：
A = {a1, a2, a3, ...} # A is a set
B = {b1, b2, b3...}
C = {c1, c2, c3...}
def p = (a:A, b:B, c:C) -> Bool # p is unspecified predicate
def q = (a:A, b:B, c:C) -> Bool
# Predicates can be defined in terms of other predicates:
def teaches = (a:A, b:B) -> there_exists c:C
such_that [ p(a, b, c) OR q(a, b, c) ]
constraint1 = forall b:B there_exists a:A
such_that teaches(a, b)
solve(constraint1)
在 Z3（或其他 SMT）中表达原子、集合、谓词、关系和一阶量词的好方法是什么？
这有标准的成语吗？必须手动完成吗？是否有可以转换它们的翻译库（不一定特定于 Z3）？
我相信 Alloy 使用 SMT 来实现谓词逻辑和关系，但 Alloy 似乎更多地设计用于交互式使用以探索模型的一致性，而不是寻找问题的具体解决方案。
"Alloy 似乎更多地设计用于交互式使用以探索模型的一致性，而不是为问题找到特定的解决方案。"
恕我直言，Alloy 在验证您自己的思维方式时表现出色。您对某些东西进行建模，通过对多个实例的可视化，您有时会意识到您建模的内容并不完全是您所希望的。
从这个意义上说，我同意你的看法。
然而，Alloy 也可用于寻找问题的具体解决方案。您可以使用约束重载模型，以便只能找到一个实例（即您的解决方案）。
当您的域 space 保持相对较小时，它也能很好地工作。
这是翻译成 Alloy 的模型：
sig A,B,C{}
pred teaches(a:A,b:B) {
some c:C | a->b->c in REL.q or a->b->c in REL.p}
// I'm a bit rusted, so .. that's my unelegant take on defining an "undefined predicate"
one sig REL {
q: A->B ->C,
p: A->B->C
}
fact constraint1 {
all b:B | some a:A | teaches[a,b]
}
run{}
如果您想自己定义集合 A、B、C 中的原子并在谓词中引用它们，您总是可以按如下方式过度约束此模型：
abstract sig A,B,C{}
one sig A1,A2 extends A{}
one sig B1 extends B{}
one sig C1,C2,C3 extends C{}
pred teaches(a:A,b:B) {
some c:C | a->b->c in REL.q or a->b->c in REL.p}
one sig REL {
q: A->B ->C,
p: A->B->C
}{
// here you could for example define the content of p and q yourself
q= A1->B1->C2 + A2 ->B1->C3
p= A1->B1->C3 + A1 ->B1->C2
}
fact constraint1 {
all b:B | some a:A | teaches[a,b]
}
run{}
在 SMTLib 中建模谓词逻辑确实是可能的；尽管与 Isabelle/HOL 等常规定理证明器相比，它可能有点麻烦。解释结果可能需要相当多的眯眼。
话虽如此，这里是使用 SMTLib 对示例问题的直接编码：
(declare-sort A)
(declare-sort B)
(declare-sort C)
(declare-fun q (A B C) Bool)
(declare-fun p (A B C) Bool)
(assert (forall ((b B))
(exists ((a A))
(exists ((c C)) (or (p a b c) (q a b c))))))
(check-sat)
(get-model)
一些注意事项：
declare-sort 创建一个未解释的排序。它本质上是一组非空值。 （也可以是无限的，没有基数假设，除了它不是空的。）对于你的具体问题，这种类型实际上是什么似乎并不重要，因为你没有使用它的任何一种直接元素。如果这样做，您可能还想尝试“声明的”排序，即数据类型声明。这可以是一个枚举，或者更复杂的东西；取决于问题。对于当前提出的问题，未解释的排序就可以了。
declare-fun 告诉求解器存在一个具有该名称和签名的未解释函数。但除此之外，它既不定义它，也不以任何方式限制它。您可以添加关于它们的“公理”以更具体地说明它们的行为方式。
支持量词，正如您在 forall 和 exists 中看到的 constraint1 的编码方式一样。请注意，SMTLib 不适合代码重用，并且通常在更高级别的绑定中编程。 （提供了来自 C/C++/Java/Python/Scala/O'Caml/Haskell 等的绑定，具有类似但不同程度的支持和功能。）否则，它应该很容易阅读。
我们最终发出 check-sat 和 get-model，要求求解器创建一个满足所有断言约束的 Universe。如果是这样，它会打印 sat 并且会有一个模型。否则，如果没有这样的宇宙，它会打印 unsat ；或者它也可以打印 unknown （或永远循环！）如果它不能决定。 SMT 求解器很难处理量词的使用，大量使用量词无疑会导致 unknown 作为答案。这是一阶谓词演算的半可判定性的固有局限性。
当我通过 z3 运行 这个规范时，我得到：
sat
(
;; universe for A:
;; A!val!1 A!val!0
;; -----------
;; definitions for universe elements:
(declare-fun A!val!1 () A)
(declare-fun A!val!0 () A)
;; cardinality constraint:
(forall ((x A)) (or (= x A!val!1) (= x A!val!0)))
;; -----------
;; universe for B:
;; B!val!0
;; -----------
;; definitions for universe elements:
(declare-fun B!val!0 () B)
;; cardinality constraint:
(forall ((x B)) (= x B!val!0))
;; -----------
;; universe for C:
;; C!val!0 C!val!1
;; -----------
;; definitions for universe elements:
(declare-fun C!val!0 () C)
(declare-fun C!val!1 () C)
;; cardinality constraint:
(forall ((x C)) (or (= x C!val!0) (= x C!val!1)))
;; -----------
(define-fun q ((x!0 A) (x!1 B) (x!2 C)) Bool
(and (= x!0 A!val!0) (= x!2 C!val!0)))
(define-fun p ((x!0 A) (x!1 B) (x!2 C)) Bool
false)
)
这需要眯着眼睛才能完全理解。第一组值告诉您求解器如何为未解释的排序 A、B 和 C 构建模型；具有见证元素和基数约束。大多数情况下您可以忽略这一部分，尽管它确实包含有用的信息。例如，它告诉我们 A 是一个包含两个元素（名为 A!val!0 和 A!val!1）的集合，C 也是，而 B 只有一个元素。根据您的限制，您将获得不同的元素集。
对于p，我们看到：
(define-fun p ((x!0 A) (x!1 B) (x!2 C)) Bool
false)
这意味着 p 总是 False；即，无论传递给它的参数是什么，它都是空集。
对于 q 我们得到：
(define-fun q ((x!0 A) (x!1 B) (x!2 C)) Bool
(and (= x!0 A!val!0) (= x!2 C!val!0)))
让我们更简单地重写一下：
q (a, b, c) = a == A0 && c == C0
其中 A0 和 C0 分别是 A 和 C 类别的成员；请参阅上面的排序声明。所以，只要 a 是 A0，c 是 C0，它就说 q 是 True，而 [=51 是什么并不重要=]是。
您可以说服自己这个模型确实满足您想要的约束条件。
综上所述；在 z3 中对这些问题进行建模确实是可能的，尽管有点笨拙并且大量使用量词会使求解器永远循环或 return unknown。解释输出可能有点麻烦，但您会意识到模型将遵循类似的模式：首先是未解释的排序，然后是谓词的定义。
旁注
正如我提到的，在 SMTLib 中对 z3 进行编程既麻烦又容易出错。这是使用 Python 接口完成的相同程序：
from z3 import *
A = DeclareSort('A')
B = DeclareSort('B')
C = DeclareSort('C')
p = Function('p', A, B, C, BoolSort())
q = Function('q', A, B, C, BoolSort())
dummyA = Const('dummyA', A)
dummyB = Const('dummyB', B)
dummyC = Const('dummyC', C)
def teaches(a, b):
return Exists([dummyC], Or(p(a, b, dummyC), q(a, b, dummyC)))
constraint1 = ForAll([dummyB], Exists([dummyA], teaches(dummyA, dummyB)))
s = Solver()
s.add(constraint1)
print(s.check())
print(s.model())
这也有一些特殊之处，但如果您选择在 Python 中对 z3 进行编程，希望它能为您的探索提供一个起点。这是输出：
sat
[p = [else -> And(Var(0) == A!val!0, Var(2) == C!val!0)],
q = [else -> False]]
它与 SMTLib 输出具有完全相同的信息，尽管写法略有不同。
函数定义样式
请注意，我们将 teaches 定义为常规 Python 函数。这是 z3py 编程中的常用风格，因为它生成的表达式会在调用时被替换。您也可以创建一个 z3 函数，如下所示：
teaches = Function('teaches', A, B, BoolSort())
s.add(ForAll([dummyA, dummyB],
teaches(dummyA, dummyB) == Exists([dummyC], Or(p(dummyA, dummyB, dummyC), q(dummyA, dummyB, dummyC)))))
请注意，这种定义方式将在内部依赖量词实例化，而不是 SMTLib 的一般函数定义工具。因此，您通常应该更喜欢 python 函数样式，因为它转化为“更简单”的内部结构。总体上定义和使用起来也容易得多。
您需要 z3 函数定义样式的一种情况是，如果您定义的函数是递归的并且它的终止依赖于符号参数。有关此的讨论，请参阅：
我想使用 Z3 来解决用原子（符号）、集合、谓词和一阶逻辑最自然地表达的问题。例如（在伪代码中）：
A = {a1, a2, a3, ...} # A is a set
B = {b1, b2, b3...}
C = {c1, c2, c3...}
def p = (a:A, b:B, c:C) -> Bool # p is unspecified predicate
def q = (a:A, b:B, c:C) -> Bool
# Predicates can be defined in terms of other predicates:
def teaches = (a:A, b:B) -> there_exists c:C
such_that [ p(a, b, c) OR q(a, b, c) ]
constraint1 = forall b:B there_exists a:A
such_that teaches(a, b)
solve(constraint1)
在 Z3（或其他 SMT）中表达原子、集合、谓词、关系和一阶量词的好方法是什么？
这有标准的成语吗？必须手动完成吗？是否有可以转换它们的翻译库（不一定特定于 Z3）？
我相信 Alloy 使用 SMT 来实现谓词逻辑和关系，但 Alloy 似乎更多地设计用于交互式使用以探索模型的一致性，而不是寻找问题的具体解决方案。
"Alloy 似乎更多地设计用于交互式使用以探索模型的一致性，而不是为问题找到特定的解决方案。"
恕我直言，Alloy 在验证您自己的思维方式时表现出色。您对某些东西进行建模，通过对多个实例的可视化，您有时会意识到您建模的内容并不完全是您所希望的。 从这个意义上说，我同意你的看法。
然而，Alloy 也可用于寻找问题的具体解决方案。您可以使用约束重载模型，以便只能找到一个实例（即您的解决方案）。 当您的域 space 保持相对较小时，它也能很好地工作。
这是翻译成 Alloy 的模型：
sig A,B,C{}
pred teaches(a:A,b:B) {
some c:C | a->b->c in REL.q or a->b->c in REL.p}
// I'm a bit rusted, so .. that's my unelegant take on defining an "undefined predicate"
one sig REL {
q: A->B ->C,
p: A->B->C
}
fact constraint1 {
all b:B | some a:A | teaches[a,b]
}
run{}
如果您想自己定义集合 A、B、C 中的原子并在谓词中引用它们，您总是可以按如下方式过度约束此模型：
abstract sig A,B,C{}
one sig A1,A2 extends A{}
one sig B1 extends B{}
one sig C1,C2,C3 extends C{}
pred teaches(a:A,b:B) {
some c:C | a->b->c in REL.q or a->b->c in REL.p}
one sig REL {
q: A->B ->C,
p: A->B->C
}{
// here you could for example define the content of p and q yourself
q= A1->B1->C2 + A2 ->B1->C3
p= A1->B1->C3 + A1 ->B1->C2
}
fact constraint1 {
all b:B | some a:A | teaches[a,b]
}
run{}
在 SMTLib 中建模谓词逻辑确实是可能的；尽管与 Isabelle/HOL 等常规定理证明器相比，它可能有点麻烦。解释结果可能需要相当多的眯眼。
话虽如此，这里是使用 SMTLib 对示例问题的直接编码：
(declare-sort A)
(declare-sort B)
(declare-sort C)
(declare-fun q (A B C) Bool)
(declare-fun p (A B C) Bool)
(assert (forall ((b B))
(exists ((a A))
(exists ((c C)) (or (p a b c) (q a b c))))))
(check-sat)
(get-model)
一些注意事项：
declare-sort创建一个未解释的排序。它本质上是一组非空值。 （也可以是无限的，没有基数假设，除了它不是空的。）对于你的具体问题，这种类型实际上是什么似乎并不重要，因为你没有使用它的任何一种直接元素。如果这样做，您可能还想尝试“声明的”排序，即数据类型声明。这可以是一个枚举，或者更复杂的东西；取决于问题。对于当前提出的问题，未解释的排序就可以了。declare-fun告诉求解器存在一个具有该名称和签名的未解释函数。但除此之外，它既不定义它，也不以任何方式限制它。您可以添加关于它们的“公理”以更具体地说明它们的行为方式。支持量词，正如您在
forall和exists中看到的constraint1的编码方式一样。请注意，SMTLib 不适合代码重用，并且通常在更高级别的绑定中编程。 （提供了来自 C/C++/Java/Python/Scala/O'Caml/Haskell 等的绑定，具有类似但不同程度的支持和功能。）否则，它应该很容易阅读。我们最终发出
check-sat和get-model，要求求解器创建一个满足所有断言约束的 Universe。如果是这样，它会打印sat并且会有一个模型。否则，如果没有这样的宇宙，它会打印unsat；或者它也可以打印unknown（或永远循环！）如果它不能决定。 SMT 求解器很难处理量词的使用，大量使用量词无疑会导致unknown作为答案。这是一阶谓词演算的半可判定性的固有局限性。
当我通过 z3 运行 这个规范时，我得到：
sat
(
;; universe for A:
;; A!val!1 A!val!0
;; -----------
;; definitions for universe elements:
(declare-fun A!val!1 () A)
(declare-fun A!val!0 () A)
;; cardinality constraint:
(forall ((x A)) (or (= x A!val!1) (= x A!val!0)))
;; -----------
;; universe for B:
;; B!val!0
;; -----------
;; definitions for universe elements:
(declare-fun B!val!0 () B)
;; cardinality constraint:
(forall ((x B)) (= x B!val!0))
;; -----------
;; universe for C:
;; C!val!0 C!val!1
;; -----------
;; definitions for universe elements:
(declare-fun C!val!0 () C)
(declare-fun C!val!1 () C)
;; cardinality constraint:
(forall ((x C)) (or (= x C!val!0) (= x C!val!1)))
;; -----------
(define-fun q ((x!0 A) (x!1 B) (x!2 C)) Bool
(and (= x!0 A!val!0) (= x!2 C!val!0)))
(define-fun p ((x!0 A) (x!1 B) (x!2 C)) Bool
false)
)
这需要眯着眼睛才能完全理解。第一组值告诉您求解器如何为未解释的排序 A、B 和 C 构建模型；具有见证元素和基数约束。大多数情况下您可以忽略这一部分，尽管它确实包含有用的信息。例如，它告诉我们 A 是一个包含两个元素（名为 A!val!0 和 A!val!1）的集合，C 也是，而 B 只有一个元素。根据您的限制，您将获得不同的元素集。
对于p，我们看到：
(define-fun p ((x!0 A) (x!1 B) (x!2 C)) Bool
false)
这意味着 p 总是 False；即，无论传递给它的参数是什么，它都是空集。
对于 q 我们得到：
(define-fun q ((x!0 A) (x!1 B) (x!2 C)) Bool
(and (= x!0 A!val!0) (= x!2 C!val!0)))
让我们更简单地重写一下：
q (a, b, c) = a == A0 && c == C0
其中 A0 和 C0 分别是 A 和 C 类别的成员；请参阅上面的排序声明。所以，只要 a 是 A0，c 是 C0，它就说 q 是 True，而 [=51 是什么并不重要=]是。
您可以说服自己这个模型确实满足您想要的约束条件。
综上所述；在 z3 中对这些问题进行建模确实是可能的，尽管有点笨拙并且大量使用量词会使求解器永远循环或 return unknown。解释输出可能有点麻烦，但您会意识到模型将遵循类似的模式：首先是未解释的排序，然后是谓词的定义。
旁注
正如我提到的，在 SMTLib 中对 z3 进行编程既麻烦又容易出错。这是使用 Python 接口完成的相同程序：
from z3 import *
A = DeclareSort('A')
B = DeclareSort('B')
C = DeclareSort('C')
p = Function('p', A, B, C, BoolSort())
q = Function('q', A, B, C, BoolSort())
dummyA = Const('dummyA', A)
dummyB = Const('dummyB', B)
dummyC = Const('dummyC', C)
def teaches(a, b):
return Exists([dummyC], Or(p(a, b, dummyC), q(a, b, dummyC)))
constraint1 = ForAll([dummyB], Exists([dummyA], teaches(dummyA, dummyB)))
s = Solver()
s.add(constraint1)
print(s.check())
print(s.model())
这也有一些特殊之处，但如果您选择在 Python 中对 z3 进行编程，希望它能为您的探索提供一个起点。这是输出：
sat
[p = [else -> And(Var(0) == A!val!0, Var(2) == C!val!0)],
q = [else -> False]]
它与 SMTLib 输出具有完全相同的信息，尽管写法略有不同。
函数定义样式
请注意，我们将 teaches 定义为常规 Python 函数。这是 z3py 编程中的常用风格，因为它生成的表达式会在调用时被替换。您也可以创建一个 z3 函数，如下所示：
teaches = Function('teaches', A, B, BoolSort())
s.add(ForAll([dummyA, dummyB],
teaches(dummyA, dummyB) == Exists([dummyC], Or(p(dummyA, dummyB, dummyC), q(dummyA, dummyB, dummyC)))))
请注意，这种定义方式将在内部依赖量词实例化，而不是 SMTLib 的一般函数定义工具。因此，您通常应该更喜欢 python 函数样式，因为它转化为“更简单”的内部结构。总体上定义和使用起来也容易得多。
您需要 z3 函数定义样式的一种情况是，如果您定义的函数是递归的并且它的终止依赖于符号参数。有关此的讨论，请参阅：