[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.7: Predicate Logic Trees
7.2 Strategies for Decomposing Trees
Brief summary:
To decompose propositions in the language of predicate logic (RL) the most efficiently in truth trees, we should follow these rules.
Strategic Rules for Decomposing Predicate Truth Trees
1. Use no more rules than needed.
2. Decompose negated quantified expressions and existentially quantified expressions first.
3. Use rules that close branches.
4. Use stacking rules before branching rules.
5. When decomposing universally quantified propositions, use constants that already occur in the branch.
6. Decompose more complex propositions before simpler propositions.
(Agler 291)
Summary
Agler will give strategic rules for decomposing truth trees in the language of predicate logic (RL). He takes the rules for the language of propositional logic (PL) and adds others now relevant to RL.
Strategic Rules for Decomposing Predicate Truth Trees
1. Use no more rules than needed.
2. Decompose negated quantified expressions and existentially quantified expressions first.
3. Use rules that close branches.
4. Use stacking rules before branching rules.
5. When decomposing universally quantified propositions, use constants that already occur in the branch.
6. Decompose more complex propositions before simpler propositions.
(Agler 291)
Agler notes that rule 2 (“Decompose negated quantified expressions and existentially quantified expressions first”) and rule 5 (“When decomposing universally quantified propositions, use constants that already occur in the branch”) are of new interest to us now. He explains, “Rule (2) gives priority to (¬∃D), (¬∀D), and (∃D) over any use of (∀D). Rule (5) is present to avoid overly complex truth trees” (Agler 291). He has us consider these propositions.
| 1 | (∀x)(∀y)¬Pxy | P |
| 2 | (∃y)Pay | P |
[We will want eventually to close off branches if we can, which means we will want to find a contradiction. We could try to do that by formulating the propositions in lines 1 and 2 with constants but in a way that shows them as a contradiction. For them to contradict, they would need to have the same constants. We know that existential decomposition requires that the constant not appear before in the branch. So we should not use universal decomposition first to establish the constants. For, that will establish constants that we will be unable to use later in our existential decomposition, thereby preventing us from creating a contradiction on the basis of propositions sharing those constants. Instead, let us start with the existentially quantified statement. It already has the constant ‘a’, so we will use ‘b’.]
| 1 | (∀x)(∀y)¬Pxy | P |
| 2 | (∃y)Pay✔ | P |
| 3 | Pab | 2∃D |
[This means that we will want to try to decompose line 1 into the negation of line 3. It has two universal quantifiers, one for each variable. We do one at a time. First let us substitute ‘a’ in for ‘x’]
| 1 | (∀x)(∀y)¬Pxy | P |
| 2 | (∃y)Pay✔ | P |
| 3 | Pab | 2∃D |
| 4 | (∀y)¬Pay | 1∀D |
[We will not put a check mark after the proposition in line 1 at this step nor with the next decomposition, because we do not do so for universal decomposition. If you recall from
section 7.1, we do not do that, because we cannot exhaust all substitutions if the domain is infinite.] And as we can see, we are then just one step away from finding the contradiction. Here we continue to follow step 5, which tells us that for our universal decomposition to choose constants used already in the branch, in this case, ‘b’ (Agler 291).
| 1 | (∀x)(∀y)¬Pxy | P |
| 2 | (∃y)Pay✔ | P |
| 3 | Pab | 2∃D |
| 4 | (∀y)¬Pay | 1∀D |
| 5 | ¬Pab X | 4∀D |
(Agler 291)
For comparison, Agler has us consider the same set of propositions, but this time we ignore rules 2 and 5. [As we will see, it will eventually close the branch, but it will only be able to do so finally by following the rules and finding the contradiction.]
| 1 | (∀x)(∀y)¬Pxy | P |
| 2 | (∃y)Pay✔ | P |
| 3 | (∀y)¬Pmy | 1∀D |
| 4 | ¬Pmb | 3∀D |
| 5 | Pac | 2∃D |
| 6 | (∀y)¬Pay | 1∀D |
| 7 | ¬Pac X | 6∀D |
(Agler 291)
As we can see, the work we did in lines 3 and 4 did not in the end have any effect on our closing the branch. The first mistake we made was not doing the existential decomposition first, which then prohibited us from using ‘b’ again when we later did do an existential decomposition. At the same time, we also in line 3 broke the 5th rule, because we used a constant, ‘m’, which did not appear before in the branch.
Agler, David. Symbolic Logic: Syntax, Semantics, and Proof. New York: Rowman & Littlefield, 2013.
.
No comments:
Post a Comment