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 P (x1, x2, . . . , xn) : ∑n 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 ∈ R Mệnh đề: ∃xP (x) là T + Ví dụ: Q(x) = ”x = x+ 1” Miền giá trị x ∈ R 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 ∈ R + 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 ∈ R x+ y = y + x với tất cả các số thực + Ví dụ: ∀x∃y(x+ y = 0), x, y ∈ R 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 6= 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 6= 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 TS. Trần Văn Hoài Hình thức hóa ngôn ngữ (2) "Mọi người đều có một người bạn tốt nhất" Nếu ta đặt câu: • B(x, y): y là bạn tốt nhất của x Ta có: ∀x∃y∀z(B(x, y) ∧ ((y 6= z)→ ¬B(x, z))) Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Hình thức hóa ngôn ngữ (3) "Nếu một người là phụ nữ và là cha mẹ, thì người này là mẹ của ai đó" Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Hình thức hóa ngôn ngữ (3) "Nếu một người là phụ nữ và là cha mẹ, thì người này là mẹ của ai đó" Nếu ta đặt câu: • C(x): x là phụ nữ • D(x): x là cha mẹ • E(x, y): x là mẹ của y Ta có: ∀x((C(x) ∧D(x))→ ∃yE(x, y)) Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Tóm tắt ý nghĩa của lượng từ Phát biểu Khi nào đúng ? Khi nào sai ? ∀x∀yP (x, y) P (x, y) là T Có một cặp x, y làm cho ∀y∀xP (x, y) với mọi x, y P (x, y) là F ∀x∃yP (x, y) Với mọi x, tồn tại y Có một x sao cho P (x, y) làm cho P (x, y) là T là Fvới mọi y ∃x∀yP (x, y) Tồn tại x sao cho Với mọi x, tồn tại y P (x, y) là Tvới mọi y làm cho P (x, y) là F ∃x∃yP (x, y) Tồn tại một cặp x, y P (x, y) là Fvới ∃y∃xP (x, y) sao cho P (x, y) là T mọi x, y Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Phủ định của lượng từ "Mọi sinh viên máy tính đều học môn logic toán" ∀xP (x) "Không phải là mọi sinh viên máy tính đều học môn logic toán" ∃x¬P (x) Phủ định Mệnh đề tương đương ¬∃xP (x) ∀x¬P (x) ¬∀xP (x) ∃x¬P (x) Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Công thức chỉnh dạng + Vị từ theo sau bởi các biến được gọi là công thức nguyên tử (atomic formula) + Công thức chỉnh dạng (wff) được xây dựng như sau: • T, Flà wff • Mệnh đề hoặc biến mệnh đề là wff • Một công thức nguyên tử là wff • Nếu A,B,C là wff thì ¬A, (A∧B), (A∨B), (A→ B), (A↔ B) là wff • Nếu x là biến (trong 1 miền) và A là wff thì ∀xA, ∃xA cũng là wff Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Ví dụ công thức chỉnh dạng + ∀xB(x) là wff + "The capital of Virginia is Richmond" là wff + ∀xB(x)∧∃xR(x) là wff + ∀xB(x)R(x), B(∃x) không là wff Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Từ wff sang mệnh đề + P (x): x không âm • ∀xP (x) là Tnếu universe là {1, 2, 3} • ∀xP (x) là Fnếu universe là {−1, 2, 3} • ∀xQ(x, y) có thể Thay Ftùy theo biến free y (giả thiết Q(x, y) là "x > y") Đặc tả cụ thể của một universe, vị từ, và việc gán giá trị cụ thể với các biến tự do trong wff được gọi là sự giải thích (intepretation) Một wff là mệnh đề khi nó được gán một giải thích Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Những dạng wff + wff là thỏa mãn (satisfiable) nếu tồn tại một giải thích làm wff T Ví dụ: ∀xP (x) là thỏa mãn + wff là hợp lệ (valid) nếu wff đúng với mọi giải thích Ví dụ: ∀xP (x) ∨ ∃x¬P (x) hợp lệ với mọi P và giải thích + wff là không hợp lệ (invalid) hoặc không thỏa mãn (un- satisfiable) nếu không tồn tại một giải thích làm wff T Ví dụ: ∀x(P (x) ∧ ¬P (x)) Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Sự tương đương + Hai wff W1,W2 là tương đương (equivalence) nếu và chỉ nếu W1 ↔ W2 với mọi giải thích Ví dụ: • ∀xP (x)⇔ ¬∃x¬P (x) với mọi P • ∀x(P (x) ∧Q(x))⇔ ∀xP (x) ∧ ∀xQ(x) với mọi P,Q Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Suy diễn trong logic vị từ Tên Luật suy diễn Universial instantiation ∀xP (x)⇒ P (c) c là 1 giá trị trong universe Universial generalization P (c)⇒ ∀xP (x) P (c) là Tvới mọi c trong một universe đang xem xét Existential instantiation ∃xP (x)⇒ P (c) c trong universe và P (c) T Existential generalization P (c)⇒ ∃xP (x) c trong universe Negation ¬∃xP (x)⇔ ∀x¬P (x) Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Ví dụ suy diễn trong logic vị từ A check is void if it has not been cashed for 30 days. This check has not been cashed for 30 days. Therefore this check is void. You can not cash a check which is void. Therefore you can not cash this check. We now have a check which can not be cashed. Predicate logic (Logic vị từ) 2008-2009 TS. Trần Văn Hoài Ví dụ suy diễn trong logic vị từ Đặt: • C(x): x is a check • T (x): x has been cashed within 30 days • V (x): x is void • S(x): x can be cashed • ThisCheck: một check cụ thể tương ứng với "this check" Ta có: (∀x((C(x) ∧ ¬T (x))→ V (x))) ∧ ¬T (ThisCheck)→ V (ThisCheck) ∀x((C(x) ∧ V (x))→ ¬S(x)) ∧ V (ThisCheck)→ ¬S(ThisCheck) C(ThisCheck) ∧ ¬S(ThisCheck)→ ∃x(C(x) ∧ ¬S(x)) Predicate logic (Logic vị từ) 2008-2009