The Foundations of Program Verification

This is a textbook on program verification. It concentrates on those verification methods that have now become classic such as the inductive assertions method of Floyd, the axiomatic method of Hoare and Scott's fixpoint induction. The aim of the book is to present these different verification methods and to explain their mathemati- cal background. The subject is treated with mathematical precision, and many examples are included. Throughout the book the same examples will reappear to illustrate how the different methods are related. The material is self-contained and accessible without prior knowledge of logic or semantics, but elementary knowledge of programming languages, formal languages and the theory of computation is helpful. A main concern has been to present the subject in as simple a setting as possible. For this reason three elementary, representative programming languages are in- troduced: a flowchart programming language, a language of while-programs and a language of recursive programs. For these programming languages the operational and denotational semantics are introduced. Each verification method is then illustrated in the most appropriate of these languages and proved correct with the help of the most appropriate of the semantics.