Agler (4.2) Symbolic Logic: Syntax, Semantics, and Proof, "Truth-Tree Decomposition Rules", 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.2 Truth-Tree Decomposition Rules

 

 

 

Brief summary:
Using the conjunction decomposition rule (∧D), we can decompose a conjunction in a truth tree by stacking the conjuncts in new rows, like this:

We make a check mark on any proposition that we have decomposed. When we apply the disjunction decomposition rule (∨D) we decompose a disjunction by making two branches and placing one disjunct under each, like this:

A tree is fully decomposed when we have decomposed all decomposable propositions in it. A tree branch consists of all the propositions found when we begin with a proposition at the bottom and follow upward through the tree. A branch is a closed branch when it contains a proposition ‘P’ and its literal negation ‘¬P,’ and we place an X marking at the bottom of the branch. A branch is a completed open branch when it is completely decomposed and yet  does not contain such a contradiction. At its  bottom we place an 0 marking. We have a completed open tree only if it has at least one completed open branch. However, we have a closed tree when all branches are closed. According to the decomposition descending rule, we decompose a proposition under every open branch that descends from that proposition. 

 

 

Summary

 

4.2 Truth-Tree Decomposition Rules

 

 

We will now learn two of the nine rules for decomposition for the language of predicate logic (PL). (Agler 105)

 

 

4.2.1 Conjunction Decomposition Rule (∧D)

 

We will need to determine whether to use a stacking, branching, or branching-and-stacking rule, depending on the sort of proposition that we are decomposing (105). We consider the following pair of propositions:

(R∧¬M), R∧(W∧¬M)

And we set up the tree for it like this:

 

As we can see, both propositions have a conjunction as the main operator. Recall that a conjunction is true only when both conjuncts are true. Thus it is true under only one truth-value assignment. [In the prior section (4.1) we learned that propositional forms that have only one truth-value assignment are decomposed using a stacking rule.] As we can see, line one has R∧¬M. It would be true, that is, v(R∧¬M) = T only if both conjuncts are true, that is, only if v(R) = T and v(¬M) =T. As we can see, we should stack the following two expressions below the given set of propositions: R and ¬M.

(Agler 106)

 

Here we are following the stacking rule called the conjunctive decomposition ∧D.

 
(Agler 106)

We will place this symbol ∧D in the right column, and just before it, we give the line number of the proposition where it came from. Also, since line 1 has had a decomposition rule applied to it, we place a checkmark ✔next to the proposition there.

 
(Agler 106)

 

Only when none of our decomposition rules can apply to our propositions do we have a fully decomposed tree.

Fully decomposed tree: A fully decomposed truth tree is a tree where all the propositions that can be decomposed have been decomposed.
(106)

 

Line 2 of our tree so far can be decomposed into R and W∧¬M. And W∧¬M can be further decomposed into W and ¬M.

 
(Agler 107)

 

As we can see, this tree has been fully decomposed (107).

 

 

4.2.2 Disjunction Decomposition Rule (∨D)

 

Agler lists all the decomposition rules in a table.

(107)

 

The next rule on our list, ∨D, is for disjunctions. A disjunction is true in three cases, and false in just one. [Recall from the prior section (4.1) that] when a propositional form is false under just one assignment, then we use a branching decomposition rule on it. In order to maintain the truth-functionality of disjunction, we put the disjuncts as they are at the ends of each branch [in other words, we do not negate either of them] (108).

 

So suppose we have the following propositions we want to decompose: R∧W, M∨¬W. We would do so like this:

 

Agler will now discuss some important terminology (109).

 

He writes: “all of the propositions in a branch can be catalogued by starting from the bottom of a branch and moving upward through the branch to the top of the tree” (109). And he defines a branch in this way:

Branch: A branch includes all the propositions obtained by starting from the bottom of the tree and reading upward through the tree.
(109)

So consider the tree from before. We can find one branch by starting at the bottom left, and work up one straight chain.

And we can follow a chain from the right side.

In the tree Agler makes, below, we can see that it has eight branches.

 

Agler’s next observation on terminology is the difference between fully and partially decomposed branches:

Fully decomposed branch:A branch is fully decomposed when all propositions in the branch that can be decomposed have been decomposed.

Partially decomposed branch: A branch is partially decomposed when there is at least one proposition in the branch that has not been decomposed.
(110)

 

Branches also can be understood as being either closed, open, or completed open branches.

Closed branch: A closed branch contains a proposition ‘P’ and its literal negation ‘¬P.’ A closed branch is represented by an ‘X.’
(111)

In the tree below, we see that in one branch there is both W and  ¬W. Thus it is closed and we place the X at the bottom of it (111).

 

Branches are open only if they are not closed.

Open branch: An open branch is a branch that is not closed, that is, a branch that does not contain a proposition ‘P’ and its literal negation ‘¬P.’
(111)

In the following there is one branch, and it is open, because it does not have a proposition and its literal negation.

 

We also notice that here the open branch has not yet been completed.

Completed open branch: A completed open branch is a fully decomposed branch that is not closed. That is, it is a fully decomposed branch that does not contain a proposition and its literal negation. An open branch is denoted by writing an ‘0’ at the bottom of the tree.
(112)

 

So let us complete that above tree and apply the new terminology to it.

(112)

We see that it has two fully decomposed branches. The left branch is completed open, because it cannot be further decomposed (so it is completed) but it has a contradiction (so it is closed). The right side branch as well is completely decomposed (so it is completed) but since there are no contradictions, it is open, and thus it is a completed open branch (112).

 

We now use the above terminology to classify trees. They can be either (a) an uncompleted open tree, (b) a completed open tree, or (c) a closed tree (113).

 

The tree is completed open so long as it has at least one completed open branch.

Completed open tree: A tree is a completed open tree if and only if it has at least one completed open branch. That is, a tree is a completed open tree if and only if it contains at least one fully decomposed branch that is not closed. A completed open tree is a tree where there is at least one branch that has an ‘0’ under it.
(113)

The tree below is a completed open tree, because it has a completed open branch (113).

 
(113)

 

The tree below is also a completed open tree. It has a closed branch. But that does not matter, because it still has at least one completed open branch (113-114).

 
(113)

 

A tree is closed only if all its branches are closed.

Closed tree: A tree is closed when all of the tree’s branches are closed. A closed tree will have an ‘X’ under every branch.
(114)

The following is a closed tree, because all its branches are closed.

In the tree below, both branches are closed, and thus the whole tree is closed.

 

There are also uncompleted open trees, which are neither completed open nor closed. This is because they are “unfinished because all of the branches have not been closed or there is not one completed open branch” (115).

 

 

4.2.3 Decompose Propositions under Every Descending Open Branch

 

Agler then notes the decomposition descending rule:

Decomposition descending rule: When decomposing a proposition ‘P,’ decompose ‘P’ under every open branch that descends from ‘P.’
(116)

So consider if we make a tree with these propositions, and we decide to decompose first line 2.

 
(116)

In accordance with our decomposition descending rule, when we decompose line 1, we do it under every open branch.

 

Now consider this tree that Agler makes, below.

When we get to line three, we have P∧M on the right-side branch. But when we decompose it, we do not do so on both branches. “This is because propositions are decomposed under open branches that descend from that proposition” (117).

 

We will look at a final example which will illustrate how decomposition can be terminated prior to having all of its contents completely decomposed. Recall that the decomposition descending rule states that “When decomposing a proposition ‘P,’ decompose ‘P’ under every open branch that descends from ‘P’ ” (116). So consider the tree below.

As we can see, we still have not decomposed line 2. However, the rule says that we only decompose under an open branch, but this one is closed. If we try to decompose it further, we will still only have closed branches.

We put the X under the left branch, because if we follow up it, we have ‘P’ and ‘¬P’. As well we find them if we follow up the right branch (118).

 

 

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

 

 

.