1.8 Natural deduction

Inference schemes

Natural deduction is a method of proving the logical validity of inferences, which, unlike truth tables or truth-value analysis, resembles the way we think. It consists in constructing proofs that certain premises logically imply a certain conclusion by using previously accepted simple inference schemes or equivalence schemes. The following three inference schemes are among the ones we will use:

α → β
α modus ponens
β
α → β
¬β modus tollens
¬α
α ∨ β
¬α disjunctive syllogism
β

The logical validity of these inference schemes can be verified by truth tables or truth-value analysis, but this is hardly necessary since their validity is sufficiently obvious to intuition. То the right of each scheme is written the name by which we will denote it. To see how the natural deduction method works, suppose that “A”, “B”, “C”, “D” and “E” are some particular sentences participating in the following inference:

1. А→В
2. B∨(A∨C)
3. B→D
4. ¬D
5. C→E/ E

The conclusion of the inference is the sentence E. The forward slash mark (“/”) functions as the line that separates the premises from the conclusion. We will prove that the conclusion logically follows from the premises using the above three inference schemes. From 3. and 4. by modus tollens we can infer ¬В:

6. ¬В 3, 4, modus tollens

We number each line so that we can refer to it if we further make inferences in which it is a premise. To the right of each deduced sentence, we write from which previous lines and by which scheme it is obtained.

As a next step, from 2. and 6. we may infer А∨С by disjunctive syllogism (to α in the inference scheme corresponds B and to β – А∨С):

7. А∨С 2, 6, disjunctive syllogism

From 1. and 6. by modus tollens we can derive ¬А:

8. ¬А 1, 6, modus tollens

From the last two sentences we get:

9. C 7, 8, disjunctive syllogism

And finally, from 5. and 9. by modus ponens, we get the desired conclusion E:

10. E 5, 9, modus ponens

Here is the complete list of inference schemes we will use in the natural deduction proof procedure1:

α → β modus ponens (MP) α → β modus tollens (MT)
α ¬β
β ¬α


α ∨ β disjunctive syllogism (DS) α → β hypothetical syllogism (HS)
¬α β → γ
β α → γ


α ∧ β simplification (S) α addition (Add)
α α ∨ β


α conjunction (Conj): (α→β) ∧ (γ→δ) constructive dilemma (CD)
β α ∨ γ
α ∧ β β ∨ δ


α → β absorption (Abs)
α → (α∧β)

As a further example, consider the following proof by natural deduction:

1. F→G
2. ¬(F∧G)∧L
3. (G∨H)→(I∧J)
4. F∨(K∨G)
5. ¬K∧L / I∨H
6. ¬(F∧G) 2, S
7. F→(F∧G) 1, Abs
8. ¬F 6, 7, MT
9. K∨G 4, 8, DS
10. ¬К 5, S
11. G 9, 10, DS
12. G∨H 11, Add
13. I∧J 3, 12, MP
14. I 13, S
15. I∨H 14, Add

We want to show that the five premises logically imply the sentence I∨H (written after the last premise, separated by a slash). 6. is derived from 2. by simplification, with α in the inference scheme being ¬(F∧G) and β being L. 8. is obtained from 6. and 7. by modus tollens, with F corresponding to α and F∧G to β. 9. is derived from 4. and 8. by disjunctive syllogism (α is F and β is K∨G). 10. is derived from 5. by simplification (α is ¬K and β is L). 13. is obtained from 3. and 12. by modus ponens (α is G∨H and β is I∧J).

Now let us prove that the following argument is logically valid:

If Alice left in the morning, she has already arrived.
If Alice has arrived, Bob knows about it.
Alice left in the morning or at noon.
If Bob knew that Alice had arrived, he would have called.
Bob didn’t call.
Alice left at noon.

We symbolize the argument’s simple sentences as follows:

M – Alice left in the morning
A – Alice has arrived.
K – Bob knows that Alice has arrived.
N – Alice left at noon.
C – Bob called.

Then the symbolic representation of the inference will be

M → A
A → K
M ∨ N
K → C
¬C
N

Here is a natural deduction proof that the inference is valid:

1. M → A
2. A → K
3. M ∨ N
4. K → C
5. ¬C / N
6. M→K 1, 2, HS
7. M→C 6, 4, HS
8. ¬M 5, 7, MT
9. N 3, 8, DS

As a rule, there are different proofs for the same inference. For example, the validity of the above inference can be proven alternatively by:

1. A→B
2. B→C
3. A∨D
4. C→E
5. ¬E / D
6. ¬C 4, 5, MT
7. ¬B 2, 6, MT
8. ¬А 1, 7, MT
9. D 3, 8, DS

Natural deduction differs from truth tables and truth-value analysis in that it is a proof procedure rather than a decision procedure. Decision procedures are general algorithms (recipes) that always bring us the answer we need. Using a truth table or a truth-value analysis, we have a guarantee that we will get the answer to whether some particular sentences (formulas) logically imply a sentence (formula), or whether two sentences are logically equivalent (both with respect to propositional logic). On the contrary, proof procedures are not like recipes whose application guarantees the desired result. Although it is true that if an inference is logically valid there is a natural deduction proof of this, we may not be able to find that proof. Because of this, decision procedures are preferable to proof procedures. However, the former are not always possible. For example, unlike propositional logic, where we have truth tables and true-value analysis, in predicate logic it is not possible to formulate a universal decision procedure for logical inference.

Equivalence schemes

In addition to inference schemes, equivalence schemes are used in natural deduction, such as the following called transposition:

α→β ⇔ ¬β→¬α

That arbitrary expressions of the form α→β and ¬β→¬α are logically equivalent can be verified by a truth table or a truth-value analysis. Unlike inference schemes, equivalence schemes in natural deduction can be used in two ways. The first is based on the fact that equivalent expressions logically follow from each other. Hence, an equivalence scheme contains two inference schemes. For example, the above equivalence scheme contains these two inference schemes:

α → β ¬β → ¬α
¬β → ¬α α → β

We can make inferences by both of them. For example, if in a natural deduction proof we have come to the sentence

А→(В∧¬С)

we can deduce from it

¬(В∧¬С)→¬А

(the form of the first sentence is α→β and that of the second is ¬β→¬α). But also vice versa – if we have come to the second sentence, we can deduce the first. This is one of the ways in which equivalence schemes can be used.

The other way is based on the principle of substitution of equivalents, which was discussed at the end of 1.6 Logical inference and logical equivalence. The principle allows us to replace an expression with a logically equivalent expression when the first is part of another expression . For example, on the basis of the principle of substitution of equivalents, using transposition we can replace any expression of the form α→β by ¬β→¬α and vice versa when these expressions are parts of other expressions. For example, if in a natural deduction proof we have come to the sentence

¬[А→(В∧¬С)]∧D

we can deduce from it

¬[¬(В∧¬С)→¬А]∧D

The second sentence is derived from the first by replacing its part “A→(B∧¬C)”, which has the form α→β, with the logically equivalent sentence “¬(B∧¬C)→¬A” having the form ¬β→¬α.

As an example of the two ways of using equivalence schemes, let us see how through transposition and the equivalence scheme

α ⇔ ¬¬α

which we will call double negation, from “A→B” and “C→¬B” we can derive “A→¬C” (the proof also uses one of the inference schemes):

1. A→B
2. C→¬B / A→¬C
3. ¬¬B→¬C 2, transposition
4. В→¬С 3, double negation
5. А→¬С 1, 4, HS

The derivation of 3. is an example of the first way an equivalence scheme can be used – 3. is logically equivalent to 2. and therefore follows from it. In the derivation of 4. the principle of substitution of equivalents is used – 4. is obtained from 3. by replacing its part “¬¬B” with the logically equivalent sentence “B”.

Here is the full list of equivalence schemes that can be used in the natural deduction proof procedure. For each of them, through a truth table or a truth-value analysis, it can be seen that the expressions on the sides of “⇔” are indeed logically equivalent.

transposition (Trans): α→β ⇔ ¬β→¬α

double negation (DN): ¬¬α ⇔ α

exportation (Exp): α→(β→γ) ⇔ (α∧β)→γ

material implication (Imp): α→β ⇔ ¬α∨β
¬(α→β) ⇔ α∧¬β

De Morgan (De M): ¬(α∧β) ⇔ ¬α∨¬β
¬(α∨β) ⇔ ¬α∧¬β

commutation (Com): α∧β ⇔ β∧α
α∨β ⇔ β∨α

association (Assoc): α∧(β∧γ) ⇔ (α∧β)∧γ
α∨(β∨γ) ⇔ (α∨β)∨γ

distribution (Distr): α∧(β∨γ) ⇔ (α∧β)∨(α∧γ)
α∨(β∧γ) ⇔ (α∨β)∧(α∨γ)

material equivalence (Equiv): α↔β ⇔ (α→β)∧(β→α)
α↔β ⇔ (α∧β)∨(¬α∧¬β)

tautology (Taut): α∧α ⇔ α
α∨α ⇔ α

As a further example, let us prove the logical validity of the following argument that God does not exist. The validity of the argument does not mean that thereby it is proven that God does not exist – some of the premises may be false. By the way, it is interesting to reflect which premise (premises) would be challenged by someone who believes God exist.

If God exists, he is good and almighty.
If God is not able to eliminate suffering in the world, he is not almighty.
If God does not want to eliminate suffering in the world, he is not good.
If God wanted to eliminate suffering in the world and was able to do it, then there would be no suffering.
There is suffering in the world.
God does not exist.

We symbolize the simple sentences by (say):

E – God exists.
G – God is good.
A – God is almighty.
F – God is able to eliminate suffering in the world.
W – God wants to eliminate suffering in the world.
S – There is suffering in the world.

When we symbolize natural language sentences in natural deduction, we try to use letters that are reminiscent of the simple sentences for which they are substituted. This is the reason why we use uppercase Latin letters instead of the usual propositional letters (“p”, “q”...).

The argument is symbolically represented by:

E→(G∧A)
¬F→¬A
¬W→¬G
(W∧F)→¬S
S
¬E

Here is a proof of its logical validity:

1. E→(G∧A)
2. ¬F→¬A
3. ¬W→¬G
4. (W∧F)→¬S
5. S / ¬E
6. ¬¬S 5, DN
7. ¬(W∧F) 4, 6, MT
8. ¬W∨¬F 7, De M
9. (¬W→¬G)∧( ¬F→¬A) 3, 2, Conj
10. ¬G∨¬A 8, 9, CD
11. ¬(G∧A) 10, De M
12. ¬E 1, 11, MT

Indirect proof and conditional proof

Indirect proof, also called reductio ad absurdum (Latin: reduction to absurdity), is a method to prove that some sentence is a logical consequence of some premises by assuming its negation. If as a result of the assumption we come to a contradiction (that is, to a sentence and its negation), this shows that it is not possible for the assumption to be true and that, therefore, its opposite is necessarily true under the premises, that is, it is implied by them.

The validity of the indirect proof is based on the law of non-contradiction and the law of excluded middle. This is evident from the following. The fact that (given the premises) by a sequence of logically valid inferences the assumption of ¬α leads to a contradiction (β∧¬β) demonstrates that if ¬α is true, β∧¬β also has to be true. But the law of non-contradiction excludes the latter, which is why ¬α cannot be true. However, by the law of excluded middle at least one of α and ¬α has to be true, and as ¬α is not true the only alternative is that α is true (given the premises).

Consider the following deduction, where an indirect proof is used:

1. (A→B)→¬D
2. D∨(C∧¬E)
3. C→E / A
4. ¬A assumption
5. ¬A∨B 4, Add
6. A→B 5, Imp
7. ¬D 1, 6 MP
8. C∧¬E 2, 7, DS
9. C 8, S
10. ¬E∧C 8, Com
11. ¬E 10, S
12. E 3, 9, MP – contradicts 11
13. A 4–12, reductio ad absurdum

In 4. we have assumed that the sentence ¬A is true. This is only an assumption – we do not claim that it is true (actually, we want to prove that it is false and hence its negation A is true). Therefore, this sentence, as well as all sentences that depend on it (those derived with its help), are shifted to the right. In this way we indicate that they may not be true – they are used solely for the purpose of the indirect proof. 5. depends on the assumption as it is derived from it; 6. is a consequence of 5. and thus the dependency is passed on to it as well; the same applies to 7., which is a consequence of 6. and 1., etc. Thus, by a series of inferences that depend on the assumption, in 12. we come to a contradiction. This proves the truth (given the premises) of A – the negation of the assumption, which is why it is no longer written to the right in 13. The rationale for affirming A in 13. is the whole series of inferences beginning with the assumption and ending with the contradiction.

In the example above, the sentence we deduced by an indirect proof was the final conclusion of the natural deduction. However, we could use indirect proofs to derive sentences that are not the final conclusion but that can be used to reach it. In this case it is important that, once we have completed an indirect proof, we no longer use the sentences written to the right, under the assumption, since they only serve the indirect proof procedure and may not be true (given the premises). Here is an example of using reductio ad absurdum twice in a single natural deduction proof:

1. A→(C∨¬B)
2. (B∧C)→(A∧D)
3. B / A↔C
4. ¬(A→C) assumption
5. A∧¬C 4, Imp
6. A 5, S
7. C∨¬B 1, 6, MP
8. ¬C 5, S (and Com)
9. ¬B 7, 8, DS – contradicts 3
10. A→C 4–9, reductio ad absurdum
11. ¬(C→A) assumption
12. C∧¬A 11, Imp
13. C 12, S
14. B∧C 3, 13, Conj
15. A∧D 2, 14, MP
16. A 15, S
17. ¬A 12 S (and Com) – contradicts 16
18. C→A 11–17, reductio ad absurdum
19. (A→C)∧(C→A) 10, 18, Conj
20. A↔C 19, Equiv

Since we want to prove the sentence A↔C, the plan is first to prove the conditionals A→C and C→A, from which by the equivalence scheme α↔β ⇔ (α→β)∧(β→α) we can deduce the desired sentence. The conditionals are derived by two indirect proofs. In 4. we assume the negation of A→C, and through a series of inferences we get to a contradiction, which allows us to derive A→C in 10. This sentence is no longer dependent on the assumption and therefore it is not written on the right. Once we have completed an indirect proof, we can no longer refer to the sentences used in it (those indented to the right). So, after 10. we are allowed to use as premises 10. itself (A→C) as well as the sentences before 4. but not the sentences from 4. to 9. In 11. we assume the negation of C→A and through a series of inferences we come to a contradiction, which enables us to establish the truth of C→A, therefore writing it on the left. At this point, we are not allowed to use the sentences from 11. to 17. anymore. In general, the rule of using assumptions is as follows: as long as we are within a proof by assumption (an indirect proof in this case), we are entitled to refer to both the sentences that are dependent on the assumption (those on the right) as well as the sentences that are independent of it (those on the left). However, once the proof by assumption is completed, we are no longer allowed to use the sentences it consists of. In 18. we have established the truth of A→C and C→A (given the premises), and the proof continues by connecting them into a conjunction and getting the final conclusion А↔С using the equivalence scheme of material equivalence.

Above, in order to derive a sentence α, we have assumed its negation ¬α and, getting to a contradiction, we have deduced α. It is clear, however, that we can also do the opposite – we can assume α and, after getting to a contradiction, deduce ¬α. This may be considered the same the only difference being an additional application of double negation: we are assuming α but because of the equivalence scheme of double negation it is the same as assuming ¬¬α (a negation). So, after coming to a contradiction we can deduce ¬α.

Another kind of proof in which an assumption is used is the conditional proof. As in the indirect proof, it is assumed in it the truth of a sentence in order to prove the truth of another sentence. The sentence assumed may not be true, so we indent it to the right and do the same with all sentences that are dependent on it, thus marking them as uncertain (perhaps false). Once the conditional proof is complete these sentences can no longer be used – they are used solely for the purpose of the conditional proof. In contrast, the sentence derived by the conditional proof as a whole is true with certainty (given the truth of the premises).

In particular, a conditional proof proceeds as follows. Assuming the truth of a sentence α, if we are able (as a result of the assumption) to logically derive a sentence β, thereby we have shown that if α is true, then β is true; in other words we have shown that the conditional sentence “If α, then β” (that is, α→β) is true, although α and β themselves may not be true.

Let's look at the following example:

1. (¬P∨Q)→¬S
2. (S∧T)∨(Q→P) / ¬P→¬Q
3. ¬P assumption
4. ¬P∨Q 3, Add
5. ¬S 1, 4, MP
6. ¬S∨¬T 5, Add
7. ¬(S∧T) 6, De M
8. Q→P 2, 7, DS
9. ¬Q 8, 3, MT
10. ¬P→¬Q 3–9, conditional proof

In 3. we have assumed that the sentence ¬P is true. This is an arbitrary assumption – we don’t know whether it is true or false (given the premises). Therefore it is indented to the right along with the sentences that depend on it (from 3. to 9.). In 10. is the conditional proof’s conclusion ¬P→¬Q. We are sure it is true (given the premises) because what it states can be expressed by the sentence “If ¬P is true, then ¬Q is true” and the sequence of inferences from 3. to 9. proofs it. The sequence demonstrates that ¬Q is a logical consequence of ¬P (starting from ¬P, by a series of logically valid inferences we have reached ¬Q), so if ¬P is true, then ¬Q is true, as the sentence claims.

Let us summarize. In the method of natural deduction, we can use conditional proofs as follows. We may always assume that an arbitrary sentence α is true, indicating that this is just an assumption by writing it on the right. Then we draw some conclusions using as premises both sentences dependent on the assumption (those on the right) and other sentence (those on the left). We can complete the proof at any time. If the sentence we have come to is β, in the next line and on the left we write the sentence α→β as the conclusion of the conditional proof. The truth of this sentence is certain (if the premises are true). From now on, we no longer have the right to use the sentences of the conditional proof (those on the right) – they serve only the conditional proof and are not part of the main natural deduction proof.

We can use both an indirect proof and a conditional proof in the same natural deduction proof. In addition, we may use a proof by assumption within another proof by assumption. Here is an example of a conditional proof within another conditional proof (we can do the same with indirect proofs):

1. (M∨N)→[(O∨P)→R] / M→(O→R)
2. M assumption
3. M∨N 2, Add
4. (O∨P)→R 3, 1, MP
5. O assumption
6. O∨P 5, Add
7. R 4, 6, MP
8. O→R 5–7, conditional proof
9. M→(O→R) 2–8, conditional proof

In cases like this, we are again guided by the rule that once a proof by assumption is completed, we are no longer entitle to use its sentences. Accordingly, while we are assuming under another assumption, i.e. while neither of the two proofs by assumption is yet completed (in the example, lines 5. to 7.), we can use all previous sentences as premises. Then, when the internal proof is completed but the external one is not jet finished, we can no longer use the sentences from the internal proof (the sentences most to the right). When also the external proof is completed, we can only use sentences that do not depend on the two assumptions (i.e. those most to left).

Using an indirect or a conditional proof, it can be shown that a sentence (formula) is a tautology. Generally, it is impossible for a tautology to be false. Therefore, since its truth does not depend on the truth of other sentences, it can be proven without any premises. In natural deduction this can only be done by an indirect or conditional proof. Here is an example of showing by reductio ad absurdum that the sentence [¬C∧(D∨C)]→D is a tautology. To this end, it is assumed that it is false (i.e., its negation is true), which leads to a contradiction. This shows that the sentence is necessarily true (a tautology).

1. ¬{[¬C∧(D∨C)]→D} assumption
2. [¬C∧(D∨C)]∧¬D 1, Imp
3. ¬C∧(D∨C) 2, S
4. ¬D 2, S (and Com)
5. D∨C 3, S (and Com)
6. C 5, 4, DS
7. ¬C 3, S – contradicts 6
8. [¬C∧(D∨C)]→D 1–7, reductio ad absurdum

In this way, also any contradiction can be shown to be such. Since a contradiction cannot be true, we assume that it is true and show that this assumption is inconsistent.

In general, the indirect proof and the conditional proof make the natural deduction proofs easier. They often make them shorter, but more importantly they make them easier to find because they allow for the application of simpler and more familiar inference schemes, such as simplification, modus ponens, modus tollens, disjunctive syllogism, etc., thus avoiding the need for artificial proof constructions.

Strictly speaking, only one of the two types of proofs by assumption introduced is needed as anything that can be proved by a conditional proof can also be proved by reductio ad absurdum, and vice versa. We introduced both of them for convenience. We are finishing the topic of natural deduction with an example of a meta-proof (a proof about proofs) showing that all that can be proved by a conditional proof can also be proved by reductio ad absurdum. Let an arbitrary sentence α→β is derived by a conditional proof:

α assumption
... inferences leading from α to β
β
α→β by conditional proof

Then the same sentence α→β can also be derived by indirect proof as follows:

¬(α→β) assumption
α∧¬β from the previous line by Imp
α from the previous line by S
... the same inferences leading from α to β
β
¬β from α∧¬β above by S (and Com) – contradicts the previous line
α→β by reductio ad absurdum

Exercises

(Download the exercises as a PDF file.)
(1) Use natural deduction to prove the following inferences:
1) 1. A→C
2. D∨(A∧B)
3. ¬D / C
2) 1. I→J
2. J∨(I∨K)
3. J→M
4. ¬M
5. K→¬N / ¬N
3) 1. A→C
2. C→(A↔B)
3. ¬B
4. ¬D→[D∨¬(A↔B)]
5. D→B / ¬A∧¬B
4) 1. A→B
2. (A∧B)→(¬¬C∧¬D)
3. ¬E→¬C
4. A
5. ¬¬E→F / F∨(¬A↔¬B)
5) 1. F→G
2. ¬(F∧G)∧L
3. (G∨H)→(I∧J)
4. F∨(K∨G)
5. ¬K∧L / I∨H
6) 1. (A∨B)∧C
2. A→D
3. B→E
4. E→F / D∨F
7) 1. Q→(V ∨R)
2. T→¬U
3. ¬V
4. T ∨Q
5. ¬U→V / R
8) 1. ¬S→(N∨O)
2. (N→U)∧(P→T)
3. (O→T)∧(P→N)
4. ¬U
5. S→U / T
9) 1. A→B
2. ¬B
3. [(¬A∧¬B)∨C]→(B∨D) / D∨¬E
10) 1. (Q∨R)→[(S∨L)→¬T]
2. (S∨U)→Q
3. S∧¬U
4. T∨K / K
(2) For each of step in the following natural deduction proofs, determine from which previous lines and by which inference or equivalence schemes are obtained:
1) 1. А∨¬B
2. ¬C→¬A / B→C
3. ¬B∨A
4. B→A
5. A→C
6. B→C
2) 1. P→¬P
2. (P∧Q)∨(R∧S) / R
3. ¬P∨¬P
4. ¬P
5. ¬P∨¬Q
6. ¬(P∧Q)
7. R∧S
8. R
3) 1. A→(B→C)
2. (¬C∨¬D)∨F
3. ¬E→(D∧¬F) / A→(B→E)
4. (A∧B)→C
5. ¬(C∧D)∨F
6. (C∧D)→F
7. C→(D→F)
8. (A∧B)→(D→F)
9. ¬(D∧¬F)→¬¬E
10. ¬(D∧¬F)→E
11. (¬D∨¬¬F)→E
12. (¬D∨F)→E
13. (D→F)→E
14. (A∧B)→E
15. A→(B→E)
4) 1. K→L
2. M→L
3. N→[K∨(K∨M)]
4. N / L
5. K∨(K∨M)
6. (K∨K)∨M
7. K∨M
8. (K→L)∧(M→L)
9. L∨L
10. L
5) 1. P→R
2. (T→¬S)→¬R / P→T
3. ¬¬R→¬(T→¬S)
4. R→¬(T→¬S)
5. ¬R∨¬(T→¬S)
6. ¬R∨¬(¬T∨¬S)
7. ¬R∨(¬¬T∧¬¬S)
8. ¬R∨(T∧¬¬S)
9. ¬R∨(T∧S)
10. (¬R∨T)∧(¬R∨S)
11. ¬R∨T
12. R→T
13. P→T
6) 1. [O→(P∧Q)]∧[R→(P∧S)]
2. [(T→¬O)∧U]→X
3. (U→X)→(T∧R) / Q∨S
4. (T→¬O)→(U→X)
5. (T→¬O)→(T∧R)
6. ¬(T→¬O)∨(T∧R)
7. ¬(¬T∨¬O)∨(T∧R)
8. (¬¬T∧¬¬O)∨(T∧R)
9. (T∧O)∨(T∧R)
10. T∧(O∨R)
11. (O∨R)∧T
12. O∨R
13. (P∧Q)∨(P∧S)
14. P∧(Q∨S)
15. (Q∨S)∧P
16. Q∨S
7) 1. P↔¬Q
2. (P→S)∧(S→P)
3. S→Q / Q
4. (P→¬Q)∧(¬Q→P)
5. P→¬Q
6. ¬¬Q→¬P
7. Q→¬P
8. S→¬P
9. P→S
10. P→¬P
11. ¬P∨¬P
12. ¬P
13. (¬Q→P)∧(P→¬Q)
14. ¬Q→P
15. ¬¬Q
16. Q
8) 1. А→(C∨¬B)
2. (B∧C)→(A∧D)
3. B / A↔C
4. А→(¬B∨C)
5. А→(B→C)
6. (А∧B)→C
7. (B∧A)→C
8. B→(A→C)
9. A→C
10. B→[C→(A∧D)]
11. C→(A∧D)
12. ¬C ∨(A∧D)
13. (¬C ∨A)∧(¬C ∨D)
14. ¬C ∨A
15. C→A
16. (A→C)∧(C→A)
17. A↔C
(3) Use natural deduction to prove the following inferences:
1) 1. W→M
2. ¬W→E / M∨E
2) 1. (R→S)∧(P→Q)
2. (S∧Q)→O
3. ¬O / ¬R∨¬P
3) 1. (A∨B)→(C∧D)
2. C→E
3. ¬E / ¬A
4) 1. K→L
2. K→M / (¬L∨¬M)→¬K
5) 1. (L∧M)→N
2. (L∧¬M)→¬N / L→(M↔N)
6) 1. S→L / S→(L∨W)
7) 1. A↔B
2. C→¬B / A→¬C
8) 1. E→(F∧G)
2. (F ∨H )→I / E→I
9) 1. (A∨B)→(C∧D) / ¬A∨C
10) 1. M∨(N∧O)
2. M→O / O
(4) Solve the examples from the previous exercise this time using reductio ad absurdum or conditional proof.
(5) Prove the following arguments by natural deduction using the letters given in parentheses to symbolize the simple statements in them. Try to prove them in two ways – first without using indirect or conditional proof and then using one of them.2
1) If I start a new job (J), I will have to buy a car (C), and if I go to the sea this summer (S), I will spend half of my savings (H). But if I buy a car and spend half of my savings, I will have to live on 10 euros a day (L). However, I cannot live on 10 euros a day. So either I won’t buy a car or I won’t go to the sea.
2) If our representative runs for president (P), if he runs a positive campaign (C), there will be a runoff (R). If there is a runoff and he wins the election (E), he will not be reelected in four years (Y). However, if he supports the death penalty (D), he will win the election and be reelected in four years. Therefore, if our representative runs for president, if he runs a positive campaign, he will not support the death penalty.
3) If the doctor injects the antibodies (I), the patient will have an allergic reaction (A), and if he has an allergic reaction, his kidney will stop functioning (K). But if the doctor does not inject the antibodies, the bacteria will spread to the bloodstream (B). The patient’s kidney will stop functioning if the bacteria spreads to the bloodstream. If the kidney stops functioning, the patient will not survive until the morning (S). Therefore, the patient will certainly not survive until the morning.
4) On New Year’s Eve (N), John drinks red wine (W). If he celebrates with friends (F), he drinks beer (B). Therefore, if John celebrates the New Year with friends, he drinks red wine and beer.
5) If Alice enrolls in Ancient Greek (G), she will also enroll in Latin (L). If she enrolls in Ancient Greek and Latin, she will enroll in logic (O). But if she enrolls in Ancient Greek, then if she enrolls in logic, she will enroll in mathematics (M). Therefore, if Alice enrolls in Ancient Greek, she will also enroll in mathematics.
6) If an economic crisis begins (E) or international conflicts arise (C), if the government fails to act (F) or takes inadequate action (I), there will be neither economic growth (G) nor political stability (S). If there is no economic growth or taxes are raised (T), there will be protests (P). Therefore, if an economic crisis begins, then if the government fails to act, there will be protests.
7) If Peter has met Mary (M), he would have told her the news (T) if he knew it (K). But Peter met Mary and did not tell her the news. So he didn’t know it.
8) If I start my own business (B), I will become rich (R), and if I start a scientific career (S), I will have free time (T). I will either start my own business or start a scientific career. However, if I start my own business, I will not have free time, whereas if I start a scientific career, I will not be rich. Therefore, I will have free time if and only if I am not rich.
9) If I go to the ball (B), I’ll have to buy а tailcoat (T). But if I buy a tailcoat, I will not be able to pay my rent (R) and repay my loan (L) at the same time. If I don’t pay the rent, I'll have to hide from the landlord (H), and I can’t do that. Besides, I'll have to repay the loan. So, I can’t go to the ball.
10) If taxes increase (T), unemployment will increase (U), and if investments decrease (I), growth (G) will decrease. If unemployment increases or investments decrease, consumption will fall (C). Consumption has not decreased. Therefore, neither taxes have been increased nor investments have been reduced.
11) If John is drinking with friends (F), tomorrow he will have a hangover (H). If his favorite team has lost (L) again, tomorrow he will be irritable (I). Therefore, if John is drinking with friends or his favorite team has lost, tomorrow he will have hangover or be irritable.
12) If Jupiter has been under the influence of Mars (M) at the beginning of the year, there will be war (W) or civil unrest (U) during the year. If Jupiter has been under the influence of Saturn (S) at the beginning of the year, either the year will be hungry (H) or there will be war. However, there will certainly be no war. Therefore, if the year will be neither hungry nor there will be civil unrest, Jupiter has been under the influence neither of Mars nor Saturn.
(6) Use natural deduction to answer the following questions:
1) Imagine that you are a detective and have the following information. There are four suspects – call them “P”, “Q”, “R” and “S”. If P is innocent, then S is also innocent, but R’s guilt will be certain. If S is innocent, then Q is among the perpetrators of the crime. If S is guilty, then so is R. R, however, has a reliable alibi. Who are guilty and who are innocent?
2) As in the previous exercise but this time the information is as follows. P is guilty if and only if Q is innocent. R is innocent if and only if S is guilty. If S is among the perpetrators, then P is also among them, and vice versa. If S is guilty, then so is Q.
3) In a restaurant, a customer tells the waiter the following: “I eat potatoes or rice, but not both at the same time. If I eat potatoes, then I don’t eat bread. If I eat bread or don’t eat potatoes, then I don’t eat rice”. What should the waiter serve?
1. The variant of natural deduction we are about to use is almost exactly like the one in (Copi, 1998). ↩ 2. Most of the examples are from exercise (2) in 1.7 Quick test of logical inference. There, the validity of the arguments had to be proven by a quick test. You can compare the two methods. ↩