ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ






TẠ THỊ THU HIỀN




NGHIÊN CỨU VỀ CHỨNG MINH TỰ ĐỘNG
(THEOREM PROVING) TRONG CafeOBJ









LUẬN VĂN THẠC SĨ

Hà Nội - 2010













































ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ





TẠ THỊ THU HIỀN




NGHIÊN CỨU VỀ CHỨNG MINH TỰ ĐỘNG
(THEOREM PROVING) TRONG CafeOBJ






Ngành : CÔNG NGHỆ THÔNG TIN
Chuyên ngành : CÔNG NGHỆ PHẦN MỀM
Mã số : 60 48 10





LUẬN VĂN THẠC SĨ


NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Phạm Ngọc Hùng








Hà Nội - 2010





i
LỜI CẢM ƠN

Trƣớc tiên tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Phạm Ngọc Hùng,
giảng viên Bộ môn Công nghệ phần mềm - Khoa Công nghệ thông tin - Trƣờng
Đại học Công nghệ - ĐHQGHN. Trong thời gian học và làm luận văn tốt nghiệp,
thầy đã dành nhiều thời gian quí báu và tận tình chỉ bảo, hƣớng dẫn tôi trong
việc nghiên cứu, thực hiện luận văn.
Tôi xin đƣợc cảm ơn các GS, TS đã giảng dạy tôi trong quá trình học tập và
làm luận văn. Các thầy cô đã giúp tôi hiểu thấu đáo hơn lĩnh vực mà mình
nghiên cứu để có thể vận dụng những kiến thức đó vào trong công tác của mình.
Xin cảm ơn bạn bè, đồng nghiệp và nhất là các thành viên trong gia đình đã
tạo mọi điều kiện tốt nhất, động viên, cổ vũ tôi trong suốt quá trình học tập và
nghiên cứu để hoàn thành tốt bản luận văn tốt nghiệp này.
Hà nội, tháng 9 năm 2010
Học viên thực hiện



Tạ Thị Thu Hiền


ii
LỜI CAM ĐOAN

Tôi xin cam đoan rằng, đây là kết quả nghiên cứu của tôi trong đó có sự

giúp đỡ rất lớn của thầy hƣớng dẫn và các đồng nghiệp ở cơ quan. Các nội dung
nghiên cứu và kết quả trong đề tài này hoàn toàn trung thực.
Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả đã
đƣợc liệt kê tại phần tài liệu tham khảo ở cuối luận văn.

Hà nội, tháng 9 năm 2010
Học viên thực hiện




Tạ Thị Thu Hiền











iii
MỤC LỤC
LỜI CẢM ƠN ii
LỜI CAM ĐOAN ii
MỤC LỤC iii
BẢNG CÁC CHỮ VIẾT TẮT iv
DANH MỤC HÌNH VẼ v

Chƣơng 1 Giới thiệu 1
1.1 Đặt vấn đề 1
1.2 Nêu bài toán 2
1.3 Kết quả 2
1.4 Cấu trúc luận văn 3
Chƣơng 2 Tổng quan về CafeOBJ 4
2.1 Giới thiệu 4
2.2 Đặc tả và kiểm chứng trong CafeOBJ 7
2.3 Ví dụ 7
Chƣơng 3 Đặc tả hệ thống đa tác tử và các thuộc tính 11
3.1 Mô tả bài toán QLOCK 11
3.2 Đặc tả bài toán QLOCK bằng ngôn ngữ cafeOBJ 14
3.3 Đặc tả các thuộc tính 20
Chƣơng 4 Kiểm chứng hệ thống đa tác tử 23
4.1 Tƣ tƣởng kiểm chứng 23
4.2 Kiểm chứng các thuộc tính của bài toán QLOCK 23
4.2.1 Chứng minh inv1(S,I,J) 23
4.2.2 Chứng minh inv2(S,I) 27
4.2.3 Chứng minh inv3(S,I) 28
4.2.4 Chứng minh inv4(S,I) 32
4.2.5 Chứng minh inv5(S,I) 33
Chƣơng 5 Kết luận 39
Tài liệu tham khảo 41
Phụ lục 1 Chứng minh cho inv1(s,i,j) 42
Phụ lục 2 Chứng minh cho inv2(s,i) 48
Phụ lục 3 Chứng minh cho inv3 (s,i) 52
Phụ lục 4 Chứng minh cho inv4(s,i) 56
Phụ lục 5 Chứng minh cho inv5(s,i) 57



iv
BẢNG CÁC CHỮ VIẾT TẮT















VIẾT TẮT
Tên đầy đủ
MAS
Multi-Agent System
OTS
Observation Transition System
QLOCK
Locking with queue


v
DANH MỤC HÌNH VẼ


Hình 2.1. Cú pháp của mô đun. 5
Hình 2.2. Đặc tả mô đun simple-nat.mod. 5
Hình 2.3. Đọc file simple-nat.mod trong CafeOBJ. 5
Hình 2.4. Mô tả eof trong CafeOBJ. 6
Hình 2.5. Định nghĩa subsort trong sort. 6
Hình 2.6. Mô đun NAT+ trong CafeOBJ. 7
Hình 2.7. Chứng minh tính kết hợp của phép cộng các số tự nhiên. 8
Hình 2.8. Chứng minh bổ đề i+0=i 9
Hình 2.9. Chứng minh 0+j=j+0. 9
Hình 2.10. Chứng minh lemma2: i + s(j) = s(i+j). 10
Hình 2.11. Chứng minh i+j = j + i. 10
Hình 3.1. Mã lệnh của các BXL. 11
Hình 3.2. Mô tả QLOCK với phƣơng thức độc quyền truy xuất. 12
Hình 3.3. View of QLOCK. 13
Hình 3.4. Mô hình QLOCK với OTS. 14
Hình 3.5. Đặc tả (signature) cho hệ thống QLOCK. 15
Hình 3.6. Đặc tả mô đun LABEL. 16
Hình 3.7. Đặc tả mô đun PID. 16
Hình 3.8. Kiểu biến tổng quát cho hàng đợi QUEUE. 17
Hình 3.9. Hàng đợi QUEUE cho bài toán QLOCK. 18
Hình 3.10. Các lemma trong queue. 19
Hình 3.11. Hành động try trong hệ thống QLOCK. 19
Hình 3.12. Đặc tả các thuộc tính trong CafeOBJ. 21
Hình 3.13. Mô đun ISTEP trong CafeOBJ. 22
Hình 4.1. Kiểm chứng inv1 với trƣờng hợp (1). 25
Hình 4.2. Kiểm chứng inv1 với trƣờng hợp (5). 25
Hình 4.3. Kiểm chứng inv1 với trƣờng hợp (*). 26


vi

Hình 4.4. Kiểm chứng inv2 với trƣờng hợp c-exit, ~(i = k). 28
Hình 4.5. Kiểm chứng inv3 với trƣờng hợp c-want(s,k), ~(i = k), ~(i \in queue(s)). 30
Hình 4.6. Kiểm chứng inv3 với c-exit(s,k), i=k. 31
Hình 4.7. Kiểm chứng inv3 với c-exit(s,k), ~(i = k), ~(i \in queue(s)). 32
Hình 4.8. Chứng minh inv4 với trƣờng hợp queue(s) = x,q, i = x. 33
Hình 4.9. Chứng minh inv5 với trƣờng hợp c-want(s,k), queue(s) = x,q, i = k. 35
Hình 4.10. Chứng minh inv5 với trƣờng hợp c-want(s,k), queue(s) = x,q, ~(i = k), x = i, ~(i \in q).36
Hình 4.11. Chứng minh inv5 với trƣờng hợp c-exit(s,k), i = k, queue(s) = x,q, x = k, ~(k \in q). 37
Hình 4.12. Chứng minh inv5 với trƣờng hợp c-exit(s,k), ~(i = k), queue(s) = x,q, x = i.38















1
CHƢƠNG 1
GIỚI THIỆU
1.1 Đặt vấn đề
Đặc tả và kiểm chứng hình thức là một pha quan trọng nhằm nâng cao độ tin cậy
và chất lƣợng của phần mềm. Có thể chia đặc tả phần mềm ra làm hai loại: đặc

tả phi hình thức là đặc tả dựa trên ngôn ngữ tự nhiên và đặc tả hình thức là đặc
tả dựa trên kiến trúc toán học. Đặc tả phi hình thức không đƣợc chặt chẽ bằng
đặc tả hình thức nhƣng đƣợc nhiều ngƣời biết và có thể dùng để trao đổi với
nhau để làm chính xác hóa các điểm chƣa rõ, chƣa thống nhất giữa các bên phát
triển hệ thống. Đặc tả hình thức là đặc tả mà ở đó các từ ngữ, cú pháp, ngữ nghĩa
đƣợc định nghĩa hình thức dựa vào toán học. Đặc tả hình thức có thể coi là một
phần của hoạt động đặc tả phần mềm. Trong đặc tả hình thức các đặc tả yêu cầu
đƣợc phân tích chi tiết, các mô tả trừu tƣợng của các chức năng chƣơng trình có
thể đƣợc tạo ra để làm rõ yêu cầu.
Đặc tả phần mềm hình thức là một đặc tả đƣợc trình bày trên một ngôn ngữ bao
gồm: từ vựng, cú pháp và ngữ nghĩa đƣợc định nghĩa. Định nghĩa ngữ nghĩa
đảm bảo ngôn ngữ đặc tả không phải là ngôn ngữ tự nhiên mà dựa trên toán học.
Các chức năng nhận các đầu vào trả lại các kết quả. Các chức năng có thể định
ra các điều kiện tiền tố và hậu tố. Điều kiện tiền tố là điều kiện cần thỏa mãn để
có dữ liệu vào, điều kiện hậu tố là điều kiện cần thỏa mãn sau khi có kết quả.
Có hai hƣớng tiếp cận đặc tả hình thức để phát triển các hệ thống tƣơng đối
phức tạp:
- Tiếp cận đại số, hệ thống đƣợc mô tả dƣới dạng các toán tử và các
quan hệ
- Tiếp cận mô hình, mô hình hệ thống đƣợc cấu trúc sử dụng các thực
thể toán học nhƣ là các tập hợp và các thứ tự
Kiểm thử một sản phẩm phần mềm là xây dựng một cách có chủ đích những tập
dữ liệu và dãy thao tác nhằm đánh giá một số hoặc toàn bộ các tiêu chuẩn của
sản phẩm phần mềm đó. Thử nghiệm có hai mục đích: chỉ ra hệ thống phù hợp
với đặc tả và phơi ra đƣợc các khuyết tật của hệ thống. Trong khi việc kiểm thử
phần mềm (software testing) [4] chỉ có thể chỉ ra các lỗi phát hiện đƣợc nhƣng
không thể chỉ ra đƣợc phần mềm hoàn toàn không có lỗi, các phƣơng pháp kiểm


2

chứng có thể đảm bảo hệ thống không có lỗi sau khi đã đƣợc kiểm chứng đúng
đắn.
Theo hƣớng tiếp cận mô hình, chúng ta có phƣơng pháp kiểm chứng mô hình
(Model checking) [3], với đầu vào là một otomat hữu hạn trạng thái và thuộc
tính cần kiểm chứng, sẽ cho kết quả đầu ra là true hoặc false. Hiện nay có nhiều
phƣơng pháp hỗ trợ đặc tả và kiểm chứng phần mềm theo hƣớng tiếp cận trên
nhƣ SPIN [5], SMV [6], NuSMV [7] Khác với kiểm chứng mô hình, chứng
minh tự động (Theorem Proving) có thể kiểm chứng các hệ thống với mô hình là
vô hạn trạng thái; CafeOBJ [2] là một ngôn ngữ hỗ trợ đặc tả và kiểm chứng
theo tƣ tƣởng của chứng minh tự động.
Mục đích của khóa luận là tìm hiểu về phƣơng pháp đặc tả và kiểm chứng hình
thức phần mềm trong CafeOBJ. Từ mô tả của hệ thống cần kiểm chứng, chúng
ta cần đặc tả hệ thống một cách hình thức bằng ngôn ngữ CafeOBJ. Các thuộc
tính cần kiểm chứng của hệ thống cũng đƣợc đặc tả một cách tƣơng tự. Sử dụng
ngữ nghĩa cú pháp trong ngôn ngữ CafeOBJ để thể hiện các đặc tả hệ thống
cũng nhƣ các đặc tả thuộc tính của hệ thống cần kiểm chứng dƣới dạng hình
thức từ các phát biểu của ngôn ngữ tự nhiên.
1.2 Nêu bài toán
Bài toán thực hiện trong khóa luận là bài toán đặc tả và kiểm chứng hệ thống đa
tác tử (MAS) sử dụng ngôn ngữ CafeOBJ. Tài liệu [1] đã giải quyết đƣợc trƣờng
hợp xung đột tài nguyên, tại một thời điểm chỉ có một tiến trình (agent) đƣợc sử
dụng tài nguyên dùng chung. Khóa luận của tôi sẽ tập trung vào chứng minh các
thuộc tính khác của hệ thống đa tác tử bằng ngôn ngữ CafeOBJ; tƣ tƣởng chứng
minh là dùng phƣơng pháp qui nạp, phân rã bài toán ra các trƣờng hợp và thêm
các bổ đề vào. Tƣ tƣởng trên đã kiểm chứng đƣợc hệ thống đa tác tử (MAS) với
không gian trạng thái là vô hạn.
1.3 Kết quả
Luận văn đã đạt đƣợc các kết quả sau:
- Tìm hiểu và nắm rõ phƣơng pháp đặc tả phần mềm sử dụng ngôn ngữ
đại số CafeOBJ.

- Nắm vững phƣơng pháp chứng minh tự động sử dụng tƣ tƣởng qui


3
nạp toán học để kiểm chứng các thuộc tính bất biến (invariant
property). Với phƣơng pháp này, để chứng minh một thuộc tính bất
biến, chúng ta cần chứng minh nó đúng tại trạng thái khởi tạo của hệ
thống. Giả sử thuộc tính đúng tại một trạng thái bất kỳ s, chúng ta phải
chứng minh nó đúng với mọi trạng thái tiếp theo của s.
- Áp dụng những kiến thức đã tìm hiểu để kiểm chứng 04 thuộc tính của
hệ thống đa tác tử. Trong hệ thống này, các tác tử chia sẻ một tài
nguyên dùng chung. Số lƣợng tác tử trong hệ thống là vô hạn vì vậy
không gian trang thái là vô hạn. Với hệ thống này, chúng ta không thể
áp dụng các phƣơng pháp kiểm chứng mô hình vì lý do trên. Kết quả
kiểm chứng cho thấy hệ thống đa tác tử thỏa mãn các thuộc tính cần
kiểm tra tại mọi trạng thái của hệ thống.
1.4 Cấu trúc luận văn
Các phần còn lại của luận văn có cấu trúc nhƣ sau:
- Chƣơng 2 trình bày tổng quan về ngôn ngữ CafeOBJ, kỹ thuật đặc tả
và kiểm chứng phần mềm bằng phƣơng pháp hình thức đƣợc sử dụng
trong CafeOBJ.
- Một hệ thống đa tác tử và 5 thuộc tính đƣợc đặc tả trong chƣơng 3.
- Chƣơng 4 mô tả về phƣơng pháp kiểm chứng hệ thống đa tác tử bằng
ngôn ngữ CafeOBJ, với tƣ tƣởng quy nạp, có thể kiểm chứng với
không gian trạng thái là vô hạn.
- Tóm tắt kết quả đã đạt đƣợc, kết luận, những hạn chế và hƣớng nghiên
cứu phát triển trong tƣơng lai sẽ đƣợc trình bày trong chƣơng 5.




4
CHƢƠNG 2
TỔNG QUAN VỀ CafeOBJ
2.1 Giới thiệu
CafeOBJ là một ngôn ngữ đặc tả đại số đƣợc phát triển ở Nhật Bản dƣới sự chỉ
đạo của GS Kokichi Futatsugi trong phòng thí nghiệm Language Design tại Viện
khoa học và công nghệ tiên tiến Nhật Bản (JAIST). Chúng hỗ trợ phƣơng pháp
kiểm chứng dựa trên kỹ thuật đặc tả đại số và phƣơng pháp quy nạp nhằm kiểm
chứng các chƣơng trình với miền trạng thái vô hạn. CafeOBJ là một ngôn ngữ
thực thi dựa trên nhiều cơ sở lôgic, chủ yếu dựa trên các đại số ban đầu và đại số
đƣợc suy luận.
Các lôgic cơ bản của CafeOBJ bao gồm :
- Lôgic đƣợc sắp xếp theo thứ tự (Order-sorted logic): một kiểu có thể
là kiểu con của kiểu khác. Ví dụ: số tự nhiên là thuộc số hữu tỉ, nhƣng
chúng đảm bảo tính chất hợp lệ là 3 phải bằng 6/2.
- Lôgic biến đổi (Rewriting logic): Ngoài ra để bằng nhau, các biểu
thức phải hợp lệ tính đối xứng, chúng ta có thể sử dụng quan hệ bắc
cầu. Đặc trƣng của quan hệ bắc cầu là rất thuận lợi để thể hiện đồng
thời hoặc tính không xác định.
- Các kiểu ẩn (Hidden sorts): Chúng ta có 2 loại trƣơng đƣơng. Một là
tƣơng đƣơng cực tiểu (minimal equivalence) chính là đồng nhất hóa 2
vế và chúng tƣơng đƣơng khi và chỉ khi chúng giống nhau thông qua
các phƣơng trình đã cho. Kiểu tƣơng đƣơng khác dùng cho kiểu ẩn, là
biến đổi 2 vế là tƣơng đƣơng khi và chỉ khi chúng ứng xử đồng nhất
dựa trên bộ quan sát đã cho.
Đặc tả trong CafeOBJ bao gồm các mô đun. Mỗi mô đun trong CafeOBJ đƣợc
định nghĩa với cú pháp nhƣ hình 2.1, trong đó < mod_name > là tên của mô đun
và mod_elements là thành phần của mô đun.

mod module-name {

module-elements
}




5


Hình 2.1. Cú pháp của mô đun.

Hình 2.2 đặc tả 2 mô đun là mô đun SIMPLE-NAT và mô đun NAT+, đƣợc lƣu
là simple-nat.mod; mô đun SIMPLE-NAT định nghĩa hai phép toán 0 và s (next).
Mô đun NAT+ kế thừa mô đun SIMPLE-NAT, định nghĩa thêm phép toán + và
tính chất của phép toán 0 và s (next) bởi từ khóa eq.









Hình 2.2. Đặc tả mô đun simple-nat.mod.

Có 3 kiểu khai báo mô đun trong CafeOBJ là mod! (Tight modules) , mod*
(Loose modules ), mod. Để load mô đun simple-nat.mod ta dùng cú pháp in
filename





Hình 2.3. Đọc file simple-nat.mod trong CafeOBJ.

Với từ khóa eof trong CafeOBJ, chƣơng trình sẽ chỉ đọc file đến dòng trƣớc từ
eof, ở hình 2.4 chƣơng trình sẽ chỉ đọc mod SIMPLE-NAT mà lờ đi mod NAT+


mod! SIMPLE-NAT {
[ Nat ]
op 0 : -> Nat { constr }
op s : Nat -> Nat { constr }
}

mod! NAT+ {
pr(SIMPLE-NAT)
op _+_ : Nat Nat -> Nat
eq 0 + M:Nat = M .
eq s (N:Nat) + M:Nat = s (N + M) .
}

CafeOBJ> in simple-nat
processing input : simple-nat.mod
defining module! SIMPLE-NAT _* done.
defining module! NAT+ _ * done.
CafeOBJ>

mod! SIMPLE-NAT {
[ Nat ]

op 0 : -> Nat { constr }
op s : Nat -> Nat { constr }
}
eof



6







Hình 2.4. Mô tả eof trong CafeOBJ.

Định nghĩa kiểu (sort) trong CafeOBJ có cú pháp nhƣ sau:


Định nghĩa kiểu con (subsort) trong kiểu (sort) nhƣ sau:


Hình 2.5 sẽ mô tả kiểu số nguyên không âm là kiểu con của kiểu số nguyên,
định nghĩa phép toán nhân hai số nguyên, phép chia một số nguyên cho một số
nguyên không âm.



Hình 2.5. Định nghĩa subsort trong sort.


Các thành phần của mô đun đƣợc cấu trúc trong ba phần chính. Phần thứ nhất,
imports chỉ rõ các mô đun phải đƣợc khai báo trong mô đun hiện thời, hay là sự
thừa kế các mô đun đã triển khai đƣợc khai báo trong mô đun hiện thời. Có ba
dạng của việc thừa kế các mô đun: protecting (thừa kế các mô đun nhƣng
không thể thay đổi chúng), extending (thừa kế các mô đun có thể mở rộng
chúng, nhƣng những mô tả ban đầu còn lại không đƣợc thay đổi) và using (thừa
kế các mô đun có thể mở rộng hoặc thay đổi sự mô tả ban đầu). Phần thứ hai,
signature, khai báo các kiểu (sorts), các kiểu con (subsorts), và các toán tử
(operators) đƣợc sử dụng trông mô đun. Và cuối cùng, axioms bao gồm sự khai
báo của các biến, các phƣơng trình (equations), các sự dịch chuyển (transitions),
[ sort-name sort-name ]

[ subsort-name < supersort-name ]

[ NzInt < Int ]
op _*_ : Int Int -> Int
op _/_ : Int NzInt -> Int




7
và các biểu thức thể hiện hành vi của mô đun.
2.2 Đặc tả và kiểm chứng trong CafeOBJ
Để cung cấp sự mô tả một mô đun trong CafeOBJ, chúng ta tìm hiểu ví dụ trong
hình 2.6, với sự định nghĩa mô đun NAT+ nhƣ là mô tả cho số tự nhiên. Mô đun
NAT+ thừa kế các kiểu (sorts) và các toán tử (operators) đã đƣợc định nghĩa
trong mô đun SIMPLE-NAT. Phần signature khai báo toán tử +. Hằng số 0,
toán tử s đƣợc khai báo bởi op trong SIMPLE-NAT. Hành vi của toán tử “+” là

đƣợc thực hiện bởi hai biểu thức và đƣợc khai báo bởi eq.









Hình 2.6. Mô đun NAT+ trong CafeOBJ.

Chúng ta có thể tham khảo thêm trong [2] về cú pháp, ngữ nghĩa của đặc tả và
kiểm chứng trong CafeOBJ.
Qui trình kiểm chứng trong CafeOBJ nhƣ sau:
- Kiểm tra thuộc tính có đúng với i=giá trị khởi đầu hay không (i là một
thành phần của thuộc tính)
- Giả sử thuộc tính đúng đúng với i bất kỳ
- Đi chứng minh thuộc tính đúng với i'=s(i)



2.3 Ví dụ
mod! NAT+{
imports {
pr(SIMPLE-NAT)
}
signature {
op _+_ : Nat Nat -> Nat
}

axioms {
vars N M : Nat
eq 0 + M = M .
eq s(N) + M = s(N + M) .
}
}





8
Để tìm hiểu về đặc tả và kiểm chứng trong CafeOBJ, chúng ta tìm hiểu một ví
dụ đơn giản về sự đặc tả hệ thống số tự nhiên, đặc tả thuộc tính cần chứng minh
và kiểm chứng thuộc tính đó. Trong ví dụ này chúng ta chỉ mô tả một số đặc tả
cơ bản với phép toán cộng (“+”), phép so sánh (“=”), phép toán (“s”) tăng số tự
nhiên lên một đơn vị, và đặc tả thuộc tính cần kiểm chứng chính là tính chất kết
hợp của phép cộng tức là:
( I+ J) + K = I + (J + K), với I, J, K là số tự nhiên bất kỳ (*).
Sử dụng mô đun NAT+ đƣợc mô tả ở trên để chứng minh cho thuộc tính (*) nhƣ
hình sau, tƣ tƣởng chứng minh là dùng phƣơng pháp quy nạp, đầu tiên kiểm
chứng (*) với i=0, sau đó giả thiết (*) đúng với trƣờng hợp i bất kỳ, sau đó
chứng minh (*) đúng với s(i). Sử dụng mod NAT+ đƣợc mô tả trong hình 2.6 để
chứng minh tính chất (*) nhƣ hình sau:












Hình 2.7. Chứng minh tính kết hợp của phép cộng các số tự nhiên.

Kết quả của hình 2.7 trả về true, vậy thuộc tính (*) đƣợc chứng minh.
Tiếp theo ta sẽ chứng minh tính chất giao hoán của phép cộng các số tự nhiên
I+ J = J+ I , với I, J là số tự nhiên bất kỳ (**).
Cũng với tƣ tƣởng quy nạp nhƣ trên nhƣng khi red 0+ j = j + 0 không trả về giá
trị true mà trả về một kiểu boolean, khi đó ta phải thêm các bổ đề vào, làm sao
CLAIM: associativity over _+_
\forall i, j, k \in Nat: (i + j) + k = i + (j + k)
will be proven by induction on i.
PROOF:
open NAT+ + EQL
declaring three arbitrary numbers i,j and k on the sort Nat:
ops i j k : -> Nat .
base step:
red ((0 + j) + k) = (0 + (j + k)) .
> should be true.
induction hypothesis:
eq (i + j) + k = i + (j + k) .
inductive step:
red ((s(i) + j) + k) = (s(i) + (j + k)) .
> should be true.
close
Q.E.D.





9
để tìm ra bổ đề, ta nhận thấy trong mô đun NAT+ ta đã có tính chất eq 0 +
M:Nat = M. Bây giờ nếu chứng minh đƣợc bổ đề j+0=j với mọi j thì kết quả
của 0+j=j+0 sẽ trả về true.








Hình 2.8. Chứng minh bổ đề i+0=i.

Sử dụng bổ đề trên ta sẽ chứng minh đƣợc j+0=0+j nhƣ hình sau






Hình 2.9. Chứng minh 0+j=j+0.

Tiếp theo giả thiết i + j = j+i, khi red s(i) + j = j + s(i) không trả về true mà trả về
một kiểu boolean, có nghĩa là ta phải thêm bổ đề vào, vậy tìm bổ đề nhƣ thế nào,
nhận thấy từ NAT+ ta có s(i) + j = s(i+j) theo giả thiết i+j=j+i vậy s(i) + j =
s(j+i), do vậy mục đích là chứng minh j+s(i) = s(j+i), hình 2.10 sau sẽ chứng

minh bổ đề trên

LEMMA1: \forall i \in Nat: i + 0 = i .
PROOF:
open NAT+ + EQL
ops i : -> Nat .
base step:
red 0 + 0 = 0 . > should be true.
induction hypothesis:
eq i + 0 = i .
inductive step:
red s(i) + 0 = s(i) . > should be true.
Close
Q.E.D.

open NAT+ + EQL
arbitarily choosen two naturals:
ops i j : -> Nat .
base step:
eq N:Nat + 0 = N . use LEMMA1.
red 0 + j = j + 0 .
> should be true.
close




10













Hình 2.10. Chứng minh lemma2: i + s(j) = s(i+j).

Hình 2.11 sau sẽ chứng minh cho tính chất giao hoán của phép cộng các số tự
nhiên







Hình 2.11. Chứng minh i+j = j + i.

Với tƣ tƣởng kiểm chứng bằng phƣơng pháp quy nạp đó, trong CafeOBJ cũng hỗ trợ
rất mạnh mẽ sẽ đƣợc đề cập ở phần sau. Đƣợc xem nhƣ là một tƣ tƣởng nổi bật của
việc kiểm chứng phần mềm và kiểm thử phần mềm. Nhờ phƣơng pháp quy nạp này
mà việc kiểm chứng các thuộc tính của hệ thống với không gian trạng thái vô hạn
đƣợc thực hiện một cách rõ ràng, trong hình 2.11 chúng ta thấy đƣợc sự kiểm chứng
bằng phƣơng pháp quy nạp với việc thêm vào các bổ đề. Sau khi thực hiện chƣơng
trình nhƣ hình 2.11 trong CafeOBJ, hệ thống CafeOBJ trả về kết quả “true”, nghĩa là

hệ thống đã đƣợc kiểm chứng thỏa mãn với điều kiện (**).
open NAT+ + EQL
arbitarily choosen two naturals:
ops i j : -> Nat .
base step:
eq N:Nat + 0 = N . use LEMMA1.
red 0 + s ( j ) = s ( 0 + j ) .
> should be true.
**> induction step
eq i + s ( j ) = s ( i + j ) .
> conclusion of induction step
red s ( i ) + s ( j ) = s ( s ( i ) + j ) .
**> should be true

**> QED for Lemma2
close

open NAT+ + EQL
arbitarily choosen two naturals:
ops i j : -> Nat .
base step:
eq N:Nat + 0 = N . use LEMMA1.
red 0 + j = j + 0 .
> should be true.
eq i + j = j + i .
eq N:Nat + s ( M:Nat ) = s ( M + N ) . use lemma2.
red s ( i ) + j = j + s ( i ) .
close




11

CHƢƠNG 3
ĐẶC TẢ HỆ THỐNG ĐA TÁC TỬ VÀ CÁC THUỘC TÍNH

3.1 Mô tả bài toán QLOCK
Giả thiết là các tác tử (agents) hay các bộ xử lý (processes) tƣơng tranh với nhau
trong việc sử dụng tài nguyên dùng chung, nhƣng tại một thời điểm chỉ có một
agent duy nhất đƣợc sử dụng tài nguyên, do vậy các bộ xử lý thực hiện loại trừ
lẫn nhau trong việc sử dụng tài nguyên. Một phƣơng thức (thuật toán hay kỹ
thuật) giải quyết việc loại trừ lẫn nhau gọi là giao thức độc quyền truy xuất
(mutual exclusion protocol).
Mã lệnh của mỗi bộ xử lý nhƣ hình 3.1 chia thành 4 đoạn
- Đoạn vào (Entry Section): chuẩn bị để đƣợc truy nhập tài nguyên
- Đoạn găng (Critical Section): sử dụng tài nguyên
- Đoạn ra ( Exit Section): giải phóng tài nguyên
- Đoạn còn lại (Remainder Section): không cần sử dụng tài nguyên







Hình 3.1. Mã lệnh của các BXL.

Trong đó QLOCK là một hệ thống sử dụng giao thức độc quyền truy xuất với
một hàng đợi (Queue) dùng chung cho tất cả các tiến trình (processes) thỏa mãn
các yêu cầu sau:

- Agents: không giới hạn số lƣợng các agents.
- Atomic action: khi có một action đang đƣợc thực hiện trong hàng đợi thì
các hành động khác phải chờ cho đến khi hành động hiện thời kết thúc.
- Trạng thái ban đầu (initial state): mọi tiến trình là ở đoạn còn lại
(Remainder Section) đƣợc gán nhãn là l1, và hàng đợi là rỗng.
Đoạn còn lại
Đoạn vào
Đoạn găng
Đoạn ra


12

Hình 3.2 sau mô tả bài toán QLOCK với phƣơng thức độc quyền truy xuất: mỗi
bộ xử lý (agent) i bất kỳ thực hiện: đầu tiên ở vào đoạn còn lại và đƣợc gán nhãn
là l1, sau đó i đƣợc đẩy vào đáy (bottom) của hàng đợi, sau đó nếu i muốn vào
miền găng thì i đƣợc gán nhãn là l2, kiểm tra i có phải ở đỉnh của hàng đợi hay
không, nếu đúng thì i đi vào miền găng và gán nhãn là cs, ngƣợc lại i phải chờ
cho đến khi là đỉnh của hàng đợi. Sau khi thực hiện trong miền găng, i đi ra
đoạn remainder section và gán nhãn l1.















Hình 3.2. Mô tả QLOCK với phƣơng thức độc quyền truy xuất.

Trong bài toán QLOCK chúng ta phải sử dụng một hàng đợi để thực hiện
phƣơng thức độc quyền truy xuất cho cả hệ thống. Việc tạo ra một hàng đợi với
các thuộc tính và phƣơng thức cơ bản của một hàng đợi nhƣ chúng ta đã biết,
gồm các phƣơng thức put đƣa một thành phần vào hàng đợi, phƣơng thức get
xóa một thành phần ra khỏi hàng đợi. Hình 3.3 sau mô tả một hàng đợi queue
với 3 tiến trình (agent) i, j, k; 2 phƣơng thức top và get; i đang ở đỉnh hàng đợi, j
ở đáy hàng đợi; i đang ở đỉnh hàng đợi do vậy có thể thực hiện phƣơng thức get
Mỗi tiến trình i thực hiện:
Remainder Section
l1
Đẩy i vào đáy queue
Critical Section
cs
Lấy ra đỉnh queue
l2

i là đỉnh
queue ?
true

: atomic action
false



13
với i mà không thực hiện phƣơng thức put với i đƣợc; phƣơng thức put đẩy k
vào cuối hàng đợi; tiến trình j ở trong hàng đợi nhƣng không ở đầu hàng đợi nên
không thực hiện đƣợc hai phƣơng thức put và get.





Hình 3.3. View of QLOCK.

Tiếp theo hình 3.4 sẽ mô hình hóa bài toán QLOCK trong hệ thống chuyển dịch
tổng quan (OTS) bằng biểu đồ ký số (signature diagram), sau đây sẽ mô tả chi
tiết hơn các ký số: Sys là kiểu thể hiện không gian trạng thái của hệ thống; Label
là kiểu thể hiện nhãn cho mỗi trạng thái, bao gồm: l1, l2, cs; Pid là kiểu thể hiện
định danh các tiến trình; Queue là kiểu thể hiện hàng đợi chứa các tiến trình; pc
là toán tử trực quan (observer) trả về nhãn của các agent ở trạng thái hiện thời,
pc có đầu vào là một trạng thái kiểu Sys và một tiến trình kiểu Pid, đầu ra là kiểu
Label; queue: toán tử trực quan (observer) trả về hàng đợi các định danh của tiến
trình ở trạng thái hiện thời, queue có đầu vào là một trạng thái kiểu Sys, đầu ra
kiểu Queue; init là trạng thái khởi đầu; want là một hành động của việc đƣa về
trạng thái tiếp theo sau khi thực hiện tiến trình có kiểu Pid với nhãn l1 ở trạng
thái có kiểu Sys; try là một hành động của việc đƣa về trạng thái tiếp theo sau
khi thực hiện tiến trình có kiểu Pid với nhãn l2 ở trạng thái có kiểu Sys, nếu tiến
trình có kiểu Pid có nhãn l2 và đang ở đỉnh của hàng đợi thì nhãn của tiến trình
đó ở trạng thái tiếp theo là cs; exit là một hành động của việc đƣa về trạng thái
tiếp theo sau khi thực hiện tiến trình có kiểu Pid với nhãn cs ở trạng thái có kiểu
Sys.



14











Hình 3.4. Mô hình QLOCK với OTS.

3.2 Đặc tả bài toán QLOCK bằng ngôn ngữ cafeOBJ
Có thể vắn tắt bài toán QLOCK dƣới dạng thuật toán (hình 3.2) trong đó:
- Queue là hàng đợi chứa các định danh (i) của các tiến trình và đƣợc
khởi tạo rỗng.
- Mọi tiến trình đƣợc khởi tạo với nhãn ban đầu là l1; khi một tiến trình
đƣợc đƣa vào hàng đợi, tiến trình đƣợc gán nhãn là l2; khi một tiến
trình đƣợc gán nhãn là l2 và ở đỉnh hàng đợi thì tiến trình đƣợc gán
nhãn là cs.
- put, top, get , \in là các phƣơng thức của hàng đợi (Queue).
QLOCK sẽ đƣợc đặc tả nhƣ một OTS với các thành phần:
- Hai hàm queue và pc
o queue(s) trả về hàng đợi các định danh của tiến trình ở
trạng thái s.
o pc(s,i) trả về nhãn (l1, l2 hay cs) của tiến trình i ở trạng
thái s.
- Khởi tạo với trạng thái ban đầu (init)




15

o queue(init) trả về empty
o pc(init, i) trả về nhãn l1 với mọi tiến trình i.
- Với 3 hành động want, try, exit
o want(s,i) đƣa về trạng thái tiếp theo sau khi thực hiện tiến
trình i với nhãn l1 ở trạng thái s.
o try(s,i) đƣa về trạng thái tiếp theo sau khi thực hiện lặp lại
tiến trình i với nhãn l2 ở trạng thái s. Nếu i có nhãn l2 và
top(queue(s) là i, thì nhãn của i ở trạng thái tiếp theo sẽ là cs.
o exit(s,i) đƣa về trạng thái tiếp theo sau khi thực hiện tiến
trình i với nhãn cs ở trạng thái s.
Chúng ta sẽ có đặc tả (signature) hệ thống nhƣ hình 3.5 bao gồm 1 kiểu không
gian trạng thái của hệ thống Sys; 3 kiểu khai báo: Queue, Label, Pid; 2 toán tử
trực quan: pc, queue; 3 hành động: want, try, exit .
















Hình 3.5. Đặc tả (signature) cho hệ thống QLOCK.

Chúng ta có đặc tả mô đun LABEL chứa nhãn của các bộ xử lý nhƣ hình 3.6 sau,
mô đun bao gồm các phần tử có kiểu Label; các hằng: l1, l2, cs; một phép toán
bằng = để so sánh hai nhãn bằng nhau có tính chất giao hoán; l1, l2, cs là khác
nhau từng đôi một; L=L trả về true.
state space of the system
*[Sys] *

visible sorts for observation
[Queue Pid Label]

observations
bop pc : Sys Pid > Label
bop queue : Sys > Queue

actions
bop want : Sys Pid > Sys
bop try : Sys Pid > Sys
bop exit : Sys Pid > Sys


Observation declaration
action declaration

Hiden sort declaration
visible sort declaration



16






Hình 3.6. Đặc tả mô đun LABEL.

Hình 3.7 sẽ đặc tả mô đun PID bao gồm các phần tử có kiểu Pid, một toán tử "="
có kiểu boolean để so sánh hai phần tử kiểu Pid có tính chất giao hoán.





Hình 3.7. Đặc tả mô đun PID.

Hình 3.8 sẽ khai báo hàng đợi tổng quát và định nghĩa cho phƣơng thức “top”
trong QUEUE trƣớc hết chúng ta tạo 2 mô đun EQTRIV và OPTION trong đó:
mô đun EQTRIV thể hiện các phần tƣ khai báo tổng quát có kiểu [Elt]; toán tử
"= " để so sánh hai phần tử kiểu Elt có tính chất giao hoán. Mô đun OPTION với
tham số truyền vào là một thể hiện của lớp EQTRIV, các phần tử có kiểu
[Option]; 3 hằng số: none, some, val; một toán tử = để so sánh hai phần tử kiểu
[Option] có tính chất giao hoán. Mô đun OPTION nhằm tiền định nghĩa cho
phƣơng thức “top” trong QUEUE. Khi một hàng đợi rỗng thì phƣơng thức “top”
sẽ trả về hằng số none ngƣợc lại sẽ trả về some(E) (trong đó E chính là phần tử ở
đỉnh hàng đợi); toán tử val là some

-1
nghĩa là val(some (E))= E; trong mô đun
OPTION có tính chất none <> some(E) và (some(E) = some(E')) = (E=E').
mod! LABEL {
[Label]
ops l1 l2 cs : -> Label
pred (_=_) : Label Label {comm}
var L : Label
eq (L = L) = true .
eq (rm = wt) = false .
eq (rm = cs) = false .
eq (wt = cs) = false .
}
mod* PID {
[Pid]
op _=_ : Pid Pid -> Bool {comm}
var I : Pid
eq (I = I) = true .
}


17












Hình 3.8. Kiểu biến tổng quát cho hàng đợi QUEUE.

Trong bài toán QLOCK chúng ta phải sử dụng một hàng đợi để thực hiện
phƣơng thức độc quyền truy xuất cho cả hệ thống. Việc tạo ra một hàng đợi với
các thuộc tính và phƣơng thức cơ bản của một hàng đợi nhƣ chúng ta đã biết,
gồm các phƣơng thức put đƣa một thành phần vào hàng đợi, phƣơng thức get
xóa một thành phần ra khỏi hàng đợi và top lấy ra một thành phần trên đỉnh của
hàng đợi, phƣơng thức \in kiểm tra một phần tử có ở trong hàng đợi hay không,
phƣơng thức del xóa một phần tử trong Queue. Các thuộc tính và những phƣơng
thức cơ bản đó đƣợc định nghĩa trong CafeOBJ nhƣ hình 3.9; mô đun QUEUE
chính là đặc tả cho hàng đợi trong hệ thống QLOCK.






mod* EQTRIV {
[Elt]
op _=_ : Elt Elt -> Bool {comm}
}
mod! OPTION(X :: EQTRIV) {
[Option]
op none : -> Option
op some : Elt.X -> Option
op val : Option -> Elt.X
op _=_ : Option Option -> Bool {comm}

var O : Option
vars E E' : Elt.X
eq val(some(E)) = E .
eq (O = O) = true .
eq (none = some(E)) = false .
eq (some(E) = some(E')) = (E = E').
}