使用方法的结果时违反断言

Question

我编写了下面的程序来验证数组是否是任何特定元素的 'clean'。我无法断言该方法的结果。尝试断言该方法的结果时，我总是遇到断言冲突。

method Main (){
 
  
  var a:= new int[3];
  
  a[0], a[1], a[2] := 1,2,3;
  var v := isClean (a, 1);
  assert v == false;

}



method isClean (a : array <int>, key : int) returns (clean : bool)
  
  requires a.Length > 0


{
  
  var i := 0;
  
  while (i < a.Length)
  
  invariant 0 <= i <= a.Length
  invariant forall k :: 0 <= k < i ==> a[k] != key
  
  {
    
    if (a[i] == key) {
      
      clean := false;
      return;
    }
    
    i := i + 1;
    
  }
  
  clean := true;
  
}

Dafny 2.3.0.10506
stdin.dfy(8,11): Error: assertion violation

Dafny program verifier finished with 2 verified, 1 error

Answer 1

您需要在 isClean 上提供一个 ensures 子句。当 Dafny 验证程序时，它一次只查看一个 method。所以Dafny在验证Main的时候，根本没有看isClean的定义。相反，它只查看 requires 和 ensures 子句。

您已经在循环不变量中完成了证明的困难部分。基本上，您只需要修改该不变量的副本，使其在调用者的上下文中有意义，作为 ensures 子句，如下所示：

ensures clean <==> (forall k :: 0 <= k < a.Length ==> a[k] != key)

（将其添加到 isClean 的 requires 子句下方。）在这个 ensures 子句中，clean 指的是 return 的命名值isClean 方法。如果你添加这个子句，Dafny 仍然会抱怨，因为你要求它证明一个 forall 量词是 false。这相当于试图证明一个 exists 量词 true，并且需要一个明确的“见证”，即 k 的值，使公式的主体变成 true/false.

在这种情况下，isCleanreturns false的直观原因是因为a[0]的值为1，所以a是not 1 的“干净”。我们可以通过添加断言

向 Dafny 证明这个“见证”

assert a[0] == 1;

到 Main 的正文，紧接在 isClean.

调用之后

为清楚起见，这里是验证程序的完整版本：

method Main() {
  var a := new int[3];
  a[0], a[1], a[2] := 1,2,3;
  var v := isClean (a, 1);
  assert a[0] == 1;
  assert v == false;
}

method isClean(a: array <int>, key: int) returns (clean: bool)
  requires a.Length > 0
  ensures clean <==> (forall k :: 0 <= k < a.Length ==> a[k] != key)
{
  var i := 0;
  while (i < a.Length)
    invariant 0 <= i <= a.Length
    invariant forall k :: 0 <= k < i ==> a[k] != key
  {
    if (a[i] == key) {
      clean := false;
      return;
    }
    i := i + 1;
  }
  clean := true;
}

使用方法的结果时违反断言

dafny assertion violation when using the result of a method

dafny