- 5 1.2 Biểu diễn tri thức trong chương trỡnh logic tổng quỏt. - 26 2.2 Ngữ nghĩa khỏc của chương trỡnh logic mở rộng. - 37 2.3 Cỏc chương trỡnh logic phõn biệt (Disjunctive Logic Programs. - Chương trỡnh logic DLV b. - Một luật của chương trỡnh được biểu diễn dưới dạng: 01 1. - Một tập cỏc luật tạo thành một chương trỡnh logic tổng quỏt (cũn được gọi là chương trỡnh logic thụng thường). - Chương trỡnh logic tổng quỏt khụng chứa not thỡ được gọi là chương trỡnh xỏc định. - Ngữ nghĩa của chương trỡnh logic được phõn biệt tựy theo cỏch định nghĩa tớnh thỏa món cỏc luật. - 8 Mụ hỡnh ổn định của chương trỡnh xỏc định Π được ký hiệu là ()a Π. - Gọi Π là một chương trỡnh logic tổng quỏt bất kỳ. - Tồn tại duy nhất một mụ hỡnh ổn định đối với một chương trỡnh logic là một thuộc tớnh quan trọng. - Cỏc chương trỡnh cú duy nhất một mụ hỡnh ổn định được gọi là cú tớnh tuyệt đối. - Khụng phải tất cả cỏc chương trỡnh đều cú tớnh tuyệt đối. - Cú những chương trỡnh cú nhiều mụ hỡnh ổn định, được gọi là chặt chẽ. - cú những chương trỡnh khụng cú mụ hỡnh ổn định nào, được gọi là khụng chặt chẽ. - Vớ dụ 1.3 Xột chương trỡnh logic tổng quỏt {}pnot pΠ. - 10 □ Chặt chẽ và tuyệt đối là cỏc thuộc tớnh quan trọng của cỏc chương trỡnh logic. - Vớ dụ 1.5 Chương trỡnh logic tổng quỏt Π bao gồm cỏc luật sau: 11. - Mệnh đề 1.2 Mọi chương trỡnh logic tổng quỏt phõn lớp đều cú tớnh tuyệt đối. - Vớ dụ sau sẽ đưa ra cỏch biểu diễn thụng tin trờn bằng chương trỡnh logic tổng quỏt. - Vớ dụ 1.6 Xem xột một chương trỡnh Β bao gồm cỏc luật sau. - Một chương trỡnh logic tổng quỏt được gọi là khụng lặp nếu đồ thị phụ thuộc nguyờn tố của nú khụng chứa chu trỡnh. - 17 Vớ dụ, đồ thị phụ thuộc của một chương trỡnh ()(){}papbΠ. - Ta cũng dễ thấy chương trỡnh Ψ là khụng lặp. - Hầu hết ngữ nghĩa của cỏc chương trỡnh logic tổng quỏt là thuộc vào lớp chương trỡnh này. - Định lý 1.5 Cho Π là một chương trỡnh khụng lặp. - Đặt Π là một chương trỡnh logic tổng quỏt và ()()1MtrΠ được định nghĩa là cỏc mụ hỡnh nhỏ nhất của ()1trΠ, thỏa món cỏc thuộc tớnh sau: (i) nếu một mụ hỡnh chứa A− thỡ nú phải khụng được chứa cả A và A+ (ii) nếu một mụ hỡnh chứa A+ thỡ nú phải chứa cả A. - Vớ dụ 1.8 Xột chương trỡnh logic tổng quỏt 1Π: p not qqnotp←← ()11tr Π bao gồm cỏc luật: ()()qpqpqp. - Bộ biờn dịch của Clark là ngữ nghĩa tường thuật đầu tiờn của chương trỡnh logic tổng quỏt. - bờn cạnh đú cỏc chương trỡnh logic mở rộng lại cú thể bao gồm cỏc thụng tin phủ định hiện. - Về mặt hỡnh thức, một chương trỡnh logic mở rộng Π là một tập cỏc luật cú dạng: 01 1. - Định nghĩa 2.1 Đặt Π là một chương trỡnh logic mở rộng khụng chứa biến. - Do đú, chương trỡnh cú một tập trả lời duy nhất {}qơ. - 25 Định nghĩa 2.2 Một chương trỡnh logic mở rộng cú tớnh mõu thuẫn nếu nú cú một tập trả lời mõu thuẫn. - Mệnh đề 2.1 Một chương trỡnh logic mở rộng Π là mõu thuẫn khi và chỉ khi Π cú duy nhất một tập trả lời Lit. - Thực chất, lớp cỏc chương trỡnh logic tổng quỏt là một lớp con của lớp cỏc chương trỡnh logic mở rộng. - Với mọi chương trỡnh logic tổng quỏt, cỏc mụ hỡnh ổn định của nú đều trựng với cỏc tập trả lời. - Bõy giờ ta sẽ tỡm cỏch để chuyển một chương trỡnh logic mở rộng về chương trỡnh logic tổng quỏt. - Mệnh đề 2.3 Một chương trỡnh logic mở rộng Π cú tớnh chất tuyệt đối nếu: (i) +Π là phõn lớp và (ii) Tập trả lời của +Π khụng chứa cỏc nguyờn tố dạng ()pt và ()'pt . - Ta hóy xem làm thế nào để biểu diễn cỏc thụng tin này bởi ngụn ngữ của chương trỡnh logic mở rộng. - Chương trỡnh logic mở rộng Β1 là tương đương với chương trỡnh logic tổng quỏt ban đầu Β. - Mệnh đề 2.4 Nếu S là một tập trả lời của một chương trỡnh logic tổng quỏt Π thỡ. - Vậy chương trỡnh 2B của ta sẽ như sau: 29. - Mệnh đề 2.3 chỉ ra chương trỡnh 2B cú một tập trả lời thớch hợp duy nhất. - Cỏch biểu diễn của (2.9) hoàn toàn thớch hợp với cỏc chương trỡnh logic mở rộng tuyệt đối. - í nghĩa của or trong chương trỡnh logic phõn biệt khỏc với. - Chương trỡnh logic phõn biệt là một tập cỏc luật cú dạng: 39 011. - Khi Li là cỏc nguyờn tố, chương trỡnh được gọi là chương trỡnh logic phõn biệt thụng thường. - Khi m = n và Li là cỏc nguyờn tố, chương trỡnh này được coi là chương trỡnh logic phõn biệt khẳng định. - Định nghĩa về một tập trả lời của chương trỡnh logic phõn biệt Π cũng giống như của chương trỡnh logic mở rộng. - Đầu tiờn ta sẽ xột tập trả lời của một chương trỡnh logic phõn biệt khụng cú phủ định ngầm. - Một tập trả lời của một chương trỡnh logic phõn biệt Π khụng chứa not là một tập con nhỏ nhất S của Lit, sao cho: (i) với mọi luật 01. - Khụng giống chương trỡnh logic mở rộng khụng chứa not, một chương trỡnh logic phõn biệt khụng chứa not cú thể cú nhiều tập trả lời. - Vớ dụ chương trỡnh ()()paorpb← cú hai tập trả lời (){}pa và (){}pb . - Ta ký hiệu tập trả lời của chương trỡnh logic phõn biệt Π khụng chứa not là ()αΠ. - Từ định nghĩa này, ta sẽ xỏc định được tập trả lời của một chương trỡnh logic phõn biệt bất kỳ. - Một tập cỏc phần tử S là một tập trả lời của một chương trỡnh logic phõn biệt Π nếu ()SSα∈Π trong đú, SΠ được xỏc định như trong định nghĩa 2.1. - Một biểu thức được gọi là đỳng (sai) đối với một chương trỡnh logic phõn biệt nếu nú đỳng (sai) trong mọi tập trả lời của chương trỡnh. - Xem xột một chương trỡnh chứa luật: aorb← Chương trỡnh này cú hai tập trả lời {}a và {}b . - Mệnh đề 2.5 Với mọi tập trả lời S của một chương trỡnh logic phõn biệt Π: (i) Với mọi luật nền cú dạng (2.11), nếu {}1,...,kmLLS. - Định nghĩa về sự phõn lớp cũng cú thể được ỏp dụng với cỏc chương trỡnh logic phõn biệt khụng chứa ơ. - Định lý sau sẽ đảm bảo sự tồn tại tập trả lời cho cỏc chương trỡnh này. - Định lý 2.6 Mọi chương trỡnh logic phõn biệt khụng chứa ơ cú tớnh phõn lớp đều cú một tập trả lời. - Ta xem xột một số chương trỡnh logic phõn biệt sau và cỏc tập trả lời của chỳng. - Chỳ ý rằng nú cú một cỏch biểu diễn tự nhiờn trong ngụn ngữ của cỏc chương trỡnh phõn biệt. - Ta sẽ biểu diễn thụng tin này bằng chương trỡnh logic phõn biệt. - Nú mở rộng phương phỏp tớnh toỏn cỏc mụ hỡnh ổn định của chương trỡnh logic tổng quỏt được mụ tả trong chương 1 để tớnh toỏn cỏc tập trả lời của chương trỡnh logic phõn biệt. - Định nghĩa 2.3 Đặt Π là một chương trỡnh logic phõn biệt. - Định lý 2.7 Với mọi chương trỡnh logic phõn biệt Π, ()answerset Π là tập cỏc tập trả lời của Π. - Vớ dụ 2.11 Xem xột chương trỡnh sau mụ tả vớ dụ 2.9. - 50 Chương 3 MễI TRƯỜNG LẬP TRèNH LOGIC Cỏc chương trỡnh logic phõn biệt là một cụng cụ mạnh để biểu diễn tri thức và suy diễn thụng thường. - Cỏc chương trỡnh logic phõn biệt với ngữ nghĩa tập trả lời cho phộp biểu diễn cỏc bài toỏn phức tạp hơn rất nhiều. - 57 3.2.2 Cấu trỳc một chương trỡnh Datalog phõn biệt kết nối cơ sở dữ liệu với lập trỡnh logic. - Mụ hỡnh của một chương trỡnh mà cú chứa phủ định hiện thỡ được gọi là tập trả lời. - Chương trỡnh này khụng cú mụ hỡnh. - Vớ dụ 3.12 Xột chương trỡnh sau lưu trong file example1. - Chỳ ý rằng cỏc tập trả lời của chương trỡnh { a v b. - Ta cú thể xõy dựng một chương trỡnh lưu trong file plan như sau: employee(a). - [1:2] Chương trỡnh này cú hai mụ hỡnh tốt nhất. - Chương trỡnh logic phõn biệt (DLV input) là một tập hữu hạn cỏc luật. - cỏc mụ hỡnh biểu diễn cho lời giải của chương trỡnh (DLV output) là cỏc tập phần tử nền. - Cần chỳ ý rằng, cỏc phần tử nền cú thể là một phần của một chương trỡnh logic. - The Program class Lớp Program mụ hỡnh húa cỏc chương trỡnh logic. - Nú cho phộp chia một chương trỡnh logic thành nhiều file văn bản. - Sự mở rộng này nhỳng hoàn toàn cỏc chương trỡnh logic vào trong cỏc chương trỡnh Java. - Do đú tập trả lời của chương trỡnh kết quả sẽ phự hợp với bài toỏn đưa ra. - Vớ dụ, xem xột chương trỡnh Π : ....paqbanotbb not a. - 78 Giả thiết ràng buộc của chương trỡnh: “p phải nhận giỏ trị đỳng”. - Nếu ta biểu diễn ràng buộc này dưới dạng thực tế trong chương trỡnh Π: p←. - 4.1.2 Cài đặt Bài toỏn N quõn hậu được biểu diễn bằng chương trỡnh logic tổng quỏt trong mụi trường lập trỡnh DLV. - Chương trỡnh biểu diễn bài toỏn như sau: row(X. - Dũng lệnh để chạy chương trỡnh trong DLV như sau. - Chương trỡnh logic DLV Chia dữ liệu vào DLV thành nhiều nguồn khỏc nhau. - file chương trỡnh là file bao gồm cỏc ràng buộc và cỏc luật. - Cỏc chương trỡnh logic khỏc nhau sẽ cú những cỏch biểu diễn tri thức khỏc nhau. - Ngữ nghĩa của cỏc chương trỡnh logic khỏc nhau về cỏch định nghĩa tớnh thỏa món cỏc luật. - Chương trỡnh logic tổng quỏt sử dụng ngữ nghĩa mụ hỡnh ổn định và cỏc dạng mở rộng của nú. - Chương trỡnh logic mở rộng xuất hiện thờm một cỏch biểu diễn phủ định, đú là phủ định hiện. - [C:1] Chương trỡnh MSTGUI.java package com.studyMST. - Chương trỡnh MST.java: package com.studyMST
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt