"quantifier free logic" 在 SMT 上下文中意味着什么？
What does "quantifier free logic" mean in SMT context?
即使是最简单的算术 SMT 问题，也需要存在量词来声明符号变量。 ∀ 量词可以通过反转约束变成 ∃。所以，我可以在 QF_* 逻辑中同时使用它们并且它有效。
我认为，"quantifier free" 对此类 SMT 逻辑意味着其他含义，但具体是什么？
说法是
∀ quantifier can be turned into ∃ by inverting the constraint
AFAIK，以下两个关系成立：
∀x.φ(x) <=> ¬∃x.¬φ(x)
¬∀x.φ(x) <=> ∃x.¬φ(x)
由于无量词的 SMT 公式 φ(x) 对其存在闭包 ∃x.φ(x) 等可满足，我们可以使用 SMT 的无量词片段表达 (simple) 否定通用量化的理论，[AFAIK] 也是 (simple) 在 普通公式 上普遍量化的积极出现（例如，如果 [∃x.]φ(x) 是 unsat 那么 ∀x.¬φ(x)¹）.
¹：假设 φ(x) 是无量词的；正如@Levent Erkok 在他的回答中指出的那样，当 φ(x) 和 ¬φ(x) 都可满足时，这种方法是不确定的
但是，例如，我们无法使用 SMT 的无量词片段找到以下量化公式的模型：
[∃y.]((∀x.y <= f(x)) and (∃z.y = f(z)))
根据记录，这是将 OMT 问题 min(y), y=f(x) 编码为量化的 SMT 公式。 [related paper]
A term t is quantifier-free iff t syntactically contains no quantifiers. A quantifier-free formula φ is equisatisfiable with its existential closure
(∃x1. (∃x2 . . .(∃xn.φ ). . .))
where x1, x2, . . . , xn is any enumeration of free(φ), the free variables in φ.
The set of free variables of a term t, free(t), is defined inductively as:
free(x) = {x} if x is a variable,free((f t1 t2 . . . tk)) = \cup_{i∈[1,k]} free(ti) for function applications,free(∀x.φ) = free(φ) \ {x}, andfree(∃x.φ) = free(φ) \ {x}.
帕特里克给出了一个很好的答案，但这里还有一些想法。 （我会把它作为评论提出来，但 Whosebug 认为它太长了！）
请注意，您不能总是玩 "negate and check the opposite" 把戏。这只有效，因为如果 属性 的否定是不可满足的，那么 属性 必须对所有输入为真。但它不会反过来：A 属性 可以是可满足的，它的否定也可以是可满足的。简单示例：x < 10。这显然是可满足的，它的否定也是如此x >= 10。所以，你不能总是通过玩这个把戏来摆脱量词。它仅在您想证明某事时才有效：然后您可以否定它并查看该否定是否不可满足。如果您担心找到公式的模型，则该方法不适用。
您始终可以简化公式并通过用未解释的函数替换它们来消除所有存在量词。然后你最终得到的是一个具有所有前缀通用性的可满足公式。显然，这 not 没有量词，但这是大多数工具自动为您执行的非常常见的技巧。
所有这些伤害都在于交替量词。不管 skolemization 是什么，如果你有交替量词，那么你的问题就已经很难处理了。维基百科关于量词消除的页面相当简洁，但它提供了一个很好的介绍：https://en.wikipedia.org/wiki/Quantifier_elimination底线：并非所有理论都承认量词消除，即使是那些理论也可能需要指数算法来消除它们；导致性能问题。
即使是最简单的算术 SMT 问题，也需要存在量词来声明符号变量。 ∀ 量词可以通过反转约束变成 ∃。所以，我可以在 QF_* 逻辑中同时使用它们并且它有效。
我认为，"quantifier free" 对此类 SMT 逻辑意味着其他含义，但具体是什么？
说法是
∀quantifier can be turned into∃by inverting the constraint
AFAIK，以下两个关系成立：
∀x.φ(x) <=> ¬∃x.¬φ(x)
¬∀x.φ(x) <=> ∃x.¬φ(x)
由于无量词的 SMT 公式 φ(x) 对其存在闭包 ∃x.φ(x) 等可满足，我们可以使用 SMT 的无量词片段表达 (simple) 否定通用量化的理论，[AFAIK] 也是 (simple) 在 普通公式 上普遍量化的积极出现（例如，如果 [∃x.]φ(x) 是 unsat 那么 ∀x.¬φ(x)¹）.
¹：假设 φ(x) 是无量词的；正如@Levent Erkok 在他的回答中指出的那样，当 φ(x) 和 ¬φ(x) 都可满足时，这种方法是不确定的
但是，例如，我们无法使用 SMT 的无量词片段找到以下量化公式的模型：
[∃y.]((∀x.y <= f(x)) and (∃z.y = f(z)))
根据记录，这是将 OMT 问题 min(y), y=f(x) 编码为量化的 SMT 公式。 [related paper]
A term
tis quantifier-free ifftsyntactically contains no quantifiers. A quantifier-free formulaφis equisatisfiable with its existential closure(∃x1. (∃x2 . . .(∃xn.φ ). . .))where
x1, x2, . . . , xnis any enumeration offree(φ), the free variables inφ.
The set of free variables of a term
t,free(t), is defined inductively as:
free(x) = {x}ifxis a variable,free((f t1 t2 . . . tk)) = \cup_{i∈[1,k]} free(ti)for function applications,free(∀x.φ) = free(φ) \ {x}, andfree(∃x.φ) = free(φ) \ {x}.
帕特里克给出了一个很好的答案，但这里还有一些想法。 （我会把它作为评论提出来，但 Whosebug 认为它太长了！）
请注意，您不能总是玩 "negate and check the opposite" 把戏。这只有效，因为如果 属性 的否定是不可满足的，那么 属性 必须对所有输入为真。但它不会反过来：A 属性 可以是可满足的，它的否定也可以是可满足的。简单示例：
x < 10。这显然是可满足的，它的否定也是如此x >= 10。所以，你不能总是通过玩这个把戏来摆脱量词。它仅在您想证明某事时才有效：然后您可以否定它并查看该否定是否不可满足。如果您担心找到公式的模型，则该方法不适用。您始终可以简化公式并通过用未解释的函数替换它们来消除所有存在量词。然后你最终得到的是一个具有所有前缀通用性的可满足公式。显然，这 not 没有量词，但这是大多数工具自动为您执行的非常常见的技巧。
所有这些伤害都在于交替量词。不管 skolemization 是什么，如果你有交替量词，那么你的问题就已经很难处理了。维基百科关于量词消除的页面相当简洁，但它提供了一个很好的介绍：https://en.wikipedia.org/wiki/Quantifier_elimination底线：并非所有理论都承认量词消除，即使是那些理论也可能需要指数算法来消除它们；导致性能问题。