Is anyone able to articulate the difference between the properties of soundness and completeness insofar as they relate to the validity of the truth tree/semantic tableau?
Asked
Active
Viewed 2.9k times
12
-
1What's the tree test? Is this what you mean? I don't think that's what you're referring to since soundness and completedness seem to have nothing to do with it. – commando May 24 '13 at 00:14
-
truth tree; it is a way to identify whether an argument is valid or not. it is much shorter than the truth table method. – user3741 May 24 '13 at 00:19
-
1@commando http://en.wikipedia.org/wiki/Truth_tree#See_also – David H May 24 '13 at 01:07
-
1http://en.wikipedia.org/wiki/Method_of_analytic_tableaux is what he actually means. maybe wikiped moved the link. – Thufir Dec 09 '13 at 14:25
3 Answers
14
Some informal definitions first:
Soundness is the property of only being able to prove "true" things.
Completeness is the property of being able to prove all true things.
So a given logical system is sound if and only if the inference rules of the system admit only valid formulas. Or another way, if we start with valid premises, the inference rules do not allow an invalid conclusion to be drawn.
A system is complete if and only if all valid formula can be derived from the axioms and the inference rules. So there are no valid formula that we can't prove.
Truth trees seem to be a method of evaluating a logical proposition (they are new to me, so this is a first glance assessment), however the rules are really just graphical versions of the normal rules of inference, so should be sound as long as the inference rules are. Of course completeness depends on the logical system. So for propositional logic, you're fine.
Luke Mathieson
- 243
- 1
- 6
2
Soundness, which states that provability implies validity
Γ ⊢ A ⇒ Γ ⊨ A
means that the calculus doesn't prove nonsense: If a tree is closed, then that means that the inference also holds semantically; we won't find tree proofs for inferences that aren't actually valid.
Completeness, which states that validity implies provability
Γ ⊨ A ⇒ Γ ⊢ A
means that the calculus is able to capture all inferences: If an inference holds semantically, then there is a closed tree for it; there will be no inferences that are semantically valid but can't be verified by the tree method.
While every reasonable calculus will be designed to be sound w.r.t. the semantics, completeness is (for FOL at least) a much less trivial and very powerful result: It means that cumbersome semantic considerations about truth in all conceivable structures can be replaced by a mechanical, easily verifiable procedure.
Note, though, that completeness dosen't imply decidability: Completeness means that we will detect all the inferences, but not necessarily all the non-inferences, as such.
In propositional logic, the truth tree test will give you a "yes" (all branches closed) for all inferences and a "no" (at least one branch open) for all non-inferences: Propositional logic is decidable. But in predicate logic, the truth tree test will give you a "yes" for all inferences, a "no" for some non-inferences, but on some non-inferences it will run forever and never come to an answer; and there is no other method that can do better: Predicate logic is undecidable.
Natalie Clarius
- 2,499
- 14
- 17
-
@Noah Schweber I suppose that by "not sufficient" you are pointing at undecidability; I added some clarification. – Natalie Clarius Jul 29 '20 at 21:30
-
Yes, that's exactly right. And I was (as you point out) being unfair to truth trees: unlike truth-tables, we can indeed leverage them for first-order logic. I've deleted my previous comment. – Noah Schweber Jul 29 '20 at 21:37
1
Taken from Restall's Logic:
- The tree method is sound. If X ⊢ A then X ⊨ A. That is, if an argument is valid according to trees, it is valid according to truth tables too.
- The tree method is complete. If X ⊨ A then X ⊢ A. That is, if an argument is valid according to truth tables, it is also valid according to trees.
Jonathan Scher
- 11
- 1