为什么不推断出这个愚蠢的post-条件?
Why this dafny post-condition is not inferred?
我已经以类似的建设性方式证明了一些纯粹存在的引理(没有结果):
https://rise4fun.com/Dafny/Wvly
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 吗?
很好的证明!问题在于后置条件中的量词没有涉及 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
函数就可以解决问题。
我已经以类似的建设性方式证明了一些纯粹存在的引理(没有结果):
https://rise4fun.com/Dafny/Wvly
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 吗?
很好的证明!问题在于后置条件中的量词没有涉及 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
函数就可以解决问题。