phần mở đầu, ba chƣơng nội dung, phần kết luận, hƣớng phát triển của đề tài và phần phần phụ lục. 2 Chƣơng 1 trình bày những khái niệm cơ sở của chƣơng trình logic, ngữ nghĩa mô hình nhỏ nhất của chƣơng trình logic, ngữ nghĩa mô hình bền vững của chƣơng trình logic thông thƣờng. Chƣơng 2 trình bày cú pháp và ngữ nghĩa của chƣơng trình logic mở rộng (ELP) theo tiếp cận ngữ nghĩa tập trả lời. Các chƣơng trình này cho phép phủ định mạnh và phủ định mặc định đƣợc phép xuất hiện trong các mệnh đề.
Cách tiếp cận ngữ nghĩa của lớp chƣơng trình này là sự mở rộng của ngữ nghĩa mô hình bền vững. Chƣơng 3 trình bày cú pháp và ngữ nghĩa của chƣơng trình logic dạng tuyển mở rộng (EDLP) và ứng dụng lớp chƣơng trình này trong việc biểu diễn tri thức thông qua một số bài toán minh họa. Các bài toán này đƣợc trình bày chi tiết từ việc biểu diễn bằng chƣơng trình logic dạng tuyển mở rộng đến việc cài đặt và thực thi bằng hệ thống trình biên dịch lập trình logic tập trả lời. Phần phụ lục trình bày việc cài đặt và thực thi một số ví dụ minh họa trong các chƣơng bằng phần mềm tích hợp Smodel và DLV mở rộng.
Phần kết luận nêu những kết quả đã đạt đƣợc và hƣớng phát triển của đề tài. Do thời gian có hạn và bản thân chỉ mới bƣớc đầu nghiên cứu về lĩnh vực này nên không thể tránh khỏi những thiếu sót, kính mong sự giúp đỡ và góp ý thêm của quý Thầy, Cô và các bạn. 3 Chƣơng 1 TỔNG QUAN VỀ CHƢƠNG TRÌNH LOGIC Chƣơng một trình bày các khái niệm cơ sở của chƣơng trình logic, lớp chƣơng trình đơn giản nhất của chƣơng trình logic đƣợc gọi là chƣơng trình logic dƣơng sẽ đƣợc xem xét trƣớc tiên cùng với ngữ nghĩa mô hình nhỏ nhất của nó [2]. Tiếp theo, chƣơng 1 sẽ trình bày việc mở rộng các chƣơng trình logic dƣơng khi cho phép toán tử phủ định not xuất hiện trong thân các quy tắc, đƣợc gọi là chƣơng trình logic thông thƣờng và tiếp cận ngữ nghĩa mô hình bền vững của lớp chƣơng trình này [9].
Đây là những kiến thức làm tiền đề cho các nghiên cứu tiếp theo về lập trình logic tập trả lời. Một số định nghĩa Định nghĩa 1.1 [1] (Bộ ký tự) Bộ ký tự bao gồm các lớp ký hiệu sau: 1. Hằng, thƣờng ký hiệu là các chữ cái thƣờng a, b, c,. Biến, thƣờng ký hiệu bởi các chữ cái in hoa X, Y, Z,.
Các ký hiệu hàm, thƣờng ký hiệu bởi f, g, h,. Các ký hiệu vị từ, thƣờng ký hiệu bởi p, q, r,. Các hằng vị từ: true, false. Các ký hiệu kết nối(phủ định), (tuyển), (hội), (suy ra) 7.
Các ký hiệu lƣợng từ: (với mọi), (tồn tại). Dấu ngoặc đơn trái (, dấu ngoặc đơn phải), dấu phẩy,. Mỗi ký hiệu hàm, ký hiệu vị từ có kèm theo một số tự nhiên xác định để chỉ số các đối số tham gia cùng với ký hiệu hàm hoặc ký hiệu vị từ đó, gọi là ngôi của chúng. Trên cơ sở bộ ký tự đã cho, ngƣời ta đƣa ra định nghĩa về hạng thức.
Hạng thức là yếu tố quan trọng của công thức logic, đƣợc xây dựng từ các hằng, biến, hàm và đƣợc định nghĩa hình thức nhƣ sau: 4 Định nghĩa 1.2 [1] (Hạng thức) Gọi A là bộ ký tự. Hạng thức đƣợc định nghĩa đệ qui nhƣ sau: (i) Mỗi hằng trong A là một hạng thức, (ii) Mỗi biến trong A là một hạng thức, (iii) Nếu f là ký hiệu hàm n-ngôi trong A và t1,.,tn là các hạng thức thì f(t1,.,tn) là một hạng thức, (iv) Hạng thức chỉ đƣợc sinh ra bởi các quy tắc trên. Một hằng đƣợc xem là ký hiệu hàm 0-ngôi. Hằng và biến là các hạng thức nguyên tố, hạng thức nền là hạng thức không chứa biến.3 [1] (Nguyên tố) Một nguyên tố có dạng p(t1,…,tn), trong đó p là ký hiệu vị từ n-ngôi và các đối t1,.,tn là các hạng thức.
Nguyên tố nền là nguyên tố không chứa biến.1 Xét nguyên tố me(Hoa,Mai), trong đó vị từ me là vị từ 2-ngôi để chỉ mối quan hệ mẹ. Hoa, Mai là các hằng và me(Hoa,Mai) có ý nghĩa là Hoa là mẹ của Mai.4 [1] (Literal) Literal là một nguyên tố, gọi là literal dương và litaral âm là phủ định của nguyên tố, ký hiệu p, với p là một nguyên tố. Ký hiệu phủ định còn đƣợc gọi là phủ định mạnh (strong negation) hoặc phủ định cổ điển (classical negation). Các literal p và p đƣợc gọi là ngƣợc nhau.
Trong phần tiếp theo sẽ xem xét lớp chƣơng trình logic đơn giản nhất – chƣơng trình logic dƣơng. Chƣơng trình logic dƣơng Định nghĩa 1. Trong mệnh đề (1), nếu n = 0 thì nó đƣợc gọi là mệnh đề đơn vị (unit clause), nghĩa là mệnh đề có dạng: a , đó là mệnh đề với thân rỗng, ký hiệu có thể bỏ qua.2 Xem chƣơng trình logic dƣơng sau: yeuthuong(X,Y) phunu(X)con(Y,X) (1) phunu(Mai) con(Hoa,Mai) Trong mệnh đề (1), nguyên tố phunu(X) để chỉ X là một phụ nữ, nguyên tố con(Y,X) để chỉ Y là con của X, yeuthuong(X,Y) là nguyên tố để chỉ X thương yêu Y. Ý nghĩa của công thức (1) là: mọi phụ nữ đều thƣơng yêu con của họ và các mệnh đề đơn vị có ý nghĩa: Mai là một phụ nữ và Hoa là con của Mai.3 Xem chƣơng trình logic dƣơng chỉ gồm 1 mệnh đề sau: connected(X) hub(Y), link(Y,X) Quy tắc trên có ý nghĩa là nếu Y là đơn vị điều khiển trung tâm và có đƣờng kết nối đến một đơn vị X thì X đƣợc kết nối.4 Xem chƣơng trình logic sau để định nghĩa số chẵn.
r1: sochan(0) r2: sochan (s(s(X))) sochan(X) Trong chƣơng trình này thì s là ký hiệu hàm 1-ngôi, đƣợc xác định bởi s(X) = X + 1 với X , nguyên tố sochan (X) để chỉ X là một số chẵn. Mệnh đề đơn vị r1 có ý nghĩa 0 là một số chẵn và r2 là mệnh đề với ý nghĩa là nếu X là số chẵn thì s(s(X)) cũng là số chẵn.6 [1] (Vũ trụ/Cơ sở/Thể hiện Herbrand) Cho P là chƣơng trình logic dƣơng. Vũ trụ Herbrand của P, ký hiệu UP, là tập các hạng thức nền đƣợc xây dựng từ các hằng và các ký hiệu hàm trong P. Cơ sở Herbrand của P, ký hiệu BP, là tập các nguyên tố nền đƣợc xây dựng từ các vị từ trong P có đối là các hạng thức nền trong vũ trụ Herbrand UP.
Một thể hiện Herbrand (hoặc đơn giản là thể hiện) của P là một tập con tùy ý của cơ sở Herbrand BP của P. Một thể hiện Herbrand có thể đƣợc xem nhƣ một tập các nguyên tố nền có giá trị đúng trong một ngữ cảnh đã cho. Vũ trụ Herbrand của chƣơng trình logic dƣơng P luôn luôn là vô hạn nếu trong P có ít nhất một ký hiệu hàm có số đối số lớn hơn 0.5 Xét chƣơng trình logic dƣơng P ở ví dụ 1.4: Vũ trụ Herbrand của P là: UP = {0, s(0), s(s(0)), s(s(s(0))),.} Cơ sở Herbrand của P là: BP = {sochan(0), sochan(s(0)), sochan(s(s(0))),.} Một số thể hiện Herbrand của P là: I1 = {sochan(0)} I2 = {sochan(0), sochan(s(0))} I3 = {sochan(sn(0)) | n {0, 2, 4,…}} I4 = BP Định nghĩa 1.7 [1] (Hiện hành nền) Một hiện hành nền của mệnh đề C có dạng (1) là một mệnh đề C’ nhận đƣợc từ C bằng cách thay thế các biến trong C bởi các hạng thức nền trong vũ trụ Herbrand UP. Ký hiệu ground(C) là tập tất cả hiện hành nền của C và đặt ground(P) =∪CP ground(C) 7 Định nghĩa 1.8 [1] (Mô hình) Cho I là một thể hiện của chƣơng trình logic dƣơng P.
Lúc đó I là mô hình của - mệnh đề nền (không chứa biến) C = a b1,…,bm ký hiệu I C nếu {b1,…,bm} I hoặc a I; - mệnh đề C, ký hiệu I C nếu I C’ với mọi C’ ground(C); - chƣơng trình P, ký hiệu I P nếu I C với mọi mệnh đề C của P.6 Xét các thể hiện I1, I2, I3, I4 của chƣơng trình logic P trong ví dụ 1.4, rõ ràng I1 không phải là mô hình của P vì mặc dầu I1 là mô hình của mệnh đề sochan(0) nhƣng I1 không phải là mô hình của mệnh đề r2 vì tồn tại mệnh đề nền sochan(s(s(0))) sochan(0) của r2 mà I1 không phải là mô hình của mệnh đề nền này. Cũng vậy, I2 cũng không phải là mô hình của P vì mệnh đề tồn tại mệnh đề nền: sochan(s(s(s(0)))) sochan(s(0)) của r2 mà I2 không phải là mô hình của nó. Tuy nhiên, I3 là mô hình của P. Ta có I3 là mô hình của r1.
I3 cũng là mô hình của r2. Thật vậy, xét mệnh đề: sochan(s(s(t)))) sochan(t) là một hiện hành nền nào đó của mệnh đề r2, trong đó t UP. Rõ ràng mệnh đề sochan(s(s(t))) sochan(t) đúng vì sochan(t) và sochan(s(s(t)))) đều thuộc I3. Vậy I3 là mô hình của P.
Ta cũng có ngay I4 là mô hình của P.9 [1] (Mô hình cực tiểu) Cho P là chƣơng trình logic dƣơng, M là mô hình cực tiểu của P nếu không tồn tại mô hình J của P sao cho J M.10 [2] (Ngữ nghĩa chƣơng trình logic dƣơng) Cho P là chƣơng trình logic dƣơng, ngữ nghĩa của P là mô hình nhỏ nhất LMP của P. 8 Mô hình nhỏ nhất LMP có thể tính đƣợc bằng cách sử dụng toán tử hệ quả trực tiếp nhờ vào một quá trình lặp. Ta có định nghĩa sau: Định nghĩa 1.11 [2] (Toán tử hệ quả trực tiếp) Cho P là chƣơng trình logic dƣơng. Đặt là toán tử đƣợc xác định nhƣ sau: Với mỗi I 2 BP , TP(I) = { A BP | tồn tại A A1,…, An thuộc ground(P) và {A1,…, An} I } trong đó 2 BP là tập các tập con của cơ sở Herbrand BP.
TP đƣợc gọi là toán tử hệ quả trực tiếp trên đó 2 BP .2 [2] Cho P là chƣơng trình logic dƣơng. Lúc đó: - Toán tử TP đơn điệu và có điểm bất động nhỏ nhất lfp(TP), - lfp(TP) là mô hình nhỏ nhất LMP của P và dãy hội tụ về LMP, trong đó: = , .7 Xét chƣơng trình logic P ở Ví dụ 1.4: r1: sochan(0) r2: sochan(s(s(X)))) sochan(X) Áp dụng Định lý 1.2 ở trên ta tính đƣợc: Ta có: = = {sochan(0)} = { sochan(0), sochan(s(s(0)))} = { sochan(0), sochan(s(s(0))), sochan(s(s(s(s(0))))),…} … = {sochan(sn(0)) | n {0, 2, 4,…}} Vậy LMP = {sochan(sn(0)) | n {0, 2, 4,…}} 9 Ví dụ 1.