Chương 8: Ngôn ngữ lập trình logic

Giảng viên: Ph.D Nguyễn Văn Hòa Khoa KT-CN-MT – ðH An Giang

1

Nội dung

(cid:1) Giới thiệu lập trình logic (cid:1) Mệnh ñề (cid:1) Ngôn ngữ Turbo ProLog

2

Giới thiệu lập trình logic

(cid:1) Các họ ngôn ngữ lập trình bậc cao (cid:2) Lập trình mệnh lệnh (imparative)

(cid:1) Thủ tục (procedural) (cid:1) Hướng ñối tượng (object)

(cid:2) Lập trình khai báo (declarative)

(cid:1) Hàm (functional) (cid:1) Logic

3

Giới thiệu lập trình logic

(cid:1) Phương thức lập trình khai báo khác với phương

thức LT mệnh lệnh ở những ñiểm nào? (cid:1) LT logic là LT khai báo (declarative) (cid:2) Dùng ngôn ngữ mô tả ñể ñặc tả các vấn ñề (cid:2) Nhấn mạnh kết quả mong ñợi hơn là cách thức nhận

(cid:1) Ứng dụng nhiều trong xử lý ngôn ngữ tự nhiên và

Trí tuệ nhân tạo

4

ñược kết quả

Giới thiệu lập trình logic

(cid:1) Một chương trình logic (Prolog) là tập hợp các

mệnh ñề

(cid:1) Mỗi một mệnh ñề ñược xây từ nhiều vị từ (cid:1) Vị từ là phát biểu về một ñối tượng có thể là ñúng

hoặc sai

fi Chương trình Prolog = các ñối tượng dữ liệu và

quan hệ giữa các ñối tượng dữ liệu

5

Giới thiệu lập trình logic

(cid:1) Hạng (term) ñược xem là ñối tượng dữ liệu (cid:1) Hạng gồm:

(cid:2) Hạng sơ cấp (elementary term) như hằng, biến (cid:2) Hạng phức hợp (compound term) như một hàm tử

6

(functor) có chứa các ñối, có dạng: (cid:1) Tên_hàm_tử(ñối1, ñối2, …) (cid:1) VD student(an)

Giới thiệu lập trình logic

(cid:1) Tam ñoạn luận

nguoi(socrates).

chet(X):- nguoi(X).

(cid:2) Socrates là người (cid:2) Mọi người ñều phải chết ⇒ Socrates phải chết

robber(jerry). childof(tom,john). rich(john). rich(X):- childof(X,Y), rich(Y) Rich(X):- robber(X)

(cid:2) Jerry là một kẻ cướp (cid:2) Tom là con của John (cid:2) John thì giàu có (cid:2) X là kẻ giàu có nếu như X có cha giàu có hoặc X là một

7

kẻ cướp

Mệnh ñề (cid:1) Một mệnh ñề có thể có một trong hai hình thức

sau: (cid:2) Sự kiện (fact): khẳng ñịnh 1 thực thể có 1 hoặc vài tính

(cid:2) Luật: ñịnh nghĩa quan hệ ñựa vào các quan hệ;

chất; woman(thuy), man(an)

(cid:1) Chương trình prolog là tập hợp các sự kiện và luật

xử lí và mô tả quan hệ giữa các ñối tượng.

(cid:1) Qui ước sự kiện:

(cid:2) P(A): A có tính chất P; student(an) (cid:2) P(A,B): A là P ñối với B; husband(an,thuy) (cid:2) P(A1,A2,…, An): P là tên của tính chất; A1…An là các

wife(A,B):- husband(B,A)

8

ñối; nguyentu(atom, symbol)

Mệnh ñề

(cid:1) Luật:

(cid:2) Từ nếu ñược viết «:-» trong Prolog (cid:2) Luật gồm có 2 phần

(cid:1) Phần bên trái chỉ kết luận, ñược gọi là ñầu (head) của luật (cid:1) Phần bên phải chỉ ñiều kiện, ñược gọi là thân của luật. Nếu có

nhiều ñiều kiện thì chúng ñược cách nhau bởi dấu phẩy.

(cid:2) Sự khác nhau giữa sự kiện và luật (cid:1) Sự kiện là khẳng ñịnh luôn luôn ñúng (cid:1) Luật do các ñiều kiện trong phần thân quyết ñịnh nên có thể

ñúng hoặc sai

9

robber(jerry). childof(tom,john). rich(john). rich(X):- childof(X,Y), rich(Y) Rich(X):- robber(X)

Ngôn ngữ Turbo Prolog

(cid:1) Prolog: Programming in logic (cid:1) 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

(cid:1) Prolog là một ngôn ngữ cấp cao (cid:1) Có ñặc ñiểm gần với ngôn ngữ tự nhiên (cid:1) Turbo Prolog ñược phát triển bởi Borland

10

Ngôn ngữ Turbo Prolog (tt)

(cid:1) 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ả

(cid:1) Ví dụ

hanhphuc(xeda)?

11

nguoi(socrates). nguoi(xeda). vua(xeda). hanhphuc(socrates)? xanhphuc(X):- vua(X),nguoi(X). hanhphuc(Y)?

Chương trình Turbo Prolog mẫu

domains

nguoi = string

predicates

cha(nguoi,nguoi) me(nguoi,nguoi) ong_noi(nguoi,nguoi) ong_ngoai(nguoi,nguoi)

clauses

/*cac qui tac */ ong_noi(X,Y):- cha(X,Z),cha(Z,Y). ong_ngoai(X,Y):- cha(X,Z),me(Z,Y). /* cac su kien */ cha(nam,minh). cha(minh,lam). cha(long,giang). cha(long,thu). me(thu,phi).

12

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

(cid:1) 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

(cid:1) ðối tượng

(cid:2) Gồm có các hằng và biến (cid:2) Hằng mang giá trị cho sẵn ở ñầu chương trình (cid:2) Các biến có giá trị thay ñổi sẽ ñược gán giá trị khi chạy

(cid:2) Tên biến là một ký tự hoa hoặc một chuỗi ký tự ñược

chương trình

(cid:2) Biến không có tên và người ta dùng ký hiệu _

13

bắt ñầu bằng một ký tự hoa

Các yếu tố cơ bản (tt)

(cid:1) Sử dụng biến trong mệnh ñề

(cid:2) Các biến là cục bộ trong mỗi mệnh ñề. Nghĩa là nếu biến X xuất hiện trong 2 mệnh ñề khác nhau thì sẽ tương ứng với 2 biến phân biệt

(cid:2) Biến xuất hiện trong 1 mệnh ñề là biến tự do

(cid:1) Ví dụ

have_a_child(X):- parent(X,Y). ñược ñọc là: …

(cid:2) Biến chỉ xuất hiện 1 lần trong mệnh ñề thì không cần

14

ñặt tên (biến vô danh) (cid:1) have_a_child(X):- parent(X,_).

Các yếu tố cơ bản (tt)

(cid:1) Quan hệ giữa các ñối tượng

(cid:2) Quan hệ giữa các ñối tượng ñược dùng dưới hình thức

(cid:2) Ví dụ: Thich(X,Y) là vị từ diễn tả câu “X thích Y”

vị từ

(cid:2) Blue(car) là vị từ diễn tả câu “Car is blue” (cid:2) Như vậy các vị từ sẽ bao gồm tên của vị từ và các ñối

trong ngôn ngữ tự nhiên

15

số. Các ñối số ñược ñặt trong ngoặc và phân cách nhau bởi dấu phẩy

Cấu trúc của một CT Turbo Prolog

(cid:1) Một chương trình Turbo Prolog thường gồm có 3 hoặc 4 ñoạn cơ bản: clauses, predicates, domains và goal

(cid:1) 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

16

Phần domains

(cid:1) Là phần ñịnh nghĩa kiểu mới dựa vào các kiểu ñã

biết

(cid:1) Các kiểu ñược ñịnh nghĩa sẽ ñược sử dụng cho

các ñối số của vị từ

(cid:1) Cú pháp ñịnh nghĩa kiểu

(cid:2) = hoặc (cid:2) = Trong ñó các kiểu mới phân cách bởi dấu «,» các kiểu ñã

17

biết phân cách bởi dấu «;»

Phần domains (tt)

(cid:1) VD

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,

18

so_luong); nha(dia_chi, dien_tich)

Phần Predicates : vị từ

(cid:1) Là phần bắt buộc phải có (cid:1) Phần predicates cần phải khai báo ñầy ñủ các vị

từ sử dụng trong phần Clauses

(cid:1) Cú pháp

(cid:1) VD

() Các kiểu ñược phân cách nhau bởi «,»

19

Predicates so_huu (ten, do_vat) so_nguyen_to(integer)

Phần Clauses : luật

(cid:1) Là phần bắt buộc phải có; dùng ñể mô tả các sự kiện và

(cid:1) Sử dụng các vị từ ñã khai báo trong phần predicates (cid:1) Cú pháp

() () ……… () 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ừ)

20

các luật

Phần Clauses (tt)

(cid:1) VD

Clauses so_nguyen_to(2):-!. so_nguyen_to(N):-N>0, so_nguyen_to(M), M0. so_huu(“Nguyen Van A”, sach(“Do Xuan Loi”, “Cau truc

21

DL”, “Khoa hoc Ky thuat”, nxb(8,1985))).

Phần goal

(cid:1) Bao gồm các mục tiêu mà ta yêu cầu Prolog xác

ñịnh và tìm kết quả (cid:1) Không bắt buộc phải có (cid:1) Nếu ñược viết sẵn trong CT thì ñó gọi là goal nội; Nếu không, khi chạy CT Prolog sẽ yêu cầu ta nhập goal vào, goal ngoại

(cid:1) VD

(cid:2) Constants (cid:2) Pi = 3.141592653

22

predicates ktnt(integer,integer) tieptuc(integer,real,real,integer) clauses ktnt(1,_):-write("Day la so nguyen to"). ktnt(2,_):-write("Day la so nguyen to"). ktnt(N,M):-N1=N-1,

N2=M/N1,N3=round(M/N1),tieptuc(N1,N2,N3,M).

tieptuc(_,N2,N3,_):-N2=N3, write("Day khong phai la so

nguyen to").

23

tieptuc(N1,N2,N3,M):-N2<>N3,ktnt(N1,M). goal clearwindow,write("Nhap N:"),readint(N),ktnt(N,N).

Các nguyên tắc của NN Prolog

(cid:1) Có 2 nguyên tắc: ñồng nhất và quay lui (cid:1) ðồng nhất

(cid:2) 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

(cid:2) Một hằng có thể ñồng nhất với một hằng (cid:2) Một biến có thể ñồng nhất với một hằng nào ñó và có

24

thể nhận luôn giá trị hằng ñó

Các nguyên tắc của NN Prolog (tt)

(cid:1) Nguyên tắc quay lui (backtract, backtracting) (cid:2) Cần chứng minh Goal : :- g1, g2, …, gj-1, gj, …, gn (cid:2) Kiểm chứng từ trái sang phải, ñến gi là sai, hệ thống cần

(cid:2) Ví dụ

phải qui lui lại gi-1

Man(x), child(Y,X)?

man(son) man(an) child(hung,an) goal: man(X), child(Y,X)?

25

Cây hợp giải

(cid:1) Xét các mệnh ñề sau ñây

sister(X,Y) :- child(X,P),child(Y,P),

woman(X), X<>Y.

26

woman(hien). child(son,lan). child(hien,lan). child(son,hung). child(hien,hung). goal: sister(hien, F)?

27

Cây hợp giải

(cid:1) Trong ví dụ trên, chúng ta tìm thấy 2 câu trả lời giống hệt nhau ñược thưc hiện bởi 2 con ñường khác nhau (cha và mẹ).

(cid:1) ðể tránh ñiều ñó, chúng ta viết lại

sister(X,Y) :- mother(M,X), father(F,X), mother(M,Y),

father(F,Y), woman(X), X<>Y.

woman(hien). child(son,lan). child(hien,lan). child(son,hung). child(hien,hung). goal: sister(hien, F)

28

29

Bộ ký tự và từ khóa

(cid:1) Prolog dùng bộ ký tự sau:

(cid:2) Các chữ cái và chữ số (A – Z, a – z, 0 – 9); (cid:2) Các toán tử (+, -, *, /, <, =, >) (cid:2) Các ký hiệu ñặc biệt

(cid:1) Một vài từ khóa

(cid:2) 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

(cid:2) Fail: Khi ta dùng goal nội, ñể nhận về tất cả các kết quả

(cid:2) ! hay còn gọi là nhát cắt, nhận chỉ một kết quả từ goal

khi chạy goal nội, ta dùng toán tử Fail

30

ngoại, ta dùng ký hiệu !

Kiểu dữ liệu chuẩn

(cid:1) Kiểu do prolog ñịnh nghĩa sẵn: char, integer, real

string và symbol

(cid:1) char: ký tự, hằng phải nằm trong dấu nháy: ‘a’,

‘#’

(cid:1) integer: -32768 ñến 32767 (cid:1) real: kiểu số thực (cid:1) string: chuỗi ký tự, hằng chuỗi ký tự nằm trong

dấu nháy kép; ”prolog”

31

Kiểu dữ liệu chuẩn: phép toán số học

Phép toán Ý nghĩa Kiểu ñối số Kiểu kết quả

+ Cộng 2 số integer, real giống kiểu ðS

- Trừ 2 số integer, real giống kiểu ðS

* Nhân 2 số integer, real giống kiểu ðS

/ Chia 2 số integer, real giống kiểu ðS

Mod Chia lấy phần dư integer integer

Div integer integer

32

Chia lấy phân nguyên

Kiểu dữ liệu chuẩn: PT quan hệ

Phép toán

Ý nghĩa

Kiểu ñối số

kết quả

Char,integer,real, string

<

Nhỏ hơn

Yes or No

Char,integer,real, string

<=

Nhỏ hơn hay bằng

Yes or No

Char,integer,real, string

=

Bằng

Yes or No

Char,integer,real, string

>

Lớn hơn

Yes or No

Char,integer,real, string

>=

Lớn hơn hay bằng

Yes or No

<> hay ><

Char,integer,real, string

Khác nhau

Yes or No

33

Kiểu dữ liệu chuẩn: các vị tự như hàm toán học Phép toán

Kiểu ñối số

Ý nghĩa

Kiểu kết quả

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

34

Kiểu do người dùng ñịnh nghĩa

(cid:1) Kiểu mẩu tin

(cid:2) Cú pháp = tên mẩu tin (danh sách

các kiểu phần tử)

Domains ten, tac_gia, nha_xb, dia_chi = string nam, thang, so_luong = integer dien_tich = real nam_xb = nxb(thang, nam)

35

Kiểu do người dùng ñịnh nghĩa (tt)

(cid:1) Kiểu danh sách

(cid:2) Cú pháp = * Domains intlist = integer* (cid:2) Một danh sách là một dãy các phần tử phân cách nhau

(cid:2) Ví dụ: []% Danh sách rỗng [1,2,3] % Danh sách gồm ba số nguyên 1, 2 và 3. [X|Y] : X là phần tử ñầu và Y là danh sách ñuôi [_|Y] : phần tử ñầu tiên của DS là biến tự do

36

bởi dấu phẩy và ñặt trong cặp dấu []

Kỹ thuật ñệ quy

(cid:1) Sử dụng ñệ quy khi một luật ñược ñịnh nghĩa nhờ

vào chính luật ñó

(cid:1) Ví dụ 1

(cid:2) Chúng ta có quan hệ child(X,Y), X là con cua Y (cid:2) Chúng ta ñịnh nghĩa quan hệ con cháu hay hậu duệ

(cid:2) Mô tả Prolog

(cid:1) descendant(X,Y):- child(X,Y). (cid:1) descendant(X,Y):- child(X,Z), descendant(Z,Y).

37

(descendant) như sau: (cid:1) X là hậu duệ của Y nếu X là con của Y (cid:1) X là hậu duệ của Y nếu là con của Z và Z là hậu duệ của Y.

Kỹ thuật ñệ quy

(cid:1) Ví dụ 2

(cid:2) Chúng ta có quan hệ giai thừa facto(N,Y), giai thừa của

(cid:2) Giai thừa của 0 bằng 1: facto(0,1) (cid:2) Giai thừa của N ñược tính từ giai thừa của N-1 (cid:2) Mô tả Prolog

Facto(0,1):- !. Facto(N, Y) :- N>0,M = N–1, facto(M, Z), Y=N*Z.

(cid:1) Trong kỹ thuật ñệ quy, trường hợp dừng ñược thể

hiện bằng một sự kiện

38

N bằng Y

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

(cid:1) Xuất ra màn hình

(cid:2) write( Arg1, Arg2, … ,Argn) in ra màn hình giá trị của các ñối

số.

(cid:2) writef(ñinh_dang, Arg1, Arg2, … ,Argn) in ra màn hình giá trị

của các ñối số theo ñịnh_dạng

(cid:2) Các ñịnh_dạng

(cid:1) “%d”: In số thập phân bình thường; ñối số phải là char hoặc integer (cid:1) “%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

(cid:1) “%e”: In số thực dưới dạng lũy thừa của 10 (cid:1) “%x”: In số Hexa; ñối số phải là char hoặc integer (cid:1) “%s”: In một chuỗi hoặc một symbol

39

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

(cid:1) Nhập vào từ bàn phím

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

40

Bài tập 1 (cid:1) Cho quan hệ cha mẹ (parent) ñược ñịnh nghĩa như

sau parent(an, hung). parent(thuy,hung). parent(linh,an). parent(le,linh). parent(anh,thuy). parent(ngoc,le). (cid:2) Hãy ñịnh nghĩa quan hệ tổ tiên (ancestor) bằng cách sử

mẹ của Y

41

dụng quan hệ parent. (cid:1) X là tổ tiên của Y nếu X là cha hay mẹ của Y (cid:1) X là tổ tiên của Y nếu X là cha hay mẹ của Z và Z là cha hay

Bài tập 2

42

Dê là ñộng vật ăn cỏ Chó sói là ñộng vật hung dữ ðộng vật hung dữ là ñộng vật ăn thịt ðộng vật ăn thịt thì ăn thịt ðộng vật ăn cỏ thì ăn cỏ ðộng vật ăn thịt thì ăn các ñộng vật ăn cỏ ðộng vật ăn thịt và ñộng vật ăn cỏ ñều uống nước Một ñộng vật tiêu thụ cái mà nó uống hoặc cái mà nó ăn (cid:1) Câu hỏi có ñộng vật hung dữ không và nó tiêu thụ cái gì? (cid:1) Xác ñịnh các luật và sự kiện