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:
Here is the complete list of inference schemes we will use in the natural deduction proof
procedure:
|
α → β
|
|
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
we can deduce from it
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:
|
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)
|
8)
|
1.
|
E→(F∧G)
|
|
2.
|
(F ∨H )→I /
E→I
|
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.
|
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?
|