Much current research in computer science is concerned with two questions: is a program correct? And how can we improve a correct program preserving correctness? This latter question is known as the refinement of programs and the purpose of this book is to consider these questions in a formal setting. In fact, correctness turns out to be a special case of refinement and so the focus is on refinement. Although a reasonable background knowledge is assumed from mathematics and CS, the book is a self-contained introduction suitable for graduate students and researchers coming to this subject for the first time. There are numerous exercises provided of varying degrees of challenge. TOC:Introduction.- Posets, lattices and categories.- Higher order logic.- Functions.- States and state transformers.- Truth values.- Predicates and sets.- Boolean expressions and conditionals.- Relations.- Types and data structures.- Predicate transformers.- The refinement calculus hierarchy.- Statements.- Statements as games.- Choice semantics.- Subclass of statements.- Correctness and refinement of statements.- Well-founded sets and ordinals.- Fixpoints.- Recursion.- Iteration and loops.- Continuity and executable statements.- Working with arrays.- The N-queens problem.- Loops and two-person games.- Statement classes and normal forms.- Specification statements.- Refinement in context.- Iteration of conjunctive statements.
