Tactical Diagrammatic Reasoning

Sven Linker, Jim Burton, Mateja Jamnik

TL;DR

This paper introduces "tactics" to Speedith, an interactive proof assistant for Euler diagrams, enabling semi-automated theorem proving. These tactics aim to make diagrammatic proofs more accessible and understandable to humans by automating proof steps and prioritizing readability, unlike traditional sentential tactics.

What Problem Does This Paper Address?

Automated reasoning with diagrams has existed for some time, but existing tools are often less sophisticated than their text-based counterparts. A key challenge is automating the construction of proofs and providing explanations that are easy for humans to follow. While sentential theorem provers have "tactics" (sequences of inference rules) to automate proofs, these are often low-level and not designed for human comprehension. This paper addresses the need for more sophisticated, human-readable automated reasoning in diagrammatic systems, specifically for Euler diagrams.

Methods

The core contribution is the extension of the Speedith proof assistant with a set of "tactics." These tactics are inspired by those found in sentential theorem provers like Isabelle but are specifically designed for diagrammatic reasoning. The authors implemented combinators (like THEN, ORELSE, REPEAT) to build complex tactics from simpler ones. They categorized tactics into rule-level (applying a single rule), low-level (combining rules for specific sub-tasks like converting diagrams to Venn form), and high-level (orchestrating lower-level tactics to solve entire subgoals). A key design principle was to inform tactic development with metrics related to human readability, such as proof length and diagram "clutter."

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Diagrammatic Reasoning for Humans: The paper strongly emphasizes that the primary goal is not just to prove theorems but to make the proofs understandable to humans. This is a significant departure from many automated reasoning systems where proof readability is a secondary concern.
  • Tactics as Explanations: The authors propose that tactics can serve as a higher-level explanation of a proof strategy, capturing the "essence" of the proof rather than just a sequence of low-level inferences.
  • Readability Metrics Drive Design: The design of the tactics was directly influenced by empirical studies on human comprehension of diagrammatic proofs, particularly concerning "clutter." This data-driven approach to tactic design is novel.
  • Venn-Style vs. Copying Tactics: The paper highlights two main families of high-level tactics: "Venn-style" reasoning (transforming diagrams into a standard Venn form before combining) and "copying" tactics (leveraging rules to transfer information between diagrams). The authors suggest that Venn-style reasoning is traditional for Euler diagrams, but copying tactics can be highly effective.
  • Depth-First vs. Breadth-First: For Venn-style reasoning, they explore both depth-first and breadth-first approaches, noting that depth-first often leads to shorter proofs with less clutter, potentially mirroring human problem-solving strategies more closely.

Key Results

The paper describes the implementation of 13 tactics, categorized into rule-level, low-level, and high-level. They present examples of how these tactics operate on diagrams. An empirical evaluation using metrics like proof length and clutter is discussed, showing that the "Venn (Depth)" tactic (tactic 12) often produces proofs that are easier for readers to understand compared to the "Venn (Breadth)" tactic (tactic 11). For instance, one theorem proved with tactic 11 resulted in 355 units of overall clutter, while tactic 12 achieved 195 units. Another example shows tactic 13 (Copy Shading And Contours) producing significantly less maximal clutter for one theorem (27) compared to another (201), demonstrating the impact of theorem structure on tactic performance.

Limitations and Future Work

  • Limited Backtracking: The current implementation of tactic combinators only creates single proof states, meaning there's no support for backtracking if a tactic fails. Extending this to return lists of possible proof states is a planned future work.
  • Splitting Conjunctions/Disjunctions: The authors intend to implement rules that split conjunctions and disjunctions into multiple subgoals, which will naturally require new tactics.
  • User-Defined Tactics: Currently, users cannot define their own tactics; this requires writing Scala code, necessitating knowledge of the underlying implementation. The authors suggest this is necessary for ensuring correctness but acknowledge it limits extensibility for end-users.
  • Pedagogical Goals: A significant future direction is using Speedith and its tactics for teaching diagrammatic reasoning. They are developing a plugin for Openproof to integrate Speedith's engine with a diagram editor, allowing users to draw, manipulate, and check diagrams.
  • iCircles Library Improvements: The underlying graphical library (iCircles) sometimes produces suboptimal diagrams (e.g., duplicate labels, poor layout), and work is underway to improve its layout algorithm.

Summary updated

Abstract

© S. Linker, J. Burton & M. Jamnik. Although automated reasoning with diagrams has been possible for some years, tools for diagrammatic reasoning are generally much less sophisticated than their sentential cousins. The tasks of exploring levels of automation and abstraction in the construction of proofs and of providing explanations of solutions expressed in the proofs remain to be addressed. In this paper we take an interactive proof assistant for Euler diagrams, Speedith, and add tactics to its reasoning engine, providing a level of automation in the construction of proofs. By adding tactics to Speedith's repertoire of inferences, we ease the interaction between the user and the system and capture a higher level explanation of the essence of the proof. We analysed the design options for tactics by using metrics which relate to human readability, such as the number of inferences and the amount of clutter present in diagrams. Thus, in contrast to the normal case with sentential tactics, our tactics are designed to not only prove the theorem, but also to support explanation.
BibTeX
@inproceedings{linker2017tactical,
  author = {Sven Linker and Jim Burton and Mateja Jamnik},
  title = {{Tactical Diagrammatic Reasoning}},
  booktitle = {Apollo},
  year = {2017},
  doi = {10.17863/cam.25161},
}
Figure