Thạc Sĩ Nghiên cứu các phương pháp biểu diễn tri thức trong lập trình logic

MỞ ĐẦU
Logic tính toán được các nhà logic học đưa ra vào những năm 1950, dựa trên các kỹ thuật tự động hóa quá trình suy diễn logic. Logic tính toán được phát triển thành lập trình logic vào những năm 1970. Từ đó hình thành một khái
niệm quan trọng là lập trình khai báo (declarative programming) đối lập với lập trình cấu trúc (procedural programming). Về ý tưởng, các lập trình viên chỉ cần đưa ra khai báo của chương trình còn việc thực hiện cụ thể do máy tính tự xác lập, trong khi đó việc thực hiện các chương trình hướng thủ tục lại được xác lập cụ thể bởi lập trình viên. Ngôn ngữ Prolog là một công cụ thực hiện rõ ý tưởng này. Chương trình dịch Prolog đầu tiên ra đời đã chứng tỏ đó là một ngôn ngữ thực hành và được phổ biến trên toàn thế giới. Sự phát triển của lập trình logic chính thức bắt đầu vào cuối những năm 1970. Những phát triển xa hơn đạt được vào đầu thập kỷ 80, bắt đầu với sự xuất hiện của quyển sách đầu tiên nói về các cơ sở lập trình logic. Việc lựa chọn lập trình logic làm mô hình cơ sở cho dự án Các hệ thống máy tính đời
thứ 5 của Nhật (Japanese Fifth Generation Computer Systems Project) đã mởmđầu cho sự phát triển của các ngôn ngữ lập trình logic khác. Nhờ khả năng khai báo tự nhiên của lập trình logic, Prolog nhanh chóng trở thành một ứng cử viên cho việc biểu diễn tri thức. Tính đầy đủ của nó trở nên rõ ràng hơn khi mối liên hệ giữa các chương trình logic với cơ sở dữ liệu suy diễn được đưa ra vào giữa thập kỷ 80. Việc sử dụng lập trình logic và cơ sở dữ liệu suy diễn để biểu diễn tri thức được gọi là “cách tiếp cận logic cho việc biểu diễn tri thức”. Cách tiếp cận này dựa trên ý tưởng là chương trình máy tính được cung cấp các đặc thù logic của tri thức trong đó, do đó nó độc lập với bất kỳ cách thực hiện riêng biệt nào, với ngữ cảnh tự do, dễ dàng thao tác và suy diễn.
Chính vì vậy, cú pháp của ngôn ngữ lập trình phải kết hợp được bất kỳ chương trình nào với đặc thù khai báo của nó. Khi đó, việc thực hiện các phương pháp tính toán sẽ thông qua so sánh các thuộc tính cụ thể với cú pháp
khai báo. Việc đưa ra một cú pháp thích hợp cho các chương trình logic được coi như một trong những lĩnh vực nghiên cứu quan trọng nhất và khó nhất trong lập trình logic.
Luận văn này sẽ trình bày các kết quả nghiên cứu về cú pháp và ngữ nghĩa của chương trình logic, bao gồm các lập trình logic thông thường và lập trình logic mở rộng, tiếp đó sẽ đề cập môi trường lập trình logic DLV (Datalog with Vel) và cách thức kết hợp môi trường logic này trong mã nguồn hướng đối tượng Java, cuối cùng trình bày hai bài toán minh họa (bài toán N quân hậu và bài toán Cây khung nhỏ nhất) được cài đặt trên DLV và được chạy trong mã nguồn hướng đối tượng Java.
MỤC LỤC
MỞ ĐẦU 3
Chương 1 CHƯƠNG TRÌNH LOGIC TỔNG QUÁT 5
1.1 Mở đầu
1.2 Biểu diễn tri thức trong chương trình logic tổng quát
1.3 Câu trả lời cho truy vấn
1.4 Một số ngữ nghĩa khác của chương trình logic tổng quát
Chương 2 LẬP TRÌNH LOGIC MỞ RỘNG 22
2.1 Biểu diễn tri thức sử dụng các chương trình logic mở rộng
2.2 Ngữ nghĩa khác của chương trình logic mở rộng
2.3 Các chương trình logic phân biệt (Disjunctive Logic Programs)
2.3.1 Giới thiệu
2.3.2 Biểu diễn tri thức sử dụng chương trình logic phân biệt
2.3.3 Tìm câu trả lời cho truy vấn
Chương 3 MÔI TRƯỜNG LẬP TRÌNH LOGIC 50
3.1 Giới thiệu.
3.2 Hệ thống DLV
3.2.1 Ngôn ngữ của môi trường DLV
3.2.2 Cấu trúc một chương trình
a. Cơ sở dữ liệu mở rộng – EDB
b. Cơ sở dữ liệu cơ bản – IDB
(i) Luật
(i.1) Luật ngầm định 59
2
(i.2) Luật phân biệt 61
(i.3) Luật phủ định 62
(ii) Ràng buộc
Chi Ha(ii.1) Ràng buộc toàn vẹn 65
(ii.2) Ràng buộc yếu 67
3.3 Gói DLV trong Java
3.3.1 Biểu diễn dữ liệu: các lớp Predicate, Literal, Model và Program
3.3.2 Kiến trúc gói DLV: lớp DlvHandler
Chương 4 CÁC BÀI TOÁN MINH HỌA 77
4.1 Bài toán N quân hậu
4.1.1 Phân tích bài toán
4.1.2 Cài đặt
4.2 Bài toán Cây khung nhỏ nhất
4.2.1 Mô tả bài toán
4.2.2 Phân tích và cài đặt
a. Chương trình logic DLV
b. Cài đặt trên Java
KẾT LUẬN 93
TÀI LIỆU THAM KHẢO 95
PHỤ LỤC 97