Xem mẫu
- 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
nguon tai.lieu . vn
