Bài giảng Logic học - Chương 7: Logic vị từ

Chương 7: Logic vị từ

Giảng viên: Nguyễn Văn Hòa

Khoa CNTT - ĐH An Giang

1

Nội dung

 Logic bậc nhất (First Order Logic – FOL)

 Cú pháp và ngữ nghĩa

 Các lượng từ

 Hợp giải với logic vị từ

 Dạng mệnh đề

 Lập trình logic Turbo Prolog

2

Tại sao sử dụng logic vị từ

 Logic mệnh đề chỉ xử lý trên các sự kiện, là các

khẳng định có giá trị đúng hoặc sai

 Logic vị từ (logic bậc nhất) cho phép chúng ta nói về

các đối tượng, tính chất của chúng, quan hệ giữa

chúng, phát biểu về một hay tất cả các đối tượng nào

đó mà không cần liệt kê trong chương trình

 Các câu không thể biểu diễn bằng logic mệnh đề

nhưng có thể biểu diễn bằng logic vị từ

 Socrates là người nên socrates phải chết

3

Cú pháp của logic vị từ

 Term (Tham chiếu đối tượng)

 Ký kiệu bằng: Lan, Tuan, DHAG

 Biến: x, y, a

 Ký hiệu hàm áp dụng cho một hay nhiều term: f(x),

tuoi(Lan), sinh-vien(Tuan)

 Câu:

 Một ký hiệu vi từ (predicate) áp dụng cho một hay nhiều

term: thuoc(Lan, DHAG), la-anh-em(Lan,Tuan)…

 t1=t2

 Nếu x là biến và  là câu thì x , x  cũng là câu

 Các câu tạo từ các câu khác với phép nối câu    →

4

Ngữ nghĩa của logic vị từ

 Có một tập ngầm định U các đối tượng mà một câu

FOL phát biểu trên đó, U được gọi là tập phát biểu

 Term tham chiếu đến đối tượng trong U

 Hằng tham chiếu đến một đối tượng cụ thể

 Biến tham chiếu đến một đối tượng nào đó (cần lượng từ hóa)

 Hàm tham chiếu đối một đối tượng thông qua đối tượng khác

 Câu là phát biểu trên các đối tượng

 Vị từ thể hiện tính chất, hoặc quan hệ giữa các đối tượng

 Lượng từ giúp phát biểu số lượng đối tượng: , 

5

Lượng từ với mọi

 Cú pháp:  <biến> <câu>

 Sinh viên CNTT thì thông minh

x sinhvien(x, CNTT) → thongminh(x)

 x P đúng trong một miềm phát biểu U, nếu và chỉ

nếu P đúng với mọi x thuộc U

 Nghĩa là tương đương với phép nối liền () của các

đối tượng trong U

sinhvien(Lan, CNTT) → thongminh(Lan)

 sinhvien(Tuan, CNTT) → thongminh(Tuan)

 sinhvien(Nam, CNTT) → thongminh(Nam)

6

Lượng từ tồn tại

 Cú pháp:  <biến> <câu>

 Sinh viên CNTT thì thông minh

 x sinhvien(x, CNTT) → thongminh(x)

 x. P đúng trong một miềm phát biểu U, nếu và

chỉ nếu P đúng với một x thuộc U

 Nghĩa là tương đương với phép nối rời () của

các đối tượng trong U

sinhvien(Lan, CNTT) → thongminh(Lan)

 sinhvien(Tuan, CNTT) → thongminh(Tuan)

 sinhvien(Nam, CNTT) → thongminh(Nam)

7

Viết FOL

 Mèo là động vật có vú

∀x.Mèo(x) → Động-vật-có-vú(x)

 Lan là sinh viên học giỏi

Sinh-viên(Lan) ∧ Học-giỏi(Lan)

 Cháu là con của anh em

∀x,y.Cháu(x,y) ↔ ∃z.(Anh-em(z,y) ∧ Con(x,z))

 Bà ngoại là mẹ của mẹ

∀x, ∃y. Bà-ngoại(x,y) ↔ ∃z.(Mẹ(x,z) ∧ Mẹ(z,y))

 Mọi người đều yêu ai đó

∀x, ∃y.Yêu(x, y)

8

Chứng minh và suy dẫn

 Suy dẫn xuất pháp từ khái niệm tổng quát của

phép “kéo theo”

 Không thể tính toán trực tiếp từ cách liệt kê

 Do đó ta sẽ phải làm theo cách chứng minh

 Trong FOL, nếu KB suy dẫn được S thì sẽ có một

tập hữu hạn chứng minh của s từ KB

9

Hợp giải bậc nhất

Tam đoạn luận:

x , P(x) → Q(x)

P(A)

Mọi người đều chết

Socrate là người

Socrate chết

Hai vấn đề mới đặt ra:

.Biến đổi FOL thành dạng

mệnh đề (clausal form)

.Hợp giải biến

Q(A)

x, P(x)  Q(x)

Tương đương theo

định nghĩa của phép

Suy ra

P(A)

Q(A)

P(A)  Q(A)

P(A)

Thay A vào x, dẫn đúng

khi đó

Q(A)

Hợp giải mệnh đề

10

Dạng mệnh đề (clausal form)

 Cấu trúc ngoài giống CNF

 Không có lượng từ

x. y. P(x)  R(x,y)

P(x)  R(x,F(y))

11

Biến đổi về dạng mệnh đề

 Câu sau được dùng làm ví dụ trong thủ tục đưa về

clause form.

 “All Romans who know Marcus either hate Caesar

or think that anyone who hates anyone is crazy”

  X: [roman(X) ^ know(X, Marcus)] →

[hate(X, Ceasar) v

( Y:  Z: hate(Y,Z) → thinkcrazy(X,Y))]

12

Biến đổi về dạng mệnh đề…

1. Loại bỏ →

dùng tương đương: a→b = ¬a v b

 Ví dụ

  X: [roman(X) ^ know(X, Marcus)] →

[hate(X, Ceasar) v

( Y:  Z: hate(Y,Z) → thinkcrazy(X,Y))]

  X: ¬[roman(X) ^ know(X, Marcus)] v

[hate(X, Ceasar) v

( Y:  Z: hate(Y,Z) → thinkcrazy(X,Y))]

13

Biến đổi về dạng mệnh đề…

2. Thu giảm tầm vực của ¬ vào đến mức term.

 Dùng tương đương:

¬(¬p) = p

 De Morgan:

¬(a v b) = ¬a ^ ¬b

¬(a ^ b) = ¬a v ¬b

 Tương đương lượng từ:

¬  X: P(X) =  X: P(X)

¬ : P(X) =  X: P(X)

 Áp dung cho ví dụ trước

  X: [¬roman(X) v ¬know(X, Marcus)] v [hate(X,Ceasar)

v

( Y:  Z: ¬hate(Y,Z) v thinkcrazy(X,Y))]

14

Biến đổi về dạng mệnh đề…

3. Chuẩn hoá các biến để các lượng từ chỉ ràng buộc

1 biến duy nhất.

 Biến đổi như VD sau:

 X: P(X) v  X: Q(X) =  X: P(X) v  Y: Q(Y)

4. Chuyển lượng từ về bên trái. Chú ý, không

chuyển thứ tự của chúng

 Ví dụ: tiếp bước 2.

 X:  Y:  Z: [¬roman(X) v ¬know(X, Marcus)] v

[hate(X, Ceasar) v

(¬hate(Y,Z) v thinkcrazy(X,Y))]

15

Biến đổi về dạng mệnh đề…

 5. Loại bỏ lượng từ tồn tại : Sử dụng hàm skolem

 Hàm skolem:

 X:  Y:  Z : P(X,Y,Z) =  X:  Y: P(X,Y,f(X,Y))

 Biến của lượng từ tồn tại được thay là hàm theo những biến

của lượng từ với mọi trước nó

 Bỏ qua các lượng từ (với mọi) còn lại ở bước 5. xem như

mọi biến đều bị tác động bởi lượng từ với mọi ( )

 Ví dụ: tiếp bước 4

[¬roman(X) v ¬know(X, Marcus)] v [hate(X, Ceasar) v

(¬hate(Y,Z) v thinkcrazy(X,Y))]

16

Biến đổi về dạng mệnh đề…

7. Chuyển hội chuẩn (Conjunctive Normal Form - CNF)

 Một chuỗi các mệnh đề kết nối nhau bằng quan hệ AND (^).

Mỗi mệnh đề có dạng một tuyển OR (v) của các biến mệnh đề.

 Dùng phép phân phố giữa v và ^

 Dạng thường gặp:

(a ^ b) v c = (a v c) ^ (b v c)

(a ^ b) v (c ^ d) = (a v c) ^ (a v d) ^ (b v c) ^ (b v d)

 Ví dụ: tiếp bước 6

¬roman(X) v ¬know(X, Marcus) v

hate(X, Ceasar) v ¬hate(Y,Z) v thinkcrazy(X,Y)

17

Biến đổi về dạng mệnh đề…

8. Tách riêng các clause trong CNF ở trên

 Nếu có clause form:

(a v ¬b) ^ (¬a v c v d) ^ (a v ¬c v e)

 Thì được tách riêng thành các clause:

1. (a v ¬b)

2. (¬a v c v d)

3. (a v ¬c v e)

 Đưa các lượng từ về từng clause

 ( X: P(X) ^ Q(X) ) =  X: P(X) ^  X: Q(X)

18

Giới thiệu về ngôn ngữ Prolog

 Cấu trúc chương trình

 Ngôn ngữ Prolog là ngôn ngữ lập trình suy luận trên cơ

sở logic toán học để giải quyết các bài toán trong lĩnh

vực trí tuệ nhân tạo.

 Đặc điểm của ngôn ngữ là xử lý tri thức của các bài

toán được mã hóa bằng ký hiệu.

 Một điểm mạnh khác của ngôn ngữ là xử lý danh sách

trên cơ sở xử lý song song và đệ qui với các thuật toán

tìm kiếm.

 Ngôn ngữ cho phép liên kết với các ngôn ngữ khác như

C, Pascal và Assembler.

19

Giới thiệu về ngôn ngữ Prolog

 Cấu trúc chương trình (tt)

Domains

/* domain declarations*/

Predicates

/* predicate declarations */

clauses

/*clauses ( rules and facts) */

goal

/*subgoal_1

subgoal_2 */

20

Bài giảng Logic học - Chương 7: Logic vị từ - Nguyễn Văn Hòa