Chapter – 5

Propositional Logic – Natural Theory of Deduction

Contents of this Chapter:

1. Natural Deductions in Propositional Logic
2. Rules of Inference and its application
3. Gentzen System (Truth -tree method)

Introduction

The nineteen rules of inference that have been set forth (nine elementary
argument forms and ten logical equivalences) are all the rules that are needed in
truth-functional logic. Together they constitute a system of natural deduction that
is compact and readily mastered, but nonetheless complete. This means that,
using this set of rules, one can construct a formal proof of validity for any valid
truth-functional argument.

1. Natural Deduction in Propositional Logic

The truth table method as a decision procedure to test the validity of a given
argument turns out to be very tedious or inconvenient when an argument
involves many different simple statements.For instance consider the following
argument:
– If Anderson was nominated, then she went to Boston.
– If she went to Boston, then she campaigned there.
– If she campaigned there, she met Douglas.
– Anderson did not meet Douglas.
– Either Anderson was nominated or someone more eligible was
selected.
– Therefore someone more eligible was selected.

The validity of this argument may be intuitively obvious, but let us consider the
matter of proof. The discussion will be facilitated by translating the argument into
symbolism as

A⸧B

B⸧C
 C⸧D

⁓D

A˅E

⸫E

To establish the validity of this argument by means of a truth table requires a table
with thirty-two rows, because five different simple statements are involved.
Instead, we can prove the argument valid by deducing its conclusion using a
sequence of just four elementary valid arguments.

1. A⸧B
2. B⸧C
3. C⸧D
4. ⁓D
5. A˅E
6. ⸫E

• From the first two premises we validly infer that using a Hypothetical
Syllogism.
• From and the third premise we validly infer that as another Hypothetical
Syllogism.
• From and the fourth premise, we validly infer that by Modus Tollens.
• From and the fifth premise, as a Disjunctive Syllogism we validly infer E,
the conclusion of the original argument.
• That the conclusion can be deduced from the five premises of the original
argument by four elementary valid arguments proves the original argument
to be valid.
• Here the elementary valid argument forms Hypothetical Syllogism (H.S.),
Modus Tollens (M.T.), and Disjunctive Syllogism (D.S.) are used as rules
of inference whose application allows conclusions to be validly inferred or
deduced from premises.

This method of deriving the conclusion of a deductive argument—using rules of

inference successively to prove the validity of the argument—is as reliable as the
truth-table method, if the rules are used with meticulous care. However, it
improves on the truth-table method in two ways: It is vastly more efficient, as has
just been shown; and it enables us to follow the flow of the reasoning process
from the premises to the conclusion and is therefore much more intuitive and
more illuminating. The method is often called natural deduction. Using natural
deduction, we can provide a formal proof of the validity of any argument that is
valid. A formal proof of validity is given by writing the premises and the
statements that we deduce from them in a single column, and setting off in another
column, to the right of each such statement, its “justification,” or the reason we
give for including it in the proof. It is convenient to list all the premises first and
to write the conclusion either on a separate line, or slightly to one side and
separated by a diagonal line from the premises.

If all the statements in the column are numbered, the “justification” for each
statement consists of the numbers of the preceding statements from which it is
inferred, together with the abbreviation for the rule of inference by which it
follows from them. The formal proof of the example argument is written as

Explanation of Example;

Question
• A⸧B
• B⸧C
• C⸧D
• ⁓D
• A˅E
• ⸫E

Step-1

1. A⸧B
2. B⸧C
3. C⸧D
4. ⁓D
5. A˅E
⸫E
Step-2
1. A ⸧ B
2. B ⸧ C
3. C ⸧ D
4. ⁓D
5. A ˅ E
⸫E
6. A ⸧ C 1,2 H.S

Explanation of Step-2

• Consider first two statements.

1. A⸧B
2. B⸧C
• From these two premises, ‘B’ is common term.
• If we remove ‘B’, we got A⸧C.
• So, solve these two statements using with Hypothetical Syllogism.
• According to the rule of Hypothetical syllogism,
p⸧q
q⸧r
⸫p⸧r
• Instead of p,q, and r, we can substitute A,B and C.
1. A ⸧ B
2. B ⸧ C
⸫A ⸧ C
Step - 3
1. A ⸧ B
2. B ⸧ C
3. C ⸧ D
4. ⁓D
5. A ˅ E
⸫E
6. A ⸧ C 1,2 H.S
7. A ⸧ D 6,3 H.S
Explanation of Step-3

• Same as Second Step.

th rd
• Consider 6 and 3 Statements.
• C⸧D
• A⸧C
• Here C is common, if we avoid ‘C’, then we got A ⸧ D.
• So, solve these two statements using with Hypothetical Syllogism.
3. C ⸧ D
6. A ⸧ C
⸫ A ⸧ D.

Step-4
1. A ⸧ B
2. B ⸧ C
3. C ⸧ D
4. ⁓D
5. A ˅ E
⸫E
6. A ⸧ C 1,2 H.S
7. A ⸧ D 6,3 H.S
8. ⁓A 7,4 M.T

Explanation of Step -4
th th
• Let’s consider 4 and 7 statements.
• If we write down they are in order,
A⸧D
⁓D
• From this we got a general form of Modus Tollens;
p⸧q
⁓q
⸫⁓p
• As per the rule, we got
7. A ⸧ D
4. ⁓D
⸫ ⁓A
Step -5
1. A ⸧ B
2. B ⸧ C
3. C ⸧ D
4. ⁓D
5. A ˅ E
⸫E
6. A ⸧ C 1,2 H.S
7. A ⸧ D 6,3 H.S
8. ⁓A 7,4 M.T
9. E 5,8 D.S

Explanation of Step-5
th th
• Let’s consider 5 and 8 statements.
• If we write down they are in order,
• A˅E
• ⁓A
• From this we got a general form of Disjunctive Syllogism;
p˅q
⁓q
⸫⁓p
As per the rule,
5. A ˅ E
8. ⁓A
⸫E
Step-6 (Conclusion)
1. A ⸧ B
2. B ⸧ C
3. C ⸧ D
4. ⁓D
5. A ˅ E
⸫E
6. A ⸧ C 1,2 H.S
7. A ⸧ D 6,3 H.S
8. ⁓A 7,4 M.T
9. E 5,8 D.S
Hence this argument is valid.
 We define a formal proof of validity of a given argument as a sequence of
statements, each of which either is a premise of that argument or follows from
preceding statements of the sequence by an elementary valid argument or by
a logical equivalence, such that the last each of which either is a premise of
that argument or follows from preceding statements of the sequence by an
elementary valid argument or by a logical equivalence, such that the last
statement in the sequence is the conclusion of the argument whose validity is
being proved.

2. Rules of Inference and Its Applications – In Symbolic Logic

Name Proof
Modus Ponnens p⸧q
p
⸫q
Modus Tollens p⸧q
⁓q
⸫⁓p
Hypothetical Syllogism p⸧q
q⸧r
⸫p⸧r
Disjunctive Syllogism p˅q
⁓p
⸫q
Constructive Dilemma (p⸧q).(r⸧s)
p.r
⸫q˅s
Destructive Dilemma (p⸧q) . (r⸧s)
⁓q ˅ ⁓s
⸫⁓p˅⁓r
Simplification p.q
⸫p
Conjunction P
q
⸫ p.q
Addition P
⸫p˅q
2.1 Modus Ponnens

• This syllogism is also known as Constructive Hypothetical Syllogism.

• It is one in which the minor premise affirms the antecedent and the
conclusion affirms the consequent of the major premise.
• The form is –
If A is B then C is D
A is B
⸫C is D.
• Example,
If Mohan works hard then he will pass the examination.
Mohan works hard.
⸫He will pass the examination.
• Here, we can symbolically represent the above argument like this:
• If Mohan works hard = P
• then he will pass the examination.= Q
• That means,
If P, the Q
P
⸫Q
• In Symbolically, If …then represented by using ‘⸧’
• So the argument in symbolically,
p⸧q
p
⸫q

2.2 Modus Tollens

• This syllogism is also known as Destructive Hypothetical Syllogism.

• It is one in which the minor premise denies the consequent of the major
premise.
• On this basis the conclusion denies the antecedent of the major premise.
If A is B, then C is D.
C is not D.
⸫A is not B.
• Example,
 If a woman loses her husband, then she becomes a widow.
This woman is not a widow.
⸫This woman has not lost her husband
• Here, we can symbolically represent the above argument like this:
• If a woman loses her husband : P
• then she becomes a widow : Q
• This woman is not a widow: ⁓Q.
• That means,
If P, the Q
⁓Q
⸫ ⁓P
• In Symbolically, If …then represented by using ‘⸧’
• So the argument in symbolically,
p⸧q
⁓q
⸫⁓p

2.3 Addition

Example,
He studies very hard
⸫Either he studies very hard or he is a very bad student
• Here we consider the first premise (P) is true.
• Second one is the additional premise (q) which add to P.
• He studies very hard : P
• he is a very bad student : q
• Either or represented by ‘˅’.
• Symbolically,
P
⸫P ˅q

2.4 Conjunction

• If P and q are two premises, we can use conjunction rule to derive p.q.
• Example,
• Let P – “ He studies very hard”.
• Let q – “ He is the best boy in the class”.
• Therefore – “He studies very hard and he is the best boy in the class”.
 • Using symbol for and : .
• Symbolically,
P
q
⸫P.q

2.5 Simplification

• If p.q is a premise, we can use simplification rule to derive p.

• Example,
• “He studies very hard and he is the best boy in the class”, p . q
• Therefore - “ He studies very hard”(p).
• Symbolically,
p.q
⸫p

2.6 Hypothetical Syllogism

• Example,
If the rainfall is adequate, then the harvest will be good.
The rainfall is adequate.
⸫The harvest will be good.
If A is B, then C is D
A is B
⸫C is D
• Here, ‘the rainfall is adequate’ is the antecedent and ‘then harvest will be
good’ is the consequent.
• If p ⸧q and q ⸧ r are two premises, we can use Hypothetical syllogism
to derive p⸧ r.
• Example,
• If it rains, I shall not go to school : p ⸧ q
• If I don’t go to school, I won’t need to homework : q ⸧ r.
• Therefore-If it rains , I won’t need to do homework : p ⸧ r.
• Symbolically,
p⸧q
q⸧r
⸫ p ⸧r
2.7 Disjunctive Syllogism

• If ⁓p and p∨q are two premises, we can use Disjunctive Syllogism to

derive q.
• Example
• "The ice cream is not vanilla flavoured“ : ⁓p
• "The ice cream is either vanilla flavoured or chocolate flavoured“: p∨q
• Therefore − "The ice cream is chocolate flavoured”
• Symbolically,
⁓p
p∨q
∴q

2.8 Constructive Dilemma

• If (P⸧Q)∧(R⸧S) and P∨R are two premises, we can use constructive

dilemma to derive Q∨S.
• Example
• “If it rains, I will take a leave”: (P⸧Q)
• “If it is hot outside, I will go for a shower”: (R⸧S)
• “Either it will rain or it is hot outside”: P∨R
• Therefore − "I will take a leave or I will go for a shower“.
• Symbolically,
(P⸧Q).(R⸧S)
P∨R
∴Q∨S

2.9 Destructive Dilemma

• If (P⸧Q)∧(R⸧S) and ⁓Q∨⁓S are two premises, we can use destructive

dilemma to derive ⁓P∨⁓R.
• Example
• “If it rains, I will take a leave”: (P⸧Q)
• “If it is hot outside, I will go for a shower”:(R⸧S)
• “Either I will not take a leave or I will not go for a shower”: ⁓Q∨⁓S.
• Therefore − "Either it does not rain or it is not hot outside“
• Symbolically,
(P⸧Q).(R⸧S)
⁓Q∨⁓S
 ∴⁓P∨⁓R

2.10 Absorption

p⸧q
⸫ p⸧ (p.q)
• Example;
• If I will study discrete math, then I will study Computer Science ; p⸧q
• As per the absorption rule; the conclusion is:
• If I will study discrete math , then I will study discrete mathematics
and I will study computer science ; p⸧ (p.q)

Some Other Examples ;

1. Find out the Formal Proof of Validity of Following Arguments;

I. (B ˅ N)⸧(K . L)
⁓K
⁓M / ⸫⁓B . ⁓M

II. (T ⸧ K). (R ⸧ S)
S⸧D
D ⸧T
R / ⸫T

III. A ˅ ( B . C)
A⸧P
⁓P / ⸫C

IV. A . (B ˅ C)
A⸧P
Q/⸫P.Q
 Answers;
I.
1. (B ˅ N)⸧(K . L)
2. ⁓K
3. ⁓M / ⸫⁓B . ⁓M
4. ⁓K ˅ ⁓L (2, Add)
5. ⁓(B˅N) (1,4 M.T)
6. (⁓B . ⁓N) (5, De.M)
7. ⁓B (6, simp)
8. ⸫ ⁓B . ⁓M (6,3 conj)

II.
1. (T ⸧ K). (R ⸧ S)
2. S⸧D
3. D ⸧T
4. R / ⸫T
5. R ⸧S (1, Simp.)
6. S ( 5,4 M.P)
7. D (2,6 M.P)
8. ⸫T (3,7 M.P)

III.
1. A ˅ ( B . C)
2. A⸧P
3. ⁓P / ⸫C
4. ⁓A (2, 3 M.T)
5. B. C ( 1, 4 D.S)
6. ⸫C ( 5, Simp.)

IV.
1. A . (B ˅ C)
2. A⸧P
3. Q/⸫P.Q
4. A (1, Simp.)
5. P (2, 4 M.P)
6. ⸫P.Q (5,3 Conj.)
 3. Truth Tree Method
Like the indirect truth table method, the truth tree method is essentially Reductio ad
absurdum. Here we take the premises along with the negation of the conclusion and attempt
to show that this leads to a conclusion. If the contradiction can be found, then the argument is
valid, and if the contradiction cannot be found then the argument is invalid. The method uses
a diagram approach which looks like an upside-down tree in which the trunk which is at the
top consists of the premises and the negation of the conclusion each stated in a separate line.
Then, below this trunk we branch out and decompose the premises and the negation of the
conclusion each stated in a separate line. In each branch, we use search for a contradiction of
two propositions such as p and ˜p. if a contradiction is found, then we close that branch by
putting an ‘x’ at the end of the branch. If no contradiction is found, then the branch remains
open and no ‘x’ is placed at the bottom of the branch. We look at the completed tree and if all
the branches are closed then the argument is valid, but if any branch is open then the argument
is invalid. Since in the tree method, we need to decompose molecular propositions into their
components, we need some “Rules of Decomposition.”
There are two kind of branching methods commonly used in truth tree method. They
are follows;
1. Stacking Rules: These rules are those in which the decomposed components of the
molecular proposition are lined up vertically downwards in sequence either on the trunk
itself or on the branches, such as in;

p.q
p
q

2. Branching Rules: Branching rules are those in which the decomposed components of
the molecular proposition are branched out in two different directions represented by
downward diagonal bars and are placed under each bar, such as in;

pvq

p q
3.1 Decomposition Rules
There are nine decomposition rules in truth tree method. They are as follows;
1. Double Negation Rule: Truth functionally ‘˜p’ is true whenever ‘p’ is false. So, ‘˜˜p’
will be true whenever ‘˜p’ is false, i.e., whenever ‘p’ is true. Hence, we can reduce ˜˜p
to ‘p’.
Proof: ˜˜p
p
2. Conjunction Rule: In truth functional definition of a conjunction is: a conjunction is
true when both conjuncts are true. So it likes;

Proof: p.q
p
q

3. Negation of Conjunction Rule: A conjunction ‘p . q’, is true whenever both ‘p’ and ‘
q’ are true. So, the negation of a conjunction is true whenever either conjunct (p or q)
is false.

Proof: ͠ (p . q)

͠p ͠q

4. Disjunction Rule: A disjunction is true whenever either of the disjuncts is true.

Proof: pvq

p q

5. Negation of Disjunctive Rule: A disjunction ‘p v q’ is true whenever either ‘p’ is

true or ‘q’ is true. Hence the negation of disjunction ‘˜(p v q)’ will be true whenever
both ‘p’ and ‘q’ are false as it says neither p nor q.
Proof:
͠ ( p v q)
͠p
͠q
6. Conditional Rule: A conditional rule is true whenever either the antecedent is false
or the consequent is true.

Proof: pͻq

͠p q

7. Negation of Conditional Rule: A conditional is false only when the antecedent is

true and the consequent is false. Hence, the negation of a conditional will be true
when the antecedent is true and the consequent is false:
Proof:
͠ (p ͻ q)
p
͠ q
8. Bi-conditional Rule: A biconditional ‘p ≡ q’ is true whenever either both ‘p’ and ‘q’
are true or both ‘p’ and ‘q’ are false.
Proof:
p≡q

p ͠p
q ͠q
9. Negation of Bi-conditional Rule: Biconditional ‘p ≡ q’ is true whenever either both
‘p’ and ‘q’ are true or both ‘p’ and ‘q’ are false, ͠ (p ≡ q) will be true when either ‘p’
is true and ‘q’ is false or when ‘p’ is false and ‘q’ is true. This rule can be represented
as;
Proof:
͠ (p ≡ q)

p ͠p
͠q q
Example:
Question: find out the validity or invalidity below argument using with tree method.
If it is raining, then the roads are wet.
If the roads are wet, then the roads are slippery.
It is raining.
Therefore, the roads are slippery.

Answer: Symbolization of the above argument is;

RͻW
WͻS
R
⸫S
If we substitute the above arguments into symbols,

pͻq
qͻr
p
⸫r
First put the premises in order, one in each row,

pͻq
qͻr
p
We place the negation of the conclusion as pet the rule;

pͻq
qͻr
p
⸫͠ r
Now use the branching method applying the rules of decomposition. In this argument, lines 1
and 2 are molecular propositions on which we need to branch out.
 1. pͻq (first premise)
2. qͻr ( Second Premise)
3. p (Third Premise)
4. ⸫͠ r (Conclusion)

5. ͠ p q ( from 1 by conditional rule).

X
(5, 3)

͠q r ( from 2 by conditional rule).

X X
( 6, 5) ( 6, 4)