Luận lý Hoare

Luận lý Hoare (còn được biết đến với tên Luận lý Floyd–Hoare) là một hệ chính quy do nhà khoa học máy tính người Anh C. A. R. Hoare phát triển, và sau đó được Hoare và những nhà nghiên cứu khác tinh lọc lại. Mục đích của hệ thống là cung cấp một tập các quy luật luận lý để suy luận tính đúng đắn của các chương trình máy tính bằng tính chính xác của luận lý toán học.
Nó được xuất bản trong bài báo năm 1969 của Hoare, ở đó Hoare đã sử dụng lại những đóng góp trước đó của Robert Floyd, người đã xuất bản một hệ thống tương tự dành cho sơ đồ luồng (flowchart).
Đặc điểm trung tâm của luận lý Hoare là bộ ba Hoare. Bộ ba này mô tả sự thực thi một đoạn mã có thể thay đổi trạng thái tính toán như thế nào. Bộ ba Hoare có dạng
trong đó "P" và "Q" là những "khẳng định" và "C" là một "mệnh lệnh". "P" được gọi là "tiền điều kiện" và "Q" là "hậu điều kiện". Những khẳng định là những công thức có dạng luận lý vị từ.
Luận lý Hoare có những tiên đề và luật suy diễn dành cho tất cả những mẫu cơ bản của ngôn ngữ lập trình mệnh lệnh. Ngoài các luật dành cho ngôn ngữ đơn giản trong bài báo nguyên thủy của Hoare, những luật dành cho những mẫu ngôn ngữ khác cũng đã được phát triển từ lúc đó bởi Hoare và nhiều nhà nghiên cứu khác. Có những luật dành cho đồng thời, thủ tục, nhảy, và con trỏ.
Tính đúng đắn bộ phận và toàn phần.
Luận lý Hoare chuẩn chỉ chứng minh tính đúng đắn bộ phận, trong khi điều kiện dừng phải được chứng minh độc lập. Do đó cách diễn dịch bộ ba Hoare là: Nếu "P" là trạng thái trước khi thực thi "C", thì "Q" sẽ là trạng thái sau khi thực thi nó, hoặc "C" không dừng (chạy vô tận). Chú ý rằng nếu "C" không dừng thì sẽ không có khái niệm "sau", do đó "Q" có thể là bất cứ thứ gì. Thực vậy, người ta có chọn "Q" là false để diễn tả rằng "C" không dừng.
Tính đúng đắn toàn phần cũng có thể được chứng minh bằng phiên bản mở rộng của quy luật While.
Các quy luật.
Luật về phát biểu gán.
Tiên đề gán chỉ ra rằng sau phép gán, bất kỳ vị từ nào chứa biến là true đối với vế phải phép gán:
Ở đây formula_4 chỉ ra rằng biểu thức "P" trong đó tất cả các lần xuất hiện tự do của biến "x" đã được thay bằng biểu thức "E".
Ý nghĩa của tiên đề gán này là giá trị đúng sai của formula_5 là tương đương với giá trị đúng sai của formula_6 sau khi gán. Do đó nếu formula_5 là "true" trước phép gán, nhờ tiên đề gán formula_6 cũng sẽ "true" sau phép gán. Ngược lại, nếu formula_5 là "false" trước phép gán, thì chắc chắn formula_6 phải là "false" sau phép gán.
Các ví dụ về những bộ ba đúng:
Tiên đề gán do Hoare đưa ra "không áp dụng" vào trường hợp có nhiều hơn một tên cùng chỉ một giá trị lưu trữ. Ví dụ,
là không đúng nếu "x" và "y" cùng đại diện cho một biến, vì không có tiền điều kiện nào có thể khiến cho "y" bằng 3 sau khi "x" được gán bằng 2.
Luật ghép.
Luật về phát biểu ghép của Hoare áp dụng cho những chương trình được thực thi tuần tự "S" và "T", trong đó "S" thực thi trước "T" và được viết là "S;T".
Ví dụ, xét hai phát biểu sau:
và
Theo luật ghép, ta có thể kết luận:
Luật While.
Ở đây "P" là điều kiện bất biến của vòng lặp.
Luật While dành cho tính đúng đắn toàn phần.
Trong luật này, ngoài việc giữ các điều kiện bất biến vòng lặp, ta cũng phải chứng minh dừng bằng cách chứng minh giá trị của một số hạng giảm dần sau mỗi lần lặp, ở đây là "t". Chú ý rằng "t" phải là giá trị thuộc tập chắc chắn, để cho mỗi bước lặp có thể tính được bằng cách giảm giá trị đi một chuỗi hữu hạn.