Chương I CHUONG TRINH LOGIC TONG QUAT 1.1 Mỡ đầu Ngôn ngữ A của một chương trình logic tổng quát Tï được xây dựng trên bảng chữ cải Á dược dịnh nghĩa như sau: Định nghia 1.1 Bang chit cai A bao gêm các loại ký hiệu sau: -_ Các biển -_ Cáo hằng số đối tượng (có thể gọi là hằng số) - Cac ky higu ham (function symbol) + Cae ky higu vi tit (predicate symbol) -_ Các liên kết logie: "nợf”, ”«< 7 - _ Cáo ký hiệu phân cách “( và ° a Trong do, not la lên kết logic được gọi là phủ dink ngdm (negation as /ailire), biển là xâu bật kỳ bao gồm các ký tự của bằng chữ cái và các chữ số, được bắt dầu bằng chữ cái viết hoa; hằng sở, ký hiệu hảm và kỷ hiệu vị từ là các xâu bắt đầu bởi chữ cái viết thường. Thông thường, sử dụng các chữ cái p, ạ,. cho các ký hiệu vị từ, 3, Ÿ, Z„. cho các ký hiệu ham va a, ð, e„.
cho các hằng số.2 Một toán hạng dược dịnh nghĩa như sau: HB(TT) được 1 Gu điển dưới dạng vị từ p và với một tập các vị từ .4, alemns(4) là một tập cơn các phân tử của /ƒB(TT) được biểu điển dưới dạng các vị từ thuộc 4 Ví dụ 1.1 Xét hương trình logie thông thường TÍ sau (a) P(e) Bie) z#(@))‹ p3) Ngôn ngữ của chương trình TT dựa trên bảng chữ cái bao gém vi tir p, ham f và các hằng số a, Avie. } " Một chương trình logic dược coi là một đặc tả cho phép xây dụng các lý thuyết có thể cho một thể giới quan còn các luật trong chương trình là những, ràng buộc mà các lý thuyết này cần phải thỏa mãn Ngĩt nghĩa của chương tì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 Trong luật văn này sẽ sử dụng ngữ ng]ấa về mỏ lành ôn định và các dạng mỡ rộng của nó. Với ngữ nghĩa nảy, các lý thuyết được xác định nhờ các tập nguyên tổ nên, gọi là các mỏ hình ên định cúa một chương trình. Ngữ nghĩa được định nghĩa như sau: Định nghĩa 1.6 Mô hìnhén định của một chương trình xác định TT là một tập con nhỏ nhật Ÿ của HB sao cho với mọi luật 4$ «©—44,.4„ của TT, nếu Á,.Ả,€8 thì 4 cổ MỞ ĐẦU T.ogic tỉnh toán được các rủ logic học đưa ra vào những nău 1950, dựa trên các kỹ thuật tự động hóa quá trình suy diễn logic.
Logie tỉnh toán dượ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 bao (declarative programming) déi lập voi lập trình cầu tric (procedural progyamming). Về ý tưởng, các lặp trình viên chỉ cần đưa ra khøi báo cửa chương bình côn việc thực hiển cụ thể do máy tỉnh tự xác lập, trong khi dó việc thực hiện các chương trình hướng thủ tục lại dược xác lập cụ thể bởi lập trinh 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 dich 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 logie chính thức bắt đầu vào cuối những năng 1970. Những phát triển xa hơn đạt được vào đâu thập kỷ 8Ó, bắt đần với sự xuất hiện của quyền sách đầu tiên nói về các co 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 thir § cia, Nhat.
Japanese Fifth Generation Computer Systems Projee) đã mũ đâu cho sự phát triển của gác ngôn ngĩữ lập tinh logie khac 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 trí 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áo chương trình logie với cơ sở đữ 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 logie và cơ sở đữ liệu suy diễn dễ biểu điền tri thức được gợi là “cách tiếp cận logic cho việc biểu diễn trì thức”. Cách tiếp cận này dựa trên ý tưởng là chương trinh máy tình được cung cắp các đặc thủ MỞ ĐẦU T.ogic tỉnh toán được các rủ logic học đưa ra vào những nău 1950, dựa trên các kỹ thuật tự động hóa quá trình suy diễn logic. Logie tỉnh toán dượ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 bao (declarative programming) déi lập voi lập trình cầu tric (procedural progyamming). Về ý tưởng, các lặp trình viên chỉ cần đưa ra khøi báo cửa chương bình côn việc thực hiển cụ thể do máy tỉnh tự xác lập, trong khi dó việc thực hiện các chương trình hướng thủ tục lại dược xác lập cụ thể bởi lập trinh 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 dich 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 logie chính thức bắt đầu vào cuối những năng 1970. Những phát triển xa hơn đạt được vào đâu thập kỷ 8Ó, bắt đần với sự xuất hiện của quyền sách đầu tiên nói về các co 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 thir § cia, Nhat. Japanese Fifth Generation Computer Systems Projee) đã mũ đâu cho sự phát triển của gác ngôn ngĩữ lập tinh logie khac 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 trí 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áo chương trình logie với cơ sở đữ 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 logie và cơ sở đữ liệu suy diễn dễ biểu điền tri thức được gợi là “cách tiếp cận logic cho việc biểu diễn trì thức”. Cách tiếp cận này dựa trên ý tưởng là chương trinh máy tình được cung cắp các đặc thủ Œ}— biến ltoán hạng, (ii) hằng số là toán hạng, (iÐ Mếu ƒlà một ký hiệu hàm bậc n và ñ.⁄,„ là các toán hang thi F (4-04) ofing là một toán hạng, u Định nghĩa 1.3 Mét toan hang được gọi là có tính chit nén (ground) nêu không có biển nào xuất hiền trong nó.4 Mét nguyên tố biểu diễn trên báng chit cai A Ja mét biéu thito c6 dang p(t,.,t,), trong do p là một ký hiệu vị từ trong A và #, là các toán hạng. Xiểu mọi z là toán hạng nên thì nguyễn tố này cũng được gợi là có tính. ta chat nên.
Một luật của chương trình dược biểu diễn dưới dạng ALS Ayo Ags MOE Aggy 01 A, ay trong đỏ, 4; là các nguyên lỔ. Về trải của luật được gọi phần đầu hay là kết luận, về phải của luật là phần thản hay là giả thiết, 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 nơi thì được gọi là chương trinh xác định Các biểu thức và luật không chứa biến thị được gọi là có tính.5 Không gian xác định terbrand biểu diễn trên ngôn ngĩt Á của chương trình TT, ký hiệu là AU (TT), là tập tái cỗ các loàn hạng riểu được biểu điển với các hàm và hằng số trong À.
Tập tất cả các nguyên tổ nên trang. ngôn ngữ của một chương trình II được dịnh nghĩa là #Z(IT) (cơ sở Herbrand của 1T). Với một vị từ p, alons(p) dược dịnh nghĩa là tập con của Mô hình ên dịnh của chương trình xác định [1 được ký hiệu lá a1) " Goi 11 là một chương trình logic tổng quát bất kỳ. Với mọi tập phần tử 3, dặt XI” là một chương trình thu được từ I[ bằng cách xỏa: ( — các luật có chứa not đvới Ác (ii) tat cd cdc norA trong các luật còn lại Ré ring, TT khéng chita not va Lon tại một mô hình ổn định đã định nghữa ở trên.
Nếu mô hinh én định nảy tring voi #, thì ta nói rằng Š là một mô hình ôn. T1 suy diễn ra một biểu thức ƒ (ký hiệu bởi T1 — ƒ ) nẻu ƒ là đúng trong mọi mỏ hình ôn định của HT. Ta cũng nói rắng câu trả lời cho một truy vẫn nên g là có nêu ø là đứng trong mọi mô hình ổn định của I1 (tức lả TIỊ- g), là không nếu —g là đứng trong mọi mô hình ốn định của I1 (tức là T= 4) và không xác định trong trường hợp còn lại.2 Xót ngôn ngữ chứa hại đối Lượng a và ð và một chương trình TT p(X)‹< mot g(X} g(a) Ta sẽ chỉ ra rằng tập S—{g(4). p(b)} là một mô hình ẩn định của II.
Xây dựng chương trình TI theo cách trên, ta có TT - {p(b)<—, g(2)<©} có một mỏ hình én dink trùng với 6. Do đó & chính là mmô hình ôn định của II Œ}— biến ltoán hạng, (ii) hằng số là toán hạng, (iÐ Mếu ƒlà một ký hiệu hàm bậc n và ñ.⁄,„ là các toán hang thi F (4-04) ofing là một toán hạng, u Định nghĩa 1.3 Mét toan hang được gọi là có tính chit nén (ground) nêu không có biển nào xuất hiền trong nó.4 Mét nguyên tố biểu diễn trên báng chit cai A Ja mét biéu thito c6 dang p(t,.,t,), trong do p là một ký hiệu vị từ trong A và #, là các toán hạng. Xiểu mọi z là toán hạng nên thì nguyễn tố này cũng được gợi là có tính. ta chat nên.
Một luật của chương trình dược biểu diễn dưới dạng ALS Ayo Ags MOE Aggy 01 A, ay trong đỏ, 4; là các nguyên lỔ. Về trải của luật được gọi phần đầu hay là kết luận, về phải của luật là phần thản hay là giả thiết, 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 nơi thì được gọi là chương trinh xác định Các biểu thức và luật không chứa biến thị được gọi là có tính.5 Không gian xác định terbrand biểu diễn trên ngôn ngĩt Á của chương trình TT, ký hiệu là AU (TT), là tập tái cỗ các loàn hạng riểu được biểu điển với các hàm và hằng số trong À.
Tập tất cả các nguyên tổ nên trang. ngôn ngữ của một chương trình II được dịnh nghĩa là #Z(IT) (cơ sở Herbrand của 1T).