Mathematical Foundation of Computer Science

DHARM

126 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

We obtain a contradiction therefore, our assumption is wrong at stage 4. Hence conclu-
sion must be true.
It will be seen that method of indirect proof may cut short the steps of deduction. There-
fore, we conveniently proved the conclusion is valid. Deduction through method of contradic-
tion also shows the inconsistency of premises. Alternatively, a set of given premises P 1 , P 2 ,
............Pn is inconsistence if formal proof obtain a contradiction (at any stage) i.e.,

1. P 1


2. P 2
   ...............
   ..............
   ..............
   n.Pn
   n + 1. (P 1 ∧ P 2 ∧ ............∧ Pn)
   .......................
   ........................
   m. R ∧ ~ R
   We obtain a contradiction R ∧ ~ R (where R is any formula), that is necessary and
   sufficient to imply that (P 1 ∧ P 2 ∧ ............∧ Pn) be a contradiction.

Example 5.23. Prove that following statements are inconsistent.
1.If Nelson drives fast then he reaches the Institute in time.
2.If Nelson drives fast then he is not lazy.
3.If Nelson reaches the Institute then he is lazy.
4.Nelson drives fast.
Sol. Write the statement in symbolic logic,
Assume, D : Nelson drives fast
I : Nelson reaches the Institute in time
L : Nelson is very lazy
So the premises are,

1. D → I


2. D → L


3. I → ~ L


4. D


5. L 2 & 4 MP


6. I 1 & 4 MP


7. ~ L 3 & 6 MP


8. L ∧ ~ L 5 & 7 Conj
   Since, we obtain a contradiction hence premises are inconsistent. Therefore statements
   are inconsistent.

Example 5.24. Prove following statements are inconsistent.
1.Stephen loves Joyce since graduation and Matrye is not happy but their parents are
happy.
2.If Stephen marries with Joyce, his collegiate Shalezi and Matrye will be happy.
3.Stephen marries with Joyce if Joyce loves Stephen.