完全正确和部分正确之间有什么区别?


回答 1:

总体正确性规范也是部分正确性规范。部分正确性较弱,因为它需要“ S终止”的额外帮助才能得出结论:R处于最终状态。

对于部分正确性规范{Q} S {R},您可以获得以下信息:给定满足Q的起始状态,S可能终止也可能不终止。如果S终止,则在执行S之后,您将达到一个满足R的最终状态。否则,R将无用,因为没有最终状态。

例如:

{x == 10}
而(y!= 0):
    y = y-1
x = 0
{x == 0}

这是部分正确性规范。如果y初始化为等于或大于0的某个数字,则S将终止,然后x为0。如果y以负数开头,则S将永远循环,并且由于它没有终止,因此您将不会到达状态'在S执行后”。

实际上,如果S是死循环,则R可以是任何值。例如,对于任何Q和R:

{Q}
而(true):
    y = y-1
{R}

始终是部分正确性规范。

如果Q不够强,则不能保证S的终止,更不用说S执行后的状态了。在这种情况下,您可以手动添加条件:S终止。有了Q和它,推理就可以继续。

对于完全正确性规范{Q} S {R},Q足以保证S的终止,因此您可以得出结论,S将终止并且最终状态满足R。

例如:

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

是总正确性规范。

顺便说一句:我不确定答案是否正确,因为该问题带有政治正确性标签。问题中的定义看起来与计算机科学完全相同。