Mathematical Foundation of Computer Science

DHARM

116 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

In the next sections we will discuss several methods to test the validity of an argument.

A simple and straight forward method is truth table method discussed in section 5.6.1. That

method is based on construction of truth table. Truth table method is efficient when numbers

of propositional variables are less. This method is tedious if number of variables are more.

Natural deduction method is general and an efficient approach to prove the validity of the

argument that will illustrated in section 5.6.2.

5.6.1 Validity by Truth Table......................................................................................

Assuming a set S of premises (S 1 , S 2 , S 3 ,.........Sk) derives the conclusion C then we say that
conclusion C logically follows from S if and only if,
S → C
Or, ((.........((S 1 ∧ S 2 ) ∧ S 3 )..........∧ Sk) → C)
So we have the only conclusion i.e.,
((.........((S 1 ∧ S 2 ) ∧ S 3 )..........∧ Sk) → C)
Thus, we obtain a formula ((.........((S 1 ∧ S 2 ) ∧ S 3 )..........∧ Sk) → C) let it be X. Now test
the tautology for X. If X is a tautology then argument is valid; Otherwise argument is invalid.
By use of truth table we test the tautology of the formula.
For example, given set of premises and conclusion,
(i)R → C
(ii)R
∴ C
we obtain the formula,
(( R → C) ∧ R) → C) : (say) X
Construct the truth table for X (Fig. 5.19).

RCR → C(R → C) ∧ R ((R → C) ∧ R) → C : X

FF T T T

FT T F T

TF F F T

TT T F T

Fig. 5.19 (Truth table for X)

Since, truth values of the formula X are all T therefore, X is a tautology. Hence argu-

ment is valid.

Example 5.10. Show that argument is invalid.

(i)R → C

(ii)C

∴ R

Sol. From the given premises & conclusion, we obtain the formula,

((R → C) ∧ C) → R) : (say) X