interpolants

Interpolants are formulas that connect two related formulas A and B in a logical system. Given A and B, an interpolant I is a formula such that A implies I, I implies B, and the non-logical symbols occurring in I are contained in the intersection of the symbols used in A and in B. When A entails B (i.e., A → B is valid), Craig’s interpolation theorem guarantees the existence of such an I. The concept applies in propositional logic and in first-order logic, and it extends to many theories used in automated reasoning.

Interpolants can be semantic or syntactic. A semantic interpolant is defined by the entailment relationships alone, while a syntactic interpolant is an explicit formula constructed within a given language. In practice, interpolants are often obtained from a proof of A → B; for example, from a resolution refutation of A ∧ ¬B one can extract an interpolant. In satisfiability modulo theories (SMT), modern solvers can produce proofs that are transformed into theory-aware interpolants. Uniform interpolation is a stronger notion in which a single interpolant suffices for all B sharing the same common language, and existence of such interpolants depends on the theory in question.

Applications of interpolants appear in fields such as program verification and software safety, model checking and symbolic execution, and database query reformulation. They are used to over-approximate or constrain reachable states, to express constraints using only the shared vocabulary, and to facilitate reasoning about how one specification relates to another. In practice, interpolants help isolate the essential connection between A and B without introducing symbols not shared by both, making them useful in verification, analysis, and information flow control.