Tutorialspoint.dev

Mathematics | Rules of Inference

Prerequisite: Predicates and Quantifiers Set 2, Propositional Equivalences

Every Theorem in Mathematics, or any subject for that matter, is supported by underlying proofs. These proofs are nothing but a set of arguments that are conclusive evidence of the validity of the theory.
The arguments are chained together using Rules of Inferences to deduce new statements and ultimately prove that the theorem is valid.

Important Definitions :

1. Argument – A sequence of statements, premises, that end with a conclusion.
2. Validity – A deductive argument is said to be valid if and only if it takes a form that makes it impossible for the premises to be true and the conclusion nevertheless to be false.
3. Fallacy – An incorrect reasoning or mistake which leads to invalid arguments.

Structure of an Argument :
As defined, an argument is a sequence of statements called premises which end with a conclusion.



Premises - p_{1},:p_{2},:p_{3},..., :p_{n}
Conclusion - q

if(p_{1}wedge p_{2}wedge p_{3}wedge ... wedge p_{n})
ightarrow q is a tautology, then the argument is termed valid otherwise termed as invalid. The argument is written as –

 egin{tabular}{l} First:Premise\ Second:Premise\ Third:Premise\ .\ .\ Nth:Premise\ hline 	herefore Conclusion end{tabular} 

Rules of Inference :
Simple arguments can be used as building blocks to construct more complicated valid arguments. Certain simple arguments that have been established as valid are very important in terms of their usage. These arguments are called Rules of Inference.

The most commonly used Rules of Inference are tabulated below –

  egin{tabular}{||c||c||c||} hline Rule of Inference & Tautology & Name\ hline  
ule{0pt}{8ex} shortstack[l]{p \ p
ightarrow q \ 
ule{1cm}{0.5pt}\ 	herefore q}& (pwedge (p
ightarrow q)) 
ightarrow q & Modus Ponens \ hline  
ule{0pt}{8ex} shortstack[l]{
eg q \ p
ightarrow q \ 
ule{1cm}{0.5pt}\ 	herefore 
eg p}& (
eg q wedge (p
ightarrow q)) 
ightarrow 
eg p & Modus Tollens \ hline  
ule{0pt}{8ex} shortstack[l]{p
ightarrow q \ q
ightarrow r \ 
ule{1.3cm}{0.5pt}\ 	herefore p 
ightarrow r}& ((p
ightarrow q) wedge (q
ightarrow r)) 
ightarrow (p
ightarrow r) & Hypothetical syllogism \ hline  
ule{0pt}{8ex} shortstack[l]{ 
eg p \ pvee q \ 
ule{0.8cm}{0.5pt}\ 	herefore q} & (
eg p wedge (pvee q)) 
ightarrow q & Disjunctive Syllogism \ hline  
ule{0pt}{8ex} shortstack[l]{p \ 
ule{1.5cm}{0.5pt} \ 	herefore (p vee q)}& p
ightarrow (pvee q) & Addition \ hline  
ule{0pt}{8ex} shortstack[l]{ (pwedge q)
ightarrow r \ 
ule{2.3cm}{0.5pt}\ 	herefore p
ightarrow (q
ightarrow r)} & ((pwedge q)
ightarrow r) 
ightarrow (p
ightarrow (q
ightarrow r)) & Exportation\ hline  
ule{0pt}{8ex} shortstack[l]{pvee q\
eg pvee r \ 
ule{1.2cm}{0.5pt} \ 	herefore qvee r}& ((pvee q) wedge(
eg pvee r)) 
ightarrow qvee r & Resolution \ hline   end{tabular}  

Similarly, we have Rules of Inference for quantified statements –

 egin{tabular}{||l||l||} hline Rule of Inference & Name\ hline hline  
ule{0pt}{6ex} shortstack[l]{forall xP(x) \ 
ule{1cm}{0.5pt}\ 	herefore P(c)} & Universal instantiation \ hline  
ule{0pt}{6ex} shortstack[l]{P(c) for an arbitrary c\ 
ule{4cm}{0.5pt}\ 	herefore forall xP(x)} & Universal generalization \ hline  
ule{0pt}{6ex} shortstack[l]{exists xP(x)\ 
ule{3cm}{0.5pt} \ 	herefore P(c):for:some:c} & Existential instantiation \ hline  
ule{0pt}{6ex} shortstack[l]{P(c) for some c \ 
ule{2.6cm}{0.5pt}\ 	herefore exists xP(x)} & Existential generalization \ hline end{tabular} 

Let’s see how Rules of Inference can be used to deduce conclusions from given arguments or check the validity of a given argument.

Example : Show that the hypotheses
“It is not sunny this afternoon and it is colder than yesterday”,
“We will go swimming only if it is sunny”,
“If we do not go swimming, then we will take a canoe trip”, and
“If we take a canoe trip, then we will be home by sunset”
lead to the conclusion
“We will be home by sunset”.
The first step is to identify propositions and use propositional variables to represent them.
p- “It is sunny this afternoon”
q- “It is colder than yesterday”
r- “We will go swimming”
s- “We will take a canoe trip”
t- “We will be home by sunset”
The hypotheses are –

eg p wedge q, r
ightarrow p, 
eg r 
ightarrow s, and s
ightarrow t.
The conclusion is –
t
To deduce the conclusion we must use Rules of Inference to construct a proof using the given hypotheses.
 egin{tabular}{||l||l||} hline Step & Reason\ hline hline 1. 
eg p wedge q & Hypothesis\ 2. 
eg p & Simplification\ 3. r 
ightarrow p & Hypothesis\ 4. 
eg r  & Modus Tollens using (2) and (3)\ 5. 
eg r 
ightarrow s & Hypothesis\ 6. s & Modus Ponens using (4) and (5)\ 7. s
ightarrow t & Hypothesis\ 8. t & Modus Ponens Using (6) and (7)\ hline end{tabular}

Resolution Principle :
To understand the Resolution principle, first we need to know certain definitions.

  1. Literal – A variable or negation of a variable. Eg- p, 
eg q
  2. Sum – Disjunction of literals. Eg- pvee 
eg q
  3. Product – Conjunction of literals. Eg- p wedge 
eg q
  4. Clause – A disjunction of literals i.e. it is a sum.
  5. Resolvent – For any two clauses C_{1} and C_{2}, if there is a literal L_{1} in C_{1} that is complementary to a literal L_{2} in C_{2}, then removing both and joining the remaining clauses through a disjunction produces another clause C. C is called the resolvent of C_{1} and C_{2}

For example,

 
C_{1} = pvee qvee r 
C_{2} = 
eg pvee 
eg s vee t 

Here, 
eg p and p are complementary to each other. Removing them and joining the remaining clauses with a disjunction gives us-
qvee r vee 
eg svee t
We could skip the removal part and simply join the clauses to get the same resolvent.
since p vee 
eg p equiv T: and,: T vee q equiv q
This is also the Rule of Inference known as Resolution.

Theorem – If C is the resolvent of C_{1} and C_{2}, then C is also the logical consequence of C_{1} and C_{2}.



The Resolution Principle – Given a set S of clauses, a (resolution) deduction of C from S is a finite sequence C_{1}, C_{2},..., C_{k} of clauses such that each C_{i} is either a clause in S or a resolvent of clauses preceding C and C_{k} = C.
We can use the resolution principle to check the validity of arguments or deduce conclusions from them. Other Rules of Inference have the same purpose, but Resolution is unique. It is complete by it’s own. You would need no other Rule of Inference to deduce the conclusion from the given argument.

To do so, we first need to convert all the premises to clausal form. The next step is to apply the resolution Rule of Inference to them step by step until it cannot be applied any further.

For example, consider that we have the following premises –

 p
ightarrow (qvee r) 
s
ightarrow 
eg r 
pwedge s 

The first step is to convert them to clausal form –

C_{1}: :
eg pvee qvee r 
C_{2}: :
eg svee 
eg r
C_{3}: :p
C_{4}: :s

From the resolution of C_{1} and C_{2}, C_{5}:: 
eg pvee qvee 
eg s
From the resolution of C_{5} and C_{3}, C_{6}:: qvee 
eg s
From the resolution of C_{6} and C_{4}, C_{7}:: q
Therefore, the conclusion is q.

GATE CS Corner Questions

Practicing the following questions will help you test your knowledge. All questions have been asked in GATE in previous years or in GATE Mock Tests. It is highly recommended that you practice them.
1. GATE CS 2004, Question 70
2. GATE CS 2015 Set-2, Question 13

References-
Rules of Inference – Simon Fraser University
Rules of Inference – Wikipedia
Fallacy – Wikipedia
Discrete Mathematics and its Applications, by Kenneth H Rosen

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter