ĐỐI SÁNH MẪU VÀ PHÉP HỢP NHẤT

Phép hợp nhất

Phép hợp nhất (unification) là một thuật toán dùng để xác định những phép thế cần thiết để làm cho hai biểu thức vị từ đối sánh (match) nhau.

Hợp nhất và các luật suy diễn khác như Modus ponens cho phép chúng ta tạo ra các suy diễn dựa trên một tập hợp các khẳng định logic. Phép hợp nhất phức tạp do có thể thay thế một biến với bất kỳ mục nào gồm cả những biến và những biểu thức hàm khác với độ phức tạp tùy ý. Những biểu thức này tự thân chúng lại có thể chứa các biến.

Thí dụ 2.11: Đối sánh foo(X,a,goo(Y)) với:

foo(X,b,foo(Y)) không đối sánh

foo(X,Y) không đối sánh

moo(X,a,goo(Y)) không đối sánh

foo(fred,a, goo(Z)) {fred/X, Z/Y}

foo(W,a,goo(jack)) {W/X,jack/Y}

foo(Z,a,goo(moo(Z))) {Z/X,moo(Z)/Y}

Nói chung một quá trình giải quyết vấn đề sẽ đòi hỏi nhiều suy diễn và do đó cần nhiều phép hợp nhất nói tiếp nhau. Các chương trình giải quyết vấn đề logic phải duy trì tính nhất quán của các phép thế biến. Điều này được phát biểu trong giải thuật đối sánh mẫu.

Giải thuật đối sánh mẫu

Hằng / hằng đối sánh : chỉ khi chúng giống hệt nhau

Hằng a / biến X đối sánh:

• Biến chưa kết buộc: biến trở thành kết buộc với hằng {a/X}
• Biến đã kết buộc : xem (1)

Biến / biến đối sánh:

• Hai biến chưa kết buộc: luôn luôn đối sánh
• Một biến kết buộc và một biến chưa kết buộc: xem (2)
• Hai biến kết buộc: xem (1)

Biểu thức / biểu thức đối sánh: chỉ khi các tên hàm hoặc vị từ, số ngôi giống nhau thì áp dụng đối sánh từng đối số một.

Lưu ý : Phạm vi của một biến là một câu. Một khi biến đã bị kết buộc, các phép hợp nhất theo sau và các suy luận kế tiếp phải giữ sự kết buộc này.

Câu hỏi :

Ứng dụng : Chương trình tư vấn tài chính

Họat động của chương trình là trợ giúp người dùng trong việc quyết định có nên đầu tư vào một tài khoản tiết kiệm hay thị trường chứng khoán hay không, một số nhà đầu tư cũng có thể muốn phân bổ số tiền của họ thành hai khoản. Việc đầu tư sẽ được gợi ý cho những nhà đầu tư dựa trên thu nhập của họ và số tiền hiện tại mà họ đã có trong tài khoản tiết kiệm. Hệ làm việc theo các quy tắc sau :

• Các cá nhân không đủ tiền tiết kiệm cần ưu tiên tăng tiền tiết kiệm, bất kể thu nhập là bao nhiêu.
• Các cá nhân có đủ tiền tiết kiệm và đủ thu nhập nên xem xét việc đầu tư mạo hiểm hơn nhưng có khả năng đem lại lợi nhuận hơn vào thị trường chứng khoán.
• Các cá nhân với thu nhập thấp nhưng đủ tiền tiết kiệm có thể chia phần thu nhập thêm vào tiết kiệm và chứng khoán, nhằm làm tăng số tiền tiết kiệm trong khi vẫn muốn tăng thu nhập thông qua chứng khoán.

Sự tương xứng giữa tiền tiết kiệm và thu nhập được xác định bởi số thành viên gia đình mà một cá nhân cần chu cấp. Quy tắc là :

• Tiết kiệm đủ là 5000$/ người phụ thuộc
• Thu nhập đủ 15000$ + (4000$ / người phụ thuộc)

Ta xây dựng hệ thống logic với các câu vị từ như sau:

With: minsavings(X) = 5000 * X minincome(X)=15000+(4000*X)

Để thực hiện một phiên tư vấn, thông tin mô tả về một nhà đầu tư nào đó được bổ sung vào tập hợp các câu vị từ. Chẳng hạn một cá nhân với 3 thành viên phụ thuộc, có số tiền trong tài khoản tiết kiệm là 22.000$ và có thu nhập ổn định là 25.000$ sẽ được mô tả như sau :

• amount_saved(22000)
• earnings(25000,steady)
• dependents(3)

Sử dụng phép hợp nhất và modus ponens, một chiến lược đầu tư đúng đắn người này có thể được rút ra như là một hệ quả logic từ những mô tả này :

Hợp giải (10), (11) với (7) bằng đối sánh {25000/X, 3/Y}, ta có :

income(inadequate)

Hợp giải (9), (11) với (4) bằng đối sánh {22000/X, 3/Y}, ta có :

savings_account(adequate)

Hợp giải (12), (13) với (3) suy ra investment (combination)

Như vậy hình thức đầu tư được tư vấn từ hệ là kết hợp cả việc gởi tiền vào tài khoản tiết kiệm và đầu tư vào chứng khoán.

TỔNG KẾT CHƯƠNG II:

Trong chương này, chúng ta đã được giới thiệu phép tính vị từ như một ngôn ngữ biểu diễn dùng cho việc giải quyết vấn đề trong AI. Chúng ta đã định nghĩa các khái niệm về biến, hàng, hàm, biểu thức, … và ngữ nghĩa của ngôn ngữ này. Dựa trên ngữ nghĩa của phép tính vị từ, các luật suy diễn cũng cho phép suy diễn các câu từ một tập hợp các biểu thức cho trước. Phần cuối chương định nghĩa một thuật toán hợp nhất và đối sánh mẫu dùng xác định các phép thay thế biến làm cho hai biểu thức đối sánh nhau, một ví dụ minh họa ứng dụng cụ thể cho giải thuật này là bài toán hệ tư vấn tài chính. Trong chương tiếp theo, lý thuyết và những kỹ thuật tìm kiếm trên không gian trạng thái bài toán sẽ được giới thiệu.

Bài tập chương II

Jane có bốn thành viên gia đình phụ thuộc, thu nhập bằng lương hàng tháng là 30.000$ và tài khoản tiết kiệm của cô ta là 20.000$. Hãy đưa ra các vị từ thích hợp mô tả tình trạng tài chính của Jane cho chương trình tư vấn tài chính và tiến hành các phép hợp nhất, suy diễn cần thiết để xác định phương thức đầu tư thích hợp cho cô ta.

Chuyển các câu sau đây thành câu trong logic vị từ:

• Tất cả các con mèo đều là động vật.
• Không có con chó nào là loài bò sát.
• Tất cả các nhà khoa học máy tính đều thích một hệ điều hành nào đó.
• Mọi đứa trẻ đều thích Coca-cola.
• Không có đứa trẻ nào thích ăn rau.
• Một số người thích kẹo, một số khác thì không.
• Không có sinh viên nào học mà thi rớt môn này.

Cho một vấn đề được phát biểu như sau:

• John thích mọi loại thức ăn.
• Táo là thức ăn.
• Gà là thức ăn.
• Tất cả mọi thứ ăn được mà vẫn còn sống thì đó là thức ăn.
• Bill ăn đậu phộng và Bill vẫn còn sống.
• Sue ăn mọi thứ mà Bill ăn.

• Hãy biểu diễn vấn đề trên theo logic vị từ bậc nhất.
• Dùng giải thuật đối sánh mẫu để chứng minh với mọiJohn thích đậu phộngvới mọi

Câu chuyện dưới đây được lấy từ quyển sách Algorithms + Data structures = Programs (Thuật toán + Cấu trúc dữ liệu = Chương trình) của N. Wirth (1976):

với mọiTôi cưới một góa phụ (W), bà ta có một cô con gái đã lớn (D). Cha tôi (F), người thường xuyên đến thăm chúng tôi đã phải lòng cô con riêng của vợ tôi và cưới cô ta. Vì thế cha tôi trở thành con rể tôi và con ghẻ tôi trở thành mẹ tôi. Vài tháng sau đó, vợ tôi sinh một đứa con trai (S₁), nó trở thành em rể của bố tôi, cũng như trở thành chú tôi. Vợ của bố tôi, tức là con ghẻ của tôi, cũng sinh một đứa con trai (S₂).với mọi

Sử dụng phép tính vị từ, hãy tạo ra một tập hợp các biểu thức biểu diễn hoàn cảnh trong câu chuyện trên. Hãy đưa ra các biểu thức định nghĩa các quan hệ gia đình cơ bản như định nghĩa bố vợ chẳng hạn, và sử dụng modus ponens trên hệ này để chứng minh kết luận với mọiTôi cũng chính là ông tôivới mọi.