logic chapter 1

1 Decision Procedure

DO YOU KNOW THAT ..............
l One can determine whether the statement form is tautology or not in a single row.
l One can determine the validity of many complicated arguments by merely constructing a
shorter truth table.
l As in geometry, so in logic, one can decide that a statement form is a tautology by showing
the impossibility of its opposite.

1.1 Decision procedure the method becomes complicated and difficult to
manage and the truth table becomes very long,
I.M. Copi defines logic as “The study of tedious and time consuming. We may make
the methods and principles used to distinguish errors while constructing it so lot of carefulness
good (correct) from bad (incorrect) reasoning.” is required. Hence we need shorter and accurate
The two main functions in logic are - (i) To decide method for determining whether a statement
whether an argument is valid or invalid; and (ii) form is tautology or not. Hence shorter truth
To decide whether a given statement form (truth table method is introduced.
functional form) is a tautology, contradiction
or contingency. A procedure (or method) for The shorter Truth Table procedure can
deciding these, is called a decision procedure. be carried out in a single line. In fact this is
The main requirement of a decision procedure the main advantage of the shorter truth table
is that it must be effective. To be an effective as a decision procedure. Shorter truth table
decision procedure, it must satisfy 3 conditions method is a quick and easy method. As it helps
– reliable, mechanical and finite. us to decide whether an argument is valid and
whether a given statement form is tautology.
1.2 Need for shorter truth table method
1.3 Nature of shorter truth table method
We have already studied Truth Table
as an effective decision procedure. Though, Shorter truth table is a decision
truth table is a simple and easy method for procedure –
deciding whether a statement form is tautology
Shorter truth table method is an effective
or not and an argument is valid or invalid, but
decision procedure as is satisfies all the
it has certain limitations. Truth table becomes
conditions of an effective decision procedure.
inconvenient when a statement form involves
i.e. reliable, mechanical and finite.
many variables i.e. with four variables the truth
table will have sixteen rows, five variables The shorter truth table method is based
thirty two rows and so on. With the increase in on the principle of reductio-ad-absurdum.
number of propositional variables in a given The principle of Reductio-ad-absurdum means
expression, the number of rows in the truth table to show that the opposite of what is to be
also increases. At such times the application of proved leads to an absurdity. In the case of

Complete the following

p • q p q pq pq p p
T T FF TF FT T F


1

, argument we begin by assuming it to be invalid truth tables, one can assign truth values to
and if the assumption leads to an inconsistency the various components of the statement
then the argument is proved as valid otherwise it form.
is invalid.
(4) Truth values are to be assigned to all
In the case of statement form we first the connectives and the variables of the
assume it to be not a tautology and if the statement form and every step is to be
assumption leads to an inconsistency then the numbered.
statement form is proved to be tautology or else
it is not a tautology. (5) After assigning the truth value one has to
check whether there is any inconsistency.
Since this method does not directly prove Inconsistencies are of two types –
whether the argument is valid/invalid or whether (i) Violation of rules of basic truth table
the statement form is a tautology or not, it is (ii) If a propositional variable gets both
called the “Indirect method”. truth values i.e. True as well as False.
1.4 Shorter Truth Table Method as a test (6) An inconsistency will prove that the given
of Tautology – statement form is a tautology. If there is
no inconsistency, it will prove that the
The shorter truth table method is based statement form is not a tautology.
on the basic truth tables of truth functional
compound propositions. (7) We mark the inconsistency with a cross
“x” below it.
Shorter truth table method is used to
decide whether a statement form is tautology (8) Write whether the given statement form is
or not. Tautology is a truth functional statement a tautology or not a tautology.
form which is true under all truth possibilities
of its components. While constructing shorter Following example demonstrates the procedure.
truth table, we assume that the statement form Example 1 ( p · p )  p
is not a tautology by placing the truth value
‘F’ under the main connective of the statement (1) One has to assume that the given statement
form. If we arrive at an inconsistency, then form is ‘not a tautology’ by writing ‘F’
the assumption is wrong and given statement under the main connective ‘’. We mark
form is a tautology (tautologous). If we do not the assumption ‘F’ with a star as shown
arrive at any inconsistency, then the assumption below.
is correct and hence the given statement form (p·p) p
is not a tautology. It is either contradictory or
F
contingency.
*
This procedure involves the following
steps – (2) The next step is to assign values by using
basic truth tables. Since in the example,
(1) For determining whether a statement implication is assumed to be false, the
form is a tautology, one has to begin by antecedent has to be true and consequent
assuming that it is not a tautology. has to be false. So we assign values as
(2) For assuming statement form is not a follows and number the steps.
tautology, one has to place ‘F’ under the (p·p)  p
main connective of the statement form.
T F F
(3) After assigning ‘False’ truth value under
the main connective, with the help of basic (1) * (1)

2