Structure Preserving Logical Inference

44 concepts33 papers1 proposal

Most modern automated reasoners—such as Boolean Satisfiability (SAT) and Quantified Boolean Formula (QBF) solvers—require inputs to be formatted in Conjunctive Normal Form (CNF) or clause form. CNF is highly uniform, consisting simply of a conjunction of disjunctions of literals. This simplicity makes it easy to implement efficient low-level data structures like watched literals.

However, this uniformity comes at a steep cost. Real-world problems rarely originate as a flat list of clauses; they are inherently hierarchical, featuring nested implications, equivalences, and high-level constraints. As noted by Juan Antonio Navarro Pérez and Andrei Voronkov in Generation of Hard Non-Clausal Random Satisfiability Problems, standard clausification processes shatter this hierarchical structure, creating a persistent need for solvers capable of native, non-clausal reasoning.

To understand why researchers have spent decades developing structure-preserving inference techniques, we must look at the two fundamental flaws of traditional clausal conversion: exponential size explosion and heuristic blindness.

The Cost of Clausification

When converting a general logical formula into CNF, a naive application of distributive laws can cause an exponential increase in the number of literals. As Neil V. Murray and Erik Rosenthal observe in Path Resolution with Link Deletion, operating directly on non-clausal representations like Negation Normal Form (NNF) completely avoids this literal explosion.

To bypass this size explosion in standard solvers, practitioners typically use the Tseitin transformation, which introduces auxiliary variables to represent intermediate gates. While this keeps the formula size linear, it introduces a new problem: it distorts the original variable space. Alessandro Previti demonstrates in Prime Compilation of Non-Clausal Formulae that when computing minimal logical consequences (prime implicates), these auxiliary variables pollute the search space. Operating directly on the non-clausal structure ensures that the reasoning process remains strictly relevant to the original problem variables.

Beyond size, flattening a formula destroys its semantic context. When an expert defines a rule as an implication ($A \rightarrow B$), they provide a directional heuristic. Richard Fikes and Gary G. Hendrix argued in A Network-Based Knowledge Representation and Its Natural Deduction System that preserving this natural structure allows deduction engines to navigate search spaces more effectively by following the logical flow of the original assertions.

Standard Clausification:
[Hierarchical Formula] ──(Tseitin Transformation)──> [Flat Sea of Clauses] (Lost Context)

Structure-Preserving:
[Hierarchical Formula] ─────────────────────────────> [Direct Non-Clausal Inference] (Retained Context)

The Core Mechanisms of Non-Clausal Inference

If we do not flatten a formula into clauses, how do we reason over it? Researchers have developed several distinct paradigms to perform inference directly on structured logic:

  • Polarity-Based Simplification: Instead of resolving clauses, algorithms can operate on general quantifier-free formulas by identifying matching atoms with opposite polarity. As Mark E. Stickel showed in A Nonclausal Connection-Graph Resolution Theorem-Proving Program, the system can substitute these atoms with truth values and apply structural simplification rules directly, maintaining the pragmatic intent of the logical statements.
  • Semantic Graphs and Path Dissolution: Formulas can be represented as directed graphs where paths represent conjunctions. In Path Dissolution: A Strongly Complete Rule of Inference, Neil V. Murray introduced a method to systematically eliminate paths containing contradictions without altering the surrounding formula structure, guaranteeing strong completeness without clausal overhead.
  • Algebraic Polynomials: Logic can be translated into abstract algebra. Deepak Kapur and Paliath Narendran developed an approach in An Equational Approach to Theorem Proving in First-Order Predicate Calculus that treats logical formulas as Boolean polynomials. This allows theorem proving to be handled via polynomial reduction, preserving natural equivalences.

Why Structure Preservation Works

The primary reason structure-preserving inference outperforms clausal reasoning on complex tasks comes down to how information flows during the search process.

1. Contextual Fact Propagation

In flat CNF solvers, Boolean Constraint Propagation (BCP) is blind to the overall hierarchy; it only triggers when a clause is reduced to a single unassigned literal. In contrast, structure-preserving systems can propagate facts through nested connectives.

Mukesh Dalal proved in Efficient Propositional Constraint Propagation that propagating facts through hierarchical NNF structures is strictly more powerful than standard BCP. By preserving the nesting of operators, the system can deduce truths and identify contradictions that are completely invisible to a solver working on a flattened format.

2. Symmetric Pruning via Duality

CNF solvers are inherently asymmetric: they are highly optimized for detecting conflicts (falsifying assignments) but struggle to recognize when a sub-problem has been satisfied. By maintaining structural awareness, a solver can exploit duality.

For instance, Lintao Zhang introduced a framework in Solving QBF by Combining Conjunctive and Disjunctive Normal Forms that maintains a complete Disjunctive Normal Form (DNF) description alongside the CNF. This allows the solver to prune the search space symmetrically, identifying satisfied branches just as quickly as conflicted ones. Similarly, Alexandra Goultiaeva and Fahiem Bacchus demonstrated in Exploiting QBF Duality on a Circuit Representation that propagating both primal and dual truth values through an explicit circuit representation allows a solver to immediately skip entire search branches that cannot influence the final output.

3. Targeted Interventions

When a flat solver encounters a dead end, it learns a conflict clause, but it cannot easily trace the failure back to a high-level design flaw in the formula. Structure preservation enables localized, intelligent backtracking and formula expansion.

Sunil Issar leveraged this in Path-Focused Duplication: A Search Procedure for General Matings, demonstrating that a prover tracking the original hierarchy of logical operators can trace search impasses back to specific quantifiers or sub-formulas. Instead of duplicating the entire formula globally, the system performs targeted, local duplication at the exact failure point, preventing search space explosion.

Application Across Domains

The necessity of preserving structural logic manifests across several distinct subfields of computer science:

  • AI Planning: In automated planning, compiling high-level derived predicates into flat conditional effects degrades performance. Sylvie Thiebaux et al. showed in In Defense of PDDL Axioms that native support for axioms allows search heuristics to accurately calculate goal distances. Furthermore, Guillem Francès and Hector Geffner demonstrated in Effective Planning with More Expressive Languages that retaining first-order structural information prevents the loss of logical dependencies, giving the planner a clearer understanding of domain physics.
  • Satisfiability Modulo Theories (SMT): When reasoning about bit-vectors, translating arithmetic operations into bit-level logic ("bit-blasting") destroys the underlying mathematical context. Andreas Fröhlich et al. demonstrated in Stochastic Local Search for Satisfiability Modulo Theories that maintaining word-level structure allows search algorithms to exploit arithmetic relationships directly, vastly outperforming bit-blasted local search.
  • Model Counting: In model counting, flattening high-level constraints into CNF strips away structural advantages. Suwei Yang et al. showed in On Top-Down Pseudo-Boolean Model Counting that preserving the native structure of Pseudo-Boolean formulas during top-down model counting provides critical structural cues that drastically accelerate the counting process.

Ultimately, structure-preserving logical inference works because it treats the syntax of a problem as a valuable map. By refusing to flatten the problem into a uniform but unreadable sea of clauses, these techniques ensure that the solver can use the original architecture of the problem to guide its search.

Key Foundational Work

A Nonclausal Connection-Graph Resolution Theorem-Proving Program (1982) — contributed 2 concept elements to this direction.
A Network-Based Knowledge Representation and Its Natural Deduction System (1977) — contributed 1 concept elements to this direction.
Vocabularies for Problem Solver State Descriptions (1977) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 32 papers
  2. Version 1 · 2026-10-04 · 31 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_structural_logic_preservation_c5c219a6,
  title = {structural logic preservation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-logic-preservation/rdr_c5c219a625ca4d0da3f82646033dd877},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_structural_logic_preservation_c5c219a6_v2,
  title = {structural logic preservation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-logic-preservation/rdr_c5c219a625ca4d0da3f82646033dd877/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake