Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 8: Ngôn ngữ lập trình logic - Nguyễn Văn Hòa

Tóm tắt Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 8: Ngôn ngữ lập trình logic - Nguyễn Văn Hòa: ...chương trỡnh  Tờn biến là một ký tự hoa hoặc một chuỗi ký tự ủược bắt ủầu bằng một ký tự hoa  Biến khụng cú tờn và người ta dựng ký hiệu _ 14 Cỏc yếu tố cơ bản (tt)  Sử dụng biến trong mệnh ủề  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 nha...ế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  VD  Constants  Pi = 3.141592653 23 predicates ktnt(integer,integer) tieptuc(integer,real,real,integer) clauses ktnt(1,_):-write("Day la so nguyen to"). ktnt(2,_):...ộp toỏn số học integerintegerChia lấy phõn nguyờn Div integerintegerChia lấy phần dưMod giống kiểu ðSinteger, realChia 2 số/ giống kiểu ðSinteger, realNhõn 2 số* giống kiểu ðSinteger, realTrừ 2 số- giống kiểu ðSinteger, realCộng 2 số+ Kiểu kết quảKiểu ủối sốí nghĩaPhộp toỏn 33 Kiểu dữ li...

pdf42 trang | Chia sẻ: havih72 | Lượt xem: 319 | Lượt tải: 0download
Nội dung tài liệu Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 8: Ngôn ngữ lập trình logic - Nguyễn Văn Hòa, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
1Chươ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
2Nội dung
 Giới thiệu lập trình logic
 Mệnh đề
 Ngơn ngữ Turbo ProLog
3Giới thiệu lập trình logic
 Các họ ngơn ngữ lập trình bậc cao
 Lập trình mệnh lệnh (imparative)
 Thủ tục (procedural)
 Hướng đối tượng (object)
 Lập trình khai báo (declarative)
 Hàm (functional)
 Logic
4Giới thiệu lập trình logic
 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?
 LT logic là LT khai báo (declarative) 
 Dùng ngơn ngữ mơ tả để đặc tả các vấn đề
 Nhấn mạnh kết quả mong đợi hơn là cách thức nhận 
được kết quả
 Ứng dụng nhiều trong xử lý ngơn ngữ tự nhiên và 
Trí tuệ nhân tạo
5Một chương trình logic (Prolog) là tập hợp các 
mệnh đề
Mỗi một mệnh đề được xây từ nhiều vị từ
 Vị từ là phát biểu về một đối tượng cĩ thể là đúng 
hoặc sai
→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
Giới thiệu lập trình logic
6Giới thiệu lập trình logic
 Hạng (term) được xem là đối tượng dữ liệu
 Hạng gồm:
 Hạng sơ cấp (elementary term) như hằng, biến
 Hạng phức hợp (compound term) như một hàm tử
(functor) cĩ chứa các đối, cĩ dạng:
 Tên_hàm_tử(đối1, đối2, )
 VD student(an)
7Giới thiệu lập trình logic
 Tam đoạn luận
 Socrates là người nguoi(socrates).
 Mọi người đều phải chết chet(X):- nguoi(X).
⇒ Socrates phải chết
 Jerry là một kẻ cướp
 Tom là con của John
 John thì giàu cĩ
 X là kẻ giàu cĩ nếu như X cĩ cha giàu cĩ hoặc X là một 
kẻ cướp
robber(jerry).
childof(tom,john).
rich(john).
rich(X):- childof(X,Y), rich(Y)
Rich(X):- robber(X)
8Mệnh đề
 Một mệnh đề cĩ thể cĩ một trong hai hình thức 
sau:
 Sự kiện (fact): khẳng định 1 thực thể cĩ 1 hoặc vài tính 
chất; woman(thuy), man(an)
 Luật: định nghĩa quan hệ đựa vào các quan hệ; 
wife(A,B):- husband(B,A)
 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.
 Qui ước sự kiện:
 P(A): A cĩ tính chất P; student(an)
 P(A,B): A là P đối với B; husband(an,thuy)
 P(A1,A2,, An): P là tên của tính chất; A1An là các 
đối; nguyentu(atom, symbol) 
9Mệnh đề
 Luật:
 Từ nếu được viết «:-» trong Prolog
 Luật gồm cĩ 2 phần
 Phần bên trái chỉ kết luận, được gọi là đầu (head) của luật
 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.
 Sự khác nhau giữa sự kiện và luật
 Sự kiện là khẳng định luơn luơn đúng
 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 robber(jerry).
childof(tom,john).
rich(john).
rich(X):- childof(X,Y), rich(Y)
Rich(X):- robber(X)
10
Ngơn ngữ Turbo Prolog
 Prolog: Programming in logic
 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
 Prolog là một ngơn ngữ cấp cao
 Cĩ đặc điểm gần với ngơn ngữ tự nhiên
 Turbo Prolog được phát triển bởi Borland
11
Ngơn ngữ Turbo Prolog (tt)
 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ả
 Ví dụ
nguoi(socrates).
nguoi(xeda). hanhphuc(xeda)?
vua(xeda). hanhphuc(socrates)?
xanhphuc(X):- vua(X),nguoi(X). hanhphuc(Y)?
12
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).
13
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
 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ự được 
bắt đầu bằng một ký tự hoa
 Biến khơng cĩ tên và người ta dùng ký hiệu _
14
Các yếu tố cơ bản (tt)
 Sử dụng biến trong mệnh đề
 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
 Biến xuất hiện trong 1 mệnh đề là biến tự do
 Ví dụ
have_a_child(X):- parent(X,Y).
được đọc là: 
 Biến chỉ xuất hiện 1 lần trong mệnh đề thì khơng cần 
đặt tên (biến vơ danh)
 have_a_child(X):- parent(X,_).
15
Các yếu tố cơ bản (tt)
 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ác đối số được đặt trong ngoặc và phân cách nhau 
bởi dấu phẩy
16
Cấu trúc của một CT Turbo Prolog
 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
 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
17
Phần domains
 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 sẽ được sử dụng cho 
các đối số của vị từ
 Cú pháp định nghĩa kiểu
 = hoặc 
 = 
Trong đĩ các kiểu mới phân cách bởi dấu «,» các kiểu đã 
biết phân cách bởi dấu «;»
18
Phần domains (tt)
 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, 
so_luong); nha(dia_chi, dien_tich)
19
Phần Predicates : vị từ
 Là phần bắt buộc phải cĩ
 Phần predicates cần phải khai báo đầy đủ các vị 
từ sử dụng trong phần Clauses
 Cú pháp
 () 
Các kiểu được phân cách nhau bởi «,»
 VD
Predicates
so_huu (ten, do_vat)
so_nguyen_to(integer)
20
Phần Clauses : luật
 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
() 
() 
() 
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ừ)
21
Phần Clauses (tt)
 VD
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))).
22
Phần goal
 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ả
 Khơng bắt buộc phải cĩ
 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
 VD
 Constants
 Pi = 3.141592653
23
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").
tieptuc(N1,N2,N3,M):-N2N3,ktnt(N1,M).
goal
clearwindow,write("Nhap N:"),readint(N),ktnt(N,N).
24
Các nguyên tắc của NN Prolog
 Cĩ 2 nguyên tắc: đồng nhất và 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 đĩ
25
Các nguyên tắc của NN Prolog (tt)
 Nguyên tắc quay lui (backtract, backtracting)
 Cần chứng minh Goal : :- g1, g2, , gj-1, gj, , gn
 Kiểm chứng từ trái sang phải, đến gi là sai, hệ thống cần 
phải qui lui lại gi-1
 Ví dụ
man(son)
man(an)
child(hung,an)
goal: man(X), child(Y,X)?
Man(x), child(Y,X)?
26
Cây hợp giải
 Xét các mệnh đề sau đây
sister(X,Y) :- child(X,P),child(Y,P), 
woman(X), XY.
woman(hien).
child(son,lan).
child(hien,lan).
child(son,hung).
child(hien,hung).
goal: sister(hien, F)?
27
28
Cây hợp giải
 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ẹ).
 ðể 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), XY.
woman(hien).
child(son,lan).
child(hien,lan).
child(son,hung).
child(hien,hung).
goal: sister(hien, F)
29
30
Bộ ký tự và từ khĩa
 Prolog dùng bộ ký tự sau: 
 Các chữ cái và chữ số (A – Z, a – z, 0 – 9); 
 Các tốn tử (+, -, *, /, ) 
 Các ký hiệu đặc biệt
 Một vài từ khĩa
 Trace: Khi cĩ từ khố này ở đầu chương trình, thì 
chương trình được thực hiện từng bước để theo dõi
 Fail: Khi ta dùng goal nội, để nhận về tất cả các kết quả 
khi chạy goal nội, ta dùng tốn tử Fail
 ! hay cịn gọi là nhát cắt, nhận chỉ một kết quả từ goal 
ngoại, ta dùng ký hiệu !
31
Kiểu dữ liệu chuẩn
 Kiểu do prolog định nghĩa sẵn: char, integer, real 
string và symbol
 char: ký tự, hằng phải nằm trong dấu nháy: ‘a’, 
‘#’
 integer: -32768 đến 32767
 real: kiểu số thực
 string: chuỗi ký tự, hằng chuỗi ký tự nằm trong 
dấu nháy kép; ”prolog”
32
Kiểu dữ liệu chuẩn: phép tốn số học
integerintegerChia lấy phân 
nguyên
Div
integerintegerChia lấy phần dưMod
giống kiểu ðSinteger, realChia 2 số/
giống kiểu ðSinteger, realNhân 2 số*
giống kiểu ðSinteger, realTrừ 2 số-
giống kiểu ðSinteger, realCộng 2 số+
Kiểu kết quảKiểu đối sốÝ nghĩaPhép tốn
33
Kiểu dữ liệu chuẩn: PT quan hệ
Yes or NoChar,integer,real, stringKhác nhau hay ><
Yes or NoChar,integer,real, stringLớn hơn hay bằng>=
Yes or NoChar,integer,real, stringLớn hơn>
Yes or NoChar,integer,real, stringBằng=
Yes or NoChar,integer,real, stringNhỏ hơn hay bằng <=
Yes or NoChar,integer,real, stringNhỏ hơn<
kết quảKiểu đối sốÝ nghĩaPhép tốn
34
Kiểu dữ liệu chuẩn: các vị tự như 
hàm tốn học
RealRealTính Logarit cơ số 10 của XLog(X)
RealRealTính logarit cơ số e của XLn(X)
RealRealTính eXExp(X)
RealRealTính arctang của XArctan(X)
RealRealTính tang của XTan(X)
RealRealTính sin của XSin(X)
Kiểu kết quảKiểu đối sốÝ nghĩaPhép tốn
35
Kiểu do người dùng định nghĩa
 Kiểu mẩu tin
 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)
36
Kiểu do người dùng định nghĩa (tt)
 Kiểu danh sách
 Cú pháp = *
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 []
 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
37
Kỹ thuật đệ quy
 Sử dụng đệ quy khi một luật được định nghĩa nhờ 
vào chính luật đĩ
 Ví dụ 1
 Chúng ta cĩ quan hệ child(X,Y), X là con cua Y
 Chúng ta định nghĩa quan hệ con cháu hay hậu duệ 
(descendant) như sau:
 X là hậu duệ của Y nếu X là con của Y
 X là hậu duệ của Y nếu là con của Z và Z là hậu duệ của Y.
 Mơ tả Prolog
 descendant(X,Y):- child(X,Y).
 descendant(X,Y):- child(X,Z), descendant(Z,Y).
38
Kỹ thuật đệ quy
 Ví dụ 2
 Chúng ta cĩ quan hệ giai thừa facto(N,Y), giai thừa của 
N bằng Y
 Giai thừa của 0 bằng 1: facto(0,1)
 Giai thừa của N được tính từ giai thừa của N-1
 Mơ tả Prolog
Facto(0,1):- !.
Facto(N, Y) :- N>0,M = N–1, facto(M, Z), Y=N*Z.
 Trong kỹ thuật đệ quy, trường hợp dừng được thể 
hiện bằng một sự kiện
39
Các hàm xuất nhập chuẩn
 Xuất ra màn hình
 write( Arg1, Arg2,  ,Argn) in ra màn hình giá trị của các đối 
số.
 writef(đinh_dang, Arg1, Arg2,  ,Argn) in ra màn hình giá trị 
của các đối số theo định_dạng
 Các định_dạng
 “%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
40
Các hàm xuất nhập chuẩn (tt)
 Nhập vào từ bàn phím
 Readln(X): Nhập một chuỗi ký tự vào biến X
 ReadInt(X): Nhập một số nguyên vào biến X
 ReadReal(X): Nhập một số thực vào biến X
 ReadChar(X): Nhập vào một ký tự vào biến X
41
Bài tập 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).
 Hãy định nghĩa quan hệ tổ tiên (ancestor) bằng cách sử 
dụng quan hệ parent.
 X là tổ tiên của Y nếu X là cha hay mẹ của Y
 X là tổ tiên của Y nếu X là cha hay mẹ của Z và Z là cha hay 
mẹ của Y
42
Bài tập 2
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
 Câu hỏi cĩ động vật hung dữ khơng và nĩ tiêu thụ cái gì?
 Xác định các luật và sự kiện

File đính kèm:

  • pdfbai_giang_nguyen_ly_ngon_ngu_lap_trinh_chuong_8_ngon_ngu_lap.pdf