Class Notes
(810,487)

United States
(314,224)

Philosophy
(46)

2250
(23)

James Hildebrand
(23)

Lecture

# N08TreeSoundness&Completeness - Tree Soundness and Completeness.pdf

Unlock Document

Buffalo State College

Philosophy

2250

James Hildebrand

Spring

Description

PROOF OF THE SOUNDNESS, CONSISTENCY
AND COMPLETENESS OF THE TREE METHOD
T’s and F’s do not appear on trees (unless, of course, they are there as sentence letters ra-
ther than as truth value assignments). It is therefore a serious question whether the results ob-
tained on the truth table will be reflected by trees in all cases. If the tree method tells us that a
set is t-f inconsistent (by producing a closed tree for that set) will that set always be t-f inconsis-
tent, or will the tree method falsely identify some t-f inconsistent sets as t-f consistent (by pro-
ducing completed open branches under the sentences in those sets)? And if a set is t-f incon-
sistent, will the tree method always detect that fact (by producing a closed tree for that set)?
These two questions concern the soundness and the completeness of the tree method respec-
tively.
SOUNDNESS: If the tree method tells us that a set is t-f inconsistent, then that set really is
t-f inconsistent.
COMPLETENESS: If a set is t-f inconsistent, the tree method will tell us that it is.
Note that the two questions are distinct. The tree test might not pick out all the t-f inconsis-
tent sets, even though any sets that it does pick out are t-f inconsistent. In that case, it would be
sound but not complete. Or it might not only pick out all the t-f inconsistent sets, but also some
t-f consistent ones. In that case, it would be complete but not sound. So both claims need to be
proven separately.
PROOF OF THE SOUNDNESS OF THE TREE METHOD
Here is a brief proof of the soundness of the tree method:
Brief soundness proof: Suppose Γ is a t-f consistent set of sentences of SL.
This means that there is at least one truth value assignment, call it α, on which all
the sentences in Γ are true. The initial stage of the tree for Γ places all and only
the sentences in Γ on the top of that tree. Consequently, the initial tree consists
exclusively of sentences that are true on α. Now note that the decomposition
rules were designed in such a way as to carry truth down along at least one
branch. That is, if the sentence you are decomposing is true on a truth value as-
signment, at least one of the branches you generate when you decompose that
sentence must consist of sentences that are also all true on that same truth value
assignment. Since, i)after the initial stage, the tree only grows as a conse-
quence of the application of decomposition rules to sentences already on the
tree, ii)every time you apply a decomposition rule you will end up with at least
one branch consisting of sentences that are all true on any truth value assign-
ment on which the sentence you are decomposing is true, and iii) all trees must
be completed after a finite number of rule applications, the completed tree for Γ
must have at least one branch consisting of sentences that are all true on α, the
truth value assignment on which all the set members on the top of the tr
ee are
true. But a completed branch that has sentences on it that are all true on one
and the same truth value assignment cannot contain an atomic sentence and the
negation of that atomic sentence, since no truth value assignment can make both a sentence and its negation true. Consequently, such a branch cannot be a
closed branch, which means it must be a completed open branch.
To sum up, if Γ is a t-f consistent set of sentences of SL, then the completed
tree for Γ must contain at least one open branch. It follows that if the completed
tree for a set, Γ, does not have an open branch (so, is closed), then Γ must be t-f
inconsistent (because we’ve shown that were it not inconsistent, it would have to
have a completed open branch). So if the tree method tells us that a set is t-f in-
consistent (by producing a closed tree for that set) then that set really is t-f incon-
sistent.
The brief soundness proof I have just presented begs certain questions. Most notably, it
claims that the tree rules were designed in such a way as to carry truth down along at least one
branch, and it claims that because each rule individually has this feature that means the tree as
a whole will have to end up with a completed open branch. These are things that need to be
proven. So, in what follows, I restate the brief proof in a more thorough fashion, employing
mathematical induction. This will serve both to provide a further illustration of how mathematical
induction works and to answer the questions I have just raised. The more thorough proof will
also illustrate, in passing, why an important feature of the tree method, the prohibition on de-
composing sentences on branches on which they do not appear, is necessary. Without that
prohibition, the bare fact that each tree rule was designed in such a way as to carry truth down
along at least one branch would be inadequate to guarantee that the tree method as a whole
will always produce the right result, so a proof of the soundness of the tree method does not
follow just from a consideration of the individual rules.
To begin, recall that a tree is generated by means of a series of one-step extensions. The
first step is to list the set members. The second step is to apply a decomposition rule to a non-
literal sentence (supposing there is one) and check it off. The third step is to again apply a de-
composition rule to a non-literal sentence (supposing there still is one) and check it off. And so
on until all non-literal sentences have been checked off.
Each of the steps prior to the last one produces a one-step extension of the tree for Γ. The
first step, supposing it is not also the last step, produces a tree (let’s call it 1 ) that consists of a
single branch (the trunk) and that is as many lines long as there are sentences in Γ. The sec-
ond step lengthens T by one or two lines and perhaps by splitting the branch (depending on
1
which rule is applied) to produce a longer and perhaps wider tree, T 2. The third step does the
same as the second; it makes T grow2into a yet longer and perhaps wider tree, T . In gene3al,
the k step applies a tree rule to generate a longer and perhaps wider tree, T , that adds one or
k
two lines to T k-1nd either extends a branch or splits one.
I now want to prove by mathematical induction that if Γ is t-f consistent (which means there
is a truth value assignment, α, on which all the sentences in Γ are true), then the last of these
trees, which is the completed tree for Γ, must contain at least one branch, call this branch θ, that
consists of sentences that are all true on α. (We are assured by our proof of the decidability of
the tree method that there must be a last tree in the series and hence a completed tree for Γ.)
For the reason already given in the “brief soundness proof,” above, θ must also be an open
branch. (No truth value assignment can make both an atomic sentence and its negation true.
Consequently, if all the sentences on θ true on α, θ cannot contain an atomic sentence and its
negation and so must be open.)
Supposing I can bring this proof off, it will follow that, if Γ is t-f consistent, the tree for Γ must
have a completed open branch (and, contrapositively, if the completed tree for Γ does not have
an open branch — so is closed — then Γ is not t-f consistent — so is t-f inconsistent). That is, it
will follow that the tree method is sound. Let’s see if I can bring this proof off. Basis clause. The first one-step extension, step 1, of the tree for any t-f consistent set, Γ, pro-
duces a branch consisting of sentences that are all true on a tva, α.
Proof: Since Γ is t-f consistent there is a tva, α, on which all the sentences in Γ are true.
But the tree method dictates that step 1 produces a tree that has just a single
branch, consisting of all and only the sentences in Γ. So, step 1 produces a branch
consisting of sentences that are all true on a tva, α.
Inductive step. If each one-step extension from step 1 to step k produces a branch consisting of
sentences that are all true on α, then step k+1 produces a branch that consists of sen-
tences that are all true on α.
Supposing that I can prove that this inductive step is true, it will follow from it together with
the basis clause that every one step extension from the first up to and including the last, which
produces the completed tree for Γ, must produce a branch consisting of sentences that are all
true on α. Hence, the last one-step extension must produce a completed tree containing an
open branch. For, from the basis clause together with the inductive step, it follows that step 2
must produce a branch that consists of sentences that are all true on α. And from this fact to-
gether with the inductive step, it follows that step 3 must produce a branch that consists of sen-
tences that are all true on α. And so on for as many steps as there are on to the last. (We have
already proven that there must be a last when proving that the tree method is decidable.)
To prove that the inductive step is true, I first assume its antecedent and then try to show
that its consequent is entailed by this supposition. So I assume that the tree produced by steps
1 to k contains a branch, θ, consisting of sentences that are all true on α. And then I ask
whether this means that the application of a decomposition rule to an unchecked sentence in
this tree must produce a branch that consists of sentences that are all true on α.
Since there are nine different decomposition rules that could be applied to produce a one-
step extension, I obviously have nine different cases to consider. In fact, however, I will con-
sider ten cases. The tenth case arises from looking at the possibilities in a different way. As-
suming that the tree produced by steps 1 to k contains a branch, θ, consisting of sentences that
are all true on α, I could apply a decomposition rule to a sentence on θ or, if the tree has multi-
ple branches, to a sentence on some other branch than θ. The tenth case I consider is that I
apply any of the nine decomposition rules to a sentence on some other branch than θ. What
happens in this case is far from trivial, as it turns out. Let’s do that case first.
Case One: Step k+1 applies a tree rule to an unchecked sentence on some other branch than
θ, the branch in the tree produced by steps 1 to k that has all true sentences on it.
In this case the proof is trite (though what it teaches us about the tree method is not). Since
the tree method dictates that sentences be decomposed only on every branch that opens be-
neath them, not on branches that open above them, the application of a tree rule to an un-
checked sentence on a branch other than θ produces no changes on θ. This means that the
“extension” of θ in Tk+1 (the tree produced by step k+1) just is θ (θ certainly does not close — a
fact that we represent graphically by drawing a vertical line beneath the last sentence on θ, to
indicate that it is continuing unchanged). Since we are supposing that θ as it is in T hak sen-
tences on it that are all true on α, and step k+1 extends θ unchanged, it follows trivially that step
k+1 produces a branch that consists of sentences that are all true on α.
Note how this case relies on an important feature of the tree method: that sentences only
get decomposed on the branches that open beneath them, not on branches that grow out from
nodes above them. Had the tree method not included this feature, our soundness proof would fail at this point. (We would not be able to prove Case One.) We know from experience that
some t-f consistent sets have trees with some closed branches. Were we to allow the non-
literal sentences that occur on these branches to be decomposed on θ the tree would close
when it should not and the method would be unsound. So it is essential to the soundness of the
tree method that we not allow sentences to be decomposed on branches that open above them.
(The inverse feature, that we must decompose sentences on every branch that opens be-
neath them, will be shown to be necessary when considering the completeness of the tree
method.)
Case Two: Step k+1 applies the “&D” rule to some unchecked sentence on θ.
In this case the tree produced by step k+1 adds two lines below θ on which a sentence of
the form P and a sentence of the form Q occur. Since these sentences are entered by &D,
there must be a sentence of the form P & Q on θ that step k+1 has checked off. By the induc-
tive hypothesis, all the sentences on θ are true on α, so α(P v Q)=T. But then by the & rule
α(P)=α(Q)=T. It follows that step k+1 produces a tree with at least one branch (θ as further ex-
tended by the two lines adding P and Q) that has sentences on it that are all true on α.
Case Three: Step k+1 applies the “vD” rule to some unchecked sentence on θ.
In this case the tree produced by step k+1 adds two branches below θ, there is a sentence
of the form P v Q on θ that step k+1 has checked off, and one of the branches below θ adds a
sentence of the form P while the other adds a sentence of the form Q. By the inductive hy-
pothesis, all the sentences on θ are true on α, so P v Q must be true on α. But if a sentence of
the form P v Q is true on some truth value assignment, then at least one of P and Q must be
true on that assignment, according to the v rule. It follows that step k+1 produces a tree with at
least one branch (θ as further extended either by the branch adding P or by the branch adding
Q) that has sentences on it that are true on α.
Case Four: Step k+1 applies the “⊃D” rule to some unchecked sentence on θ.
In this case the tree produced by step k+1 adds two branches below θ, there is an un-
checked sentence of the form P ⊃ Q on θ that step k+1 has checked off, and one of the
branches below θ adds a sentence of the form ~P while the other adds a sentence of the form
Q. By the inductive hypothesis, all the sentences on θ are supposed to be true on α, so α(P ⊃
Q)=T. But then either α(P)=F or α(Q)=T, by ⊃ rule. But then by ~ rule either α(~P)=T or
α(Q)=T. It follows that step k+1 produces a tree with at l

More
Less
Related notes for 2250