IT3160E

Introduction to Artificial Intelligence

Chapter 4: Knowledge and Inference

Lê Thanh Hương
School of Information and Communication Technology - HUST
Knowledge-based Agents
• Know about the world
• They maintain a collection of facts (sentences) about the world, their
Knowledge Base, expressed in some formal language.
• Reason about the world
• They are able to derive new facts from those in the KB using some inference
mechanism.
• Act upon the world
• They map percepts to actions by querying and updating the KB.

2
What is Logic ?

• A logic is a triplet <L,S,R>

• L, the language of the logic, is a class of sentences described by a precise syntax,
usually a formal grammar
• S, the logic’s semantic, describes the meaning of elements in L
• R, the logic’s inference system, consisting of derivation rules over L

• Examples of logics:
• Propositional, First Order, Higher Order, Temporal, Fuzzy, Modal, Linear, …

3
Propositional Logic

• Propositional Logic is about facts in the world that are either true or
false, nothing else
• Propositional variables stand for basic facts
• Sentences are made of
• propositional variables (A,B,…),
• logical constants (TRUE, FALSE), and
• logical connectives (not,and,or,..)
• The meaning of sentences ranges over the Boolean values {True,
False}
• Examples: It’s sunny, John is married

4
Language of Propositional Logic

• Symbols
• Propositional variables: A,B,…,P,Q,…
• Logical constants: TRUE, FALSE
• Logical connectives: ,,, , 

• Sentences
• Each propositional variable is a sentence
• Each logical constant is a sentence
• If  and  are sentences then the following are sentences
( ),  ,    ,    ,    ,   

5
Formal Language of Propositional Logic

• Formal Grammar
• Sentence -> Asentence | Csentence

• Asentence -> TRUE | FALSE | A | B|…

• Csentence -> (Sentence) | Sentence | Sentence Connective Sentence

• Connective -> ,,, , 

6
Semantic of Propositional Logic

• The meaning of TRUE is always True, the meaning of FALSE is

always False
• The meaning of a propositional variable is either True or False
• depends on the interpretation
• assignment of Boolean values to propositional variables
• The meaning of a sentence is either True or False
• depends on the interpretation

7
Semantic of Propositional Logic

• True table

P Q Not P P and Q P or Q P implies Q P equiv Q

False False True False False True True

False True True False True True False

True False False False True False False

True True False True True True True

ab  ab  ba

8
Semantic of Propositional Logic

• Entailment
• Given
• A set of sentences 
• A sentence 
• We write
 ╞ 
if and only if every interpretation that makes all sentences in true also makes  true
• We said that  entails 

9
Inference in Propositional Logic

• Forward Chaining
• Backward Chaining

10
Forward Chaining

• Given a set of rules, i.e. formulae of the form

p1  p2  ...  pn  q
and a set of known facts, i.e., formulae of the form
q, r,…
• A new fact p is added
• Find all rules that have p as a premise
• If the other premises are already known to hold then
• add the consequent to the set of know facts, and
• trigger further inferences

11
Forward Chaining

• Example

12
Forward Chaining

13
Forward Chaining

14
Forward Chaining

15
Forward Chaining

16
Forward Chaining

17
Forward Chaining

18
Example

E1. Given Fact = {a,b,ma}. Prove hc

1. a,b,ma →c 6. a,B →hc
2. a,b,c → A 7. A,B →C
3. b,A → hc 8. B,C →A
4. a,b,c → B 9. A,C →B
5. a,b,c →C

19
Forward Chaining

Input:
◼ Sentences/clauses in Horn format (Fact)
◼ A rule set R p1  p2  ...  pn  q
◼ Goal
Output:
◼ “Success” if Goal can be inferred from Fact

Method: Use
• Temp - a set of propositional variables which are true at the
current time
• Sat - a set of satisfied rules

20
Forward Chaining

{1 Temp = Fact;
Sat= FindRules(Temp,R);
while Sat<>0 and GoalTemp do
{2 r  get(Sat); /* r: left → q */
R = R \ {r}; Trace = Trace  {r};
Temp = Temp  {q};
Sat = FindRules(Temp,R)
}2
if Goal  Temp then exit(“Success”)
else exit(“Not success”)
}1
21
Example

E1. Given Fact = {a,b,ma}. Prove hc

1. a,b,ma →c 6. a,B →hc
2. a,b,c → A 7. A,B →C
3. b,A → hc 8. B,C →A
4. a,b,c → B 9. A,C →B
5. a,b,c →C

22
Exercises

Compare stack and queue

1- Given Fact={a}, Goal={u} 2 - Given Fact={a}, Goal={u}
1. a→ b 1. a → b
2. b→c 2. d → c
3. c→d 3. c → u
4. a→u 4. a → m
5. b → n
6. m → p
7. p → q
8. q → u

23
Backward Chaining

• Given a set of rules, and a set of known facts

• We ask whether a fact P is a consequence of the set of rules and the
set of known facts
• The procedure check whether P is in the set of known facts
• Otherwise find all rules that have P as a consequent
• If the premise is a conjunction, then process the conjunction conjunct by
conjunct

24
Backward Chaining

• Example

25
Backward Chaining

26
Backward Chaining

27
Backward Chaining

28
Backward Chaining

29
Backward Chaining

Variables:
◼ Goal: set of variables needed to be proved
◼ temp = {f| f is needed to be proved until now}
◼ trace ={(f,j)| to prove f, use rule j: leftj→f}
◼ Flag Back = true when backtrack
false otherwise

30
 f  temp
F
T T
f  Fact temp = 0? OK
F
Find rj: leftj → f

not OK T Trace = Trace {(f,j)}

Found
temp = temp  leftj\Fact
T
F
F
f Goal? (g,k)  trace:
Find (g,k)  trace with f, try rj
rk: leftk → g; f  leftk

Find rule (g,l), l>k

temp = temp\leftk
F T
f=g Found temp = temp  leftl\fact
trace = trace {(g,l)}
31
Backward Chaining

Example:
1. A,C → B 6. a,B→ hc
2. a,b,ma →c 7. b,A → hc
3. a,b,c → A 8. c,S → hc
4. a,b,c → B 9. a,b,c → S
5. a,b,c → C 1’. ha,c → B
Fact={a,b,ma}; Goal={hc}

32
Exercises

E1. Given Fact={a,b,ma}, E2. Given Fact={a},

Goal={hc} Goal={u}
1. a,b,ma → c
1. a → b
2. a,b,C → s
3. a,s → ha
2. d → c
4. b,s → hb 3. c → u
5. c,s → hc 4. a → m
6. a,B → hc 5. b → n
7. a,b,c → B
6. m → p
7. p → q
8. q → u
33
Transformation rules

Commutativity of 

Associativity of 

Double negation elimination

Contraposition

de Morgan

Distributivity of  and 

34
Transformation rules (con’t)

Absorption law:
• (A  (A  B)  A • (A  (A  B))  A

Rules about 0, 1:
• A00 • A0A
• A11 • A1A
• 1  0 • 0  1
Law of the Excluded Middle:
• A  A  1

Law of contradiction:
• A  A  0

35
Transform into CNF

B1,1  (P1,2  P2,1)

1. Remove , replace α  β by (α  β)(β  α).

(B1,1  (P1,2  P2,1))  ((P1,2  P2,1)  B1,1)

2. Remove , replace α  β by α β.

(B1,1  P1,2  P2,1)  ((P1,2  P2,1)  B1,1)

3. Move negation inward using the de Morgan’s rule :

(B1,1  P1,2  P2,1)  ((P1,2  P2,1)  B1,1)

4. Applying the “and” distribution rule :

(B1,1  P1,2  P2,1)  (P1,2  B1,1)  (P2,1  B1,1)

36
Example

(AB)→(C→D)
1. Remove 
(AB)(CD)
2. Move negation inward
(AB)(CD)
3. Distribution
(ACD)(BCD)

37
Exercises

Transform the following expression into CNF.

1. P  (P  Q  R)
2. (P  Q)  (P  Q)
3. (P  Q)  (P  Q)
4. (P  Q)  R
5. (P (Q  R))  ((P  S)  R)
6. (P  (Q  R))  S
7. PQRS
8. ((ab)c)→(cd)
Priority:    → 

38
1. P  (P  Q  R)
2. (P  Q)  (P  Q)
3. (P  Q)  (P  Q)
4. (P  Q)  R
5. (P (Q  R))  ((P  S)  R)
6. (P  (Q  R))  S
7. PQRS

39
Resolution

Conjunctive Normal Form - CNF

E.g., (A  B)  (B  C  D)

• Resolution rule for CNF:

l1 …  lk, m1  …  mn
l1  …  li-1  li+1  …  lk  m1  …  mj-1  mj+1 ...  mn

in which li and mj bù nhau

E.g., P1,3  P2,2, P2,2

P1,3

40
Resolution

• Herbrand’s Theorem (~1930)

• A set of sentences S is unsatisfiable if and only there exists a finite subset Sg
of the set of all ground instances Gr(S), which is unsatisfiabe
• Herbrand showed that there is a procedure to demonstrate the
unsatisfiability of a unsatisfiable set of sentences
• Robinson propose the Resolution procedure (~1950)

41
Idea of Resolution

• Refutation-based procedure
• S |= A if and only if is unsatisfible
S  {A}
• Resolution procedure
• Transform S  {A} into a set of clauses
• Apply Resolution rule to find a the empty clause
(contradiction)
• If the empty clause is found
• Conclude S |= A
• Otherwise
• No conclusion

42
Idea of Resolution

• A clause is a disjunction of literals, i.e., has the form

P1  P2  ...  Pn Pi  []Ri

• The empty clause corresponds to a contradiction

• Resolution rule
A B B  C
AC

43
Robinson’s Resolution

44
Robinson’s Resolution

Given KB = {P1, P2, ..., Pn}. Prove Q.

Add Q to KB: KB = KB  Q. Prove unsatisfied.

1. Write each Pi, Q in one line.

2. Transfer to CNF representation
(a1…an)  (b1…bn) (*)
3. Rewrite each line (*) into smaller lines:
a1…an
b1…bn

45
Robinson’s Resolution

Consider 2 lines
u) pq
v) pr
Resolution:
w) qr
Contrast appears when KB contains 2 lines:
i) t
ii) t
 done

46
Examples

E1) E2)
1. a 1. ab→c
2. a→b 2. bc →d
3. b→(c→d) 3. a
4. c 4. b
Prove d
Prove d

47
Examples

E3) E4)
1. p 1. ((ab)c)→(cd)
2. p→q 2. amd→f
3. qrs→t 3. m→bc
4. p→u 4. a→c
5. v→w 5. (af)→(eg)
6. u→v 6. (mf)→g
7. v→t
Given a,m are true. Prove g
Given r,s are true. Prove t

48
Exercise 5

1. a1  a2  a3  a4
2. a1  a5
3. a2  a3  a5
4. a2  a4  a6  a7
5. a5  a7
6. a1  a3  a6  a7

• Given a1, a2 are true .

• Transfer the above sentences to the CNF representation
• Apply the Robinson's resolution, prove a7 is true.

49