Automating Theorem Proving with SMT

Rustan Leino

ITP 2013 |

The power and automation offered by modern satisfiability-modulotheories (SMT) solvers is changing the landscape for mechanized formal theorem proving. For instance, the SMT-based program verifier Dafny supports a number of proof features traditionally found only in interactive proof assistants, like inductive, co-inductive, and declarative proofs. To show that proof tools rooted in SMT are growing up, this paper presents, using Dafny, a series of examples that illustrate how theorems are expressed and proved. Since the SMT solver takes care of many formal trivialities automatically, users can focus more of their time on the creative ingredients of proofs.