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

Chia sẻ: Bạch Đăng Kỳ | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

37
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng - Chương 5: Logic có nội dung trình bày tổng quan về logic, logic mệnh đề, ngôn ngữ logic, các thành phần của hệ thống logic,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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 2
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. 1879, logic mệnh đề hiện đại được phát triển bởi Gottlob Frege 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 heuristic chứng minh 38 định lí trong số 52 định lý trong cuốn “Principa Mathematica” Allen Newell 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 3
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 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ó ◦ 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. Ưu điểm của logic là cung cấp sự diễn đạt ý nghĩa và súc tích 4
Ứ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 5
Ngôn ngữ tự nhiên Ví dụ: ◦ Một hào tốt hơn đồng 5 xu ◦ Đồ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 xu tốt hơn là không có gì ◦ 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 ?!? 6
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. Các loại ngôn ngữ logic: ◦ Logic mệnh đề (propositional logic) ◦ Logic vị từ (predicate logic): logic bậc nhất ◦… 7
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 8
Các thành phần của hệ thống logic Cú pháp (syntax) Ngữ nghĩa (Semantic) Công thức (formula) Mô hình(models) PP suy dẫn (entailment methods) 9
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 ∧ 𝑊𝑒𝑡 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) ◦ Ví dụ: Wet 0 1 0 Rain 1 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. 10
Nội dung chính Tổng quan Logic mệnh đề Logic bậc nhất 11
Các thành phần của hệ thống logic Cú pháp (syntax) Ngữ nghĩa (Semantic) Công thức (formula) Mô hình(models) PP suy dẫn (entailment method) 12
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ếu 𝛼 và 𝛽 là công thức thì các định nghĩa đệ qui đây cũng là công thức: ◦ Phủ định: ¬𝛼 ◦ Nối liền (conjunction): α ∧ β ◦ Nối rời (disjunction): α ∨ 𝛽 ◦ Kéo theo (implication): α → 𝛽 ◦ Tương đương (biconditional): α ↔ 𝛽 13
Một số ví dụ Công thức: ◦𝐴 ◦ ¬𝐴 ◦ ¬𝐵 → 𝐶 ◦ ¬𝐴 ∧ ¬𝐵 → 𝐶 ∨ ¬𝐵 ∨ D ◦ ¬¬𝐴 Không phải công thức: ◦ 𝐴¬𝐵 ◦ 𝐴+𝐵 14
Các thành phần của hệ thống logic Cú pháp (syntax) Ngữ nghĩa (Semantic) Công thức (formula) Mô hình(models) PP suy dẫn (entailment method) 15
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ụ: ◦ Có 3 kí hiệu mệnh đề: A, B và C ◦ Có 23 = 8 mô hình tương ứng: A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 16
Ngữ nghĩa 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ả α ◦ 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) Trường hợp đệ qui: với hai công thức 𝛼 và 𝛽 bất kì, ta có: 𝐼(𝛼, w) 𝐼(𝛽, w) 𝐼(¬𝛼, w) 𝐼(𝛼 ∧ 𝛽, w) 𝐼(𝛼 ∨ 𝛽, w) 𝐼(𝛼 → 𝛽, w) 𝐼(𝛼 ↔ 𝛽, w) 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 17
Ví dụ Cho công thức: α = (¬A ∧ B) ↔ 𝐶 Và mô hình w = A: 1, B: 1, C: 0 Hàm phiên dịch: I 𝛼, w = 1 ◦ I ¬A, 𝑤 = 0 ◦ 𝐼 ¬A ∧ B, 𝑤 = 0 ◦ I ¬A ∧ B ↔ 𝐶, w = 0 18
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 19
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 20