Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang

Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ Thông tin và Truyền thông
Năm học 2012-2013
Nội dung môn học:
 Giới thiệu về Trí tuệ nhân tạo
 Tác tử
 Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc
 Logic và suy diễn
 Biểu diễn tri thức
 Biểu diễn tri thức không chắc chắn

Họcmáy

Học

máy
2
Trí tuệ nhân tạo
Giới thiệu
v
ề lo
g
ic
g
 Logic là ngôn ngữ hình thức cho phép (giúp) biểudiễn thông
t
in
dướ

 Cú pháp (syntax): để xác định các mệnh đề (sentences)
trong
một
ngôn
ngữ
trong
một
ngôn
ngữ
 Ngữ nghĩa (semantics): để xác định “ý nghĩa" củacácmệnh
đề trong một ngôn ngữ
ắ
ề
 Tứclà, xácđịnh sựđúng đ
ắ
ncủamộtmệnh đ
ề
 Ví dụ: Trong ngôn ngữ của toán học

(x+2
≥
y)
là
một
mệnh
đề
;(
x+y
>
{})

đề
 (x+2 ≥ y) là đúng nếuvàchỉ nếugiátrị (x+2) không nhỏ hơngiátrị y
 (x+2 ≥ y) là đúng khi x = 7, y = 1

(x+2
≥
y)
là
sai
khi
x
=
0y
=
6

(x+2

≥

y)

là
sai
khi
x

0
,
y

suy
diễ
n c
h
o p
hé
p c
hứ
ng m
i
n
h

(
suy
l
u
ậ
n ra
)
c
á
c
biểu thức
 Ví dụ: Luật suy diễn any plus zero Ⱶ any
ề ầ
 Một định lý (theorem) là một mệnh đ
ề
logic c
ầ

ụ
 I(one) nghĩa là 1 (∈ N)
 I(two) nghĩa là 2 (∈ N)
 I(
p
lu
s
) nghĩa là phép cộng + : N x N → N
 I(equal) nghĩa là phép so sánh bằng = : N x N → {true, false}
 I(one plus one equal two) nghĩa là true
 Nếu diễn giải của một biểu thức là đúng (true), chúng ta
nói rằng phép diễn giải này là một mô hình (model) của
biểuthức
biểu

thức
 Một biểu thức đúng đối với bất kỳ phép diễn giải nào thì
được gọi là một biểu thức đúng đắn (valid)
 Ví dụ: A OR NOT
A
5
Trí tuệ nhân tạo
T
ính bao hàm
 Tính bao hàm có nghĩalàmột cái gì đó tuân theo (bị hàm
chứa
ý
n
g
hĩabởi


cơ
sở
tri

thức
KB
bao
hàm
(
hàm
chứa
)

mệnh
đề
α

nếuvàchỉ nếu α là đúng trong mọimôhình(thế giới)
mà trong đó KB là đúng – Tứclà: nếu KB đúng, thì α
cũn
g
p
hải đún
g
g
p
g
 Ví dụ: Nếu mộtcơ sở tri thức KB chứacácmệnh đề “Đội bóng A
đãthắng” và “Đội bóng B đãthắng”, thì KB bao hàm mệnh đề


4)

bao
hàm
mệnh
đề
(4

=

x+y
)
 Tính bao hàm là mối quan hệ giữacácmệnh đề dựatrên
ngữ nghĩa
6
Trí tuệ nhân tạo
Các mô hình
 Các nhà logic học thường hay xem
xét các sự việc theo các mô hình
(models)
(models)
 Các mô hình là các không gian (thế
giới) có cấu trúc, mà trong các không
gian đó tính đúng đắn(củacácsự
gian

đó

tính


m
 M(α) là tập hợp tất cả các mô hình
của α
 KB╞ α nếu và chỉ nếu M(KB) ⊆ M(α)
 Ví dụ: KB = “Đội bóng A đã thắng và
đội bóng B đã thắng”, α = “Đội bóng
A đãthắng
”
A

đã

thắng
7
Trí tuệ nhân tạo
Suy diễn lo
g
ic (1)
g
 KB ├
i
α

Mệnh
đề
α
được
suy
ra

 Tính đúng đắn (soundness)
 Một thủ tục suy diễn i đượcgọilàđúng đắn (sound), nếuthủ tục
i
hỉ
á
ệ h
đề
đ
b
hà
(tild t )
i
suy ra c
hỉ
c
á
cm
ệ
n
h
đề
đ
ược
b
ao
hà
m
(
en
t

hỉ h
(lt)
ế

Một

thủ
t
ụcsuy
diễ
n
i
đ
ượcgọ
i
là
h
o
à
nc
hỉ
n
h
(
comp
l
e
t
e
)

nc
hỉ
n
h
, n
ế
u
bất
c
ứ
khi
n
à
o
KB
╞
α,
thì
c
ũ
ng
đú
ng
đốivới KB ├
i
α

(
Trong
phần

hoàn chỉnh
9
Trí tuệ nhân tạo
Suy diễn lo
g
ic (3)
g
 Logic là một cách để biểu diễn hình thức và suy diễn tự
động
động
 Việc suy diễn (reasoning) có thể được thực hiện ở mức
cú pháp (bằng các chứng minh):
suy diễndiễndịch
cú

pháp

(bằng

các

chứng

minh):

suy

diễn

diễn

 Với một biểu thức và một phép diễn giải, kiểm tra xem
phép diễn giải có phải là một mô hình của biểu thức
khôn
g
?: ki
ể
m tra mô hình
(
model checkin
g)
g
(g)
 Suy diễn ngữ nghĩa ở mức của tất cả các phép diễn giải
có thể: kiểm tra tính đúng đắn (validity checking)
 Logics that are sound (correct) and complete:
provability corresponds to validity
11
Trí tuệ nhân tạo
Lo
g
ic định đề
–
Cú
p
há
p
(1)
g
pp
 Logic định đề (propositional logic) là loại logic đơn giản


biể
u
thứ
c
(đị
n
h

đề)
 Các giá trị hằng logic đúng (true) và sai (false) là các biểu
thức
 Nếu S
1
là một biểu thức, thì (¬S
1
) cũng là một biểu thức
(Phép phủ định)
12
Trí tuệ nhân tạo
Lo
g
ic định đề
–
Cú
p
há
p
(2)
g

S
2
)
c
ũ
ng
là
m
ột

biểu thức (Phép kết hợp / và)
 Nếu S
1
và S
2
là các biểu thức, thì
(
S
1
∨ S
2
)
cũn
g
là m
ộ
t
1
2
(


theo
)
 Nếu S
1
và S
2
là các biểu thức, thì (S
1
⇔ S
2
) cũng là một
biểu thức (Phép tương đương)
 Không gì khác (các dạng trên) là một biểu thức
13
Trí tuệ nhân tạo
Cú
p
há
p
của lo
g
ic định đề
–
Ví dụ
pp
g
 p
 q
 r

r))

⇔
(p

∧
q)
∨
(p

∧
r)
14
Trí tuệ nhân tạo
T
hứ
t
ựưu tiên của các toán
t
ử lo
g
ic
g
 Thứ tự ưu tiên của các toán tử logic (từ cao xuống thấp)
 ¬, ∧, ∨, ⇒, ⇔
 Sử dụng cặp ký tự “()” để xác định mức độ ưu tiên
Các ví dụ

Các


(
¬
p)

∧
q

chứ

không

phải

¬
(p

∧
q)
 p ∧¬q ⇒ r tương đương (p ∧ (¬q)) ⇒ r – chứ không phải
p ∧ (¬(q ⇒ r)) hoặc p ∧ ((¬q) ⇒ r)
15
Trí tuệ nhân tạo
Lo
g
ic định đề
–
N
g
ữ n
g

i
S
đú
S
i
)
m
1
≡
(S
1
=sa
i
,
S
2
=
đú
ng,
S
3
=sa
i
)
 Với 3 ký hiệu định đề như ví dụ trên, có thể chỉ ra 8 mô
hình
có
thể
hình
có

g
mô hình
g
ị
ý( g
)
ệ
g
m đó
¬S
1
là đúng, khi và chỉ khi S
1
là sai
S
∧
S
là
đúng
khi
và
chỉ
khi
S
là
đúng
và
S
là
đúng

là đúng
S
1
⇒ S
2
là đúng, khi và chỉ khi S
1
là sai hoặcS
2
là đúng
là sai, khi và ch
ỉ
khi S
1
là đúng và S
2
là sai
S
1
⇔ S
2
là đúng, khi và chỉ khi S
1
⇒S
2
là đúng và S
2
⇒S
1
là đúng

d
ụ tr
ê
n, t
hì
g
iá
tr
ị
c
ủ
a
biểuthức logic định đề sau sẽ là:
¬S
1
∧ (S
2
∨ S
3
) = đúng ∧ (đúng ∨ sai) = đúng ∧ đúng = đúng
17
Trí tuệ nhân tạo
Ngữ nghĩa của logic định đề – Ví dụ (1)
 Xét mô hình m
1
≡
(p=đúng, q=sai), ta có ngữ nghĩa (giá
tr
ị
lo

 ¬p ⇔ q là đúng
18
Trí tuệ nhân tạo
Ngữ nghĩa của logic định đề – Ví dụ (2)
 Xét mô hình m
2
≡
(p=sai, q=đúng), ta có ngữ nghĩa (giá
tr
ị
lo
g
ic
)
của các biểu thức sau
ị g)
 ¬p là đúng
 ¬q là sai
 p ∧ q là sai
 p ∨ q là đúng
p
⇒
qlà
đúng

p

⇒
q


S
S
VS
S
⇒
S
S
⇔
S
S
1
S
2
¬
S
1
S
1
Λ
S
2
S
1
VS
2
S
1
⇒
S
2

cùn
g
mô hình: α ≡ ß khi và chỉ
ệ y ggg
khi α╞ β và β╞ α
21
Trí tuệ nhân tạo
Biểu diễn bằn
g
lo
g
ic định đề
–
Ví dụ
gg
 Giả sử chúng ta có các định đề sau

p
≡
“
Chiều nay
trời
nắng
”

p

≡
Chiều


trong
ngôn
ngữ
tự
nhiên

Biểu
diễn
các
phát
biểu
trong
ngôn
ngữ
tự
nhiên
 “Chiều nay trời không nắng và thờitiếtlạnh hơn hôm qua”: ¬p ∧ q
 “Tôi sẽđibơi nếunhư chiều nay trờinắng”: p → r
“
Nế
tôi
(
ẽ
)
khô
đi
b i
thì
tôi
ẽ

:
¬
r → s
 “Nếutôi(sẽ) đi đá bóng thì tôi sẽ về nhà vào buốitối”: s → t
22
Trí tuệ nhân tạo
Mâu thuẫn và Tautolo
gy
g
 Một biểuthức logic định đề luôn có giá trị sai (false) trong
mọi
phép
diễn
giải
(
mọi
mô
hình
)
thì
được
gọi
là
một
mọi
phép
diễn
giải
(
mọi

∨
q)
¬
(p

∧
q)

↔
(
¬
p

∨
¬
q)
¬(p ∨ q) ↔ (¬p ∧¬q)
23
Trí tuệ nhân tạo
Tính thỏa mãn được và Tính đúng đắn
 Một biểuthức logic định đề là thỏamãnđược
(
satisfiable
)
,
nếubiểuthức đó đún
g
tron
g
m

thỏ
am
ã
n
đ
ược
(unsatisfiable), nếu không tồntạibấtkỳ mô hình nào mà
trong đóbiểuthứclàđúng
Ví
d
A
A

Ví

d
ụ:
A
∧¬
A
 Một biểuthứclàđúng đắn (valid), nếubiểuthức đúng
trong
mọi
mô
hình
trong
mọi
mô
hình
 Ví dụ: đúng; A ∨¬A; A ⇒ A; (A ∧ (A ⇒ B)) ⇒ B

một
định
lý)
 Cơ sở tri thức KB có bao hàm (về mặtngữ nghĩa)
α
hay
khôn
g
: KB
╞

α
?
g
╞
 Nói cách khác,
α
có thểđượcsuyra(đượcchứng minh) từ cơ sở
tri thức KB hay không?
Câ
hỏi
đặt
ra
Liệ
có
tồn
tại
một
thủ
t c

số hữu hạncácbước?
ố
ề

Đố
ivới logic định đ
ề
, câu trả lờilàcó!
25
Trí tuệ nhân tạo