soundness-and-completeness

Soundness

• What all can be derived is entailed.

$$KB⊢f\subseteq KB\models f$$

• This statement states that what all derived is has superset of what all is entailed.

• Soundness of an reasoning algorithm means that it proves only true statements which are totally valid. These statements are guaranteed to be true. Deductive reasoning algorithms are supposed to sound in nature.

• Soundness means that if a sentence is provable, then it must be true with all its interpretations. In other words, it should also be entailed.

• A proof system is sound if everything that is provable is actually true.

Completeness

• What all be derived is more that what all can be entailed.

$$KB⊢f\supseteq KB\models f$$

• This states that what all can be entailed is a part of what all can be derived.

• Completeness means that it proves all the true statements. It ensures that it can find a valid solution for any valid input.

• A proof system is complete if everything that is true can be proved

It is required for any algorithm to be sound and complete.

References

1. logic - what does soundness of a semantic reasoner mean? @stakeoverflow
2. https://textbooks.cs.ksu.edu/cis301/4-chapter/4_9-soundcomplete/index.html