Bài giảng Hệ chuyên gia (Expert System): Chương 2.3 - PGS.TS. Phan Huy Khánh

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:69

Thêm vào BST

Báo xấu

91
lượt xem 8
download

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

Chương 2.3 của bài giảng Hệ chuyên gia trang bị cho người học những hiểu biết về lôgic vị từ bậc một. Sau khi học xong chương này người học có thể biết cách biểu diễn tri thức nhờ logic vị từ bậc một. Mời các bạn cùng tham khảo.

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 Hệ chuyên gia (Expert System): Chương 2.3 - PGS.TS. Phan Huy Khánh

Hệ chuyên gia (Expert System) PGS.TS. Phan Huy Khánh khanhph@vnn.vn Chương 2 Biểu diễn tri thức nhờ logic vị từ bậc một 2.3
Chương 2 Biểu diễn tri thức nhờ logic vị từ bậc một a Phần 2.3 : V Lôgic vị từ bậc một V Biểu diễn tri thức nhờ logic vị từ bậc một 2/69
Limitations of Propositional Logic 2 a Can't directly talk about properties of individuals or relations between individuals V E.g., how to represent the fact that John is tall? a We have no way to conclude that John is good at basketball! a Generalizations, patterns, regularities can't easily be represented V E.g., all triangles have 3 sides 3/69
Predicate Logic Overview a Predicate Logic V Principles V Objects V Relations V properties a Syntax a Semantics a Extensions and Variations a Proof in Predicate Logic a Important Concepts and Terms 4/69
Alphabet Constants Constants Variale Variale Function Function Predicate Predicate PP00 Connective Connective Quantifier Quantifier Delimiters Delimiters a..z a..z A..Z A..Z ff gg hh PP Q Q RR ¬ ¬ ∧∧ ∨∨ → →↔↔ ∀ ∀ ∃∃ ,, (( )) Term Term ttii Atom Atom PP Q Q RR Term Term f(t f(t11,, …t …tnn)) Atom Atom P(t P(t11,, …t …tnn)) Wff Wff P∧ Q→ P∧ Q → RR Wffff W ∃X ∃X ∀Y ∀Y (P(X, Y) → (P(X, Y) → R(Y)) R(Y)) 5/69
Bảng ký hiệu (Alphabet) a Bảng ký hiệu để xây dựng các biểu thức đúng gồm : V Các dấu phân cách (separator signs) : dấu phẩy ( , ), dấu mở ngoặc ( ( ) và dấu đóng ngoặc ( ) ) V Các hằng (constant) : có dạng chuỗi sử dụng các chữ cái in thường a..z Ví dụ : a, block V Các biến (variable) : có dạng chuỗi sử dụng các chữ cái in hoa A..Z Ví dụ : X, NAME. V Các vị từ (predicate) : được viết tương tự các biến, sử dụng các chữ cái in hoa A..Z Ví dụ : ISRAINING, ON(table), P(X, blue), BETWEEN(X, Y, Z) 6/69
Bảng ký hiệu (Alphabet) a Các phép nối logic (logical connector) : V ¬, ∧, ∨, → và ↔ tương ứng với các phép phủ định, và, hoặc, kéo theo và kéo theo lẫn nhau (tương đương) a Các dấu lượng tử V ∃ lượng tử tồn tại (existential quantifier) V ∀ lượng tử toàn thể (universal quantifier) 7/69
Names a Constants are used to name existing objects: V The interpretation identifies the object in the real world V No constant can name more than one object V An object can have more than one name or no name at all Gaius Tiberius Sempronius Sempronius Honest Abe Gracchus Gracchus Lincoln a Variables: Leonard Euler V = {X, Y, Z, …} 8/69
BNF Grammar Predicate Logic → | ( ) | , ... | ¬ → (, ...) | = → (, ...) | | → ∧|∨|→|↔ → ∀| ∃ → a, b, c, max, carl, jim, jack → A, B, C, X1 , X2, COUNTER, POSITION → father-of, square-position, sqrt, cosine → P, Q, LARGER, BETWEEN, YOUNGER-THAN Ambiguities are resolved through precedence or parentheses 9/69
First Order Predicate Logics Syntax term ::= variable | function_symbol_of_arity_n(t1, …, tn) n>0 | function_symbol_of_arity_0 constant atom ::= predicate_symbol_of_arity_n(t1, …, tn) n>0 | predicate_symbol_of_arity_0 constant literal ::= atom positive literal | ¬ atom negative literal wff ::= atom well formed formula (sentence) | (¬ wff) negation | (wff ∧ wff) conjunction | (wff ∨ wff) disjunction | (wff → wff) implication | (wff ↔ wff) equivalence | (∀ variable wff) universal formula | (∃ variable wff) existential formula 10/69
Các hàm (function) a Các hàm : V có cách viết tương tự các hằng V sử dụng các chữ in thường a..z V Mỗi hàm có bậc (hay số lượng các đối) cố định, là một số nguyên dương a Ví dụ : V f(X), weight(elephan), successor(M, N) là các hàm có bậc lần lượt là 1, 1, và 2 a Người ta quy ước rằng : V Các hằng là những hàm bậc không (nil) V Ví dụ : a, elephan, block là các hằng 11/69
Function Symbols a Function symbols V function_name(arg1, arg2, …, argn) V Identifies the object referred to by a tuple of objects V May be defined implicitly through other functions, or explicitly through tables a Function names begin with a lowercase letter or are expressed with a symbol V F = {f, g, h, …} = F0 ∪ F1 ∪ F2 ∪ … a Function arities: V F0: function symbols of arity 0 (constants): a, b, max, jim V F1: function symbols of arity 1 (one argument) V F2: function symbols of arity 2 (two arguments) V … 12/69
Functions Examples a A function is used to express complex names V age(max) Max’s age V password(claire) Claire’s password a A function may be nested V Max’s age’s double double(age(max)) V father(mother(max)) Max’s mother’s father V starship(son(dr_crusher)) Dr_Crusher’s son’s starship a A function is never a predicate V Can’t nest predicates TALL(TALL(max)) a Function symbols of arity >1 V youngestChild(max, ann) Max and Ann’s youngest child V *(5, +(2, 4)) 30 a A predicate forms a sentence, while a function names an individual 13/69
Hạng, hay hạng tử (term) a Hạng được tạo thành từ hai luật sau : V Các hằng và các biến là các hạng V Nếu f là một hàm có bậc n ≥ 1 và nếu t1,..., tn đều là các hạng, thì hàm f (t1,..., tn) cũng là một hạng a Ví dụ các hàm sau đây đều là các hạng : V successor(X, Y), weight(b), successor(b, wight(Z)) a Nhưng các hàm sau đây không phải là hạng : V P(X, blue) vì P là vị từ V weight (P(b)) vì P(b) không phải là hạng (vị từ không làm đối cho hàm) 14/69
Predicates a Predicate symbols : V PREDICATE(arg1, arg2, …, argn) V A (determinate) property possessed by an object: Shape, Size V A (determinate) relationship among objects: Shape relationship, size relationship, positional relationship… V The number of arguments is called the predicate’s arity V The order of the arguments is important a Predicates have names beginning with an uppercase letter or are represented by an operator symbol V P = P0 ∪ P1 ∪ P2 ∪ … a Predicate arities: P0: predicate symbols of arity 0 (constants: proposition) : P, Q, R, … P1: predicate symbols of arity 1 (one argument) P2: predicate symbols of arity 2 (two arguments) … 15/69
Nguyên tử (atom) a Nguyên tử được tạo thành từ hai luật sau : V Các mệnh đề (vị từ bậc 0) là các nguyên tử V Nếu P là một vị từ bậc n (n ≥ 1) và nếu t1,..., tn đều là các hạng, thì P(t1,..., tn) cũng là một nguyên tử a Ví dụ các vị từ sau đây là các nguyên tử : V P(X, blue), EMPTY, BETWEEN(table, X, sill(window)) a Còn : V successor (X, Y, sill (window) không phải nguyên tử, mà là các hàm 16/69
Atomic Sentences a A atomic sentence: V Expressesa claim that is either true or false V Formed by a single predicate followed by one or more arguments a Example: V Max is tall TALL(max) V A is larger than B LARGER(A, B) V B is not larger than A ¬LARGER(B, A) V C is smaller than D, or D is not smaller than C SMALLER(C, D), ¬SMALLER(D, C) V A is between B and E: BETWEEN(A, B, E) 17/69
Các công thức chỉnh a Các công thức chỉnh (CTC) được tạo thành từ ba luật sau : V Các nguyên tử là các CTC V Nếu G và H là các CTC, thì (¬G), (G ∧ H), (G ∨ H), (G → H) và (G ↔ H) cũng là các CTC được tạo thành từ G và H V Nếu G là một CTC và X là một biến, thì (∃X)G và (∀X)G cũng là các CTC a (∃X)G được đọc là : V Tồn tại biến X sao cho G được thoả mãn a (∀X)G được đọc là : V Với mọi biến X thì G đều được thoả mãn 18/69
Bài tập ở lớp : Chuyển thành vị từ a Ai đủ 18 tuổi mới được phép lái xe a Gái đủ 18 tuổi, trai 20 tuổi mới được phép lập gia đình a Kiểm tra hồ sơ V Nhập học tại các trường ĐH, CĐ V Sản phẩm V Quy trình công nghệ... Mần reng tui lấy ví dụ ? 1. Xác định không gian các sự kiện, nhân vật thật liên quan 2. Tìm các hằng, biến, hàm và/hoặc vị từ tương ứng với các phát biểu 3. Gán nghĩa cho tứng thành phần để kiểm tra tính đúng đắn 4. Nhận kết quả 19/69
Well-formed Formula (wff) a Any atomic sentence is a wff a If A are B are wffs then so are ¬A A∧B A∨B A→B A↔B a B is a cube or B is large (a large cube): CUBE(B) ∨ LARGE(B) a E and C are in the same row and E is in back of B: SAMEROW(E, C) ∧ BACKOF(E, B) 20/69