This course provides a first introduction to the Curry-Howard correspondence between programs and proofs, from a theoretical programmer's perspective: we want to understand the theory behind logic and programming languages, but also to write concrete programs (in OCaml) and proofs (in Agda). After an introduction to functional programming languages, we present propositional logic, λ-calculus, the Curry-Howard correspondence, first-order logic, Agda, dependent types and homotopy type theory.
This comprehensive and highly readable textbook teaches how to formally reason about computer programs using an incremental approach and the verification-aware programming language Dafny. Program Proofs shows students what it means to write specifications for programs, what it means for programs to satisfy those specifications, and how to write proofs that connect specifications and programs. Writing with clarity and humor, K. Rustan M. Leino first provides an overview of the basic theory behind reasoning about programs. He then gradually builds up to complex concepts and applications, until students are facing real programs using objects, data structures, and non-trivial recursion. To emphasize the practical nature of program proofs, all material and examples use the verification-aware programming language Dafny, but no previous knowledge of Dafny is assumed. Written in a highly readable and student-friendly style Builds up to complex concepts in an incremental manner Comprehensively covers how to write proofs and how to specify and verify both functional programs and imperative programs Uses real program text from a real programming language, not psuedo code Features engaging illustrations and hands-on learning exercises
A practical introduction to the development of proofs and certified programs using Coq. An invaluable tool for researchers, students, and engineers interested in formal methods and the development of zero-fault software.
A handbook to the Coq software for writing and checking mathematical proofs, with a practical engineering focus. The technology of mechanized program verification can play a supporting role in many kinds of research projects in computer science, and related tools for formal proof-checking are seeing increasing adoption in mathematics and engineering. This book provides an introduction to the Coq software for writing and checking mathematical proofs. It takes a practical engineering focus throughout, emphasizing techniques that will help users to build, understand, and maintain large Coq developments and minimize the cost of code change over time. Two topics, rarely discussed elsewhere, are covered in detail: effective dependently typed programming (making productive use of a feature at the heart of the Coq system) and construction of domain-specific proof tactics. Almost every subject covered is also relevant to interactive computer theorem proving in general, not just program verification, demonstrated through examples of verified programs applied in many different sorts of formalizations. The book develops a unique automated proof style and applies it throughout; even experienced Coq users may benefit from reading about basic Coq concepts from this novel perspective. The book also offers a library of tactics, or programs that find proofs, designed for use with examples in the book. Readers will acquire the necessary skills to reimplement these tactics in other settings by the end of the book. All of the code appearing in the book is freely available online.
Many students have trouble the first time they take a mathematics course in which proofs play a significant role. This new edition of Velleman's successful text will prepare students to make the transition from solving problems to proving theorems by teaching them the techniques needed to read and write proofs. The book begins with the basic concepts of logic and set theory, to familiarize students with the language of mathematics and how it is interpreted. These concepts are used as the basis for a step-by-step breakdown of the most important techniques used in constructing proofs. The author shows how complex proofs are built up from these smaller steps, using detailed 'scratch work' sections to expose the machinery of proofs about the natural numbers, relations, functions, and infinite sets. To give students the opportunity to construct their own proofs, this new edition contains over 200 new exercises, selected solutions, and an introduction to Proof Designer software. No background beyond standard high school mathematics is assumed. This book will be useful to anyone interested in logic and proofs: computer scientists, philosophers, linguists, and of course mathematicians.
This book constitutes the referred proceedings of the First International Conference on Certified Programs and Proofs, CPP 2011, held in Kenting, Taiwan, in December 2011. The 24 revised regular papers presented together with 4 invited talks were carefully reviewed and selected from 49 submissions. They are organized in topical sections on logic and types, certificates, formalization, proof assistants, teaching, programming languages, hardware certification, miscellaneous, and proof perls.
This book is for graduate students and researchers, introducing modern foundational research in mathematics, computer science, and philosophy from an interdisciplinary point of view. Its scope includes proof theory, constructive mathematics and type theory, univalent mathematics and point-free approaches to topology, extraction of certified programs from proofs, automated proofs in the automotive industry, as well as the philosophical and historical background of proof theory. By filling the gap between (under-)graduate level textbooks and advanced research papers, the book gives a scholarly account of recent developments and emerging branches of the aforementioned fields.
This book constitutes the refereed proceedings of the Third International Conference on Certified Programs and Proofs, CPP 2013, colocated with APLAS 2013 held in Melbourne, Australia, in December 2013. The 18 revised regular papers presented together with 1 invited lecture were carefully reviewed and selected from 39 submissions. The papers are organized in topical sections on code verification, elegant proofs, proof libraries, certified transformations and security.
Most aspects of our private and social lives—our safety, the integrity of the financial system, the functioning of utilities and other services, and national security—now depend on computing. But how can we know that this computing is trustworthy? In Mechanizing Proof, Donald MacKenzie addresses this key issue by investigating the interrelations of computing, risk, and mathematical proof over the last half century from the perspectives of history and sociology. His discussion draws on the technical literature of computer science and artificial intelligence and on extensive interviews with participants. MacKenzie argues that our culture now contains two ideals of proof: proof as traditionally conducted by human mathematicians, and formal, mechanized proof. He describes the systems constructed by those committed to the latter ideal and the many questions those systems raise about the nature of proof. He looks at the primary social influence on the development of automated proof—the need to predict the behavior of the computer systems upon which human life and security depend—and explores the involvement of powerful organizations such as the National Security Agency. He concludes that in mechanizing proof, and in pursuing dependable computer systems, we do not obviate the need for trust in our collective human judgment.
This book constitutes the refereed proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2000, held as part of ETAPS 2000 in Berlin, Germany, in March/April 2000. The 33 revised full papers presented together with one invited paper and two short tool descriptions were carefully reviewed and selected from a total of 107 submissions. The papers are organized in topical sections on software and formal methods, formal methods, timed and hybrid systems, infinite and parameterized systems, diagnostic and test generation, efficient model checking, model-checking tools, symbolic model checking, visual tools, and verification of critical systems.
