Soundness and completeness of systems

Question

First some terminology (borrowed from here, page 14):

A positive program is a program with an error.

A negative program is a program without an error.

So there are four types of programs:

A positive program, analysed as positive -> true positive (TP).

A positive program, analysed as negative -> false negative (FN).

A negative program, analysed as positive -> false positive (FP).

A negative program, analysed as negative -> true negative (TN).

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

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

So judging by what I wrote above:

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

A colleague told me sound systems also accept FP programs. Can someone confirm this and explain why they do?

Answer 1

The book explains it like this:

Soundness prevents false negatives and completeness prevents false positives.

So in order for the system to be sound, it need not prevent false positives, but only false negatives. To prevent false positives, it must be complete.

The book explains it further by using type systems as an example:

In modern languages, type systems are sound (they prevent what they claim to) but not complete (they reject programs they need not reject). Soundness is important because it lets language users and language implementers rely on X never happening. Completeness would be nice, but hopefully it is rare in practice that a program is rejected unnecessarily and in those cases, hopefully it is easy for the programmer to modify the program such that it type-checks.

Type systems are not complete because for almost anything you might like to check statically, it is impossible to implement a static checker that given any program in your language (a) always terminates, (b) is sound, and (c) is complete. Since we have to give up one, (c) seems like the best option (programmers do not like compilers that may not terminate).

Answer 2

Let's say a house owners set up alarm systems to detect thieves. The owner who dislikes false alarm due to other causes than illegal intrusion makes the system less sensitive, in this case, when the alarm sounds, it means "alarm means there is an intruder" with the danger of not detecting skillful thieves. The careful and cautious owner who can live with the false alarm but never wants the intrusion maybe make the system more sensitive. In this case, "no alarm means there is no intrusion".

The first system that never accepts the false positive (false alarm, in this example) is called sound system, and it means there is no type 1 error. The second system that never misses the intrusion, in other words, never accepts the false negative, is called complete system, and it means there is no type 2 error. Soundness does not guarantee completeness, and vice versa. With perfect sensitivity of the alarm system, there is no false alarm nor missing intrusion to make the system sound and complete.

This page (http://ubccpsc311.blogspot.jp/2010/11/7-ways-to-approach-soundness-and.html) gives seven perspectives on soundness and completeness. Also refer to Soundness and Completeness of a algorithm, which says that complete algorithm always find an answer when sound algorithm never gives wrong answer (never returns a false results). This https://softwareengineering.stackexchange.com/questions/140705/what-does-it-mean-to-say-an-algorithm-is-sound-and-complete also might help.

The contents from An Integrated approach to software engineering shows another perspective on static analyzer example.

In the book, soundness captures the occurrence of false positives, in other words, with the perfect sound system, there are no error reports when they are actually warnings: less soundness implies more false positives.

Having said that, I think the author's comment can be a typo, and it should have written as "soundness prevents false positives ...". Possibly, in the author's field the soundness means otherwise than normally used, but I'm not sure.

A good way to understand these definitions is that soundness prevents false negatives and completeness prevents false positives.

Also, I think that OP's comment is also confusing:

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

The better/correct description could be

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