GIỚI THIỆU
Kiểm chứng mô hình và các kỹ thuật kiểm thử hiện đang được coi là giải pháp chủ yếu để đảm bảo chất lượng cho sản phẩm phần mềm, đặc biệt là các hệ thống đa tác tử Trong khi các kỹ thuật kiểm thử chỉ có khả năng phát hiện lỗi, chúng không thể khẳng định rằng hệ thống không còn lỗi, do đó không đủ để đảm bảo chất lượng cho các hệ thống yêu cầu độ tin cậy cao Một phương pháp phổ biến hiện nay là kiểm chứng mô hình, với nhiều công cụ hỗ trợ như SMV và NuSMV Tuy nhiên, phương pháp này chỉ áp dụng cho các hệ thống có số lượng tác tử hữu hạn và yêu cầu xây dựng máy hữu hạn trạng thái để mô tả hành vi của hệ thống, điều này trở thành điểm yếu khi số lượng tác tử có thể thay đổi trong quá trình phát triển và thực thi Ngoài ra, vấn đề bùng nổ không gian trạng thái có thể xảy ra khi áp dụng kiểm chứng mô hình cho các hệ thống lớn với số lượng tác tử không xác định Trong những trường hợp này, phương pháp chứng minh định lý là lựa chọn phù hợp để đảm bảo tính đúng đắn của các hệ đa tác tử.
Luận văn này nhằm chứng minh tính đúng đắn cho bài toán xung đột tài nguyên trong các hệ đa tác tử sử dụng chung đa tài nguyên Tài liệu [2] đã xác nhận tính đúng đắn của một số thuộc tính bất biến trong hệ thống đa tác tử với một tài nguyên chung Tuy nhiên, khi áp dụng cho hệ thống với nhiều tài nguyên chung, phương pháp đặc tả cần được điều chỉnh Do đó, luận văn tập trung nghiên cứu một phương pháp đặc tả và kiểm chứng cho các hệ đa tác tử với nhiều tài nguyên, cụ thể là áp dụng vào hệ thống đại lý vé máy bay, sử dụng bộ chứng minh định lý CafeOBJ [3, 4].
Phần còn lại của luận văn được cấu trúc như sau: Chương 2 cung cấp tổng quan về ngôn ngữ CafeOBJ, công cụ hỗ trợ đặc tả và kiểm chứng phần mềm theo tư tưởng chứng minh định lý Chương 3 trình bày việc đặc tả và kiểm chứng các hệ đa tác tử sử dụng chung đa tài nguyên, giới thiệu hệ thống và phương pháp liên quan Chương 4 tập trung vào việc đặc tả và chứng minh tính đúng đắn cho hệ thống đại lý vé máy bay, với ví dụ minh họa cụ thể về việc đặt vé máy bay, mô tả bài toán bằng ngôn ngữ tự nhiên và hệ chuyển trạng thái quan sát được (OTS), từ đó thực hiện kiểm chứng bằng CafeOBJ Cuối cùng, Chương 5 đưa ra kết luận và định hướng phát triển, kèm theo tài liệu tham khảo và phụ lục.
TỔNG QUAN VỀ CafeOBJ
Giới thiệu
CafeOBJ là một ngôn ngữ đặc tả đại số có khả năng thực thi trên nhiều cơ sở lôgic khác nhau, chủ yếu dựa vào các đại số ban đầu và các đại số suy diễn Ngôn ngữ này hỗ trợ phương pháp kiểm chứng thông qua các kỹ thuật đặc tả đại số và quy nạp toán học, nhằm xác minh tính đúng đắn của các chương trình với miền trạng thái vô hạn CafeOBJ bao gồm ba lôgic cơ bản.
Lôgic được sắp xếp theo thứ tự (order-sorted logic) cho phép một kiểu có thể là kiểu con của một kiểu khác, ví dụ như tập hợp các số tự nhiên là tập con của tập hợp các số hữu tỷ, điều này chứng minh rằng 3 bằng 6/2 Hệ thống này cũng hỗ trợ việc kế thừa các phép toán, cho phép phép toán trên tập hợp số hữu tỷ tự động áp dụng cho tập hợp số tự nhiên Hơn nữa, mối quan hệ kiểu con giúp đơn giản hóa việc xác định các phép toán cục bộ và xử lý các ngoại lệ.
Logic biến đổi cho phép các biểu thức trở nên đồng nhất thông qua tính đối xứng và quan hệ bắc cầu, không cần phải trực tiếp Việc áp dụng quan hệ bắc cầu mang lại lợi ích lớn trong việc thể hiện tính đồng thời và tính bất định, tạo điều kiện thuận lợi cho việc phân tích và giải quyết các vấn đề phức tạp.
Các kiểu ẩn được chia thành hai loại tương đương Thứ nhất là tương đương cực tiểu, trong đó hai vế được coi là tương đương khi chúng giống nhau theo các điều kiện và phương trình đã được xác định Thứ hai là loại tương đương dành cho kiểu ẩn, trong đó hai vế tương đương khi chúng phản ứng giống nhau trước cùng một bộ quan sát.
CafeOBJ cung cấp tính năng truyền tham số rất hữu ích, cho phép định nghĩa nhiều kiểu dữ liệu trừu tượng như danh sách, tập hợp, hàng đợi và ngăn xếp Mỗi kiểu dữ liệu này có thể được định nghĩa thông qua mô-đun có khả năng truyền tham số, với các thành phần cơ bản được truyền từ bên ngoài vào.
Trong CafeOBJ, việc đặc tả được thực hiện thông qua các mô-đun, và khi khai báo mô-đun, người dùng có thể bắt đầu với từ khóa module hoặc mod Có ba kiểu khai báo mô-đun trong CafeOBJ: mod!, mod* và mod Mặc dù ngôn ngữ CafeOBJ không phân biệt ba kiểu khai báo này trong quá trình thực thi, nhưng việc chỉ rõ kiểu của mô-đun là rất quan trọng để hiểu đầy đủ và chính xác về đặc tả của mô-đun, đặc biệt trong các hệ thống phức tạp.
Một mô-đun không có tham số trong CafeOBJ được khai báo với cú pháp được trình bày như trong hình 2.1 module module_name { module_element *
Hình 2.1: Định nghĩa mô-đun trong CafeOBJ
Chi tiết của định nghĩa mô-đun trong hình 2.1 như sau:
The term "Module_name" refers to the specific name of the module being defined, while "module_element" encompasses the various components of the module These components may include import declarations for inheriting from other modules, sort declarations for defining types, variable declarations for establishing variables, operation declarations for defining functions, equation declarations for mathematical expressions, and transition declarations for state changes.
Chúng ta cùng xem xét hai ví dụ trong hình 2.2: Đặc tả mô-đun SIMPLE- NAT và hình 2.3 : đặc tả mô-đun NAT+
Hình 2.2: Đặc tả mô-đun SIMPLE-NAT trong CafeOBJ
Để khai báo và định nghĩa một mô-đun, trước tiên cần xác định kiểu của mô-đun, sau đó là tên của mô-đun Cụ thể, trong hình 2.2, kiểu dữ liệu Nat được định nghĩa trên dòng đầu tiên.
2), định nghĩa hằng số 0 thuộc kiểu dữ liệu Nat ta bắt đầu bằng từ khóa op (dòng
3), định nghĩa phép toán s (phép tăng một số tự nhiên lên 1 đơn vị) ta bắt đầu bằng từ khóa op (dòng 4)
Hình 2.3: Đặc tả mô-đun NAT+ trong CafeOBJ
Chi tiết của khai báo trong hình 2.3 như sau:
Mô-đun NAT+ kế thừa từ mô-đun SIMPLE-NAT, trong CafeOBJ hỗ trợ ba kiểu kế thừa: protecting (pr), extending (ex) và using (us) Phép toán cộng được khai báo bằng từ khóa op, với hai đối số kiểu Nat và kết quả cũng là kiểu Nat Phương trình đầu tiên định nghĩa phép cộng số 0 với một số Nat bất kỳ, bắt đầu bằng từ khóa eq, với kết quả trả về là chính nó, lưu ý rằng sau mỗi phương trình cần có dấu cách và dấu chấm “.” Cuối cùng, phương trình thứ hai định nghĩa phép cộng của phép toán s tăng biến N lên một đơn vị với biến M, và vế phải là phép toán s tăng kết quả của phép cộng N và M lên một đơn vị.
Chúng ta đã hoàn tất việc đặc tả hai mô-đun SIMPLE-NAT và NAT+ Tiếp theo, hãy lưu file đặc tả với tên example1.mod Để đọc mô-đun đã lưu trong file example1.mod, khởi động chương trình CafeOBJ, chỉ đến đường dẫn lưu file và gõ lệnh in, sau đó thêm một dấu cách và nhập example1.mod.
Chương trình CafeOBJ đọc đặc tả thành công thì sẽ có thông báo như sau: processing input : example1.mod
defining module! SIMPLE-NAT _* done
CafeOBJ hỗ trợ tổ chức các thành phần của mô-đun thành ba khối chính: khối imports để khai báo các mô-đun tham chiếu, khối signature để định nghĩa kiểu dữ liệu và phép toán, và khối axioms để khai báo các biến Điều này giúp việc đặc tả trở nên rõ ràng hơn.
(variables), các phương trình (equations), các dịch chuyển (transitions) Hình 2.5 mô tả chi tiết việc tổ chức các khối của mô-đun NAT+ mod! NAT+ { imports { pr(SIMPLE-NAT)
} signature { op _+_ : Nat Nat -> Nat
} axioms { eq 0 + M:Nat = M eq s (N:Nat) + M:Nat = s (N + M)
Hình 2.5: Tổ chức các thành phần của một mô-đun.
Đặc tả và kiểm chứng trong CafeOBJ
Sau khi xác định hệ thống và các thuộc tính của nó, bước tiếp theo là kiểm thử xem các thuộc tính này có phù hợp với đặc tả đã đưa ra hay không CafeOBJ cung cấp hỗ trợ cho việc kiểm chứng thông qua phương pháp quy nạp toán học.
Ví dụ minh họa
Bài viết này trình bày việc chứng minh tính chất kết hợp của phép cộng “+” trong tập hợp các số tự nhiên (NAT+) theo mô-đun đã được mô tả trong phần 2.1.
Tính chất kết hợp của phép cộng “+” ba số tự nhiên A, B, C được phát biểu như sau:
(A + B) + C = A + (B + C), với A, B, C là các số tự nhiên bất kỳ (*)
Hệ thống các số tự nhiên được đặc tả thông qua mô-đun SIMPLE-NAT và mô-đun NAT+, trong đó tính chất (*) là thuộc tính cần chứng minh Hình 2.6 minh họa các công đoạn chứng minh cho tính chất này, bao gồm open NAT+ và EQL.
Khai báo 3 số tự nhiên a, b, c bất kỳ ops a b c : -> Nat
Bước quy nạp: red ((s(a) + b) + c) = (s(a) + (b + c)) close
Hình 2.6: Các công đoạn chứng minh tính chất (*)
Sau khi thực hiện trong chương trình CafeOBJ ta thu được kết quả đều là true Điều đó chứng tỏ thuộc tính (*) đã được chứng minh.
ĐẶC TẢ HỆ THỐNG ĐA TÁC TỬ SỬ DỤNG CHUNG ĐA TÀI NGUYÊN
Giới thiệu bài toán
Hệ thống có nhiều tài nguyên dùng chung cho nhiều tác tử, trong đó mỗi tài nguyên chỉ được phép sử dụng bởi một tác tử tại một thời điểm nhất định Để đảm bảo tính đúng đắn và tránh xung đột tài nguyên giữa các tác tử, cần phải đặc tả rõ ràng hệ thống và các thuộc tính liên quan.
Hệ thống cần tạo ra số hàng đợi tương ứng với số tài nguyên hiện có, và các hàng đợi này sẽ được chia sẻ giữa tất cả các tác tử Mỗi hàng đợi sẽ đại diện cho một loại tài nguyên, do đó, tác tử muốn sử dụng tài nguyên nào phải đảm bảo rằng nó đã tồn tại trong hàng đợi tương ứng với tài nguyên đó.
Mỗi tác tử i khi tham gia vào hệ thống sẽ được gán nhãn rm Khi tác tử ở trong hàng đợi, chúng mang nhãn wt, và khi đang sử dụng tài nguyên, nhãn của chúng là cs Việc gán nhãn này giúp hệ thống quản lý trạng thái của từng tác tử, từ đó đưa ra quyết định xử lý hiệu quả.
Khi một tác tử i tham gia vào hệ thống mà chưa có nhu cầu sử dụng tài nguyên, nó sẽ được gán nhãn là rm, biểu thị rằng tác tử đang ở miền dư Khi tác tử yêu cầu sử dụng tài nguyên, nhãn của nó sẽ chuyển thành wt và được đưa vào cuối hàng đợi tương ứng Nếu tác tử ở đỉnh hàng đợi, nó sẽ được cấp phát tài nguyên và nhãn của nó sẽ đổi thành cs Sau khi hoàn thành việc sử dụng tài nguyên, nhãn của tác tử sẽ trở lại rm, đánh dấu rằng tác tử đã trở về miền dư.
Lưu đồ trong hình 3.1 minh họa quá trình hoạt động của hệ thống và đặc điểm độc quyền truy xuất của các tác tử đối với từng tài nguyên.
Hình 3.1: Lưu đồ mô tả quá trình hoạt động của hệ thống cũng như tính chất độc quyền truy xuất của các tác tử đối với mỗi tài nguyên
Hệ thống hoạt động thông qua các thao tác trên từng hàng đợi tương ứng với từng tài nguyên Khi một tác tử cần sử dụng tài nguyên, hệ thống sẽ đưa tác tử đó vào hàng đợi phù hợp Sau đó, hệ thống sẽ kiểm tra để xác định tác tử nào đang ở đầu hàng đợi và cho phép tác tử đó sử dụng tài nguyên Hình 3.2 minh họa rõ ràng cho quá trình này.
Hình 3.2: Thao tác của hệ thống đối với mỗi hàng đợi tương ứng với mỗi tài nguyên
Theo mô tả đối với hệ thống như trên thì hệ thống cần thỏa mãn các yêu cầu sau:
Mỗi tài nguyên trong hệ thống đều có quyền truy xuất độc quyền, nghĩa là khi một tác tử với định danh i đang sử dụng tài nguyên nào đó, thì không có tiến trình nào khác với định danh j (j ≠ i) có thể truy cập vào tài nguyên mà i đang sử dụng.
Mỗi tác tử trong hệ thống cần phải sử dụng tài nguyên chưa được sử dụng bởi bất kỳ tác tử nào, nếu có ít nhất một tác tử khác muốn sử dụng tài nguyên đó Điều này đảm bảo rằng một trong các tác tử sẽ được cấp quyền truy cập vào tài nguyên cần thiết.
- Đối với việc khởi tạo trạng thái ban đầu: mọi hàng đợi trong hệ thống đều rỗng, mọi tác tử đều đang ở miền dư
Chúng ta cùng xem xét một số kịch bản của hệ thống trên một hàng đợi tương ứng với một tài nguyên bất kỳ
Trong một hệ thống có ba tác tử được định danh là 1, 2 và 3, cả ba đều muốn sử dụng tài nguyên r8, với hàng đợi tương ứng là q8 Khi tác tử 3 có nhu cầu sử dụng tài nguyên, hệ thống gán nhãn wt cho tác tử này và đưa vào đuôi hàng đợi q8 Tiếp theo, tác tử 2 cũng có nhu cầu sử dụng tài nguyên, được gán nhãn wt và đưa vào hàng đợi sau tác tử 3 Khi miền găng cs trống, tác tử 3 ở đỉnh hàng đợi q8 được gán nhãn cs, cho phép sử dụng tài nguyên r8 Sau khi tác tử 3 hoàn thành việc sử dụng tài nguyên và được gán nhãn rm, nó quay trở lại miền dư cùng với tác tử 1 Các kịch bản tiếp theo của hệ thống diễn ra tương tự và được mô tả trong hình 3.3a và 3.3b.
Hình 3.3a: Một số kịch bản của hệ thống
Hình 3.3b: Một số kịch bản của hệ thống.
Phương pháp đặc tả
3.2.1 Đặc tả các tác tử
Hệ thống đa tác tử cho phép truy xuất tài nguyên chung tại mọi trạng thái, đảm bảo rằng mỗi tài nguyên chỉ được một tác tử truy xuất tại một thời điểm Mỗi tài nguyên được quản lý cẩn thận, với RId là tập hợp các định danh tài nguyên, trong đó r đại diện cho một tài nguyên cụ thể thuộc RId.
Trong hệ thống đa tác tử sử dụng chung đa tài nguyên, AId đại diện cho tập các định danh của các tác tử, RId là tập các định danh của các tài nguyên, và Sys là không gian trạng thái của hệ thống Mỗi tác tử i ∈ AId tương ứng với một tập hữu hạn các hành động ai1, ai2, , ain, được định nghĩa bởi hàm aij: Sys × RId × AId → Sys với j = 1, , n.
Hình 3.4: Định nghĩa tập hữu hạn các hành động của các tác tử
Với s ∈ Sys và con_aij : Sys × RId × AId → {true, false}, aij(s, r, i) = s’
Nếu con_aij(s, r, i) = true, thì s’ ∈ Sys và s’ khác s; ngược lại, aij(s, r, i) = s Khi s’ = aij(s, r, i), ta xác định s’ là trạng thái tiếp theo của s khi tác tử i thực hiện thành công hành động aij tại trạng thái s.
Không gian trạng thái của hệ thống đa tác tử (ký hiệu không gian trạng thái là
Hệ thống Sys bao gồm vô hạn các trạng thái, bắt đầu từ trạng thái khởi tạo được ký hiệu là init Mỗi trạng thái s ∈ Sys tương ứng với một tài nguyên r, tạo thành một cấu trúc phức tạp trong quá trình vận hành của hệ thống.
Hệ thống đa tác tử RId sẽ chuyển đến trạng thái tiếp theo s’ khi một trong các tác tử i ∈ AId thực hiện thành công hành động aij(s, r, i) với j = 1, …, n, trong đó s’ = aij(s, r, i) và s’ khác s Không gian trạng thái của hệ thống này được định nghĩa đệ quy và sử dụng chung đa tài nguyên.
Sys = {init} ∪ {aij(s, r, i) | s ∈ Sys, r ∈ RId, i ∈ AId, j ∈ [1 n] }
Hình 3.5: Định nghĩa đệ quy không gian trạng thái của hệ thống đa tác tử sử dụng chung đa tài nguyên
3.2.3 Đặc tả các thuộc tính bất biến
Trước khi triển khai hệ thống, đặc biệt là hệ đa tác tử, cần kiểm chứng một số thuộc tính quan trọng Nghiên cứu này tập trung vào thuộc tính bất biến, một đặc điểm cơ bản của các hệ thống Thuộc tính bất invariant yêu cầu hệ thống phải thỏa mãn tại mọi trạng thái, được định nghĩa là: inv: Sys × RId × AId × AId → { true, false}.
Để chứng minh thuộc tính bất biến của hệ đa tác tử sử dụng chung đa tài nguyên, cần xác định và chứng minh rằng thuộc tính này luôn luôn được thỏa mãn trong mọi tình huống.
Hình 3.7: Chứng minh thuộc tính bất biến luôn thỏa mãn.
Kiểm chứng hệ thống đa tác tử sử dụng chung đa tài nguyên
Hiện nay, kiểm chứng mô hình là phương pháp phổ biến để chứng minh tính đúng đắn của các hệ đa tác tử Tuy nhiên, hạn chế lớn nhất của phương pháp này là bùng nổ không gian trạng thái khi áp dụng cho hệ thống lớn, khiến nó khó khả thi trong thực tế Kiểm chứng mô hình chỉ hiệu quả với các hệ thống có không gian trạng thái hữu hạn, trong khi các hệ đa tác tử có số lượng tác tử không xác định có thể dẫn đến không gian trạng thái vô hạn Do đó, phương pháp này không thể áp dụng cho các hệ đa tác tử Để chứng minh tính đúng đắn của các hệ đa tác tử sử dụng chung đa tài nguyên, có thể áp dụng phương pháp chứng minh theo tư tưởng quy nạp toán học, bắt đầu bằng việc kiểm tra thuộc tính inv tại trạng thái khởi tạo.
Để xác định tính đúng đắn của thuộc tính inv(init, r, i, j), nếu kết quả là sai, chúng ta có thể kết luận rằng hệ thống không thỏa mãn thuộc tính này Ngược lại, nếu đúng, chúng ta sẽ tiến hành chứng minh quy nạp Bước đầu tiên là giả sử thuộc tính inv đúng tại một trạng thái s bất kỳ (s ∈ Sys), tức là inv(s, r, i, j) = true, và chứng minh rằng thuộc tính này cũng đúng tại tất cả các trạng thái tiếp theo của s Những trạng thái tiếp theo được xác định khi một tác tử thực hiện hành động tại trạng thái s Nếu inv thỏa mãn tại tất cả các trạng thái tiếp theo, hệ thống sẽ thỏa mãn thuộc tính inv Tuy nhiên, trong quá trình chứng minh, nhiều trường hợp có thể cho kết quả là một biểu thức logic thay vì true hoặc false, đòi hỏi chúng ta cung cấp thêm tri thức để rút gọn biểu thức và chứng minh tính thỏa mãn Việc tìm kiếm các hệ quả liên quan đến thuộc tính inv có thể gặp khó khăn và tốn thời gian, do đó, trước khi cung cấp các hệ quả cho hệ thống, chúng cần được chứng minh tính đúng đắn như các thuộc tính riêng biệt.
Quy trình chứng minh tính thỏa mãn của thuộc tính inv bằng phương pháp quy nạp toán học được mô tả trong hình 3.8
{inv(init, r, i, j) = true? | r ∈ RId, i, j ∈ AId}
Hình 3.8: Quy trình chứng minh các thuộc tính bất biến của hệ đa tác tử sử dụng chung đa tài nguyên.
ĐẶC TẢ VÀ CHỨNG MINH TÍNH ĐÚNG ĐẮN CHO HỆ THỐNG ĐẠI LÝ VÉ MÁY BAY
Mô tả bài toán trong hệ chuyển trạng thái quan sát được - OTS (Observational Transition System)
Trong phần trước, chúng ta đã mô tả hệ thống bằng ngôn ngữ tự nhiên và xác định một số thành phần quan trọng Bằng cách hiểu rõ hệ thống, phần này sẽ tập trung vào việc đặc tả hệ thống trong khung của Hệ chuyển trạng thái quan sát được (OTS).
Queue: Kiểu dữ liệu hàng đợi
ATASys là một kiểu dữ liệu mô tả không gian trạng thái của hệ thống, trong khi Label là kiểu dữ liệu thể hiện các nhãn của các đại lý, bao gồm các thành phần như rm, wt và cs.
AId: Kiểu dữ liệu thể hiện các định danh của các đại lý
FId: Kiểu dữ liệu thể hiện các định danh của các chuyến bay
Các phương thức trực quan trên PC và queue đều cung cấp thông tin quan trọng về trạng thái của hệ thống Cụ thể, phương thức trực quan trên PC trả về nhãn của một đại lý tại một trạng thái nhất định, trong khi phương thức trực quan trên queue cung cấp hàng đợi tương ứng với mỗi chuyến bay trong cùng một trạng thái.
Các phương thức chuyển trạng thái trong hệ thống bao gồm: phương thức "rm" (want) trả về trạng thái tiếp theo của hệ thống với ba tham số đầu vào là không gian trạng thái, định danh chuyến bay và định danh tác giả Tương tự, phương thức "wt" (try) cũng trả về trạng thái tiếp theo với cùng ba tham số đầu vào Cuối cùng, phương thức "cs" (exit) thực hiện chuyển trạng thái và trả về trạng thái tiếp theo với ba tham số đầu vào giống như các phương thức trên.
Hình 4.1: Mô hình hệ thống đại lý vé máy bay được mô tả trong hệ chuyển trạng thái quan sát được – OTS.
Đặc tả hệ thống với CafeOBJ
Bắt nguồn từ mô hình hệ thống trong hệ chuyển trạng thái quan sát được (OTS), chúng ta tiến hành đặc tả hệ thống trong CafeOBJ Mô-đun được sử dụng để đặc tả hệ thống này được gọi là ATA.
Đại lý vé máy bay (Airline Ticket Agent) bao gồm các thành phần chính như kiểu ẩn *[ATASys]*, thể hiện không gian trạng thái của hệ thống Phương thức trực quan pc trả về nhãn của một đại lý tương ứng với một chuyến bay tại bất kỳ trạng thái nào, với các nhãn gồm rm, wt và cs Mô-đun ATA kế thừa từ các mô-đun khác như LABEL, mô-đun định nghĩa các nhãn của đại lý, mô-đun FID, mô-đun xác định các chuyến bay, và mô-đun QUEUE.
(mô-đun đặc tả cho kiểu dữ liệu hàng đợi) (từ dòng 1 đến 3), khai báo kiểu ẩn
Mô-đun ATASys được thiết lập với trạng thái khởi tạo init và khai báo các phương thức trực quan pc và queue, cùng với các phương thức chuyển trạng thái Các mô-đun này sẽ được đặc tả chi tiết hơn sau này Hình 4.2a cung cấp cái nhìn tổng quan về các thành phần và phương thức của mô-đun ATA, tuy nhiên chưa có định nghĩa cụ thể cho các phương thức trực quan pc, queue và các phương thức chuyển trạng thái như want, try, exit.
Mô-đun ATA kế thừa các mô-đun LABEL, FID
3: pr(QUEUE(AID{sort Elt -> AId, sort EltErr -> AIdErr, op none -> none})) 4: *[ATASys]*
Đặc tả trạng thái khởi tạo của hệ thống
Các phương thức trực quan
6: bop pc : ATASys FId AId -> Label
7: bop queue : ATASys FId -> Queue
Các phương thức chuyển trạng thái
8: bop want : ATASys FId AId -> ATASys
9: bop try : ATASys FId AId -> ATASys
10: bop exit : ATASys FId AId -> ATASys
Hình 4.2a: Phần đặc tả đầu tiên của mô-đun ATA
Để chứng minh tính đúng đắn của hệ thống với mô-đun hệ thống ATA đã được đặc tả, chúng ta cần khai báo các luật và tiên đề Tiếp theo, cần mô tả chi tiết các trạng thái, phương thức trực quan, phương thức chuyển trạng thái, cũng như các điều kiện chuyển trạng thái của hệ thống.
Phương thức pc là một phương thức trực quan, có chức năng xác định nhãn của một đại lý tương ứng với một chuyến bay trong bất kỳ trạng thái nào của hệ thống Phương thức này yêu cầu ba tham số đầu vào: S, FI và AI, trong đó S thuộc kiểu dữ liệu ATASys (trạng thái hệ thống), FI là kiểu dữ liệu FId (định danh chuyến bay) và AI thuộc kiểu dữ liệu liên quan.
AId là kiểu dữ liệu định danh của các đại lý, trong khi đầu ra của phương thức trực quan PC là giá trị thuộc kiểu nhãn của các đại lý (Label) Tại trạng thái khởi tạo, các thông tin này đóng vai trò quan trọng trong việc xác định và quản lý các đại lý.
Nhãn của các đại lý liên quan đến chuyến bay có giá trị tại trạng thái khởi tạo (init) của hệ thống Hình 4.2b minh họa phần đặc tả tiếp theo của mô-đun ATA, trong đó trình bày phương thức trực quan pc và xác định nhãn của các đại lý.
11: eq pc(init,FI:FId,AI:AId) = rm
Hình 4.2b: Đặc tả phương thức pc tại trạng thái khởi tạo của hệ thống (init)
Trong phần đặc tả tiếp theo của module ATA, chúng ta sẽ đi vào chi tiết phương thức queue trong trạng thái khởi tạo của hệ thống (init) Ở giai đoạn khởi tạo, tất cả các hàng đợi tương ứng với từng chuyến bay đều ở trạng thái rỗng, do đó, đặc tả được thực hiện như sau:
12: eq queue(init, FI:FId) = empty
Hình 4.2c: Đặc tả chi tiết cho phương thức queue tại trạng thái khởi tạo (init) của hệ thống
Chúng ta đã hoàn thành việc mô tả hai phương thức trực quan pc và queue của hệ thống ở trạng thái khởi tạo (init) Tiếp theo, chúng ta cần đi vào chi tiết để mô tả các phương thức chuyển trạng thái want, try và exit trong mô-đun ATA.
Các phương thức chuyển trạng thái want, try và exit của hệ thống yêu cầu sử dụng các tham số đầu vào thuộc các kiểu dữ liệu như không gian trạng thái (ATASys), đại lý (AId), hàng đợi (Queue) và chuyến bay (FId) Điều này sẽ được trình bày chi tiết trong phần đặc tả tiếp theo của mô-đun.
ATA chúng ta cần khai báo các biến thuộc các kiểu tương ứng trước khi sử dụng
Hình 4.2d: Khai báo các biến S, AI, AJ, QI, FI trước khi sử dụng
Phương thức c-want được sử dụng để xác định liệu một đại lý bất kỳ AI có đủ điều kiện chuyển sang nhãn wt cho chuyến bay FI tại trạng thái S hay không Nếu nhãn của AI tương ứng với FI tại trạng thái S là rm (nghĩa là đại lý chưa có nhu cầu sử dụng chuyến bay FI), phương thức c-want sẽ trả về giá trị true Ngược lại, nếu không, phương thức sẽ trả về giá trị false Đầu vào của c-want bao gồm ba tham số với các kiểu dữ liệu tương ứng.
ATASys, FId, AId Đầu ra của phương thức c-want có kiểu dữ liệu logic Hình 4.2e mô tả chi tiết phương thức c-want trong mô-đun ATA.
17: op c-want : ATASys FId AId -> Bool {strat: (0 1)} 18: eq c-want(S,FI,AI) = (pc(S,FI,AI) = rm)
Hình 4.2e: Đặc tả chi tiết phương thức c-want
Nếu một đại lý bất kỳ AI chưa có nhu cầu sử dụng một chuyến bay bất kỳ
Sau khi thực hiện lệnh "want" tại trạng thái S với chuyến bay FI, nhãn của AJ ở trạng thái mới "want(S, FI, AI)" sẽ là wt nếu AI bằng AJ Ngược lại, nhãn của AJ sẽ không thay đổi so với trạng thái trước đó, chỉ có nhãn của AI là thay đổi.
Nếu phương thức kiểm tra điều kiện c-want của AI đối với chuyến bay FI ở trạng thái S trả về giá trị False, điều này có nghĩa là AI không đủ điều kiện để thực hiện lệnh want cho chuyến bay FI tại trạng thái S Sau khi thực hiện lệnh want, trạng thái của hệ thống sẽ không thay đổi so với trước đó.
4.2f là phần đặc tả tiếp theo của mô-đun ATA, đặc tả chi tiết cho phương thức chuyển trạng thái want
19: ceq pc(want(S,FI,AI),FI,AJ) = (if AI = AJ then wt else pc(S,FI,AJ) fi) if c-want(S,FI,AI)
20: ceq want(S,FI,AI) = S if not c-want(S,FI,AI)
Hình 4.2f: Đặc tả chi tiết phương thức want
Nếu một đại lý AI chưa sử dụng chuyến bay FI, sau khi thực hiện lệnh want tài trạng thái S, AI sẽ được đưa vào cuối hàng đợi tương ứng với chuyến bay FI tại trạng thái S đó Phần đặc tả tiếp theo của mô-đun ATA cung cấp chi tiết cho phương thức queue như hình 4.2g.
21: ceq queue(want(S,FI,AI),FI) = put(AI,queue(S,FI)) if c-want(S,FI,AI)
Hình 4.2g: Đặc tả chi tiết phương thức queue
Chứng minh tính đúng đắn của hệ thống
Để đảm bảo tính chính xác trong việc sử dụng chung các chuyến bay của hệ thống, cần xây dựng mô-đun INV nhằm kiểm chứng rằng không xảy ra xung đột trong quá trình thực thi.
3: pred inv : ATASys FId AId AId
op inv : ATASys FId AId AId -> Bool
7: eq inv(S,FI,AI,AJ) = (((pc(S,FI,AI) = cs) and(pc(S,FI,AJ) = cs)) implies AI = AJ)
Hình 4.8: Đặc tả mô-đun INV
Chi tiết của mô-đun INV như sau:
Mô-đun INV kế thừa từ mô-đun ATA với kiểu protecting, định nghĩa thuộc tính bất invariant inv là một phép toán với bốn tham số đầu vào: không gian trạng thái ATASys, chuyến bay FId, và hai đại lý AId Đầu ra của inv là kiểu logic Bool Các biến S, AI, AJ, và FI được khai báo làm tham số cho phép toán inv Ý nghĩa của thuộc tính bất invariant inv được thể hiện qua biểu thức logic, trong đó nếu hai đại lý khác nhau AI và AJ cùng sử dụng một chuyến bay FI tại một trạng thái S nhất định, thì thuộc tính inv sẽ có giá trị false Để chứng minh rằng giá trị của thuộc tính inv luôn là true tại mọi trạng thái S trong không gian trạng thái ATASys, nghĩa là không xảy ra xung đột giữa các đại lý trong việc sử dụng chuyến bay, cần xây dựng mô-đun ISTEP để áp dụng tư tưởng quy nạp của CafeOBJ.
s được hiểu là trạng thái hiện tại
s' được hiểu là trạng thái tiếp theo của s
Bước chứng minh quy nạp
7: eq istep(AI,AJ) = inv(s,FI,AI,AJ) implies inv(s',FI,AI,AJ)
Hình 4.9: Đặc tả mô-đun ISTEP
Bước cơ sở: Chứng minh thuộc tính bất biến inv thỏa mãn tại trạng thái khởi tạo init của hệ thống
4: red inv(init,Fi,Ai,Aj)
Hình 4.10: Chứng minh tính đúng đắn của thuộc tính bất biến inv tại trạng thái khởi tạo init của hệ thống
Kết quả của lệnh inv là true, cho thấy thuộc tính bất biến inv được thỏa mãn trong trạng thái khởi tạo init của hệ thống.
Có thể thực hiện các bước rút gọn để chứng minh một biểu thức logic trong CafeOBJ, hoặc tự tay thực hiện từng bước rút gọn để đạt được kết quả cuối cùng.
Để chứng minh cho trường hợp tổng quát với phương thức chuyển trạng thái "want", cần khai báo thêm một đại lý thứ ba là Ak, bên cạnh Ai và Aj đã được sử dụng trong trạng thái khởi tạo "init".
Việc sử dụng đại lý thứ ba Ak giúp chia nhỏ công đoạn chứng minh thành các phần nhỏ hơn Bằng cách chứng minh từng phần nhỏ này, ta có thể xác nhận rằng toàn bộ công đoạn ban đầu cũng đã được chứng minh đúng.
Khai báo các toán tử
4: ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s,
ta khai báo như sau:
5: eq inv(s,FI:FId,AI:AId,AJ:AId) = true
Kiểm tra tính đúng đắn
7: red inv(s',Fi,Ai,Aj)
Hình 4.11: Chứng minh tính đúng đắn của thuộc tính bất biến inv trong trường hợp tổng quát với phương thức chuyển trạng thái want
Kết quả thực hiện lệnh trên tạo ra một biểu thức logic, và để rút gọn biểu thức này, cần bổ sung thêm tri thức và các luật Khi thực hiện lệnh want với đại lý Ak, cần kiểm tra điều kiện c-want của Ak, đồng thời Ak có thể là Ai hoặc không Vì vậy, chúng ta cần xây dựng bảng phân tách các trường hợp tương ứng.
Các trường hợp cần chứng minh
Các trường hợp của c-want
Các trường hợp quan hệ giữa Ai và Ak
Các trường hợp quan hệ giữa Aj và
3 not (Ai = Ak) Aj = Ak
Hình 4.12: Bảng phân tách các trường hợp cần chứng minh cho thuộc tính bất biến inv với phương thức chuyển trạng thái want
Nếu tất cả các trường hợp cần chứng minh đều đúng, thì tính chính xác của thuộc tính bất biến inv trong phương thức chuyển trạng thái want sẽ được xác nhận.
Trường hợp c-want(s,Fi,Ak), Ai = Ak, Aj = Ak:
C-want(s,Fi,Ak) được định nghĩa là c-want(s,Fi,Ak) = true, với điều kiện pc(s,Fi,Ak) phải bằng rm Do đó, trong CafeOBJ, chúng ta khai báo luật: eq pc(s,Fi,Ak) = rm.
- Ai = Ak nghĩa là (Ai = Ak) = true Do đó, ta khai báo trong CafeOBJ luật sau : eq Ai = Ak
- Aj = Ak nghĩa là (Aj = Ak) = true Do đó, ta khai báo trong CafeOBJ luật sau : eq Aj = Ak
Hình 4.13 là phần đặc tả cho trường hợp này trong CafeOBJ để kiểm chứng thuộc tính bất biến inv open INV
Khai báo các hằng bất kỳ ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-want(s,Fi,Ak) eq pc(s,Fi,Ak) = rm
Ai = Ak eq Ai = Ak
Aj = Ak eq Aj = Ak
Trạng thái tiếp theo của s eq s' = want(s,Fi,Ak)
Kiểm tra tính đúng đắn red inv(s',Fi,Ai,Aj) close
Hình 4.13: Kiểm chứng trường hợp c-want(s,Fi,Ak), Ai = Ak, Aj = Ak
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp này được kiểm chứng là đúng
Trường hợp c-want(s,Fi,Ak), Ai = Ak, not (Aj = Ak) :
- eq pc(s,Fi,Ak) = rm
Hình 4.14 là phần đặc tả cho trường hợp này trong CafeOBJ: open INV ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-want(s,Fi,Ak) eq pc(s,Fi,Ak) = rm
Ai = Ak eq Ai = Ak
not (Aj = Ak) eq (Aj = Ak) = false eq s' = want(s,Fi,Ak)
Kiểm tra tính đúng đắn red inv(s',Fi,Ai,Aj) close
Hình 4.14: Kiểm chứng trường hợp c-want(s,Fi,Ak), Ai = Ak, not (Aj = Ak)
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp này được kiểm chứng là đúng
Trường hợp c-want(s,Fi,Ak), not (Ai = Ak), Aj = Ak :
- eq pc(s,Fi,Ak) = rm
- eq (Ai = Ak) = false open INV
Khai báo các hằng bất kỳ ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-want(s,Fi,Ak) eq pc(s,Fi,Ak) = rm
Aj = Ak eq Aj = Ak
not (Ai = Ak) eq (Ai = Ak) = false
Trạng thái tiếp theo của s eq s' = want(s,Fi,Ak)
Kiểm tra tính đúng đắn red inv(s',Fi,Ai,Aj) close
Hình 4.15: Kiểm chứng trường hợp c-want(s,Fi,Ak), not (Ai = Ak), Aj = Ak
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp này được kiểm chứng là đúng
Trường hợp c-want(s,Fi,Ak), not (Ai = Ak), not (Aj = Ak) :
- eq pc(s,Fi,Ak) = rm
Hình 4.16 là phần đặc tả cho trường hợp này trong CafeOBJ để kiểm chứng thuộc tính bất biến inv open INV
Khai báo các hằng bất kỳ ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-want(s,Fi,Ak) eq pc(s,Fi,Ak) = rm
not (Ai = Ak) eq (Ai = Ak) = false
not (Aj = Ak) eq (Aj = Ak) = false
Trạng thái tiếp theo của s eq s' = want(s,Fi,Ak)
Kiểm tra tính đúng đắn red inv(s',Fi,Ai,Aj) close
Hình 4.16: Trường hợp c-want(s,Fi,Ak), not (Ai = Ak), not (Aj = Ak) Kết quả thực hiện đoạn lệnh trên trả về một biểu thức logic như sau:
((((pc(s,Fi,Ai) = cs) and (pc(s,Fi,Aj) = cs)) and (Ai
= Aj)) xor (((pc(s,Fi,Ai) = cs) and (pc(s,Fi,Aj) cs)) xor true))
Hình 4.17: Kết quả trường hợp c-want(s,Fi,Ak), not (Ai = Ak), not (Aj = Ak)
Biểu thức logic inv(s, Fi, Ai, Aj) trả về giá trị true, tương đương với inv(s, FI:FId, AI:AId, AJ:AId) = true Do đó, inv(s, Fi, Ai, Aj) sẽ cho kết quả true khi Fi và Ai được xác định.
Aj là những hằng số cụ thể được thay vào
Từ suy luận trên, ta có thể biến đổi đặc tả của trường hợp này như sau: open INV
Khai báo các hằng bất kỳ ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-want(s,Fi,Ak) eq pc(s,Fi,Ak) = rm
not (Ai = Ak) eq (Ai = Ak) = false
not (Aj = Ak) eq (Aj = Ak) = false
Trạng thái tiếp theo của s eq s' = want(s,Fi,Ak)
Kiểm tra tính đúng đắn red inv(s,Fi,Ai,Aj) implies inv(s',Fi,Ai,Aj) close
Hình 4.18: Kiểm chứng trường hợp c-want(s,Fi,Ak), not (Ai = Ak), not (Aj = Ak) sử dụng INST, TRANS, HIDE
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp này được kiểm chứng là đúng
Trường hợp not c-want(s,Fi,Ak) : not c-want(s,Fi,Ak) có nghĩa là c-want(s,Fi,Ak) = false Do đó, ta khai báo trong CafeOBJ luật: c-want(s,Fi,Ak) = false
Hình 4.19 là phần đặc tả cho trường hợp này trong CafeOBJ để kiểm chứng thuộc tính bất biến inv open INV
Khai báo các hằng bất kỳ ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Giả sử inv đúng với trạng thái s eq inv(s,FI:FId,AI:AId,AJ:AId) = true
not c-want(s,Fi,Ak) eq c-want(s,Fi,Ak) = false
Trạng thái tiếp theo của s eq s' = want(s,Fi,Ak)
Kiểm tra tính đúng đắn red inv(s',Fi,Ai,Aj) close
Hình 4.19: Kiểm chứng trường hợp not c-want(s,Fi,Ak)
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp này đã được kiểm chứng là đúng
Tính đúng đắn của thuộc tính bất biến INV với phương thức chuyển trạng thái want đã được chứng minh là chính xác trong tất cả các trường hợp có thể xảy ra.
Tương tự ta chứng minh tính đúng đắn của thuộc tính inv với phương thức chuyển tạng thái try
- c-try(s,Fi,Ak) thỏa mãn, có nghĩa là pc(s,Fi,Ak) = wt và top(queue(s,Fi))
= Ak Do đó, ta khai báo các luật trong CafeOBJ là : eq pc(s,Fi,Ak) = wt , eq top(queue(s,Fi)) = Ak
- Ai = Ak thỏa mãn, có nghĩa là (Ai = Ak) = true, khai báo trong CafeOBJ luật: eq Ai = Ak
Trong CafeOBJ, khi Aj bằng Ak (Aj = Ak), điều này được xác định là đúng (true) và được khai báo bằng luật eq Aj = Ak Đặc tả trường hợp 1 của phương thức try trong CafeOBJ được thực hiện bằng cách mở INV.
Khai báo các hằng bất kỳ ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Khai báo các giả thiết eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-try(s,Fi,Ak) eq pc(s,Fi,Ak) = wt eq top(queue(s,Fi)) = Ak
Ai = Ak eq Ai = Ak
Aj = Ak eq Aj = Ak
Trạng thái kế tiếp của s eq s' = try(s,Fi,Ak)
Rút gọn để kiểm chứng red inv(s',Fi,Ai,Aj) close
Hình 4.20: Kiểm chứng trường hợp 1 của phương thức try
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp 1 của phương thức try được kiểm chứng là đúng
- c-try(s,Fi,Ak) thỏa mãn, có nghĩa là pc(s,Fi,Ak) = wt và top(queue(s,Fi))
= Ak Do đó, ta khai báo các luật trong CafeOBJ là : eq pc(s,Fi,Ak) = wt , eq top(queue(s,Fi)) = Ak
- Ai = Ak thỏa mãn, có nghĩa là (Ai = Ak) = true, khai báo trong CafeOBJ luật: eq Ai = Ak
Trong CafeOBJ, quy tắc không bằng nhau được thể hiện qua biểu thức (Aj = Ak) = false, với khai báo eq (Aj = Ak) = false Điều này áp dụng cho trường hợp 2 của phương thức try, cụ thể là mở INV.
Khai báo các hằng tùy ý ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Khai báo các giả thiết eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-try(s,Fi,Ak) eq pc(s,Fi,Ak) = wt eq top(queue(s,Fi)) = Ak
Ai = Ak eq Ai = Ak
~(Aj = Ak) eq (Aj = Ak) = false
Định nghĩa trạng thái kế tiếp của s eq s' = try(s,Fi,Ak)
Thực hiện rút gọn để kiểm chứng red inv(s',Fi,Ai,Aj) close
Hình 4.21: Kiểm chứng try với trường hợp 2
Kết quả của đoạn lệnh trên trả về một biểu thức logic:
((pc(s,Fi,Aj) = cs) xor true):Bool
Để chứng minh biểu thức logic trả về giá trị true, cần khai báo một bổ đề bổ sung, cụ thể là bổ đề lemma1 trong mô-đun LEMMA1.
Khai báo một bất biến với cách tiếp cận khác op lemma1 : ATASys FId AId -> Bool
Khai báo các biến trong CafeOBJ var S : ATASys var AI : AId var FI : FId
Định nghĩa bất biến với cách tiếp cận mới eq lemma1(S,FI,AI) = (pc(S,FI,AI) = cs implies top(queue(S,FI)) = AI)
Hình 4.23: Phần đặc tả của bổ đề lemma1
Phân tích từ lemma1 ta thấy một bổ đề đúng đắn như sau:
((pc(s,Fi,Aj) = cs) = false
Bổ đề đúng đắn được rút ra từ lemma1 đã được áp dụng vào đặc tả kiểm chứng try trong trường hợp 2, dẫn đến đặc tả như sau: open INV.
Khai báo các hằng tùy ý ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Khai báo các giả thiết eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-try(s,Fi,Ak) eq pc(s,Fi,Ak) = wt eq top(queue(s,Fi)) = Ak
Ai = Ak eq Ai = Ak
~(Aj = Ak) eq (Aj = Ak) = false
Thêm bổ đề eq (pc(s,Fi,Aj) = cs ) = false
Định nghĩa trạng thái kế tiếp của s eq s' = try(s,Fi,Ak)
Thực hiện rút gọn để kiểm chứng red inv(s',Fi,Ai,Aj) close
Hình 4.25: Kiểm chứng try với trường hợp 2 sau khi áp dụng bổ đề đúng đắn được rút ra từ lemma1
Kết quả thực hiện đoạn lệnh trên trả về giá trị true Vậy trường hợp 2 được kiểm chứng là đúng
Trường hợp 3: c-try(s,Fi,Ak) not (Ai = Ak)
Aj = Ak Đặc tả: open INV
Khai báo các hằng tùy ý ops s s' : -> ATASys op Fi : -> FId ops Ai Aj Ak : -> AId
Khai báo các giả thiết eq inv(s,FI:FId,AI:AId,AJ:AId) = true
c-try(s,Fi,Ak) eq pc(s,Fi,Ak) = wt eq top(queue(s,Fi)) = Ak
not (Ai = Ak) eq (Ai = Ak) = false
(Aj = Ak) eq Aj = Ak
Định nghĩa trạng thái kế tiếp của s eq s' = try(s,Fi,Ak)
Thực hiện rút gọn để kiểm chứng red inv(s',Fi,Ai,Aj) close
Hình 4.26: Kiểm chứng try với trường hợp 3
Kết quả thực hiện đoạn lệnh trên trả về một biểu thức logic như sau:
(pc(s,Fi,Ai) = cs) xor true
Hình 4.27: Kết quả trả về của đoạn lệnh kiểm chứng try với trường hợp 3
Phân tích từ bổ đề lemma1 đã khai báo ở trên ta thấy một bổ đề đúng đắn như sau:
((pc(s,Fi,Aj) = cs) = false
Hình 4.28: Bổ đề đúng đắn được rút ra từ bổ đề lemma1
Thêm bổ đề này vào đặc tả và thực hiện đoạn lệnh ta thấy kết quả trả về true Vậy trường hợp 3 được kiểm chứng là đúng
