Unit 3 Resolution Refutation Examples

CS621: Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept.,
IIT Bombay
Lecture 8– Logic and Intelligent

Question Answering (puzzle solving)
Problem-1
From Predicate Calculus

Club Example (Zohar Manna, 1974)
 Facts and Rules: A, B and C belong to the

Himalayan club. Every member in the club is
either a mountain climber or a skier or both.
A likes whatever B dislikes and dislikes
whatever B likes. A likes rain and snow. No
mountain climber likes rain. Every skier likes
snow.
 Question: Is there a member who is a
mountain climber and not a skier?
Solution step-1: Knowledge
Extraction
 Let mc denote mountain climber and sk denotes skier. Knowledge
representation in the given problem is as follows:
1. member(A)
2. member(B)
3. member(C)
4. ∀x[member(x) → (mc(x) ∨ sk(x))]
5. ∀x[mc(x) → ~like(x,rain)]
6. ∀x[sk(x) → like(x, snow)]
7. ∀x[like(B, x) → ~like(A, x)]
8. ∀x[~like(B, x) → like(A, x)]
9. like(A, rain)
10. like(A, snow)
11. Question: ∃x[member(x) ∧ mc(x) ∧ ~sk(x)]
 We have to infer the 11th expression from the given 10.
 Done through Resolution Refutation.
Step-2: Conversion to Clausal Form
1. member(A)
2. member(B)
3. member(C)
4. x[member ( x)  (mc( x)  sk ( x))]
– Can be written as
[member( x)  (mc( x)  sk ( x))]
– ~ member ( x)  mc( x)  sk ( x)
5. x[ sk ( x)  lk ( x, snow)]
– ~ sk ( x)  lk ( x, snow)
6. x[mc( x) ~ lk ( x, rain)]
– ~ mc( x) ~ lk ( x, rain)
7. x[like( A, x) ~ lk ( B, x)]
– ~ like( A, x) ~ lk ( B, x)
8. x[~ lk ( A, x)  lk ( B, x)]
– lk ( A, x)  lk ( B, x)
9. lk ( A, rain)
10. lk ( A, snow)
11. x[member ( x)  mc( x)  ~ sk ( x)]
– Negate– x[~ member ( x) ~ mc( x)  sk ( x)]
Step-3: standardizing the variables apart
1. member(A)
2. member(B)
3. member(C)
4. ~ member ( x1)  mc( x1)  sk ( x1)
5. ~ sk ( x 2)  lk ( x 2, snow)
6. ~ mc( x 3) ~ lk ( x 3, rain )
7. ~ like( A, x 4) ~ lk ( B, x 4)
8. lk ( A, x 5)  lk ( B, x 5)
9. lk ( A, rain)
10. lk ( A, snow)
11. x[~ member ( x 6) ~ mc( x 6)  sk ( x 6)]
~ like( A, x 4) ~ lk ( B, x 4) lk ( A, snow) 10
7
12 ~ lk ( B, snow) ~ sk ( x 2)  lk ( x 2, snow) 5
13 ~ sk ( B ) ~ member ( x1)  mc( x1)  sk ( x1) 4
14 ~ member ( B )  mc( B ) member (B ) 2
11
x[~ member ( x 6 ) ~ mc( x 6)  sk ( x 6)] mc(B) 15
16 ~ member ( B )  sk ( B ) ~ sk ( B) 13
17 ~ member ( B ) member (B) 2

Problem-2
From predicate calculus

A “department” environment
1. Dr. X is the HoD of CSE
2. Y and Z work in CSE
3. Dr. P is the HoD of ME
4. Q and R work in ME
5. Y is married to Q
6. By Institute policy staffs of the same
department cannot marry
7. All married staff of CSE are insured by LIC
8. HoD is the boss of all staff in the
department
Diagrammatic representation
CSE ME
Dr. P
Dr. X
Z
Y Q R
married
Questions on “department”
 Who works in CSE?
 Is there a married person in ME?
 Is there somebody insured by LIC?
Problem-3
(Zohar Manna, Mathematical Theory of
Computation, 1974)
From Propositional Calculus

Tourist in a country of truth-
sayers and liers
 Facts and Rules: In a certain country, people
either always speak the truth or always
lie. A tourist T comes to a junction in the
country and finds an inhabitant S of the
country standing there. One of the roads at
the junction leads to the capital of the
country and the other does not. S can be
asked only yes/no questions.
 Question: What single yes/no question can T
ask of S, so that the direction of the capital is
revealed?
Diagrammatic representation
Capital
S (either always says the truth

Or always lies)
T (tourist)
Deciding the Propositions: a very difficult
step- needs human intelligence
 P: Left road leads to capital

 Q: S always speaks the truth
Meta Question: What question
should the tourist ask
 The form of the question
 Very difficult: needs human intelligence
 The tourist should ask
 Is R true?
 The answer is “yes” if and only if the
left road leads to the capital
 The structure of R to be found as a
function of P and Q
A more mechanical part: use
of truth table
P Q S’s R
Answer
T T Yes T
T F Yes F
F T No F
F F No T
Get form of R: quite
mechanical
 From the truth table
 R is of the form (P x-nor Q) or (P ≡ Q)
Get R in
English/Hindi/Hebrew…
 Natural Language Generation: non-trivial
 The question the tourist will ask is
 Is it true that the left road leads to the
capital if and only if you speak the truth?
 Exercise: A more well known form of this
question asked by the tourist uses the X-OR
operator instead of the X-Nor. What changes
do you have to incorporate to the solution, to
get that answer?
Problem-4
From Propositional Calculus

Another tourist example: this time in a
restaurant setting in a different country
(Manna, 1974)
 Facts: A tourist is in a restaurant in a country when
the waiter tells him:
 “do you see the three men in the table yonder? One of them
is X who always speaks the truth, another is Y who always
lies and the third is Z who sometimes speaks the truth and
sometimes lies, i.e., answers yes/no randomly without
regard to the question.
 Question: Can you (the tourist) ask three yes/no
questions to these men, always indicating who
should answer the question, and determine who of
them is X, who y and who Z?
Solution: Most of the steps are
doable by humans only
 Number the persons: 1, 2, 3
 1 can be X/Y/Z
 2 can be X/Y/Z
 3 can be X/Y/Z
 Let the first question be to 1
 One of 2 and 3 has to be NOT Z.
 Critical step in the solution: only
humans can do?
Now cast the problem in the
same setting as the tourist and
the capital example
 Solving by analogy
 Use of previously solved problems
 Hallmark of intelligence
Analogy with the tourist and
the capital problem
 Find the direction to the capital
  Find Z; who amongst 1, 2 and 3 is Z?
 Ask a single yes/no question to S (the person
standing at the junction)
  Ask a single yes/no question to 1
 Answer forced to reveal the direction of the
capital
  Answer forced to reveal who from 1,2,3 is Z
Question to 1
 Ask “Is R true” and the answer is yes if
and only if 2 is not Z
 Propositions
 P: 2 is not Z
 Q: 1 always speaks the truth, i.e., 1 is X
Use of truth table as before
P Q 1’s R
Answer
T T Yes T
T F Yes F
F T No F
F F No T
Question to 1: the first
question
 Is it true that 2 is not Z if and only
if you are X?
Analysis of 1’s answer
 Ans= yes
 Case 1: 1 is X/Y (always speaks the truth
or always lies)
 2 is indeed not Z (we can trust 1’s answer)
 Case 2: 1 is Z
 2 is indeed not Z (we cannot trust 1’s answer;
but that does not affect us)
Analysis of 1’s answer (contd)
 Ans= no
 Case 1: 1 is X/Y (always speaks the truth
or always lies)
 2 is Z; hence 3 is not Z
 Case 2: 1 is Z
 3 is not Z
Note carefully: how cleverly Z is identified.

Can a machine do it?
Next steps: ask the 2nd
question to determine X/Y
 Once “Not Z” is identified- say 2, ask
him a tautology
 Is P≡P
 If yes, 2 is X
 If no, 2 is Y
Ask the 3rd Question
 Ask 2 “is 1 Z”
 If 2 is X
 Ans=yes, 1 is Z
 Ans=no, 1 is Y
 If 2 is Y (always lies)
 Ans=yes, 1 is X
 Ans=no, 1 is Z
 3 is the remaining person
What do these examples
show?
 Logic systematizes the reasoning process
 Helps identify what is
mechanical/routine/automatable
 Brings to light the steps that only human
intelligence can perform
 These are especially of foundational and structural
nature (e.g., deciding what propositions to
start with)
 Algorithmizing reasoning is not trivial
Assignment on Deduction,
Induction and Abduction
Guidelines for submission
Inference
method Deduction Induction Abduction
task
Survival
Efficiency
Life Quality
Fill the cells
 Put a tick in the cell <i, j> if the inference
method j is needed for the task i.
 Support the decision with an appropriate
example
 Before doing the task provide your
 Definitions
 References (work that you have studied for doing
the assignment)

Unit 3 Resolution Refutation Examples

Uploaded by

Copyright:

Available Formats

Unit 3 Resolution Refutation Examples

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 3 Resolution Refutation Examples

Uploaded by

Copyright:

Available Formats

CS621: Artificial Intelligence

Lecture 8– Logic and Intelligent

From Predicate Calculus

 Facts and Rules: A, B and C belong to the

13 ~ sk ( B ) ~ member ( x1)  mc( x1)  sk ( x1) 4

14 ~ member ( B )  mc( B ) member (B ) 2

17 ~ member ( B ) member (B) 2

From predicate calculus

From Propositional Calculus

S (either always says the truth

 P: Left road leads to capital

From Propositional Calculus

Note carefully: how cleverly Z is identified.

You might also like