- Atlas
- Computer Science
- Computational Logic
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
- Decidability and Complexity of Logical Fragments 1929-Present
- Formal Foundations of Computation and Logic 1931-Present
- Automated Theorem Proving 1965-Present
- Axiomatic semantics 1967-Present
- Logic Programming 1972-Present
- Proof assistant 1972-Present
- Knowledge Representation and Ontologies 1975-Present
- Deductive database 1978-Present
- Model Checking 1981-Present
- Description logic 1985-Present
- Conflict-Driven Clause Learning 1996-Present
- Satisfiability Modulo Theories 1998-Present
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
- Computational logic, Wikipedia
- Gödel's incompleteness theorems, Wikipedia
- Fragment (logic), Wikipedia
- Herbrand's theorem, Wikipedia
- Resolution (logic), Wikipedia
- Prolog (History, introduction), Wikipedia
- Logic programming, Wikipedia
- Datalog (History), Wikipedia
- Hoare logic, Wikipedia
- Separation logic, Wikipedia
- Dynamic logic (modal logic), Wikipedia
- Proof assistant, Wikipedia
- Description logic, Wikipedia
- Formal verification, Wikipedia
- 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.
- 1929-Present
Decidability and Complexity of Logical Fragments
Which logical fragments are decidable and how complex?
- 1931-Present
Formal Foundations of Computation and Logic
What is computation and what are its limits?
- 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 CurriculumA first course in ATP typically covers four clusters of concepts that build on each other:- 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.
- 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).
- 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.
- 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 HistoryThe 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
- 1967-Present
- 1972-Present
- 1972-Present
- 1975-Present
Knowledge Representation and Ontologies
How can knowledge be represented for machine reasoning?
- 1978-Present
Deductive database
How can databases answer recursive queries logically?
- 1981-Present
- 1985-Present
Description logic
How can concepts and roles be reasoned about decidably?
- 1996-Present
Conflict-Driven Clause Learning
How can SAT solvers learn from conflicts?
- 1998-Present
Satisfiability Modulo Theories
How can SAT solvers reason with theories?
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.
Formal Foundations of Computation and Logic influenced by Decidability and Complexity of Logical Fragments
The negative solution of the decision problem for first-order logic by Church and Turing built directly on the decidability results and techniques of F1, and in turn founded the formal theory of computation.
Carried by Alonzo Church; Alan Turing.
Logic Programming grew out of Automated Theorem Proving
Logic programming grew directly out of resolution theorem proving: Kowalski's procedural interpretation of Horn clauses turned Robinson's resolution rule into a computation mechanism, and Colmerauer's Prolog implemented it.
Carried by Robert Kowalski; Alain Colmerauer.
Deductive database grew out of Logic Programming
Datalog and deductive databases emerged as a restriction of logic programming to function-free Horn clauses, giving a tractable model for recursive queries.
Carried by Hervé Gallaire; Jack Minker.
Description logic grew out of Knowledge Representation and Ontologies
Description logics were developed as a decidable formalization of the structured inheritance networks and frame-based knowledge representation systems that had arisen in F7.
Carried by Ronald J. Brachman; Hector J. Levesque.
Satisfiability Modulo Theories influenced by Conflict-Driven Clause Learning
Satisfiability modulo theories built directly on CDCL SAT solvers, using them as the Boolean engine while adding theory-specific decision procedures for arithmetic, arrays, and other domains.
Carried by Clark Barrett; Cesare Tinelli.
Automated Theorem Proving influenced by Decidability and Complexity of Logical Fragments
Robinson's resolution principle was designed as a complete proof procedure for first-order logic, addressing the same validity problem whose decidability had been mapped by F1.
Carried by J. Alan Robinson.
Automated Theorem Proving influenced by Formal Foundations of Computation and Logic
Automated theorem provers implemented mechanical proof search on the formal systems and computability notions established by F2, using formal proofs as objects that machines could manipulate.
Carried by Martin Davis; Hilary Putnam.
Axiomatic semantics influenced by Formal Foundations of Computation and Logic
Floyd and Hoare's axiomatic semantics treated programs as formal objects and proofs of correctness as derivations in a logical system, extending the formalist approach of F2 to imperative code.
Carried by Robert W. Floyd; C. A. R. Hoare.
Model Checking influenced by Formal Foundations of Computation and Logic
Model checking applied the formal semantics of temporal logics, themselves grounded in the model theory of F2, to finite-state systems, turning satisfaction into an algorithmic question.
Carried by Edmund M. Clarke; E. Allen Emerson.
Proof assistant influenced by Automated Theorem Proving
The LCF proof assistant was built on the same goal-directed proof search and inference rules developed in automated theorem proving, with Milner's team adapting them for interactive use.
Carried by Robin Milner.
Conflict-Driven Clause Learning influenced by Automated Theorem Proving
Conflict-driven clause learning extended the DPLL backtracking search of automated theorem proving with clause learning and non-chronological backtracking, turning it into a powerful SAT-solving architecture.
Carried by João P. Marques-Silva; Karem A. Sakallah.
Satisfiability Modulo Theories influenced by Model Checking
Bounded model checking, a SAT-based technique within model checking, demonstrated the practical power of SAT solvers for verification and motivated the integration of theories into SAT, leading to SMT.
Carried by Armin Biere; Alessandro Cimatti.
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.
Decidability and Complexity of Logical Fragments grew out of First-order logic in Philosophical Logic
Decidability and complexity questions for logical fragments are posed within the framework of first-order logic as fixed by Frege and refined by Hilbert and Ackermann. The decision problem for first-order validity, and the fragment-by-fragment classification that followed, presuppose the syntax and semantics of first-order logic.
Carried by Gottlob Frege; David Hilbert; Wilhelm Ackermann.
Decidability and Complexity of Logical Fragments grew out of Fregean predicate logic in Logic
Frege's predicate logic with quantifiers and relations is the object language whose fragments (monadic, prefix, guarded) later received decidability and complexity classifications. The very notion of a logical fragment is a restriction of the Fregean language.
Carried by Gottlob Frege; Begriffsschrift (1879).
Formal Foundations of Computation and Logic grew out of Incompleteness and Limitative Metamathematics in Mathematical Logic
Incompleteness and limitative metamathematics, extended by Turing's and Church's undecidability results, is the direct source of the formal foundations of computation. The field's questions about what formal systems can and cannot decide descend from this tradition.
Carried by Kurt Gödel; Alan Turing; Alonzo Church.
Formal Foundations of Computation and Logic grew out of Gödelian metamathematics in Logic
Gödel's incompleteness theorems and his arithmetization of syntax are the direct ancestors of the formal foundations of computation and logic, including the undecidability results that frame the field. The field's central limitative results are generalisations and extensions of Gödel's metamathematics.
Carried by Kurt Gödel; On Formally Undecidable Propositions (1931).
Formal Foundations of Computation and Logic influenced Logic-Based Knowledge Representation in Knowledge Representation Reasoning
Logic-based KR inherited from the foundational work of Church, Turing, Gödel and others the idea that deductive reasoning can be formalised and mechanised; McCarthy's Advice Taker (1958) proposed representing facts in a formal logical language and computing conclusions from them.
Carried by John McCarthy; Programs with Common Sense (1959).
Formal Foundations of Computation and Logic influenced Digital Logic and Computer Architecture in Electrical Engineering
Formal logic and computability theory, especially Turing's 1936 model of computation, supplied the abstract machine concepts that computer architecture realised in hardware. The stored-program design drew directly on this formal foundation.
Carried by Alan Turing; On Computable Numbers (1936).
Formal Foundations of Computation and Logic influenced Formal grammar and parsing theory in Compiler Design
Turing machines, recursive function theory and Post's production systems from mathematical logic provided the formal machinery of grammars and automata that parsing theory built on. Chomsky explicitly drew on Post and on recursive function theory when defining the grammar hierarchy.
Carried by Alan Turing; Emil Post; Noam Chomsky.
Automated Theorem Proving grew out of Proof Theory in Mathematical Logic
Automated theorem proving grew directly out of proof theory: Herbrand's theorem and Gentzen's sequent calculus and natural deduction supplied the calculi that early theorem provers implemented. The resolution method and later provers are refinements of these proof-theoretic systems.
Carried by Jacques Herbrand; Gerhard Gentzen; J. Alan Robinson.
Logic Programming led to Answer Set Programming and Constraint Formalisms in Knowledge Representation Reasoning
In computational logic, ASP-and-constraint systems are logic programs extended with constraint domains, descending from the stable-model semantics of logic programming.
Logic Programming led to Deductive databases and Datalog in Database Theory
Datalog and deductive databases grew directly out of logic programming: the model-theoretic semantics of Horn clauses and SLD resolution developed in the 1970s were taken over as the query semantics for deductive rules.
Carried by Alain Colmerauer; Robert Kowalski.
Logic Programming led to Answer Set Programming in Knowledge Representation Reasoning
In computational logic, ASP is the answer-set semantics of logic programs made into a computing formalism; it descends from the stable-model and well-founded semantics literature of logic programming.
Carried by Michael Gelfond; Vladimir Lifschitz.
Proof assistant grew out of Curry–Howard correspondence in Proof Theory
The Curry–Howard correspondence, identifying proofs with programs and propositions with types, is the theoretical foundation of type-theoretic proof assistants. Automath and later systems such as Coq and Agda are direct implementations of this correspondence.
Carried by Haskell Curry; William Alvin Howard; Nicolaas Govert de Bruijn.

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 LogicRelated fields
Fields its ideas are linked to
- Mathematical Logic 10 links
- Knowledge Representation Reasoning 8 links
- Logic 7 links
- Database Theory 3 links
- Automata 3 links
- Electrical Engineering 2 links
- Proof Theory 2 links
- Modal Logic 2 links
- Proof Complexity 2 links
- Knowledge Organization 1 link
- Legal Reasoning 1 link
- Philosophical Logic 1 link
More in Theory Of Computation
- Algorithmic Game Theory
- Automata
- Complexity Theory
- Computability
- Computational Learning Theory
- Cryptography
- Proof Complexity
- Quantum Computation
- Theory Of Computation
See where Computational Logic sits on the Map of Human Knowledge