Mở đầu về ngôn ngữ Prolog 11 Với mọi X và Y, nếu X là cha (hay mẹ) của Y thì Y là con của X. Có sự khác nhau cơ bản giữa sự kiện và luật. Một sự kiện, chẳng hạn : parent(tom, liz). là một điều gì đó luôn đúng, không có điều kiện gì ràng buộc.
Trong khi đó, các luật liên quan đến các thuộc tính chỉ được thoả mãn nếu một số điều kiện nào đó được thoả mãn. Mỗi luật bao gồm hai phần: • phần bên phải (RHS: Right Hand Side) chỉ điều kiện, còn được gọi là thân (body) của luật, và • phần bên trái (LH: Left Hand Side S) chỉ kết luận, còn được gọi là đầu (head) của luật. Nếu điều kiện parent(X, Y) là đúng, thì child(Y, X) cũng đúng và là hậu quả lôgich của phép suy luận (inference). đầu thân Câu hỏi sau đây giải thích cách Prolog sử dụng các luật : Liz có phải là con của Tom không ? ?- child(liz, tom) Thực tế, trong chương trình không có sự kiện nào liên quan đến con, mà ta phải tìm cách áp dụng các luật.
Luật trên đây ở dạng tổng quát với các đối tượng X và Y bất kỳ, mà ta lại cần các đối tượng cụ thể liz và tom. Ta cần sử dụng phép thế (substitution) bằng cách gán giá trị liz cho biến Y và tom cho X. Người ta nói rằng các biến X và Y đã được ràng buộc (bound) : X = tom và Y = liz Lúc này, phần điều kiện có giá trị parent(tom, liz) và trở thành đích con (sub-goal) để Prolog thay thế cho đích child(liz, tom). Tuy nhiên, đích này thoả mãn và có giá trị Yes vì chính là sự kiện đã thiết lập trong chương trình.
Sau đây, ta tiếp tục bổ sung các quan hệ mới. Quan hệ mẹ mother được định nghĩa như sau (chú ý dấu phẩy chỉ phép hội hay phép và lôgich) : mother(X, Y) :- parent(X, Y), woman(X). 12 Lập trình lôgic trong Prolog được hiểu là : Với mọi X và Y, X là mẹ của Y nếu X là cha (hay mẹ) của Y và X là nữ. Đồ thị sau đây minh hoạ việc định nghĩa các quan hệ child, mother và grandparent sử dụng một quan hệ khác : Trong đồ thị, người ta quy ước rằng : các nút tương ứng với các đối tượng (là các đối của một quan hệ).
Các cung nối các nút tương ứng với các quan hệ nhị phân, được định hướng từ đối thứ nhất đến đối thứ hai của quan hệ. Một quan hệ đơn được biểu diễn bởi tên quan hệ tương ứng với nhãn của đối tượng đó. Các quan hệ cần định nghĩa sẽ được biểu diễn bởi các cung có nét đứt. Mỗi đồ thị được giải thích như sau : nếu các quan hệ được chỉ bởi các cung có nét liền được thoả mãn, thì quan hệ biểu diễn bởi cung có nét đứt cũng được thoả mãn.
woman X X X parent child parent mother parent grandparent Y Y Y parent Z Hình III. Định nghĩa quan hệ con, mẹ và ông bà sử dụng một quan hệ khác. Như vậy, quan hệ ông−bà grandparent được viết như sau : grandparent(X, Z) :- parent(X, Y), parent(Y, Z). Để thuận tiện cho việc đọc chương trình Prolog, ta có thể viết một luật trên nhiều dòng, dòng đầu tiên là phần đầu của luật, các dòng tiếp theo là phần thân của luật, mỗi đích trên một dòng phân biệt.
Bây giờ quan hệ grandparent được viết lại như sau : grandparent(X, Z) :- parent(X, Y), parent(Y, Z). Ta tiếp tục định nghĩa quan hệ chị em gái sister như sau : Với mọi X và Y, X là một chị (em) gái của Y nếu (1) X và Y có cùng cha (cùng mẹ), và (2) X là nữ. Z parent parent woman X sister Y Hình III. Định nghĩa quan hệ chị (em) gái.
Chú ý cách giải thích điều kiện X và Y có cùng cha mẹ : một Z nào đó phải là một cha mẹ của X, và cũng Z đó phải là một cha mẹ của Y. Hay nói một cách khác là : Z1 là một cha mẹ của X, Z2 là một cha mẹ của Y, và Z1 đồng nhất với Z2. An là nữ, Ann và Sue cùng cha mẹ nên Ann là chị em gái của Sue, ta có : ?- sister(ann, sue). Yes Ta cũng có thể hỏi ai là chị em gái của Sue như sau : ?- sister(X, sue).
Prolog sẽ lần lượt đưa ra hai câu trả lời : X = ann ->; X = sue ->. Yes Vậy thì Sue lại là em gái của chính mình ?! Điều này sai vì ta chưa giải thích rõ trong định nghĩa chị em gái. Nếu chỉ dựa vào định nghĩa trên đây thì câu trả lời của Prolog là hoàn toàn hợp lý. Prolog suy luận rằng X và Y có thể đồng nhất với nhau, mỗi người đàn bà có cùng cha mẹ sẽ là em gái của chính mình.
Ta cần sửa lại định nghĩa bằng cách thêm vào điều kiện X và Y khác nhau. Như sẽ thấy sau này, Prolog có nhiều cách để giải quyết, tuy nhiên lúc này ta giả sử rằng quan hệ : different(X, Y) đã được Prolog nhận biết và được thoả mãn nếu và chỉ nếu X và Y không bằng nhau. Định nghĩa chị (em) gái mới như sau : sister(X, Y) :- parent(Z, X), parent(Z, Y), woman(X).2 : Ta lấy lại ví dụ cổ điển sử dụng hai tiên đề sau đây : 14 Lập trình lôgic trong Prolog Tất cả mọi người đều chết. Socrate là một người.
Ta viết trong Prolog như sau : mortal(X) :- man(X). Một định lý được suy luận một cách lôgich từ hai tiên đề này là Socrate phải chết. Ta đặt các câu hỏi như sau : ?- mortal(socrate). Yes Ví dụ III.3 : Để chỉ Paul cũng là người, còn Bonzo là con vật, ta viết các sự kiện : man(paul).
Con người có thể nói và không phải là loại vật, ta viết luật : speak(X) :- man(X), not(animal(bonzo)). Ta đặt các câu hỏi như sau : ?- speak(bonzo). Yes Ví dụ III.4 : Ta đã xây dựng các sự kiện và các luật có dạng vị từ chứa tham đối, sau đây, ta lấy một ví dụ khác về sự kiện và luật không chứa tham đối : 'It is sunny'. 'It is summer'.
'It is hot' :- 'It is summer', 'It is sunny'. 'It is cold' :- 'It is winter', 'It is snowing'. Từ chương trình trên, ta có thể đặt câu hỏi : ?- 'It is hot'. Yes Câu trả lời 'It is hot' là đúng vì đã có các sự kiện 'It is sunny' và 'It is summer' trong chương trình.
Còn câu hỏi « ?- 'It is cold.' » có câu trả lời sai. Mở đầu về ngôn ngữ Prolog 15 III. Định nghĩa luật đệ quy Bây giờ ta tiếp tục thêm một quan hệ mới vào chương trình. Quan hệ này chỉ sử dụng quan hệ parent, và chỉ có hai luật.
Luật thứ nhất định nghĩa các tổ tiên trực tiếp, luật thứ hai định nghĩa các tổ tiên gián tiếp. Ta nói rằng X là một tổ tiên gián tiếp của Z nếu tồn tại một liên hệ cha mẹ (ông bà) giữa X và Z : Trong cây gia hệ ở Hình III.1, Tom là tổ tiên trực tiếp của Liz, và tổ tiên gián tiếp của Sue. Ta định nghĩa luật 1 (tổ tiên trực tiếp) như sau : Với mọi X và Z, X là một tổ tiên của Z nếu X là cha mẹ của Z. X X parent ancestor parent Z (a) parent ancesto r parent Y (b) Hình III.
Quan hệ tổ tiên : (a) X là tổ tiên trực tiếp của Z, (b) X là tổ tiên gián tiếp của Z. Định nghĩa luật 2 (tổ tiên gián tiếp) phức tạp hơn, trình Prolog trở nên dài dòng hơn, mỗi khi càng mở rộng mức tổ tiên hậu duệ như chỉ ra trong Hình III. Kể cả luật 1, ta có quan hệ tổ tiên được định nghĩa như sau : ancestor(X, Z) :- % luật 1 định nghĩa tổ tiên trực tiếp parent(X, Z). 16 Lập trình lôgic trong Prolog ancestor(X, Z) :- % ngũ đại đồng đường parent(X, Y1), parent(Y1, Y2), parent(Y2, Y3), parent(Y3, Z).
Tuy nhiên, tồn tại một cách định nghĩa tổ tiên gián tiếp ở mức bất kỳ nhờ phép đệ quy (recursive) như sau : Với mọi X và Z, X là một tổ tiên của Z nếu tồn tại Y sao cho (1) X là cha mẹ của Y và (2) Y là một tổ tiên của Z. X X X parent parent ancestor Y1 Y Y1 parent parent ancestor Y2 ancestor Z Y2 parent Y3 Z Z Hình III. Các cặp tổ tiên hậu duệ gián tiếp ở các mức khác nhau. X = jim ->; X = ann ->; X = sue ->; X = bill Yes Mở đầu về ngôn ngữ Prolog 17 Trong Prolog, hầu hết các chương trình phức tạp đều sử dụng đệ quy, đệ quy là một khả năng mạnh của Prolog.
Z ancestor Hình III.Dạng đệ quy của quan hệ tổ tiên (được quay ngang cho thuận tiện). Cho đến lúc này, ta đã định nghĩa nhiều quan hệ (parent, woman, man, grandparent, child, sister, mother và ancestor). Ta thấy mỗi quan hệ chỉ tương ứng với một mệnh đề, tuy nhiên, quan hệ ancestor lại có hai mệnh đề. Người ta nói rằng những mệnh đề này liên quan (concern) đến quan hệ ancestor.
Trong trường hợp tất cả các mệnh đề đều liên quan đến một quan hệ, người ta nhận được một thủ tục (procedure). Sử dụng biến trong Prolog Khi tính toán, NSD có thể thay thế một biến trong một mệnh đề bởi một đối tượng khác. Lúc này ta nói biến đã bị ràng buộc. Các biến xuất hiện trong một mệnh đề được gọi là biến tự do.
Người ta giả thiết rằng các biến là được lượng tử toàn thể và được đọc là «với mọi». Tuy hiên có nhiều cách giải thích khác nhau trong trường hợp các biến chỉ xuất hiện trong phần bên phải của luật. có thể được đọc như sau : (a) Với mọi X và Y, nếu X là cha (hay mẹ) của Y thì X có một người con. Khi một biến chỉ xuất hiện một lần trong một mệnh đề thì không cần đặt tên cho nó.
Prolog cho phép sử dụng các biến nặc danh (anonymous variable) là các biến có tên chỉ là một dấu gạch dưới dòng _. Ta xét ví dụ sau : have_a_child(X) :- parent(X, Y). 18 Lập trình lôgic trong Prolog Luật trên nêu lên rằng với mọi X, X có một con nếu X là cha của một Y nào đó. Ta thấy đích have_a_child không phụ thuộc gì vào tên của con, vì vậy có thể sử dụng biến nặc danh như sau : have_a_child(X) :- parent(X, _).
Mỗi vị trí xuất hiện dấu gạch dưới dòng _ trong một mệnh đề tương ứng với một biến nặc danh mới.