PGS.TS. Phan Huy Kh
PGS.TS. Phan Huy Kh
á
á
nh
nh


H
H



chuyên gia
chuyên gia

(
(
Expert System
Expert System
)
)
Chng 2
Biu din tri thc

nh

logic v

t





t
t



b
b


c m
c m


t
t
\
\
Ph
Ph


n 2.3 :
n 2.3 :
u
u
Lôgic v
Lôgic v

c nh
c nh


logic v
logic v


t
t


b
b


c m
c m


t
t
3/
3/
69
69
Limitations of Propositional Logic 2
Limitations of Propositional Logic 2
\
\

all triangles have 3 sides
all triangles have 3 sides
4/
4/
69
69
Predicate Logic Overview
Predicate Logic Overview
\
\
Predicate Logic
Predicate Logic
u
u
Principles
Principles
u
u
Objects
Objects
u
u
Relations
Relations
u
u
properties
properties
\
\

, ( )
Constants

a z

Constants

a z
Variale

A Z

Variale

A Z
Function

f g h

Function

f g h
Predicate

P
0

P Q R

Predicate

f(t
1

, …t
n

)

Term

f(t
1

, …t
n

)
Atom

P Q R

Atom

P Q R
Atom

P(t
1

, …t


∃X ∀Y (P(X, Y) →

R(Y))

Wff

∃X ∀Y (P(X, Y) →

R(Y))
Alphabet
Alphabet
6/
6/
69
69
B
B


ng ký hi
ng ký hi


u (
u (
Alphabet
Alphabet
)
)

c đ
c đ
ú
ú
ng g
ng g


m :
m :
u
u
C
C
á
á
c
c
d
d


u phân c
u phân c
á
á
ch
ch
(separator signs) :
(separator signs) :

) v
) v
à
à

d
d


u đ
u đ
ó
ó
ng ngo
ng ngo


c (
c (
)
)
)
)
u
u
C
C
á
á
c


ng c
ng c
á
á
c ch
c ch



c
c
á
á
i in th
i in th


ng
ng
a
az
z
V
V
í
í


ng chu
ng chu


i s
i s



d
d


ng c
ng c
á
á
c ch
c ch



c
c
á
á
i in hoa
i in hoa
A


(predicate) :
(predicate) :
đ
đ


c vi
c vi


t tng t
t tng t



c
c
á
á
c
c
bi
bi


n
n
, s
, s

í
í
d
d


: ISRAINING, ON(table), P(X, blue), BETWEEN(X, Y, Z)
: ISRAINING, ON(table), P(X, blue), BETWEEN(X, Y, Z)
7/
7/
69
69
B
B


ng ký hi
ng ký hi


u (
u (
Alphabet
Alphabet
)
)
\
\
C
C

à
à
↔
↔
tng
tng


ng v
ng v


i c
i c
á
á
c ph
c ph
é
é
p ph
p ph


đ
đ


nh, v
nh, v

\
\
C
C
á
á
c
c
d
d


u l
u l


ng t
ng t


u
u
∃
∃
l
l


ng t
ng t



(universal quantifier)
(universal quantifier)
8/
8/
69
69
Names
Names
\
\
Constants are used to name existing
Constants are used to name existing
objects:
objects:
u
u
The interpretation identifies the object in the real world
The interpretation identifies the object in the real world
u
u
No
No
constant can name more than one object
constant can name more than one object
u
u
An object can have more than one
An object can have more than one

Tiberius
Tiberius

Sempronius
Sempronius

Gracchus
Gracchus
9/
9/
69
69
BNF Grammar Predicate Logic
BNF Grammar Predicate Logic
<Sentence>
<Sentence>

→
→

<AtomicSentence
<AtomicSentence
>
>
|
|
(
(
<
<

¬

<
<
Sentence
Sentence
>
>
<
<
AtomicSentence>
AtomicSentence>

→
→

<
<
Predicate>(<Term>,
Predicate>(<Term>,
)
)

|
|

<
<
Term>=
Term>=

<
Variable
Variable
>
>
<
<
Connective>
Connective>

→
→

∧
∧

|
|

∨
∨

|
|

→
→

|
|

<
<
Variable>
Variable>

→
→

A, B, C, X
A, B, C, X

1
1
, X
, X

2
2

, COUNTER, POSITION
, COUNTER, POSITION
<Function>
<Function>

→
→

father
father
-

10/
10/
69
69
First Order Predicate Logics Syntax
First Order Predicate Logics Syntax
term
term

::=
::=

variable
variable

| function_symbol_of_arity_n(t
| function_symbol_of_arity_n(t

1
1

,
,
…
…
, t
, t

n
n


n
n

)
)

n>0
n>0

| predicate_symbol_of_arity_0
| predicate_symbol_of_arity_0

constant
constant
literal
literal

::=
::=

atom
atom

positive literal
positive literal

|
|
¬

negation

| (wff
| (wff
∧
∧

wff)
wff)

conjunction
conjunction

| (wff
| (wff
∨
∨

wff)
wff)

disjunction
disjunction

| (wff
| (wff
→
→

wff)

| (
| (
∃
∃

variable wff)
variable wff)

existential
existential

formula
formula
11/
11/
69
69
C
C
á
á
c h
c h
à
à
m (function)
m (function)
\
\
C

á
c h
c h


ng
ng
u
u
s
s


d
d


ng c
ng c
á
á
c ch
c ch


in th
in th


ng

l


ng c
ng c
á
á
c đ
c đ


i) c
i) c


đ
đ


nh, l
nh, l
à
à
m
m


t s
t s


c h
à
à
m c
m c
ó
ó
b
b


c l
c l


n l
n l


t l
t l
à
à
1, 1, v
1, 1, v
à
à
2
2
\

nh


ng h
ng h
à
à
m b
m b


c không (nil)
c không (nil)
u
u
V
V
í
í
d
d


: a, elephan, block l
: a, elephan, block l
à
à
c
c
á

…
, arg
, arg
n
n
)
)
u
u
Identifies the object referred to by a tuple of objects
Identifies the object referred to by a tuple of objects
u
u
May be defined implicitly through other functions, or explicitly
May be defined implicitly through other functions, or explicitly
through tables
through tables
\
\
Function names begin with a lowercase letter or are
Function names begin with a lowercase letter or are
expressed with a symbol
expressed with a symbol
u
u
F = {f, g, h,
F = {f, g, h,
…
…
} = F

: function symbols of arity 0 (constants):
a, b, max,
a, b, max,
jim
jim
u
u
F
F
1
1
: function symbols of arity 1 (one argument)
: function symbols of arity 1 (one argument)
u
u
F
F
2
2
: function symbols of arity 2 (two arguments)
: function symbols of arity 2 (two arguments)
u
u
…
…
13/
13/
69
69
Functions Examples

u
Max
Max
’
’
s age
s age
’
’
s double
s double
double(age(max))
double(age(max))
u
u
father(mother(max))
father(mother(max))
Max
Max
’
’
s mother
s mother
’
’
s father
s father
u
u
starship(son(dr_crusher))

u
youngestChild(max, ann)
youngestChild(max, ann)
Max and Ann
Max and Ann
’
’
s youngest child
s youngest child
u
u
*(5, +(2, 4))
*(5, +(2, 4))
30
30
\
\
A predicate forms a sentence,
A predicate forms a sentence,
while a function names an individual
while a function names an individual
14/
14/
69
69
H
H


ng, hay h



hai lu
hai lu


t sau :
t sau :
u
u
C
C
á
á
c h
c h


ng v
ng v
à
à
c
c
á
á
c bi
c bi



à
à
m c
m c
ó
ó
b
b


c n
c n
≥
≥
1
1
v
v
à
à
n
n


u t
u t
1
1
, , t
, , t

1
1
, , t
, , t
n
n
) c
) c


ng l
ng l
à
à
m
m


t h
t h


ng
ng
\
\
V
V
í
í

u
u
successor(X, Y), weight(b), successor(b, wight(Z))
successor(X, Y), weight(b), successor(b, wight(Z))
\
\
Nhng c
Nhng c
á
á
c h
c h
à
à
m sau đây không ph
m sau đây không ph


i l
i l
à
à
h
h


ng :
ng :
u
u

à
à
h
h


ng (v
ng (v


t
t


không l
không l
à
à
m đ
m đ


i cho h
i cho h
à
à
m)
m)
15/
15/

)
)
u
u
A (determinate) property possessed by an object: Shape, Size
A (determinate) property possessed by an object: Shape, Size
u
u
A (determinate) relationship among objects:
A (determinate) relationship among objects:
Shape relationship, size relationship, positional relationship
Shape relationship, size relationship, positional relationship
…
…
u
u
The number of arguments is called the predicate
The number of arguments is called the predicate
’
’
s arity
s arity
u
u
The order of the arguments is important
The order of the arguments is important
\
\
Predicates have names beginning with an uppercase letter
Predicates have names beginning with an uppercase letter

P
P

0
0

: predicate symbols of arity 0 (constants: proposition) : P, Q,
: predicate symbols of arity 0 (constants: proposition) : P, Q,
R,
R,
…
…
P
P

1
1

: predicate symbols of arity 1 (one argument)
: predicate symbols of arity 1 (one argument)
P
P

2
2

: predicate symbols of arity 2 (two arguments)
: predicate symbols of arity 2 (two arguments)
…
…

nh t


hai lu
hai lu


t sau :
t sau :
u
u
C
C
á
á
c m
c m


nh đ
nh đ


(v
(v


t
t



t v
t v


t
t


b
b


c n (n
c n (n
≥
≥
1)
1)
v
v
à
à
n
n


u t
u t
1

1
, , t
, , t
n
n
) c
) c


ng l
ng l
à
à
m
m


t nguyên t
t nguyên t


\
\
V
V
í
í
d
d


P(X, blue), EMPTY, BETWEEN(table, X, sill(window))
\
\
Còn :
Còn :
u
u
successor (X, Y, sill (window)
successor (X, Y, sill (window)
không ph
không ph


i nguyên t
i nguyên t


, m
, m
à
à
l
l
à
à
c
c
á
á
c h

argument
s
s
\
\
Example:
Example:
u
u
Max is tall
Max is tall
TALL(max)
TALL(max)
u
u
A is larger than B
A is larger than B
LARGER(A, B)
LARGER(A, B)
u
u
B is not larger than A
B is not larger than A
¬
¬
LARGER(B, A)
LARGER(B, A)
u
u
C is smaller than D, or D is not smaller than C


nh
nh
\
\
C
C
á
á
c công th
c công th


c ch
c ch


nh (C
nh (C
TC)
TC)
đ
đ


c t
c t


o th

á
c CTC
c CTC
u
u
N
N


u G v
u G v
à
à
H l
H l
à
à
c
c
á
á
c CTC,
c CTC,
th
th
ì
ì
(
(
¬

à
c
c
á
á
c CTC đ
c CTC đ


c t
c t


o th
o th
à
à
nh t
nh t


G v
G v
à
à
H
H
u
u
N

th
ì
ì
(
(
∃
∃
X)G v
X)G v
à
à
(
(
∀
∀
X)G c
X)G c


ng l
ng l
à
à
c
c
á
á
c CTC
c CTC
\


i bi
i bi


n X sao cho G đ
n X sao cho G đ


c tho
c tho


mãn
mãn
\
\
(
(
∀
∀
X)G
X)G
đ
đ


c đ
c đ


u đ


c tho
c tho


mãn
mãn
19/
19/
69
69
B
B
à
à
i t
i t


p
p



l
l




i đ
i đ


c ph
c ph
é
é
p l
p l
á
á
i xe
i xe
\
\
G
G
á
á
i đ
i đ


18 tu
18 tu


i, trai 20 tu


m tra h
m tra h


s
s
u
u
Nh
Nh


p h
p h


c t
c t


i c
i c
á
á
c tr
c tr


ng H


d

?
1.

Xác đnh không gian các s

kin,
nhân vt tht liên quan
2.

Tìm các hng, bin, hàm và/hoc v

t
tng ng vi các phát biu
3.

Gán ngha cho tng thành phn đ

kim tra tính đúng đn
4.

Nhn kt qu
20/
20/
69
69
Well
Well


B
B
A
A
∨
∨

B
B
A
A
→
→

B
B
A
A
↔
↔

B
B
\
\
B is a cube or B is large (a large cube):
B is a cube or B is large (a large cube):
CUBE(B)
CUBE(B)

A and B are identical
A and B are identical
u
u
Usually, written in infix form A = B
Usually, written in infix form A = B
u
u
The equality symbol
The equality symbol
“
“
=
=
“
“
is an (in
is an (in
-
-
fix) shorthand
fix) shorthand
u
u
FATHER(jane) = jim,
FATHER(jane) = jim,
or
or
=(FATHER(jane), jim)
=(FATHER(jane), jim)

≠
≠
E
E
E is not identical to iteself
E is not identical to iteself
22/
22/
69
69
V
V
í
í

d
d


\
\
C
C
á
á
c công th
c công th


c sau đây l

u
((
((
¬
¬
(P(a)
(P(a)
→
→
P(b)))
P(b)))
→
→
¬
¬
P(b))
P(b))
\
\
Còn c
Còn c
á
á
c công th
c công th


c sau đây không ch
c sau đây không ch


à
m,
m,
u
u
f (P(a))
f (P(a))
: h
: h
à
à
m c
m c
ó
ó
đ
đ


i l
i l
à
à
m
m


t v
t v



t tr
t tr


c ki
c ki


n (literal) hay tr
n (literal) hay tr


đ
đ
ú
ú
ng n
ng n


u n
u n
ó
ó
l
l
à
à
m


t nguyên t
t nguyên t


u
u
Trong m
Trong m


t CTC,
t CTC,
tr
tr


c ho
c ho


c sau c
c sau c
á
á
c ký t
c ký t


n

n, c
á
á
c h
c h
à
à
m, c
m, c
á
á
c v
c v


t
t


, n
, n
g
g


i ta c
i ta c
ó
ó
th

69
C
C
á
á
c b
c b


c xây d
c xây d


ng CTC
ng CTC
\
\
Cho m
Cho m


t ph
t ph
á
á
t bi
t bi


u (s

H
à
à
T
T


nh
nh
\
\
X
X
á
á
c đ
c đ


nh c
nh c
á
á
c mi
c mi


n đ
n đ


D1
u
u
Quê : H
Quê : H
à
à
T
T


nh, H
nh, H
à
à
Tây, H
Tây, H
à
à
Giang
Giang
…
…
Y
Y
∈
∈
D2
D2
\

c m


nh đ
nh đ


u
u
Cu Tý quê H
Cu Tý quê H
à
à
T
T


nh : QUÊ(cutý, h
nh : QUÊ(cutý, h
à
à
t
t


nh), QUÊ(X, Y)
nh), QUÊ(X, Y)
u
u
Cu Tý xa quê H


nh :
nh :
NH
NH


QUÊ(cutý, h
QUÊ(cutý, h
à
à
t
t


nh), NH
nh), NH


QUÊ(X, Y)
QUÊ(X, Y)
\
\
Xây d
Xây d


ng CTC
ng CTC
u

69
Predicate Logics: some terminology
Predicate Logics: some terminology
\
\
There is a predicate logic for each basis
There is a predicate logic for each basis
B=
B=
(
(
F, P
F, P
)
)
of function and predicate symbols
of function and predicate symbols
\
\
Terms formed on basis B are called
Terms formed on basis B are called
B
B
-
-
terms
terms
:
:
the set of all B

B
\
\
Formulas with all variables bound to a quantifier
Formulas with all variables bound to a quantifier
are called
are called
closed formulas
closed formulas
\
\
Formulas with no quantifier
Formulas with no quantifier
are called
are called
quantifier free formulas
quantifier free formulas
\
\
Formulas with no quantifier and no variable
Formulas with no quantifier and no variable
are called
are called
ground formulas
ground formulas
25/
25/
69
69
M



ng, trong m
ng, trong m


t CTC :
t CTC :
u
u
M
M


t bi
t bi


n đ
n đ


c l
c l


ng t
ng t



m vi l
m vi l


ng t
ng t


h
h
ó
ó
a c
a c


a bi
a bi


n k
n k


t
t


v
v

c
c
ó
ó
c
c
á
á
c bi
c bi


n t
n t


do (free variable),
do (free variable),
l
l
à
à
c
c
á
á
c bi
c bi



à
à
(
(
∃
∃
Y) Q(X, Y) c
Y) Q(X, Y) c
ó
ó
ch
ch


a bi
a bi


n t
n t


do X
do X
\
\
Logic v
Logic v



(first
(first
−
−
order) :
order) :
u
u
Trong CTC không đ
Trong CTC không đ


nh ngh
nh ngh


a l
a l


ng t
ng t


cho v
cho v


t
t

f) (
f) (
∀
∀
f) (
f) (
∀
∀
X) P(f (X), b)
X) P(f (X), b)
không ph
không ph


i l
i l
à
à
nh
nh


ng v
ng v


t
t

