系统的健全性和完备性

Question

首先是一些术语(借用自这里，第14页)：

正向程序是一个有错误的程序。

负程序是一个没有错误的程序。

因此，有四种类型的程序：

一个阳性程序，分析为阳性->真阳性(TP)。

一种阳性程序，分析为阴性->假阴性(FN)。

一种负程序，被分析为阳性->假阳性(FP)。

一个负程序，被分析为负->真负(TN)。

一个系统是声音，如果它从来不接受一个积极的程序。

一个系统是完全，如果它从来不拒绝一个负程序。

​

所以从我上面写的来判断：

A complete system accepts FN and TN programs.
A sound system also accepts FN and TN programs.

一位同事告诉我，健全的系统也接受FP程序。有人能证实这一点并解释他们为什么这么做吗？

Answer 1

这本书是这样解释的：

健全防止虚假否定，完整性防止假阳性。

因此，为了使系统健全，不需要防止假阳性，而只需要防止假阴性。为了防止假阳性，它必须是完整的。

本书以类型系统为例进一步解释了这一问题：

在现代语言中，类型系统是健全的(它们阻止他们声称的东西)，但不完整(他们拒绝他们不需要拒绝的程序)。稳健性很重要，因为它让语言用户和语言实现者依赖于X永远不会发生。完整性很好，但希望在实践中很少会有程序被不必要地拒绝，在这种情况下，希望程序员能够很容易地修改程序，使其能够进行类型检查。 类型系统是不完整的，因为几乎任何您想静态检查的东西，都不可能实现一个静态检查器，它给出了您语言中的任何程序(a)总是终止，(b)是健全的，(c)是完整的。由于我们不得不放弃一个，(c)似乎是最好的选择(程序员不喜欢不可能终止的编译器)。

Answer 2

假设房主设置警报系统来侦查窃贼。由于非法入侵以外的其他原因而不喜欢虚惊的所有者使系统变得不那么敏感，在这种情况下，当警报响起时，就意味着“警报意味着有入侵者”，有可能找不到熟练的盗贼。能够忍受虚惊而不想被入侵的谨慎谨慎的所有者可能会使系统更加敏感。在这种情况下，“没有警报意味着没有入侵”。

第一个系统不接受假阳性(在本例中为假警报)称为声音系统，这意味着没有1型错误。第二个系统从来没有错过入侵，换句话说，不接受假阴性，称为完全系统，这意味着没有2型错误。健全并不能保证完整，反之亦然。具有完善的报警系统灵敏度，无虚警或漏报入侵，使系统健全完整。

这个页面(http://ubccpsc311.blogspot.jp/2010/11/7-ways-to-approach-soundness-and.html)给出了关于可靠性和完整性的七个透视图。也可以参考算法的稳健性与完备性，它说当声音算法没有给出错误的答案时，完整的算法总是找到答案(永远不会返回错误的结果)。这个https://softwareengineering.stackexchange.com/questions/140705/what-does-it-mean-to-say-an-algorithm-is-sound-and-complete也可能有帮助。

软件工程的集成方法的内容在静态分析器示例中显示了另一个透视图。

​

​

在这本书，soundness captures the occurrence of false positives，换句话说，在完美的声音系统，没有错误报告，当它们实际上是警告：less soundness implies more false positives。

话虽如此，我认为作者的评论可能是一个错误，它应该写成“健全防止假阳性.”。可能，在作者的领域中，稳健性的意思不是通常使用的，但我不确定。

理解这些定义的一个好方法是，正确防止虚假否定，完整性防止假阳性。

此外，我认为OP的评论也令人困惑：

A system is sound, if it never accepts a positive program.
A system is complete, if it never rejects a negative program.

更好的/正确的描述可以是

A system is sound, if it never accepts a false positive program.
A system is complete, if it never accepts a false negative program.