Logic vị từ - TS. Trần Văn Hoài

Biểu diễn tri thức bằng mệnh đề gặp phải một trở ngại cơ bản là ta không thể can thiệp vào cấu trúc của một mệnh đề. Hay nói một cách khác là mệnh đề không có cấu trúc
Nội dung trích xuất từ tài liệu:
Logic vị từ - TS. Trần Văn Hoài TS. Trần Văn Hoài Logic vị từPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Điểm yếu của logic mệnh đề (1) Không thể hiện được các phát biểu có các biến Ví dụ: x=y+3 x>3 Bởi vì các biến chưa có giá trị. Tuy nhiên, phát biểu dạng như trên xuất hiện rất nhiềuPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Điểm yếu của logic mệnh đề (2) Những sự tương đương sau không biểu diễn được bằng logic mệnh đề Không phải tất cả bánh đều ăn được và Chỉ một số bánh ăn được Not all integers are even và Some integers are not even Để suy diễn, mỗi mệnh đề phải được liệt kê riêng lẽPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Logic vị từ Khắc phục các điểm yếu nêu trên Phát biểu x > 3 có 2 phần: • Biến x • Tính chất của biến x (> 3), được gọi là vị từ (predicate) Nói cách khác Predicate là vị từ mô tả tính chất của những đối tượng, hoặc quan hệ giữa chúng Ký hiệu phát biểu P (x) ⇒ P (2), P (4) là mệnh đềPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Ví dụ Xét các câu sau • The car Tom is driving is blue • The sky is blue • The cover of this book is blue Chúng ta có thể có 1 vị từ is blue, viết tắt là B. B(x) nghĩa là x is blue Khi đó, ta có thể biểu diễn các câu như sau • B(The car Tom is driving) • B(The sky) • B(The cover of this book)Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Dạng tổng quát Một phát biểu có n biến x1, x2 , . . . , xn được ký hiệu là P (x1 , x2, . . . , xn ) được gọi là hàm mệnh đề (propositional function) P được gọi là vị từ Ví dụ: P (x, y, z) : x + y = z n P (x1 , x2 , . . . , xn ) : i=1 xi =1Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Vị từ không phải là mệnh đề Phát biểu x > 1 không phải là mệnh đề Để biến x > 1 thành mệnh đề, một trong 2 cách sau phải thực hiện « Gán giá trị cụ thể cho x « Chuyển phát biểu sang dạng There is a number x for which x > 1 hoặc là For every number x, x > 1 holdsPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Lượng từ (quantifier) Gán giá trị cho tất cả các biến của P ⇒ mệnh đề Cách khác là dùng các lượng từ • ∀: với mọi ∀xP (x) = P (x) là Tvới mọi x • ∃: tồn tại ∃xP (x) = Tồn tại x sao cho P (x) là T ⇒ Cần một miền giá trị cho x (universe of discourse) Miền giá trị là tập các đối tượng quan tâm của một biến Mệnh đề chỉ có giá trị Thay Fnếu miền giá trị đã được xác địnhPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Ví dụ toán tử với mọi (∀) Ví dụ: Mọi sinh viên máy tính phải học môn logic P (x) = x phải học môn logic Mệnh đề: ∀xP (x) Ví dụ: Chính xác hơn S(x) = x là sinh viên máy tính P (x) = x phải học môn logic Mệnh đề: ∀x(S(x) → P (x))Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Ví dụ toán tử tồn tại (∃) Ví dụ: P (x) = ”x > 3” Miền giá trị x ∈ Ê Mệnh đề: ∃xP (x) là T Ví dụ: Q(x) = ”x = x + 1” Miền giá trị x ∈ Ê Mệnh đề: ∃xQ(x) là FPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Tầm vực của lượng từ Ký hiệu bởi [] hoặc (), nếu không có thì tầm vực là công thức nhỏ nhất ngay sau lượng từ Biến x là bound nếu • Biến x được gán giá trị • Biến x được lượng từ hóa Biến x là free nếu nó không bound Ví dụ: ¸ ∀xP (x, y) thì x là bound và y là free ¸ ∀x(∃yP (x, y)∨Q(x, y)) thì x, y trong P (x, y) là bound, trong khi y trong Q(x, y) là freePredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Xác định chân trị ∀xP (x) = P (x1 ) ∧ P (x2 ) ∧ . . . ∧ P (xn ) ∃xP (x) = P (x1 ) ∨ P (x2 ) ∨ . . . ∨ P (xn )Trong đó x1, x2 , . . . , xn là liệt kê các giá trị có thể có của x¸ Thử tất cả các xi với ∀ để xác định T¸ Tìm một xi với ∃ để xác định TPredicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Thứ tự các lượng từ Thứ tự của lượng từ là quan trọng, chỉ trừ khi Tất cả các lượng từ là với mọi hoặc tất cả là tồn tại Đọc từ trái sang phải, áp dụng từ trong raPredicate logic (Logic vị từ) 2008-2009 ...