A Proof-Checker for Dynamic Logic

Steven D. Litvintchouk, Vaughan R. PrattIJCAI 1977

In 1977, S.D. Litvintchouk and Vaughan Pratt introduced a practical tool for a then-emerging formal system: Dynamic Logic (DL). This work marked a significant shift from purely theoretical logic toward automated software verification, providing a unified framework for reasoning about program behavior. By implementing a proof-checker in LISP, the authors demonstrated that computers could effectively validate complex arguments regarding program correctness and termination.

The Formalism of Dynamic Logic

Dynamic Logic treats programs as modalities, akin to "necessarily" or "possibly" in standard modal logic. In this view, programs act as operators that modify the truth of statements. For instance, the expression $[a]P$ signifies that "after every execution of program $a$, statement $P$ must hold." This approach allows DL to subsume earlier, more specialized systems like Floyd-Hoare logic (for partial correctness) and Manna-Waldinger logic (for total correctness).

Common expressions and properties represented in Dynamic Logic notation.

The authors also noted that reasoning about deterministic programs as if they were nondeterministic can often simplify the proof process. By decomposing program behaviors into five basic constructs—Assignments, Tests, Alternation, Sequencing, and Iteration—DL can formalize almost any first-order conversation about a program's input/output behavior.

System Architecture and Methodology

The authors implemented their proof-checker in approximately 1,800 lines of LISP on a PDP-10. The system does not automatically generate proofs; instead, it rigorously verifies human-written proofs to ensure no logical leaps or errors were made. The core mechanism is the "Show" Rule, which operates in two distinct phases:

  1. IDENTIFY (The Unification Phase): The system takes user-provided "templates" (simplified propositional versions of the formulas) and attempts to "unify" or match them with the actual, complex logical formulas. This ensures that the structure of the argument is consistent.
  2. VERIFY (The Modal SAT Phase): Once the structure is confirmed, the system uses a satisfiability tester for modal propositional logic. It eliminates "box" and "diamond" modalities to see if the underlying logic holds.

To bridge the gap between abstract logic and actual programming, the system incorporates a routine for Presburger arithmetic. This allows the checker to understand basic integer math (like $X := X + 1$) without requiring every algebraic step to be explicitly proven.

Handling Loops and Invariants

While DL provides a robust framework for sequential code, loops remain a significant challenge. The system utilizes specific axioms for iteration, but proving properties about loops often requires human-provided invariants.

Notation for invariants and convergence in Dynamic Logic.

Proving properties like "convergence" or finding the "weakest invariant" remains the most difficult part of the verification process, often requiring clever human insight to guide the automated checker.

Evaluation and Results

The tool was evaluated using several classic benchmarks in program verification:

  • The Manna-Pnueli Program: A notoriously "obscure" flowchart program designed to test termination proofs. The system successfully checked the proof, which traditionally requires complex arguments about well-founded sets.
  • The Knuth-Morris-Pratt (KMP) Algorithm: The authors applied the tool to verify substantial portions of the correctness proof for this classic pattern-matching algorithm.

The results demonstrated that despite the theoretical complexity of modal logic, a Davis-Putnam-based satisfiability tester could be highly efficient for the types of formulas encountered in real-world program proofs.

Conclusion and Legacy

Litvintchouk and Pratt's work demonstrated that Dynamic Logic could serve as a "one-stop shop" for program verification. While the system was "batch-oriented" rather than interactive—requiring users to submit entire proof files—it laid the groundwork for modern intelligent programming environments. The authors envisioned a future where these logical "black boxes" are integrated into development tools to catch errors in real-time or help generate reliable software automatically.

Summary updated

BibTeX
@inproceedings{litvintchouk1977proof,
  author = {Steven D. Litvintchouk and Vaughan R. Pratt},
  title = {{A Proof-Checker for Dynamic Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure