Hoare Logic Loop Invariant

我正在研究Hoare Logic,我在理解寻找循环不变量的方法时遇到了问题。 有人可以解释用于计算循环不变量的方法吗? 循环不变量应该包含什么才能成为“有用的”? 我只是处理简单的例子,找到不变量并在例子中证明部分和完整的修正:
{ i ≥ 0 } while i > 0 do i := i−1 { i = 0 }
    
已邀请:
如果我们谈论Hoare的逻辑来证明(部分)程序的正确性,那么你使用前置条件和后置条件,分解程序并使用Hoare逻辑推理系统的规则来创建和证明一个归纳公式。 在您的示例中,您希望使用规则分解程序
{p} while b do S {p^not(b)} <=> {p^b} S {p}
在你的情况下 p:i≥0 b:i> 0 S:我:= i-1。 所以在下一步我们推断
{i ≥ 0 ^ i > 0} i := i−1 {i ≥ 0}
。这可以进一步推断并且很容易证明。 我希望这有帮助。     
我不确定这是否会回答你的问题,但以防万一: 非循环的“循环不变”是在循环迭代之前和之后保持为真的事实陈述。它实质上定义了程序相对于该循环的一致性约束。 我不太了解Hoare Logic如何准确地告诉你如何“计算”循环不变量,但我怀疑这样的事情将取决于被分析的代码的语言,而不是正式的证明语言本身。您是否拥有正在使用的正式算法描述?我或许可以进一步了解更多背景知识。 有用的循环不变量将描述关于应用程序状态的特定内容。例如,如果您正在编写插入排序,主元素运动循环的有用循环不变量将基本上声明(子)列表在执行循环之前和之后包含相同的对象集合,并且可能是先前的元素按排序顺序保持排序顺序。     
有用(为你的推理)是不变量的要点。因此,查看您想要证明的后置条件,并尝试组成一个不变量,这将帮助您逐步到达后置条件,并且可以从循环代码中派生出来。     

要回复问题请先登录注册