Computational Logic

Computational logic is the branch of computer science and mathematical logic that asks how reasoning itself can be turned into calculation.

12 frameworks, from 1929 to today · Theory Of Computation · Computer Science

still a working view ended · each leads to its entry below

Overview

Computational logic is the branch of computer science and mathematical logic that asks how reasoning itself can be turned into calculation1. Its practitioners build formal languages in which statements can be written precisely, give those languages meanings that machines can manipulate, and then design procedures that decide, search, or prove. The stakes are practical as well as philosophical: every database query engine, every chip-verification tool, every proof assistant checking a mathematical theorem, and every program that must be shown correct rests on ideas worked out in this field. Its history is a sequence of attempts to make logic do work — first on paper, then on machines, and finally at industrial scale.

From Leibniz's Dream to Frege's Notation

The ambition is old. Gottfried Wilhelm Leibniz, around 1700, imagined a calculus ratiocinator — a universal symbolic language in which disputes could be settled by computation rather than argument. He never built it, but the idea that reasoning might be reduced to rule-governed symbol manipulation persisted. The decisive step came from Gottlob Frege, whose Begriffsschrift (1879) introduced a two-dimensional logical notation with quantifiers, giving for the first time a language in which the full structure of mathematical statements could be expressed. Frege's project foundered on a contradiction in his system, pointed out by Bertrand Russell in 1901, but the notation survived: Russell and Alfred North Whitehead's Principia Mathematica (1910–1913) rebuilt logic on a firmer footing and demonstrated that substantial mathematics could be derived from axioms by explicit rules.

The crucial shift for computational logic was the realization that these derivations were mechanical. A proof in a formal system is a finite sequence of formulas, each either an axiom or obtained from earlier ones by a rule, and checking whether a sequence is a proof requires no insight — only careful symbol-matching. This is what makes logic a candidate for computation.

Hilbert's Program and the Discovery of Limits

David Hilbert, in the 1920s, posed the question that would define the field's foundations: could mathematics be shown consistent and complete by finitary means? The Entscheidungsproblem — the decision problem — asked more specifically whether there is a procedure that, given any statement of first-order logic, decides whether it is valid. Kurt Gödel's incompleteness theorems (1931) showed that any sufficiently strong consistent formal system contains true statements it cannot prove, dashing the broader program2. Then in 1936 Alonzo Church and Alan Turing independently answered the decision problem negatively: no such procedure exists. Turing's paper introduced the Turing machine and, with it, the notion of computability that would anchor all of computer science.

These negative results did not end the enterprise; they redirected it. If not everything is decidable, the productive questions become: which fragments of logic are decidable, and how efficiently? This question — decidability and complexity of logical fragments — became a permanent strand of the field3. A landmark early result was Thoralf Skolem's 1919–1920 procedure for the decidable class of first-order formulas now called the Bernays–Schönfinkel class, and later work by Mojżesz Presburger (1929) showed that arithmetic without multiplication is decidable. The pattern was set: restrict the language, and reasoning may become mechanical.

Resolution, Herbrand, and the First Theorem Provers

The mid-century brought the first concrete proof procedures. Jacques Herbrand's 1930 thesis showed how to reduce first-order validity to propositional satisfiability over a growing set of ground instances — the Herbrand universe4. In 1965 J. Alan Robinson published the resolution principle, a single inference rule for first-order logic: from clauses (disjunctions of literals) derive new clauses by unifying complementary literals5. Resolution was elegant and complete, and it made automated deduction a real engineering target.

The 1950s and 1960s saw the first programs. Martin Davis's 1954 program for Presburger arithmetic, and the Davis–Putnam procedure (1960) for propositional satisfiability, were early milestones. The Davis–Putnam–Logemann–Loveland (DPLL) procedure of 1962 gave a complete backtracking search for propositional satisfiability — the problem of deciding whether a Boolean formula in conjunctive normal form has a satisfying assignment. DPLL was not fast by later standards, but its structure — unit propagation, branching, backtracking — became the skeleton of nearly every modern SAT solver. Automated theorem proving grew as a community, with early successes in geometry and algebra, and with a persistent tension between general provers (powerful but slow) and specialized decision procedures (fast but narrow).

Logic as a Programming Language

A different route opened in the early 1970s. Robert Kowalski and colleagues at Edinburgh observed that a clause of the form conclusion if premise₁ and … and premiseₙ can be read declaratively as a logical implication or operationally as a procedure call. Alain Colmerauer's group in Marseille, working on natural-language processing, built the first Prolog interpreter around 19726. Prolog programs are sets of such clauses; running a program means asking a query and letting a resolution-based search find substitutions that make it true6. This was logic programming: computation as deduction7.

The idea was influential far beyond Prolog. It encouraged a view of programs as specifications and of execution as proof search, and it fed into the design of deductive databases. In 1978 the Datalog language — function-free Horn clauses — was introduced (the name came later, in the 1980s) as a clean model for recursive queries8. Datalog's restriction made evaluation tractable and its semantics well-behaved, and it became the theoretical core of deductive databases, later influencing query languages and, much later, modern rule engines and program-analysis tools.

Axiomatic Semantics and the Problem of Correct Programs

Parallel to proof search ran the question of program correctness. In 1967 Robert Floyd proposed attaching assertions to flowchart edges and proving them inductively. C. A. R. Hoare's 1969 paper on an axiomatic basis for computer programming turned this into a compositional proof system: the Hoare triple {P} S {Q} asserts that if precondition P holds before statement S, then postcondition Q holds afterward, with rules for assignment, sequencing, conditionals, and loops9. Hoare logic made it possible to reason about programs in the same formal style as mathematics, and it spawned a family of program logics (separation logic, dynamic logic, refinement calculi) that remain central to software verification1011.

The practical counterpart was interactive theorem proving: systems in which a human guides a machine through a proof, with the machine checking each step12. The LCF system (Robin Milner, Edinburgh, early 1970s) introduced the idea of a small trusted kernel in which all proofs are constructed, a design that survives in HOL, Isabelle, and Coq. These systems made large formalizations possible — the four-colour theorem in Coq (2005), the odd-order theorem in Isabelle (2012) — and they established a working division of labour between human insight and machine checking.

Model Checking and the Verification Boom

By the late 1970s, hardware and protocols were becoming too complex for hand proof. In 1981 Edmund Clarke and E. Allen Emerson, and independently Jean-Pierre Queille and Joseph Sifakis, introduced model checking: given a finite-state system and a specification in temporal logic — a logic for reasoning about "always," "eventually," and "until" — automatically check whether the system satisfies the specification. The method was fully automatic and produced counterexamples when it failed, which made it usable by engineers. Its weakness was state explosion: the number of states grows exponentially with the number of components. Techniques such as symbolic model checking with binary decision diagrams (Ken McMillan, early 1990s) and later bounded model checking and SAT-based approaches pushed the method to industrial scale, and model checking became a standard tool in chip design.

Description Logics and Knowledge Representation

A separate lineage grew from the desire to represent knowledge — classes, individuals, and their relationships — in a logic with decidable reasoning. Description logics, developed from the mid-1980s by researchers including Ronald Brachman, Hector Levesque, and Franz Baader, are families of formal languages for concepts and roles, designed so that subsumption (is one concept a subset of another?) and instance checking are decidable. They underpin ontologies and the Semantic Web's OWL language, and they connect to the older knowledge-representation tradition that sought to encode commonsense and domain knowledge in machine-usable form. The recurring trade-off — expressive power versus decidability — is the same one that shaped the field's foundations13.

Satisfiability Modulo Theories and the Modern Solver

The most recent major turning point was the realization that many reasoning problems mix propositional structure with domain-specific theories: arithmetic, arrays, bit-vectors, uninterpreted functions. Satisfiability modulo theories (SMT), developed from the late 1990s, combines a SAT solver — deciding the propositional skeleton — with theory solvers that check consistency in each domain. The DPLL(T) architecture made this combination efficient, and modern SMT solvers such as Z3 and CVC5 are now embedded in program verifiers, symbolic execution engines, and synthesis tools. The SAT side itself was transformed by conflict-driven clause learning (CDCL) in the late 1990s and 2000s, which turned DPLL's backtracking search into a learning system capable of handling industrial instances with millions of variables.

Where the Field Stands

Today computational logic is less a single discipline than a toolkit shared across computer science. SAT and SMT solvers are infrastructure; model checking is routine in hardware verification; interactive provers verify compilers and operating-system kernels; Datalog and its extensions power program analysis and network configuration; description logics underlie biomedical ontologies141513. The foundational questions remain open: the complexity of deciding richer fragments, the scalability of proof search, the integration of learning with deduction, and the boundary between what can be decided and what must be approximated. The through-line from Leibniz to the present is unchanged — the conviction that reasoning, properly formalized, can be carried out by a machine, and the steady discovery of how much, and how little, that conviction can deliver.

References

  1. Computational logic, Wikipedia
  2. Gödel's incompleteness theorems, Wikipedia
  3. Fragment (logic), Wikipedia
  4. Herbrand's theorem, Wikipedia
  5. Resolution (logic), Wikipedia
  6. Prolog (History, introduction), Wikipedia
  7. Logic programming, Wikipedia
  8. Datalog (History), Wikipedia
  9. Hoare logic, Wikipedia
  10. Separation logic, Wikipedia
  11. Dynamic logic (modal logic), Wikipedia
  12. Proof assistant, Wikipedia
  13. Description logic, Wikipedia
  14. Formal verification, Wikipedia
  15. Deductive database, Wikipedia

The frameworks of Computational Logic

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1929-Present

    Decidability and Complexity of Logical Fragments

    Which logical fragments are decidable and how complex?

    Fly to its tower in Nousfarer

  2. 1931-Present
  3. 1965-Present

    Automated Theorem Proving

    Can machines find proofs automatically?

    About Automated Theorem Proving
    Automated Theorem Proving (ATP) emerged in the 1960s as the first systematic effort to mechanize logical deduction. Its central question was: how much of human-style reasoning in first-order logic can be turned into an algorithm? ATP aimed at full first-order deduction, using a single, uniform inference rule—the resolution principle—that is both sound and complete. However, completeness came at a steep computational cost: unrestricted resolution explores an enormous search space, and for many problems the procedure never terminates in practice. ATP therefore became a craft of heuristics and search strategies, establishing the foundational trade-off that would define computational logic: how to balance expressiveness with tractability.
    Core Curriculum
    A first course in ATP typically covers four clusters of concepts that build on each other:
    1. Logical foundations for refutation: The starting point is First-Order Logic as the language of theorems. Formulas are transformed into Clausal Normal Form (CNF) via Skolemization (removing existential quantifiers) and Herbrand's Theorem, which grounds first-order validity in propositional satisfiability over a finite set of ground instances. This sets up the refutation paradigm: to prove a theorem, assume its negation and derive a contradiction.
    1. The inference engine: The Resolution Principle is the core rule: from two clauses containing complementary literals, infer a new clause. Unification makes resolution work with variables by finding the most general substitution that makes literals identical. Inference Rules are limited to resolution and factoring, and the overall method is Proof by Refutation—showing that the negation of the theorem together with the axioms leads to the empty clause (a contradiction).
    1. Controlling the search: Because resolution generates many irrelevant clauses, Search Strategies (e.g., breadth-first, set of support, linear resolution) and Heuristics (e.g., weighting clauses, preferring short clauses) are essential to prune the search space. Subsumption eliminates clauses that are logically weaker than existing ones, further reducing redundancy.
    1. Extensions for equality and theories: Basic resolution cannot handle equality efficiently. Paramodulation extends resolution to reason about equality by allowing substitution of equals for equals. This leads to Equational Reasoning and Term Rewriting as specialized inference methods. Decision Procedures for specific theories (e.g., Presburger arithmetic) can be integrated as subroutines, though they are more characteristic of later SMT solving.
    Intellectual History
    The roots of ATP lie in early 20th-century logic. Jacques Herbrand (1930) provided a key precursor with Herbrand's theorem, which connects first-order validity to propositional satisfiability. In the 1950s, work on automated deduction began with the Davis–Putnam procedure (1960) for propositional logic, but the breakthrough for first-order logic came in 1965 when Alan Robinson published "A Machine-Oriented Logic Based on the Resolution Principle." Robinson showed that a single inference rule—resolution combined with unification—is complete for first-order logic, giving ATP a clean theoretical foundation.
    Throughout the late 1960s, researchers developed heuristics and refinements to make resolution practical. Larry Wos and colleagues introduced paramodulation (1969) for equality reasoning and pioneered the use of subsumption and set-of-support strategies. Early ATP systems such as Otter (later, 1980s) and AProS built on these ideas. Despite these advances, ATP remained limited to relatively small problems; the search space was simply too large for many mathematical theorems.
    This limitation directly motivated the next framework in computational logic: Logic Programming (LP), which emerged around 1970. LP narrowed the logic to Horn clauses and used SLD-resolution, a goal-directed, linear form of resolution that made the search space far more predictable. LP traded expressiveness for efficiency, treating logical formulas as executable programs. ATP and LP coexisted, with ATP continuing to be used for hard mathematical problems (e.g., the Robbins conjecture proved by William McCune's EQP in 1996, a later success).
    Later frameworks such as SAT Solving (1990s) and SMT Solving (2000s) further specialized the trade-off: SAT solvers handle propositional logic with huge formulas, while SMT solvers combine SAT with decision procedures for theories. ATP remains relevant for problems rich in quantifiers, and modern systems often integrate techniques from multiple frameworks. The legacy of ATP is the foundational insight that deduction can be mechanized, but only with careful management of the search space—a lesson that shaped all subsequent computational logic.
    The 16 concepts its tower teaches
    • Clausal Normal Form
    • Decision Procedures
    • Empty Clause
    • Equational Reasoning
    • First-Order Logic
    • Herbrand's Theorem
    • Heuristics
    • Inference Rules
    • Paramodulation
    • Proof by Refutation
    • Resolution Principle
    • Search Strategies
    • Skolemization
    • Subsumption
    • Term Rewriting
    • Unification

    Fly to its tower in Nousfarer

  4. 1967-Present

    Axiomatic semantics

    How can we prove programs correct?

    Fly to its tower in Nousfarer

  5. 1972-Present

    Logic Programming

    Can logic serve as a programming language?

    Fly to its tower in Nousfarer

  6. 1972-Present

    Proof assistant

    Can machines check mathematical proofs?

    Fly to its tower in Nousfarer

  7. 1975-Present

    Knowledge Representation and Ontologies

    How can knowledge be represented for machine reasoning?

    Fly to its tower in Nousfarer

  8. 1978-Present

    Deductive database

    How can databases answer recursive queries logically?

    Fly to its tower in Nousfarer

  9. 1981-Present

    Model Checking

    Can we automatically verify finite-state systems?

    Fly to its tower in Nousfarer

  10. 1985-Present

    Description logic

    How can concepts and roles be reasoned about decidably?

    Fly to its tower in Nousfarer

  11. 1996-Present

    Conflict-Driven Clause Learning

    How can SAT solvers learn from conflicts?

    Fly to its tower in Nousfarer

  12. 1998-Present

    Satisfiability Modulo Theories

    How can SAT solvers reason with theories?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Decidability and Complexity of Logica…Formal Foundations of Computation and…Automated Theorem ProvingAxiomatic semanticsLogic ProgrammingProof assistantKnowledge Representation and Ontologi…Deductive databaseModel CheckingDescription logicConflict-Driven Clause LearningSatisfiability Modulo Theories

Beyond the field

Where Computational Logic's ideas came from in other fields, and what they led to there: the strongest 12 of 47 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Computational Logic is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Computational Logic

Related fields

Fields its ideas are linked to

More in Theory Of Computation

See where Computational Logic sits on the Map of Human Knowledge