Agler (4.5) Symbolic Logic: Syntax, Semantics, and Proof, "Truth-Tree Walk Through", summary

 

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Logic & Semantics, Entry Directory]
[David Agler, entry directory]
[Agler’s Symbolic Logic, entry directory]

[The following is summary. Boldface (except for metavariables) and bracketed commentary are my own. Please forgive my typos, as proofreading is incomplete. I highly recommend Agler’s excellent book. It is one of the best introductions to logic I have come across.]

 

 

 

Summary of

 

David W. Agler

 

Symbolic Logic: Syntax, Semantics, and Proof

 

Ch.4: Truth Trees

4.5 Truth-Tree Walk Through

 

 

 

Brief summary:
By using the four rules of truth-tree decomposition that Agler lays out, we can more efficiently decompose a tree, as seen in a number of examples. In certain cases, we will not even need to decompose all the propositions, on account of the fact that we were able to close all branches as early as possible.

 

 

Summary

 

4.5 Truth-Tree Walk Through

 

 

We will carefully examine three truth-trees. The first one has these propositions: M→P, ¬(P∨Q), and (R∨S)∧¬P. First we stack up the propositions at the top.

Next let us decompose the conjunction in line three. [Recall Rule 3 from section 4.4.3: we should decompose stacking before branching, because this means fewer operations down the line.]

We have another stacking rule for the negated disjunction in line 2, so let us decompose that next.

Now since line one will close off a branch, let us do that next.

As we can see, the right branch will close.

That leaves us with decomposing the disjunction on line 4.

And here both are open branches.

All decomposable propositions have been decomposed, so it is completed. And, it has at least one open branch, so it is open.

 

We will now decompose these propositions:

¬(M→P)

¬(P↔Q)

¬(P∨M)∨¬Q

P→M
(Agler 135)

So let us first set them as propositions.

[Again recall Rule 3 from section 4.4.3: we should use stacking rules before branching rules.] From this list we can see that there is just one proposition that takes a stacking rule, ¬(M→P), so in accordance with rule 3, we should start with this one.

[Recall Rule 2 from section 4.4.3: we should first use rules that close branches.] Suppose we next decomposed P→M. That would give us M and ¬P. But as we just got those already, we would not close any branches that way. Yet what if we decompose ¬(P↔Q)? This will give us two branches, one with P and ¬Q, and the other with ¬P and Q. The first of the two branches has a contradiction of P and ¬P. This means it will close. So we can do this one next.

And so it is the left branch that we mark as closed.

Now, what if we decomposed ¬(P∨M)∨¬Q? We would get two branches, one with ¬(P∨M) and the other with ¬Q. Since we have Q in the branch above, we would close off one of these newer branches. So let us do this one.

As we can see, it is the right branch that closes.

Now our choices are ¬(P∨M) and P→M. Since ¬(P∨M) takes a stacking rule, we should do that one next.

But we notice that this gives us ¬M, which contradicts M from above. So we mark this branch as closed.

But now there are no more branches along which to continue our decomposition. So we will not need to decompose P→M. Thus by following the rules and thinking strategically, we can save effort and make a more elegant tree.

The above walkthrough shows that even though a tree can be fully decomposed by decomposing propositions randomly, a tactical use of the decomposition rules will reduce the complexity of the tree and your total amount of work.
(137)

 

We now examine the following propositions:

P→Q

T→[(Q∨R)∨(¬S∨M)]

(P∨Q)∨R

(P→M)∨[W↔(¬S∨S)]

¬(¬P∨Q)

Let us place them as propositions.

This could potentially be a very complicated tree. Hence we need to look for contradictions so we can close branches as early as possible. Looking at the simplest propositions, in lines 1 and 5, we already see a way to close all branches early. ¬(¬P∨Q) will ultimately give us P and ¬Q. And P→Q will give us ¬P or Q. Since ¬(¬P∨Q) is a stacking rule, let us start with that.

Now let us decompose the doubly negated P.

And finally, we decompose the conditional of line 1.

And as we can see, this closes off both branches.

 

 

 

 

Agler, David. Symbolic Logic: Syntax, Semantics, and Proof. New York: Rowman & Littlefield, 2013.

 

 

.