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

Chia sẻ: Adadf Adaf | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST

Báo xấu

167
lượt xem 21
download

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

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

Chủ đề:

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

Lưu

Nội dung Text: 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ều Predicate 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 =1 Predicate 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 holds Predicate 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 định Predicate 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à F Predicate 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à free Predicate 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 T Predicate 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 ra Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Ví dụ thứ tự khác nhau Ví dụ: ∀x∀y(x + y = y + x) Tvới tất cả x, y ∈ Ê Ví dụ: ∀x∃y(x + y = 0) là T, trong khi ∃y∀x(x + y = 0) là F Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Diễn giải ý nghĩa (1) Ví dụ: ∀x∀y(x + y = y + x), x, y ∈ Ê x + y = y + x với tất cả các số thực Ví dụ: ∀x∃y(x + y = 0), x, y ∈ Ê Với mọi số thực x, tồn tại số thực y thỏa mãn x + y = 0 Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Diễn giải ý nghĩa (2) Diễn giải phát biểu sau: ∀x(C(x) ∨ ∃y(C(y) ∧ F (x, y)))) Trong đó: • C(x): x có máy tính • F (x, y): x, y là bạn • x, y ∈ tất cả sinh viên trong trường Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Diễn giải ý nghĩa (2) Diễn giải phát biểu sau: ∀x(C(x) ∨ ∃y(C(y) ∧ F (x, y)))) Trong đó: • C(x): x có máy tính • F (x, y): x, y là bạn • x, y ∈ tất cả sinh viên trong trường Với mọi sinh viên x trong trường, hoặc x có máy tính, hoặc tồn tại sinh viên y có máy tính và sinh x, y là bạn. Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Diễn giải ý nghĩa (3) Diễn giải phát biểu sau: ∃x∀y∀z(((F (x, y) ∧ F (x, z) ∧ (y = z)) → ¬F (y, z))) Trong đó: • F (x, y): x, y là bạn • x, y, z ∈ tất cả sinh viên trong trường Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Diễn giải ý nghĩa (4) Diễn giải phát biểu sau: ∃x∀y∀z(((F (x, y) ∧ F (x, z) ∧ (y = z)) → ¬F (y, z))) Trong đó: • F (x, y): x, y là bạn • x, y, z ∈ tất cả sinh viên trong trường Tồn tại một sinh viên x, sao cho với mọi sinh viên y, với mọi sinh viên z khác y, nếu x là bạn của y và x là bạn của z thì y, z không là bạn của nhau. Predicate logic (Logic vị từ) 2008-2009
TS. Trần Văn Hoài Hình thức hóa ngôn ngữ (1) (1) "Có sinh viên nào đó trong lớp đã tham quan Hà Nội" (2) "Mọi sinh viên trong lớp đã thăm Nha Trang hoặc Vũng Tàu" Nếu ta đặt câu: C(x): x đã thăm Hà Nội D(x): x đã thăm Nha Trang E(x): x đã thăm Vũng Tàu Ta có: (1): ∃xC(x) (2): ∀x(D(x) ∨ E(x)) Predicate logic (Logic vị từ) 2008-2009