Dafny 在与不成立的 assume 一起使用时验证一个 assert。

huangapple go评论52阅读模式
英文:

Dafny verifies an assert when used with an assume which does not hold

问题

I used assume and assert as in the following method:

method testAssumes(x: int) returns (s: int)
{
  var z: int := -1;
  assume {:axiom} z > 0;
  var y: int;
  y := x + z + 1;
  assert y > 0;
  return y;
}

奇怪的是,它验证通过了,但实际上不应该通过,因为 y := x + z + 1 而且 x 可能是负数。当我将 z 的值更改为 1 时,验证报错,表示 assert 可能无法满足。对于这种行为是否有解释?

英文:

I used assume and assert as in the following method:

method testAssumes(x:int)  returns (s:int)
 {
  var z:int:=-1;
  assume {:axiom} z>0;
  var y:int;
  y:=x+z+1;
  assert y>0;  
  return y;
}

Strangely enough it verifies while it should not since y:=x+z+1 and x could be negative.
When I changed the value of z to 1, the verifies complaints that the assert might not hold.

Is there an explanation for this behavior?

答案1

得分: 2

你假设了一些不成立的事情。因此,根据“爆炸原理”,你可以得出任何结论。

来自Dafny 文档 关于 assume 的引用:

assume 语句允许用户指定一个逻辑命题,Dafny 可以在没有证明的情况下假定为真。如果事实上这个命题不成立,这可能导致无效的结论。

编辑
这里有一个关于 Dafny 如何(可能,并不是说它一定会这样)推导出断言条件(y > 0)为真的示例:

  1. var z:int:=-1; 告诉Dafny z == -1,因此Dafny以后可以使用这个事实。
  2. assume {:axiom} z > 0; 告诉Dafny z > 0,因此Dafny以后也可以使用这个事实。
  3. Dafny首先证明 y > 0 || z > 0 为真。这很容易,因为Dafny知道 z > 0 为真。
  4. 为了证明 y > 0,Dafny需要证明 z > 0 为假(由于 y > 0 || z > 0 为真,所以 y > 0 必须为真)。但这可以使用第1点的事实来证明,即 z == -1
英文:

You are assuming something that is not true. As a result, you can derive any conclusion (by the Principle of explosion).

A quote from Dafny documentation regarding assume:

> The assume statement lets the user specify a logical proposition that
> Dafny may assume to be true without proof. If in fact the proposition
> is not true this may lead to invalid conclusions.

Edit:
Here is an example of how Dafny could (possibly, not saying that it happens this way) derive the assert condition (y > 0) to be true:

  1. var z:int:=-1; tells Dafny that z == -1, so Dafny can later use this fact.
  2. assume {:axiom} z>0; tells Dafny that z > 0, therefore Dafny can later use this fact too.
  3. Dafny starts by proving that y > 0 || z > 0 is true. This is easy, since Dafny knows z > 0 to be true.
  4. To show that y > 0, Dafny needs to prove that z > 0 is false (and since y > 0 || z > 0 is true, y > 0 must be true). But this can be shown using the fact from 1., i.e., that z == -1.

huangapple
  • 本文由 发表于 2023年5月22日 23:27:21
  • 转载请务必保留本文链接:https://go.coder-hub.com/76307740.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定