Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Lập trình và ngôn ngữ lập trình » Lập trình logic

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • VOCW

    This module and collection are included inLens: Vietnam OpenCourseWare's Lens
    By: Vietnam OpenCourseWare

    Click the "VOCW" link to see all content affiliated with them.

Recently Viewed

This feature requires Javascript to be enabled.
 

Lập trình logic

Module by: ThS. Nguyễn Văn Linh. E-mail the author

TỔNG QUAN

Mục tiêu

Sau khi học xong chương này, sinh viên cần phải nắm:

  • Khái niệm về lập trình logic.
  • Các nguyên tắc trong lập trình logic.
  • Viết chương trình đơn giản bằng ngôn ngữ Prolog.

Nội dung cốt lõi

  • Lập trình logic.
  • Căn bản về ngôn ngữ lập trình Prolog.

Kiến thức cơ bản cần thiết

Kiến thức và kĩ năng lập trình căn bản

GIỚI THIỆU VỀ LẬP TRÌNH LOGIC

Trong lập trình logic, ta có thể sử dụng các vị từ để định nghĩa các khái niệm của tất cả các môn khoa học khác.

Ví dụ định nghĩa một số nguyên tố:

Số nguyên tố N là một số nguyên lớn hơn 1, chỉ chia hết cho 1 và chính nó.

Để xét xem số N có phải là số nguyên tố hay không, người ta thường sử dụng dấu hiệu nhận biết: Số nguyên tố là một số nguyên dương, không chia hết cho mọi số nguyên tố nhỏ hơn nó và 2 là số nguyên tố nhỏ nhất.

Dấu hiệu này có thể mô tả bằng các vị từ như sau:

  • 2 là một số nguyên tố.
  • N là một số nguyên tố nếu N>0, M là số nguyên tố nào đó, M<N và N không chia hết cho M.

Khi mô tả bài toán dưới dạng logic vị từ, ta có thể yêu cầu hệ thống tìm kiếm các lời giải liên quan đến các khai báo đó. Bài toán cần giải được xem là “mục tiêu” mà hệ thống phải chứng minh trên cơ sở các tri thức đã được khai báo.

Như thế, toàn bộ các ký hiệu của ngôn ngữ lập trình suy về một công thức đặc biệt:

  • Phát sinh từ một yêu cầu.
  • Nhằm chứng minh một mục tiêu. Để trả lời cho câu hỏi đó hệ thống xem nó như là một “đích” và cố chứng minh “đích” đó bằng cách tạo những suy diễn trên cơ sở các tri thức đã khai báo.

Một ngôn ngữ logic có thể được dùng trong giai đoạn đặc tả yêu cầu của quy trình xây dựng một sản phẩm phần mềm. Hơn thế nữa, logic vị từ cho phép biểu diễn hầu hết các khái niệm và các định lý trong các bộ môn khoa học.

Một trong những ngôn ngữ lập trình logic có hỗ trợ rất nhiều cho lĩnh vực trí tuệ nhân tạo mà ta xét đến ở đây đó là ngôn ngữ Prolog.

NGÔN NGỮ PROLOG

Giới thiệu

Prolog là một ngôn ngữ cấp cao, có đặc điểm gần với ngôn ngữ tự nhiên, từ những người mới học đến những lập trình viên chuyên nghiệp đều có thể tiếp cận một cách nhanh chóng, viết ra một chương trình ứng dụng hữu ích.

Prolog ra đời vào năm 1973 do C.Camerauer (Đại học Marseilles, Pháp) và nhóm đồng sự phát triển. Từ đó đến nay, qua nhiều lần cải tiến, đặc biệt hãng Borland cho ra đời phần mềm TURBO PROLOG với nhiều ưu điểm, thuận tiện cho người sử dụng. Để giải quyết một số vấn đề, ta nhận thấy sử dụng ngôn ngữ Prolog cho ta chương trình gọn nhẹ hơn nhiều so với các ngôn ngữ khác.

Khác với những ngôn ngữ cấu trúc như Pascal, hay C mà ta đã làm quen, Prolog là một ngôn ngữ mô tả, với một số sự kiện và quy luật suy diễn đã mô tả, Prolog sẽ suy luận cho ta các kết quả.

Các yếu tố cơ bản của Turbo Prolog

Trong một chương trình Prolog, ta cần khai báo các yếu tố sau đây: đối tượng, quan hệ giữa các đối tượng, sự kiện và các luật.

Đối tượng

Gồm có các hằng và biến. Hằng mang giá trị cho sẵn ở đầu chương trình hoặc trong quá trình viết ta đưa vào; Các biến có giá trị thay đổi sẽ được gán giá trị khi chạy chương trình. Tên biến là một ký tự hoa hoặc một chuỗi ký tự, bắt đầu bằng một ký tự hoa.

Có một loại biến đặc biệt gọi là biến tự do, biến này không có tên và người ta dùng ký hiệu _ (dấu gạch dưới) thay cho tên biến.

Quan hệ giữa các đối tượng

Quan hệ giữa các đối tượng được dùng dưới hình thức vị từ.

Ví dụ: Thich(X,Y) là vị từ diễn tả câu “X thích Y” trong ngôn ngữ tự nhiên.

Blue(car) là vị từ diễn tả câu “Car is blue”.

Như vậy các vị từ sẽ bao gồm tên của vị từ và các đối số của nó. Các đối số được đặt trong ngoặc và phân cách nhau bởi dấu phẩy.

Sự kiện và luật

Sự kiện là một vị từ diễn tả một sự thật.

Ví dụ: “2 là một số nguyên tố” là một sự kiện vì nó diễn tả sự thật 2 là một số nguyên tố.

Luật là vị từ diễn tả quy luật suy diễn mà ta công nhận đúng. Luật được trình bày dưới dạng một mệnh đề.

Ví dụ để suy diễn số nguyên N bất kỳ là một số nguyên tố ta viết:

“N là một số nguyên tố nếu N>0, M là số nguyên tố nào đó, M<N và N không chia hết cho M”.

Cấu trúc của một chương trình Prolog

Một chương trình Prolog thường gồm có 3 hoặc 4 đoạn cơ bản: clauses, predicates, domains và goal. Phần goal có thể bỏ đi, nếu ta không thiết kế goal trong chương trình, thì khi thực hiện, hệ thống sẽ yêu cầu ta nhập goal vào.

Phần Domains

Đây là phần định nghĩa kiểu mới dựa vào các kiểu đã biết. Các kiểu được định nghĩa ở đây sẽ được sử dụng cho các đối số trong các vị từ. Nếu các vị từ sử dụng đối số có kiểu cơ bản thì có thể không cần phải định nghĩa lại các kiểu đó. Tuy nhiên để cho chương trình sáng sủa, người ta sẽ định nghĩa lại cả các kiểu cơ bản.

Cú pháp: <danh sách kiểu mới> = <kiểu đã biết> hoặc <danh sách kiểu mới> = <danh sách kiểu đã biết>

Trong đó các kiểu mới phân cách nhau bởi dấu phẩy, còn các kiểu đã biết phân cách nhau bởi dấu chấm phẩy.

Ví dụ:

Domains

ten, tac_gia, nha_xb, dia_chi = string

nam, thang, so_luong = integer

dien_tich = real

nam_xb = nxb(thang, nam)

do_vat = sach(tac_gia, ten, nha_xb, nam_xb); xe(ten, so_luong); nha(dia_chi, dien_tich)

Trong ví dụ trên, ta đã định nghĩa các kiểu mới, trong đó các kiểu mới ten, tac_gia, nha_xb, dia_chi dựa vào cùng một kiểu đã biết là string; các kiểu mới nam, thang, so_luong dựa vào cùng một kiểu đã biết là integer; kiểu mới dien_tich dựa vào kiểu đã biết là real; kiểu mới năm_xb dựa vào kiểu nxb được xây dựng từ các kiểu đã biết là thang, nam; còn kiểu do_vat lại dựa vào các kiểu sach, xe, nha mà các kiểu này lại dựa vào các kiểu đã biết.

Phần Predicates

Đây là phần bắt buộc phải có. Trong phần này chúng ta cần phải khai báo đầy đủ các vị từ sử dụng trong phần Clauses, ngoại trừ các vị từ mà Turbo Prolog đã xây dựng sẵn.

Cú pháp: <Tên vị từ> (<danh sách các kiểu>)

Các kiểu là các kiểu cơ bản hoặc là các kiểu đã được định nghĩa trong phần domains và được viết phân cách nhau bơi dấu phẩy.

Ví dụ:

Predicates

so_huu (ten, do_vat)

so_nguyen_to(integer)

Trong ví dụ trên ta khai báo hai vị từ. Trong đó vị từ so_huu (ten, do_vat) để chỉ một người có tên là ten sẽ sở hữu môt do_vat nào đó. Còn vị từ so_nguyen_to(integer) để xét xem một số integer nào đó có phải là số nguyên tố hay không.

Phần Clauses

Đây là phần bắt buộc phải có dùng để mô tả các sự kiện và các luật, sử dụng các vị từ đã khai báo trong phần predicates.

Cú pháp:

<Tên vị từ>(<danh sách các tham số>) <kí hiệu>

<Tên vị từ 1>(<danh sách các tham số 1>) <kí hiệu>

………

<Tên vị từ N>(<danh sách các tham số N>) <kí hiệu>

Trong đó: Tên vị từ phải là các tên vị từ đã được khai báo trong phần predicates. Các tham số có thể là các hằng hoặc biến có kiểu tương thích với các kiểu tương ứng đã được khai báo trong các vị từ ở trong phần predicates; các tham số được viết cách nhau bởi dấu phẩy. Các kí hiệu bao gồm:

:- (điều kiện nếu).

, (điều kiện và).

; (điều kiện hoặc).

. (kết thúc vị từ)

Ví dụ:

Clauses

so_nguyen_to(2):-!.

so_nguyen_to(N):-N>0,

so_nguyen_to(M),

M<N,

N MOD M <>0.

so_huu(“Nguyen Van A”, sach(“Do Xuan Loi”, “Cau truc DL”, “Khoa hoc Ky thuat”, nxb(8,1985))).

Chú ý: Nếu trong các tham số của một vị từ có biến thì biến này phải xuất hiện ít nhất 2 lần trong vị từ đó hoặc trong các vị từ dùng để suy diễn ra vị từ đó. Nếu chỉ xuất hiện một lần thì bắt buộc phải dùng biến tự do.

Ví dụ: Để diễn tả sự kiện: Tổ hợp chập 0 của N (N bất kỳ) bằng 1, ta không thể viết Tohop(N,0,1) vì biến N chỉ xuất hiện đúng một lần trong vị từ này, do đó ta phải viết Tohop(_,0,1) .

Phần Goal

Bao gồm các mục tiêu mà ta yêu cầu Turbo Prolog xác định và tìm kết quả. Đây là phần không bắt buộc phải có. Nếu ta viết sẵn trong chương trình thì đó gọi là goal nội; Nếu không, khi chạy chương trình Turbo Prolog sẽ yêu cầu ta nhập goal vào, lúc này gọi là goal ngoại.

Cú pháp phần goal giống như cú pháp phần clauses. Tức là ta đưa vào một hoặc một số các vị từ.

Nếu tất cả các tham số của vị từ là hằng thì kết quả nhận được là Yes (đúng) hoặc No (sai). Nếu trong các tham số của vị từ có biến thì kết quả trả về sẽ là các giá trị của biến.

Ngoài các phần chủ yếu nói trên, ta có thể đưa vào các phần liên quan đến khai báo hằng, các tập tin liên quan hoặc chỉ thị dịch.

Ví dụ:

Constants

Pi = 3.141592653

Một số ví dụ về chương trình prolog

Ví dụ 1: Xét xem một số N có phải là số nguyên tố hay không.

domains

so_nguyen = integer

predicates

so_nguyen_to(so_nguyen)

Clauses

so_nguyen_to(2):-!.

so_nguyen_to(N):-N>0,

so_nguyen_to(M),

M<N,

N MOD M <>0.

goal

so_nguyen_to(13).

Ví dụ 2: Giả sử ta có bảng số liệu như sau:

Bảng 1
Tên người giới tính Đặc điểm Tiêu chuẩn kết bạn
lan nữ đẹp, khoẻ, tốt, khoẻ, thông minh, đẹp
hồng nữ đẹp, thông minh, giàu khoẻ, thông minh, giàu
thuỷ nữ tốt, khoẻ, giàu đẹp, khoẻ, thông minh
anh nam khoẻ, giàu, thông minh đẹp, thông minh, tốt
bình nam đẹp, khoẻ, thông minh đẹp, khoẻ
hùng nam giàu, thông minh, khoẻ tốt, thông minh, khoẻ

Tiêu chuẩn kết bạn là hai người khác phái, người này hội đủ các tiêu chuẩn của người kia và ngược lại. Hãy viết chương trình để tìm ra các cặp có thể kết bạn với nhau.

domains

ten, g_tinh = symbol

predicates

gioi_tinh(ten, g_tinh)

dep(ten)

tot(ten)

giau(ten)

thong_minh(ten)

khoe(ten)

thich(ten,ten)

ket_ban(ten,ten)

clauses

gioi_tinh(lan,nu).

gioi_tinh(hong,nu).

gioi_tinh(thuy,nu).

gioi_tinh(anh,nam).

gioi_tinh(binh,nam).

gioi_tinh(hung,nam).

dep(lan).

dep(hong).

dep(binh).

khoe(thuy).

khoe(lan).

khoe(binh).

khoe(anh).

khoe(hung).

tot(lan).

tot(thuy).

thong_minh(hong).

thong_minh(anh).

thong_minh(hung).

thong_minh(binh).

giau(hong).

giau(thuy).

giau(hung).

thich(lan,X):-khoe(X), dep(X), thong_minh(X).

thich(hong,X):-khoe(X), thong_minh(X), giau(X).

thich(thuy,X):-khoe(X), dep(X), thong_minh(X).

thich(ann,X):-dep(X), tot(X), thong_minh(X).

thich(binh,X):-dep(X), khoe(X).

thich(hung,X):-khoe(X), tot(X), thong_minh(X).

ket_ban(X,Y):- gioi_tinh(X,M),

gioi_tinh(Y,N),

M<>N,

thich(X,Y),

thich(Y,X).

Các nguyên tắc của ngôn ngữ Prolog

Việc giải quyết vấn đề trong ngôn ngữ Prolog chủ yếu dựa vào hai nguyên tắc sau: Đồng nhất, quay lui.

Đồng nhất

Một quan hệ có thể đồng nhất với một quan hệ nào đó cùng tên, cùng số lượng tham số, các đại lượng con cũng đồng nhất theo từng cặp.

Một hằng có thể đồng nhất với một hằng.

Một biến có thể đồng nhất với một hằng nào đó và có thể nhận luôn giá trị hằng đó.

Chẳng hạn trong ví dụ 2 nói trên nếu ta sử dụng goal dep(lan) thì có kết quả là Yes. Nếu ta dùng goal dep(X) thì sẽ có 3 kết quả: X=lan, X=hong và X=binh.

Khi ta dùng goal dep(lan) thì dep(lan) sẽ đồng nhất với sự kiện dep(lan) trong phần clauses và do hai vị từ đồng nhất với nhau và hai đối số hằng đồng nhất nhau nên kết quả là Yes.

Khi dùng goal dep(X) thì dep sẽ được đồng nhất với dep và biến X đồng nhất với hằng lan, do đó ta có kết quả X=lan. Tương tự X=hong và X=binh.

Quay lui

Giả sử hệ thống đang chứng minh goal g, trong đó g được mô tả như sau:

g :- g1, g2, …, gj-1, gj, …, gn.

Khi các gi kiểm chứng từ trái sang phải, đến gj là sai thì hệ thống sẽ quay lui lại gj-1 để tìm lời giải khác.

Chẳng hạn trong ví dụ 2 nói trên, khi ta yêu cầu Goal: thich(lan,X), ta được X=binh.

Vị từ thich(lan,X) sẽ được đồng nhất với thich(lan,X) trong phần clauses, theo đó hệ thống phải chứng minh thich(lan,X):-khoe(X), dep(X), thong_minh(X).

  • Trước hết đồng nhất khoe(X) với khoe(thuy) => X=thuy.
  • Do dep(thuy) sai nên quay lui đồng nhất khoe(X) với khoe(lan) => X=lan.
  • Do dep(lan) đúng nên tiếp tục kiểm tra thong_minh(lan).
  • Do thong_minh(lan) sai nên quay lui để đồng nhất khoe(X) với khoe(binh) để có X=binh, sau đó kiểm tra thấy dep(binh) và thong_minh(binh) đều đúng nên X=binh là một nghiệm.

Bộ ký tự, từ khoá

Prolog dùng bộ ký tự sau: các chữ cái và chữ số (A – Z, a – z, 0 – 9); các toán tử (+, -, *, /, <, =, >) và các ký hiệu đặc biệt.

Một số từ khoá:

  1. Trace: Khi có từ khoá này ở đầu chương trình, thì chương trình được thực hiện từng bước để theo dõi; dùng phím F10 để tiếp tục.
  2. Fail: Khi ta dùng goal nội, chương trình chỉ cho ta một kết quả (mặc dù có thể còn những kết quả khác), để nhận về tất cả các kết quả khi chạy goal nội, ta dùng toán tử Fail.
  3. ! hay còn gọi là nhát cắt, goal ngoại luôn cho ta mọi kết quả, muốn nhận chỉ một kết quả từ goal ngoại, ta dùng ký hiệu !.

Các kiểu dữ liệu

Trong prolog có kiểu dữ liệu chuẩn và kiểu do người lập trình định nghĩa.

Kiểu dữ liệu chuẩn

Là kiểu dữ liệu do prolog định nghĩa sẵn. Prolog cung cấp các kiểu dữ liệu chuẩn là: char, integer, real, string và symbol.

  1. Char: Là kiểu ký tự. Hằng ký tự phải nằm giữa hai dấu nháy đơn.

Ví dụ: ‘a’, ‘#’.

  1. Integer: Là kiểu số nguyên, tập giá trị bao gồm các số nguyên từ -32768 đến 32767.
  2. Real: Là kiểu số thực, tập giá trị bao gồm các số thực thuộc hai đoạn: đoạn các số âm từ -10307 đến -10-307 và đoạn số dương từ 10-307 đến 10307.
  3. String: Là kiểu chuỗi ký tự. Hằng chuỗi ký tự phải nằm giữa hai dấu nháy kép.

Ví dụ: “Turbo prolog 2.0”

  1. Symbol: Là một kiểu sơ cấp, có hình thức giống chuỗi ký tự. Hằng symbol có hai dạng: Dãy các chữ, số và dấu gạch dưới viết liên tiếp, ký tự đầu phải viết thường (chẳng hạn: telephone_number); Dãy các ký tự ở giữa một cặp hai nháy kép (giống như chỗi ký tự)
  2. Một số phép toán của các kiểu

Phép toán số học

Bảng 2
Phép toán Ý nghĩa Kiểu của đối số Kiểu kết quả
+ Cộng hai số Integer, real giống kiểu đối số
- Trừ hai số Integer, real giống kiểu đối số
* Nhân hai số Integer, real giống kiểu đối số
/ Chia hai số Integer, real giống kiểu đối số
Mod Phép chia lấy phần dư Integer Integer
Div Phép chia lấy phần nguyên Integer Integer

Phép toán quan hệ

Bảng 3
Phép toán Ý nghĩa Kiểu của đối số Kết quả
< Nhỏ hơn Char, integer, real, string Yes hoặc No
<= Nhỏ hơn hay bằng Char, integer, real, string Yes hoặc No
= Bằng Char, integer, real, string Yes hoặc No
> Lớn hơn Char, integer, real, string Yes hoặc No
>= Lớn hơn hay bằng Char, integer, real, string Yes hoặc No
<> hay >< Khác Char, integer, real, string Yes hoặc No

Các vị từ như các hàm toán học

Bảng 4
Vị từ Ý nghĩa Kiểu của đối số Kiểu kết quả Ví dụ
Sin(X) Tính sin của X real real  
Tan(X) Tính tang của X real real  
Arctan(X) Tính arctang của X real real  
Exp(X) Tính eX real real  
Ln(X) Tính logarit cơ số e của X real real  
Log(X) Tính Logarit cơ số 10 của X real real  
SQRT(X) Tính căn bậc hai của X real real  
ROUND(X) Cho ta số nguyên là số X được làm tròn, dấu là dấu của X real integer round(2.3)=2round(2.5)=3round(-2.5)=-2round(-2.6)=-3
TRUNC(X) Cho phần nguyên của số X, dấu là dấu của X real integer trunc(2.5)=2trunc(-2.6)=-2
ABS(X) Cho ta trị tuyệt đối của X real real  
Random(X) Cho ta số thực X nằm trong khoảng [0, 1) real real  
Random(Y, X) Cho ta số nguyên X nằm trong khoảng [0, Y) real integer  

Toán tử NOT(X) : Nếu X là Yes thì NOT(X) là No và ngược lại.

Các kiểu dữ liệu do người lập trình định nghĩa

  1. Kiểu mẩu tin:

Cú pháp: <tên kiểu mẩu tin> = tên mẩu tin (danh sách các kiểu phần tử)

Ví dụ:

Domains

ten, tac_gia, nha_xb, dia_chi = string

nam, thang, so_luong = integer

dien_tich = real

nam_xb = nxb(thang, nam)

do_vat = sach(tac_gia, ten, nha_xb, nam_xb); xe(ten, so_luong); nha(dia_chi, dien_tich)

predicates

so_huu(ten,do_vat)

clauses

so_huu(“Nguyen Van A”, sach(“Do Xuan Loi”, “Cau truc DL”, “Khoa hoc Ky thuat”, nxb(8,1985))).

so_huu(“Le thi B”, xe(“Dream II”, 2)).

so_huu(“Nguyen Huu C”, nha(“3/1 Ly Tu Trong, tp Can Tho”, 100.5))

  1. Kiểu danh sách

Cú pháp: <tên kiểu danh sách> = <tên kiểu phần tử>*

Ví dụ:

Domains

intlist = integer*

Một danh sách là một dãy các phần tử phân cách nhau bởi dấu phẩy và đặt trong cặp dấu ngoặc vuông.

Ví dụ:

[]% Danh sách rỗng

[1,2,3] % Danh sách gồm ba số nguyên 1, 2 và 3.

Cấu trúc của danh sách bao gồm hai phần: Phần đầu là phần tử đầu tiên của danh sách và phần đuôi là một danh sách của các phần tử còn lại.

Danh sách được viết theo dạng [X|Y] thì X là phần tử đầu và Y là danh sách đuôi. Chẳng hạn trong danh sách [1,2,3] thì đầu là số nguyên 1 và đuôi là danh sách [2,3].

Trong danh sách cũng có thể dùng biến tự do, chẳng hạn ta có thể viết [_|Y] để chỉ một danh sách có đầu là một phần tử nào đó và có đuôi là danh sách Y.

Các hàm xuất nhập chuẩn

Xuất ra màn hình

  1. Write( Arg1, Arg2, … ,Argn) in ra màn hình giá trị của các đối số.
  2. Writef( Formatstring, Arg1, Arg2, … ,Argn) in ra màn hình giá trị của các đối số theo định dạng được chỉ định trong Formastring.

Trong đó Formastring là một chuỗi có thể là:

  • “%d”: In số thập phân bình thường; đối số phải là char hoặc integer.
  • “%c”: Đối số là một số integer, in ký tự có mã Ascci là đối số đó, chẳng hạn writef(“%c”,65) được A.
  • “%e”: In số thực dưới dạng lũy thừa của 10.
  • “%x”: In số Hexa; đối số phải là char hoặc integer.
  • “%s”: In một chuỗi hoặc một symbol.

Nhập vào từ bàn phím

  1. Readln(X): Nhập một chuỗi ký tự vào biến X.
  2. ReadInt(X): Nhập một số nguyên vào biến X.
  3. ReadReal(X): Nhập một số thực vào biến X.
  4. ReadChar(X): Nhập vào một ký tự vào biến X.

Kỹ thuật đệ quy

Đệ quy là kỹ thuật lập trình được sử dụng trong nhiều ngôn ngữ. Trong Turbo Prolog ta sử dụng đệ quy khi một vị từ được định nghĩa nhờ vào chính vị từ đó.

Như đã nói trong chương lập trình hàm, trong chương trình đệ quy phải có ít nhất một trường hợp dừng và lời gọi đệ quy phải chứa yếu tố dẫn đến trường hợp dừng. Trong Prolog, trường hợp dừng được thể hiện bằng một sự kiện, yếu tố dẫn đến trường hợp dừng thể hiện bằng một biến, liên hệ với biến ban đầu bởi một công thức.

Ví dụ 1: Tính n giai thừa.

Predicates

Facto (integer, integer)

Clauses

Facto(0,1):- !.

Facto(N, FactN) :- N > 0, M = N – 1, facto(M, factM), factN = N*factM.

Ở ví dụ trên ta đã định nghĩa một vị từ dùng để tính giá trị giai thừa của một số tự nhiên, đối số thứ nhất là số cần tính giai thừa và đối số thứ hai dùng để nhận giá trị trả về.

Trường hợp dừng ở đây được xác đinh bởi sự kiện 0 giai thừa là 1.

Để tính N! ta tính M! với M= N-1. Yếu tố dẫn đến trường hợp dừng là biến M có giá trị bằng N-1.

Ví dụ 2: Xác định một phần tử trong danh sách các symbol

domains

symbol_list = symbol*

predicates

element1(integer,symbol_list,symbol)

element (integer,symbol_list,symbol)

clauses

% element1 không suy diễn ngược được

element1(1,[X|_],X).

element1(N,[_|L],Y):-M=N-1,

element1(M,L,Y).

% element có thể suy diễn ngược

element(1,[X|_],X).

element(N,[_|L],Y):-element(M,L,Y),

N=M+1.

Sự suy diễn thuận chiều là cho danh sách và vị trí, tìm được phần tử tại vị trí đó, chẳng hạn, nếu ta đưa vào goal element(2,[a,b,c,d],X) ta được X=b.

Sự suy diễn ngược ở đây là cho danh sách và phần tử, tìm được vị trí của phần tử đó, chẳng hạn, nếu ta đưa vào goal element(N,[a,b,c,d], b) ta được N=2.

Ví dụ 3: Sắp xếp một danh sách các số nguyên

domains

list=integer*

predicates

insert(integer,list,list)

sort(list,list)

clauses

insert(E,[],[E]).

insert(E,[A|B],[E,A|B]):-E<=A.

insert(E,[A|B],[A|C]):-E>A,insert(E,B,C).

sort([],[]).

sort([X|R1],L):-sort(R1,R),

insert(X,R,L).

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks