为什么不推断出这个愚蠢的post-条件？

Question

我已经以类似的建设性方式证明了一些纯粹存在的引理（没有结果）：

lemma DivModExistsUnique_Lemma (x:nat, y:nat)  
requires y != 0
ensures exists q:nat, r:nat :: x == y*q + r &&  r < y 
{
var q:nat, r:nat := 0, x;
while r >= y 
  invariant x == y*q + r
  {
  q := q + 1;
  r := r - y;
  }
assert x == y*q + r &&  r < y;
}

我不明白为什么这个post-条件不是从证明中的最后一个断言中推断出来的。

有一些额外的提示可以给 Dafny 吗？

Answer 1

很好的证明！问题在于后置条件中的量词没有涉及 r 的“匹配模式”（也称为“触发器”）。 Dafny 对此发出了警告。那么这是什么意思？

为了证明存在量词，验证者试图找到一个证人。在寻找见证人时，验证者不会尝试数学中的每一个可能的术语，甚至不会尝试出现在程序其他地方的每一个术语。相反，验证者将其注意力限制在 both 出现在证明上下文中其他地方的术语 and 具有量词的“匹配模式”的形状.在 Dafny IDE（VS Code 或 Emacs）中，您可以将光标放在量词上，IDE 将向您显示 Dafny select 编辑的触发器。（同样，在您的情况下，它会显示“无触发器”。）

关于什么是触发器，什么是触发器，有一些规则（请参阅 Dafny FAQ 或 Whosebug 上的许多已回答问题）。对于 q，验证者将 select 术语 y*q 作为触发器。这是允许的，因为 Dafny 允许 * 出现在触发器中。但是，r 唯一可能有用的触发器是 ... + r 和 r < ...，这两个都不被允许，因为触发器不允许提及 + 或 < .因此，Dafny 找不到量词的触发器，这实质上意味着它永远不会找到证明存在量词的证人。

要解决此问题，您可以引入一个涉及量化变量的函数。例如，

function MulAdd(a: nat, b: nat, c: nat): nat {
  a*b + c
}

lemma DivModExistsUnique_Lemma(x:nat, y:nat)  
  requires y != 0
  ensures exists q:nat, r:nat :: x == MulAdd(y, q, r) && r < y
{
  var q:nat, r:nat := 0, x;
  while r >= y 
    invariant x == MulAdd(y, q, r)
  {
    q := q + 1;
    r := r - y;
  }
}

将证明你的程序。然后 IDE 还会向您显示 Mul(y, q, r) 被 select 编辑为触发器。

没有触发器的量词往往是只使用“built-in 符号”的量词，例如 +、< 和 &&。当你的问题有其他功能时，验证者通常可以找到触发器。

为了证明，最符合我口味的解决方案是使用引理 out-parameters。这意味着引理可以只是“return”它计算的 q 和 r。它还使引理更易于使用，因为引理的调用者通常需要对量词进行 Skolemize（您在 Dafny 中使用 assign-such-that 运算符 :| 进行 - 这也涉及触发器，通过方式）。但是你说你（出于某种原因）试图避免 out-parameters。如果是这样，那么 MulAdd 函数就可以解决问题。

为什么不推断出这个愚蠢的post-条件？

Why this dafny post-condition is not inferred?

assert

formal-languages

dafny

formal-verification

formal-methods