Agler (4.4) Symbolic Logic: Syntax, Semantics, and Proof, "Basic Strategies", 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.4 Basic Strategies

Brief summary:
In order to decompose a proposition in a truth-tree as efficiently as possible, we should follow certain rules, namely:

Strategic rule 1: Use no more rules than needed.
Strategic rule 2: Use rules that close branches.
Strategic rule 3: Use stacking rules before branching rules.
Strategic rule 4: Decompose more complex propositions before simpler propositions.

For the first rule, if for example we just need to know if the tree is open, we only need to find one completed open branch, and we can leave the rest unfinished. For the second rule, we can minimize the amount of decompositions by closing off branches as early as possible. For the third rule, we minimize the decompositions by stacking before branching; for, if we branch first, we have to repeat more operations, as we have more branches along which to stack formula. And for the fourth rule, by decomposing complex propositions first, we do not have to repeat complex ones further down, as we multiply the branches as we go.

Summary

4.4 Basic Strategies

Agler will offer some basic strategies for decomposing truth-trees more efficiently. He lists them now, and he will address each one in turn:

Strategic rule 1: Use no more rules than needed.
Strategic rule 2: Use rules that close branches.
Strategic rule 3: Use stacking rules before branching rules.
Strategic rule 4: Decompose more complex propositions before simpler propositions.
(Agler 127)

4.4.1 Strategic Rule 1

The first rule:

Strategic rule 1: Use no more rules than needed.

(Agler 127)

Some tasks do not require that we use all possible decompositions. We might just need only a few to determine if the propositions have certain properties. [Recall from section 4.2.2 that a completed open branch is a fully decomposed branch that is not closed, meaning that it does not contain a proposition and its literal negation. And a tree is a completed open tree if and only if it has at least one completed open branch.] For example, in order to determine if the tree is open, we just need to find one completed open branch. Agler illustrates with the following example.

(P∧¬W)∧¬M

M∨(¬M∨P)

(Agler 128)

First we set the propositions.

Then we decompose the conjunction in the first line.

Now let’s decompose the conjunction in line 3.

And finally, let us decompose the disjunction in line 2.

As we can see, the left branch has no more formulas to decompose [notice all the decomposable ones in that branch have checkmarks.] But also, there is not a proposition and its literal negation. Thus it is open.

Do we need to decompose the complex formula at the right branch? No, because we already determined the tree is an open tree, and so we can end here.

4.4.2 Strategic Rule 2

The second rule states:

Strategic rule 2: Use rules that close branches.

(Agler 128)

Whenever we “decompose a complex proposition, it must be
decomposed into every open branch below the decomposed proposition” (128). [To make the task more efficient, it would be better to close off branches sooner rather than later, because this way we have fewer branches under which to decompose the other propositions from above.] Thus, “It is generally advisable to decompose propositions that will close branches” (128).

Agler illustrates with the following set of propositions:

[Let us do it the wrong way first to see why Agler’s way is better. We will first decompose the disjunction on line 2.

At this point, we see that line 1 has negations of terms in our branches. But we will here do it the wrong way and decompose a different proposition, namely, the disjunction in line 3.

And finally we decompose the disjunction from line 1.

We then determine which branches are opened and closed.

] Agler first decomposes the disjunction in line 2.

Now note that in line 1 we have negations of M and P, so we should do this line next. That way, we can close off some branches early.

As we can see, there are contradictions on the far left and the far right branches.

Now we only need to decompose line 3 below the middle two branches.

And now we can assess which are open and which are closed.

[As we can see, we get the same results as with the less efficient way that we tried first.] This tree is completed open because there is at least one completed open branch (129).

4.4.3 Strategic Rule 3

We now examine the third strategic rule.

Strategic rule 3: Use stacking rules before branching rules.

(Agler 130)

Agler says that we want our trees “to be tall and not bushy”. [Suppose two situations. In one, you branch early on, then stack later. In this case, you do more work, because you may need to decompose the same stacking propositions along each branch. But if you did the stacking ones first, then all these are decomposed along a single branch. Then when you decompose the branching ones, all the stacking have been done already, and so you will not need to double them.]

Whenever you decompose a complex proposition, it must be decomposed into every open branch below the decomposed proposition. Using stacking rules before branching rules has the benefit of simplifying trees.

(130)

Agler will illustrate with these propositions: ¬M∨Q and (R∧Q)∧P. First we place them as propositions at the top of the tree.

Now let us do it the wrong way first. In other words, we will first do the branching one. So let us decompose the disjunction in line 1.

Next, let us decompose the conjunction in line 2.

As we can see, this leaves us with another conjunction in line 4. Let us decompose that.

Now we are done.

Suppose instead that we first used the stacking rule. So first we decompose the conjunction in line 2.

Next we decompose the conjunction in line 3.

And finally we decompose the disjunction in line 1.

As we can see, this is more efficient. (131)

4.4.4 Strategic Rule 4

The fourth rule is:

Strategic rule 4: Decompose more complex propositions before simpler propositions.

(131)

Agler says that this is the weakest of the rules. [His point seems to be that it has the least effect on efficiency. He will demonstrate by showing two different ways to decompose propositions. The one that follows this rule will have the same number of branches and decompositions. However, along those branches there will be simpler propositions.] He illustrates with the propositions: (M∨S)∨(Q∨R) and R∨S. [This first manner of doing it will show us the better way.] So let us first set them up.

Now let us follow the rule and do the more complex one first. So we decompose the disjunction in line 1.

[At this point it might be arbitrary which to do next, since all are equally complex now.] Let us now decompose the disjunctions at ends of each branch.

And finally we decompose the disjunction in line 2.

Now we will do it the slightly less efficient way. Instead of starting with the more complex formulation, we well decompose the simpler one, the disjunction in line 2.

Next we decompose the disjunction in line 1.

And finally we decompose the disjunctions in line 4.

Agler notes: “Although using strategic rule 4 may not reduce the overall size of the tree, it can help simplify the number of different applications of a rule applied” (132). [His point might be the following. So look at the wrong way above. In line 4, we applied the disjunction rule to two different formulas, namely, M∨S and Q∨R. However, in the right way, at that step we only applied it to one formula, R∨S. Another thing we might note is that in the right way, we write fewer letters.]

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

.