Mathematical Foundation of Computer Science

DHARM

114 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

5.5 Tautology.........................................................................................................................

A formula which is true (T) under all possible interpretation is called a tautology. Conversely,

a formula which is false (F) under all possible interpretation is called a contradiction. Hence,

negation of contradiction is a tautology.

As we know entries in the last column of the truth table shows the truth value to the

formula. If this column has all entries true (T) then the formula is a tautology. Consequently,

the truth value of the tautology is true (T) always.

For example, the formula (A ∨ ~ A) is a tautology. Because truth value entries in the

truth table at last column are all T. (Fig. 5.17)

A ~ A(A ∨ ~ A)

FT T

TF T

Fig. 5.17
Example 5.9. Show the formula ((P → Q) ∧ (~ P ∨ Q)) ∨ (~ ( P → Q) ∧ ( ~ P ∨ Q)) is a tautology.
Truth values of the formula are shown in truth table (Fig. 5.16). From the truth table we
observe that truth values shown at column 10 are all T. Therefore, formula is a tautology.

5.6 Theory of Inference.........................................................................................................

The objective of the study of logic is to determine the criterion so that validity of an argument

is determined. The criterion is nothing but the computational procedure based on rules of

inference and the theory associated such rules is known as inference theory. It is concerned

with the inferring a conclusion from set of given premises. The computation process of conclu-

sion from a set of premises by using rules of inference is called formal proof or deduction.

Assume that there are k statements S 1 , S 2 , S 3 ,.........Sk. These statements are facts/

premises/ hypothesis. Let these statements draw a conclusion C.

That is,

(i)S 1

(ii)S 2

(iii)S 3

.....................

(k)Sk

∴∴∴∴∴ C

For example, premises (i)S 1 : If it rains I will not go to Institute.

and (ii)S 2 : It is raining.

Conclusion, Therefore, I will not go to Institute. : C