6. Conditional Derivations

6.1  An argument from Hobbes

In his great work, Leviathan, the philosopher Thomas Hobbes (1588-1679) gives an important argument for government.  Hobbes begins by claiming that without a common power, our condition is very poor indeed.  He calls this state without government, “the state of nature”, and claims

Hereby it is manifest that during the time men live without a common power to keep them all in awe, they are in that condition which is called war; and such a war as is of every man against every man…. In such condition there is no place for industry, because the fruit thereof is uncertain: and consequently no culture of the earth; no navigation, nor use of the commodities that may be imported by sea; no commodious building; no instruments of moving and removing such things as require much force; no knowledge of the face of the earth; no account of time; no arts; no letters; no society; and which is worst of all, continual fear, and danger of violent death; and the life of man, solitary, poor, nasty, brutish, and short.[8]

Hobbes developed what is sometimes called “contract theory”.  This is a view of government in which one views the state as the product of a rational contract.  Although we inherit our government, the idea is that in some sense we would find it rational to choose the government, were we ever in the position to do so.  So, in the passage above, Hobbes claims that in this state of nature, we have absolute freedom, but this leads to universal struggle between all people.  There can be no property, for example, if there is no power to enforce property rights.  You are free to take other people’s things, but they are also free to take yours.  Only violence can discourage such theft.  But, a common power, like a king, can enforce rules, such as property rights.  To have this common power, we must give up some freedoms.  You are (or should be, if it were ever up to you) willing to give up those freedoms because of the benefits that you get from this.  For example, you are willing to give up the freedom to just seize people’s goods, because you like even more that other people cannot seize your goods.

We can reconstruct Hobbes’s defense of government, greatly simplified, as being something like this:

If we want to be safe, then we should have a state that can protect us.

If we should have a state that can protect us, then we should give up some freedoms.

Therefore, if we want to be safe, then we should give up some freedoms.

Let us use the following translation key.

P:  We want to be safe.

Q:  We should have a state that can protect us.

R:  We should give up some freedoms.

The argument in our logical language would then be:

(P →Q)

(Q→R)

_____

(P→R)

This is a valid argument.  Let’s take the time to show this with a truth table.

premise  premise  conclusion
P Q R (P→Q) (Q→R) (P→R)
T T T T T T
T T F T F F
T F T F T T
T F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T

The rows in which all the premises are true are the first, fifth, seventh, and eighth rows.  Note that in each such row, the conclusion is true.  Thus, in any kind of situation where the premises are true, the conclusion is true.  This is our semantics for a valid argument.

What syntactic method can we use to prove this argument is valid?  Right now, we have none.  Other than double negation, we cannot even apply any of our inference rules using these premises.

Some logic systems introduce a rule to capture this inference; this rule is typically called the “chain rule”.  But, there is a more general principle at stake here: we need a way to show conditionals.  So we want to take another approach to showing this argument is valid.

6.2  Conditional derivation

As a handy rule of thumb, we can think of the inference rules as providing a way to either show a kind of sentence, or to make use of a kind of sentence.  For example, adjunction allows us to show a conjunction.  Simplification allows us to make use of a conjunction.  But this pattern is not complete:  we have rules to make use of a conditional (modus ponens and modus tollens), but no rule to show a conditional.

We will want to have some means to prove a conditional, because sometimes an argument will have a conditional as a conclusion.  It is not clear what rule we should introduce, however.  The conditional is true when the antecedent is false, or if both the antecedent and the consequent are true.  That’s a rather messy affair for making an inference rule.

However, think about what the conditional asserts:  if the antecedent is true, then the consequent is true.  We can make use of this idea not with an inference rule, but rather in the very structure of a proof.  We treat the proof as embodying a conditional relationship.

Our idea is this:  let us assume some sentence, Φ.  If we can then prove another sentence Ψ, we will have proved that if Φ is true then Ψ is true.  The proof structure will thus have a shape like this:

    \[ \fitchctx{ \subproof{\pline{\phi}}{ \ellipsesline\\ \pline{\psi} } \fpline{(\phi \lif \psi)} } \]

The last line of the proof is justified by the shape of the proof:  by assuming that Φ is true, and then using our inference rules to prove Ψ, we know that if Φ is true then Ψ is true.  And this is just what the conditional asserts.

This method is sometimes referred to as an application of the deduction theorem.  In chapter 17 we will prove the deduction theorem.  Here, instead, we shall think of this as a proof method, traditionally called “conditional derivation”.

A conditional derivation is like a direct derivation, but with two differences.  First, along with the premises, you get a single special assumption, called “the assumption for conditional derivation”.  Second, you do not aim to show your conclusion, but rather the consequent of your conclusion.  So, to show (Φ→Ψ) you will always assume Φ and try to show Ψ.  Also, in our logical system, a conditional derivation will always be a subproof.  A subproof is a proof within another proof.  We always start with a direct proof, and then do the conditional proof within that direct proof.

Here is how we would apply the proof method to prove the validity of Hobbes’s argument, as we reconstructed it above.

    \[ \fitchprf{\pline[1.] {(P \lif Q)} [premise]\\ \pline[2.]{(Q \lif R))} [premise]\\ } { \subproof{\pline[3.]{P}[assumption for conditional derivation]}{ \pline[4]{Q}[modus ponens, 1, 3]\\ \pline[5.]{R}[modus ponens, 2, 4] } \pline[6.]{(P \lif R)}[conditional derivation, 3-5] } \]

Our Fitch bars make clear what is a sub-proof here; they let us see this as a direct derivation with a conditional derivation embedded in it.  This is an important concept:  we can have proofs within proofs.

An important principle is that once a subproof is done, we cannot use any of the lines in the subproof.  We need this rule because conditional derivation allowed us to make a special assumption that we use only temporarily.  Above, we assumed P.  Our goal is only to show that if P is true, then R is true.  But perhaps P isn’t true.  We do not want to later make use of P for some other purpose.  So, we have the rule that when a subproof is complete, you cannot use the lines that occur in the subproof.  In this case, that means that we cannot use lines 3, 4, or 5 for any other purpose than to show the conditional (P→R).  We cannot now cite those individual lines again.  We can, however, use line 6, the conclusion of the subproof.

The Fitch bars—which we have used before now in our proofs only to separate the premises from the later steps—now have a very beneficial use.  They allow us to set aside a conditional derivation as a subproof, and they help remind us that we cannot cite the lines in that subproof once the subproof is complete.

It might be helpful to give an example of why this is necessary.  That is, it might be helpful to give an example of an argument made invalid because it makes use of lines in a finished subproof.  Consider the following argument.

If you are Pope, then you have a home in the Vatican.

If you have a home in the Vatican, then you hear church bells often.

_____

If you are Pope, then you hear church bells often.

That is a valid argument, with the same form as the argument we adopted from Hobbes.  However, if we broke our rule about conditional derivations, we could prove that you are Pope.  Let’s use this key:

S:  You are Pope.

T:  You have a home in the Vatican.

U:  You hear church bells often.

Now consider this “proof”:

    \[ \fitchprf{\pline[1.]{(S \lif T)} [premise]\\ \pline[2.]{(T \lif U))} [premise]\\ } { \subproof{\pline[3.]{S}[assumption for conditional derivation]}{ \pline[4]{T}[modus ponens, 1, 3]\\ \pline[5.]{U}[modus ponens, 2, 4] } \pline[6.]{(S \lif U)}[conditional derivation, 3-5]\\ \pline[7.]{S}[repeat, 3] } \]

And, thus, we have proven that you are Pope.  But, of course, you are not the Pope.  From true premises, we ended up with a false conclusion, so the argument is obviously invalid.  What went wrong?  The problem was that after we completed the conditional derivation that occurs in lines 3 through 5, and used that conditional derivation to assert line 6, we can no longer use those lines 3 through 5.  But on line 7 we made use of line 3. This violates the accessibility rule. Line 3 is an assumption, not something we know to be true; our reasoning from lines 3 through line 5 was to ask, if S were true, what else would be true? Auxiliary assumptions, and sentences derived from them, are only open so long as their scope lines continue. An assumption is discharged when its subproof ends. Open assumptions are assumptions that have not been discharged, while closed assumptions are assumptions that have been discharged.  When we are done with that conditional derivation, we can use only the conditional that we derived, and not the steps used in the conditional derivation.

6.3  Some additional examples

Here are a few kinds of arguments that help illustrate the power of the conditional derivation.

This argument makes use of conjunctions.

(P→Q)

(R→S)

_____

((P&R)→(Q&S))

We always begin by constructing a direct proof, using the Fitch bar to identify the premises of our argument, if any.

    \[ \fitchprf{\pline[1.]{(P \lif Q)} [premise]\\ \pline[2.]{(R \lif S)} [premise]\\ } { } \]

Because the conclusion is a conditional, we assume the antecedent and show the consequent.

    \[ \fitchprf{\pline[1.]{(P \lif Q)} [premise]\\ \pline[2.]{(R \lif S)} [premise]\\ } { \subproof{\pline[3.]{(P \land R)}[assumption for conditional derivation]}{ \pline[4]{P}[simplification, 3]\\ \pline[5.]{Q}[modus ponens, 1, 4]\\ \pline[6.]{R}[simplification, 3]\\ \pline[7.]{S}[modus ponens, 2, 6]\\ \pline[8.]{(Q \land S)}[adjunction, 5, 7] } \pline[9.]{((P \land R) \lif (Q \land S))}[conditional derivation, 3-8] } \]

Here’s another example.  Note that the following argument is valid.

(P→(S→R))

(P→(Q→S))

_____

(P→(Q→R))

The proof will require several embedded subproofs.

    \[ \fitchprf{\pline[1.]{(P \lif (S \lif R))} [premise]\\ \pline[2.]{(P \lif (Q \lif S))} [premise]\\ } { \subproof{\pline[3.]{P}[assumption for conditional derivation]}{ \subproof{\pline[4.]{Q} [assumption for conditional derivation]}{ \pline[5.]{(Q \lif S)}[modus ponens, 2, 3]\\ \pline[6.]{S}[modus ponens, 5, 4]\\ \pline[7.]{(S \lif R)}[modus ponens, 1, 3]\\ \pline[8.]{R}[modus ponens, 7, 6] } \pline[9.]{(Q \lif R)}[conditional derivation, 4-8] } \pline[10.]{(P \lif (Q \lif R))}[conditional derivation, 3-9] } \]

6.4  Theorems

Conditional derivation allows us to see an important new concept.  Consider the following sentence:

((P→Q) →(~Q→~P))

This sentence is a tautology.  To check this, we can make its truth table.

P Q ~Q ~P (P→Q) (~Q→~P) ((P→Q)→(~Q→~P))
T T F F T T T
T F T F F F T
F T F T T T T
F F T T T T T

This sentence is true in every kind of situation, which is what we mean by a “tautology”.

Now reflect on our definition of “valid”:  necessarily, if the premises are true, then the conclusion is true.  What about an argument in which the conclusion is a tautology?  By our definition of “valid”, an argument with a conclusion that must be true must be a valid argument—no matter what the premises are!  (If this confuses you, look back at the truth table for the conditional.  Our definition of valid includes the conditional: if the premises are true, then the conclusion is true.  Suppose now our conclusion must be true.  Any conditional with a true consequent is true.  So the definition of “valid” must be true of any argument with a tautology as a conclusion.)  And, given that, it would seem that it is irrelevant whether we have any premises at all, since any will do.  This suggests that there can be valid arguments with no premises.

Conditional derivation lets us actually construct such arguments.  First, we will draw our Fitch bar for our main argument to indicate that we have no premises.   Then, we will construct a conditional derivation.  It will start like this:

    \[ \fitchprf{} { \subproof{\pline[1.]{(P \lif Q)}[assumption for conditional derivation]}{ } } \]

But what now?  Well, we have assumed the antecedent of our sentence, and we should strive now to show the consequent.  But note that the consequent is a conditional.  So, we will again do a conditional derivation.

    \[ \fitchprf{} { \subproof{\pline[1.]{(P \lif Q)}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lnot Q} [assumption for conditional derivation]}{ \pline[3.]{\lnot P}[modus tollens, 1, 2]\\ } \pline[4.]{(\lnot Q \lif \lnot P)}[conditional derivation, 2-3] } \pline[5.]{((P \lif Q) \lif (\lnot Q \lif \lnot P))}[conditional derivation, 1-4] } \]

This is a proof, without premises, of ((P→Q)→(~Q→~P)).  The top of the proof shows that we have no premises.  Our conclusion is a conditional, so, on line 1, we assumed the antecedent of the conditional.  We now have to show the consequent of the conditional; but the consequent of the conditional is also a conditional, so we assumed its antecedent on line 2.   Line 4 is the result of the conditional derivation from lines 2 to 3.  Lines 1 through 4 tell us that if (P→Q) is true, then (~Q→~P) is true.  And that is what we conclude on line 5.

We call a sentence that can be proved without premises a “theorem”.  Theorems are special because they reveal the things that follow from logic alone.  It is a very great benefit of our propositional logic that all the theorems are tautologies.  It is an equally great benefit of our propositional logic that all the tautologies are theorems.  Nonetheless, these concepts are different.  “Tautology” refers to a semantic concept:  a tautology is a sentence that must be true.  “Theorem” refers to a concept of syntax and derivation:  a theorem is a sentence that can be derived without premises.

Theorem:  a sentence that can be proved without premises.

Tautology:  a sentence of the propositional logic that must be true.

6.5 How to Make a Conditional Proof

Conditional Proofs

A conditional proof (or deduction): allows us to prove conditional claims. The conditional asserts if the antecedent is true, then the consequent is true. A conditional proof assumes the antecedent of a conditional, then uses a series of discrete truth-preserving steps to move from the antecedent to the consequent such that if the antecedent is true, the consequent must be true. Each step is either a rule of inference or a rule of replacement such that whenever you have a sentence of one form you may replace it with a sentence of another form.

Notation: Each line of a proof must be enumerated and justified.

  1. Enumerate each line of a proof.
  2. Justify each sentence of a proof in a justification column to the right.
  3. For each non-derived sentence of a proof, write “premise” or “assumption.”
  4. For each derived sentence of a proof, write the name of the inference rule or replacement rule used, and the sentence(s) used to infer the derived sentence, in numerical order.
  5. Draw a horizontal line, a “fitch bar,” between non-derived sentences (e.g. premises and assumptions) and derived sentences.
  6. Draw a vertical “scope” line to the left of any non-derived sentences. 

Terms, Conventions and the Accessibility Rule:

Derived Sentence: a sentence obtained by applying a inference rule or a replacement rule.

Scope Line: a vertical scope line indicates the beginning and end of a proof or subproof.

Fitch Bar: a horizontal fitch bar separates non-derived sentences, assumptions and premises, from derived sentences.

Subproof: a proof within a proof. Subproofs are necessary for conditional proofs and indirect proofs.

Open a subproof: a subproof begins with an assumption, which must be justified by the citing “assumption for …” and the rule one hopes to use.

End a subproof: a subproof ends by using the rule indicated on the justification for the assumption, and citing the entire subproof.

Discharged Assumption: the assumption of a successfully ended subproof.

Open Assumption: assumption that has not been discharged.

Closed Assumption: assumption that has been discharged.

Accessibility Rule:  sentence is accessible if it can be used to infer a new sentence at a given line in a proof.  A sentence is accessible if it is an open assumption or falls within the scope of an open assumption.

Example: Proof that the following arguments are valid:

  1. Premises: P, Q. Conclusion: (P→Q).

    Scope line  – Vertical line
    Fitch bar – Horizontal line
    Justification – Right column
    Subproof – Line 3 & 4Notice that conditional proof is truth-preserving. Whenever P is true and Q is true, (P→Q) must be true.
    P Q (P Q)
    T T T T T
    T F T F F
    F T T T T
    F F T T F
  2. Premises: (P→Q), (Q→R). Conclusion: (P→R)

    Scope line  – Vertical line
    Fitch bar – Horizontal line
    Justification – Right column
    Open assumption – that P, Q, and R are only accessible while the scope line of the subproof is in effect (lines 3-5)Notice that conditional proof is truth-preserving. Whenever(P→Q) and (Q→R) are true, (P→R) must be true.
    P Q R (P Q) (Q R) (P R)
    T T T T T T T T T T T T
    T T F T T T T F F T F F
    T F T T F F F T T T T T
    T F F T F F F T F T F F
    F T T F T T T T T F T T
    F T F F T T T F F F T F
    F F T F T F F T T F T T
    F F F F T F F T F F T F

6.6  Key Concepts

Conditional Derivations

Conditional proof (conditional derivation): an ordered list of sentences in which every sentence is either a premise, is the special assumption for conditional derivation, or is derived from earlier lines using an inference rule. If the assumption for conditional derivation is Φ, and we derive as some step in the proof Ψ, then we can write after this Ψ) as our conclusion.

Subproof: a proof within a proof. Each subproof begins with an auxiliary assumption, whose scope is indicated by the scope line immediately to its left.

Assumption: is a non-derived sentence assumed during a proof for particular purposes. An assumptions is only in effect so long as its scope line continues.

Discharged Assumption: the assumption of a successfully ended subproof. Primary assumptions are never discharged.

Open Assumption: assumption that has not been discharged.

Closed Assumption: assumption that has been discharged.

Accessibility Rule: A sentence is accessible, can be used in a proof, if and only if it is an open assumption or falls within the scope of an open assumption.

Rule of Inference: Conditional proof
 

Notice that conditional proof is truth-preserving. Whenever P is true and Q is true, (P→Q) must be true.

P Q (P Q)
T T T T T
T F T F F
F T F T T
F F T F

 

Tautology (see also 5.6 Key Concepts): a sentence of propositional logic that must be true; it cannot possibly be false. A sentence is a tautology in propositional logic if the column under its main connective is true on every row of a complete truth table. Consider the truth table for ((P→Q) → (~Q→~P)):

P Q ((P Q) (~ Q ~ P))
T T T T T T F T T F T
T F T F F T T F F F T
F T F T T T F T T T F
F F F T F T T F T T F

Look at the column for the main connective, conditional : on every row, the sentence is true, so it is a tautology. Note: all tautologies are theorems, and all theorems are tautologies.

Theorem: a sentence that can be proved without premises. Theorems reveal claims that follow from logic alone. Consider the proof for ((P→Q) → (~Q→~P)):

Note: All theorems are tautologies, and all tautologies are theorems.

6.7  Exercises

Within this section, you will find two types of problems for the chapter material. Firstly there are interactive exercises that randomly test your knowledge. Secondly, there is a comprehensive list of exercise questions with all answers at the back of the text.

Interactive Exercises

A. Conditional Proofs. Prove the following arguments are valid.  This will require conditional proofs.

Coming soon! Until then refer to section A of the Full Exercise Question Sets below.

B. Prove the following theorems.

Coming soon! Until then refer to section B of the Full Exercise Question Sets below.

C. Make a truth table for each of the following complex sentences, in order to see when it is true or false.  Identify which are tautologies.  Prove the tautologies.

D. In normal colloquial English, write your own valid argument with at least two premises and with a conclusion that is a conditional. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like formal logic).  Translate it into propositional logic and prove it is valid.

 

Full Exercise Question Sets

  1. Conditional Proofs. Prove the following arguments are valid.  This will require conditional proofs.

    1. Premise:  P, Q.  Conclusion:  (PQ).
    2. Premise:  (PQ), (Q→R).  Conclusion: (P→R).
    3. Premise:  (P→Q), (SR).  Conclusion: ((~Q&~R)→(~P&~S).
    4. Premise:  (PQ).  Conclusion:  ((P&R)→Q).
    5. Premises:  ((R&Q)→S), (~P→(R&Q)).  Conclusion:  (~S→P).
    6. Premises:  (P~Q).  Conclusion:  (Q→~P).
    7. Premise:  (PQ), (P→R).  Conclusion: (P→(Q&R)).
    8. Premise:  (P→(Q→R)), Q.  Conclusion: (P→R).
  2. Prove the following theorems.

    1. (PP).
    2. ((PQ)((RP)(RQ))).
    3. ((P (QR))((PQ)(PR)).
    4. ((~PQ)(~QP)).
    5. (((PQ)&(PR))(P(Q&R))).
  3. Make a truth table for each of the following complex sentences, in order to see when it is true or false.  Identify which are tautologies.  Prove the tautologies.

    1. ((PQ)Q).
    2. (P(PQ)).
    3. (P(QP)).
    4. (P~P).
    5. (P~~P).
  4. In normal colloquial English, write your own valid argument with at least two premises and with a conclusion that is a conditional. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like formal logic).  Translate it into propositional logic and prove it is valid.


[8] Hobbes (1886: 64).

definition

License

Icon for the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Elementary Formal Logic Copyright © 2020 by Jenna Woodrow and Craig DeLancey is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License, except where otherwise noted.

Share This Book