Hoare logic - total correção de loops

Considere um loop while do formulário:

$\texttt{while (C) {S}}$

com a condição e o corpo do loop. $\texttt{C}$ $\texttt{S}$

Seja $\texttt{I}$ e $\texttt{V}$ respectivamente, uma invariável e uma variante desse loop. A regra para a correção total dos loops while é dada no meu livro por:

Se $\texttt{I} \Rightarrow \texttt{V} \geq 0$

E $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Então $[\texttt{I}] \, \texttt{while (C) {S}} \, [\texttt{I} \land \neg \texttt{C}]$

Pelo que acho que entendi, para que o loop termine, a variante $\texttt{V}$ deve diminuir estritamente e também deve ser delimitada por zero. No entanto, quando traduzo isso matematicamente, obtenho uma proposição diferente daquela do meu livro:

[V \geq 0 0 \land V = v_{0 0}] S [V \geq 0 0 \land V < v_{0 0}]

$[\texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{V} \geq 0 \land \texttt{V} < v_0]$

Minha pergunta : esta última proposição e a regra do meu livro estão dizendo a mesma coisa sobre o que precisa ser comprovado para que o loop termine? Em outras palavras: é

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

o mesmo que

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ junto com $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Por que ou por que não?

hoare-logic Dory
fonte

A afirmação de que "𝚅 deve diminuir estritamente e que também deve ser delimitada por zero" é suficiente é enganosa. Você também precisa que 𝚅 seja uma função com um alcance bem fundamentado. Imagine usar os números racionais não negativos e construa um contra-exemplo.

Kai

Respostas:

Eles são equivalentes, no sentido de que toda vez que você pode aplicar a regra do livro didático, também pode aplicar sua própria regra e vice-versa. O invariante para as duas regras é semelhante, mas não é o mesmo.

Convertendo uma instância de regra de livro didático em uma instância de sua regra

Suponha que tenhamos uma aplicação ou sua regra de livro didático. seja, encontramos alguns para os quais: $\texttt{I}$

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ junto com $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Então, graças à implicação acima, também temos . Usando a regra PrePost, podemos reescrever a invariante em seu equivalente e obtemos uma aplicação da sua regra: $\texttt{I} \iff \texttt{I} \land \texttt{V} \geq 0$

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Aqui, usamos o mesmo invariante da regra do livro.

Convertendo uma instância de sua regra em uma instância de regra de livro didático

Agora, para a direção inversa. Suponha que encontramos para sua regra: $\texttt{I}$

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Agora, não podemos assumir , portanto, não podemos usar para a regra do livro didático. No entanto, podemos usar como um novo invariante . Nós trivialmente temos por construção (*). Além disso, a partir da hipótese $\texttt{I} \Rightarrow \texttt{V} \geq 0$ $\texttt{I}$ $\texttt{I}' := \texttt{I} \land \texttt{V} \geq 0$ $\texttt{I}' \Rightarrow \texttt{V} \geq 0$

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

podemos obter (pelo PrePost)

$[\texttt{I}' \land \texttt{C} \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I}' \land \texttt{V} < v_0]$ (**)

As propriedades (*) e (**) são exatamente o que precisamos para aplicar a regra do livro.

chi
fonte