达夫尼。证明一个区间的所有值都出现在 seq 中

Question

我试图证明以下引理。这看起来真的很微不足道，但我无法证明这一点。提前致谢！

lemma test(x : seq<int>)
  // if the values from x are margined by an interval
  // the values are different
  // and the number of values equals the size of the interval
  // then all values from the interval appear in x

  requires forall i :: 0 <= i < |x| ==> 
    0 <= x[i] < |x|;

  requires forall i :: 0 <= i < |x| ==>
   forall i' :: 0 <= i' < |x| && i != i' ==>
     x[i] != x[i'];

  ensures forall v :: 0 <= v < |x| ==>
    exists i :: 0 <= i < |x| && x[i] == v;
{

}

https://rise4fun.com/Dafny/d8VK

Answer 1

这是一种方法，使用关于集合基数的一些事实。

lemma test(x : seq<int>)
  // if the values from x are margined by an interval
  // the values are different
  // and the number of values equals the size of the interval
  // then all values from the interval appear in x

  requires forall i :: 0 <= i < |x| ==> 
    0 <= x[i] < |x|;

  requires forall i :: 0 <= i < |x| ==>
   forall i' :: 0 <= i' < |x| && i != i' ==>
     x[i] != x[i'];

  ensures forall v :: 0 <= v < |x| ==> v in x
{
    var L: set<int>, R: set<int> := {}, RangeSet(0, |x|);
    var i := 0;
    CardinalityRangeSet(0, |x|);
    while i < |x|
        invariant 0 <= i <= |x|
        invariant L == set j | 0 <= j < i :: x[j]
        invariant forall v | v in L :: v in x
        invariant forall v | 0 <= v < |x| :: v in L || v in R
        invariant |R| == |x| - i

    {
        L, R := L + {x[i]}, R - {x[i]};
        i := i + 1;
    }
}

predicate InRange(lo: int, hi: int, i: int)
{
    lo <= i < hi
}

function RangeSet(lo: int, hi: int): set<int>
{
    set i | lo <= i < hi && InRange(lo, hi, i)
}

lemma CardinalityRangeSet(lo: int, hi: int)
    decreases hi - lo
    ensures |RangeSet(lo, hi)| == if lo >= hi then 0 else hi - lo
{
    if lo < hi {
        assert RangeSet(lo, hi) == {lo} + RangeSet(lo + 1, hi);
        CardinalityRangeSet(lo + 1, hi);
    }
}

我稍微更改了您的规范以使用 Dafny 语法 v in x，这与您编写的内容等效，并且 Dafny 更容易推理。

证明的基本思想是从元素0..|x|的范围R开始，然后迭代地从R中移除元素x[i]并添加到L。这保持了 0..|x| 范围内的每个数字在 L 或 R 中的不变性，而 R 的基数在每次迭代中都会减少。因此，在循环结束时 R 为空，因此范围内的每个数字都必须在 L 中，因此在 x.

中

我还使用了一个通过归纳证明的辅助引理来表明 RangeSet 具有预期的大小。

（已编辑以消除 RangeSet 中的 "No terms found to trigger on" 警告。引入谓词 InRange 可以触发它，但您仍然需要在 RangeSet 因为否则它无法确定集合是有限的。）

达夫尼。证明一个区间的所有值都出现在 seq 中

Dafny. Prove that all values from an interval appear in seq

seq

dafny