Fundamental Proof Methods in Computer Science ─ A Computer-Based Approach

Proof is the primary vehicle for knowledge generation in mathematics. In computer science, proof has found an additional use: verifying that a particular system (or component, or algorithm) has certain desirable properties. This book teaches students to read and write proofs using Athena, a freely downloadable computer language. Athena proofs are machine-checkable and written in an intuitive natural-deduction style. The book contains more than 300 exercises, most with full solutions; by putting proofs into practice, it demonstrates the fundamental role of logic and proof in computer science as no other existing text does.

Guided by examples and exercises, students are quickly immersed in the most useful high-level proof methods, including equational reasoning, several forms of induction, case analysis, proof by contradiction, and abstraction/specialization. Athena is particularly suited to the needs of computer science students as proofs are expressed with programming constructs based closely on those used in conventional programming. Block structure, for example, plays a key role in Athena's natural-deduction style. These similarities allow useful analogies to be drawn between proofs-as-programs and ordinary programs. The book also includes auxiliary material on SAT and SMT solving, automated theorem proving, and logic programming.

The book can be used by upper undergraduate- or graduate-level computer science students with a basic level of programming and mathematical experience. Professional programmers, practitioners of formal methods, and researchers in logic-related branches of computer science will find it a valuable reference.

Konstantine Arkoudas is a Senior Research Scientist and Software Engineer in the Machine Learning Group for Bloomberg R&D. David Musser is Professor Emeritus of Computer Science at Rensselaer Polytechnic Institute.