Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng

CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG

Logic THS. BÙI THỊ DANH

BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM

Nội dung chính

Tổng quan

Logic mệnh đề

Logic bậc nhất

Lịch sử phát triển

Thế kỉ 4 TCN, Aristotle phát minh logic tam đoạn luận, hệ thống suy diễn hình thức đầu tiên.

Logic là mô hình chủ đạo trong lĩnh vực trí tuệ nhân tạo trước những năm 1990s ◦ 1956, Allen Newell và Herbert Simon demo “Logic Theorist”, chương trình AI sử dụng

Allen Newell

heuristic chứng minh 38 định lí trong số 52 định lý trong cuốn “Principa Mathematica” của Whitehead và Russell.

◦ 1965, J. Alan Robinson phát minh ra phương pháp chứng minh hợp giải.

◦ 1972, Alain Colmerauer phát triển ngôn ngữ Prolog

Herbert Simon

1879, logic mệnh đề hiện đại được phát triển bởi Gottlob Frege

Lịch sử phát triển

Ngày nay, logic không còn là mô hình ưa thích do sự phát triển của xác suất và máy học

◦ Là mô hình dựa trên luật cứng nhắc; trong khi máy học có thể tự động điều chỉnh mô hình dựa vào dữ

liệu.

Các nguyên nhân: ◦ Xác định, không xử lý trường hợp không chắc chắn; trong khi mô hình xác suất thì có

Ưu điểm của logic là cung cấp sự diễn đạt ý nghĩa và súc tích

Ứng dụng: trợ lí ảo

Đưa thông tin

Đặt câu hỏi

Sử dụng ngôn ngữ tự nhiên

Sắp xếp các thông tin không đồng nhất

Lập luận với các thông tin có được

Ngôn ngữ tự nhiên

◦ Đồng 5 xu tốt hơn một xu

◦ Do đó, một hào tốt hơn một xu

Ví dụ: ◦ Một hào tốt hơn đồng 5 xu

◦ Không có gì tốt hơn hòa bình thế giới

◦ Do đó, một xu tốt hơn hòa bình thế giới ?!?

Ví dụ ◦ Một xu tốt hơn là không có gì

Ngôn ngữ logic

Là một dạng ngôn ngữ hình thức thích hợp hơn cho việc mô tả tri thức tường thuật (declarative knowledge) và dễ dàng kết nối với ngôn ngữ tự nhiên.

◦ Logic mệnh đề (propositional logic)

◦ Logic vị từ (predicate logic): logic bậc nhất

◦ …

Các loại ngôn ngữ logic:

Hai mục tiêu của logic

Biểu diễn tri thức về thế giới

Lập luận dựa trên tri thức có được

Cho máy tính

Các thành phần của hệ thống logic

Công thức (formula)

Mô hình(models)

Ngữ nghĩa (Semantic) Cú pháp (syntax)

PP suy dẫn (entailment methods)

Các thành phần của hệ thống logic

Cú pháp: định nghĩa công thức như thế nào là hợp lệ ◦ Ví dụ: Rain ∧ 𝑊𝑒𝑡

◦ Ví dụ:

Wet

Rain

Ngữ nghĩa: với mỗi công thức, ý nghĩa của nó là gì? Ngữ nghĩa xác định các mô hình (hay cấu hình của thế giới)

Luật suy diễn: cho công thức 𝑓, công thức mới 𝑔 nào có thể được thêm vào mà không thay đổi ngữ nghĩa ◦ Ví dụ: cho Rain ∧ 𝑊𝑒𝑡, có thể dẫn xuất thêm Rain.

Nội dung chính

Tổng quan

Logic mệnh đề

Logic bậc nhất

Các thành phần của hệ thống logic

Công thức (formula)

Mô hình(models)

Ngữ nghĩa (Semantic) Cú pháp (syntax)

PP suy dẫn (entailment method)

Cú pháp

Kí hiệu mệnh đề (công thức nguyên tử): A, B, C, …

Các liên kết logic: ¬, ∧, ∨, ⟶, ⟷

◦ Nối liền (conjunction): α ∧ β

◦ Nối rời (disjunction): α ∨ 𝛽

◦ Kéo theo (implication): α → 𝛽

◦ Tương đương (biconditional): α ↔ 𝛽

Nếu 𝛼 và 𝛽 là công thức thì các định nghĩa đệ qui đây cũng là công thức: ◦ Phủ định: ¬𝛼

Một số ví dụ

◦ 𝐴

◦ ¬𝐴

◦ ¬𝐵 → 𝐶

◦ ¬𝐴 ∧ ¬𝐵 → 𝐶 ∨ ¬𝐵 ∨ D

◦ ¬¬𝐴

Công thức:

◦ 𝐴¬𝐵

◦ 𝐴 + 𝐵

Không phải công thức:

Các thành phần của hệ thống logic

Công thức (formula)

Mô hình(models)

Ngữ nghĩa (Semantic) Cú pháp (syntax)

PP suy dẫn (entailment method)

Ngữ nghĩa

Mô hình (model) 𝑤 trong logic mệnh đề là một phép gán giá trị thật (True hoặc False) cho các kí hiệu mệnh đề

Ví dụ:

A

B

C

◦ Có 3 kí hiệu mệnh đề: A, B và C ◦ Có 23 = 8 mô hình tương ứng:

Ngữ nghĩa

◦ False (0) tương ứng với 𝑤 không thoả 𝛼

Trường hợp cơ sở: với mỗi kí hiệu mệnh đề 𝑝 (tức A, B, C…) thì 𝐼 𝛼, 𝑤 = w(p)

Cho một công thức 𝛼 và mô hình 𝑤, hàm phiên dịch 𝐼 𝛼, 𝑤 trả về: ◦ True (1) tương ứng với 𝑤 thoả α

𝐼(𝛼, w)

𝐼(𝛽, w)

𝐼(¬𝛼, w)

𝐼(𝛼 ∧ 𝛽, w)

𝐼(𝛼 ∨ 𝛽, w)

𝐼(𝛼 → 𝛽, w)

𝐼(𝛼 ↔ 𝛽, w)

Trường hợp đệ qui: với hai công thức 𝛼 và 𝛽 bất kì, ta có:

Ví dụ

Cho công thức: α = (¬A ∧ B) ↔ 𝐶

Và mô hình w = A: 1, B: 1, C: 0

◦ 𝐼 ¬A ∧ B, 𝑤 = 0

◦ I ¬A ∧ B ↔ 𝐶, w = 0

Hàm phiên dịch: I 𝛼, w = 1 ◦ I ¬A, 𝑤 = 0

Ngữ nghĩa

Một công thức được gọi là hợp lệ (true) khi và chỉ khi hàm phiên dịch của nó trên tất cả các mô hình đều đúng

Ví dụ: 𝑃 ∨ 𝐻 ∧ ¬𝐻 → 𝑃 là hợp lệ

𝑃 ∨ 𝐻 𝑃 ∨ 𝐻 ∧ ¬𝐻 P H 𝑃 ∨ 𝐻 ∧ ¬𝐻 → 𝑃

0 0 0 0 1

0 1 1 0 1

1 0 1 1 1

1 1 1 0 1

Ngữ nghĩa

Một công thức được gọi là thoả mãn được (satisfiable) khi và chỉ khi hàm phiên dịch của nó đúng trên ít nhất một mô hình.

Một công thức được gọi là không thoả mãn được (unsatisfiable) khi và chỉ khi hàm phiên dịch của nó không đúng trên mọi mô hình.

Ví dụ: 𝑃 ∨ 𝐻 ∧ ¬𝐻 là thoả mãn được

𝑃 ∨ 𝐻 𝑃 ∨ 𝐻 ∧ ¬𝐻 P H

0 0 0 0

0 1 1 0

1 0 1 1

1 1 1 0

Cơ sở tri thức (knowledge base)

Gọi ℳ(𝛼) là tập các mô hình 𝑤 mà I 𝛼, w = 1

Một cơ sở tri thức KB được định nghĩa như là sự nối liền/giao của các công thức:

ℳ(𝛼)

ℳ KB = ሩ 𝛼∈KB

Ví dụ: Cho KB = {Rain ∨ Snow, Traffic}

Ví dụ

Nối liền/ giao

Tính thoả mãn được (Satisfiability)

Một cơ sở tri thức KB được gọi là thoả mãn được nếu 𝓜 𝑲𝑩 ≠ ∅

◦ Biến: kí hiệu mệnh đề. Miền giá trị {0, 1}

◦ Ràng buộc: các công thức

◦ Phép gán: mô hình

Các thuật toán phổ biến:

◦ DPLL (kĩ thuật quay lui + tỉa nhánh)

◦ Walksat (tìm kiếm cục bộ ngẫu nhiên)

◦ …

Kiểm tra tính thoả mãn (SAT Problem) trong logic mệnh đề là một trường hợp được biệt của CSP, cụ thể

SAT được chứng minh là bài toán NP-khó

Ví dụ

Cho KB = {A ∨ B, B ⟷ ¬C}. Cho biết KB có tính thoả mãn được hay không?

Trả lời:

Biến CSP: A, B và C

Đồ thị ràng buộc:

 KB có tính thoả mãn được.

Tìm được một phép gán thoả các ràng buộc: {A: 1, B: 0, C: 1}

Các thành phần của hệ thống logic

Công thức (formula)

Mô hình(models)

Ngữ nghĩa (Semantic) Cú pháp (syntax)

PP suy dẫn (entailment method)

Sự suy dẫn (entailment)

KB suy dẫn 𝛼, được viết là 𝑲𝑩 ⊨ 𝜶, khi và chỉ khi 𝓜 𝑲𝑩 ⊆ 𝓜 𝜶 ◦ 𝛼 không thêm thông tin hay ràng buộc vào KB

Ví dụ: Rain ∧ Snow ⊨ Snow

Sự mâu thuẫn (contradiction)

KB mâu thuẫn với 𝛼 khi và chỉ khi 𝓜 𝑲𝑩 ∩ 𝓜 𝜶 = ∅ ◦ 𝛼 mâu thuẫn với những điều mà ta đã biết

Ví dụ: Rain ∧ Snow mâu thuẫn với ¬Snow

 KB mâu thuẫn với f khi và chỉ khi KB suy dẫn ra ¬f

Các phương pháp suy dẫn KB ⊨ 𝛼

Lập bảng chân trị (hay phương pháp liệt kê)

Luật suy diễn

Lập bảng chân trị (hay liệt kê)

◦ Liệt kê tất cả các mô hình

◦ Chọn các mô hình làm cho KB là đúng.

◦ Kiểm tra xem 𝛼 có đúng với tất cả các mô hình này không?

Ý tưởng:

Độ phức tạp: với N kí hiệu mệnh đề ◦ Độ phức tạp tính toán: O 2𝑁 ◦ Độ phức tạp lưu trữ: O N

Không hiệu quả

Lập bảng chân trị (liệt kê)

Luật suy diễn

Luật suy diễn là các mẫu hình thức mô tả một tri thức mới có thể được dẫn xuất từ tri thức đang có như thế nào ◦ Công thức 𝛼 được suy diễn từ KB, kí hiệu là 𝑲𝑩 ⊢ 𝜶

Tiền đề/Giả thuyết 𝛼, 𝛼 → 𝛽 𝛼, 𝛽 𝛼 ∧ 𝛽 𝛼 ¬¬𝛼 𝛼 ∨ 𝛽, ¬𝛽 𝛼 ∨ 𝛽, ¬𝛽 ∨ 𝛾

Kết luận 𝛽 𝛼 ∧ 𝛽 𝛼 𝛼 ∨ 𝛾 𝛼 𝛼 𝛼 ∨ 𝛾

Luật suy diễn Modus Ponens And - Introduction And - Elimination Or - Introduction Double Negation Unit Resolution Resolution

Ví dụ

Suy diễn 𝑺 từ KB như bên dưới

Bước Nguồn gốc

Công thức 𝑃 ∧ 𝑄 KB 𝑃 ∧ 𝑄 1 Cho trước

𝑃 → 𝑅 𝑃 → 𝑅 2 Cho trước

𝑄 ∧ 𝑅 → 𝑆

𝑄 ∧ 𝑅 → 𝑆 𝑃 3 4 Cho trước 1 And-Elim

𝑅 5 4,2 Modus Ponens

𝑄 𝑄 ∧ 𝑅 6 7 1 And-Elim 5,6 And-Intro

𝑆 8 3,7 Modus Ponens

Luật suy diễn

Một tập luật suy diễn được gọi là đúng (sound) nếu:

𝜶: 𝑲𝑩 ⊢ 𝜶 ⊆ 𝜶: 𝑲𝑩 ⊨ 𝜶

𝜶: 𝑲𝑩 ⊢ 𝜶 ⊇ 𝜶: 𝑲𝑩 ⊨ 𝜶

Một tập luật suy diễn được gọi là đầy đủ (complete) nếu:

Luật suy diễn

Rain,Rain→Wet Wet

Cho biết có đủ không?

KB ⊢ {Wet} KB ⊨ {Rain, Wet}

Luật suy diễn

Nhiều tập luật suy diễn đúng nhưng không đủ.

}

◦ Xét luật suy diễn {

𝛼,𝛼→𝛽 𝛽

◦ Về mặt ngữ nghĩa: KB ⊨ 𝛼

◦ Về mặt cú pháp: KB ⊬ 𝛼

Ví dụ: cho KB = Rain, Rain ∨ Snow → Wet và 𝛼 = Wet

 Luật suy diễn tương ứng không đầy đủ

Giải pháp cho tính đầy đủ

◦ Luật hợp giải với công thức ở dạng CNF

Giải pháp 1: Sử dụng các luật suy diễn mạnh.

Giải pháp 2: Giới hạn tập công thức được phép sử dụng. ◦ Logic mệnh đề bao gồm các mệnh đề dạng Horn

KB ở dạng CNF (Conjunctive Normal Form)

Môt literal hoặc là một công thức nguyên tử (postive literal) hoặc phủ định của công thức nguyên tử (negative literal)

Một clause (mệnh đề) là một literal hoặc nối rời của hai hoặc nhiều literal

Ví dụ: A, ¬𝐴, …

Một công thức 𝛼 được gọi là ở dạng CNF nếu nó là nối liền của các clause

Ví dụ: A ∨ ¬B ∨ 𝐶

Ví dụ: A ∨ B ∧ C ∨ ¬D ∨ E ∧ ¬E ∨ F

KB ở dạng CNF (Conjunctive Normal Form)

Với mỗi công thức 𝛼 của logic mệnh đề, tồn tại một công thức A ở dạng CNF sao cho α và A tương đương logic

Các CNF được dùng trong lập trình logic (Prolog)

Tồn tại một thuật toán đa thức để chuyển α sang A

Chuyển đổi công thức sang dạng CNF

◦ Chuyển 𝒑 ↔ 𝒒 thành 𝒑 → 𝒒 ∧ 𝒒 → 𝒑

Sử dụng De Morgan để chuyển phép phủ định vào trong ◦ Chuyển ¬ 𝒑 ∧ 𝒒 thành ¬𝒑 ∨ ¬𝒒

◦ Chuyển ¬ 𝒑 ∨ 𝒒 thành ¬𝒑 ∧ ¬𝒒

Phân phối phép nối rời (OR) vào nối liền (AND) ◦ Chuyển 𝒑 ∨ (𝒒 ∧ 𝒓) thành 𝒑 ∨ 𝒒 ∧ 𝒑 ∨ 𝒓

Loại bỏ phép kéo theo và tương đương ◦ Chuyển 𝒑 → 𝒒 thành ¬𝒑 ∨ 𝒒

Ví dụ

Chuyển công thức 𝑨 ⟷ 𝑩 ∧ 𝑪 về dạng CNF?

◦ Tương đương 𝐴 → B ∧ C ∧ B ∧ C → 𝐴

◦ Tương đương ¬𝐴 ∨ B ∧ C ∧ ¬ B ∧ C ∨ 𝐴

◦ Tương đương ¬A ∨ 𝐵 ∧ ¬𝐴 ∨ 𝐶 ∧ ¬B ∨ ¬𝐶 ∨ 𝐴

Lời giải:

Hợp giải cho CNF

Nếu A hoặc B hoặc C là đúng, nhưng A không đúng thì B hoặc C phải đúng

(A ∨ B ∨ 𝐶) (¬𝐴 ) ∴ (B ∨ C)

(A ∨ B ∨ 𝐶) (¬𝐴 ∨ D ∨ E ) ∴ (B ∨ C ∨ D ∨ E) Nếu A sai thì B hoặc C phải đúng, còn nếu A đúng thì D hoặc E phải đúng Do đó, vì A hoặc đúng hoặc sai, B hoặc C hoặc D hoặc E phải đúng

Lược giản B

(A ∨ B) (¬𝐴 ∨ B ) ∴ (B ∨ B) ≡ B

Hợp giải Robinson

Chứng minh KB ⊨ 𝛼 tương đương với chứng minh KB ∧ ¬𝛼 không thoả (unsatisfiable)

Function PL-Resolution(KB, 𝛼) return true hoặc false

clauses ← tập các mệnh đề ở dạng CNF của KB ∧ ¬𝛼 new𝐶lauses ← loop

for each 𝐶𝑖, 𝐶𝑗 trong clauses do

resolvents ← PL − Resolve(𝐶𝑖, 𝐶𝑗) if resolvents chứa mệnh đề rỗng then return true new𝐶lauses ← new𝐶lauses ∪ resolvents

end for if newClauses ⊆ clauses then return false clause𝑠 ⟵ clauses ڂ newClauses

end loop

Ví dụ

Cho KB = A → B ∨ 𝐶 , A, ¬B và 𝛼 = 𝐶. Cho biết liệu KB ⊨ 𝛼?

Chuyển KB ∧ ¬𝛼 về dạng CNF: ¬A ∨ B ∨ 𝐶, A, ¬B, ¬𝐶

Thực hiện hợp giải:

Suy dẫn

Công thức ¬A ∨ B ∨ 𝐶 A ¬B ¬𝐶

B ∨ 𝐶 𝐶 ∙ KB KB KB Phủ định kết luận Hợp giải ¬A ∨ B ∨ 𝐶 và A Hợp giải B ∨ 𝐶 và ¬B Hợp giải 𝐶 và ¬𝐶

Ví dụ

Cho KB ={𝐴 → 𝐵 ∨ 𝐶 , 𝐵 → (𝐷 ∨ 𝐹), 𝐴 ∧ 𝐷 → 𝐹, 𝐶 → 𝐹} và 𝛼= 𝑨 → 𝑭

Chứng minh KB ⊨ 𝛼?

KB ở dạng Horn

◦ Chẳng hạn, dạng Horn (HNF – Horn normal form)

Nếu các công thức trong KB được giới hạn ở dạng đặc biệt, một số luật suy diễn đúng có thể trở thành đầy đủ

◦ Hợp giải

◦ Tam đoạn luận (Modus ponens)

Hai luật suy diễn đúng và đầy đủ tương ứng với KB ở dạng HNF là:

KB ở dạng Horn

Dạng Horn: một mệnh đề (clause) có nhiều nhất một positive literal

Ví dụ: 𝐴 ∨ ¬𝐵 , ¬𝐵 ∨ ¬𝐶 ∨ 𝐷

Lưu ý: Không phải mọi công thức trong logic mệnh đề đều có thể đưa về dạng Horn

Các công thức dạng Horn:

Dạng

Rules

Facts

Integrity Constraints

Công thức ¬𝐵1 ∨ ¬𝐵2 ∨. .∨ ¬𝐵𝑘 ∨ 𝐴 hoặc 𝐵1 ∧ 𝐵2 ∧. .∧ 𝐵𝑘 → 𝐴 𝐵 ¬𝐵1 ∨ ¬𝐵2 ∨. .∨ ¬𝐵𝑘 hoặc 𝐵1 ∧ 𝐵2 ∧. .∧ 𝐵𝑘 → 𝐹𝑎𝑙𝑠𝑒

KB ở dạng Horn

KB ở dạng Horn là nối liền các công thức dạng Horn

Ví dụ: 𝐴 ∨ ¬𝐵 ∧ ¬𝐵 ∨ ¬𝐶 ∨ 𝐷

Luật suy diễn: Modus Ponens

𝛼 → 𝛽, 𝛼

∴ 𝛽

◦ Các thuật toán này gần với suy diễn tự nhiên và chạy với thời gian tuyến tính

Suy dẫn 𝐾𝐵 ⊨ 𝛼 ở dạng Horn có thể được thực hiện bằng phương pháp suy diễn tiến và suy diễn lùi

Suy diễn tiến (Forward chaining)

Kích hoạt tất cả các luật mà tiền đề của nó thoả trong KB, bổ sung kết luận vào KB, lặp cho đến khi tìm thấy kết luận

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Ví dụ

Chứng minh 𝑬 từ KB như bên dưới

KB Bước Công thức

𝐴 ∧ 𝐵 → 𝐶

Suy dẫn Cho trước 𝐴 ∧ 𝐵 → 𝐶

2 Cho trước 𝐶 ∧ 𝐷 → 𝐸 𝐶 ∧ 𝐷 → 𝐸

𝐶 ∧ 𝐹 → 𝐺

3 4 Cho trước Cho trước 𝐶 ∧ 𝐹 → 𝐺 𝐴 𝐴

5 Cho trước 𝐵 𝐵

𝐷

6 7 Cho trước 1, 4 và 5 𝐷 𝐶

8 2, 6, và 7 𝐸

FC – Bài tập ví dụ 2

Cho các luật và sự kiện như sau

◦ IF nóng AND có khói THEN có lửa

◦ IF có lửa THEN bật vòi phun nước cứu hỏa

◦ IF chuông báo cháy reo THEN có khói

◦ chuông báo cháy reo

◦ nóng

Chứng minh hành động bật vòi phun nước cứu hỏa xảy ra?

Suy diễn lùi (Backward chaining)

◦ Kiểm tra xem Q đã biết chưa, hay

◦ Chứng minh bằng cách suy diễn lùi tất cả tiền đề của một luật nào đó rút ra Q

Tránh lặp vô tận: kiểm tra xem một mục tiêu phụ đã nằm trong ngăn xếp mục tiêu hay chưa

Ý tưởng: quay lùi từ câu hỏi Q

◦ Đã thất bại

Tránh lặp lại công việc: kiểm tra xem một mục tiêu phụ mới ◦ Đã được chứng minh đúng, hay

Suy diễn lùi (Backward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q L  M  P

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q L  M  P A  B  L 

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q L  M  P A  B  L  

A? B?

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q L  M  P

 

L?  A? B?

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q L  M  P

L?  A? B?

  L  B  M

L? B?

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

P  Q L  M  P

 

L?  A? B?

 

M?  L? B?

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

 

L?  A? B?

 

M?  L? B?

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)

 

L?  A? B?

 

M?  L? B?

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Ví dụ

Chứng minh 𝑬 từ KB như bên dưới

• E? 𝐶 ∧ 𝐷 → 𝐸 KB

• C?

𝐴 ∧ 𝐵 → 𝐶

𝐶 ∧ 𝐷 → 𝐸 • A? Cho trước

𝐶 ∧ 𝐹 → 𝐺 • B? Cho trước

𝐴

• D? Cho trước

𝐵

𝐷

Ví dụ

Cho các luật và sự kiện như sau

◦ IF nóng AND có khói THEN có lửa

◦ IF có lửa THEN bật vòi phun nước cứu hỏa

◦ IF chuông báo cháy reo THEN có khói

◦ chuông báo cháy reo

◦ nóng

Chứng minh hành động bật vòi phun nước cứu hỏa xảy ra

Tổng kết

Hiểu rõ khái niệm logic, vai trò và ứng dụng của nó.

Hiểu rõ logic mệnh đề: các thành phần và các phương pháp suy dẫn. Từ đó, vận dụng thành thạo các phương pháp suy dẫn: ◦ Hợp giải Robinson: KB ở dạng CNF

◦ Suy diễn tiến, suy diễn lùi: KB ở dạng Horn

Nắm vững kiến trúc của một hệ thống logic, gồm: cú pháp, ngữ nghĩa và phương pháp suy diễn

Tài liệu tham khảo

Cơ sở Trí tuệ Nhân tạo, Lê Hoài Bắc, Tô Hoài Việt, NXB Khoa học & Kỹ thuật.

Artificial Intelligence: A Modern Approach, 3rd Edition, S. Russel and P. Norvig, Pearson Education Inc., 2010

Slide bài giảng Trí tuệ nhân tạo, GV. Tô Hoài Việt, GV. Lê Ngọc Thành, Khoa CNTT, ĐH. KHTN TP.HCM

Techniques in Artificial Intelligence (SMA 5504) , MIT OpenCourseWare, Massachusetts Institute of Technology

Artificial Intelligence: Principles and Techniques, Stanford courses, Autumn 2015.

Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng - Chương 5: Logic

Logic THS. BÙI THỊ DANH

Nội dung chính

Lịch sử phát triển

Lịch sử phát triển

Ứng dụng: trợ lí ảo

Sử dụng ngôn ngữ tự nhiên

Ngôn ngữ tự nhiên

Ngôn ngữ logic

Hai mục tiêu của logic

Các thành phần của hệ thống logic

Các thành phần của hệ thống logic

Nội dung chính

Các thành phần của hệ thống logic

Cú pháp

Một số ví dụ

Các thành phần của hệ thống logic

Ngữ nghĩa

A

B

C

Ngữ nghĩa

Ví dụ

Ngữ nghĩa

Ngữ nghĩa

Cơ sở tri thức (knowledge base)

Ví dụ

Tính thoả mãn được (Satisfiability)

Ví dụ

Các thành phần của hệ thống logic

Sự suy dẫn (entailment)

Sự mâu thuẫn (contradiction)

Các phương pháp suy dẫn KB ⊨ 𝛼

Lập bảng chân trị (hay liệt kê)

Lập bảng chân trị (liệt kê)

Luật suy diễn

Tiền đề/Giả thuyết 𝛼, 𝛼 → 𝛽 𝛼, 𝛽 𝛼 ∧ 𝛽 𝛼 ¬¬𝛼 𝛼 ∨ 𝛽, ¬𝛽 𝛼 ∨ 𝛽, ¬𝛽 ∨ 𝛾

Kết luận 𝛽 𝛼 ∧ 𝛽 𝛼 𝛼 ∨ 𝛾 𝛼 𝛼 𝛼 ∨ 𝛾

Luật suy diễn Modus Ponens And - Introduction And - Elimination Or - Introduction Double Negation Unit Resolution Resolution

Ví dụ

Luật suy diễn

Luật suy diễn

Luật suy diễn

Giải pháp cho tính đầy đủ

Giải pháp 2: Giới hạn tập công thức được phép sử dụng. ◦ Logic mệnh đề bao gồm các mệnh đề dạng Horn

KB ở dạng CNF (Conjunctive Normal Form)

KB ở dạng CNF (Conjunctive Normal Form)

Chuyển đổi công thức sang dạng CNF

Ví dụ

Hợp giải cho CNF

Hợp giải Robinson

Ví dụ

Ví dụ

KB ở dạng Horn

KB ở dạng Horn

KB ở dạng Horn

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn tiến (Forward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Ví dụ

FC – Bài tập ví dụ 2

Suy diễn lùi (Backward chaining)

Suy diễn lùi (Backward chaining)

𝑃 → 𝑄 𝐿 ∧ 𝑀 → 𝑃 𝐵 ∧ 𝐿 → 𝑀 𝐴 ∧ 𝑃 → 𝐿 𝐴 ∧ 𝐵 → 𝐿 𝐴 𝐵

Suy diễn lùi (Backward chaining)