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

Hạn chế của logic mệnh đề

Mục tiêu của logic là biểu diễn tri thức, sự kiện của thế giới một cách súc tích. Logic mệnh đề có đảm bảo việc này?

Alice và Bob đều biết số học ◦ AliceKnowsArithmetic ∧ BobKnowsArithmetic

◦ BobIsStudent → BobKnowsArithmetic

Tất cả sinh viên đều biết số học ◦ AliceIsStudent → AliceKnowsArithmetic

◦ …

Nhiều, cồng kềnh

Mọi số nguyên chẵn lớn hơn 2 đều là tổng của 2 số nguyên tố ◦ ???

Khó biểu diễn

Hạn chế của Logic mệnh đề

(alice, Knows, arithmetic)

◦ Lượng từ (quantifier) và biến (variable): “tất cả” là một lượng từ có thể dùng để ám chỉ mọi người, mà

không phải liệt kê từng người một…

Logic mệnh đề thiếu các khái niệm để cho phép diễn đạt sự kiện súc tích hơn, chẳng hạn: ◦ Đối tượng (object) và quan hệ (relation): các mệnh đề (AliceKnowsArithmetic) có cấu trúc bên trong

 Logic bậc nhất (First Order Logic – FOL)

Logic bậc nhất (First Order Logic)

Cú pháp: các thành phần cơ bản

◦ Ví dụ: 𝑎𝑙𝑖𝑐𝑒, 𝑏𝑜𝑏, 2, 𝑐𝑝𝑢 …

Kí hiệu hằng (Constant symbol) ◦ Biểu diễn đối tượng

Kí hiệu vị từ (Predicate symbol) ◦ Biểu diễn quan hệ (trả lời ‘yes’ hoặc ‘no’)

◦ Ví dụ: 𝐵𝑟𝑜𝑡ℎ𝑒𝑟 (𝑟𝑖𝑐ℎ𝑎𝑟𝑑, 𝑗𝑜ℎ𝑛), 𝐺𝑟𝑒𝑎𝑡𝑒𝑟𝑇ℎ𝑎𝑛(3, 2), …

Kí hiệu hàm (Function symbol) ◦ Biểu diễn cho hàm (Trả về một giá trị)

◦ Ví dụ: 𝑆𝑞𝑟𝑡(4), 𝑀𝑜𝑡ℎ𝑒𝑟𝑂𝑓(𝑗𝑜ℎ𝑛), …

Cú pháp: các thành phần cơ bản

Khái niệm Ví dụ

Hằng (constant)

alice, arithmetic, bob, 2, …

Vị từ (Predicate) Knows, Brother, GreaterThan, …

Hàm (Function) MotherOf, Sqrt, …

Biến (Variable)

x, y, a, b

¬,∧,∨, →, ↔ Phép nối (Connective)

Sự bằng nhau (Equality) =

∃ , ∀ Lượng từ (Quantifier)

Cú pháp

◦ Biến: 𝑥, 𝑦, 𝑎, 𝑏, …

◦ Hàm: 𝑆𝑞𝑟𝑡(4), 𝑀𝑜𝑡ℎ𝑒𝑟𝑂𝑓(𝑗𝑜ℎ𝑛), …

Term là biểu thức logic ám chỉ đối tượng. ◦ Hằng: 𝑎𝑙𝑖𝑐𝑒, 𝑏𝑜𝑏, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐, 2

◦ Công thức nguyên tử: vị từ áp dụng lên biểu thức

◦ 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐)

◦ Phép nối áp dụng lên công thức

◦ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 → 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐)

◦ Lượng từ áp dụng lên công thức

◦ ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 → 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐)

Công thức hoặc câu (sentence)

Cú pháp: Lượng từ

Lượng từ với mọi (∀): ◦ ∀𝑥 𝑃(𝑥) thì giống như 𝑃 𝐴 ∧ 𝑃 𝐵 ∧ ⋯

Lượng từ tồn tại (∃): ◦ ∃𝑥 𝑃(𝑥) thì giống như 𝑃 𝐴 ∨ 𝑃 𝐵 ∨ ⋯

◦ ∀𝑥 ∃𝑦 𝑃 𝑥, 𝑦 thì khác với ∃𝑥∀𝑦 𝑃(𝑥, 𝑦)

Một số thuộc tính: ◦ ¬∀𝑥 𝑃(𝑥) tương đương với ∃𝑥 ¬𝑃(𝑥)

Cú pháp: Qui tắc De Morgan cho lượng từ

¬ 𝑃 ∨ 𝑄 ≡ ¬𝑃 ∧ ¬𝑄 ∀𝑥 𝑃 𝑥 ≡ ¬∃𝑥 ¬𝑃(𝑥)

∃𝑥 𝑃(𝑥) ≡ ¬∀𝑥 ¬𝑃(𝑥) ¬ 𝑃 ∧ 𝑄 ≡ ¬𝑃 ∨ ¬𝑄

¬∀𝑥 𝑃(𝑥) ≡ ∃𝑥 ¬𝑃(𝑥) 𝑃 ∨ 𝑄 ≡ ¬ ¬𝑃 ∧ ¬𝑄

¬∃𝑥 𝑃(𝑥) ≡ ∀𝑥 ¬𝑃(𝑥) 𝑃 ∧ 𝑄 ≡ ¬ ¬𝑃 ∨ ¬𝑄

Cú pháp: Lượng từ với ngôn ngữ tự nhiên

◦ ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 → 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐)

Lượng từ với mọi (∀): ◦ Mọi sinh viên đều biết số học

Lượng từ tồn tại (∃): ◦ Một số sinh viên thì biết số học

◦ ∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡(𝑥) ∧ 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐)

Cú pháp: ví dụ

Mọi loại nấm màu tím đều có độc ◦ ∀𝑥 𝑀𝑢𝑠ℎ𝑟𝑜𝑜𝑚 𝑥 ∧ 𝑃𝑢𝑟𝑝𝑙𝑒 𝑥 → 𝑃𝑜𝑖𝑠𝑜𝑛𝑜𝑢𝑠(𝑥)

Mèo là động vật có vú ◦ ∀𝑥 𝐶𝑎𝑡 𝑥 → 𝑚𝑎𝑚𝑚𝑎𝑙(𝑥)

Không ai yêu Lan ◦ ¬∃𝑥 𝐿𝑜𝑣𝑒(𝑥, 𝐿𝑎𝑛) hoặc ∀𝑥 ¬𝐿𝑜𝑣𝑒(𝑥, 𝐿𝑎𝑛)

Cháu là con của anh em ◦ ∀𝑥∀𝑦 𝑁𝑖𝑒𝑐𝑒𝑁𝑒𝑝ℎ𝑒𝑤 𝑥, 𝑦 ↔ ∃𝑧 𝑆𝑖𝑏𝑙𝑖𝑛𝑔(𝑦, 𝑧) ∧ 𝐶ℎ𝑖𝑙𝑑(𝑥, 𝑧)

◦ ∀𝑥∀𝑦 𝑥 = 𝐺𝑟𝑎𝑛𝑑𝑚𝑜𝑡ℎ𝑒𝑟 𝑦 ↔ ∃𝑧 𝑥 = 𝑀𝑜𝑡ℎ𝑒𝑟 𝑧 ∧ 𝑧 = 𝑀𝑜𝑡ℎ𝑒𝑟(𝑦)

Bà ngoại là mẹ của mẹ ◦ ∀𝑥∀𝑦 𝐺𝑟𝑎𝑛𝑑𝑚𝑜𝑡ℎ𝑒𝑟 𝑥, 𝑦 ↔ ∃𝑧 𝑀𝑜𝑡ℎ𝑒𝑟(𝑥, 𝑧) ∧ 𝑀𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑦)

Cú pháp: ví dụ

Có một số khóa học mà mọi sinh viên đều tham gia ◦ ∃𝑦 𝐶𝑜𝑢𝑟𝑠𝑒 𝑦 ∧ ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 → 𝑇𝑎𝑘𝑒𝑠(𝑥, 𝑦)

Mọi số nguyên chẵn lớn hơn 2 là tổng của 2 số nguyên tố ◦ ∀𝑥 𝐸𝑣𝑒𝑛𝐼𝑛𝑡 𝑥 ∧ 𝐺𝑟𝑒𝑎𝑡𝑒𝑟 𝑥, 2 → ∃𝑦∃𝑧 𝐸𝑞𝑢𝑎𝑙𝑠(𝑥, 𝑆𝑢𝑚 𝑦, 𝑧 ) ∧ 𝑃𝑟𝑖𝑚𝑒(𝑦) ∧ 𝑃𝑟𝑖𝑚𝑒(𝑧)

Nếu một sinh viên học một khóa học và khóa học đó có đề cập đến một khái niệm thì sinh viên đó biết về khái niệm đó. ◦ ∀𝑥∀𝑦∀𝑧 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 ∧ 𝐶𝑜𝑢𝑟𝑠𝑒 𝑦 ∧ 𝑇𝑎𝑘𝑒𝑠 𝑥, 𝑦 ∧ 𝐶𝑜𝑣𝑒𝑟𝑠 𝑦, 𝑧 → 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑧)

Cú pháp: bài tập

Lan là sinh viên học giỏi

Mọi người đều yêu ai đó

Ai cũng có một cha

Ai cũng có một cha và một mẹ

Bất kỳ ai có một cha cũng có một mẹ

Cú pháp: bài tập

Lan là sinh viên học giỏi

◦ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝐿𝑎𝑛 ∧ 𝑆𝑡𝑢𝑑𝑦 − 𝑤𝑒𝑙𝑙(𝐿𝑎𝑛)

Mọi người đều yêu ai đó

◦ ∀𝑥∃𝑦 𝐿𝑜𝑣𝑒𝑠(𝑥, 𝑦)

Ai cũng có một cha

◦ ∀𝑥 ∃𝑦 𝐹𝑎𝑡ℎ𝑒𝑟(𝑦, 𝑥)

Ai cũng có một cha và một mẹ

◦ ∀𝑥 ∃𝑦 ∃𝑧 𝐹𝑎𝑡ℎ𝑒𝑟(𝑦, 𝑥) ∧ 𝑀𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑥)

Bất kỳ ai có một cha cũng có một mẹ

◦ ∀𝑥 ∃𝑦 𝐹𝑎𝑡ℎ𝑒𝑟 𝑦, 𝑥 → ∃𝑧 𝑀𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑥)

Ngữ nghĩa

◦ 𝑤 𝑎𝑙𝑖𝑐𝑒 = 𝑜1, 𝑤 𝑏𝑜𝑏 = 𝑜2, 𝑤 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐 = 𝑜3

◦ Kí hiệu vị từ sang cặp các đối tượng

◦ 𝑤 𝐾𝑛𝑜𝑤𝑠 = 𝑜1, 𝑜3 , 𝑜2, 𝑜3 , …

Mô hình 𝑤 trong logic bậc nhất ánh xạ ◦ Kí hiệu hằng số sang đối tượng

Ngữ nghĩa

Nếu tồn tại ánh xạ một – một giữa các kí hiệu hằng số và các đối tượng thì logic bậc nhất là dạng ngắn của logic mệnh đề

KB ở dạng Logic bậc nhất

Ví dụ:

Propositionalization

𝑆𝑡𝑢𝑑𝑒𝑛𝑡(𝑎𝑙𝑖𝑐𝑒) ∧ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑏𝑜𝑏 ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 → 𝑃𝑒𝑟𝑠𝑜𝑛(𝑥) ∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑥 ∧ 𝐶𝑟𝑒𝑎𝑡𝑖𝑣𝑒(𝑥)

KB ở dạng Logic mệnh đề

𝑆𝑡𝑢𝑑𝑒𝑛𝑡(𝑎𝑙𝑖𝑐𝑒) ∧ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑏𝑜𝑏 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑎𝑙𝑖𝑐𝑒 → 𝑃𝑒𝑟𝑠𝑜𝑛(𝑎𝑙𝑖𝑐𝑒) ∧ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑏𝑜𝑏 → 𝑃𝑒𝑟𝑠𝑜𝑛(𝑏𝑜𝑏) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑎𝑙𝑖𝑐𝑒 ∧ 𝐶𝑟𝑒𝑎𝑡𝑖𝑣𝑒(𝑎𝑙𝑖𝑐𝑒) ∨ 𝑆𝑡𝑢𝑑𝑒𝑛𝑡 𝑏𝑜𝑏 ∧ 𝐶𝑟𝑒𝑎𝑡𝑖𝑣𝑒 𝑏𝑜𝑏

Phương pháp suy dẫn

Mục tiêu: cần các luật suy diễn có thể làm việc với các công thức có lượng từ

◦ Có suy diễn được 𝑄 𝑎𝑙𝑖𝑐𝑒 ?

◦ Vấn đề: 𝑃(𝑥) và 𝑃(𝑎𝑙𝑖𝑐𝑒) không khớp nhau

Ví dụ ◦ Cho 𝑃(𝑎𝑙𝑖𝑐𝑒) và ∀𝑥 𝑃 𝑥 → 𝑄 𝑥

◦ Phép thay thế (substitution): ánh xạ công thức sang một công thức khác.

◦ Phép đồng nhất (unification): làm cho hai công thức giống nhau.

Đề xuất các khái niệm:

Phép thay thế (substitution)

Một phép thay thế 𝜃 là một ánh xạ từ các biến sang các kí hiệu hằng hoặc biến khác

Kí hiệu: 𝑆𝑢𝑏𝑠𝑡 𝜃, 𝛼 , trả về kết quả thực hiện phép thay thế 𝜃 trên công thức 𝛼

◦ 𝑆𝑢𝑏𝑠𝑡 𝑥/𝑎𝑙𝑖𝑐𝑒, 𝑦/𝑧 , 𝑃(𝑥) ∧ 𝐾(𝑥, 𝑦) = 𝑃(𝑎𝑙𝑖𝑐𝑒) ∧ 𝐾(𝑎𝑙𝑖𝑐𝑒, 𝑧)

Ví dụ ◦ 𝑆𝑢𝑏𝑠𝑡 𝑥/𝑎𝑙𝑖𝑐𝑒 , 𝑃(𝑥) = 𝑃(𝑎𝑙𝑖𝑐𝑒)

Phép đồng nhất (unification)

◦ Hoặc lỗi nếu không tồn tại 𝜃

Phép đồng nhất thực hiện trên hai công thức 𝛼 𝑣à 𝛽, trả về một phép thay thế 𝜃 làm cho hai công thức giống nhau, tức: ◦ Hoặc 𝑈𝑛𝑖𝑓𝑦 𝛼, 𝛽 = 𝜃 sao cho 𝑆𝑢𝑏𝑠𝑡 𝜃, 𝛼 = 𝑆𝑢𝑏𝑠𝑡 𝜃, 𝛽

◦ 𝑈𝑛𝑖𝑓𝑦 𝐾𝑛𝑜𝑤𝑠 𝑎𝑙𝑖𝑐𝑒, 𝑦 , 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑧) = 𝑥/𝑎𝑙𝑖𝑐𝑒, 𝑦/𝑧

◦ 𝑈𝑛𝑖𝑓𝑦 𝐾𝑛𝑜𝑤𝑠 𝑎𝑙𝑖𝑐𝑒, 𝑦 , 𝐾𝑛𝑜𝑤𝑠(𝑏𝑜𝑏, 𝑧) = 𝑙ỗ𝑖

◦ 𝑈𝑛𝑖𝑓𝑦 𝐾𝑛𝑜𝑤𝑠 𝑎𝑙𝑖𝑐𝑒, 𝑦 , 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝐹(𝑥)) = 𝑥/𝑎𝑙𝑖𝑐𝑒, 𝑦/𝐹(𝑎𝑙𝑖𝑐𝑒)

Ví dụ: ◦ 𝑈𝑛𝑖𝑓𝑦 𝐾𝑛𝑜𝑤𝑠 𝑎𝑙𝑖𝑐𝑒, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐 , 𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑎𝑟𝑖𝑡ℎ𝑚𝑒𝑡𝑖𝑐) = 𝑥/𝑎𝑙𝑖𝑐𝑒

Phương pháp suy dẫn

Hợp giải với KB ở dạng CNF

Suy diễn với KB ở dạng Horn

Hợp giải với KB ở dạng CNF

Nhắc lại: Để chứng minh 𝐾𝐵 ⊨ 𝛼 ta chứng minh 𝐾𝐵 ∧ ¬𝛼 không thỏa

◦ Áp dụng luật hợp giải: tìm cặp mệnh đề đối ngẫu 𝑃 và ¬𝑃

Các bước chứng minh: ◦ Chuyển 𝐾𝐵 ∧ ¬𝛼 về dạng CNF

Chuyển về dạng CNF

◦ ∀𝑥 ∀𝑦 𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 → 𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 → ∃𝑦 𝐿𝑜𝑣𝑒𝑠(𝑦, 𝑥)

Ví dụ: Người yêu tất cả các động vật thì được yêu bởi một ai đó

◦ ∀𝑥 ∀𝑦 ¬𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 ∨ 𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 → ∃𝑦 𝐿𝑜𝑣𝑒𝑠(𝑦, 𝑥)

◦ ∀𝑥 ¬ ∀𝑦 ¬𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 ∨ 𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 ∨ ∃𝑦 𝐿𝑜𝑣𝑒𝑠(𝑦, 𝑥)

Loại bỏ dấu tương đương và kéo theo

◦ ∀𝑥 ∃𝑦 𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 ∧ ¬𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 ∨ ∃𝑦 𝐿𝑜𝑣𝑒𝑠(𝑦, 𝑥)

Đẩy dấu phủ định vào trong, loại bỏ 2 dấu phủ định

◦ ∀𝑥 ∃𝑦 𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 ∧ ¬𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 ∨ ∃𝑧 𝐿𝑜𝑣𝑒𝑠(𝑧, 𝑥)

Chuẩn hóa biến: mỗi lượng từ nên sử dụng các biến khác nhau

Chuyển về dạng CNF

◦ ∀𝑥 ∃𝑦 𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 ∧ ¬𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 ∨ ∃𝑧 𝐿𝑜𝑣𝑒𝑠(𝑧, 𝑥)

∨ 𝐿𝑜𝑣𝑒𝑠(𝑍(𝑥), 𝑥)

◦ ∀𝑥 𝐴𝑛𝑖𝑚𝑎𝑙 𝑌 𝑥 ∧ ¬𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑌 𝑥

Skolem hóa: thay thế các biến với lượng từ tồn tại bằng hàm Skolem theo các biến có lượng từ với mọi

∨ 𝐿𝑜𝑣𝑒𝑠(𝑍(𝑥), 𝑥)

◦ 𝐴𝑛𝑖𝑚𝑎𝑙 𝑌 𝑥 ∧ ¬𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑌 𝑥

Bỏ lượng từ với mọi: các biến còn lại giả định là với mọi

◦ 𝐴𝑛𝑖𝑚𝑎𝑙 𝑌 𝑥 ∨ 𝐿𝑜𝑣𝑒𝑠(𝑍(𝑥), 𝑥) ∧ ¬𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑌 𝑥 ∨ 𝐿𝑜𝑣𝑒𝑠(𝑍(𝑥), 𝑥)

Phân phối ∨ 𝑣ớ𝑖 ∧:

Hợp giải

𝛼1∨⋯∨𝛼𝑛∨ℎ1 𝛽1∨⋯∨𝛽𝑚∨¬ℎ2 𝑆𝑢𝑏𝑠𝑡 𝜃,𝛼1∨⋯∨𝛼𝑛∨𝛽1∨⋯∨𝛽𝑚

𝐴𝑛𝑖𝑚𝑎𝑙 𝑌 𝑥 ∨ 𝐿𝑜𝑣𝑒𝑠(𝑍 𝑥 ,𝑥) ¬𝐿𝑜𝑣𝑒𝑠 𝑢,𝑣 ∨ 𝐹𝑒𝑒𝑑𝑠(𝑢,𝑣) 𝐴𝑛𝑖𝑚𝑎𝑙 𝑌 𝑥 ∨ 𝐹𝑒𝑒𝑑𝑠 (𝑍 𝑥 ,𝑥)

◦ Trong đó, 𝜃 = 𝑈𝑛𝑖𝑓𝑦(ℎ1, ℎ2)

◦ Phép thay thế 𝜃 = 𝑈𝑛𝑖𝑓𝑦 𝑢/𝑍 𝑥 , 𝑣/𝑥

Luật hợp giải: Ví dụ

Ví dụ 1

Chứng minh ∃𝑧 𝑄(𝑧) từ KB như bên cạnh

KB

𝑃 𝑥 → 𝑄(𝑥)

𝑃(𝐴)

Bước Công thức Suy dẫn

1 Cho trước ¬𝑃(𝑥) ∨ 𝑄(𝑥)

2 Cho trước 𝑃(𝐴)

3 ¬𝑄(𝑧)

5 ¬𝑃(z) False Phủ định kết luận 1, 3 𝜃 = { Τ𝑥 𝑧} 2, 4 𝜃 = 𝑧/𝐴

Ví dụ 2

Cho KB như bên cạnh. Tìm 𝑧 sao cho 𝑄(𝑧) đúng

KB 𝑃 𝑥 → 𝑄(𝑥) 𝑃(𝐴)

𝑃(𝐵)

Bước

Suy dẫn

Công thức ¬𝑃(𝑥) ∨ 𝑄(𝑥)

1 Cho trước

𝑃(𝐴) 𝑃(𝐵) 2 3 Cho trước Cho trước

¬𝑄(𝑧) 4

¬𝑃(z) 5

6 False

7 False Phủ định kết luận 1, 4 𝜃 = { Τ𝑥 𝑧} 2, 5 𝜃 = 𝑧/𝐴 3, 5 𝜃 = 𝑧/𝐵

Ví dụ 3

◦ Art là cha của Bob và Bud.

◦ Bob là cha của Cal và Coe.

◦ Ông nội là cha của cha.

Cho KB gồm các câu như sau. Hỏi Art có phải là ông nội của Coe không?

◦ 𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙) ∧ 𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

◦ ∃𝑧 𝐹𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑧 ∧ 𝐹𝑎𝑡ℎ𝑒𝑟 𝑧, 𝑦 → 𝐺𝑟𝑎𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑦

◦ 𝐺𝑟𝑎𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟 𝑎𝑟𝑡, 𝑐𝑜𝑒 ?

Biểu diễn lại KB theo logic bậc nhất ◦ 𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏) ∧ 𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

Ví dụ 3

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

Công thức

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

Cho trước

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙)

Cho trước

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

Cho trước

¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑥, 𝑧) ∨ ¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑧, 𝑦) ∨ 𝐺𝑟𝑎𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟(𝑥, 𝑦)

Cho trước

¬𝐺𝑟𝑎𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟 𝑎𝑟𝑡, 𝑐𝑜𝑒

Phủ định kết luận

¬𝐹ather(𝑎𝑟𝑡, z) ∨ ¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑧, 𝑐𝑜𝑒)

5, 6 𝜃 = { Τ𝑥 𝑎𝑟𝑡 , Τ𝑦 𝑐𝑜𝑒}

¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, coe)

1, 7 𝜃 = Τ𝑧 𝑏𝑜𝑏

False

4, 5

Bước 1 Suy dẫn Cho trước

Ai là ông của Coe?

Bước

Công thức

Suy dẫn

Cho trước

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

Cho trước

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

Cho trước

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙)

Cho trước

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

Cho trước

¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑥, 𝑧) ∨ ¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑧, 𝑦) ∨ 𝐺𝑟𝑎𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟(𝑥, 𝑦)

Phủ định kết luận

5, 6 𝜃 = { Τ𝑥 𝑥2 , Τ𝑦 𝑐𝑜𝑒} 4, 7 𝜃 = Τ𝑧 𝑏𝑜𝑏

¬𝐺𝑟𝑎𝑛𝑑𝑓𝑎𝑡ℎ𝑒𝑟 𝑥2, 𝑐𝑜𝑒 ¬𝐹ather(𝑥2, z) ∨ ¬𝐹𝑎𝑡ℎ𝑒𝑟(𝑧, 𝑐𝑜𝑒) ¬𝐹ather(𝑥2, 𝑏𝑜𝑏)

False

1, 8 𝜃 =

Τ𝒙𝟐 𝒂𝒓𝒕

Bài tập 1

Là phạm tội nếu một người Mỹ bán vũ khí cho kẻ địch

Nono có một vài tên lửa

Tất cả các tên lửa mà Nono có đều được bán bởi West

Tên lửa là vũ khí

Một kẻ thù của nước Mỹ được gọi là kẻ địch

West là một người Mỹ

Nono là một kẻ thù của nước Mỹ

West có phạm tội không?

Bài tập 1

Là phạm tội nếu một người Mỹ bán vũ khí cho kẻ địch ◦ ∀𝑥∀𝑦∀𝑧 𝐴𝑚𝑒𝑟𝑖𝑐𝑎 𝑥 ∧ 𝑊𝑒𝑎𝑝𝑜𝑛 𝑦 ∧ 𝐻𝑜𝑠𝑡𝑖𝑙𝑒 𝑧 ∧ 𝑆𝑒𝑙𝑙𝑠 𝑥, 𝑦, 𝑧 → 𝐶𝑟𝑖𝑚𝑖𝑛𝑎𝑙(𝑥)

Nono có một vài tên lửa ◦ ∃𝑥 𝑂𝑤𝑛𝑠 𝑛𝑜𝑛𝑜, 𝑥 ∧ 𝑀𝑖𝑠𝑠𝑖𝑙𝑒(𝑥) Tất cả các tên lửa mà Nono có đều được bán bởi West ◦ ∀𝑥 𝑀𝑖𝑠silex∧Ownsnono,x→Sells(west,x,nono)

Tên lửa là vũ khí ◦ ∀𝑥 𝑀𝑖𝑠𝑠𝑖𝑙𝑒 𝑥 → 𝑊𝑒𝑎𝑝𝑜𝑛(𝑥)

Một kẻ thù của nước Mỹ được gọi là kẻ địch ◦ ∀𝑥 𝐸𝑛𝑒𝑚𝑦 𝑥, 𝑎𝑚𝑒𝑟𝑖𝑐𝑎 → 𝐻𝑜𝑠𝑡𝑖𝑙𝑒(𝑥)

West là một người Mỹ ◦ 𝐴𝑚𝑒𝑟𝑖𝑐𝑎(𝑤𝑒𝑠𝑡)

Nono là một kẻ thù của nước Mỹ ◦ 𝐸𝑛𝑒𝑚𝑦(𝑛𝑜𝑛𝑜, 𝑎𝑚𝑒𝑟𝑖𝑐𝑎)

West có phạm tội không? 𝐶𝑟𝑖𝑚𝑖𝑛𝑎𝑙(𝑤𝑒𝑠𝑡)

Bài tập 1

Bài tập 2

Người nào yêu tất cả động vật thì được yêu bởi ai đó

Bất kì ai giết động vật thì không được ai yêu

Jack yêu tất cả động vật

Hoặc Curiosity hoặc Jack đã giết Tuna

Tuna là một con mèo

Mèo là một loài động vật

Hỏi Jack có giết Tuna không?

Bài tập 2

Người nào yêu tất cả động vật thì được yêu bởi ai đó

◦ ∀𝑥 ∀𝑦 𝐴𝑛𝑖𝑚𝑎𝑙 𝑦 → 𝐿𝑜𝑣𝑒𝑠 𝑥, 𝑦 → ∃𝑧 𝐿𝑜𝑣𝑒𝑠(𝑧, 𝑥)

Bất kì ai giết động vật thì không được ai yêu

◦ ∀𝑥∃𝑦 𝐾𝑖𝑙𝑙𝑠 𝑥, 𝑦 → ∀𝑧 ¬𝐿𝑜𝑣𝑒𝑠(𝑧, 𝑥)

Jack yêu tất cả động vật

◦ ∀𝑥 𝐴𝑛𝑖𝑚𝑎𝑙 𝑥 → 𝐿𝑜𝑣𝑒𝑠(𝐽𝑎𝑐𝑘, 𝑥)

Hoặc Curiosity hoặc Jack đã giết Tuna

◦ 𝐾𝑖𝑙𝑙𝑠 𝑐𝑢𝑟𝑖𝑜𝑠𝑖𝑡𝑦, 𝑡𝑢𝑛𝑎 ∨ 𝐾𝑖𝑙𝑙𝑠(𝑗𝑎𝑐𝑘, 𝑡𝑢𝑛𝑎)

Tuna là một con mèo

◦ 𝐶𝑎𝑡(𝑇𝑢𝑛𝑎)

Mèo là một loài động vật

◦ ∀𝑥 𝐶𝑎𝑡 𝑥 → 𝐴𝑛𝑖𝑚𝑎𝑙(𝑥)

Hỏi Curiosity có giết Tuna không? 𝐾𝑖𝑙𝑙𝑠(𝑐𝑢𝑟𝑖𝑜𝑠𝑖𝑡𝑦, 𝑡𝑢𝑛𝑎)

Bài tập 2

Suy diễn với KB ở dạng Horn

′ , 𝑎1

′ , 𝑎𝑘

Modus Ponen Ví dụ

◦ 𝐶𝑜𝑣𝑒𝑟𝑠 𝑐𝑠221, 𝑙𝑜𝑔𝑖𝑐

Cho các tiền đề ◦ 𝑇𝑎𝑘𝑒𝑠 𝑎𝑙𝑖𝑐𝑒, 𝑐𝑠221

◦ ∀𝑥∀𝑦∀𝑧 𝑇𝑎𝑘𝑒𝑠 𝑥, 𝑦 ∧ 𝐶𝑜𝑣𝑒𝑟𝑠 𝑦, 𝑧 →

′ , 𝑎1 ∧ . . . ∧ 𝑎𝑘

◦ 𝜃 = 𝑈𝑛𝑖𝑓𝑦 𝑎1

′ ∧ . . . ∧ 𝑎𝑘

𝐾𝑛𝑜𝑤𝑠(𝑥, 𝑧)

◦ Áp dụng 𝜃 để xác định kết luận:

◦ 𝑆𝑢𝑏𝑠𝑡 𝜃, 𝑏 = 𝑏′

. . . ∀𝑥1 … 𝑥𝑛 𝑎1 ∧ . . . ∧ 𝑎𝑘 → 𝑏 𝑏′ ◦ Tìm phép đồng nhất tổng quát nhất trên tiền đề

Kết luận ◦ 𝜃 = 𝑥/𝑎𝑙𝑖𝑐𝑒, 𝑦/𝑐𝑠221, 𝑧/𝑙𝑜𝑔𝑖𝑐 ◦ 𝑏′ = 𝐾𝑛𝑜𝑤𝑠(𝑎𝑙𝑖𝑐𝑒, 𝑙𝑜𝑔𝑖𝑐)

Suy diễn tiến (forward chaining)

function FOL − FC − ASK(KB, 𝛼) returns phép thay thế hoặc false

repeat until 𝑛𝑒𝑤 là rỗng

𝑛𝑒𝑤 ← { } for each công thức 𝑟 trong 𝐾𝐵 do

Chuẩn hóa r 𝑡ℎà𝑛ℎ 𝑝1 ∧ ⋯ ∧ 𝑝𝑛 → 𝑞 for each 𝜃 sao cho (p1 …  pn)= (p’1 …  p’n) do

Với p’1,…, p’n nào đó trong KB

𝑞′ ← 𝑆𝑢𝑏𝑠𝑡(𝜃, q) if 𝑞′ không phải là một câu đã có trong KB hay 𝑛𝑒𝑤 then

thêm q’ vào new

  Unify(q’, )

if  thành công then return 

Thêm 𝑛𝑒𝑤 𝑣à𝑜 𝐾𝐵

return false

Ví dụ

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝑀𝑜𝑡ℎ𝑒𝑟(𝐴𝑣𝑒, 𝐵𝑒𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦) 1 = {x/ave, y/bee}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑏𝑒𝑒)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑏𝑜𝑏, 𝑐𝑎𝑙

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑎𝑙)

2 = {x/bee, y/cal}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑎𝑙)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑎𝑣𝑒, 𝑏𝑒𝑒)

3 = {x/bee, y/coe}

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑎𝑙)

𝑀𝑜𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)

𝑃𝑎𝑟𝑒𝑛𝑡 𝑥, 𝑦 ∧ 𝑃𝑎𝑟𝑒𝑛𝑡 𝑦, 𝑧 → 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑧)

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑐𝑜𝑒) ?

Ví dụ

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑏𝑒𝑒)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑎𝑙)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦) 1 = {x/art, y/bob}

𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑜𝑒)

q’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑏𝑜𝑏, 𝑐𝑎𝑙

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

2 = {x/art, y/bud}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

q’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑢𝑑)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑎𝑣𝑒, 𝑏𝑒𝑒)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙)

3 = {x/bob, y/cal}

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑜𝑒)

q’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑎𝑙)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑎𝑙)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

4 = {x/bob, y/coe}

q’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)

𝑃𝑎𝑟𝑒𝑛𝑡 𝑥, 𝑦 ∧ 𝑃𝑎𝑟𝑒𝑛𝑡 𝑦, 𝑧 → 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑧)

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑐𝑜𝑒) ?

Ví dụ

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑏𝑒𝑒)

𝑃𝑎𝑟𝑒𝑛𝑡 𝑥, 𝑦 ∧ 𝑃𝑎𝑟𝑒𝑛𝑡 𝑦, 𝑧 → 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑧) 1 = {x/ave,y/bee,z/cal} 𝑃𝑎𝑟𝑒𝑛𝑡(𝐴𝑣𝑒, 𝐵𝑒𝑒) ∧ 𝑃𝑎𝑟𝑒𝑛𝑡(𝐵𝑒𝑒, 𝐶𝑎𝑙)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑎𝑙)

q’ = 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑐𝑎𝑙)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑏𝑜𝑏, 𝑐𝑎𝑙

𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑜𝑒)

2 = {x/ave,y/bee,z/coe} 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑏𝑒𝑒) ∧ 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑒𝑒, 𝑐𝑜𝑒) q’ = 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑐𝑜𝑒)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑜𝑏) ∧ 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑎𝑙)

3 = {x/art, y/bob, z/cal}

𝑀𝑜𝑡ℎ𝑒𝑟(𝑎𝑣𝑒, 𝑏𝑒𝑒)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑢𝑑)

q’ = 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑐𝑎𝑙)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑜𝑒)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑢𝑑)

4 = {x/art, y/bob, z/coe} 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑜𝑏) ∧ 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑜𝑒) q’ = 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟(𝑏𝑒𝑒, 𝑐𝑎𝑙)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)

𝐹𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)

𝑃𝑎𝑟𝑒𝑛𝑡 𝑥, 𝑦 ∧ 𝑃𝑎𝑟𝑒𝑛𝑡 𝑦, 𝑧 → 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑧)

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑐𝑜𝑒) ?

Ví dụ - cây suy diễn

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑐𝑎𝑙)

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑐𝑜𝑒)

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑐𝑎𝑙)

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑣𝑒, 𝑐𝑜𝑒)

𝑃𝑎𝑟𝑒𝑛𝑡 𝑎𝑣𝑒, 𝑏𝑒𝑒

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑏𝑢𝑑) 𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑎𝑙)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝑃𝑎𝑟𝑒𝑛𝑡 𝑏𝑒𝑒, 𝑐𝑜𝑒

𝑃𝑎𝑟𝑒𝑛𝑡 𝑏𝑒𝑒, 𝑐𝑎𝑙

𝑀𝑜𝑡ℎ𝑒𝑟 𝑎𝑣𝑒, 𝑏𝑒𝑒

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝑀𝑜𝑡ℎ𝑒𝑟 𝑏𝑒𝑒, 𝑐𝑜𝑒

𝑀𝑜𝑡ℎ𝑒𝑟 𝑏𝑒𝑒, 𝑐𝑎𝑙

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑢𝑑)

Suy diễn lùi (Backward Chaining)

function FOL − BC − ASK(KB, goals, θ) returns tập các phép thay thế

inputs:

𝐾𝐵 : một cơ sở tri thức 𝑔𝑜𝑎𝑙𝑠: danh sách ở dạng nối liền của câu truy vấn 𝜃: phép thay thế hiện tại, được khởi tạo rỗng { }

biến cục bộ: ans, một phép thay thế , được khởi tạo rỗng { }

if 𝑔𝑜𝑎𝑙𝑠 là rỗng then return 𝜃 𝑞′ ← 𝑆𝑢𝑏𝑠𝑡 𝜃, 𝑓𝑖𝑟𝑠𝑡 𝑔𝑜𝑎𝑙𝑠 for each 𝑟 trong KB mà r có dạng chuẩn (p1  …  pn → q)

và 𝜃′ ← 𝑈𝑛𝑖𝑓𝑦(𝑞, 𝑞′) thành công

ans  FOL − BC − ASK(KB, [p1,…,pn| REST(goals)],   ’)  ans

return ans

Ví dụ 1

𝑨𝒔𝒌(𝑮𝒓𝒂𝒏𝒅𝑷𝒂𝒓𝒆𝒏𝒕(𝒂𝒓𝒕, 𝒄𝒂𝒍), {})

𝑞′ = 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡 𝑎𝑟𝑡, 𝑐𝑎𝑙 // 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦)  𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧) → 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥 , 𝑧) 𝜃′ = {𝑥/𝑎𝑟𝑡, 𝑧/𝑐𝑎𝑙} 𝐴𝑠𝑘({𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦), 𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡, 𝑧/𝑐𝑎𝑙})

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑦) // 𝐹𝑎𝑡ℎ𝑒𝑟(𝑥2, 𝑦2) → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥2, 𝑦2) 𝜃′ = 𝑥2/𝑎𝑟𝑡, 𝑦/𝑦2 𝐴𝑠𝑘({𝐹𝑎𝑡ℎ𝑒𝑟(𝑥2, 𝑦2), 𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡, 𝑧/𝑐𝑎𝑙, 𝑥2/𝑎𝑟𝑡, 𝑦/𝑦2}}

𝑞’ = 𝐹𝑎𝑡ℎ𝑒𝑟 𝑎𝑟𝑡, 𝑦2 // 𝐹𝑎𝑡ℎ𝑒𝑟(𝐴𝑟𝑡, 𝐵𝑜𝑏) ’ = {𝑦2/𝑏𝑜𝑏} 𝐴𝑠𝑘({𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡, 𝑧/𝑐𝑎𝑙, 𝑥2/𝑎𝑟𝑡, 𝑦2/𝑏𝑜𝑏, 𝑦/𝑦2})

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡 𝑏𝑜𝑏, 𝑐𝑎𝑙 // 𝐹𝑎𝑡ℎ𝑒𝑟 𝑥3, 𝑦3 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥3, 𝑦3) ’ = {𝑥3/𝑏𝑜𝑏, 𝑦3/𝑐𝑎𝑙} 𝐴𝑠𝑘({𝐹𝑎𝑡ℎ𝑒𝑟(𝑥3, 𝑦3)}, {… 𝑥3/𝑏𝑜𝑏, 𝑦3/𝑐𝑎𝑙}  𝑎𝑛𝑠

Ví dụ 1 – Cây suy diễn

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

{𝑥/𝑎𝑟𝑡, 𝑦/𝑐𝑎𝑙, 𝑧/𝑏𝑜𝑏}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑧)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑧, 𝑐𝑎𝑙)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑧)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑧, 𝑐𝑎𝑙)

{𝑥/𝑎𝑟𝑡, 𝑦/𝑐𝑎𝑙}

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑐𝑎𝑙)

Ví dụ 2

𝑨𝒔𝒌(𝑮𝒓𝒂𝒏𝒅𝑷𝒂𝒓𝒆𝒏𝒕(𝒂𝒓𝒕, 𝒛), {}) 𝑞’ = 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑧) // 𝑃𝑎𝑟𝑒𝑛𝑡 𝑥, 𝑦  𝑃𝑎𝑟𝑒𝑛𝑡 𝑦, 𝑧 → 𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑧) ’ = {𝑥/𝑎𝑟𝑡} 𝐴𝑠𝑘({𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦), 𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡})

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑦) // 𝐹𝑎𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦) ’ = {𝑥/𝑎𝑟𝑡} 𝐴𝑠𝑘({𝐹𝑎𝑡ℎ𝑒𝑟(𝑥, 𝑦), 𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡})

𝑞’ = 𝐹𝑎𝑡ℎ𝑒𝑟 𝑎𝑟𝑡, 𝑦 // 𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏) ’ = {𝑥/𝑎𝑟𝑡, 𝑦/𝑏𝑜𝑏} 𝐴𝑠𝑘({𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡, 𝑦/𝑏𝑜𝑏})

𝑞’ = 𝑃𝑎𝑟𝑒𝑛𝑡 𝑏𝑜𝑏, 𝑧 // 𝐹𝑎𝑡ℎ𝑒𝑟 𝑥2, 𝑦2 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥2, 𝑦2) ’ = {𝑥2/𝑏𝑜𝑏, 𝑦2/𝑧}

Ví dụ 2

𝑨𝒔𝒌(𝑮𝒓𝒂𝒏𝒅𝑷𝒂𝒓𝒆𝒏𝒕(𝒂𝒓𝒕, 𝒛), {}) ...........................

𝐴𝑠𝑘({𝐹𝑎𝑡ℎ𝑒𝑟(𝑥2, 𝑦2)}, {… 𝑥2/𝑏𝑜𝑏, 𝑦2/𝑧})

𝑞’ = 𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑧) // 𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙) ’ = {𝑧/𝑐𝑎𝑙}

𝐴𝑠𝑘({}, {… 𝑧/𝑐𝑎𝑙})  𝑎𝑛𝑠

// 𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒) ’ = {𝑧/𝑐𝑜𝑒}

𝐴𝑠𝑘({}, {… 𝑧/𝑐𝑜𝑒})  ans

// 𝑀𝑜𝑡ℎ𝑒𝑟 𝑥, 𝑦 → 𝑃𝑎𝑟𝑒𝑛𝑡(𝑥, 𝑦) ’ = {𝑥/𝑎𝑟𝑡} 𝐴𝑠𝑘({𝑀𝑜𝑡ℎ𝑒𝑟(𝑥, 𝑦), 𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)}, {𝑥/𝑎𝑟𝑡}}

𝑞’ = 𝑀𝑜𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑦)  𝑓𝑎𝑙𝑠𝑒

Ví dụ 2 – Cây suy diễn

{𝑥/𝑎𝑟𝑡, 𝑦/𝑏𝑜𝑏, 𝑧/𝑐𝑜𝑒}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑜𝑒)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑐𝑎𝑙)

{𝑥/𝑎𝑟𝑡, 𝑦/𝑏𝑜𝑏, 𝑧/𝑐𝑎𝑙}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑏𝑜𝑏, 𝑧)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑏𝑜𝑏)

{𝑥/𝑎𝑟𝑡, 𝑦/𝑏𝑜𝑏}

𝐹𝑎𝑡ℎ𝑒𝑟(𝑎𝑟𝑡, 𝑦)

𝐹𝑎𝑡ℎ𝑒𝑟(𝑦, 𝑧)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑦)

𝑃𝑎𝑟𝑒𝑛𝑡(𝑦, 𝑧)

{𝑥/𝑎𝑟𝑡}

𝐺𝑟𝑎𝑛𝑑𝑃𝑎𝑟𝑒𝑛𝑡(𝑎𝑟𝑡, 𝑧)

Suy diễn lùi (Backward Chaining)

Tìm kiếm chứng minh bằng cách đệ qui theo chiều sâu: không gian tuyến tính theo kích thước của chứng minh

◦ Giải pháp: Kiểm tra trạng thái hiện tại với mọi trạng thái đang có trong stack

Không đầy đủ do lặp vô tận

◦ Giải pháp: dùng bộ nhớ tạm lưu các mục tiêu con đã duyệt

Không hiệu quả do các mục tiêu con bị lặp lại (cả khi thất bại cũng như thành công)

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.

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

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

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 6: Logic (tiếp theo)

Logic THS. BÙI THỊ DANH

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

Nội dung chính

Hạn chế của logic mệnh đề

Khó biểu diễn

Hạn chế của Logic mệnh đề

Logic bậc nhất (First Order Logic)

Cú pháp: các thành phần cơ bản

Kí hiệu vị từ (Predicate symbol) ◦ Biểu diễn quan hệ (trả lời ‘yes’ hoặc ‘no’)

Kí hiệu hàm (Function symbol) ◦ Biểu diễn cho hàm (Trả về một giá trị)

Cú pháp: các thành phần cơ bản

Hằng (constant)

alice, arithmetic, bob, 2, …

Biến (Variable)

x, y, a, b

Cú pháp

Cú pháp: Lượng từ

Cú pháp: Qui tắc De Morgan cho lượng từ

Cú pháp: Lượng từ với ngôn ngữ tự nhiên

Lượng từ tồn tại (∃): ◦ Một số sinh viên thì biết số học

Cú pháp: ví dụ

Cháu là con của anh em ◦ ∀𝑥∀𝑦 𝑁𝑖𝑒𝑐𝑒𝑁𝑒𝑝ℎ𝑒𝑤 𝑥, 𝑦 ↔ ∃𝑧 𝑆𝑖𝑏𝑙𝑖𝑛𝑔(𝑦, 𝑧) ∧ 𝐶ℎ𝑖𝑙𝑑(𝑥, 𝑧)

Cú pháp: ví dụ

Cú pháp: bài tập

Cú pháp: bài tập

Ngữ nghĩa

Ngữ nghĩa

Propositionalization

Phương pháp suy dẫn

Phép thay thế (substitution)

Phép đồng nhất (unification)

Phương pháp suy dẫn

Hợp giải với KB ở dạng CNF

Chuyển về dạng CNF

Chuyển về dạng CNF

Hợp giải

Ví dụ 1

KB

Ví dụ 2

Bước

Suy dẫn

Công thức ¬𝑃(𝑥) ∨ 𝑄(𝑥)

Ví dụ 3

Ví dụ 3

Ai là ông của Coe?

Bước

Công thức

Suy dẫn

Bài tập 1

Nono là một kẻ thù của nước Mỹ

Bài tập 1

Bài tập 1

Bài tập 2

Bài tập 2

Bài tập 2

Suy diễn với KB ở dạng Horn

Suy diễn tiến (forward chaining)

function FOL − FC − ASK(KB, 𝛼) returns phép thay thế hoặc false

repeat until 𝑛𝑒𝑤 là rỗng

𝑛𝑒𝑤 ← { } for each công thức 𝑟 trong 𝐾𝐵 do

Chuẩn hóa r 𝑡ℎà𝑛ℎ 𝑝1 ∧ ⋯ ∧ 𝑝𝑛 → 𝑞 for each 𝜃 sao cho (p1 …  pn)= (p’1 …  p’n) do

Với p’1,…, p’n nào đó trong KB

𝑞′ ← 𝑆𝑢𝑏𝑠𝑡(𝜃, q) if 𝑞′ không phải là một câu đã có trong KB hay 𝑛𝑒𝑤 then

if  thành công then return 

return false

Ví dụ

Ví dụ

Ví dụ

Ví dụ - cây suy diễn

Suy diễn lùi (Backward Chaining)

inputs:

biến cục bộ: ans, một phép thay thế , được khởi tạo rỗng { }

ans  FOL − BC − ASK(KB, [p1,…,pn| REST(goals)],   ’)  ans

Ví dụ 1

Ví dụ 1 – Cây suy diễn

Ví dụ 2

Ví dụ 2

𝑨𝒔𝒌(𝑮𝒓𝒂𝒏𝒅𝑷𝒂𝒓𝒆𝒏𝒕(𝒂𝒓𝒕, 𝒛), {}) ...........................

Ví dụ 2 – Cây suy diễn