zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Giáo trình Logic Toán: Phần 2

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:122

Báo xấu

142
lượt xem 36
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình Logic Toán gồm 8 bài học. Phần 2 giáo trình gồm nội dung các bài học: Ngôn ngữ Prolog, logic mờ. Mời các bạn tham khảo nội dung chi tiết của tài liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Logic Toán: Phần 2

Giáo trình Logic Toán BÀI 6: lGÔl lGỮ PROLOG 1. Tư duy lập trình và định nghĩa vấn đề trên Prolog Đối với Prolog, một chương trình có thể hiểu như là các tri thức được người lập trình cung cấp cho hệ thống Prolog. N hờ vào các kiến thức được cung cấp, hệ thống có thể trả lời được các câu hỏi được đặt ra, và câu trả lời có thể đạt được nhờ cơ chế suy luận của hệ thống dựa trên những kiến thức được cung cấp ban đầu. Đơn vị kiến thức mà người lập trình cung cấp cho Prolog gọi là các vị từ (predicate). Các vị từ dùng để biểu diễn các khái niệm mà người lập trình muốn hệ thống dùng để suy luận để đạt được các kiến thức khác mà mình mong muốn. Về mặt kỹ thuật, các predicate có thể được xem như các hàm, nhưng giá trị trả về chỉ có thể là các giá trị luận lý - đúng hoặc sai. Và giá trị trả về này chỉ có thể sử dụng để suy luận, Prolog không có cơ thế chồng chất hàm như các ngôn ngữ thủ tục khác, chính điều này sẽ làm những người quen với việc lập trình thủ tục gặp khó khăn khi bước đầu lập trình với Prolog. Công việc đầu tiên khi lập trình trên Prolog là định nghĩa các vị từ - các khái niệm mà mình cần cung cấp cho chương trình. Xét các ví dụ sau: VD1: Dữ kiện ban đầu: Mọi người đều phải chết. Socrates là người. Yêu cầu: Chúng ta muốn hệ thống phải có khả năng suy luận và trả lời được các vấn đề liên quan đến các khái niệm trên: ai là người, ai không là người, ai phải chết, ai không phải chết. Ở đây chúng ta có một sự suy luận thông minh đặc trưng cho sức mạnh của Prolog: hệ thống sẽ tự động suy luận rằng Socrates phải chết (điều không được cung cấp ban đầu). Để biểu diễn các vấn đề trên bằng ngôn ngữ Prolog, chúng ta cần phải xác định cần phải biểu diễn những khái niệm gì. Trong vấn đề này chúng ta có hai khái niệm cần biểu diễn: một thực thể nào đó có thể là người (hoặc không), và một thực thể nào đó có thể chết. N hư vậy chúng ta biểu diễn vấn đề đầu tiên bằng ngôn ngữ Prolog như sau: nguoi(symbol) Symbol là một kiểu dữ liệu đặc biệt của Prolog, dùng để biểu diễn cho một thực thể, một khái niệm tổng quát. Chúng ta sẽ trở lại vấn đề này sau. N hư vậy chúng ta vừa định nghĩa một khái niệm: một symbol nào đó có thể là người, một symbol nào khác thì không. Hiểu như một sự định nghĩa hàm, chúng ta có thể xem như định nghĩa một hàm mang tên nguoi, hàm này có thông số một biến thuộc kiểu dữ liệu symbol, và kết quả của hàm này, không cần phải khai báo thuộc về kiểu gì, vì chỉ có thể thuộc kiểu boolean, chỉ có thể đúng hoặc sai. N hiệm vụ của Prolog là phải trả lời được với giá trị symbol nhập vào, thì hàm này Gv: Trịnh Huy Hoàng Trang 58
Giáo trình Logic Toán cho ra kết quả đúng hoặc sai, tức symbol ấy có phải là người hay không. Prolog chỉ có thể làm được điều này nếu như nếu như chúng ta cung cấp cho hệ thống một cơ chế suy luận đúng đắn, tức là giải thích được cho Prolog hiểu như thế nào là người? Tương tự như vậy, chúng ta định nghĩa về vấn đề một thực thể nào đó phải chết bằng vị từ sau chet(symbol) N hư vậy với bài toán đã nêu, chúng ta sẽ đặt ra hai vị từ nguoi(symbol) chet(symbol) VD2: Yêu cầu: tính giá trị giai thừa của một số nguyên bất kỳ. Bài toán trên không cho biết dữ kiện ban đầu. Chúng ta phải cung cấp các dữ kiện ban đầu, để Prolog có thể dựa vào đó để suy luận, để từ đó hệ thống có thể giải quyết được yêu cầu của chúng ta. Việc cung cấp dữ kiện ban đầu cho hệ thống là rất quan trọng quyết định vấn đề giải quyết yêu cầu của chúng ta. Một trong những cách giải quyết có thể được lựa chọn là chúng ta sẽ cho hệ thống biết giá trị giai thừa của toàn bộ số nguyên: giai thừa của 0 là 1, giai thừa của 1 là 1, giai thừa của 2 là 2, giai thừa của 3 là 6, giai thừa của 4 là 24… Dễ dàng nhận thấy rằng cách này là không khả thi, và trong thực tế, con người cũng không tiếp thu tri thức theo cách này. Chúng ta có thể cung cấp dữ kiện cho hệ thống theo cách khác: giai thừa của một số là tích các số từ 1 đến số đó. N hư vậy với cách giải quyết này, chúng ta có hai khái niệm cần phải cung cấp: giai thừa của một số là gì, và tích của các số nguyên tính từ 1 đến một số là gì? Cách đặt vấn đề này có thể giải quyết được bài toán, tuy nhiên chúng ta có thể đặt vấn đề theo một cách khác đơn giản, và hợp với tinh thần của Prolog hơn: giai thừa của 0 là 1, và giai thừa của một số lớn hơn 0 là giai thừa của số liền trước nó nhân với chính nó. Với cách đặt vấn đề này, chúng ta chỉ có một khái niệm phải biểu diễn: giai thừa của một số là gì? (thật ra chúng ta còn một số khái niệm phải đưa ra: một số đứng trước một số là gì, nhân hai số nghĩa là gì, tuy nhiên Prolog đã cung cấp các toán tử để giải quyết vấn đề này. Hiểu theo một nghĩa nào đó, các vấn đề trên là các tiên đề, không cần phải giải thích với hệ thống.) N ếu quen với ngôn ngữ lập trình thủ tục, chúng ta có khuynh hướng khai báo vị từ diễn tả khái niệm giai thừa như sau: giaithua(integer) Ở đây cách đặt vấn đề như vậy là không thích hợp với ngôn ngữ Prolog, vì. Một vị từ chỉ có thể trả lời là đúng hoặc sai, trong khi chúng ta đang mong muốn kết quả trả về theo cách khai báo này một số. N gôn ngữ Prolog không có sự chồng chất hàm, nghĩa là kết quả của hàm (vị từ) không thể dùng như một thông số cho một vị từ khác, trong khi chúng ta đang định dùng kết quả của hàm này để tính tiếp giá trị cho một hàm khác.(Chúng ta định dùng hàm này để tính giai thừa của n -1 , rồi nhân tiếp cho n để ra kết quả cuối cùng). Gv: Trịnh Huy Hoàng Trang 59
Giáo trình Logic Toán Vị từ thích hợp sẽ được khai báo như sau: giaithua(integer,integer) Điều này, hiểu theo ngôn ngữ thủ tục, nghĩa là chúng ta khai báo một hàm có thông số là hai số nguyên, và kết quả trả về sẽ là đúng hoặc sai. Điều chúng ta muốn diễn tả có nghĩa là: giai thừa của một số nguyên (integer) sẽ là một số nguyên khác. N ếu chúng ta giải thích được cho Prolog hiểu giai thừa của một số nguyên sẽ được tính như thế nào, hệ thống sẽ có khả năng trả lời cho cả câu hỏi thuận (giai thừa của một số nguyên là gì), câu hỏi nghịch (số nguyên nào có giai thừa bằng số nguyên này), và nghi vấn (giai thừa của một số nguyên X có phải là số nguyên Y hay không). Tuy nhiên mục đích của chúng ta chỉ cung cấp các dữ kiện để hệ thống có thể trả lời câu hỏi thuận (và có thể trả lời thêm câu hỏi nghi vấn) mà thôi. Tóm tắt: Lập trình trên Prolog là cung cấp cho hệ thống các khái niệm và diễn giải các khái niệm đó. Các khái niệm được cung cấp qua các vị từ. Các vị từ có thể xem như các hàm như chỉ trả về giá trị đúng hoặc sai. Việc hệ thống có thể trả lời được những câu hỏi nào liên quan đến khái niệm đã cung cấp phụ thuộc vào việc chúng ta diễn giải các khái niệm trên cho hệ thống 2. Các clause, cách giải thích các vấn đề trên Prolog Sau khi đã cung cấp cho hệ thống các khái niệm cần thiết, chúng ta cần phải giải thích các khái niệm mình đã cung cấp, Prolog sẽ dùng các lời giải thích này để thực hiện việc suy luận và trả lời câu hỏi của chúng ta. Các lời giải thích này được gọi là các mệnh đề (clauses). Có hai dạng mệnh đề: sự kiện (fact), và luật( rule). Các sự kiện là những điều mà chúng ta công nhận là đúng. Luật là những quy tắc mà chúng ta xác định điều kiện đúng cho chúng. VD3: hãy viết phần clause cho vị từ nguoi đã định nghĩa trong VD1 Dữ kiện ban đầu chỉ cung cấp cho chúng ta một vấn đề liên quan đến người: Socrates là người. Theo như cách tư duy trong không gian của bài toán, chỉ có một con người duy nhất: Socrates. Không ai khác là người. N hư vậy chúng ta sẽ viết phần clause cho vị từ này như sau: nguoi(socrates). Chúng ta vừa viết một sự kiện: socrates là người là điều chắc chắn đúng. Bất kỳ symbol nào có tên là socrates là người là chắc chắn đúng, không cần phải có một điều kiện ràng buộc nào kèm theo. Lưu ý: i/Có hai cách viết dạng hằng (literal) cho symbol trên Prolog: - Một danh hiệu mở đầu bằng ký tự thường (socrates, sOCRATES…) Gv: Trịnh Huy Hoàng Trang 60
Giáo trình Logic Toán - Một chuỗi ký hiệu đặt trong cặp ký hiệu "," ("socrates","SOCRATES"," sOCRATES", "Socrates"…) ii/ một mệnh đề luôn kết thúc bằng ký tự '.' VD4: hãy viết phần clause cho vị từ chet trong VD1. Dữ kiện ban đầu chỉ cung cấp cho chúng ta một sự kiện liên quan đến vấn đề này: symbol sẽ phải chết nếu (và chỉ nếu) đó là người. Điều này sẽ xác định một quy tắc: symbol sẽ chỉ phải chết, tức vị từ sẽ trả về kết quả true, nếu symbol đó là người. Vấn đề symbol nào là người và symbol nào không là người chúng ta đã đưa ra khái niệm và giải thích cho Prolog trong các ví dụ 1 và 3. N hư vậy phần mệnh đề sẽ được viết như sau: chet(X):-nguoi(X). Mệnh đề dạng rule sẽ bao gồm hai phần, nằm ở hai bên cặp ký hiệu ":-". Phần bên trái cho biết vị từ đang được đề cập và các thông số tương ứng. Phần bên phải, xác định điều kiện trả lời đúng cho luật trên, bao gồm các lời gọi các vị từ khác, được ngăn cách bởi ký hiệu ',', gọi là các mệnh đề con (sub-clause). Trong ví dụ trên, chỉ có một sub-clause. Một luật chỉ trả lời đúng nếu tất cả các sub-clause bên vế phải đều trả lời đúng. Trong ví dụ trên, chúng ta có một biến X. Tất cả các thông số mở đầu bằng ký tự hoa đều được Prolog hiểu là biến. Biến này là thông số của vị từ chet. Do đã khai báo ở phần vị từ, X sẽ được hiểu là một biến thuộc kiểu symbol. Kết quả sẽ trả về đúng nếu tất cả sub-clause bên vế phải đều trả lời là đúng. Trong trường hợp này, chỉ có một sub-clause xác định xem X có phải là người không. N hư vậy chúng ta đã biểu diễn được khái niệm một symbol sẽ phải chết nếu symbol đó là người, tức là tất cả những dữ kiện ban đầu được cung cấp. VD5: Hãy viết phần clause cho vị từ giaithua ở VD2. Từ các dữ kiện được cung cấp (do chúng ta tự cung cấp cho mình để giải bài toán), chúng ta thấy có một sự kiện chắc chắn đúng: giai thừa của 0 là 1, và có một luật suy diễn: giai thừa của n là (n-1)!*n. Chúng ta sẽ viết phần mệnh đề cho vị từ này như sau: giaithua(0,1). giaithua(X,Y) -: X1 = X -1, giaithua(X1,Y1), Y = Y1*X. Trước khi hiểu những điều được mô tả trong các ví dụ trên, chúng ta sẽ có một số nhận xét như sau: - Trước tiên, chúng ta thấy vị từ giaithua được biểu diễn bằng hai mệnh đề: một sự kiện và một luật. Khi viết nhiều mệnh đề cho một vị từ, các mệnh đề phải được viết liên tiếp nhau (không được xen mệnh đề của vị từ khác vào). Gv: Trịnh Huy Hoàng Trang 61
Giáo trình Logic Toán - Chúng ta sẽ hiểu hai mệnh đề con đầu tiên X1 = X -1, giaithua(X1,Y1) biểu diễn cho công việc tính giai thừa của X-1. Tuy nhiên chúng ta không được viết giaithua(X-1,Y1). Thông số của các mệnh đề con phải là biến, không được phép là biểu thức. - Chúng ta thấy sự xuất hiện của ký hiệu '= ' và sẽ hiểu như mệnh đề con X1 = X-1 là phép gán. Trên Prolog không có phép gán. Ký hiệu '=' biểu diễn cho một phép toán đặc biệt của Prolog, phép hợp nhất (unification), và cũng như các mệnh đề khác, phép hợp nhất này sẽ trả về kết quả đúng hoặc sai, biểu diễn cho kết quả công việc hợp nhất thành công hay không. Xem thêm về phép hợp nhất trong các phần sau. - Phần vị từ trên biểu diễn cho việc sử dụng kỹ thuật lập trình đệ quy, sẽ là sức mạnh lập trình chủ yếu của Prolog. Xem thêm về phần lập trình đệ quy trên Prolog trong các phần sau. Tóm tắt Các khái niệm được mô tả qua các vị từ sẽ được giải thích bằng các mệnh đề. Có hai loại mệnh đề: sự kiện và luật. Thông số được truyền trong lời gọi các mệnh đề con phải là biến. Các kỹ thuật chủ yếu để lập trình trên Prolog là hợp nhất và đệ quy. 3. Thực thi chương trình. - Đặt câu hỏi và nhận câu trả lời Đến đây chúng ta đã có thể thực thi các chương trình trên. Trên cửa sổ Prolog, nhập nội dung đoạn chương trình vào vùng cửa sổ soạn thảo. (Chúng ta có thể luôn chuyển về vùng cửa sổ này bằng phím nóng Alt+E). VD6: Viết chương trình hoàn chỉnh cho VD1. N ội dung chương trình nhập hoàn chỉnh cho VD1 như sau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). chet(X):-nguoi(X). N hư vậy chúng ta thấy trong một chương trình Prolog, các phần khai báo các vị từ và hiện thực các mệnh đề được bắt đầu bằng các từ khoá predicates và clauses. Lưu ý: Phần predicates phải được viết trước phần dành cho clauses. Chúng ta sử dụng Turbo Prolog để thử các ví dụ trên: Giao diện chương trình sẽ như sau: Gv: Trịnh Huy Hoàng Trang 62
Giáo trình Logic Toán Để thực thi chương trình, người sử dụng nhập yêu cầu (câu hỏi) của mình cho hệ thống.Yêu cầu này gọi là goal. Có hai loại goal:goal nội và goal ngoại. Phần này chỉ trình bày về goal ngoại. Để nhập goal ngoại, sau khi đã hoàn tất việc soạn thảo chương trình, chúng ta dùng phím tắt Alt+R để chuyển sang vùng giao tiếp của chương trình. Câu hỏi chúng ta đặt ra cho hệ thống phải chỉ dựa vào các tri thức mà chúng ta đã cung cấp cho hệ thống. Chúng ta đã cung cấp cho hệ thống các khái niệm nguoi và chet, như vậy chúng ta chỉ có thể đặt các câu hỏi liên quan đến hai khái niệm này. N gay sau dấu nhắc Goal: tại vùng cửa sổ này, chúng ta có thể nhập câu hỏi như sau: nguoi("Socrates") Dựa trên tinh thần của của khái niệm, câu phát biểu của chúng ta có nghĩa là "Socrates là người", và vì đây là câu phát biểu trong vùng goal, nên hệ thống sẽ hiểu rằng chúng ta muốn đặt một câu hỏi nghi vấn "Socrates là người phải không?" Sau khi ấn Enter, chúng ta sẽ thấy hệ thống có ngay câu trả lời: Yes. Thay bằng một tên khác, ví dụ: nguoi("Xeda") Hệ thống sẽ trả lời N o. Chúng ta thấy các câu trả lời của hệ thống dựa trên kiến thức mà chúng ta đã cung cấp. Dựa vào những gì mà chúng ta đã cung cấp, hệ thống chỉ biết có một người là Socrates, tất cả những symbol khác đều không phải là người. Tuy nhiên, với cơ chế suy luận mà chúng ta cung cấp, hệ thống có thể suy luận ra những điều chưa được cung cấp sẳn. Đây chính là điểm tạo nên sức mạnh lập trình của Prolog. Gv: Trịnh Huy Hoàng Trang 63
Giáo trình Logic Toán N hập vào goal như sau: chet("Socrates") Câu trả lời là: Yes. Với một tên người khác: chet("Xeda") Câu trả lời là: N o. Hệ thống đã tự động suy luận theo nguyên lý mà chúng ta muốn nó phải "học": ai là người thì người đó phải chết. N goài những câu hỏi dạng Yes/N o, Prolog có thể trả lời các câu hỏi yêu cầu tìm đáp số. Chúng ta nhập vào một goal như sau: chet(X) Đến đây, trong câu hỏi của chúng ta có một biến: X (nhắc lại: mọi danh hiệu mở đầu là ký tự hoa đều là biến). Khi trong câu hỏi của chúng ta chứa một (hoặc nhiều) biến, hệ thống sẽ tìm các giá trị có thể có của biến để cho câu phát biểu của ta là đúng. Hiểu ở mức ý niệm, câu hỏi của chúng ta là: ai là người? Kết quả trả lời của câu hỏi (ai) sẽ được chứa trong biến X. Câu trả lời sẽ là: X = Socrates Tương tự như trên, hệ thống sẽ dựa vào cơ chế suy luận đã được cung cấp để tìm ra lời giải với những câu hỏi dành cho các vị từ có các mệnh đề tương ứng là các luật. N hập vào goal như sau: chet(X) Hệ thống sẽ trả lời như sau: X = Socrates. VD7: Hoàn chỉnh và thực thi chương trình cho VD2 Chương trình hoàn chỉnh như sau: predicates giaithua(integer,integer) clauses giaithua(0,1). giaithua(X,Y):- X1 = X -1, giaithua(X1,Y1), Y = X*Y1. Chúng ta lưu ý là khi kết thúc mỗi mệnh đề đều có ký hiệu '.' Chúng ta có thể đặt cho hệ thống goal dạng nghi vấn như sau: giaithua(3,6) Hiểu theo ngôn ngữ tự nhiên sẽ là: có phải giai thừa của 3 là 6 hay không? Câu trả lời là: Yes Hoặc chúng ta có thể đặt câu hỏi: giaithua(3,8) Gv: Trịnh Huy Hoàng Trang 64
Giáo trình Logic Toán Câu trả lời sẽ là: N o. Chúng ta sẽ đặt câu hỏi theo dạng tìm lời giải: giaithua(3,X) Câu trả lời sẽ là X = 6 Chúng ta cũng có thể đặt câu hỏi ngược: giaithua(X,6) Ý tưởng của câu hỏi sẽ là: giai thừa của số nào sẽ bằng 6. Tuy nhiên chúng ta không cung cấp cho hệ thống cơ chế suy luận để trả lời câu hỏi này. Hệ thống sẽ trả lời: N o Solution. Tất nhiên chúng ta có thể đặt câu hỏi như sau: giaithua(X,Y) Cả hai thông số đều là biến. N hư vậy câu hỏi có thể hiểu là: số nào (X) giai thừa thì thành một số khác (Y). Câu hỏi gần như vô nghĩa và những câu trả lời của hệ thống cũng sẽ chẳng mang một ý nghĩa thực sự có nghĩa nào. Tóm tắt: Chương trình Prolog sẽ hoạt động theo cơ chế tương tác. N gười sử dụng sẽ cung cấp yêu cầu, gọi là goal, và hệ thống sẽ trả lời các yêu cầu này. Có hai loại goal: goal nội và goal ngoại. N ếu goal không chứa biến thì hệ thống sẽ kiểm tra phát biểu của chúng ta là đúng hoặc sai, ngược lại, hệ thống sẽ tìm các giá trị của các biến làm cho phát biểu của ta là đúng. 4. Phép hợp nhất - Cơ chế tìm câu trả lời của Prolog. 4.1/ Phép hợp nhất Công việc quan trọng nhất của Prolog trong việc tìm câu trả lời là thực hiện việc hợp nhất. Phép hợp nhất được biểu diễn bằng dấu =, và nó có hai thành phần, tạm gọi là vế trái vế phải. Phép hợp nhất sẽ trả về kết quả true hoặc false. Có các trường hợp hợp nhất sau: a. Cả hai vế đều là hằng hoặc biểu thức chứa toàn hằng. N ếu giá trị của hai vế là bằng nhau thì phép hợp nhất thành công (đáp số là true), ngược lại phép hợp nhất sẽ thất bại (kết quả là false) 7 = 7 _ true 7 = 8 _ false "abc" = "abc" _ true "abcd" = "abc" _ false Gv: Trịnh Huy Hoàng Trang 65
Giáo trình Logic Toán 7 = 6 +1 _ true 6 = 7 +1 _ false b. Một trong hai vế là hằng hoặc trong biểu thức chứa toàn hằng, vế kia là biến hoặc biểu thức có chứa biến. Trường hợp 1: N ếu tất cả các biến đều có giá trị (gọi là các biến ở tình trạng bound), chúng ta quay về trường hợp a 7 = X _ false nếu X đã có giá trị là 6 7 = X +1 _ true nếu X đã có giá trị là 6 Y = "Socrates" _ true nếy Y đã có giá trị là "Socrates" Trường hợp 2: N ếu có biến chưa có giá trị (gọi là biến ở tình trạng unbound), Prolog sẽ gán giá trị cho biến sau cho hai vế có giá trị như nhau và trả về kết quả là true. N ếu không tìm giá trị như vậy, phép hợp nhất sẽ cho kết quả là false. 7 = X _ true nếu X chưa có giá trị, sau phép hợp nhất này, X sẽ có giá trị là 7-1 = X*X _ false vì không thể tìm cho X giá trị nào làm cho giá trị hai vế là như nhau. c. Cả hai vế đều là biến hoặc các biểu thức có chứa biến Trường hợp 1: tất cả các biến đều có chứa giá trị, chúng ta sẽ quay về trường hợp a X = Y _ true nếu cả X và Y đều đã có giá trị và những giá trị này bằng nhau X -1 = Y _ false nếu X và Y đều đã có giá trị và X nhỏ hơn Y. Trường hợp 2: tất cả các biến của một vế đều đã có giá trị, chúng ta sẽ quay về về trường hợp b X = Y _ true nếu X chưa có giá trị và Y đã có giá trị, sau phép hợp nhất, X sẽ nhận giá trị của Y X - 1 = Y _ true nếu X chưa có giá trị, Y đã có giá trị. Sau phép hợp nhất, X sẽ có giá trị bằngg Y +1 Trường hợp 3: cả hai vế đều còn chứa biến ở tình trạng unbound _ hợp nhất thất bại X = Y _ false nếu cả X và Y đều chưa gán giá trị X-1 = Y _ false nếu cả X và Y đều chưa gán giá trị 4.2/ Cơ chế tìm câu trả lời của Prolog N ếu chúng ta đặt ra cho Prolog một câu hỏi, Prolog sẽ thực hiện công việc so trùng (match), tức là tìm mệnh đề đầu tiên đề cập đến khái niệm mà chúng ta muốn hỏi. Trở lại VD6, sau khi đã hoàn tất chương trình, chúng ta đặt ra Goal như sau: nguoi("Socrates") Prolog sẽ tìm mệnh đề đầu tiên có liên quan đến khái niệm nguoi. Hiển nhiên, mệnh đề đầu tiên (và duy nhất có liên quan đến khái niệm này là: nguoi("Socrates") Gv: Trịnh Huy Hoàng Trang 66
Giáo trình Logic Toán N hư vậy, khi đã có goal (nguoi("Socrates")) và tìm thấy mệnh đề liên quan (nguoi("Socrates")), Prolog sẽ tiến hành tìm kiếm lời giải, công việc này tiến hành bằng cách tạo mối liên kết giữa các thông số ở phần goal và các thông số ở phần mệnh đề. Có các trường hợp sau: a. Cả hai thông số này đều là các biến unbound, trong trường hợp này Prolog sẽ xem cả hai thông số là 1. b. Ở tất cả các trường hợp khác, Prolog sẽ tiến hành phép hợp nhất giữa hai loại thông số. Sau khi đã tạo mối quan hệ giữa các thông số ở phần goal và phần clause, Prolog sẽ tiến hành các sub-clause (nếu mệnh đề này một luật). N ếu tất cả các sub-clause thành công và các biến ở phần goal đã ở tình trạng bound (tức là đã có giá trị), Prolog sẽ thông báo lời giải. N ếu là câu hỏi thuộc dạng Yes/N o như ví dụ trên, tức là câu hỏi không chứa biến, Prolog sẽ trả lời Yes nếu công việc hợp nhất như đã nói ở phần b thành công và các sub-clause đều thành công (nếu mệnh đề so trùng là một luật). Quay trở lại với ví dụ của chúng ta, ở đây thông số của Goal là một hằng ("Socrates), và thông số của mệnh đề tương ứng cũng là một hằng ("Socrates), hai hằng này hợp nhất thành công, và kết quả trả lời là Yes. N ếu chúng ta đặt ra câu hỏi khác: nguoi("Xeda") Prolog cũng chỉ tìm thấy một mệnh đề liên quan đến khai niệm này (nguoi("Socrates")), và vì sự hợp nhất giữa hai hằng "Socrates" và "Xeda" thất bại, đáp số sẽ trả lời là N o. Chúng ta xét trường hợp câu hỏi của chúng ta có chứa biến: nguoi(X) Hệ thống sẽ tìm thấy mệnh đề có liên quan đến vấn đề này (nguoi("Socrates")) , vàtiến hành hợp nhất giữa X và "Socrates", và vì X chưa có giá trị (unbound) nên phép hợp nhất thành công, X có giá trị là "Socrates". Vì việc hợp nhất giữa các thông số giữa phần goal và phần clause đã thành công, đây là một sự kiện nên không cần phải thực hiện phần sub-clause, và sau khi hợp nhất, tất cả các biến cần tìm đã có giá trị (ở đây chỉ có một biến là X), nên hệ thống sẽ công bố đã tìm ra lời giải và in ra giá trị của X ( X = "Socrates") Chúng ta xét trường hợp khi ở câu hỏi phần goal so trùng với một luật: chet(Y) Chúng ta hoàn toàn có thể đặt câu hỏi là chet(X), nhưng chúng ta sẽ đặt tên biến khác để tiện phân biệt giữa biến trong câu hỏi của goal và thông số cục bộ ở mệnh đề. Câu hỏi trong goal được so trùng với mệnh đề sau: chet(X): - nguoi (X). Gv: Trịnh Huy Hoàng Trang 67
Giáo trình Logic Toán Vì hai biến X(thông số của mệnh đề) và Y(thông số của goal) đều chưa chứa giá trị, hệ thống sẽ xem cả hai biến là một, tức là, khi X có được giá trị thì Y cũng có giá trị đó và ngược lại. Do đây là một luật, nên hệ thống sẽ tiến hành thực hiện các sub-clause. Hệ thống sẽ thực hiện sub-clause đầu tiên nguoi(X). Quá trình thực hiện các sub-clause ở vế phải sẽ được thực hiện như sau: a. N ếu sub-clause này có thông số là biến unbound, Prolog sẽ tìm giá trị của biến này để sub-clause có giá trị Yes, nếu không tìm được giá trị như vậy, sub-clause sẽ thất bại. b. N ếu sub-clause có thông số đều là biến bound (đã có giá trị) hoặc là hằng, Prolog sẽ kiểm tra xem sub-clause có trả về giá trị Yes hay không, nếu không, subclause sẽ thất bại. Các sub-clause sẽ được tiến hành từ trái qua phải, và nếu có một sub-clause thất bại, mệnh đề được so trùng sẽ thất bại. Trong trường hợp trên, khi tiến hành sub-clause nguoi(X), do biến X là unbound, nên chúng ta rơi vào trường hợp a, hệ thống sẽ tìm giá trị của X cho sub-clause trên là đúng. Cách tìm kiếm câu trả lời cho sub-clause này hòan tòan giống như cách hệ thống tìm câu trả lời khi chúng ta đặt câu hỏi này trong phần goal, và như vậy X sẽ có giá trị là "Socrates" sau khi sub-clause này thực hiện xong. Do X và Y được xem như một, nên khi X có giá trị là "Socrates" thì Y cũng có giá trị này. Do tất cả các sub-clause đã thực hiện xong, và Y đã có giá trị, nên Prolog công bố là đã tìm ra lời giải và in ra giá trị của Y. Tóm tắt: Phép hợp nhất là nền tảng của mọi hoạt động của Prolog để tìm ra lời giải. Để trả lời câu hỏi, Prolog so trùng câu hỏi với mệnh đề và tạo mối liên quan giữa các thông số. Prolog tìm ra lời giải khi thực hiện thành công một mệnh đề và tất cả các biến nếu có trong các thông số của goal đều đã có giá trị. 5. Sự quay lui - Khống chế số lượng lời giải -Vị từ nhát cắt và fail Goal nội và goal ngoại (internal goal và external goal) Khi chúng ta sử dụng Alt-R để chuyển sang cửa sổ giao tiếp và nhập vào goal, goal này gọi là goal ngoại. Chúng ta có thể thêm phần goal này hẳn trong phần soạn thảo chương trình, goal này gọi là goal nội. VD8: Viết lại chương trình giải quyết VD6 sử dụng goal nội Gv: Trịnh Huy Hoàng Trang 68
Giáo trình Logic Toán Chương trình được viết lại như sau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). chet(X):-nguoi(X). goal nguoi(X),write(X) Trong ví dụ này, chúng ta đã thêm phần goal vào trong chương trình. Khi thực thi, hệ thống sẽ không hỏi goal nữa, và tự động thực hiện các yêu cầu trong phần goal. Tuy nhiên khi thực hiện goal nội, hệ thống sẽ không tự động in kết quả nữa. Chúng ta phải gọi vị từ write để làm điều này. Vị từ này sẽ cho kết quả là đúng nếu các thông số nhập vào là đều là biến ở trạng thái bound hoặc là hằng. Sự quay lui (back-tracing) trên Prolog Hợp nhất là hòn đá nền tảng cho cơ chế suy luận của Prolog, tuy nhiên, để tìm ra lời giải đúng, Prolog phải sử dụng cơ chế quay lui, khi giá trị đầu tiên được gán cho thông số không phải là lời giải. Chúng ta xét ví dụ sau: VD9: predicates nguoi(symbol) 20 vua(symbol) sungsuong(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). vua("Xeda). sungsuong(X) :- nguoi(X),vua(X). N hư vậy trong ví dụ này, ngoài khái niệm về người, chúng ta đưa ra khái niệm về vua và sự sung sướng. Diễn giải những thông tin trong các dữ kiện trên thành ngôn ngữ tự nhiên, chúng ta có được các điều sau: "Thế giới mà chúng ta sống có hai người là Socrates và Xeda. Chúng ta có một vua la Xeda, và một thực thể nào đó chỉ sung sướng nếu thực thể đó vừa người vừa là vua." Lưu ý rằng trong ví dụ trên, các mệnh đề liên quan đến cùng một vị từ phải viết liên tiếp nhau. Xét khi hệ thống trả lời câu hỏi sau: sungsuong(X) Gv: Trịnh Huy Hoàng Trang 69
Giáo trình Logic Toán Trước tiên hệ thống sẽ so trùng goal trên với mệnh đề sungsuong(X) :-nguoi(X),vua(X). Lưu ý rằng vào lúc này chúng ta có hai biến X: một biến X là thông số của goal và một biến X là thông số của mệnh đề. Về nguyên tắc, hai biến X này hoàn toàn khác nhau. Tuy nhiên, khi so trùng goal với mệnh đề, do cả hai biến X lúc này đều chưa chứa giá trị, nên chúng sẽ được xem như một. N hưng cần chú ý rằng biến X sử dụng trong các sub-clause là biến X thông số của mệnh đề. Sau đó Prolog sẽ tiến hành các sub-clause. Ở sub-clause đầu tiên, nguoi(X), tương tự như VD6, Prolog sẽ tìm được câu trả lời là X = Socrates. Khi thực hiện sub-clause thứ hai, vua(X), do X đã có giá trị (Socrates), Prolog sẽ kiểm tra xem giá trị này có làm giá trị của mệnh đề là true hay không. N hư các ví dụ trên, việc tiến hành trả lời một sub-clause cũng tương tự như khi trả lời một goal, Prolog lại so trùng sub-clause với một mệnh đề cùng tên. Prolog tìm thấy một mệnh đề liên quan đến vua là vua("Xeda") và tiến hành hợp nhất giữa X và Xeda. Do X đã có giá trị là Socrates, việc hợp nhất thất bại. Tuy nhiên khi sub-clause này thất bại, không có nghĩa rằng Prolog sẽ vội kết luận rằng mệnh đề này thất bại. Ở đây công việc tìm kiếm câu trả lời thất bại sau khi biến X được gán giá trị và chuyển từ trạng thái bound sang unbound. Hệ thống sẽ quay lại thời điểm biến X được gán giá trị (khi trả lời sub-clause nguoi(X)) , X được chuyển lại sang tình trạng unbound, và cố gắng tìm kiếm một giá trị khác của X để cho mệnh đề con này vN n đúng. Công việc này được gọi là back-tracing. Do việc so trùng sub-clause này với mệnh đề nguoi("Socrates") thất bại, hệ thống sẽ so trùng với mệnh đề khác. \ếu không còn mệnh đề nào khác liên quan đến subclause, việc thực hiện mệnh đề mới thật sự thất bại, tuy nhiên ở đây hệ thống tìm thấy một mệnh đề khác liên quan đến khái niệm này là nguoi("Xeda"). Việc hợp nhất giữa X và "Xeda" lại được thực hiện, X sẽ có giá trị là Xeda và sau đó, khi lại tiếp tục thực hiện sub-clause vua(X) thì chúng ta sẽ dễ dàng thấy rằng sub-clause lần này được thực hiện thành công. Prolog đã tìm ra lời giải, tuy nhiên, ở trường hợp này, ngoài sự hợp nhất, Prolog còn sử dụng thêm một "vũ khí" mới, đó là sự quay lui. Khống chế số lượng lời giải Chúng ta xét ví dụ sau VD10: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). chet(X) :- nguoi(X). Gv: Trịnh Huy Hoàng Trang 70
Giáo trình Logic Toán Ví dụ không có gì phức tạp, so với VD6, chúng ta chỉ thêm một người mới là Xeda. Khi sử dụng goal ngoại, với câu hỏi nguoi(X) Chúng ta có hai lời giải: X = Socrates X = Xeda. Chúng ta cảm thấy hai đáp số này là hiển nhiên. Tuy nhiên nếu chúng ta dùng goal nội tương tự VD8, chúng ta chỉ có một đáp số là Socrates. Đây là một trong những điểm khác biệt căn bản của goal nội và goal ngoại. Goal nộichỉ tìm câu trả lời đầu tiên còn goal ngoại tìm tất cả các câu trả lời có thể. Để khống chế số lượng lời giải theo ý mình, chúng ta sử dụng hai vị từ đặc biệt là nhát cắt (cut) và fail, như các ví dụ sau: VD11: Viết lại VD10, sử dụng vị từ fail để in ra tất cả các lời giải trong trường hợp dùng goal nội. Chương trình sẽ được viết lại như sau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). chet(X) :- nguoi(X). goal nguoi(X),nl,write(X),fail nl: là vị từ đặc biệt, luôn trả về kết quả là đúng, và chỉ đơn giản là xuống dòng trước khi in thông tin mới ra cửa sổ giao tiếp. Fail: là một vị từ đặc biệt, luôn luôn trả về kết quả là sai. N hư vậy để in ra tất cả các kết quả, chúng ta dùng một thủ thuật (trick) thường gặp khi lập trình trên Prolog: sau khi đã tìm thấy lời giải cho sub-goal nguoi(X) và in giá trị này ra bằng lời gọi vị từ write(X), chúng ta gọi vị từ fail để nhận được kết quả là sai. Do cơ chế back- tracing đã nói ở trên, Prolog lại quay lại thời điểm gọi sub-goal nguoi(X) để tìm lời giải khác và in ra. Quá trình này cứ tiếp tục cho đến khi không thể tìm thấy thêm một lời giải nào khác. Bằng cách này, chúng ta đã in ra tất cả các lời giải cho câu hỏi nguoi(X), tuy nhiên lưu ý rằng với goal chính thì không tìm ra lời giải (do chúng ta luôn gọi vị từ fail cho subgoal cuối cùng) VD12: Viết lại VD10, dùng vị từ nhát cắt để để in ra một lời giải cho câu hỏi chet(X) cho trường hợp dùng goal ngoại. Vị từ nhát cắt được viết là !, là vị từ đặc biệt, sẽ trả lời đúng khi goal chưa tìm thấy lời giải nào, ngược lại sẽ báo là sai. Gv: Trịnh Huy Hoàng Trang 71
Giáo trình Logic Toán Chương trình sẽ được viết lại như sau: predicates nguoi(symbol) chet(symbol) clauses nguoi("Socrates"). nguoi("Xeda"). chet(X) :- nguoi(X),!. Khi sử dụng goal ngoại là chet(X), khi trả lời sub-clause nguoi(X), hệ thống tìm ra đáp số là X = Socrates, và vì lúc này mệnh đề được so trùng chet(X) chưa có đáp số nào, vị từ ! tiếp theo sẽ trả lời là thành công. Do chúng ta đang sử dụng goal ngoại, Prolog sẽ tìm tất cả các câu trả lời có thể có, nên hệ thống sẽ tìm một câu trả lời khác. Để làm điều đó, hệ thống sẽ tìm xem subclause nguoi(X) có đáp số nào khác không. Chúng ta sẽ dễ dàng nhận thấy rằng hệ thống tìm thấy một đáp số khác là X = Xeda. Tuy nhiên do goal đã có một lời giải, nên sub-clause tiếp theo là ! sẽ báo là thất bại, và lời giải thứ hai không được chấp nhận. Tóm tắt Goal nội sẽ tìm lời giải đầu tiên, và goal ngoại sẽ tìm tất cả các lời giải có thể có. Prolog sẽ sử dụng cơ chế quay lui khi một biến khi chuyển từ trạng thái unbound sang bound sẽ dN n đến sự thất bại trong việc truy tìm lời giải Vị từ fail luôn trả lời là sai, sử dụng khi chúng ta muốn in tất cả các lời giải với goal nội. Vị từ ! sẽ trả lời đúng khi goal chưa có lời giải và ngược lại. 6. Lập trình đệ quy với Prolog Chúng ta nhớ lại rằng với VD2, chúng ta đã cố gắng né tránh cách đặt vấn đề để giải bài toán giai thừa theo cách nhân dồn các số từ 1 đến số cần tính giá trị giai thừa. Điều này sẽ dẫn đến một điểm yếu của Prolog: không cung cấp các cấu trúc điều hiển cần thiết, dN n đến việc khó khăn khi thực hiện phép lặp. uy nhiên ví dụ này cũng cho thấy một kỹ thuật lập trình tạo nên sức mạnh chủ yếu của Prolog: lập trình đệ quy. Kỹ thuật này cũng phù hợp với suy nghĩ của con người khi tiếp cận giải quyết vấn đề và khiến cho việc lập trình trên Prolog có một sự uyển chuyển và nhẹ nhàng trong việc viết mã. Tuy vậy, nó tạo ra một sự khó khăn với những người quen lập trình thủ tục. Chúng ta sẽ xem xét lại từng bước trong việc gọi đệ quy để tìm ra lời giải. VD13: Xét từng bước quá trình gọi đệ quy và hợp nhất của VD7 với goal là giaithua(2,X) N hắc lại, chúng ta đã có đoạn chương trình như sau: predicates giaithua(integer,integer) Gv: Trịnh Huy Hoàng Trang 72
Giáo trình Logic Toán clauses giaithua(0,1):-!. giaithua(X,Y):- X1 = X -1, giaithua(X1,Y1), Y = X*Y1 Ở đây có một sự thay đổi nhỏ: chúng ta đặt nhát cắt để chuyển sự kiện đầu thành luật. Chúng ta muốn khẳng định: nếu số cần tìm giai thừa là 0 thì giai thừa của nó là 1, và kết quả này là duy nhất, không cần phải tiếp tục tìm các trường hợp khác. Với goal là giaithua(2,X), hệ thống sẽ so trùng với mệnh đề giaithua(0,1) là mệnh đề đầu tiên tìm thấy có liên quan đến khái niệm giaithua. Hệ thống sẽ hợp nhất các thông số theo thứ tự, 2 hợp nhất với 0 và X hợp nhất với 1. Công việc hợp nhất X với 1 thành công, X có giá trị là 1, nhưng 2 hợp nhất với 0 thất bại. Hệ thống sẽ tiếp tục tìm kiếm lời giải khác bằng cách so trùng với mệnh đề khác. Lần này hệ thống so trùng goal với mệnh đề giaithua(X,Y). Khi tạo mối liên quan giữa các thông số, hệ thống hợp nhất 2 với X của mệnh đề và Y với X của goal. Chúng ta sẽ ký hiệu XG là X thông số của goal. Do Y và XG đều chưa có giá trị, Prolog sẽ xem hai biến này là một. Sau đó hệ thống bắt đầu thực hiện từng sub-clause: X1 = X - 2 X1 là biến mới, và chưa có giá trị. X đã có giá trị là 2, nên X - 1 có giá trị là 1. Hợp nhất X1 với 1 ta sẽ có giá trị của X1 là 1. giaithua(X1,Y1) Ở đây mệnh đề giai thừa được gọi đệ quy. Lưu ý lúc này X1 đã có giá trị là 1, Y1 là biến mới chưa có giá trị, vì vậy nhiệm vụ của hệ thống là tìm giá trị của Y1 sao cho sub-clause giaithua(X1,Y1) cho giá trị là đúng. Và cũng như các ví dụ trên, cách thức Prolog trả lời một sub-clause cũng tương tự như khi trả lời câu hỏi từ goal, tức là lại so trùng câu hỏi với các mệnh đề đã biết So trùng với giaithua(0,1), Prolog tiến hành hợp nhất X1 với 0, Y1 với 1, do X1 đã có giá trị là 1, việc hợp nhất với 0 thất bại, Prolog phải so trùng với mệnh đề khác. So trùng với giaithua(X,Y), Prolog tiến hành hợp nhất X1 với X đồng nhất Y1 với Y. Chúng ta ký hiệu X và Y ở lần gọi đệ quy này là X2 và Y2, và sử dụng cách ký hiệu tương tự như vậy cho các biến còn lại ở lần gọi đệ quy này cũng như các lần gọi đệ quy tiếp theo. N hư vậy X2 sẽ có giá trị là 1 và Y1 sẽ có giá trị mà Y2 sẽ có. Tương tự ở lần gọi thứ nhất, các sub-clause của mệnh đề trên ở lần gọi thứ hai này sẽ lần lượt được gọi: - X12 = X2 - 1, hợp nhất X12 với X2 -1, ta có X12 có giá trị là 0. - giaithua(X12,Y12), X12 đã có giá trị là 0, Prolog sẽ tìm giá trị của Y12 bằng việc tiếp tục so trùng giaithua(X12,Y12) với các mệnh đề có liên quan: So trùng giaithua(X12,Y12) với giaithua(0,1). Do X12 đã có giá trị là 0, Prolog tiến hành hợp nhất X12 với 0 và Y12 với 1. Thực hiện tiếp sub-clause !, do câu hỏi giaithua(X12,Y12) chưa tìm được câu trả lời nào, nên sub-clause này trả lời là đúng. Việc thực hiện mệnh đề giaithua(0,1) thành công, và Y12 đã có giá trị là 1 nên câu hỏi giaithua(X12,Y12) đã có đáp số. Vị từ ! sẽ ngăn chặn việc tìm các đáp số khác, vì vậy trong trường hợp này, Prolog không tiếp tục so trùng tiếp với mệnh đề giaithua(X,Y). - Y2 = X2 * Y12, lúc này Y2 chưa có giá trị, X2 và Y12 đã có giá trị là 1 và 1 nên Prolog sẽ hợp nhất Y2 và 1. Kết quả sẽ là Y2 có giá trị là 1. N hư vậy đến đây các Gv: Trịnh Huy Hoàng Trang 73
Giáo trình Logic Toán sub-clause của mệnh đề giaithua(X2,Y2) đã thực thi thành công, và Y2 đã có giá trị là 1, và vì Y1 được đồng nhất với Y2, nên Y1 cũng sẽ có giá trị là 1. Y = X* Y1, lúc này Y chưa có giá trị, X và Y1 đã lần lượt có giá trị là 2 và 1, nên Prolog hợp nhất Y và 2*1, kết quả Y sẽ có giá trị là 2. N hư vậy đến đây các sub-clause của mệnh đề giaithua(X,Y) đã thực thi thành công, và Y đã có giá trị là 2, và vì XG được đồng nhất với Y, nên XG cũng sẽ có giá trị la ø2, và lời giải của bài toán đã được tìm thấy. Tóm tắt: Đệ quy là sức mạnh lập trình chủ yếu trên Prolog Mỗi lần gọi đệ quy, các thông số và biến cục bộ trong mỗi mệnh đề sẽ được tạo mới tương ứng với lần gọi đệ quy dó. Có thể dùng nhát cắt để ngăn chặn các lần gọi đệ quy thừa khi đã tìm ra đáp số 7. Danh sách trên Prolog Danh sách là kiểu dữ liệu cấu trúc đặc biệt trên Prolog. Có thể hiểu danh sách như một kiểu dãy một chiều, và phần tử của danh sách có thể thuộc về kiểu dữ liệu bất kỳ, tuy nhiên các phần tử trong cùng một danh sách phải cùng kiểu. Định nghĩa kiểu danh sách Kiểu danh sách là một kiểu dữ liệu (user-defined type) do người dùng định nghĩa trên Prolog. Chúng ta cần phải định nghĩa một kiểu dữ liệu danh sách trước khi sử dụng. Phần định nghĩa kiểu dữ liệu mới sẽ được khai báo sau từ khoá domains và đặt ở đầu chương trình. VD14: Khai báo một kiểu dữ liệu mới là một danh sách số nguyên trên Prolog có tên là list. domains list = integer* Ký hiệu * biểu hiện cho danh sách. list sẽ là kiểu dữ liệu danh sách có phần tử thuộc kiểu integer. Cấu trúc của danh sách Một danh sách trên Prolog bao gồm hai phần: phần đầu (head) là phần tử đầu tiên của danh sách và phần đuôi (tail) là danh sách các phần tử còn lại của danh sách. Một danh sách có thể mô tả theo hai cách: - Liệt kê các phần tử của danh sách, ví dụ: [1,2,3,4,5] - Mô tả phần đầu và phần đuôi của danh sách, ngăn cách bởi dấu |, ví dụ [1|[2,3,4,5]] VD15: Mô tả một danh sách bao gồm 5 số nguyên là 1,2,3,4,5 Gv: Trịnh Huy Hoàng Trang 74
Giáo trình Logic Toán Danh sách trên có thể mô tả theo các cách sau: [1,2,3,4,5] [1|[2,3,4,5]] [1|[2|[3,4,5]]] [1|[2|[3|[4,5]]]] [1|[2|[3|[4|[5]]]]] [1|[2|[3|[4|[5|[]]]]]] Lưu ý: danh sách rỗng có thể được mô tả như sau: [] VD16: Viết chương trình in ra phần đầu và phần đuôi của một danh sách. Chương trình này thực chất chỉ giúp chúng ta nhìn rõ hơn khái niệm về danh sách. Chương trình được viết như sau: domains list = integer* predicates indanhsach(list,integer,list) clauses indanhsach(L,H,T):- L = [H|T]. Xét khi chúng ta nhập goal vào như sau: indanhsach([1,2,3,4,5],X,Y) Prolog sẽ so trùng goal với mệnh đề indanhsach(L,H,T), L được hợp nhất với [1,2,3,4,5], X được đồng nhất với H, Y được đồng nhất với T. Khi thực hiện sub-clause L = [H|T], L được hợp nhất với [H|T], như vậy phần đầu của L sẽ hợp nhất với H, phần đuôi sẽ hợp nhất với T. Do L đã có giá trị là [1,2,3,4,5], phần đầu của L sẽ có giá trị là 1, phần đuôi sẽ có giá trị là [2,3,4,5], vậy sau khi hợp nhất, H sẽ có giá trị là 1 và L sẽ có giá trị là [2,3,4,5]. Cũng tức là X sẽ có giá trị là 1 và Y có giá trị là [2,3,4,5]. Prolog đã tìm thấy lời giải và sẽ in ra lời giải này. Lưu ý: Chương trình trên sẽ chạy sai nếu danh sách nhập vào là rỗng ([]) do lời giải của chúng ta chưa xử lý trường hợp này Phần mệnh đề cho vị từ indanhsach có thể viết lại là indanhsach([H|T],H,T). Tóm tắt Danh sách là kiểu dữ liệu cấu trúc đặc biệt do người dùng định nghĩa trên Prolog Một danh sách bao gồm hai phần: phần đầu là phần tử đầu, phần đuôi là danh sách các phần tử còn lại của danh sách. Trong trường hợp danh sách rỗng, phần đầu của danh sách sẽ không có. 8. Lập trình đệ quy với danh sách trên Prolog Khi xử lý danh sách trên Prolog, người lập trình phải từ bỏ phong cách dùng vòng lặp để xử lý dãy mà phải tận dụng kỹ thuật đệ quy để tìm ra lời giải. Chúng ta xét một số ví dụ sau đây: Gv: Trịnh Huy Hoàng Trang 75
Giáo trình Logic Toán VD17: Viết vị từ đếm xem một danh sách có bao nhiêu phần tử. Đầu tiên chúng ta phải định nghĩa được công việc mà chúng ta định làm. Chúng ta sẽ viết một vị từ như sau: dem(list,integer) Chúng ta đếm trong một danh sách có bao nhiêu phần tử. Ví dụ khi gọi goal dem([1,2,3,4],X), đáp số sẽ là X = 4 Tiếp theo chúng ta phải xác định một thuật giải phù hợp với tinh thần của Prolog. Không thể dùng vòng lặp, chúng ta phải xây dựng một giải thuật đệ quy. Một giải thuật đệ quy sẽ bao gồm hai phần: điều kiện dừng và lời gọi đệ quy. Điều kiện dừng cho bài toán này rất dễ dàng: khi danh sách không có phần tử nào, thì hiển nhiên số phần tử của nó là 0. Vậy điều kiện dừng sẽ được viết như sau: dem([],0):-!. Khi trường hợp danh sách không có phần tử nào, đáp số 0 là duy nhất, vậy chúng ta có thể dùng nhát cắt để yêu cầu Prolog không tìm thêm lời giải nào khác. Phần đệ quy hơi khó đối với những ai chưa quen với danh sách trên Prolog. Prolog chỉ cung cấp cho chúng ta cơ chế chia danh sách thành hai phần: phần tử đầu và phần đuôi danh sách các phần tử còn lại. N hư vậy lời giải gần như đã tự nó hiện ra: chúng ta sẽ gọi đệ quy để đếm phần đuôi có bao nhiêu phần tử rồi cộng nó với 1 (phần tử đầu) sẽ ra số phần tử trong một danh sách. Phần này sẽ được viết như sau: dem([H|T],X):- dem(T,X1), X = X1+1. Tư tưởng đệ quy đã được thể hiện rất rõ ràng: đếm phần đuôi T của danh sách để có được tổng X1, hợp nhất X với X1+1 sẽ cho đáp số cần tìm. Tuy nhiên chúng ta thấy ở đây biến H hòan tòan không cần dùng trong vế phải của mệnh đề. Prolog không coi đây là lỗi, nhưng sẽ "phàn nàn" về việc này. Xét về hiệu quả lập trình, hòan tòan không cần khai báo tên biến mới cho thành phần H trong trường hợp này. Có một nguyên tắc để nhận ra những biến "vô dụng" như vậy: đó là những biến chỉ xuất hiện 1 lần trong suốt mệnh đề. Đối với trường hợp này, ta nên dùng ký hiệu '_' thay cho tên biến để biểu diễn biến này không cần dùng trong thuật giải. Vậy phần đệ quy sẽ được "tinh chế" như sau: dem([_|T],X):- dem(T,X1), X = X1+1. N hư vậy toàn bộ chương trình hoàn chỉnh sẽ như sau: domains list = integer* predicates dem(list,integer) clauses dem([],0):-!. dem([_|T],X):- dem(T,X1), X = X1+1. VD18: Viết vị từ tính tổng các phần tử trong một danh sách domains list = integer* predicates Gv: Trịnh Huy Hoàng Trang 76
Giáo trình Logic Toán tong(list,integer) clauses tong([],0):-!. tong([H|T],X):- tong(T,X1), X = X1+H. Tư duy đệ quy ở đây là: chúng ta tính tổng phần đuôi của danh sách, rồi cộng nó với phần tử đầu để tính tổng danh sách. VD19: Viết vị từ kiểm tra một số nguyên có nằm trong danh sách hay không. Xác định vấn đề: chúng ta sẽ viết vị từ ptu(integer,list), khi gọi ptu(2,[1,3,5]) kết quả sẽ là N o, ngược lại khi gọi ptu(3,[1,3,5]), kết quả sẽ là Yes. Ở đây chúng ta phải xác định được các trường hợp một phần tử nằm trong một danh sách. Và chúng ta phải trình bày được các khái niệm này một cách đệ quy. Sau đây là ý tưởng của thuật giải: có hai trường hợp để một số nguyên là phần tử của một danh sách: số nguyên này là phần tử đầu của danh sách hoặc nó là phần tử của phần đuôi danh sách. Sau khi xác định được ý tưởng, chúng ta có bài giải như sau: domains list = integer* predicates ptu(integer,list) clauses ptu(H,[H|_]):-!. ptu(H,[_|T]):- ptu(H,T). Lưu ý: Chúng ta đã thay thế các biến chỉ xuất hiện một lần trong một mệnh đề bằng ký hiệu '_' như đã nói. Ở mệnh đề đầu đã có ký hiệu nhát cắt, nên nếu mệnh đề này đúng, bài toán đã có lời giải và không so trùng đến mệnh đề thứ hai. \hư vậy mệnh đề thứ hai chỉ được so trùng khi mệnh đề thứ nhất thấy bại, và vì mệnh đề thứ nhất ứng với trường hợp số nguyên cần tìm bằng với phần tử đầu của danh sách, nên khi mệnh đề thứ nhất thất bại, tức là số nguyên cần tìm không bằng với phần tử đầu của danh sách, nên trong mệnh đề thứ hai, chúng ta không cần quan tâm đến phần tử đầu của danh sách. VD20: Xác định phần tử thứ n của danh sách Khi ta gọi ptn([1,3,5,7,9],2,X) -_ X = 3 (phần tử thứ 2 của danh sách). Vì Prolog chỉ cho chúng ta truy xuất phần tử đầu tiên của danh sách, nên chúng ta phải xây dựng thuật giải đệ quy dựa trên cơ sở này: nếu n bằng 1 thì phần tử cần tìm là phần tử đầu của danh sách, ngược lại thì đó sẽ là phần tử thứ n -1 của phần đuôi danh sách. domains list = integer* Gv: Trịnh Huy Hoàng Trang 77

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.