Software Foundations Volume 1: Logical Foundations – Free Online Book (Pierce et al., v7.1) BSCS

BSCS and MS students can read Software Foundations, Volume 1: Logical Foundations free online. It is the first book of the Software Foundations series from the University of Pennsylvania, written by Benjamin C. Pierce and seven co-authors, and it suits Formal Methods, Logic in Computer Science and Programming Languages courses. There is no official PDF: the book is a set of web pages and Rocq source files, and the current release is Version 7.1 from August 2026.

What makes this book different is that every chapter is a program. Each one is a script for the Rocq proof assistant, which was called Coq until 2025, so you read, run and prove inside the same file. You begin with functional programming and proofs by induction, then learn logic, inductively defined propositions and the Curry-Howard correspondence, and finish with a small imperative language called Imp and proof automation. No background in logic or programming languages is assumed, but you need a first programming course, some mathematical maturity and the patience to install software and work the exercises.

Book Overview

CourseFormal Methods / Logic and Proof in Computer Science
Degree ProgramsBSCS, MS Computer Science
LevelAdvanced undergraduate to graduate (intermediate to advanced)
EditionVersion 7.1 (24 August 2026), for Rocq 9.0.0 or later
AuthorsBenjamin C. Pierce, Arthur Azevedo de Amorim, Chris Casinghino, Marco Gaboardi, Michael Greenberg, Cătălin Hriţcu, Vilhelm Sjöberg, Brent Yorgey (with 23 named contributors)
PublicationElectronic textbook, hosted at the University of Pennsylvania
LanguageEnglish
Total Chapters18 chapters plus a Preface and a Postscript
Programming LanguageRocq (formerly Coq), with OCaml in the extraction chapter
ExercisesAbout 270 star-rated exercises (1 to 5 stars), most meant to be solved inside Rocq
LicenseMIT License (LICENSE file in the official distribution, Copyright (c) 2026) — Model: Link-only
FormatFree online book (HTML) with downloadable Rocq source files (lf.tgz); no PDF

Chapter List

Chapter 0: Preface

Recommended path · Difficulty: Easy · Key topics: Rocq, proof assistants, functional programming, VSCode and Docker, exercise stars, chapter dependencies

The Preface introduces the whole Software Foundations series and explains why every volume is literally a script for the Rocq proof assistant, meant to be read alongside an interactive session. It describes the three threads of this volume: logic, proof assistants and functional programming. Then it turns practical. You get the tested Rocq version, the recommended VSCode plus Docker setup, other ways to install, the one-to-five star scale for exercises, how to download the sources and a note on the Coq to Rocq rename. Pointers to sample exams and lecture videos close it.

Key Points:

  • Each text is a Rocq script, so every definition, example and proof in the book is machine-checked.
  • The three threads are logic, proof assistants and functional programming, which the book treats as one story.
  • Rocq was called Coq until 2025, and the Preface says this release still mixes both names.
  • The files were tested with Rocq 9.0.0, and VSCode with Docker is the recommended setup.
  • Exercises carry one to five stars, and the classroom autograder awards 1, 2, 3, 6 and 10 points for them.
  • The authors ask readers not to post exercise solutions in public places.

Practice Tip: Set up the VSCode and Docker folder first, open Basics.v and step through it with the keyboard shortcut the Preface gives. If the highlighted region follows your cursor, your whole toolchain works.

Common Mistake: Reading the book like an ordinary textbook without running it. The Preface says the exercises are designed to be worked in Rocq, and the proofs only make sense when you watch the goals change.

Important Questions:

  • Why does the series call itself one hundred percent formalized? Each volume is a Rocq script, so the text, the definitions and the proofs are all checked by the proof assistant.
  • Which exercises give good coverage of the core material? The non-optional, non-advanced ones; optional ones add practice and advanced ones add challenge.

Chapter 1: Functional Programming in Rocq (Basics)

Recommended path · Difficulty: Easy · Key topics: Inductive types, pattern matching, bool and nat, Fixpoint, Compute and Example, reflexivity, rewrite, destruct

Basics builds a small functional language from almost nothing. You define enumerated types such as days and booleans, then types with arguments such as colors and nybbles, and finally the unary natural numbers with the constructors O and S. Functions are written by pattern matching and structural recursion. The chapter then starts proving: simplification with reflexivity, rewriting with hypotheses, and case analysis with destruct. It ends with warm-ups, a formal model of a course late-day grading policy and a binary numeral exercise.

Key Points:

  • Rocq has very little built in, so bool and nat are ordinary Inductive definitions.
  • A match must cover every constructor, and a Fixpoint must recurse on a structurally smaller argument.
  • An example can be checked with Compute, with an Example proved by reflexivity, or by extraction to OCaml, Scheme or Haskell.
  • x = y is a proposition you try to prove, while x =? y is a boolean you compute.
  • destruct n as [| n'] splits a goal into the O case and the S n' case.
  • Admitted marks an unfinished proof, and exercises ask you to replace it with a real one.
  • The chapter has 20 exercises rated from one to three stars.

Practice Tip: Try to prove that n + 1 =? 0 is false using only simpl and reflexivity, watch it get stuck, then add destruct n. You will see exactly why unknown values block computation.

Common Mistake: Mixing up = and =?. The first is a claim, the second is a function that returns true or false, and they are not interchangeable in definitions.

Important Questions:

  • What is the difference between = and =? in Rocq? The first is a logical proposition to be proved, and the second is a boolean function that computes an answer.
  • Why does simpl get stuck on n + 1 =? 0 when n is unknown? Both + and =? begin by matching on a value built from n, so n must first be split into its O and S cases.

Chapter 2: Proof by Induction (Induction)

Recommended path · Difficulty: Medium · Key topics: induction tactic, induction hypothesis, assert, commutativity and associativity, informal proofs, binary numerals, normalization

Simplification and case analysis cannot show that zero is also a neutral element of addition on the right, because the unknown number can be arbitrarily large. This chapter introduces the induction tactic, which gives a base case and a step case with an induction hypothesis, and uses it for facts such as commutativity and associativity of addition. It shows assert for local lemmas and compares a Rocq proof with the informal proof a mathematician would write. A binary numeral case study follows, including why converting binary to a number and back needs a normalization function.

Key Points:

  • induction n as [| n' IHn'] creates one goal for O and one for S n' with the hypothesis IHn'.
  • Each chapter imports the previous one, which must be compiled first into a .vo file, much like .class or .o files.
  • assert (H : ...) proves a small fact on the spot, useful when rewrite would change the wrong place.
  • The chapter’s motto is that informal proofs are algorithms and formal proofs are code.
  • Natural number to binary and back always round-trips, but binary to number to binary may not, because different binary values can mean the same number.
  • A normalize function picks the simplest representation and makes the second round trip provable.
  • The chapter has 12 exercises, some marked advanced.

Practice Tip: Step through the proof of addition associativity with your cursor and watch both subgoals. Then write the same proof in plain English on paper and compare the two.

Common Mistake: Repeating destruct to cope with a number of unknown size. Each use gets you one step further and you never finish, so switch to induction.

Important Questions:

  • Why can reflexivity not prove n + 0 = n? Addition matches on its first argument, which is the unknown n, so nothing can be computed and induction on n is needed.
  • When is assert useful? When you need one specific instance of a fact for a single step, such as a particular use of commutativity, without giving it a top-level name.

Chapter 3: Working with Structured Data (Lists)

Recommended path · Difficulty: Medium · Key topics: pairs, natlist, cons and nil, append, reverse, bags, Search, option, partial maps

Lists moves from single numbers to structured data. It defines pairs of numbers, then lists of numbers with nil and cons and the notations :: and [ ], and writes the standard functions: repeat, length, append, head and tail, plus a bag (multiset) type with counting and membership. Proofs by simplification, case analysis and induction on lists follow, including reverse and a lesson on generalizing statements. The chapter closes with the option type for functions that can fail and a small list-based partial map, which prepares the ground for the Maps chapter.

Key Points:

  • A list is either nil or a number consed onto another list, so proofs go by cases or induction on that shape.
  • Proving that reversing keeps the length needs a helper lemma about the length of appended lists.
  • When induction gets stuck, a more general statement gives a stronger induction hypothesis.
  • The Search command finds existing theorems by the functions they mention, by a pattern, or inside one module.
  • nth_error returns None or Some a instead of inventing a dummy number for a missing element.
  • The partial map is a list of key and value records; update shadows old entries and find returns the first match.
  • The chapter has 19 exercises, with bags and reverse as the main themes.

Practice Tip: Before writing a helper lemma, run Search rev and a search with a pattern such as two additions on each side of an equals sign. You will often find the theorem already exists.

Common Mistake: Returning a default value such as 0 for a missing list element. Nobody can then tell whether 0 was found or the list was too short, which is why the chapter switches to option.

Important Questions:

  • Why is a lemma about appended lists needed to prove that reverse preserves length? The step case produces length (rev l' ++ [n]), and only a general fact about the length of l1 ++ l2 lets the proof continue.
  • Why does nth_error return an option? It separates a genuine answer from the error case of a list that is too short, which a default number cannot do.

Chapter 4: Polymorphism and Higher-Order Functions (Poly)

Recommended path · Difficulty: Medium · Key topics: polymorphic lists, implicit arguments, products, options, filter, map, fold, anonymous functions, currying, Church numerals

Poly adds two big ideas: polymorphism and higher-order functions. Lists become list X, and type inference, argument synthesis and implicit arguments spare you from writing types by hand. Pairs and options are generalized in the same way. The second half treats functions as data: filter, map and fold, anonymous functions written with fun, functions that return functions, and the fact that multi-argument functions are one-argument functions in disguise. Advanced exercises on Church numerals show numbers represented purely as function iteration.

Key Points:

  • list is a family of types, so nil and cons take the element type as their first parameter.
  • Writing {X : Type} makes a type argument implicit, and @ in front of a name makes it explicit again.
  • (x, y) is a value, while X * Y is a type built from two types.
  • filter keeps elements that pass a test, map transforms every element and fold combines elements with a binary operator and a starting value.
  • X -> Y -> Z means X -> (Y -> Z), which is what makes partial application and currying possible.
  • A Church numeral for n applies a given function exactly n times.
  • The chapter has 20 exercises, including a group of advanced ones on Church numerals.

Practice Tip: Apply map to the same list of numbers with a function that returns booleans and then one that returns lists of booleans. The output type changes each time, which shows why map has two type parameters.

Common Mistake: Confusing the value (x, y) with the type X * Y. The first is built from two values and the second from two types, and the chapter warns that it is easy to mix them up at first.

Important Questions:

  • What does declaring a type argument implicit do? It tells Rocq to infer that argument from the others, so you rarely write it, and you can still supply it by hand with @ when inference fails.
  • Why is fold described as more powerful than map and filter? It walks the whole list with an arbitrary combining function, so functions such as length and map itself can be written in terms of it.

Chapter 5: More Basic Tactics (Tactics)

Recommended path · Difficulty: Medium · Key topics: apply, apply with, injection, discriminate, tactics on hypotheses, specialize, generalize dependent, conditional rewrite, unfold, destruct with eqn

Tactics widens the toolkit needed for real proofs. The apply tactic finishes a goal from a hypothesis or lemma and turns the premises into new subgoals, with apply with for variables it cannot guess. Constructors are shown to be injective and disjoint, which injection and discriminate exploit through the principle of explosion. Next come tactics that work on hypotheses, forward reasoning, specialize, controlling the induction hypothesis with generalize dependent, rewriting with conditional statements, unfold, and destruct on compound expressions.

Key Points:

  • apply H works when the conclusion of H matches the goal, and its premises become new subgoals.
  • Constructors are injective (S n = S m gives n = m) and disjoint (O never equals S n).
  • discriminate closes any goal whose hypothesis equates two different constructors.
  • apply L in H reasons forward from a hypothesis, while plain apply reasons backward from the goal.
  • If a variable is introduced before induction, the induction hypothesis is too specific; keep it general or use generalize dependent.
  • destruct e eqn:E keeps the equation E, so information about the expression is not thrown away.
  • The chapter has 19 exercises, from one star to four.

Practice Tip: Prove that double is injective twice, once introducing m too early and once leaving it general. Compare the two induction hypotheses side by side.

Common Mistake: Using destruct on a compound expression without eqn:. The substitution removes every copy of the expression and the proof can no longer remember which case it is in.

Important Questions:

  • What two facts about constructors do injection and discriminate use? Constructors are injective, so equal results mean equal arguments, and different constructors never produce equal values.
  • Why does introducing m before inducting on n break the proof that double is injective? The induction hypothesis then talks about one fixed m instead of every m, so it cannot be applied to the predecessor.

Chapter 6: Logic in Rocq (Logic)

Recommended path · Difficulty: Medium · Key topics: Prop, conjunction, disjunction, negation, False, iff, exists, In, decidability and reflection, functional extensionality, excluded middle

Logic shows how Rocq states and proves ordinary logical reasoning. Propositions are first-class values of type Prop, and each connective gets its introduction and elimination tactics: split for and, left and right for or, destruct for assumptions, exfalso for contradictions, iff as two implications and exists with a witness. The chapter then programs with propositions, applies theorems like functions, compares booleans with Prop through reflection and ends with the logic of Rocq itself: functional extensionality as an axiom and why excluded middle is not provable.

Key Points:

  • Every well-formed proposition has type Prop, whether it is true or not.
  • Prove A /\ B with split, prove A \/ B with left or right, and use destruct to take them apart.
  • ~ P means P -> False, and from False anything follows (ex falso quodlibet).
  • To prove exists x, P you must give a witness; destructing an existential gives you both the witness and the proof.
  • Booleans are decidable and usable in match; propositions work with rewrite but cannot be tested in a function, and reflection links the two.
  • Functional extensionality is not provable in Rocq but can be added as an Axiom, and Print Assumptions shows which axioms a proof uses.
  • The chapter has 32 exercises, including a five-star one on classical axioms.

Practice Tip: After finishing any theorem, run Print Assumptions on it. It lists the axioms the proof depends on, which is a good habit before you add axioms of your own.

Common Mistake: Writing if n = 2 then ... in a function. A proposition is not decidable in general, so Rocq rejects it; use the boolean test n =? 2 instead.

Important Questions:

  • Why can Rocq not prove P \/ ~P for an arbitrary P? Proving a disjunction means choosing left or right, and for an unknown P there is no information to choose with; this is what makes Rocq’s logic constructive.
  • How do bool and Prop differ for a property such as evenness? A boolean function always computes an answer and can be used in match, while a Prop can state undecidable properties and works with rewrite; reflection lemmas let you move between them.

Chapter 7: Inductively Defined Propositions (IndProp)

Recommended path · Difficulty: Hard · Key topics: inductive propositions, evenness, less-than-or-equal, evidence, inversion, induction on evidence, regular expressions, remember, pumping lemma, reflect

IndProp is the longest and most important chapter. It defines propositions by rules instead of by functions: evenness, less-than-or-equal, transitive closures, permutations and the Collatz property, which cannot be a Fixpoint because Rocq cannot see that it terminates. Evidence for such a proposition is treated like data that you can build, take apart with inversion and use for induction. A regular-expression case study defines matching as an inductive relation, introduces remember, and develops the weak and strong pumping lemmas. The reflect idiom and an extended verified matcher follow, in a chapter with 52 exercises, the most in the book.

Key Points:

  • The constructors of an inductive proposition, such as ev_0 and ev_SS, are the primitive pieces of evidence.
  • An argument left of the colon in an Inductive is a parameter, and one right of the colon is an index.
  • inversion H considers every way the evidence H could have been built and drops impossible cases automatically.
  • Induction on evidence gives one case per constructor, with an induction hypothesis for each recursive premise.
  • le is defined by two rules, le_n and le_S, and exp_match has seven rules saying when a string matches each kind of regular expression.
  • remember e as x eqn:Eq makes an argument general so that induction on a hypothesis can work.
  • reflect P b says P holds exactly when b is true, and destructing it splits cases and rewrites in one step.

Practice Tip: Draw the derivation tree that shows ev 4 on paper, then build the same evidence in Rocq with apply ev_SS twice and apply ev_0. The two will line up rule by rule.

Common Mistake: Using case analysis when induction on the evidence is needed. The induction hypothesis then talks about the predecessor of the number, which is not even, so it does not help.

Important Questions:

  • Why is the Collatz property defined inductively and not with a Fixpoint? The recursive call on 3n + 1 is not smaller than n, so Rocq’s termination checker rejects both a recursive function and a recursive property; the inductive form simply lists the ways the property can hold.
  • What does inversion do on evidence of an inductive proposition? It splits into one case per constructor that could have produced the evidence, adds the equations those constructors imply, and discards cases that are contradictory.

Chapter 8: Total and Partial Maps (Maps)

Recommended path · Difficulty: Medium · Key topics: total maps, partial maps, string keys, higher-order update, functional extensionality, eqb_spec, map inclusion

Maps builds the dictionary data structure used by every later chapter. A total map is simply a function from strings to values with a default, and updating it means wrapping a new function around the old one, a neat piece of higher-order programming. Partial maps sit on top of that as total maps into option with the default None. The chapter switches from the custom id type of Lists to Rocq’s standard string, adds convenient notation, states the lemmas later chapters rely on and ends with map inclusion, which is useful for scoping rules in languages with variables.

Key Points:

  • A total_map A is a function string -> A, and t_empty v returns v for every key.
  • t_update m x v returns a new function that answers v for key x and asks the old map for any other key.
  • No separate lookup function is needed, because looking up a key is just function application.
  • A partial map is a total map into option A whose default is None.
  • Proofs about updates use eqb_spec for case analysis, and some of them need functional extensionality.
  • From this chapter on, standard library definitions are imported instead of earlier chapters.
  • The chapter has 6 exercises, most of them optional.

Practice Tip: Build a map that sends two string keys to true and everything else to false, then use Compute on several keys before and after an update to see shadowing at work.

Common Mistake: Expecting two maps that give the same answers to be equal automatically. Proving equality of functions needs the functional extensionality axiom from the Logic chapter.

Important Questions:

  • How does t_update add a binding without a list or tree? It builds a new function that checks whether the key equals x and returns v, and otherwise defers to the old map.
  • Why are partial maps built on total maps? A total map into option A reuses all the total-map lemmas, and a missing key simply gives None.

Chapter 9: The Curry-Howard Correspondence (ProofObjects)

Off the recommended path (optional) · Difficulty: Hard · Key topics: proof objects, propositions as types, dependent types, Qed and Defined, connectives as inductive types, equality, trusted computing base, proof irrelevance

ProofObjects asks what propositions and proofs really are. If evidence is data, then propositions are types and proofs are programs, which is the Curry-Howard correspondence. The chapter shows that tactic scripts quietly build proof terms you can inspect with Print and can also write by hand. Implication and forall turn out to be function types, and conjunction, disjunction, existentials, True, False and even equality are ordinary inductive types, which explains the tactics used earlier. It then explains why Rocq’s small type checker is the only part you must trust, and ends with proof irrelevance.

Key Points:

  • Propositions correspond to types and proofs correspond to programs; : reads as both “has type” and “is a proof of”.
  • P -> Q is shorthand for forall (_ : P), Q, so implication and quantification are the same kind of function type.
  • and has the single constructor conj, or has or_introl and or_intror, and ex packs a witness with its proof.
  • False has no constructors, so a match on it needs no branches.
  • Rocq’s equality has one constructor, eq_refl, and reflexivity is shorthand for applying it.
  • Qed rechecks the whole term from scratch, so a buggy tactic cannot sneak in a wrong proof.
  • The chapter has 18 exercises, with three advanced ones on propositional extensionality.

Practice Tip: Prove ev 4 with tactics, run Print on it, and compare the result with the hand-written term ev_SS 2 (ev_SS 0 ev_0). They are the same evidence.

Common Mistake: Believing every tactic is trusted. Only the final type checker is, which is why a tactic bug can break a script but not Rocq’s logic.

Important Questions:

  • What is the Curry-Howard correspondence? It is the pairing of propositions with types and proofs with programs, so that proving a statement means constructing a value of the matching type.
  • Why does Rocq reject a recursive function that never terminates? If it were accepted, it could be used to build a value of type False and prove anything.

Chapter 10: Induction Principles (IndPrinciples)

Off the recommended path (optional) · Difficulty: Hard · Key topics: nat_ind, generated induction principles, induction hypotheses, parameters and indices, informal proof templates, explicit proof terms

Every Inductive declaration makes Rocq generate an induction principle, a theorem named t_ind. This chapter shows nat_ind and list_ind and explains that the induction tactic is a wrapper that applies them. It gives the general recipe: one case per constructor, with a hypothesis for each recursive argument. You see how the exact form of a definition changes the principle, how principles for propositions such as ev work, and how to write induction proofs informally as templates. The last part builds proof terms with fix and uses induction ... using for non-standard principles.

Key Points:

  • For a type t the generated principle is t_ind, for example nat_ind or list_ind.
  • A constructor with no recursive arguments gives the case “P holds of c”, and each recursive argument adds an induction hypothesis.
  • Non-recursive types such as rgb also get a principle, even though it is rarely needed.
  • Two equivalent definitions of le give different principles, and the version with a general parameter is simpler.
  • The informal templates say: induct on the value or on the derivation, and give one case per constructor.
  • An explicit recursive function can build the proof term that nat_ind represents.
  • The chapter has 10 exercises, mostly about reading and writing the principles Rocq generates.

Practice Tip: Run Check nat_ind and Check list_ind and read each case aloud in plain English. Then do a short proof with apply nat_ind instead of induction to see the bookkeeping the tactic normally hides.

Common Mistake: Treating induction as magic. It only applies the generated principle, so with apply nat_ind you must introduce the step case’s variables by hand.

Important Questions:

  • What does the induction principle for natural numbers say? If a property holds for zero, and holds for S n whenever it holds for n, then it holds for every natural number.
  • Why does the form of an inductive definition matter? A general parameter, such as the left argument of le, produces a simpler induction principle than a version where that argument repeats in every constructor.

Chapter 11: A Formal Development of the Curry-Howard Correspondence (CurryHoward)

Off the recommended path · Difficulty: Hard · Key topics: natural deduction, simply-typed lambda calculus, typing rules, erasure, provability, typability, products, sums, the empty type

This chapter is absent from the older version 6.7 files and appears in the current 7.1 release. It makes the Curry-Howard correspondence precise instead of leaving it as an analogy. It embeds a small logic in Rocq, with atoms, implication and falsehood and a natural deduction proof system, and embeds the simply-typed lambda calculus with its typing rules. Erasing the programs from the typing rules leaves exactly the proof rules: variables match the axiom rule, functions match implication introduction and application matches implication elimination. The chapter proves the first main theorem, extends both sides to conjunction, disjunction, products, sums and the empty type, and ends with the converse theorem as an advanced section.

Key Points:

  • Propositions are built from atoms (named by strings), implication and false; negation and truth are derived from these.
  • The proof rules are axiom, implies introduction, implies elimination and false elimination, with assumptions kept in a list.
  • The programming language has variables, functions fun (x : t) => e and applications, with typing rules t-var, t-abs and t-app.
  • Erase the programs from t-var, t-abs and t-app and you get axiom, implies introduction and implies elimination.
  • The first theorem says a typing derivation for a program yields a proof of the corresponding proposition.
  • Conjunction corresponds to products, disjunction to sums and falsehood to the empty type.
  • The chapter has 16 exercises, and the last one proves the converse theorem.

Practice Tip: Write the typing derivation for fun (x:X) => fun (y:Y) => x on paper, then erase the programs. What remains is a proof of X -> (Y -> X).

Common Mistake: Mixing up the two levels. The chapter reasons about a logic embedded inside Rocq, which is different from using Rocq’s own logic, so keep the object logic and Rocq’s logic apart.

Important Questions:

  • What is the first main theorem of the correspondence? If a program has a type in some environment, then the corresponding proposition is provable from the corresponding assumptions.
  • Which typing rule matches false elimination? The rule t-magic, where a value of the empty type can be turned into a value of any type.

Chapter 12: Properties of Relations (Rel)

Off the recommended path (optional chapter) · Difficulty: Medium · Key topics: binary relations, partial functions, reflexive, transitive, symmetric, antisymmetric, equivalence, partial order, reflexive transitive closure

Rel is a short optional chapter on binary relations, written for readers who want more practice or who will need these definitions later. A relation on a set X is a function of type X -> X -> Prop. The chapter defines partial functions and the usual properties, namely reflexive, transitive, symmetric and antisymmetric, then equivalence relations, partial orders and preorders, using “less than or equal” on numbers as the running example. It ends with the reflexive and transitive closure of a relation and a second definition with a single step rule that has a simpler induction principle, plus proofs that the two agree.

Key Points:

  • The Rocq name relation always means a binary relation on one set.
  • A partial function relates each input to at most one output; <= is not one, since 0 is related to both 0 and 1.
  • An equivalence relation is reflexive, symmetric and transitive.
  • A partial order is reflexive, antisymmetric and transitive, and a preorder drops antisymmetry.
  • The reflexive transitive closure is the smallest such relation containing the original, and for next_nat it equals le.
  • The definition with a single step rule avoids a nondeterministic rule and gives a simpler induction principle.
  • The chapter has 12 exercises, all optional.

Practice Tip: Prove by hand that le is reflexive and transitive, then check each property one by one against the definition of a partial order.

Common Mistake: Using the closure definition with the free-standing transitivity rule in induction proofs. The chapter notes that its nondeterminism makes proofs awkward, which is why the single-step version exists.

Important Questions:

  • Why is <= not a partial function? Zero is related to zero and to one, and a partial function would then force 0 to equal 1, which is absurd.
  • How does a partial order differ from a preorder? Both are reflexive and transitive, but only a partial order must also be antisymmetric.

Chapter 13: Simple Imperative Programs (Imp)

Recommended path · Difficulty: Hard · Key topics: abstract syntax, arithmetic and boolean expressions, evaluation, states, commands, big-step semantics, determinism, tacticals, lia

Imp turns Rocq on another subject: a tiny imperative language with assignment, sequencing, conditionals and while loops. You define abstract syntax for arithmetic and boolean expressions, evaluation functions and an optimization proved sound, and a section on Rocq automation introduces try, ;, repeat, Ltac and lia. Evaluation is then redefined as an inductive relation with inference-rule notation. Variables live in a total-map state. Because loops may not terminate, command evaluation is a relation, and the chapter proves it deterministic and ends with exercises such as a stack-machine compiler and language extensions.

Key Points:

  • aexp, bexp and com are abstract syntax trees; the concrete syntax is left to the ImpParser chapter.
  • A state is a total map from variable names to numbers with a default of 0.
  • A Fixpoint evaluator for while is rejected because loops need not terminate, so evaluation is the relation st =[ c ]=> st'.
  • Inference rules are implications, with the premises above the line and the conclusion below it.
  • A relational definition handles partial and nondeterministic features, such as division by zero, that a function cannot.
  • try, ; and repeat shorten repetitive proofs, and lia decides linear integer arithmetic.
  • The chapter has 18 exercises, ranging from one to four stars.

Practice Tip: Turn off notations and coercions with the commands the chapter shows, look at the raw syntax tree of the factorial program, then turn them back on. You will see how much the notations hide.

Common Mistake: Trying to define command evaluation by plain recursion on a command. Rocq’s termination checker rejects the while case, so the definition has to be a relation.

Important Questions:

  • Why is command evaluation a relation and not a function? A while loop may run forever, so there is not always a final state, and Rocq functions must always terminate.
  • What does determinism of evaluation claim? Starting from the same state, a command can reach at most one final state, so the evaluation relation behaves like a partial function.

Chapter 14: Lexing and Parsing in Rocq (ImpParser)

Off the recommended path (optional chapter) · Difficulty: Medium · Key topics: lexical analysis, tokens, parser combinators, option with error messages, step-indexed parsing, recursive descent

The Imp chapter ignores how a programmer’s text becomes an abstract syntax tree. This optional chapter fills that gap by writing a lexer and a parser in Rocq’s functional language. The lexer classifies each character as white space, a letter, a digit or something else, and groups characters into tokens. The parser uses an option type that carries error messages, a few generic combinators such as many and expect, and a recursive-descent parser for identifiers, numbers, arithmetic and boolean expressions and commands. The chapter is deliberately terse, has no exercises and mainly shows that it can be done.

Key Points:

  • The lexer turns a string into a list of tokens by classifying characters, so the parser never sees raw text.
  • The parser returns optionE, a variant of option whose failure case holds an error message.
  • Generic combinators such as many and expect are reused to build the specific parsers.
  • The many combinator is step-indexed, meaning it carries an extra count that bounds how long it can run.
  • Separate functions parse identifiers, numbers, arithmetic expressions, boolean expressions and commands.
  • The chapter has no exercises, and the authors say its monadic idioms may take some work to understand.

Practice Tip: Skip straight to the Examples section at the end, as the authors suggest, run the example parses, then change the input strings slightly and read what the parser returns.

Common Mistake: Assuming the parser is verified. The Extraction chapter points out that nothing is proved about it, so only the evaluator it feeds is certified.

Important Questions:

  • Why does the Imp language need a parser at all? The earlier chapters define only abstract syntax trees, and a parser is what turns text a programmer types into those trees.
  • What does it mean that the many combinator is step-indexed? It takes an extra count that goes down with each recursive call, which lets Rocq see that the repetition must stop.

Chapter 15: An Evaluation Function for Imp (ImpCEvalFun)

Off the recommended path (optional chapter) · Difficulty: Hard · Key topics: step-indexed evaluator, fuel, option state, ceval_step, relational versus functional semantics, determinism

The Imp chapter gave up on defining command evaluation as a function and used a relation instead. This optional chapter shows how to make the function approach work after all. It begins with a broken evaluator that has no while case, then adds an extra argument that acts like fuel in a tank: evaluation runs until it finishes or the fuel runs out, in which case it returns no state. Small notation hides the plumbing. The chapter then proves that this step-indexed function and the relational semantics agree, in both directions, and uses that fact for a shorter proof of determinism.

Key Points:

  • The evaluator takes a step index and returns an option state, with None meaning it ran out of fuel.
  • The index does not count steps exactly; sequencing passes the same index to both recursive calls.
  • test_ceval lets you run an Imp program on a start state and see the final values.
  • A lemma shows that giving the evaluator more fuel never changes an answer it has already found.
  • The two evaluators coincide, so anything provable about the relation carries over to the function.
  • The chapter has 4 exercises, one rated four stars and advanced.

Practice Tip: Use test_ceval to run a small Imp program with an if from the empty state and read off the values of X, Y and Z. It runs the evaluator with a fixed amount of fuel and shows what the relational rules would also derive.

Common Mistake: Thinking the step index is a literal count of evaluation steps. The chapter warns it is not, and this matters when you read the correctness proof.

Important Questions:

  • Why does adding a step index make a recursive evaluator acceptable to Rocq? Every recursive call uses a smaller index, so the function is guaranteed to terminate, and running out of fuel is reported as None.
  • What does it mean that the two definitions of evaluation coincide? A command reaches a final state in the relation exactly when the step-indexed function returns that state for some amount of fuel.

Chapter 16: Extracting OCaml from Rocq (Extraction)

Off the recommended path · Difficulty: Medium · Key topics: Extraction, OCaml, Haskell, Scheme, Extract Inductive, Extract Constant, certified interpreter, driver program

Extraction is the payoff chapter for people who want working programs from verified definitions. You pick a target language, where OCaml is the most mature, Haskell mostly works and Scheme is a bit out of date, and ask Rocq to extract ceval_step to a file such as imp1.ml. Next you control how Rocq types and constants map to native OCaml ones, with a warning that making these translations sensible is your own responsibility. The chapter then assembles a complete Imp interpreter from the extracted evaluator and parser plus a hand-written driver compiled with ocamlc.

Key Points:

  • The Extraction command writes OCaml, Haskell or Scheme code for a definition and everything it depends on.
  • Extract Inductive and Extract Constant replace Rocq types and constants with native OCaml ones.
  • Nothing checks that these replacements preserve meaning, so you are responsible for them.
  • The driver, impdriver.ml, is written by hand and prints the first four memory locations of the final state.
  • Because ceval_step was proved equivalent to ceval, the extracted evaluator is a certified Imp interpreter.
  • The parser is not certified, since nothing was proved about it.
  • The chapter has no exercises, and later volumes carry the topic further.

Practice Tip: Follow the ocamlc command from the chapter to build the driver together with the extracted files, then run it on a small Imp program.

Common Mistake: Mapping a Rocq constant to a native operator without checking that the meanings agree. The chapter uses replacing minus with OCaml subtraction as its warning example.

Important Questions:

  • What does extraction give you that a proof alone does not? An executable program in OCaml, Haskell or Scheme taken from the verified definition, which can be compiled with a fast ordinary compiler.
  • What does “certified interpreter” mean in this chapter, and what is its limit? The evaluator is proved equivalent to the relational semantics, but the parser in front of it is unverified, and you also trust the target compiler.

Chapter 17: More Automation (Auto)

Recommended path · Difficulty: Medium · Key topics: auto, hint databases, Ltac match goal, eapply, eauto, existential variables, congruence

Auto introduces proof automation. The auto tactic searches for a proof built from intros and apply; it never fails and never leaves a half-done goal, and it uses the hypotheses plus a hint database that you can extend. The chapter then tackles the determinism proof of Imp, using Ltac and match goal to find the right hypotheses automatically, which makes proofs robust when the language grows. Next come eapply and eauto, which delay choosing a value, and the rules for existential variables. It ends with the congruence tactic for equalities and a few exercises on shortening proofs.

Key Points:

  • auto either solves the goal completely or leaves it untouched, and its default search depth is 5.
  • debug auto shows the whole search trace, while info_auto shows only the successful path.
  • Hint Resolve T : core adds a lemma to the global database, though separate hint databases are better style.
  • match goal finds hypotheses by shape, so a proof does not need to name them.
  • eapply and eauto leave existential variables to be filled in later, but they are noticeably slower.
  • All existential variables must be resolved by the time Qed is reached.
  • congruence decides equalities between uninterpreted functions and understands constructors.

Practice Tip: Take a proof you wrote by hand earlier, replace its middle with auto, and read the output of info_auto to see what it applied.

Common Mistake: Using eauto everywhere because it is more powerful. Experts reach for apply and auto first and switch to the e variants only when needed.

Important Questions:

  • Why is auto safe to try on any goal? It either finishes the goal or does nothing, so a failed search never breaks the proof state.
  • What does eapply do that apply does not? It does not demand concrete values for variables that do not appear in the goal, and instead leaves them as existential variables to be decided later.

Chapter 18: A Streamlined Treatment of Automation (AltAuto)

Off the recommended path · Difficulty: Medium · Key topics: tacticals, try, semicolon, repeat, assumption, subst, constructor, lia, congruence, intuition, auto, eauto, Ltac, match goal

AltAuto covers automation a second way, in a more streamlined order than Imp and Auto, and the book treats it as an alternative to Auto. It starts with a regular-expression optimizer whose manual proof is full of repetition, then fixes that with the tacticals try, ;, its local form and repeat. Tactics that avoid naming hypotheses follow: assumption, contradiction, subst and constructor. Then come automatic solvers (lia, congruence, intuition), search with auto and eauto, and Ltac with match goal, used to build a small tautology prover.

Key Points:

  • T; T' runs T' on every subgoal that T creates, and try T never fails.
  • repeat T never fails either, but it loops forever if T always succeeds without progress, as repeat simpl does.
  • constructor picks the first applicable constructor in definition order, which may not be the one you want.
  • lia handles linear integer arithmetic, congruence handles equalities, and intuition handles propositional tautologies.
  • match goal tries branches in order and backtracks into later branches when a tactic fails.
  • Unlike a term match, match goal patterns may reuse a metavariable and match several hypotheses.
  • The chapter has 11 exercises, including a four-star advanced one on writing your own proof-search tactic.

Practice Tip: Define a small tactic with Ltac that does destruct and then tries reflexivity on every branch, and use it to redo a few proofs from the Basics chapter in one shot.

Common Mistake: Running repeat with a tactic that always succeeds. The tactic evaluation does not have to terminate, so Rocq will simply hang.

Important Questions:

  • What is the difference between try and repeat? try T runs T once and does nothing if it fails, while repeat T keeps running it until it fails or stops making progress.
  • When would you use lia and when congruence? Use lia when the goal is about numbers and linear arithmetic, and congruence when it is about equalities where functions are treated as black boxes.

Postscript

Recommended path · Difficulty: Easy · Key topics: review, functional programming, logic, Rocq, later volumes, further reading

The Postscript is short. It looks back at the three themes of the volume: functional programming with immutable data, higher-order functions and polymorphism; logic, with inductive sets and relations, inductive proofs and proof objects; and Rocq itself, with its functional core language, core tactics and automation. It compares logic to calculus in mechanical and civil engineering as the mathematical basis of software engineering. Then it points forward to the later volumes, some readable straight after this one and some needing part of Volume 2, and lists further resources.

Key Points:

  • The review groups the volume into functional programming, logic and the Rocq proof assistant.
  • Logic plays the role for software engineering that calculus plays for mechanical or civil engineering.
  • Some later volumes can be read right after this one, while others need a few chapters of Volume 2.
  • Each volume’s Preface lists its own prerequisites.
  • Further resources include two Haskell books, Certified Programming with Dependent Types, the Coq’Art book and the DeepSpec 2017 summer school materials.
  • The Bibliography file lists all cited works and has no block of its own on this page.

Important Questions:

  • What three ideas does the Postscript say the volume covered? Functional programming, logic with inductive definitions and proofs, and the Rocq proof assistant with its tactics and automation.
  • Where does the book send you after finishing? To the later Software Foundations volumes, whose prefaces state their prerequisites, plus the further reading it lists.

How to Study This Book

This book is meant to be worked, not just read. The Preface says each chapter is a Rocq script to be read alongside an interactive session, so install Rocq before you start. The authors recommend VSCode with Docker, using the provided .tgz of source files, and the Preface also lists a native Rocq install, VsRocq, Proof General and RocqIDE as alternatives. If your course gives you its own copy of the files, use that one instead of the public release.

The book does not number its chapters. On this page the Preface is Chapter 0 and the chapters are numbered 1 to 18 in the order of the official table of contents. The book’s own dependency diagram marks a recommended path for a one-semester course: the Preface, then Chapters 1 to 7 in order (Basics, Induction, Lists, Poly, Tactics, Logic, IndProp), then Maps (8), Imp (13), Auto (17) and the Postscript. Everything else is an extension you can add afterwards.

Chapters 1 to 3 are the foundation and move quickly if you have programmed before. Spend your real time on Chapters 5 to 7. Chapter 5 teaches the tactics you will use for the rest of the book, Chapter 6 teaches how Rocq expresses logic, and Chapter 7 is the hardest because it has 52 exercises and the idea of evidence you can take apart and induct over. If Chapter 7 feels slow, that is normal; do the non-optional exercises first and leave the optional ones, including the extended regular-expression matcher, for a second pass.

Know the dependencies before you skip. ProofObjects (9) comes after IndProp, and both IndPrinciples (10) and CurryHoward (11) depend on ProofObjects. Rel (12) depends on IndProp. ImpParser (14), ImpCEvalFun (15) and Auto (17) depend on Imp (13), and Extraction (16) depends on ImpParser. AltAuto (18) is not drawn in the dependency diagram, and the CurryHoward chapter refers to it as an alternative to Auto, so one automation chapter is enough on a first pass.

Use the star ratings. One-star exercises should take a minute or two and are meant to be done as you read. Two stars take five to ten minutes and three stars ten to thirty, while four and five stars take half an hour or more. Doing just the non-optional, non-advanced exercises gives good coverage of the core. There are roughly 270 star-rated exercises across 16 chapters, and Auto and AltAuto repeat a few of them. The authors ask you not to post solutions publicly, because the book is used for graded courses.

Know what the book does not cover. It does not teach Hoare logic, program equivalence or static type systems; those are in Volume 2, Programming Language Foundations, and Volume 3, Verified Functional Algorithms, shows how to verify data structures. It is not a Rocq reference manual, and it does not teach other proof assistants. Finally, there is no PDF: the book is HTML pages and Rocq files, and the Bibliography page only lists the works cited.


Used In These Programs

This book is used for the Formal Methods course in: BS Computer Science and MS Computer Science. Browse all Formal Methods books or all Computer Science books.

Who Should Read This

The Preface says this book is meant for readers from advanced undergraduates to PhD students, so it suits BSCS and MS Computer Science students who have finished a first programming course and have some mathematical maturity, such as a discrete mathematics course with proofs by induction. It fits Formal Methods, Logic in Computer Science, Programming Languages and Software Verification courses. If you need to refresh induction and logic first, read Discrete Mathematics: An Open Introduction alongside the early chapters, and use Think Python if you want a gentler start on programming. It is not a book for complete beginners, not a quick exam-revision guide, and it asks you to install software and work every chapter at a computer.


Applicable Universities

This book is useful for students at Pakistani universities offering BS Computer Science and MS Computer Science, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

Official Copy of Software Foundations Volume 1

This book is free from its official site. There is no official PDF, so the legitimate free way to use it is the online edition, and the Rocq source files can be downloaded from the same page. Click the button below to open the official Logical Foundations page at softwarefoundations.cis.upenn.edu, where you can read the chapters in your browser or download the source files. The book is meant to be run in Rocq, so install it first.

→ Visit Official Page

FAQs

Is Software Foundations Volume 1 free?

Yes. The official site publishes the whole book free to read online and offers the source files as a download. The LICENSE file in the official distribution is the MIT License with the notice Copyright (c) 2026, which allows using, copying and sharing the files as long as the notice is kept. The authors also ask readers not to post exercise solutions in public places.

Is there a PDF of Logical Foundations?

No official PDF is offered. The book is published as web pages and as Rocq source files in a tarball named lf.tgz, because each chapter is meant to be run in the Rocq proof assistant. This page links only to the official site and does not host any file.

Which version is this, and is it Coq or Rocq?

This page describes Version 7.1, dated 24 August 2026 and tested with Rocq 9.0.0. Rocq was called Coq until 2025, and the Preface says the release is still in a transitional state, so both names appear. If your course still uses an older Coq release, use the files your instructor gives you.

How many chapters and exercises does it have?

Besides the Preface and the Postscript there are 18 chapters, and 16 of them have exercises. Counting the star-rated ones gives roughly 270 in total, rated from one to five stars, and a few repeat between the two automation chapters, Auto and AltAuto. Some exercises are marked optional or advanced.

Do I need to install anything, and is it good for beginners?

Yes, you need Rocq or the recommended VSCode and Docker setup, because the book is meant to be read alongside an interactive session. It assumes no background in logic or programming languages, but you must have programmed before and be comfortable with mathematical reasoning such as induction. It is not a first programming book.

What should I read after Logical Foundations?

The Postscript points to the later volumes of the series. Volume 2, Programming Language Foundations, covers operational semantics, Hoare logic and static type systems, and Volume 3, Verified Functional Algorithms, shows how to specify and verify data structures. Some can be read right after this volume and some need a few chapters of Volume 2, and each volume’s Preface lists its prerequisites.

Related Books

Software Foundations Volume 1 is a demanding but rewarding way to learn how proofs and programs fit together, with every definition checked by Rocq and hundreds of exercises to work. It is not a quick read or an exam guide, and it needs a working Rocq setup. Browse more Computer Science books for the rest of your semester.

Software Foundations, Volume 1: Logical Foundations by Benjamin C. Pierce, Arthur Azevedo de Amorim, Chris Casinghino, Marco Gaboardi, Michael Greenberg, Cătălin Hriţcu, Vilhelm Sjöberg and Brent Yorgey, with contributions from the people named on the official page. Version 7.1 (24 August 2026). Distributed under the MIT License (LICENSE file in the official distribution, Copyright (c) 2026). Official source: https://softwarefoundations.cis.upenn.edu/lf-current/index.html. This page links to the official site and does not host or copy the book.

Leave a Comment