Formal Logic/Sentential Logic/Constructing a Complex Derivation

From Wikibooks, open books for an open world
< Formal Logic‎ | Sentential Logic
Jump to: navigation, search
← Subderivations and Discharge Rules ↑ Sentential Logic Theorems →



Constructing a Complex Derivation[edit]

An example derivation[edit]

Subderivations can be nested. For an example, we provide a derivation for the argument

\mathrm{P} \land \mathrm{R} \rightarrow \mathrm{T},\ \ \mathrm{S} \land \lnot \mathrm{T},\ \ \mathrm{S} \rightarrow \lnot \mathrm{Q}\,\!      \mathrm{P} \lor \mathrm{Q} \rightarrow \lnot \mathrm{R}\,\!

We begin with the premises and then assume the antecedent of the conclusion.

Note. Each time we begin a new subderivation and enter a temporary assumption, there is a specific formula we are hoping to derive when it comes time to end the derivation and discharge the assumption. To make things easier to follow, we will add this formula to the annotation of the assumption. That formula will not officially be part of the annotation and does not affect the correctness of the derivation. Instead, it will serve as an informal reminder to ourselves noting where we are going.

 
1.   \mathrm{P} \land \mathrm{R} \rightarrow\mathrm{T}\,\!   Premise
2.   \mathrm{S} \land \lnot \mathrm{T}\,\!   Premise
3.   \mathrm{S} \rightarrow \lnot \mathrm{Q}\,\!   Premise
 
4.     \mathrm{P} \lor \mathrm{Q}\,\!   Assumption    [\mathrm{P} \lor \mathrm{Q} \rightarrow \lnot \mathrm{R}]\,\!


This starts a subderivation to derive the argument's conclusion. Now we will try a Disjunction Elimination (DE) to derive its consequent:

\lnot \mathrm{R}\,\!


This will require the showing two conditionals we need for the antecedent lines of a DE, namely:

\mathrm{P} \rightarrow \lnot \mathrm{R}\,\!

and

\mathrm{Q} \rightarrow \lnot \mathrm{R}\,\!


We begin with the first of these conditionals.

 
5.       \mathrm{P}\,\!   Assumption    [\mathrm{P} \rightarrow \lnot \mathrm{R}]\,\!
     
6.         \mathrm{R}\,\!   Assumption    [\lnot \mathrm{R}]\,\!


This subderivation is easily finished.

 
7.         \mathrm{P} \land \mathrm{R}\,\!   5, 6 KI
8.         \mathrm{T}\,\!   1, 7 CE
9.         \lnot \mathrm{T}\,\!   2 KE


Now we are ready to discharge the two assumptions at Lines 5 and 6.

 
10.       \lnot \mathrm{R}\,\!   6–9 NI
   
11.     \mathrm{P} \rightarrow \lnot \mathrm{R}\,\!   5–10 CI


Now it's time for the second conditional needed for our DE planned back at Line 4. We begin.

 
12.       \mathrm{Q}\,\!   Assumption    [\mathrm{Q} \rightarrow \lnot \mathrm{R}]\,\!
     
13.         \mathrm{R}\,\!   Assumption    [\lnot \mathrm{R}]\,\!
14.         \mathrm{S}\,\!   2 KE
15.         \lnot \mathrm{Q}\,\!   3, 14 CE


Note that we have a contradiction between Lines 12 and 15. But line 12 is in the wrong place. We need it in the same subderivation as Line 15. A silly trick at Lines 16 and 17 below will accomplish that. Then the assumptions at Lines 12 and 13 can be discharged.

 
16.         \mathrm{Q} \land \mathrm{Q}\,\!   12, 12 KI
17.         \mathrm{Q}\,\!   16 KE
     
18.       \lnot \mathrm{R}\,\!   13–17 NI
   
19.     \mathrm{Q} \rightarrow \lnot \mathrm{R}\,\!   12–18 CI


Finally, with Lines 4, 11, and 19, we can perform the DE we've been wanting since Line 4.

 
20.     \lnot \mathrm{R}\,\!   4, 11, 19 DE


Now to finish the derivation by discharging the assumption at Line 4.

 
21.   \mathrm{P} \lor \mathrm{Q} \rightarrow \lnot \mathrm{R}\,\!   4–20 CI

The complete derivation[edit]

Here is the completed derivation.

 
1.   \mathrm{P} \land \mathrm{R} \rightarrow\mathrm{T}\,\!   Premise
2.   \mathrm{S} \land \lnot \mathrm{T}\,\!   Premise
3.   \mathrm{S} \rightarrow \lnot \mathrm{Q}\,\!   Premise
 
4.     \mathrm{P} \lor \mathrm{Q}\,\!   Assumption    [\mathrm{P} \lor \mathrm{Q} \rightarrow \lnot \mathrm{R}]\,\!
   
5.       \mathrm{P}\,\!   Assumption    [\mathrm{P} \rightarrow \lnot \mathrm{R}]\,\!
     
6.         \mathrm{R}\,\!   Assumption    [\lnot \mathrm{R}]\,\!
7.         \mathrm{P} \land \mathrm{R}\,\!   5, 6 KI
8.         \mathrm{T}\,\!   1, 7 CE
9.         \lnot \mathrm{T}\,\!   2 KE
     
10.       \lnot \mathrm{R}\,\!   6–9 NI
   
11.     \mathrm{P} \rightarrow \lnot \mathrm{R}\,\!   5–10 CI
   
12.       \mathrm{Q}\,\!   Assumption    [\mathrm{Q} \rightarrow \lnot \mathrm{R}]\,\!
     
13.         \mathrm{R}\,\!   Assumption    [\lnot \mathrm{R}]\,\!
14.         \mathrm{S}\,\!   2 KE
15.         \lnot \mathrm{Q}\,\!   3, 14 CE
16.         \mathrm{Q} \land \mathrm{Q}\,\!   12, 12 KI
17.         \mathrm{Q}\,\!   16 KE
     
18.       \lnot \mathrm{R}\,\!   13–17 NI
   
19.     \mathrm{Q} \rightarrow \lnot \mathrm{R}\,\!   12–18 CI
20.     \lnot \mathrm{R}\,\!   4, 11, 19 DE
 
21.   \mathrm{P} \lor \mathrm{Q} \rightarrow \lnot \mathrm{R}\,\!   4–20 CI