﻿ 1.8 Natural deduction

### 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 IH (written after the last premise, separated by a slash). 6. is derived from 2. by simplification, with α in the inference scheme being ¬(FG) and β being L. 8. is obtained from 6. and 7. by modus tollens, with F corresponding to α and FG to β. 9. is derived from 4. and 8. by disjunctive syllogism (α is F and β is KG). 10. is derived from 5. by simplification (α is ¬K and β is L). 13. is obtained from 3. and 12. by modus ponens (α is GH and β is IJ).

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.

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 “AB” 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, 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 Athe 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 AC, the plan is first to prove the conditionals AC and CA, 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 AC, and through a series of inferences we get to a contradiction, which allows us to derive AC 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 (AC) as well as the sentences before 4. but not the sentences from 4. to 9. In 11. we assume the negation of CA and through a series of inferences we come to a contradiction, which enables us to establish the truth of CA, 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 AC and CA (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∧(DC)]→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

 (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