割り当てのためのホアリトリプルp {x/e} x:= e {p}
-
16-10-2019 - |
質問
私はウィキペディアで提示されたホアーロジックを理解しようとしています、ウィキペディアのホアーロジックどうやら、私が正しく理解していれば、ホアートリプル$$ {p } 〜c〜 {q } $$は
Cの直前の場合、Cが終了する限り、QはCの直後に保持します。 (a)
ただし、割り当て公理スキーマは別の方法で解釈されているようです。
$$ frac {} { {p [x/e] } ~~ x:= e ~~ {p }} $$
ウィキペディアは言う:
割り当て公理は、$ {p [x/e] } $の真実が、$ {p } $の後割り当て真実と同等であることを意味します。したがって、割り当ての前に$ {p [x/e] } $がtrueでしたが、割り当てaxiomによって、$ {p } $はその後真になります。逆に、割り当てステートメントの前に$ {p [x/e] } $ falseでしたが、$ {p } $はfalseでなければなりません。
Hoareのトリプルは、x:= eの前にp [x/e]がx:= = eの後に保持されることを確認するだけだと思います。その定義により、p(x)がx:= eの後に保持された場合、p [x/e]がx:= eの前に保持されることを確認しません。
私の素朴な質問は、割り当ての前に$ {p [x/e] } $が割り当て後に$ {p } $に相当することができることです。これは私の投稿の先頭でポイント(a)と矛盾していますか?
解決
ウィキペディアが言っていることはそれであることに注意してください
割り当て公理は、$ {p [x/e] } $の真実が 後退の真実 $ {p } $の。
言い換えれば、($ p $は$ x:= e $の実行後に保持されます)if($ p [x/e] $は実行前に保持されます)。これは、提供された定義$ a $と同等です。これは、通常、Hoare Tripleのより直感的な定義です。
他のヒント
ウィキペディアのテキストの言葉遣いはある程度燃え上がっているようです。
割り当て公理は、{p [x/e]}の真実が 同等 {p}の割り当て後の真実に。
割り当て公理はそれを意味しません。それは{p [x/e]}の真実を意味するだけです 示す {p}のアフター割り当ての真実。 「同等性」を意味するものではありません。
ただし、同等性も有効な事実です。割り当てのためのホアー公理がそれを言わないということだけです。
ホアーのような証明システムの明確で厳密な扱いのための優れたソースは、適切で古いものです 連続プログラムと同時プログラムの検証.
それはより多くのものを意味します
Cの前にpが真であった場合、その後qは真です。
通常、Cは環境を変えるため、時間の考慮事項があります。
この例を考えてください:$ c =(x:= 42)$および$ p =(x> 10)$。次に、ルールのインスタンスが理にかなっています。
編集:時間の考慮事項は重要です。ここでは、$ p $ "$ x = e $"(つまり、after)は$ p [x/e] $(before)に相当します。 「$ x = e $」は「後」を指定するためだけのものであることに注意してください。$ x $が$ e $に表示できるため、実際の平等ではありません。
例えば
$$ {0 +42> 10 } ~~ x:= 0 ~~ {x +42> 10 } $$ $$ {x +42> 10 } ~~ x:= x +42〜 〜 {x> 10 } $$
あなたがそれを証明するのを助けることができます
$$ { mbox {true} } ~~ x:= 0〜;〜x:= x + 42 ~~ {x> 10 } $$
サイドノートでは、私は個人的に表記$ p [x/e] $が非常に混乱していることがわかりました。