Почему правило присваивания такое, какое оно есть в логике Хоара?

cs.stackexchange https://cs.stackexchange.com/questions/118322

Вопрос

Почему правило присваивания такое, какое оно есть в логике Хоара/аксиоматической семантике?Я не могу взять в толк, почему правило присвоения отличается от того, что я ожидал.

Я понимаю, что логика Хоара используется для доказательства формальных утверждений о состоянии программы по мере выполнения команд.Таким образом, если мы выполним команду $$x:=e$$ Я бы ожидал, что следующий у государства есть такая замена...но, похоже, замена происходит до мы выполняем задание, которое я нахожу странным.Я бы ожидал:

$$ \{ P \} x:= e \{P[e/x]\}$$

Учитывая, что $P$ являются заявлениями о состоянии программы.

Я уверен, что этому есть хорошее объяснение, и извините, если это основной вопрос, я знаю, что так и должно быть.Но может ли кто-нибудь объяснить мне это?

Дополнительный вопрос:

Почему бы нам не написать правило присваивания следующим образом:

$$ \{ Q \} x:= e \{Q[x/e]\}$$

обратите внимание, что это НЕ то же самое, что мое первоначальное предложение, потому что у нас есть $x$ и $e$ поменялись местами.т.е.в состоянии post везде, где у нас есть $e$ мы размещаем $x$ (и это прекрасно, потому что оператор, который мы только что выполнили, заключается в том, что $x$ содержит значение $e$, так что мы должны быть в состоянии заменить $e$ для $x$ в постусловии, если предварительное условие поможет.

Похожие посты, которые я прочитал и которые не помогли:

Приложение:

Для нас, дислексиков, в этом вопросе именно это означает обозначение подстановки:

$$ P[e/x] = P[e o x] $$

т.е.заменять каждое свободное появление $x$ с выражением/термином/штуковиной $e$.

Это было полезно?

Решение

Так что после чтения и мышления об этом больше это мое объяснение ( Спасибо Программное обеспечение Фонды ):

Ключевая путаница для меня, кажется, является значением $ p [e / x] $ (заменяет каждый свободный экземпляр x с e). Что это делает, это везде, где вы видите символ $ x $ буквально удалить его и разместить $ E $ . например $ p [e / x]= (x + y + 1) [e / x] \ to p [e / x]= (e + y + 1) $ Так что обратите внимание, как $ x $ буквально исчезла из $ p $ . Так что мы хотим, когда мы сделаем задание:

$$ x:= e $$

что утверждение верно, если у нас было $ x $ вместо $ e $ . Так что, если правило:

$$ \ {p [e / x] \} x:= e \ {p} $$

Тогда, что мы хотим, когда мы хотим, когда мы подключаем $ x $ для $ E $ Мы хотим заявление в рассмотрении, чтобы быть правдой. Поэтому, прежде чем мы начали код, у нас есть $ P [E / X] $ . Затем мы запускаем задание и все экземпляры $ e $ исчезают, и мы получаем $ x $ заменить их. Что должен быть правдой, если код, который управлял заданием (поскольку $ x $ теперь удерживайте значение $ E $ , так что вы можете удалить $ E $ 's и place $ x $ ).

Это объяснение абстрактной концепции. Давайте (бесстыдно) используйте пример фонда программного обеспечения (SF):

{{y= 1}} x ::= y {{x= 1}} на английском языке: если мы начнем в состоянии, где значение y равно 1, и мы присваиваем y к x, то мы Отделка в состоянии, где X равно 1. То есть свойство равен 1 получено от Y на X.

Еще один полезный абзац от SF:

Точно так же, в {{Y + z= 1}} x ::= y + z {{x= 1}} Такое же свойство (равное одному) передается на х из выражения y + z на правой стороне назначения. В целом, если A есть арифметическое выражение, то {{a= 1}} x ::= a {{x= 1}} является действительным тройным топором.

Дополнение от комментариев Отличное наблюдение:

Важно признать, что правило { п [ свидетельствовать / Икс Несомненно } Икс знак равно свидетельствовать { п } позволяет как выражением свидетельствовать и переменная Икс произойти в постусловие. Другими словами, правило вывода позволяет вывести посткондицию, в котором любое подмножество вхождений свидетельствовать в предварительном условии были заменены на Икс , в том числе ни один из них. Более того, он позволяет одновременно выводить все эти разные поступления.

Ответить на бонус Почему это

1) $ \ {p [e / x] \} x:= e \ {p} $

лучше, чем

2) $ \ {q \} x:= e \ {q [x / e] \} $ :

Помимо тонкой точки замены x с выражениями, которые могут быть невидимыми (например, e= 0, если мы должны заменить $ 0 $ с бесконечным количеством $ x $ 's? Что если нули нет там ... правила должны быть синтаксическими, но я думаю, что лучше избежать таких путаний), я думаю, что это причина: < / P >.

Какое правило назначения должно захватить, состоит в том, что мы присваиваем выражение e к переменной X. Таким образом, только X должен быть «заменен» е. Интуитивно, в коде (или, точнее состояние программы $ \ sigma $ ) Когда x начинает удерживать значение e, это не случайно означает, что везде, где Там может быть E, что он становится X после выполнения задания $ x:= e $ . На самом деле то, что это значит, так это то, что сейчас в состоянии после у нас есть X. Теперь эти X, если у нас не было назначения, должно иметь значение $ e $ i.e. Мы только «отменить» замену / назначение команду назначения. Не все другие случайные выражения e. Короче говоря, единственный способ узнать, где разместить правильные E, - это начать в состоянии посту, после того, как назначение было сделано, а затем начать от этого места E's. Если мы сделаем это назад, мы могли бы заменять E, мы не хотели заменять (даже если они, вероятно, были верны, что, я думаю, они должны, поскольку мы говорим, что X содержит значение E после назначения E до x).

Другие советы

Предположим, мы запускаем программу x := e, и пусть $\сигма$ быть начальным состоянием, и $\сигма'$ быть конечным состоянием.

Важнейшей интуицией здесь является:ценность $x$ в окончательный государство $\сигма'$ совпадает со значением выражения $e$ в первоначальный государство $\сигма$.Действительно, последнее - это то значение, которое мы придаем $x$ с помощью команды x := e.

Следовательно, если $P(-)$ является свойством значений, формула $P(\mbox{$x$-в-конечном-состоянии})$ эквивалентно $P(\mbox{$e$-в-исходном-состоянии})$.Другими словами $P(x)$ в постусловие (в состоянии $\сигма'$) действительно эквивалентно $P(e)$ в предварительное условие (в состоянии $\сигма$).

Использование подстановки - это лишь более формальный способ рассматривать постусловие как "формулу, которая зависит от $x$", т.е.как $P(x)$, а затем требующий $P(e)$ в качестве предварительного условия.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top