Equivalence-preserving preprocessing of propositional logic formulae using existential graphs and implication hypergraphs

  • Jordina Francès de Mas

Student thesis: Doctoral Thesis (PhD)


Current approaches to propositional logic (PL) solving and simplification are search-based, require flattening transformations, backtracking, and use many non-equivalence-preserving techniques. This thesis presents an alternative approach, which is based on the study of Peirce's existential graphs and the analysis of implication graphs, capable of simplifying PL formulae in arbitrary form by applying novel deep inference rules that can detect redundancies across nesting levels. In particular, we first introduce a set of novel simplification techniques based on the exploration of binary implication graphs, which are guaranteed to be equivalence-preserving, monotonically decrease the size of the problem, and result in terminating and confluent procedures (up to variable renaming). We next introduce a novel PL formula representation able to capture all of its implication information in a tractable manner, which we call binary implication hypergraph. This novel PL formula encoding in the form of a directed hypergraph allows us to derive a suite of even more powerful simplification rules with similar guarantees.

As a proof of concept, we provide an algorithm for a subset of our techniques and study its complexity, which is in line with the complexity limits found elsewhere in the literature. We then implement it and test it on SAT benchmarks with up to hundreds of thousands of variables, clauses and literals, which proves the practical feasibility of our framework, and compare our results to and in combination with the state-of-the-art, obtaining very promising results.

Both existential graphs and our novel hypergraph formula representation offer a fresh view of preprocessing never explored before, which results in a systematic, explainable, technology-independent, equivalence-preserving method for simplifying PL formulae in arbitrary form, and constitutes a step forward on the quest for greater reasoning automation and shorter proofs, and opens the door to a whole new body of research.
Date of Award12 Jun 2024
Original languageEnglish
Awarding Institution
  • University of St Andrews
SupervisorJuliana Kuster Filipe Bowles (Supervisor)


  • Propositional logic simplification
  • Equivalence-preserving preprocessing
  • Automated reasoning
  • Automated deduction
  • Inference
  • Existential graphs
  • Knowledge representation
  • Implication graphs
  • Hypergraphs
  • Propositional satisfiability

Access Status

  • Full text embargoed until
  • 7 May 2026

Cite this