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...
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:
- bai_giang_nguyen_ly_ngon_ngu_lap_trinh_chuong_8_ngon_ngu_lap.pdf