В чем разница между полной и частичной правильностью?


Ответ 1:

Спецификация полной корректности также является спецификацией частичной корректности. Частичная корректность слабее, потому что для того, чтобы прийти к выводу, требуется дополнительная помощь «S завершается»: R сохраняется в конечном состоянии.

Для спецификации частичной корректности {Q} S {R} вы можете получить следующую информацию: Учитывая начальное состояние, которое удовлетворяет Q, S может завершиться или нет. Если S завершается, после выполнения S вы достигнете конечного состояния, которое удовлетворяет R. Если нет, то R бесполезен, так как конечного состояния нет.

Например:

{Х} == 10
while (y! = 0):
    у = у - 1
х = 0
{Х == 0}

Это частичная корректность спецификации. Если y инициализируется с некоторым числом, равным или большим 0, S прекратит работу, и после этого x будет 0. В то время как если y начинается с отрицательного числа, S будет зацикливаться вечно, и, поскольку оно не завершается, вы не достигнете состояния ' после казни С.

Действительно, R может быть чем угодно, если S - тупик. Например, для любых Q и R:

{Q}
пока (правда):
    у = у - 1
{Р}

это всегда частичная корректность спецификации.

Если Q недостаточно силен, вы не можете гарантировать завершение S, не говоря уже о причинах состояния после выполнения S. В этом случае вы можете вручную добавить условие: S завершается. С Q и этим рассуждение может продолжаться.

Для полной спецификации корректности {Q} S {R}, Q достаточно силен, чтобы гарантировать завершение S, поэтому вы можете заключить, что S завершится, и конечное состояние удовлетворяет R.

Например:

{x == 10}
while (x! = 0):
    х = х - 1
{x == 0}

полная спецификация правильности

Кстати, я не уверен, что ответ правильный, потому что вопрос помечен как политкорректный. Хотя определение в вопросе выглядит точно так же, как и в информатике.