Maharashtra Board Class 12 Logic Chapter 1 Decision Procedure PDF Download

Decision Procedure

Do you know that one can determine whether the statement form is tautology or not in a single row. One can determine the validity of many complicated arguments by merely constructing a shorter truth table. 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

I.M. Copi defines logic as "The study of the methods and principles used to distinguish good (correct) from bad (incorrect) reasoning."

The two main functions in logic are (i) To decide whether an argument is valid or invalid and (ii) To decide whether a given statement form (truth functional form) is a tautology, contradiction or contingency.

A procedure (or method) for deciding these, is called a decision procedure.

The main requirement of a decision procedure is that it must be effective. To be an effective decision procedure, it must satisfy 3 conditions - reliable, mechanical and finite.

Teacher's Note

A decision procedure is like a clear rule to check if something is right or wrong. Just like we have rules to check if an answer in math is correct.

Exam Trick

Remember: Decision procedure = a fixed method. Like the steps to make tea - always the same, every time.

Points to Remember

Logic helps us know good reasoning from bad reasoning.
A decision procedure must be reliable, mechanical and finite.
There are two main uses of decision procedure in logic.

1.2 Need For Shorter Truth Table Method

We have already studied Truth Table as an effective decision procedure. Though, truth table is a simple and easy method for deciding whether a statement form is tautology or not and an argument is valid or invalid, but it has certain limitations.

Truth table becomes inconvenient when a statement form involves many variables. With four variables the truth table will have sixteen rows. With five variables there are thirty two rows and so on.

With the increase in number of propositional variables in a given expression, the number of rows in the truth table also increases. At such times the application of the method becomes complicated and difficult to manage. The truth table becomes very long, tedious and time consuming.

We may make errors while constructing it so lot of carefulness is required. Hence we need shorter and accurate method for determining whether a statement form is tautology or not. Hence shorter truth table method is introduced.

The shorter Truth Table procedure can be carried out in a single line. In fact this is the main advantage of the shorter truth table as a decision procedure. Shorter truth table method is a quick and easy method. As it helps us to decide whether an argument is valid and whether a given statement form is tautology.

Teacher's Note

When we have many statements to check, a full truth table takes too long. Like when your teacher has to check 40 students' papers, she cannot write everything out long - she uses a quicker method.

Exam Trick

Remember: More variables = longer truth table = more time. Shorter method = saves time. This is the main advantage.

Points to Remember

Truth table becomes long with many variables.
Full truth table can take very long time.
Shorter truth table method is faster and easier.
Both methods give the same answer.

1.3 Nature Of Shorter Truth Table Method

Shorter truth table is a decision procedure.

Shorter truth table method is an effective decision procedure as it satisfies all the conditions of an effective decision procedure. That is, reliable, mechanical and finite.

The shorter truth table method is based on the principle of reductio-ad-absurdum.

The principle of Reductio-ad-absurdum means to show that the opposite of what is to be proved leads to an absurdity.

In the case of argument we begin by assuming it to be invalid. If the assumption leads to an inconsistency then the argument is proved as valid. Otherwise it is invalid.

In the case of statement form we first assume it to be not a tautology. If the assumption leads to an inconsistency then the statement form is proved to be tautology. Otherwise it is not a tautology.

Since this method does not directly prove whether the argument is valid or invalid or whether the statement form is a tautology or not, it is called the "Indirect method".

Teacher's Note

Reductio-ad-absurdum means we assume something is wrong and then check if this causes problems. If it does, then our first idea was right. Like when you check if a door is locked by trying it.

Exam Trick

Remember: Reductio-ad-absurdum = assume opposite = check for contradiction. If contradiction comes, then original statement is true.

Points to Remember

Shorter truth table is an indirect method.
It is based on reductio-ad-absurdum principle.
We assume the opposite and look for problems.
If problems come, the opposite is wrong.

1.4 Shorter Truth Table Method As A Test Of Tautology

The shorter truth table method is based on the basic truth tables of truth functional compound propositions.

Shorter truth table method is used to decide whether a statement form is tautology or not. Tautology is a truth functional statement form which is true under all truth possibilities of its components.

While constructing shorter truth table, we assume that the statement form is not a tautology by placing the truth value 'F' under the main connective of the statement form.

If we arrive at an inconsistency, then the assumption is wrong and given statement form is a tautology (tautologous). If we do not arrive at any inconsistency, then the assumption is correct and hence the given statement form is not a tautology. It is either contradictory or contingency.

This procedure involves the following steps.

1. For determining whether a statement form is a tautology, one has to begin by assuming that it is not a tautology.

2. For assuming statement form is not a tautology, one has to place 'F' under the main connective of the statement form.

3. After assigning 'False' truth value under the main connective, with the help of basic truth tables, one can assign truth values to the various components of the statement form.

4. Truth values are to be assigned to all the connectives and the variables of the statement form and every step is to be numbered.

5. After assigning the truth value one has to check whether there is any inconsistency. Inconsistencies are of two types (i) Violation of rules of basic truth table (ii) If a propositional variable gets both truth values that is True as well as False.

6. An inconsistency will prove that the given statement form is a tautology. If there is no inconsistency, it will prove that the statement form is not a tautology.

7. We mark the inconsistency with a cross "x" below it.

8. Write whether the given statement form is a tautology or not a tautology.

Following example demonstrates the procedure.

Example 1 (p • p) ⊃ p

1. One has to assume that the given statement form is 'not a tautology' by writing 'F' under the main connective '⊃'. We mark the assumption 'F' with a star as shown below.

(p • p) ⊃ p
F
*

2. The next step is to assign values by using basic truth tables. Since in the example, implication is assumed to be false, the antecedent has to be true and consequent has to be false. So we assign values as follows and number the steps.

(p • p) ⊃ p
T F F
(1) * (1)

3. In the next step one has to assign truth values to the component statements of the antecedent. The antecedent is 'p • p' is true. Conjunction is true when both its conjuncts are true. So one has to assign values as follows and number them.

(p • p) ⊃ p
T T T F F
(2) (1) (2) * (1)

4. Next step is to find out whether these assumption leads to any inconsistency. In the above example one gets inconsistent values for 'p'. We indicate inconsistency by 'x' mark as shown below.

(p • p) ⊃ p
T T T F F
(2) (1) (2) * (1)
x x x

In the above example there is inconsistency in step number 1 and 2. So the assumption is wrong. Hence the given statement form is a tautology.

Example 2 (p • ∼ q) V (q ⊃ p)

1. To begin with, one has to assume that the given statement form is 'not a tautology', by writing 'F' below the main connective 'V' (Disjunction). We mark the assumption "F" with a star as shown below.

(p • ∼ q) V (q ⊃ p)
F
*

2. The next step is to assign truth values by using basic truth tables. Since in the example disjunction is assumed to be false, both the disjuncts will be false.

(p • ∼ q) V (q ⊃ p)
F F F
(1) * (1)

3. The next step is to assign truth values to the components of both the disjuncts and number them. In case of 1st disjunct "•" (conjunction) is the main connective and it is false. Conjunction is false under three possibilities, so we should not assign values to its components. We try to get truth values of the second disjunct which is "q ⊃ p". Implication is false only under one condition that is when its antecedent is true and its consequent is false. So one has to assign values to its components and number them as shown below.

(p • ∼ q) V (q ⊃ p)
F F T F F
(1) * (2) (1) (2)

4. Since one knows the truth values of both 'p' and 'q', the same truth values can be assigned to the components of the left disjunct, as shown below and number them.

(p • ∼ q) V (q ⊃ p)
F F F T F T F F
(3) (1) (5) (4) * (2) (1) (2)

5. Next step is to see whether these truth values lead to any inconsistency. In the above example, there is no inconsistency. The assumption is correct. Hence the given statement form is not a tautology.

Teacher's Note

When we test a statement with this method, we check all the truth values step by step. Like checking a recipe to see if it is right by following each step carefully.

Exam Trick

Remember: If you find 'x' marks (inconsistency), the statement is a tautology. If no 'x' marks, it is not a tautology. Count the marks to know the answer quickly.

Points to Remember

We start by assuming the statement is not a tautology.
We place 'F' under the main connective.
We find all truth values step by step.
Inconsistency means the statement is a tautology.
No inconsistency means the statement is not a tautology.

Example 3 (p ⊃ ∼ q) ≡ ∼ (q • p)

One has to assume that the given statement form is 'not a tautology' by writing 'F' under the main connective '≡' (equivalence). Equivalent statement is false under two possibilities. (1) The first component is true and the second is false. And (2) The first component is false and second is true. We have to solve the example by assuming both the possibilities.

1st possibility

Considering the first possibility, values are assigned in the given example as follows.

(p ⊃ ∼ q) ≡ ∼ (q • p)
T F F
1 * 1

2. The next step is to assign truth values to the components of equivalence and number them. In case of first component "⊃" is the main connective and it is true. Implication is true under three possibilities, so we should not assign values to its components. We try to get truth values of the second component which is '∼ (q • p)'. We already placed 'F' below '∼'. When negation is false, conjunction has to be true. Accordingly one has to assign values to its components as shown below.

(p ⊃ ∼ q) ≡ ∼ (q • p)
T F F T T T
1 * 1 3 2 3

3. Since one knows the truth values of both 'p' and 'q', the same truth values can be assigned to the variables in the first component and also to the negation of the variable 'q' as shown below.

(p ⊃ ∼ q) ≡ ∼ (q • p)
T T F T F F T T T
4 1 6 5 * 1 3 2 3
x

4. There is inconsistency in step number 1 as it violates the rule of implication. So the assumption is wrong. Hence the given statement form is a tautology, in the case of first possibility.

2nd possibility

1. (p ⊃ ∼ q) ≡ ∼ (q • p)
F F T
1 * 1

Considering the second possibility, truth values are assigned as follows.

The next step is to assign truth values to the components of equivalence. In case of first component '⊃' is false. So truth values are assigned as follows.

2. (p ⊃ ∼ q) ≡ ∼ (q • p)
T F F T F T
2 1 2 3 * 1

'∼ q' is 'F' so 'q' will be 'T'

Since one knows the truth values of both 'p' and 'q', the same truth values can be assigned to the variables in the second component as shown below.

3. (p ⊃ ∼ q) ≡ ∼ (q • p)
T F F T F T T F T
2 1 2 3 * 1 5 4 6
x

There is inconsistency in step number 4 as it violates the rule