此循环不变且 post 条件是否正确？

Question

我正在尝试为此代码编写循环不变式和 post 条件：

sum = 0;
for (i = 0; i < 10; ++i)
  ++sum;

sum = 10 是这里明显的 post 条件。但是有朋友告诉我，i = sum也是一个循环不变量，sum = 12也是一个post条件。我检查了以下内容：

循环不变量最初为真：对于 i = sum 也是如此，因为两者最初都是 0
循环不变量被保留：假设 i < 10 和 i = sum 然后在一次迭代后 ++i = ++sum
循环不变量意味着post条件：假设i >= 10和i = sum则sum = 12也为真

但是这里的sum显然不等于12。那么我的推理有什么问题吗？

Answer 1

采用稍微不同的不变量 i == sum && i <= 10。与 i >= 10 一起得到 i = sum = 10.

顺便说一句。在您最初的推理中，您不能得出 sum = 12 是正确的结论，只能得出 sum >= 10 是正确的结论。后者是正确的，只是不足以证明想要的结果。

Answer 2

// Loop invariant SUM_IS_INDEX: sum == i
// Loop variant: i is increased in every step, and initial value 0 before 10.

sum = 0;
for (i = 0;
        // SUM_IS_INDEX      before the actual loop
        i < 10;
        // next loop step, after first step:
        // sum == index + 1
        ++i
        // next index = index + 1
        // sum == index
        // SUM_IS_INDEX      after a loop step, continuing
        ) {
    // SUM_IS_INDEX
    ++sum;
    // sum == index + 1
}
// Post: i >= 10 (negation of the for condition), SUM_IS_INDEX

关于 12 的评论更多地与 i 相关。要获得 i == 10，需要添加一个仅以 1 为增量的谓词。

最佳实践是在控制流顺序中重写 for：

sum = 0;
i = 0;
while (i < 10)
    ++sum;
    ++i:
}

这可以防止愚蠢的错误。

此循环不变且 post 条件是否正确？

is this loop invariant and post condition correct?

algorithm

invariants

hoare-logic