Transcript 323-670 ปัญญาประดิษฐ์ (Artificial Intelligence)

CS.462
Artificial Intelligence
SOMCHAI THANGSATHITYANGKUL
Lecture 05 : Knowledge Base & First Order Logic
Knowledge base
• A knowledge base KB is a set of sentences. Example
KB:
JerryGivingLecture (TodayIsTuesday 
TodayIsThursday)
 JerryGivingLecture
• It is equivalent to a single long sentence: the
conjunction of all sentences
(JerryGivingLecture (TodayIsTuesday 
TodayIsThursday)) JerryGivingLecture
2
Entailment
• Entailment is the relation of a sentence
logically
follows from other sentences.
 |= 
 |=  if and only if, in every interpretation
in which  is true,  is also true
• Deduction theorem:  |=  if and only if 
  is valid (always true)
3
Natural Deduction
• Proof is a sequence of sentences
First ones are premises (KB)
Then, you can write down on line j the result of applying
an inference rule to previous lines
When f is on a line, you know KB f
If inference rules are sound, then KB f











Modu
s
ponen
s
Modu
s
tolens
AndAndintroduct eliminat
4
ion
ion
Natural deduction example
Prove S
Step Formula
Derivation
1
PQ
Given
2
PR
Given
3
(Q  R) S
Given
5
Natural deduction example
• KB:
1. JerryGivingLecture  (TodayIsTuesday 
TodayIsThursday)
2.  JerryGivingLecture
Prove:
 TodayIsTuesday
6
Step
Formula
Derivation
1
JerryGivingLecture 
(TodayIsTuesday  TodayIsThursday)
Given
2
 JerryGivingLecture
Given
3
JerryGivingLecture 
(TodayIsTuesday  TodayIsThursday)
Biconditional
elimination to 1.
4
(TodayIsTuesday  TodayIsThursday)
JerryGivingLecture
Biconditional
elimination to 1.
5
JerryGivingLecture 
(TodayIsTuesday  TodayIsThursday)
Contrapositive to
4.
7
Propositional Resolution
8
Propositional Resolution Example
9
Resolution tree
•
•
•
•
KB : (A  CD)  (ADE)  (A  C)
Prove : (DE)
Negated conclusion : (DE)
Convert KB in the CNF, So we have KB:
1.
2.
3.
4.
5.
(A  C  D)
(A  D  E)
(A  C)
D
E
10
Resolution tree
11
Try this
(P → Q) → Q ,
(P → P) → R ,
(R → S) → ¬(S → Q) Prove R
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36