在程序和 post 条件下具有未知变量的 Hoare 三元组的有效性？

Question

我不确定 x 在这个霍尔三元组中的值：{ a = 0 } while (x > a) do (x := x − 1) { x = 0 }。

关于如何证明这个霍尔三元组是否有效，我有 2 个潜在的想法：

假设x为0，霍尔三元组有效，或者
假设 x 是任意值，我们将其分解为案例并得出结论，霍尔三元组不适用于 x

以上两种方法是否有效，或者我应该采用另一种方法吗？

Answer 1

所以你有

{a = 0}
while (x > a)
    x := x - 1
{x = 0}

让我们试试循环不变量 x ≥ a & a = 0 并用 I 缩写它。当我们注释程序时，我们得到：

{a = 0}
{I}              # Loop invariant should be true before the loop
while (x > a)
    {I & x > a}  # Loop invariant + condition holds
    x := x - 1
    {I}          # Loop invariant should be true after each iteration
{I & x ≤ a}      # Loop invariant + negation of loop condition
{x = 0}

现在我们需要将最弱的前提条件应用到 x := x - 1:

{a = 0}
{I}
while (x > a)
    {I & x > a}
    {x - 1 ≥ a & a = 0}  # I[x-1/x]
    x := x - 1
    {I}
{I & x ≤ a}
{x = 0}

我们最终有以下证明义务：

(a = 0) ⇒ (x ≥ a & a = 0) 成立，因为 x ∈ ℕ
(x ≥ a & a = 0) ⇒ (x - 1 > a & a = 0)，成立。证明很简单。
(x ≥ a & a = 0 & x ≤ a) ⇒ (x = 0)成立。证明很简单。

所以原来的霍尔三元组成立。

在程序和 post 条件下具有未知变量的 Hoare 三元组的有效性？

Validity of Hoare triple with unknown variable in program and post-condition?

correctness

hoare-logic