如何在Hoare Triples中找到循环不变

Question

嘿，我是新的thare triples，我无法理解在假设中找到循环不变。例如，循环

[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].

.

不变是[2x + y> 5]，但我不明白如何找到它。关于如何找到它的逐步解释将非常感谢。

Answer 1

首先了解循环不变的含义。这意味着在初始的程序/算法的每次迭代中都是如此的条件，以及循环终止。你的程序是这样的。

$$ x> 1 \ text {and} y> 1 $$

$$ \ text {whis} x> 0 $$

$$ \ hspace {4cm} \ text {do} x：= x - 1，y：= y + 2 $$

$$ \ text {end} $$

$$ x + y> 5 $$

$ 2x + y> 5 $ 是您所描述的不变性。从程序中可以看到 $ x $ 和 $ y $ 将大于 $ 1 $ 。所以在循环 $ 2x + y> 5 $ （您可以证明它）的第一次迭代中。注意在每次迭代时循环 $ x $ 按值 $ 1 $ 和Y的值是通过两个所以，所以不等式 $ 2x + y> 5 $ 。你可以证明它。现在来到终止条件，此时 $ x $ 将是负数和我的索赔是 $ y $ 将至少 $ 5 $ 。因此，Invariant $ 2x + y> 5 $ si true通过while循环的迭代。

示例：

let $ x= 2 $ 和 $ y= 2 $ ，然后 $ 2 \ times 2 + 2= 6> 5 $ 满足。现在在第二次迭代 $ x= 1，y= 4 $ so $ 1 \ times 2 + 4> 5 $ 满意。现在 $ x= 0，y= 6 $ ，循环终止， $ 2 \ times 0 + 6> 5 $ 。