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

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

ꢀ Giꢂi thiꢃu lꢄp trình logic

ꢀ Mꢃnh ñꢅ

ꢀ Ngôn ngꢆ Turbo ProLog

2

Giꢃ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

3

Giꢃ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

4

Giꢃi thiꢄu lꢁp trình logic

ꢀ Mꢖ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

5

Giꢃ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)

6

Giꢃi thiꢄu lꢁp trình logic

ꢀ Tam ñoꢑn luꢄn

ꢁ Socrates là ngưꢜi

nguoi(socrates).

chet(X):- nguoi(X).

ꢁ Mꢇi ngưꢜi ñꢅu phꢀi chꢒt

⇒ Socrates phꢀi chꢒt

robber(jerry).

ꢁ Jerry là mꢖt kꢝ cưꢂp

ꢁ Tom là con cꢈa John

ꢁ John thì giàu có

childof(tom,john).

rich(john).

rich(X):- childof(X,Y), rich(Y)

Rich(X):- robber(X)

ꢁ X là kꢝ giàu có nꢒu như X có cha giàu có hoꢏc X là mꢖt

kꢝ cưꢂp

7

Mꢄ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; A1…An là các

ñꢊi; nguyentu(atom, symbol)

8

Mꢄ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)

9

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

10

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).

vua(xeda).

hanhphuc(xeda)?

hanhphuc(socrates)?

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

11

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

ꢀ 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 _

13

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,_).

14

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

15

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

16

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

ꢁ <DS kiꢎu mꢂi> = <kiꢎu ñã biꢒt> hoꢏc

ꢁ <DS kiꢎu mꢂi> = <DS kiꢎu ñã biꢒt>

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 «;»

17

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)

18

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

<Tên vꢙ tꢘ> (<danh sách các kiꢎu>)

Các kiꢎu ñưꢋc phân cách nhau bꢍi «,»

ꢀ VD

Predicates

so_huu (ten, do_vat)

so_nguyen_to(integer)

19

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

<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>

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

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