Ngôn ngữ DLPᴬ và một số ứng dụng

Nội dung text: Ngôn ngữ DLPᴬ và một số ứng dụng

1. 92 Journal of Science – Phu Yen University, No.26 (2021), 92-99 NGÔN NGỮ DLPA VÀ MỘT SỐ ỨNG DỤNG Võ Thị Như Lý* Trường Cao đẳng Công thương miền Trung Ngày nhận bài: 03/4/2020; Ngày nhận đăng: 08/01/2021 Tóm tắt Trong bài báo này, chúng tôi xem xét cú pháp và ngữ nghĩa của ngôn ngữ lập trình logic DLPA cùng các tính chất ngữ nghĩa của ngôn ngữ DLPA, được gọi đơn giản là chương trình logic dạng tuyển kết tập. Chúng tôi cũng trình bày một số ứng dụng điển hình sử dụng ngôn ngữ DLPA chạy trên hệ thống lập trình DLV. Từ khóa: Lập trình logic, ngôn ngữ DLPA, hệ thống DLV 1. Giới thiệu tố thỏa mãn một vài điều kiện, được diễn Trong suốt những thập kỷ qua, một đạt một cách dễ dàng và tự nhiên bằng mô hình lập trình mới là “Lập trình logic” ngôn ngữ DLPA. Ngôn ngữ DLPA được áp đã ra đời. Lập trình logic (LP) chủ yếu dựa dụng để giải quyết được nhiều bài toán thực trên ý tưởng lập trình khai báo, ở đó các tế phức tạp, chẳng hạn bài toán sắp xếp chỗ chương trình không được tạo ra từ các câu ngồi, các bài toán tối ưu hóa của lý thuyết lệnh cũng như từ các hàm mà được tạo ra đồ thị và nhiều dạng suy luận phỏng đoán. chủ yếu dựa trên tập các vị từ. Lĩnh vực 2. Ngôn ngữ DLPA nghiên cứu LP được nhiều nhà khoa học 2.1. Cú pháp của ngôn ngữ DLPA quan tâm và đã được áp dụng vào việc biểu 2.1.1. Tập DLPA (Armi et.,2003). diễn và xử lý tri thức phức tạp trong lĩnh Một tập DLPA là một tập ký hiệu hoặc là vực trí tuệ nhân tạo và các lĩnh vực nổi lên một tập nền. Trong đó: khác như quản trị tri thức và tích hợp thông - Tập ký hiệu có dạng {Vars : Conj}, tin. Hiện nay LP được mở rộng theo nhiều trong đó Vars là một danh sách các biến và hướng khác nhau, trong đó ngôn ngữ DLPA Conj là hội của các literal thông thường (có – một sự mở rộng của LP, cho phép các thể chứa các literal âm). hàm kết tập xuất hiện trong các quy tắc của - Tập nền là tập các cặp có dạng chương trình logic. t: Conj , trong đó t là danh sách các Hàm kết tập có ý nghĩa rất đáng kể, hằng và Conj là hội của các literal thông nó cho phép mô hình hóa một cách tự nhiên thường nền. và ngắn gọn về nhiều vấn đề. Nó làm tăng 2.1.2. Hàm kết tập/nguyên tố kết tập khả năng diễn đạt các thuộc tính, thường (Armi et., 2003). nảy sinh trong các ứng dụng thế giới thực, a) Một hàm kết tập có dạng f(S), trong được mã hóa theo cách đơn giản và tự đó S là một tập DLPA và f là một trong số nhiên. Trong số đó, có những thuộc tính các hàm #count, #min, #max, #sum, yêu cầu áp dụng các toán tử toán học (như #times. sum, times, count ) trong một tập các yếu b) Một nguyên tố kết tập có dạng ___ , trong đó f(S) là một * Email: lyvo2019@gmail.com Lgpp12 f S Rg
2. Tạp chí Khoa học – Trường Đại học Phú Yên, Số 26 (2021), 92-99 93 mô hình nào. hàm kết tập, pp12,,,,,  , Lg Xét chương trình có các ràng buộc yếu và Rg là các hạng thức (biến hoặc hằng) và như sau: gọi là chặn. “ Lg p ” hoặc “p Rg ” có 1 2 a  b. c :− b. :~ a. :~ b. :~ c. thể không có. Ở đây, mức độ đánh giá và độ ưu tiên 2.1.3. Nguyên tố, literal (Armi et.,2003). được bỏ qua, giá trị được gán ngầm định là a) Một nguyên tố là một nguyên tố thông 1. Nếu ta gọi trong DLV, ta thu được kết thường hoặc một nguyên tố kết tập. quả sau: b) Một literal L là một nguyên tố A hoặc Best Model: {a} phủ định của nguyên tố A. Nếu A là Chú ý rằng các tập trả lời của chương nguyên tố kết tập thì L là literal kết tập. trình {a  b, c:−b } là {a} và {b, c}. Sự 2.1.4. Quy tắc DLPA (Faber et., 2011). xuất hiện của các ràng buộc yếu đã loại bỏ Một quy tắc DLPA r là một cấu trúc có dạng: {b, c} vì nó mâu thuẫn với các ràng buộc a1  a2  . . . an :−b1 , b2, . . . , bk, not bk+1 yếu (trong khi đó {a} chỉ mâu thuẫn một , . . . , bm ràng buộc yếu). trong đó a1 , a2, . . . , an là các nguyên tố 2.1.6. Chương trình DLPA (Faber et., 2008). thông thường, b1 , b2, . . . , bm là những Một chương trình DLPA là một tập các quy nguyên tố, n 0 , m k 0 , m + n tắc DLPA và các ràng buộc yếu (nếu có). 1, tuyển a1  a2  . . . an là đầu của r và Để đơn giản và không mất tính tổng hội b1, b2, . . . , bk, not bk+1 , . . . , bm là thân quát, ta giả sử rằng thân của mỗi quy tắc của r. Ký hiệu H(r) = {a1, , an} và B(r) = gồm nhiều nhất là một nguyên tố kết tập. {b1, b2, , bk, not bk+1, , not bm}. Một quy Biến toàn cục của r là biến xuất hiện trong tắc với phần đầu rỗng (nghĩa là n = 0) thì nguyên tố thông thường của r, biến cục bộ được gọi là ràng buộc toàn vẹn (hay ràng là biến chỉ xuất hiện trong hàm kết tập của buộc mạnh). Một quy tắc với thân rỗng r. (nghĩa là k = m = 0) được gọi là một sự kiện 2.2. Ngữ nghĩa của ngôn ngữ DLPA và ta thường bỏ qua ký hiệu “:−”. 2.2.1. Các khái niệm 2.1.5. Ràng buộc yếu (Faber et., 2008). a) Vũ trụ và cơ sở của chương trình Một ràng buộc yếu wc cú pháp có dạng: DLPA P A :~ L1  Lk [w : l] Cho P là chương trình DLP , vũ trụ của P, trong đó k 1 và các Li (i = 1, , n) là các ký hiệu Up chỉ tập các hằng xuất hiện trong literal, còn weight(wc) = w và layer(wc) = P, cơ sở của P, ký hiệu BP là tập các nguyên l là các hằng hoặc biến nguyên dương và w, tố thông thường xây dựng từ các vị từ của l có thể được bỏ qua và mặc định là bằng 1. P với hằng trong UP. Ràng buộc yếu cho phép ta biểu diễn b) Phép thế và hiện hành của chương một số các bài toán tối ưu theo một cách tự trình DLPA P (James, P. D., & Faber, W. nhiên và đơn giản. Trong khi các ràng buộc (2011)). chuẩn (ràng buộc toàn vẹn, ràng buộc Phép thế là một ánh xạ từ tập các mạnh) luôn phải được thỏa mãn, ràng buộc biến đến tập UP các hằng trong P. Phép thế yếu biểu diễn một mức độ mong muốn nào từ tập các biến toàn cục của quy tắc r đến đó, tức là chúng có thể được thỏa mãn khi tập UP là phép thế toàn cục đối với quy tắc có thể nhưng chúng không loại bỏ bất kỳ r. Phép thế từ tập các biến cục bộ của tập
3. 94 Journal of Science – Phu Yen University, No.26 (2021), 92-99 ký hiệu S đến tập UP là phép thế cục bộ đối [t1 | t1, , tn  SI ] với S. Phép định giá I(f(S)) của hàm kết tập Cho tập ký hiệu S không chứa biến f(S) theo I là kết quả của việc áp dụng hàm toàn cục, S = {Vars: Conj}, hiện hành của f trên I(S). Nếu đa tập I(S) không nằm trong S, ký hiệu inst(S), là tập nền: miền của f thì I(f(S)) =  . inst(S) = {훾(Vars) : 훾(Conj)  | 훾 là phép Một nguyên tố kết tập A = Lgp f(S) thế cục bộ đối với S}. 1 Một hiện hành nền của quy tắc r nhận p 2 Rg là đúng theo thể hiện I nếu: được qua 2 bước: (i) I(f(S)) , và (1) Phép thế toàn cục  đối với r được áp (ii) Quan hệ Lgp 1 I( f ( S )) và dụng đầu tiên trên r. I( f ( S )) p Rg đều thỏa mãn; (2) Mỗi tập ký hiệu S trong (r) được thay 2 còn ngược lại thì A sai. thế bởi hiện hành inst(S). Một literal kết tập hiện hành not A= not Hiện hành của chương trình DLPA P, f(S) k đúng theo I nếu: ký hiệu Ground(P), là tập tất cả các hiện p 2 hành có thể có của các quy tắc của P. (i) I(f(S)) , và c) Thể hiện và phép định giá (Faber (ii) I(f(S)) k đều thoả mãn; et.,2004). còn ngược lại thì A sai. A Một thể hiện của chương trình DLP Một qui tắc r đúng theo I (ký hiệu là: I ⊨ P là một tập các nguyên tố thông thường ) nếu một vài nguyên tố trong phần đầu nền I  BP. của quy tắc đúng theo I (∃ℎ ∈ ( ): ⊨ Việc xác định giá trị chân lý của A ℎ) và tất cả literal trong thân quy tắc đúng theo thể hiện I, trong đó A là literal thông theo I (∀ ∈ ( ): ⊨ ). thường nền hoặc hội các literal thông (Mô hình của chương trình DLPA) Một mô thường nền, ký hiệu là I(A) được định nghĩa hình của chương trình DLPA P là một thể theo cách thông thường. hiện M của P sao cho mọi quy tắc r Bên cạnh việc gán giá trị chân lý cho Ground(P) là đúng theo M. Mô hình M của các literal thông thường nền thì một thể P là mô hình cực tiểu nếu không tồn tại mô hiện còn cung cấp ngữ nghĩa cho các tập hình N của P sao cho N là tập con thực sự nền, các hàm kết tập và các literal kết tập. của M. Ngữ nghĩa của một tập nền, một hàm kết 2.2.2. Tập trả lời tập, một nguyên tố kết tập theo một thể a) Phép biến đổi Gelfond Lifschitz (Faber hiện, tương ứng là một đa tập, một giá trị et.,2008). và một giá trị chân lý. Phép biến đổi Gelfond Lifschitz của chương Phép định giá I(S) của tập S theo thể A trình DLP nền P theo tập X  BP là một hiện I là đa tập của hằng đầu tiên của các chương trình DLPA nền dương PX thu được phần tử trong S mà hội của chúng là đúng từ P bằng cách: theo I. Chính xác hơn, đặt SI = { - Xoá tất cả quy tắc r P mà literal t1, ,tn  t1, ,tn :Conj S Conj là phủ định trong B(r) là sai theo X hoặc đúng theo I}. Phép định giá I(S) của S theo literal kết tập là sai theo X, thể hiện I là đa tập - Xoá các literal kết tập, literal phủ định từ những quy tắc còn lại.
4. Tạp chí Khoa học – Trường Đại học Phú Yên, Số 26 (2021), 92-99 95 b) Tập trả lời của chương trình DLPA P là tối thiểu đã đưa ra tập X  BP sao cho X là tập trả lời của Giả sử rằng các nhân viên được cung Ground(P)X. cấp một số sự kiện có dạng emp(EmpId, Cho chương trình DLPA P sau đây: Sex, Skill, Salary); Qui mô của đội, số d(1):− lượng tối thiểu các kỹ năng khác nhau, a  b:− c ngân sách, mức lương tối đa và số lượng tối b:− not a , not c , #count{Y: d(Y)}>0 thiểu nhân viên nữ lần lượt được qui định a  c: − not b, #sum{Y: d(Y)}>1 bởi các nguyên tố nEmp(N), nSkill(N), Xét thể hiện I = {b, d(1)}, lúc đó PI như budget(B), maxSal(M) và women(W). Từ sau: những thông tin này, thực hiện mã hoá các yêu cầu bằng ngôn ngữ DLPA ta nhận được d(1):− chương trình sau: a  b:− c (r )in(I)  out(I) :- emp(I, Sx, Sk, Sa). b:− 1 (r ):- nEmp(N),not #count{I : in(I)} = N. Ta nhận thấy I là tập trả lời của PI, nên nó 2 (r ):- nSkill(M), not #count{Sk : emp(I, là tập trả lời của P. 3 Sx, Sk, Sa), in(I)} M. Xem thể hiện J = {a, d(1)}, lúc đó PJ như sau: (r4) :- budget(B), not #sum{Sa, I : emp(I, d(1):− Sx, Sk, Sa), in(I)} B. a  b:−c (r5):- maxSal(M), not #max{Sa : emp(I, Ta nhận thấy J là tập trả lời của PJ, vì vậy Sx, Sk, Sa), in(I)} M. nó cũng là tập trả lời của P . (r6):- women(W), not #count{I : emp(I, f, Xét tập K = {c, d(1)},ta có PK = PJ nhưng Sk, Sa), in(I)} W. K không phải là tập trả lời của PK , vì đối Quy tắc dạng tuyển (r1) “dự đoán” với quy tắc r: a  b:−c, thì B(r) K một nhân viên có trong đội hay không, nhưng H(r)  K  không thoả. Thực vậy, trong khi 5 ràng buộc (r2-r6) tương ứng có thể chỉ ra rằng chỉ có I và J là các tập trả với 5 yêu cầu P1 - P5 . Nhờ vào các hàm trả lời của P. kết tập nên việc chuyển đổi các yêu cầu 3. Một số ứng dụng dễ dàng hơn. Đây là một ví dụ làm nổi 3.1. Bài toán xây dựng đội làm việc cho bật tính hữu ích của biểu diễn tập hợp và một dự án đa tập. Việc mã hoá của yêu cầu P2 đòi Một đội làm việc cho một dự án được xây hỏi một tập bởi vì ta muốn đếm số kỹ dựng từ tập các nhân viên theo các yêu cầu năng khác nhau; hai nhân viên trong đội sau đây: có kỹ năng giống nhau sẽ được đếm một P1. Đội phải có một số lượng nhân viên lần. Ngược lại, P3 yêu cầu tính tổng các cụ thể. phần tử của đa tập; nếu 2 nhân viên có P2. Trong đội phải có ít nhất các kỹ năng lương giống nhau thì cả hai giá trị lương khác nhau theo yêu cầu phải được cộng tổng hợp cho P3. Điều P3. Tổng lương của các nhân viên làm này đạt được bằng cách thêm biến I (định việc trong đội không vượt quá ngân sách danh của mỗi nhân viên) trong Vars. Việc đề ra. định giá của {Sa, I : emp((I, Sx, Sk, Sa), P . Lương của mỗi nhân viên nằm trong 4 in(I)} sinh ra tập S = { Sa,I : Sa là giới hạn cho phép. lương của nhân viên I trong đội}. Hàm P5. Số lao động nữ trong đội phải đạt mức
5. 96 Journal of Science – Phu Yen University, No.26 (2021), 92-99 tổng #sum được áp dụng trên đa tập của nEmp(3). nSkill(2). budget(40). thành phần Sa đầu tiên của bộ Sa,I maxSal(40). women(1). trong S. Thực thi chương trình này bằng hệ Giả sử các sự kiện đầu vào là: thống DLV ta nhận được kết quả như emp(a, s,2,10). emp(b,s,1,5). hình sau: emp(c,s,3,3). emp(d,f,4,40). emp(e,f,5,10). Hình 1: Kết quả thực thi chương trình bằng hệ thống DLV Chương trình này có 3 tập trả lời sau: có trọng số. Tìm cây khung của G và có M1 = {emp(a,s,2,10), emp(b,s,1,5), trọng số nhỏ nhất. emp(c,s,3,3), emp(d,f,4,40), emp(e,f,5,10), a) Chương trình viết bằng ngôn ngữ DLPA nEmp(3), nSkill(2), budget(40), và không sử dụng hàm kết tập: maxSal(40), women(1), out(a), in(b), in(c), root(a). out(d), in(e)} node(a). node(b). node(c). node(d). node(e). M2 = {emp(a,s,2,10), emp(b,s,1,5), edge(a,b,4). edge(a,c,3). edge(c,b,2). edge(c,d,3). emp(c,s,3,3), emp(d,f,4,40), emp(e,f,5,10), edge(b,e,4). edge(d,e,5). nEmp(3), nSkill(2), budget(40), in_tree(X,Y,C) v out_tree(X,Y) :- maxSal(40), women(1), in(a), out(b), in(c), edge(X,Y,C), reached(X). out(d), in(e)} :- root(X), in_tree(_,X,C). M3 = {emp(a,s,2,10), emp(b,s,1,5), :- in_tree(X,Y,C), in_tree(Z,Y,C), X != Z. emp(c,s,3,3), emp(d,f,4,40), emp(e,f,5,10), reached(X):- root(X). nEmp(3), nSkill(2), budget(40), reached(Y):- reached(X), in_tree(X,Y,C). maxSal(40), women(1), in(a), in(b), out(c), :- node(X), not reached(X). out(d), in(e)} :~ in_tree(X,Y,C). [C:1] 3.2. Bài toán tìm cây khung nhỏ nhất đồ thị Thực thi chương trình này bằng hệ thống Cho G = là một đồ thị có hướng và DLV ta nhận được kết quả như ở hình sau:
6. Tạp chí Khoa học – Trường Đại học Phú Yên, Số 26 (2021), 92-99 97 Hình 2. Kết quả thực thi chương trình của Bài toán đồ thị Tập trả lời tìm được là: edge(a,b,4). edge(a,c,3). edge(c,b,2). M1 = {root(a), node(a), node(b), node(c), edge(c,d,3). edge(b,e,4). edge(d,e,5). node(d), node(e), edge(a,b,4), in_tree(X,Y,C) v out_tree(X,Y) :- edge(a,c,3), edge(b,e,4), edge(c,b,2), edge(X,Y,C). edge(c,d,3), edge(d,e,5), reached(a), %nút gốc của cây không có cung đến out_tree(a,b), in_tree(a,c,3), reached(b), :- root(R), not #count{X : in_tree(X,R,C)} reached(c), in_tree(b,e,4), in_tree(c,b,2), = 0. in_tree(c,d,3), reached(e), reached(d), %mỗi nút trong cây chỉ có một cung đến out_tree(d,e)} :- edge(_,Y,_), not #count{X : Cost ([Weight:Level]): in_tree(X,Y,_)} = 1. b) Chương trình viết bằng ngôn ngữ DLPA :~ in_tree(X,Y,C). [C:1] và có sử dụng hàm kết tập: Thực thi chương trình này bằng hệ thống root(a). DLV ta nhận được kết quả như ở hình sau: node(a). node(b). node(c). node(d). node(e). Hình 3. Kết quả thực thi chương trình của Bài toán đồ thị (dùng hàm kết tập) Tập trả lời tìm được là: in_tree(c,d,3), reached€, reached(d), M1 = {root(a), node(a), node(b), node(c), out_tree(d,e)} node(d), node€, edge(a,b,4), Cost ([Weight:Level]): edge(a,c,3), edge(b,e,4), edge(c,b,2), Ta nhận thấy kết quả chương trình khi dùng edge(c,d,3), edge(d,e,5), reached(a), hàm kết tập và khi không dùng hàm kết tập out_tree(a,b), in_tree(a,c,3), reached(b), đều cho ra tập trả lời như nhau. Tuy nhiên, reached(c), in_tree(b,e,4), in_tree(c,b,2), khi dùng hàm kết tập thì số lượng quy tắc
7. 98 Journal of Science – Phu Yen University, No.26 (2021), 92-99 phải dùng sẽ được rút ngắn, mã hóa một khi thêm vào hàm kết tập thì không làm cách trực tiếp, tự nhiên và sử dụng được tăng độ phức tạp của chương trình logic các quan hệ kế thừa nên sẽ biểu diễn tri dạng tuyển (Faber et.,2004). thức tốt hơn. Và các nghiên cứu chỉ ra rằng ∅ {Ms} {M} {As} {Ns} {Ms,As, Ns} {A} {N} {M,A,N} 푃 푃 푃 푃 푃 푃 Không co-NP co-NP co-NP ∏ ∏ ∏ ∏ ∏ ∏ có phủ 2 2 2 2 2 2 định (not) 푃 푃 푃 푃 푃 푃 푃 푃 푃 Phủ ∏ ∏ ∏ ∏ ∏ ∏ ∏ ∏ ∏ định 2 2 2 2 2 2 2 2 2 (not) Bảng 1. Sự phức tạp của chương trình logic dạng tuyển với hàm kết tập Trong đó: chương trình DLPA thông qua một số bài Ms: Kết tập đơn điệu phân tầng toán thực tế và cài đặt các bài toán này trên M: Kết tập đơn điệu hoàn toàn (có thể có hệ thống DLV. đệ qui) - Việc mở rộng chương trình logic As: Kết tập không đơn điệu phân tầng dạng tuyển với các hàm kết tập góp phần A: Kết tập kháng đơn điệu hoàn toàn tạo thêm điểm mạnh trong việc mô hình Ns: Kết tập không đơn điệu phân tầng hóa một cách tự nhiên các tri thức không N: Kết tập không đơn điệu hoàn toàn đầy đủ và làm nổi bật những đặc tính của Tất cả các dạng kết tập đều có kết quả là các ngôn ngữ biểu diễn tri thức mới. Ngoài 푃 ∏2 cũng chính bằng chương trình logic ra, còn góp phần vào nghiên cứu phương dạng tuyển chuẩn. pháp định giá truy vấn đối với chương trình 4. Kết luận DLPA - Bài báo đã biểu diễn tri thức bằng TÀI LIỆU THAM KHẢO Armi, T. D., Faber, W., Ielpa, G., Leone, N., & Pfeifer, G. (2003). Aggregate Functions in DLV. Messina, Italy: ASP'03, 274 – 288. Armi, T. D., Faber, W., Ielpa, G., Leone, N., & Pfeifer, G. (2003). Aggregate Functions in Disjunctive Logic Programming: Semantics, Complexity, and Implementation in DLV. Acapulco, Mexico: IJCAI 2003, 847-852. Faber, W., Leone, N., & Pfeifer, G. (2004). Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity. J.J. Alferes, J. Leite (Eds.), Proceedings of the 9th European Conference on Artificial Intelligence (JELIA 2004), Lecture Notes in AI (LNAI), vol. 3229, Springer-Verlag, 200–212. Faber, W., Leone, N., & Pfeifer, G. (2011). Semantics and complexity of recursive aggregates in answer set programming. Contents lists available at Science Direct Artificial Intelligence, 278–298.
8. Tạp chí Khoa học – Trường Đại học Phú Yên, Số 26 (2021), 92-99 99 Faber, W., Pfeifer, G., Leone, N., Armi, T. D., & Ielpa, G. (February 2008). Design and Implementation of Aggregate Functions in the DLV System. Department of Mathematics, University of Calabria 87036 Rende (CS), Italy, 12-20. Faber, W., Eiter, T., Georg, G., Leone, N., Pfeifer, G., Perri, S., & Francesco, S. (2006). The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic, 499-562. James, P. D., & Faber, W. (2011). Logic Programming and Nonmonotonic Reasoning. Vancouver, Canada: 11th International Conference. Logic Programming Language DLPA and its applications Vo Thi Nhu Ly Mientrung Industry And Trade College Email: lyvo2019@gmail.com Received: April 03, 2020; Accepted: January 08, 2021 Abstract In this paper, we summarize some syntax, semantics and semantic properties of the Logic Programming Language DLPA which is also simply called Disjunctive logic program with Aggregate Functions. We also demonstrate some applications in using the Logic Programming Language DLPA implemented in the Datalog plus Vel (DLV) system. Keywords: Logic Programming, DLPA Language, DLV system.