Home > Hoare logic

Hoare acknowledges earlier contributions from Robert Floyd, who had published a similar system for flowcharts.

The central feature of Hoare logic is the Hoare triple. A triple describes how the execution of a piece of code changes the state of the computation. A Hoare triple is of the form

where P and Q are assertions and C is a command. P is called the precondition and Q the postscondition. Assertions are formulas in predicate logic. The intuitive reading of such a triple is: Whenever P holds of the state before the execution of C, then Q will hold afterwards. Note that if C does not terminate, then there is no "after", so Q can be any statement at all. Indeed, one can choose Q to be false to express that C does not terminate.

This is called "partial correctness". If C terminates and at termination Q is true, the expression exhibits "total correctness". Termination would have to be proved separately.

Hoare logic has axioms and inference rules for all the constructs of a simple imperative programming languageIn computer science, imperative programming as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. In much the same way as the imperative mood i.

The assignment axiom states that after the assignment any predicate holds for the variable that was previously true for the right-hand side of the assignment:

An example of a valid triple is:

1 See also

• Design by contractDesign by contract or DBC is a methodology for designing computer software. It prescribes that software designers should define precise checkable interface specifications for software components based upon the theory of Abstract data types and the concept
• Program verificationProgram verification is the process of formally proving that a computer program does exactly what is stated in the program specification it was written to realize. See also Formal verification.
• Dijkstra

2 References

• C. A. R. Hoare. "An axiomatic basis for computer programming". Communications of the ACMThe Association for Computing Machinery or ACM was founded in 1947 as the world's first scientific and educational computing society. Its membership is currently around 78,000. Its headquarters are in New York, New York. Activities is organized into over, 12(10):576-585, October 1969. [1]

• Robert D. Tennent: "Specifying Software" (a recent textbook that includes an introduction to Hoare logic) BooksEnthsiast.com [2]