|
|
Introduction to Logic
|
Tools for Thought
|
|
Soundness and Completeness |
In talking about Logic, we now have two notions - logical entailment and provability. A set of premises logically entails a conclusion if and only if every truth assignment that satisfies the premises also satisfies the conclusion. A sentence is provable from a set of premises if and only if there is a finite proof of the conclusion from the premises.
The concepts are quite different. One is based on truth assignments; the other is based on symbolic manipulation of expressions. Yet, for the proof systems we have been examining, they are closely related.
|
We say that a proof system is sound if and only if every provable conclusion is logically entailed. In other words, if Δ ⊢ φ, then Δ ⊨ φ. We say that a proof system is complete if and only if every logical conclusion is provable. In other words, if Δ ⊨ φ, then Δ ⊢ φ.
|
The Hilbert system is sound and complete for Propositional Logic. In other words, for this system, logical entailment and provability are identical. An arbitrary set of sentences Δ logically entails an arbitrary sentence φ if and only if φ is provable from Δ using Hilbert.
|
The upshot of this result is significant. On large problems, the proof method often takes fewer steps than the truth table method. (Disclaimer: In the worst case, the proof method may take just as many or more steps to find an answer as the truth table method.) Moreover, proofs are usually much smaller than the corresponding truth tables. So writing an argument to convince others does not take as much space.
|
Use the arrow keys to navigate.
Press the escape key to toggle all / one.
|
|