为什么 CVC4 SMT 求解器 return 未知（不完整）？

Question

我正在摆弄 CVC4 SMT solver online version（使用 lang = cvc4）。

我没有使用标准 SMT-LIB format, but the native language implemented by CVC4，因为它更简单。但是，我无法证明非常直接和明显的陈述。例如，第一个 CHECKSAT 给了我 sat（可满足），这是正确的，但第二个 CHECKSAT 给了我 unknow.

OPTION "incremental";

ASSERT FORALL (k : INT): ((k > 5 AND k < 7) => (k = 6));

CHECKSAT; % this returns sat, okay!

arr: ARRAY INT OF REAL;
ASSERT arr[6] = 123;

ASSERT FORALL (k : INT): ((k > 5 AND k < 7) => (arr[k] = 123));

CHECKSAT; % this returns unknown, why?

为什么CVC4不能证明这么简单的谓词逻辑表达式？据我了解，SMT检查是不可判定的，因此，没有程序可以证明所有正确的陈述。然而，这似乎是一个非常简单的案例，所以我想我误解了什么。

Answer 1

如您所述，量词使逻辑成为半可判定的，而 SMT 求解器通常不能很好地处理此类问题。但是，在这种特殊情况下，--fmf-bound 选项似乎有效。（即运行 cvc4 --fmf-bound，您会看到它响应 sat）。此参数启用基于有限整数边界的有限实例化，这恰好解决了这种情况。请注意，它可能适用于也可能不适用于其他问题。

您可以通过在脚本中添加以下行来实现相同的目的：

OPTION "fmf-bound";

详情见本文：https://cvc4.cs.stanford.edu/papers/CADE24-2013/qi_for_fmf_reynolds_cade24.pdf

为什么 CVC4 SMT 求解器 return 未知（不完整）？

Why does CVC4 SMT solver return unknown (incomplete)?

math

logic

smt

formal-verification

cvc4