Page 108 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes Universal Elimination (or Universal Instantiation)
∀α ϕ
ϕβ )
( α
Restriction: No free occurrence of α in ϕ falls within the scope of a quantifier quantifying a
variable occurring in β.
Existential Introduction (or Existential Generalization)
ϕβ )
( α
∃α ϕ
Restriction: No free occurrence of α in ϕ falls within the scope of a quantifier quantifying a
variable occurring in β.
Existential Elimination (or Existential Instantiation)
∃α ϕ
ϕβ ) ψ
( α
ψ
Restriction 1: No free occurrence of α in ϕ falls within the scope of a quantifier quantifying a
variable occurring in β.
Restriction 2: There is no occurrence, free or bound, of β in ψ.

Example 1: Let us consider the following assumptions: “If it rains today, then we will not
go on a canoe today. If we do not go on a canoe trip today, then we will go on a canoe trip
tomorrow. Therefore (Mathematical symbol for “therefore” is ∴), if it rains today, we will go on
a canoe trip tomorrow. To make use of the rules of inference in the above table p we let be the
proposition “If it rains today”, q be “ We will not go on a canoe today” and let r be “We will go
on a canoe trip tomorrow”. Then this argument is of the form:

p → q
q → r
∴
p → r

Example 2: Let us consider a more complex set of assumptions: “It is not sunny today and
it is colder than yesterday”. “We will go swimming only if it is sunny”, “If we do not go
swimming, then we will have a barbecue”, and “If we will have a barbecue, then we will be
home by sunset” lead to the conclusion “We will be home before sunset.” Proof by rules of
inference: Let p be the proposition “It is sunny this today”, q the proposition “It is colder than
yesterday”, r the proposition “We will go swimming”, s the proposition “We will have a
barbecue”, and t the proposition “We will be home by sunset”. Then the hypotheses become
¬p ∧ q, r → p, ¬r → s and s → t. Using our intuition we conjecture that the conclusion might be
t. Using the Rules of Inference table, we can proof the conjecture easily:

Step Reason
1. ¬p ∧ q Hypothesis
2. ¬p Simplification using Step 1
3. r → p Hypothesis

102 LOVELY PROFESSIONAL UNIVERSITY