TRƯỜNG ………………….
KHOA……………………….
----------

Báo cáo tốt nghiệp
Đề tài:
Phương pháp kiểm chứng tính đúng đắn của một chương
trình Java đa luồng thơng qua sử dụng logic Hoare

-1-


TĨM TẮT KHĨA LUẬN
Có rất nhiều phương pháp để kiểm chứng tính đúng đắn của một chương trình Java đa
luồng. Một trong các phương pháp đó là sử dụng logic Hoare. Kiểm chứng tính đúng
đắn của một chương trình Java đa luồng sử dụng logic Hoare yêu cầu ta cần phải
chứng minh một chương trình được bổ sung và chú thích dưới sự thi hành của các lệnh
phải thỏa mãn: Nếu bước tính tốn thi hành một phép gán, thì ta sử dụng các điều kiện
tính đúng đắn cục bộ để chứng minh tính quy nạp của sự thi hành các thuộc tính của
cấu hình cục bộ, và kiểm tra tính khơng có can thiệp đối với tất cả các cấu hình cục bộ
khác và các bất biến lớp khác. Đối với giao tiếp, tính bất biến đối với thi hành các đối
tác và bất biến toàn cục được chứng tỏ thông qua kiểm tra sự hợp tác đối với giao tiếp.
Giao tiếp với chính nó khơng ảnh hưởng trạng thái tồn cục; tính bất biến của các
thuộc tính cịn lại dưới các quan sát tương ứng được chứng tỏ thơng qua kiểm tra tính
khơng có can thiệp. Cuối cùng, đối với tạo đối tượng, tính bất biến đối với bất biến
tồn cục, tạo cấu hình cục bộ, bất biến lớp của đối tượng được tạo được đảm bảo các
điều kiện của kiểm tra hợp tác đối với tạo đối tượng; tất cả các thuộc tính khác được
chứng tỏ là bất biến thơng qua sử dụng kiểm tra tính khơng có can thiệp.

-2-

MỤC LỤC
TÓM TẮT KHÓA LUẬN................................................................................................- 1 MỞ ĐẦU ..........................................................................................................................- 4 CHƯƠNG 1. LOGIC HOARE ........................................................................................- 6 1.1. Logic vị từ..................................................................................................................- 6 1.2. Các tiên đề của Logic Hoare .....................................................................................- 9 1.2.1. Các công thức đúng cú pháp cho chứng minh chương trình................................- 9 1.2.2. Tiên đề của phép gán............................................................................................- 10 1.2.3. Các quy tắc bổ sung..............................................................................................- 10 CHƯƠNG 2. NGÔN NGỮ TUẦN TỰ ..........................................................................- 12 2.1. Cú pháp ...................................................................................................................- 13 2.2. Ngữ nghĩa ................................................................................................................- 16 2.2.1. Trạng thái và các cấu hình...................................................................................- 16 2.2.2. Các ngữ nghĩa tốn tử..........................................................................................- 18 2.3. Ngôn ngữ khẳng định..............................................................................................- 20 2.3.1. Cú pháp ................................................................................................................- 20 2.3.2. Ngữ nghĩa..............................................................................................................- 21 2.4. Hệ chứng minh ........................................................................................................- 25 2.4.1. Phác thảo chứng minh..........................................................................................- 26 2.4.2. Kiểm chứng các điều kiện ....................................................................................- 31 CHƯƠNG 3. NGÔN NGỮ TƯƠNG TRANH .................... Error! Bookmark not defined.
3.1. Cú pháp ...................................................................................................................- 42 3.2. Ngữ nghĩa ................................................................................................................- 42 3.3. Hệ chứng minh ........................................................................................................- 43 3.3.1. Phác thảo chứng minh..........................................................................................- 43 3.3.2. Kiểm chứng các điều kiện ....................................................................................- 43 CHƯƠNG 4. BỘ ĐIỀU PHỐI LẶP LẠI............................. Error! Bookmark not defined.
4.1. Cú pháp ...................................................................................................................- 47 4.2. Ngữ nghĩa ................................................................................................................- 47 4.3. Hệ chứng minh……………………………………………………………………….- 484.3.1. Phác thảo chứng minh..........................................................................................- 49 4.3.2. Kiểm chứng các điều kiện ....................................................................................- 51 CHƯƠNG 5. PHÉP TOÁN ĐIỀU KIỆN TRƯỚC YẾU NHẤT..................................- 53 5.1. Các phép toán thay thế............................................................................................- 54 5.2. Kiểm chứng các điều kiện…………………………………………………………...- 54CHƯƠNG 6. TÍNH ĐÚNG ĐẮN......................................... Error! Bookmark not defined.
6.1. Tính đúng đắn .........................................................................................................- 59 KẾT LUẬN………………………………………………………………………………..- 62TÀI LIỆU THAM KHẢO………………………………………………………………..- 63-

-3-


MỞ ĐẦU

Yêu cầu của người dùng đối với một phần mềm ngày nay là khơng những nó phải có
giao diện đẹp, tốc độ xử lý dữ liệu nhanh, tốc độ phản ứng của chương trình với người
dùng cũng là một u cầu khơng thể bỏ qua. Một chương trình u cầu vừa có giao
diện đẹp, vừa xử lý nhanh chạy trên một máy cấu hình bình thường thì cần có một cơ
chế để quản lý cấp phát tài nguyên của máy một cách phù hợp. Và cơ chế quản lý đa
luồng chính là một giải pháp cho các yêu cầu trên. Ngơn ngữ lập trình Java là một
ngơn ngữ lập trình bậc cao hỗ trợ rất mạnh cho lập trình đa luồng, được sử dụng nhiều
trong các hệ thống lớn cũng như trong các phần mềm có quy mơ vừa và nhỏ.
Trong các hệ thống lớn, chỉ một lỗi rất nhỏ cũng có thể dẫn tới những kết quả tai
hại, hoặc thậm chí là phá hủy hệ thống. Do đó ta thấy được tính quan trọng đối với
việc kiểm chứng tính đúng đắn của một chương trình. Việc kiểm chứng tính đúng đắn
của một chương trình Java đa luồng là không thể thiếu được trong việc phát triển hệ
thống. Ta cần có một phương pháp kiểm chứng tính đúng đắn của một chương trình
Java đa luồng. Đó chính là phương pháp thông qua sử dụng logic Hoare.
Logic Hoare là một hệ thống hình thức được phát triển bởi các nhà khoa học máy
tính Anh C.A.R.Hoare, và về sau được cải tiến bởi Hoare và các nhà nghiên cứu khác.
Mục đích của hệ thống này là cung cấp một tập các quy tắc logic để lý luận về tính
đúng đắn của các chương trình máy tính với tính chính xác của các logic toán học.

Logic Hoare là cơ sở để định nghĩa tính đúng đắn của hệ thống.
Trong khóa luận tốt nghiệp này em sẽ trình bày về phương pháp kiểm chứng tính
đúng đắn của một chương trình Java đa luồng thơng qua sử dụng logic Hoare.
Khóa luận sẽ có sáu chương với nội dung chính như sau:
 Chương 1: Logic Hoare
 Chương 2: Ngôn ngữ tuần tự

-4-


 Chương 3: Ngôn ngữ tương tranh
 Chương 4: Bộ điều phối lặp lại
 Chương 5: Phép toán trước yếu nhất
 Chương 6: Tính đúng đắn

Tuy nhiên do cịn nhiều hạn chế về thời gian cũng như kiến thức của bản thân,
khóa luận này khơng thể tránh khỏi những thiếu sót. Em rất mong nhận được sự quan
tâm góp ý của các thầy, cô giáo cũng như các anh, chị và các bạn, những người quan
tâm đến vấn đề này.
Em xin chân thành cảm ơn thầy giáo, tiến sỹ Đặng Văn Hưng, người đã hướng
dẫn trực tiếp, động viên và giúp đỡ em rất nhiều để hồn thành khóa luận này.
Cuối cùng, em xin bày tỏ lòng biết ơn sâu sắc tới gia đình, bạn bè, các thầy cơ
giáo, những người đã quan tâm, giúp đỡ em rất nhiều trong suốt những năm ngồi trên
ghế nhà trường.

Hà Nội, tháng 5 năm 2009
Sinh viên
LÊ VĂN VIỄN

-5-



CHƯƠNG 1. LOGIC HOARE

1.1. Logic vị từ
Định nghĩa: Vị từ là một hàm nhận một giá trị Bool.
Một vị từ thực sự là một giá trị logic được biểu hiện bằng tham số. Nó có thể đúng với
một số đối số, và sai với một số đối số khác. Chẳng hạn x > 0 là một vị từ với một đối
số, ta có thể đặt tên nó là gt0(x). Do vậy mà gt0(5) là đúng và gt0(0) là sai.
Định nghĩa: Các thành phần của logic vị từ wffs gồm có các thành phần sau:
• Các định danh biến – một tập (thường là vô hạn) của các tên biến, thường
là x , x 1 , x 2 , ..., y , y 1 , y 2 , ...
• Các định danh hằng – một tập (hữu hạn, vô hạn, hoặc rỗng) của các tên hằng,
thường là a , a 1 , a 2 , ..., b , b1 , b 2 ...
• Các định danh vị từ – một tập (không rỗng) của các tên vị từ, thường
là p , p 1 , p 2 , ..., q , q 1 , q 2 ...
•

Các

định

danh

hàm

–

một


tập

các

tên

hàm,

thường

là f , f 1 , f 2 , ..., g , g 1 , g 2 , ...
Mỗi định danh hàm và định vị từ có một số cố định của các đối số mà nó chấp nhận là
arity.
Định nghĩa: Các tốn hạng của logic vị từ được định nghĩa một cách đệ quy như sau:
(i) các tên biến và các tên hằng là toán hạng, và
(ii) nếu t1 , ... , tk là các tốn hạng và f là một tên hàm có số các đối số cố định là k,
thì f t1 , t 2 , ..., tk  là một toán hạng

-6-


Một tốn hạng khơng chứa các biến được gọi là toán hạng cơ sở.
Định nghĩa: nếu t1 , ... , tk là các tốn hạng và vị từ p có số của các đối số cố định là k,
thì p t1 , t 2 , ..., tk  là một cơng thức ngun tử của logic vị từ.
Các phép tốn logic thêm vào trong logic vị từ là lượng hóa phổ biến  x đọc là
với mọi x, và lượng hóa tồn tại,  x đọc là tồn tại x. Trong sơ đồ ưu tiên để tránh các
dấu ngoặc trong các cơng thức,  có độ ưu tiên thấp nhất trong các liên kết.

Định nghĩa: Các công thức đúng ngữ pháp (wffs) của logic vị từ được định nghĩa đệ
quy như sau:

(i) mỗi công thức nguyên tử là một công thức đúng ngữ pháp wff, và
(ii) nếu  và  là wffs và x là một tên biến, thì mỗi công thức sau đây cũng là
một công thức đúng ngữ pháp:
• (  )
•    

• ( x. )

•    

• x. 

•    

•    

Hai phép tốn lượng hóa cung cấp một ngữ nghĩa không thể thiếu được để biểu
diễn các khẳng định về các kết quả chân lý của các vị từ. Sự thể hiện của mỗi phép
toán trong các phép toán logic phụ thuộc vào hiểu biết về khơng gian từ đó các giá trị
của các biến có thể được đưa ra. Nếu không gian này là hữu hạn, nói rằng c1 , c2 , ..., ck ,
thì những phép tốn logic mới này có thể được biểu thị bằng cách sử dụng các quan hệ
logic mệnh đề. Một cơng thức x.  thì tương đương với sự kết hợp của các công
thức đúng ngữ pháp đạt được bằng sự thay thế x bởi mỗi phần tử của các phần tử trong
khơng gian (ví dụ, x. p  x, y  p c1 , y   p c2 , y   ...  pck , y  ). Tương tự như vậy một
công thức x. tương đương với sự tách rời của các công thức wffs đạt được bởi thay
thế x bằng mỗi phần tử của các phần tử của khơng gian (ví dụ
x. p  x , y  p c1 , y   pc2 , y   ...  p ck , y  ).

Các phép tốn lượng hóa này u cầu ta phân biệt cách sử dụng của các biến.
Chẳng hạn, cơng thức p(x) có một tham biến x, và nó có thể đúng với một số giá trị và

sai với một số giá trị khác. Tuy nhiên, công thức x. p( x ) thực sự khơng có tham biến

-7-


và thể hiện một giá trị duy nhất – giá trị x được gọi là biên trong trường hợp trước và
tự do trong trường hợp sau. Nó minh họa hai vai trò khác nhau đối với các biến trong
biểu thức đúng khn dạng logic mệnh đề do đó phải phân biệt cẩn thận.
Định nghĩa: Các xuất hiện bị chặn của các biến trong x. là các xuất hiện bị chặn
của các biến trong  , cộng thêm tất các xuất hiện của x trong  ,  được gọi là phạm
vi của lượng hóa. Tất cả các xuất hiện của biến mà không bị chặn là các biến tự do.
Tương tự định nghĩa áp dụng cho x.  . Một cơng thức đúng ngữ pháp wff được gọi
là đóng nếu nó khơng có các xuất hiện của biến tự do.
Định nghĩa: Một thể hiện i gồm có
(i) Một tập D không rỗng – miền (hoặc không gian của các giá trị)
(ii) Một phép gán  của
• mỗi tên vị từ n đối số thành một quan hệ n vị trí trong D,
• mỗi tên hàm n đối số thành một hàm n vị trí trong D,
• mỗi định danh hằng thành một phần tử của D.
Ta viết i = D,  
Một thể hiện là một toán hạng thể hiện nếu D là tất cả các toán hạng, và các
phép gán đối với mỗi tên hàm là toán hạng khởi tạo tương ứng,
  f t1 ,..., tk   f t1 ,..., tk  .

Định nghĩa: Một thể hiện được cho i = D,   , một biến gán (hoặc trạng thái)  là
hàm trong tập các biến V,  : V  D. Phép gán được mở rộng một cách đệ quy để
mang một giá trị cho tất cả các tốn hạng và các cơng thức,
(i) đối với các tốn hạng
• với biến x, val ( x )   x  , và đối với hằng c, val (c)   c  ,
• với một toán hạng phức hợp val ( f ( t 1 ,..., t k ))   ( f )( val ( t1 ),..., val ( t k ))

(ii) đối với các cơng thức
• đối với một cơng thức ngun tử val ( p(t1 ,..., t k )   ( p )(val (t1 ),..., val (tk ))
• đối với các công thức phức hợp
val ( )  val ( )

-8-


val  (   )  val  ( )  val  (  )
val (   )  val ( )  val (  )
val (   )  val ( )  val (  )
val (   )  val ( )  val (  )

val x.   true nếu val '    true đối với mỗi  ' trong đó  '  y     y  đối với
y  x , false nếu ngược lại.

val x.   true nếu val '    true đối với mỗi  ' trong đó  '  y     y  đối với
y  x , = false nếu ngược lại.

Hai định nghĩa cuối cùng này biểu thị rằng, cho một thể hiện và một trạng thái,
chỉ có một giá trị duy nhất được quyết định cho mỗi toán hạng và mỗi cơng thức bởi
việc ước lượng mỗi phép tốn logic. Điều này cung cấp các giá trị đúng ta sử dụng
phân loại các công thức.
Định nghĩa: Cho  là một biểu thức hợp khuân dạng wff, i là một thể hiện, và  là
một trạng thái. Thì  thỏa mãn  dưới i, i |  nếu val ( ) = true. Biểu thức hợp
khuân dạng  là đúng trên i, i |  , nếu mọi trạng thái thỏa mãn  dưới i, và i được
gọi là mô hình của  ,  là sai trên i nếu khơng có trạng thái nào thỏa mãn  dưới i.
Một thể hiện được gọi là mơ hình của một tập các biểu thức hợp khn dạng nếu nó là
mơ hình của từng biểu thức hợp khuân dạng wff trong tập, và nếu nó là một thể hiện
tốn hạng, thì nó được gọi là một mơ hình tốn hạng.

Định nghĩa: Một công thức đúng ngữ pháp wff là đúng logic (công thức hằng đúng)
nếu nó đúng trên mọi thể hiện, có thể thỏa mãn nếu tồn tại một thể hiện và trạng thái
thỏa mãn nó, và ngược lại nếu nó là không thể thỏa mãn.
Định nghĩa: Một công thức đúng ngữ pháp wff là một hệ quả logic của một tập các
công thức đúng ngữ pháp  ,  |  , nếu mọi thể hiện và trạng thái thỏa mãn mỗi
   ,  và  là tương đương logic,    nếu với mọi thể hiện và trạng thái  ,
val ( )  val (  )

1.2. Các tiên đề của Logic Hoare
1.2.1. Các công thức đúng cú pháp cho chứng minh chương trình

-9-


Các công thức ta viết sẽ xác nhận các thuộc tính của các chương trình (các đoạn
chương trình thực sự). Do vậy, các công thức phải bao gồm các xác nhận và chương
trình tới cơng thức mà nó gắn liền. Các xác nhận chương trình (wffs) có dạng

 P   
gồm 3 thành phần:
• P là một đoạn chương trình - một lệnh (có thể phức hợp), và
•  và  là các công thức logic vị từ sử dụng các tên biến và hàm/thao tác của
chương trình, các ký hiệu {, } là các siêu ký hiệu được sử dụng để biểu thị bắt đầu và
kết thúc của các công thức logic vị từ, và không nên hiểu như là các ký hiệu trong
ngơn ngữ lập trình. Cơng thức logic  được gọi là điều kiện trước, và  được gọi là
điều kiện sau.
1.2.2. Tiên đề của phép gán
Ta giả thiết rằng X :  biểu thị một lệnh gán, trong đó X là một biến và  là một
biểu thức thích hợp. Tiên đề của phép gán nằm dưới hệ thống logic để chứng minh các
chương trình không điều kiện.

Tiên đề của phép gán:

| P X   X :   P 

trong đó P là một công thức logic vị từ, X là một biến,  là một biểu thức, và

P X    là công thức P với mỗi lần xuất hiện của X được thay thế bởi  . Một
bước chứng minh được xác nhận bởi việc chứng minh cú pháp công thức tương ứng.
Tuy nhiên ta không phân biệt các công thức mà chúng tương đương logic.
Độ mạnh của các công thức đúng ngữ pháp
Nếu P và Q là các công thức đúng ngữ pháp mà P  Q , thì ta nói rằng P là một xác
nhận mạnh hơn Q, và Q thì yếu hơn P. Một điều kiện mạnh hơn là một điều kiện mà
nhiều – ít hơn các giá trị thỏa mãn một điều kiện mạnh hơn.
1.2.3. Các quy tắc bổ sung
Tiên đề Skip

|  P  skip  P  với P là một công thức logic mệnh đề bất kỳ. Bằng trực
giác, vì skip khơng làm gì, nên cái gì đúng sau sự thực hiện của nó thì cũng như là cái
đã đúng trước đó.

- 10 -


Các quy tắc bổ trợ
Độ mạnh của điều kiện trước
Đó là quy tắc đầu tiên của các quy tắc suy luận trong hệ chứng minh chương trình. Ý
kiến một cách trực quan là nếu một xác nhận chương trình có thể được chứng minh, thì
điều kiện trước có thể được thay thế bởi bất kỳ công thức nào kéo theo nó.

|  Q    R , |  P  Q

P  R 
 là một đoạn chương trình bất kỳ.

Độ yếu của điều kiện sau
Đó là quy tắc tiếp theo của các quy tắc suy luận trong hệ thống chứng minh chương
trình. Ý kiến một cách trực quan là nếu một xác nhận chương trình có thể được chứng
minh, thì điều kiện sau có thể được thay thế bởi bất kỳ cơng thức nào nó kéo theo.

|   P   Q , |  Q  R
|  P   R 
 là một đoạn chương trình bất kỳ.

Quy tắc tuần tự

|  P

 C 1 Q , |  Q  C 2  R 
|  P  C 1 ; C 2 R 

Quy tắc điều kiện

|  P  B C 1 R , |  P   B C
|  P if B then C 1 else C 2 R

Quy tắc while

|  P 

|  P  B C P 
while B do C P   B 


- 11 -

R 

2


Tính đúng đắn: nếu

P S Qcó thể được chứng minh, thì điều tất nhiên là thực

hiện S từ một trạng thái thỏa mãn P sẽ chỉ kết thúc trong các trạng thái thỏa mãn Q.
Để mô tả rõ ràng về hệ chứng minh, ta trình bày hệ chứng minh tăng dần trong các
mức: Ta bắt đầu với một hệ chứng minh đối với ngôn ngữ con tuần tự của Java, cho
phép tạo đối tượng và thi hành phương thức động. Ở cấp này biểu thị cách để quản lý
các hoạt động của một luồng duy nhất. Trong mức thứ hai, ta cho phép thêm vào tạo
đối tượng động, dẫn tới sự thi hành đa luồng. Hệ chứng minh tương ứng mở rộng hệ
chứng minh trong ngôn ngữ Java seq với các điều kiện quản lý tạo luồng động và theo
các khía cạnh chen ngang vào. Cuối cùng, ta tích hợp kỹ thuật quản lý đồng bộ hóa
của Java. Quản lý đồng bộ hóa cho phép thi hành các loại trừ lẫn nhau trên đối tượng.

- 12 -


CHƯƠNG 2. NGÔN NGỮ TUẦN TỰ

2.1. Cú pháp
Đối với mỗi kiểu, miền giá trị tương ứng được trang bị với một tập hợp chuẩn các toán
tử với phần tử điển hình f. Mỗi tốn tử f có một kiểu duy nhất t1   t n  t và một thể

hiện cố định của f, trong đó các hằng là các tốn tử khơng có tham biến.
Đối với các biến, ta phân biệt định nghĩa giữa các biến thể hiện và các biến cục
bộ (tạm thời). Các biến thể hiện giữ trạng thái của một đối tượng và tồn tại suốt vòng
đời của đối tượng. Các biến cục bộ được cấp phát trong bộ nhớ Stack; chúng thể hiện
vai trò của các tham biến hình thức và các biến của các định nghĩa phương thức và chỉ
tồn tại trong sự thi hành của phương thức chứa chúng. Ta định nghĩa IVar là tập các
biến thể hiện với các phần tử x, và TVar là tập các biến cục bộ với các phần tử u, u’, v,
… Cho Var = IVar  TVar với phần tử điển hình y là tập các biến của chương trình.,
trong đó  là tốn tử tập hợp tách rời nhau.
Cú pháp trừu tượng:
e ::= x | u | this | null | f (e, …, e)
eret ::  | e

stm ::= x := e | u:= e | u:= new c
| u := e.m (e, …,e) | e.m (e, …,e)
|  | stm; stm | if e then stm else stm fi | while e do stm od …
meth ::= m (u, …, u) { stm; return eret }
methrun ::= run () { stm; return}

class ::= class c { meth … meth}
classmain ::= class c { meth … meth methrun }

prog ::= class … class classmain

- 13 -


Bên cạnh việc sử dụng biến cục bộ và biến thể hiện, các biểu thức e  Exp được
xây dựng từ biến tham chiếu đến chính nó this, tham chiếu rỗng là null, và từ các biểu
thức con sử dụng các toán tử được cho. Để hỗ trợ một giao diện rõ ràng giữa hành vi

bên trong và hành vi bên ngồi đối tượng, Java seq khơng cho phép các tham chiếu hạn
chế tới các biến thể hiện. Chú ý rằng tất cả các biểu thức của ngôn ngữ không có ảnh
hưởng, có nghĩa là, sự ước lượng của chúng khơng thay đổi trạng thái chương trình.
Chỉ có sự thi hành của các lệnh có ảnh hưởng tới trạng thái chương trình.
Các câu lệnh stm  Stm , cho phép các phép gán, tạo đối tượng, thi hành các
phương thức, và các cấu trúc điều khiển chuẩn như là dãy các lệnh hợp thành, các lệnh
điều kiện, và vòng lặp. Viết  cho câu lệnh rỗng.
Định nghĩa phương thức m u1 , ..., u n   stm; return eret bao gồm một phương thức
tên m, một danh sách các tham biến hình thức u1, ..., un , và thân phương thức của dạng
stm; return eret , có nghĩa là, ta yêu cầu rằng các thân của phương thức được kết thúc
bởi một câu lệnh trả về duy nhất có dạng return hoặc là return e, trả về sự điều khiển
và có thể trả về một giá trị. Nhiều khi ta bỏ qua các câu lệnh trả về mà không có giá trị
trả về trong các phương thức. Tập hợp Methc chứa các phương thức của lớp c. Ta ký
hiệu thân của phương thức m của lớp c là body m , c . Thỉnh thoảng ta đề cập rõ ràng đến
các kiểu của giá trị trả về và các tham số hình thức theo kiểu Java t m t1 u1 , ..., tn un 
Một lớp được định nghĩa bằng tên c của nó và các phương thức, trong đó tên của
các phương thức được đảm bảo khác nhau. Một chương trình là một tập hợp của các
định nghĩa lớp có các tên lớp khác nhau, trong đó một lớp chính classmain định nghĩa
bằng phương thức run của nó. Ta gọi thân của phương thức run của lớp chính là câu
lệnh chính của chương trình. Phương thức run khơng thể bị gọi.
Tập các biến thể hiện IVarc của một lớp c được cho một cách rõ ràng bởi các biến
thể hiện xuất hiện trong lớp; khai báo tập các biến cục bộ của phương thức cũng được
đưa ra một cách tương tự. Trong các ví dụ ta nhiều khi định nghĩa một cách rõ ràng
biến thể hiện và biến cục bộ theo kiểu Java: khai báo t y; trong các lớp bên ngoài các
định nghĩa phương thức khai báo y là một biến thể hiện của kiểu t của lớp, trong khi đó
nếu khai báo bên trong của một phương thức chỉ rõ y là một biến cục bộ.
Bên cạnh các rút gọn của các kiểu đã được đề cập, do các nguyên nhân kỹ thuật
đã dẫn tới các giới hạn sau: Ta yêu cầu các lệnh thi hành phương thức chỉ chứa các
biến cục bộ, nghĩa là, không có các biểu thức e0 , ..., en trong một lời gọi hàm


- 14 -


e0 .me1 , ..., en  chứa các biến thể hiện. Ngồi ra, các tham biến hình thức phải khơng

xuất hiện bên phía trái của các phép gán. Các giới hạn này kéo theo trong suốt quá
trình thi hành của một phương thức các giá trị của các tham biến thực sự và hình thức
khơng bị thay đổi. Cuối cùng, kết quả của việc tạo các đối tượng và thi hành các
phương thức có thể khơng bị gán cho các biến thể hiện. Hạn chế này cho phép một hệ
chứng minh với kiểm chứng các điều kiện riêng biệt cho tính khơng có can thiệp và
tính hợp tác.

class C {
int x1;

void m1 (C o) {
x1 := o.m2 (x1);
return
}

int m2 (int u) {
return u + 1
}
}

Sự biến đổi sau đây thỏa mãn các yêu cầu, nhưng chèn thêm các điểm điều khiển
trước và sau khi gọi phương thức trong m1:
class C {
int x1;
void m1 (C o) {

int u, v;
u := x1;

- 15 -


v := o.m2 (u);
x1 := v;
return
}

int m2 (Int u) {
return u + 1
}
}
2.2. Ngữ nghĩa
2.2.1. Trạng thái và các cấu hình
Cho Val t là các miền rời nhau với các kiểu khác nhau t. Đối với lớp có tên là c, các tập
rời nhau Val c với các phần tử điển hình là  ,  , ... biểu thị các tập vô hạn của các định
danh đối tượng. Giá trị của null trong kiểu c là null c  Val c . Nói chung ta chỉ viết null,
khi c là rõ ràng từ ngữ cảnh. Ta đinh nghĩa Val c null là Val c  null c , và tương ứng đối
với các kiểu hợp thành. Tập tất cả các giá trị có thể khơng null  t Val t được viết là
Val, và Val null biểu thị  t Val t null . Cho Init : Var  Val null là một hàm gán một giá trị
khởi tạo cho mỗi biến y  Var , nghĩa là, null, false, và 0, cho lớp, giá trị kiểu logic, và
các kiểu số nguyên, và tương ứng cho các kiểu hợp thành. Ta định nghĩa biến this
 Var , là một tham chiếu tới chính nó khơng phải trong miền của Init.

Cấu hình của một chương trình bao gồm tập hợp của các đối tượng đang tồn tại
cùng với giá trị của các biến thể hiện của chúng, và cấu hình của luồng đang thi hành.
Trước khi hình thức hóa các cấu hình tồn cục của một chương trình, ta định nghĩa các

trạng thái cục bộ và các cấu hình cục bộ.
Một trạng thái cục bộ    loc của sự thi hành một phương thức giữ giá trị của
các biến cục bộ của phương thức và được mơ hình hóa như là một hàm bộ phận của
kiểu TVar  Val null . Ta tham chiếu tới các trạng thái cục bộ của phương thức m của
lớp c bởi  m,c . Trạng thái cục bộ ban đầu  m,c init gán cho mỗi biến cục bộ u từ miền của
nó giá trị Init(u). Một cấu hình cục bộ  , , stm  của một phương thức của đối tượng

- 16 -


  null chỉ rõ, thêm vào trạng thái cục bộ  , điểm thi hành của nó được biểu diễn bởi

câu lệnh stm. Một cấu hình luồng  là một ngăn xếp của các cấu hình cục bộ

 0 ,  0 , stm0  1 ,  1 , stm1  …  n ,  n , stmn  , mô tả dãy của các sự thi hành phương thức
của luồng được cho. Ta viết  o   , , stm  có nghĩa là đẩy một cấu hình cục bộ mới
vào trong ngăn xếp.
Các đối tượng được mô tả đặc điểm bởi các trạng thái thể hiện  inst   inst của
kiểu IVar   this  Val null sao cho nó ở trong miền dom   inst  của  inst . Ta viết  c inst
để ký hiệu các trạng thái của các thể hiện của lớp c. Các ngữ nghĩa sẽ duy trì
 c inst  this   Val c bất biến. Trạng thái thể hiện ban đầu

c, init

inst

gán một giá trị từ

Val c tới this, và tới mỗi biến thể hiện x cịn lại của nó giá trị Init(x).


Một trạng thái toàn cục    của kiểu  c Val c 



inst

lưu trữ đối với mỗi

đối tượng đang tồn tại hiện thời, nghĩa là, một đối tượng đang thuộc về miền của  ,
trạng thái thể hiện của đối tượng. Tập các đối tượng đang tồn tại của kiểu c trong một
trạng thái  được cho bởi Val c   , và Val c null    Val c    null c   . Đối với các
kiểu còn lại, Val t   và Val null t   được định nghĩa tương ứng. Ta tham chiếu tới tập
t

 t Val t   bởi Val   ; Val null   biểu thị  t Val null   . Trạng thái thể hiện của một đối

tượng   Val c   được cho bởi    với thuộc tính bất biến   

 this  . Ta yêu cầu

rằng, một trạng thái toàn cục được cho, khơng có biến thể hiện nào trong bất kỳ các
đối tượng đang tồn tại nào tham chiếu tới một đối tượng không tồn tại, nghĩa là,
   x   Val null   cho tất cả các lớp c và các đối tượng   Val c   .

Một cấu hình tồn cục T ,  mơ tả các đối tượng hiện thời qua trạng thái toàn
cục  , tập T chứa cấu hình của luồng đang thi hành. Đối với các ngôn ngữ tương tranh
của các phần sau, T sẽ là một tập các cấu hình của tất cả các luồng đang thi hành hiện
thời. Tương ứng với giới hạn trong các trạng thái toàn cục, ta yêu cầu rằng các cấu
hình cục bộ   , , stm  trong T , 


chỉ tham chiếu tới các định danh đối tượng đang

tồn tại, nghĩa là,   Val   và  (u )  Val null   đối với tất cả các u từ miền của  .
Trong phần tiếp theo, ta viết

 , , stm   T nếu tồn tại một cấu hình cục bộ

 , , stm  trong một ngăn xếp của các ngăn xếp thi hành của T.

- 17 -


Hàm ngữ nghĩa

 _  _ , _ :  inst  loc    Exp Valnull 

ước lượng

trong ngữ cảnh của một trạng thái thể hiện cục bộ  inst ,   các biểu thức đang chứa
các biến từ dom   inst   dom    , dom (f) biểu thị miền của hàm f. Các biến thể hiện x
và các biến cục bộ u được ước lượng lần lượt là  inst  x  và  u  , biến this ước lượng là
 inst this  , và null có tham chiếu null như giá trị.

x  

inst

,

  inst  x 


u  

inst

,

  u 

this  

inst

,

  inst this

null  

inst

,

 null

 f  e1 , ..., en  

inst ,




 f e1 

 inst ,



, ...,en 

 inst ,



Ta biểu diễn bằng  u  v  trạng thái cục bộ gán giá trị v cho u;  inst x  v 
được định nghĩa một cách tương tự, trong đó  inst  . x  v  cho kết quả từ  bằng
cách gán v cho biến thể hiện x của đối tượng   Val   . Ta sử dụng những toán tử





này một cách tương tự cho các vector của các biến. Ta cũng sử dụng  y  v cho










các dãy biến bất kỳ;  inst  . y  v và   . y  v được định nghĩa tương tự. Cuối
cùng, đối với các trạng thái toàn cục,     inst  bằng với  trừ đi  ; trong trường
hợp   Val   , toán tử mở rộng tập các đối tượng đang tồn tại bởi  , có trạng thái
thể hiện của nó được khởi tạo cho  inst .
2.2.2. Các ngữ nghĩa tốn tử
Trước khi có một cái nhìn chặt chẽ về các quy tắc ngữ nghĩa cho phép biến đổi quan
hệ  , ta bắt đầu bằng định nghĩa về điểm vào của một chương trình. Cấu hình ban
đầu

T0 ,  0

của

dom  0    ,  0    inst

một
c, init

chương

trình

, và

T0  ,  init

this  

trong đó c là lớp chính, và   Val c là đối tượng ban đầu.


- 18 -



thỏa
run, c

mãn



, bodyrun, c ,


Ta gọi một cấu hình T , 
một tính tốn T0 ,  0   T , 

của một chương trình là có thể đạt được nếu tồn tại
sao cho T0 , 0 là cấu hình ban đầu của chương trình

và   là bao đóng bắc cầu phản thân của  . Một cấu hình cục bộ  , , stm   T được
cho phép trong T ,  , nếu nó có thể được thi hành, nghĩa là, nếu có một bước tính
tốn T ,   T ' ,  ' đang thi hành stm trong trạng thái cục bộ  và đối tượng  .



T    , , x: e; stm ,   T     , , stm,  .x   e 

  


T    , , u: e; stm ,   T    , u  e

  , 

  , 

, stm, 

  Val c \ Val    inst   c , init inst this     '      inst 
NEW
T    , , u : new c ; stm  ,   T     , u   , stm ,  '



m u  body   Methc

  e 0 

u  e 
    ,  , u : e .m e ; stm ,  

  , 

T

 Val c    '   init

m,c




  , 

CALL

0

T    , , receive u; stm   , ' , body , 



  , '



 ' '   u ret  eret 
RETURN
T     ,  , receive u ret ; stm    ,  ' , return eret  
T     ,  ' ' , stm , 

T   , , return ,   T   , ,, 

- 19 -

RETURN run



ASS loc


ASS inst


Các phép gán tới các biến thể hiện hoặc các biến cục bộ cập nhật trạng thái thành
phần tương ứng, có nghĩa là, cả trạng thái thể hiện và trạng thái cục bộ (quy tắc ASS inst
và quy tắc ASS loc ). Tạo đối tượng bằng lệnh u : new c tạo một đối tượng mới của kiểu
c với một định danh mới được lưu trữ trong biến cục bộ u, và khởi tạo các biến thể
hiện của đối tượng mới. Thi hành một phương thức mở rộng lời gọi dãy bằng một cấu
hình cục bộ mới (quy tắc CALL). Ta sử một câu lệnh phụ trợ receive u để nhớ biến mà
trong đó kết quả của phương thức được gọi sẽ được lưu trữ lúc trả về. Sau khi khởi tạo
trạng thái cục bộ và truyền các tham biến, luồng bắt đầu thi hành các lệnh trong thân
của phương thức. Khi trả về từ một lời gọi phương thức, phương thức được gọi ước
lượng biểu thức trả về và chuyển nó cho phương thức gọi, sau đó phương thức gọi cập
nhật trạng thái cục bộ của nó. Thân phương thức kết thúc sự thi hành của nó và
phương thức gọi có thể tiếp tục. Luồng đang thi hành kết thúc vịng đời của nó thơng
qua sự trả về từ phương thức run của đối tượng ban đầu (quy tắc RETURN run ).
2.3. Ngôn ngữ khẳng định
Logic khẳng định bao gồm một ngôn ngữ con cục bộ và một ngôn ngữ con tồn cục.
Các khẳng định cục bộ mơ tả các trạng thái thể hiện cục bộ, và được sử dụng để chú
thích các phương thức trong các tốn hạng của các biến cục bộ và của các biến thể
hiện của lớp mà chúng thuộc về. Các khẳng định toàn cục mơ tả trạng thái tồn cục,
nghĩa là, tồn bộ một hệ thống của các đối tượng và các cấu trúc giao tiếp của nó.
2.3.1. Cú pháp
Trong ngơn ngữ của các khẳng định, ta giới thiệu một tập vô hạn LVar của các biến
logic với phần tử điển hình là z , trong đó ta giả thiết rằng các biến thể hiện, các biến
cục bộ và con trỏ this không nằm trong LVar. Ta sử dụng LVar t cho tập các biến logic
của kiểu t. Các biến logic được sử dụng để lượng hóa trong cả ngơn ngữ cục bộ và
ngơn ngữ tồn cục. Bên cạnh đó, chúng cịn được sử dụng như là các biến tự do để
biểu diễn các biến cục bộ trong ngơn ngữ khẳng định tồn cục: Để biểu diễn một thuộc

tính cục bộ trong mức toàn cục, mỗi biến cục bộ trong một khẳng định cục bộ được
cho sẽ được thay thế bởi một biến logic mới.
Các biểu thức cục bộ e  LExp là các biểu thức của ngơn ngữ lập trình có thể
chứa các biến logic. Tập các biểu thức cục bộ của kiểu t được ký hiệu bởi LExp t . Một
cách lạm dụng ký hiệu, ta sử dụng e, e’, … khơng những cho các biểu thức chương
trình mà cịn cho các phần tử điển hình của các biểu thức cục bộ. Các khẳng định cục
bộ p, p' , q, ...,  LAss là các công thức logic chuẩn thông qua các biểu thức logic cục

- 20 -


bộ. Ta cho phép ba dạng của lượng hóa thơng qua các biến logic: Lượng hóa tồn tại
z. p chỉ được cho phép đối với các miền khơng có các tham chiếu đối tượng, nghĩa là,

kiểu của z được yêu cầu là các kiểu Int, Bool, hoặc là một kiểu hợp thành được xây
dựng từ các kiểu này. Đối với các kiểu tham chiếu c, dạng này của lượng hóa không
được cho phép, do vậy đối với các kiểu tham chiếu, sự tồn tại của một giá trị phụ thuộc
động vào trạng thái tồn cục. Khơng cho phép lượng hóa tồn tại đối với các kiểu đối
tượng đảm bảo rằng giá trị của một khẳng định cục bộ thực sự chỉ phụ thuộc vào các
giá trị của các biến thể hiện và các biến cục bộ, mà không phụ thuộc vào trạng thái
tồn cục. Tuy nhiên, một dạng lượng hóa có thể khẳng định sự tồn tại của các đối
tượng trong mức cục bộ thỏa mãn một vị từ, dạng được cung cấp là rõ ràng về tập các
đối tượng. Do vậy, các lượng hóa tồn tại z  e. p và z  e. p khẳng định sự tồn tại
của một phần tử, theo thứ tự, sự tồn tại của một dãy con của một dãy được cho e, sao
cho với một thuộc tính mà p đúng.
Các biểu thức toàn cục E , E ' , ...  GExp được xây dựng từ các biến logic, null, các
biểu thức toán tử, và các tham chiếu hạn chế E.x tới các biến thể hiện x của các đối
tượng E. Ta viết GExp t đối với tập các biểu thức toàn cục của kiểu t. Các khẳng định
toàn cục P, Q, ... GAss là các công thức logic thông qua các biểu thức logic tồn cục.
Khơng giống như ngơn ngữ cục bộ, ngữ nghĩa của một biểu thức toàn cục được định

nghĩa trong ngữ cảnh của một trạng thái toàn cục. Do vậy lượng hóa tồn tại được cho
phép đối với tất cả các kiểu và được thể hiện cho các dãy thông qua tập các giá trị
đang tồn tại và null, nghĩa là, tập các giá trị Val  null trong một cấu hình tồn cục
T ,

Nhiều khi ta viết lượng hóa thơng qua các giá trị kiểu t trong dạng  z : t  . p tạo
sự rõ ràng cho miền lượng hóa; ta cũng sử dụng cùng ký hiệu trong ngơn ngữ tồn cục.
Sử dụng z . p thay cho z . p .
2.3.2. Ngữ nghĩa
Các biến logic được thể hiện tương đối tới môi trường logic    , đó là, một hàm
cục bộ của kiểu LVar  Val null , gán các giá trị cho các biến logic. Ta ký hiệu bằng





 z  v môi trường logic gán các giá trị v cho các biến z . Tương tự như vậy đối với





các cập nhật trạng thái cục bộ và trạng thái thể hiện, ta cũng sử dụng  y  v cho các
dãy biến tùy y để biểu diễn môi trường logic gán cho mỗi biến logic trong y giá trị

- 21 -


tương ứng trong v . Đối với một môi trường logic  và một trạng thái toàn cục  , ta
nói rằng  chỉ tham chiếu tới các giá trị đang tồn tại trong  , nếu   z Val null   đối

với tất cả z dom   . Thuộc tính này phù hợp với định nghĩa của lượng hóa trong đó
các dãy chỉ thơng qua các giá trị đang tồn tại và null, và trong thực tế, trong các cấu
hình cục bộ có thể đạt tới được các biến chỉ có thể tham chiếu tới các giá trị đang tồn
tại hoặc là null.
Hàm ngữ nghĩa _ L  ,  ,  của kiểu    inst   loc   LExp  LAss  Val null  ước
lượng các biểu thức cục bộ và các khẳng định cục bộ trong ngữ cảnh của một môi
trường logic  và một trạng thái thể hiện cục bộ  inst ,   . Hàm ước lượng được định
nghĩa cho các biểu thức

và các khẳng định chỉ chứa các biến từ

dom    dom  inst   dom   . Trạng thái thể hiện cục bộ cung cấp ngữ cảnh đối với ngữ

nghĩa cho các biểu thức ngơn ngữ lập trình do vậy được định nghĩa bởi hàm ngữ nghĩa

_ , ,  ; môi trường logic ước lượng các biến logic. Một lượng hóa tồn tại z . p với
z LVar t ước lượng là đúng trong môi trường logic  và trạng thái thể hiện cục bộ

 inst ,   khi và chỉ khi tồn tại một giá trị vVal t sao cho p đúng trong môi trường logic
 z  v  và trạng thái thể hiện cục bộ  inst ,   , trong đó đối với kiểu t của z chỉ có kiểu
Int, Bool, hoặc các kiểu hợp thành được xây dựng từ hai kiểu này là được cho phép.
Sự ước lượng của một lượng hóa tồn tại z  e . p với z LVar t và e LExp list t được định
nghĩa tương tự, trong đó sự tồn tại của một phần tử trong dãy được yêu cầu. Một
khẳng định z  e . p với z LVar list t và e LExp list t chỉ rõ sự tồn tại của một dãy con
của

e

sao


cho

p

đúng.

Trong

, inst , |L p cho  pL,  inst ,  true

phần

sau

ta

cũng

viết

(L thỏa mãn vị từ p dưới thể hiện

i( ,  inst , )). | L p ta phát biểu rằng ,  inst , | L p đúng đối với các môi trường logic
bất kỳ, các trạng thái thể hiện bất kỳ, và các trạng thái cục bộ bất kỳ.

zL,

inst,

 z


xL,

inst,

 instx

uL,

inst,

  u

this L  , 

inst

,

  inst this 

- 22 -


null L  , 

inst

 f e1 , ..., en L ,


,

inst ,

 null



 f e1 L

 ,  inst ,

, ..., en L

 ,  inst ,



p  true khi và chỉ khi p  false
p  p   true khi và chỉ khi p   true và  p   true
z . p  true khi và chỉ khi  p
 true  với vVal
z  e . p  true khi và chỉ khi  z  e  p
 true  với vVal
z  e . p  true khi và chỉ khi z  e  p
 true  với vVal
 ,  inst ,

 ,  inst ,


L

L

 ,  inst ,

1

2

 ,  inst ,

 , inst ,

L

1

2

L

L

  z  v ,  inst ,

 ,  inst ,

L


null

L

  z  v ,  inst ,

 ,  inst ,

L

null

L

  z  v ,  inst ,

 ,  inst , 

L

L

null

Bởi vì các khẳng định tồn cục không chứa các biến cục bộ và các tham chiếu
không hạn chế tới các biến thể hiện, nên các ngữ nghĩa của các khẳng định tồn cục
khơng tham chiếu tới các trạng thái thể hiện cục bộ nhưng tới các trạng thái toàn cục.
Hàm ngữ nghĩa

 G  ,  ,  của kiểu     GExp  GAss  Val null  , cho các biểu


thức toàn cục và các khẳng định toàn cục ngữ nghĩa trong ngữ cảnh của một môi
trường logic  và một trạng thái toàn cục  . Để đúng theo định nghĩa,  được yêu
cầu chỉ tham chiếu tới các giá trị đang tồn tại trong miền của  , và theo thứ tự biểu
thức và khẳng định chỉ có thể chứa các biến tự do từ miền của  . Các biến logic, null,
và các biểu thức toán tử được ước lượng tương tự như các khẳng định cục bộ. một
biểu thức toàn cục E.x được cho bởi giá trị của biến thể hiện x của đối tượng được
tham chiếu tới bởi biểu thức E. Sự ước lượng của một biểu thức E.x chỉ được định
nghĩa nếu E tham chiếu tới một đối tượng đang tồn tại trong  . Chú ý rằng khi E và
E’ tham chiếu tới cùng một đối tượng, đó là, E và E’ là các bí danh, thì E.x và E’.x
biểu diễn cùng một biến. Các ngữ nghĩa của phép phủ định và phép hội là chuẩn. Một
lượng hóa z . P với z  LVal t ước lượng đúng trong ngữ cảnh của  và  nếu P ước
lượng đúng trong ngữ cảnh của z  v  và  , đối với giá trị v  Val t null   . Chú ý
rằng lượng hóa chỉ thơng qua các dãy các đối tượng thông qua tập của các đối tượng
đang tồn tại và null.

z G  , 

null G  , 

  z 

 null

- 23 -


 f E1 , ..., En G ,
E. xG  ,


 P 
P  P

 ,

G

1

2

 z . P 

 ,



 E 

G

 ,

, 

, ..., En G



 khi và chi khi P 

true  khi và chi khi P 

 true

,

 ,



G

1

 khi



x  

 true

G  , 

G



 f E1 G


và chi khi

P 

G

 ,

G

 ,

false

 true

 true


 và P

 voi v  Val

2

G  , 

null

 true




 

Đối với một trạng thái toàn cục  và một môi trường logic  đang tham chiếu
chỉ tới các giá trị đang tồn tại trong  ta viết ,  | G P khi P là đúng trong ngữ cảnh
của  và  . Ta viết | G P nếu P đúng đối với các trạng thái toàn cục và các môi
trường logic  bất kỳ đang tham chiếu chỉ tới các giá trị đang tồn tại trong  .
Để biểu thị một thuộc tính cục bộ p trong ngơn ngữ khẳng định toàn cục, ta định
nghĩa sự thay thế nâng lên pz / this bởi thay thế đồng thời trong p tất cả các lần xuất
hiện của tham chiếu tới chính nó – con trỏ this bằng biến logic z, được đảm bảo không
xuất hiện trong p, và biến đổi tất cả các lần xuất hiện của các biến thể hiện x trong các
tham chiếu hạn chế z.x. Để thuận tiện cho việc ký hiệu ta xem các biến cục bộ đang
xuất hiện trong khẳng định toàn cục pz / this như là các biến logic. Các biến cục bộ
này được thay thế bởi các biến logic mới. Đối với các lượng hóa tồn tại

z ' . p  z / this sự thay thế áp dụng cho khẳng định p. Các lượng hóa tồn tại cục bộ
được biến đổi trong các lượng hóa tồn tại tồn cục trong đó các quan hệ  và  được
biểu thị ở mức tồn cục như là các tốn tử.
this z / this   z
xz / this   z. x
uz / this  u

z' . p  z / this  z ' . p z / this
z'  e . p z / this  z ' . z '  ez / this  pz / this
z'  e . p z / this  z ' . z '  ez / this  pz / this
trong đó z là biến mới. Ta viết P (z) đối với pz / this , và tương tự cho các biểu thức.
Sự thay thế này sẽ được sử dụng để kết hợp các thuộc tính của các trạng thái thể
hiện cục bộ trong mức toàn cục. Sự thay thế bảo toàn ngữ nghĩa của các khẳng định


- 24 -


cục bộ, ngữ nghĩa của các biến cục bộ đã được cung cấp được biểu diễn trùng khớp
bởi môi trường logic:
Bổ đề 2.3.1. (Sự thay thế nâng lên) Cho  là một trạng thái tồn cục,  và  một
mơi trường logic và trạng thái cục bộ, cả hai đang tham chiếu chỉ tới các giá trị đang
tồn tại trong  . Hơn nữa cho p là một khẳng định cục bộ đang chứa các biến cục bộ

 

u . Nếu  u   u và z là một biến logic mới, thì

,  | G p z / this  khi và chỉ khi  ,    z , | L p

2.4. Hệ chứng minh
Chứng minh tính đúng đắn của một thuộc tính của chương trình gồm có ba bước. Đầu
tiên, thuộc tính được u cầu phải được chỉ rõ bởi sự bổ sung và chú thích chương
trình, nghĩa là, bằng sự bổ sung chương trình với các biến phụ trợ không ảnh hưởng
đến luồng điều khiển của chương trình gốc, và bằng sự đính kèm các vị từ cho các cấu
trúc chương trình cú pháp. Một chương trình được bổ sung và chú thích được gọi là
một phác thảo chứng minh. Thứ hai, phác thảo chứng minh phải được áp dụng đối với
phác thảo chứng minh riêng biệt, có kết quả là tập kiểm chứng các điều kiện. Cuối
cùng, kiểm chứng các điều kiện phải được chứng minh.
Để thuận lợi về mặt kỹ thuật, đầu tiên ta đưa ra kiểm chứng các điều kiện như là
các bộ ba Hoare chuẩn của dạng p stm q, trong đó stm là một phép gán bội hoặc là
các thành phần tuần tự của các phép gán bội, đang biểu thị các cập nhật trạng thái.
Trong kiểm chứng các điều kiện được đưa ra trong ngôn ngữ khẳng định cục bộ, các
phép gán bội trong bộ ba Hoare có thể tham chiếu tới các biến thể hiện và cục bộ. Các

phép gán trong các điều kiện tồn cục có thể sử dụng các biến logic và các tham chiếu
hạn chế tới các biến thể hiện. Các lệnh trong các điều kiện tồn cục có thể sử dụng các
biến logic và các tham chiếu hạn chế tới các biến thể hiện. Các biến cục bộ được biểu
thị trong ngôn ngữ tồn cục bởi các biến logic.
Ví dụ 2.4.1. Bộ ba logic Hoare u  0  v  0x : u * vx  0, được đưa ra trong ngôn
ngữ cục bộ, phát biểu rằng nếu cả hai biến u và v có các giá trị dương, thì sau khi thi
hành phép gán x := u * v giá trị của biến x là dương.
Bộ ba Hoare u  0  v  0z. x : u * vz. x  0 , được đưa ra trong ngơn ngữ tồn
cục, phát biểu rằng nếu cả hai biến u và v có giá trị dương thì sau khi thi hành phép
gán z.x = u * v, có nghĩa là, sau khi gán giá trị của u * v cho biến thể hiện x của đối
tượng z, giá trị của z.x là dương.

- 25 -