Hoare Triple для назначения p {x/e} x: = e {p}

Question

Я пытаюсь понять логику Хоэра, представленную в Википедии,Логика Hoare в ВикипедииОчевидно, если я правильно понимаю, тройной $$ {p } ~ c ~ {q } $$ означает

Если P непосредственно перед C, то Q удерживается сразу после C, пока C заканчивается. (А)

Однако схема аксиомы назначения, по -видимому, интерпретируется по -другому:

$$ frac {} { {p [x/e] } ~~ x: = e ~~ {p }} $$

Википедия говорит:

Аксиома назначения означает, что истина $ {p [x/e] } $ эквивалентна истинству после согласования $ {p } $. Таким образом, $ {p [x/e] } $ true до назначения, с помощью аксиомы назначения, тогда $ {P } $ будет верно, после чего. Наоборот, были $ {p [x/e] } $ false до оператора назначения, $ {p } $, следовательно, должен быть ложным.

Я думаю, что тройка Hoare только подтверждает, что если p [x/e] до x: = e, то p (x) удерживается после x: = e. По его определению не подтверждает, что если p (x) удерживается после x: = e, то p [x/e] удерживается до x: = e.

Мой наивный вопрос: как $ {p [x/e] } $ до того, как назначение может быть эквивалентно $ {P } $ после назначения? Это противоречит точке (а) в начале моего поста?

Answer 1

Обратите внимание, что говорит Википедия, что

Аксиома назначения означает, что истина $ {p [x/e] } $ эквивалентна Последствия истина $ {P } $.

Другими словами, ($ p $ удерживает после выполнения $ x: = e $), если ($ p [x/e] $ удерживает перед выполнением). Это эквивалентно определению $ a $, которое вы предоставили, что, как правило, является более интуитивным определением для Hoare Triple.

Answer 2

Кажется, что формулировка текста Википедии в некоторой степени является хлопьями:

Аксиома назначения означает, что истина {p [x/e]} эквивалент к истине после согласования {p}.

Аксиома назначения не означает это. Это только означает, что истина {p [x/e]} подразумевает Последующая истина {P}. Это не означает «эквивалентность».

Однако эквивалентность также является действительным фактом. Просто то, что аксиома Hoare для назначения не говорит.

Хороший источник для четкой и строгой обработки систем, похожих на Hoare Проверка последовательных и параллельных программ.

Answer 3

Это означает больше чего -то вроде

Если P был правдой до C, то Q будет правдой после этого.

Есть временные соображения, потому что обычно C изменяет окружающую среду.

Подумайте об этом примере: $ c = (x: = 42) $ и $ p = (x> 10) $. Тогда экземпляр вашего правила имеет смысл.

РЕДАКТИРОВАТЬ: Временные соображения важны. Здесь, $ p $, где "$ x = e $" (т.е. после) эквивалентно $ p [x/e] $ (до). Обратите внимание, что «$ 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] $ очень запутанной.