Bài giảng Trí tuệ nhân tạo - Bài 6: Logic và suy diễn

Trí Tuệ Nhân Tạo

(Artificial Intelligence)

Thân Quang Khoát

khoattq@soict.hust.edu.vn

Viện Công nghệ thông tin và Truyền thông

Trường Đại Học Bách Khoa Hà Nội

Năm 2020

Nội dung môn học:

n Giới thiệu về Trí tuệ nhân tạo

n Tác tử

n Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc

n Logic và suy diễn

n Biểu diễn tri thức

n Biểu diễn tri thức không chắc chắn

n Học máy

Trí tuệ nhân tạo

2

Giới thiệu về logic

n Logic là ngôn ngữ hình thức cho phép (giúp) biểu diễn thông

tin dưới dạng các kết luận có thể được đưa ra

q Logic = Syntax + Semantics

n Cú pháp (syntax): để xác định các mệnh đề (sentences)

trong một ngôn ngữ.

n Ngữ nghĩa (semantics): để xác định “ý nghĩa" của các mệnh

đề trong một ngôn ngữ

q Tức là, xác định sự đúng đắn của một mệnh đề

n Ví dụ: Trong ngôn ngữ của toán học

q (x+2 ≥ y) là một mệnh đề; (x+y > {}) không phải là một mệnh đề

q (x+2 ≥ y) là đúng nếu và chỉ nếu giá trị (x+2) không nhỏ hơn giá trị y

q (x+2 ≥ y) là đúng khi x = 7, y = 1

q (x+2 ≥ y) là sai khi x = 0, y = 6

Trí tuệ nhân tạo

3

Cú pháp (syntax)

n Cú pháp = Ngôn ngữ + Lý thuyết chứng minh

n Ngôn ngữ (Language)

q Các ký hiệu (symbols), biểu thức (expressions), thuật ngữ (terms),

công thức (formulas) hợp lệ

q Ví dụ: one plus one equal two

n Lý thuyết chứng minh (Proof theory)

q Tập hơp các luật suy diễn cho phép chứng minh (suy luận ra) các

biểu thức

q Ví dụ: Luật suy diễn any plus zero Ⱶ any

n Một định lý (theorem) là một mệnh đề logic cần chứng minh

n Việc chứng minh một định lý không cần phải xác định ngữ nghĩa

(interpretation) của các ký hiệu!

Trí tuệ nhân tạo

4

Ngữ nghĩa (semantics)

n Ngữ nghĩa = Ý nghĩa (diễn giải) của các ký hiệu

n Ví dụ

q I(one) nghĩa là 1 (Î N)

q I(two) nghĩa là 2 (Î N)

q I(plus) nghĩa là phép cộng + : N x N ® N

q I(equal) nghĩa là phép so sánh bằng = : N x N ® {true, false}

q I(one plus one equal two) nghĩa là true

n 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ểu thức

n 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)

q Ví dụ: A OR NOT A

Trí tuệ nhân tạo

5

Tính bao hàm

n Tính bao hàm có nghĩa là một cái gì đó tuân theo (bị hàm

chứa ý nghĩa bởi, được suy ra từ) một cái gì khác:

KB ╞ α

n Một cơ sở tri thức KB bao hàm (hàm chứa) mệnh đề α

nếu và chỉ nếu α là đúng trong mọi mô hình (thế giới)

mà trong đó KB là đúng. Tức là: nếu KB đúng, thì α cũng

phải đúng

q Ví dụ: Nếu một cơ sở tri thức KB chứa các mệnh đề “Đội bóng

A đã thắng” và “Đội bóng B đã thắng”, thì KB bao hàm mệnh đề

“Đội bóng A hoặc đội bóng B đã thắng”

q Ví dụ: Mệnh đề (x+y = 4) bao hàm mệnh đề (4 = x+y)

Trí tuệ nhân tạo

6

Các mô hình

n Các nhà logic học thường hay xem

xét các sự việc theo các mô hình

(models)

n 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ủa các sự

việc) có thể đánh giá được

n Định nghĩa: m là một mô hình của

mệnh đề α nếu α là đúng trong m

n M(α) là tập hợp tất cả các mô hình

của α

n KB╞ α nếu và chỉ nếu M(KB) Í M(α)

q Ví dụ: KB = “Đội bóng A đã thắng và

đội bóng B đã thắng”, α = “Đội bóng

A đã thắng”

Trí tuệ nhân tạo

7

Suy diễn logic (1)

n KB ├_iα

q Mệnh đề α được suy ra từ KB bằng cách áp dụng thủ tục (suy

diễn) i

q (Nói cách khác) Thủ tục i suy ra mệnh đề α từ KB

n Tính đúng đắn (soundness)

q Một thủ tục suy diễn i được gọi là đúng đắn (sound), nếu thủ tục

i suy ra chỉ các mệnh đề được bao hàm (entailed sentences)

q Thủ tục i là đúng đắn, nếu bất cứ khi nào KB ├_iα, thì cũng đúng

đối với KB╞ α

q Nếu thủ tục i suy ra mệnh đề α, mà α không được bao hàm trong

KB, thì thủ tục i là không đúng đắn (unsound)

Trí tuệ nhân tạo

8

Suy diễn logic (2)

n Tính hoàn chỉnh (completeness)

q Một thủ tục suy diễn i được gọi là hoàn chỉnh (complete), nếu

thủ tục i có thể suy ra mọi mệnh đề được bao hàm (entailed

sentences)

q Thủ tục i là hoàn chỉnh, nếu bất cứ khi nào KB╞ α, thì cũng đúng

đối với KB ├_iα

n (Trong phần tiếp theo của bài giảng) chúng ta sẽ xét đến

logic vị từ bậc 1 (first-order logic)

q Có khả năng biểu diễn (diễn đạt) hầu hết các phát biểu logic

q Với logic vị từ bậc 1, tồn tại một thủ tục suy diễn đúng đắn và

hoàn chỉnh

Trí tuệ nhân tạo

9

Suy diễn logic (3)

n Logic là một cách để biểu diễn hình thức và suy diễn tự

động

n 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ễn diễn dịch

(deductive reasoning)

n Việc suy diễn có thể được thực hiện ở mức ngữ nghĩa

(bằng các mô hình): suy diễn dựa trên mô hình

(model-based reasoning)

Trí tuệ nhân tạo

10

Suy diễn logic (4)

n Suy diễn ngữ nghĩa ở mức của một phép diễn giải (mô

hình):

q

Với một biểu thức, có tồn tại một mô hình không?

có thể thỏa mãn được (satisfiability)?

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ông?: kiểm tra mô hình (model checking)

n 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)

Trí tuệ nhân tạo

11

Logic định đề: Cú pháp (1)

n Logic định đề (propositional logic) là loại logic đơn giản

nhất

n Biểu thức định đề (propositional formula)

q Một ký hiệu định đề (S₁, S₂, …) là một biểu thức (định đề)

q Các giá trị hằng logic đúng (true) và sai (false) là các biểu

thức

q Nếu S₁là một biểu thức, thì (¬S₁) cũng là một biểu thức

(Phép phủ định)

Trí tuệ nhân tạo

12

Logic định đề: Cú pháp (2)

n Biểu thức định đề (propositional formula)…

q Nếu S₁và S₂là các biểu thức, thì (S₁Ù S₂) cũng là một

biểu thức (Phép kết hợp / và)

q Nếu S₁và S₂là các biểu thức, thì (S₁Ú S₂) cũng là một

biểu thức (Phép tuyển / hoặc)

q Nếu S₁và S₂là các biểu thức, thì (S₁Þ S₂) cũng là một

biểu thức (Phép suy ra / kéo theo)

q Nếu S₁và S₂là các biểu thức, thì (S₁Û S₂) cũng là một

biểu thức (Phép tương đương)

q Không gì khác (các dạng trên) là một biểu thức

Trí tuệ nhân tạo

13

Cú pháp của logic định đề: Ví dụ

n p

n q

n r

n true

n false

n ¬p

n (¬p) Ù true

n ¬((¬p) Ú false)

n (¬p) Þ (¬((¬p) Ú false))

n (p Ù (q Ú r)) Û (p Ù q) Ú (p Ù r)

Trí tuệ nhân tạo

14

Thứ tự ưu tiên của các toán tử logic

n Thứ tự ưu tiên của các toán tử logic (từ cao xuống thấp)

q ¬, Ù, Ú, Þ, Û

n Sử dụng cặp ký tự “()” để xác định mức độ ưu tiên

n Các ví dụ

q p Ù q Ú r tương đương (p Ù q) Ú r

chứ không phải p Ù (q Ú r)

q ¬p Ù q tương đương (¬p) Ù q

chứ không phải ¬(p Ù q)

q p Ù ¬q Þ r tương đương (p Ù (¬q)) Þ r

chứ không phải p Ù (¬(q Þ r)) hoặc p Ù ((¬q) Þ r)

Trí tuệ nhân tạo

15

Logic định đề: Ngữ nghĩa (1)

n Với một mô hình (model) cụ thể, nó sẽ xác định giá trị

đúng/sai cho mỗi ký hiệu định đề

q Ví dụ: Với 3 ký hiệu S₁, S₂và S₃, thì có thể lấy ví dụ một mô hình

m₁xác định như sau:

m₁º (S₁=sai, S₂=đúng, S₃=sai)

n Với 3 ký hiệu định đề như ví dụ trên, có thể chỉ ra 8 mô

hình có thể

Trí tuệ nhân tạo

16

Logic định đề: Ngữ nghĩa (2)

n Ngữ nghĩa của một mô hình m = Các quy tắc để đánh giá giá

trị chân lý (đúng/sai) của các mệnh đề trong mô hình m đó

¬S₁là đúng, khi và chỉ khi S₁là sai

S₁Ù S₂là đúng, khi và chỉ khi S₁là đúng và S₂là đúng

S₁Ú S₂là đúng, khi và chỉ khi S₁là đúng hoặc S₂là đúng

S₁Þ S₂là đúng, khi và chỉ khi S₁là sai hoặc S₂là đúng;

là sai, khi và chỉ khi S₁là đúng và S₂là sai

S₁Û S₂là đúng, khi và chỉ khi S₁ÞS₂là đúng và S₂ÞS₁là đúng

n Ví dụ: Với mô hình m₁như trong ví dụ trước, thì giá trị

của biểu thức logic định đề sau sẽ là:

¬S₁Ù (S₂Ú S₃) = đúng Ù (đúng Ú sai) = đúng Ù đúng = đúng

Trí tuệ nhân tạo

17

Ngữ nghĩa của logic định đề: Ví dụ (1)

n Xét mô hình m₁º (p=đúng, q=sai), ta có ngữ nghĩa (giá

trị logic) của các biểu thức sau

q ¬p là sai

q ¬q là đúng

q p Ù q là sai

q p Ú q là đúng

q p Þ q là sai

q q Þ p là đúng

q p Û q là sai

q ¬p Û q là đúng

Trí tuệ nhân tạo

18

Ngữ nghĩa của logic định đề: Ví dụ (2)

n Xét mô hình m₂º (p=sai, q=đúng), ta có ngữ nghĩa (giá

trị logic) của các biểu thức sau

q ¬p là đúng

q ¬q là sai

q p Ù q là sai

q p Ú q là đúng

q p Þ q là đúng

q q Þ p là sai

q p Û q là sai

q ¬p Û q là đúng

Trí tuệ nhân tạo

19

Bảng chân lý đối với các toán tử logic

¬

Þ

Û

S₁

sai sai đúng sai

sai đúng đúng sai đúng đúng sai

đúng sai sai sai đúng sai sai

S₂

S₁S₁ΛS₂S₁VS₂S₁S₂S₁S₂

sai đúng đúng

đúng đúng sai đúng đúng đúng đúng

Trí tuệ nhân tạo

20

Bài giảng Trí tuệ nhân tạo - Bài 6: Logic và suy diễn - Thân Quang Khoát