# Logic Programming and Prolog

> A comprehensive lecture note on logic programming through Prolog, covering facts, rules, unification, resolution, backtracking, tabling, constraint logic programming, knowledge representation, symbolic AI, and neuro-symbolic approaches.

- Author: Muhammet Ali Köker
- Language: en
- Canonical: https://alikoker.com.tr/en/logic-programming-and-prolog
- Translation: https://alikoker.com.tr/mantiksal-programlama-ve-prolog
- Published: 2015-10-18T12:00:00+03:00
- Modified: 2026-09-17T01:43:54+03:00
- Verified: 2026-09-17T01:43:54+03:00
- Type: article

Logic programming describes a problem not only through sequences of operations, but through **facts, relations, rules, and queries**. Prolog is the best-known implementation of this approach. Its distinctive feature is that the boundary between program and knowledge representation becomes unusually narrow: the same definition may be read as a logical statement and executed as a computation.

The paradigm is directly related to the propositions, predicates, relations, and graphs studied in [Discrete Mathematics](/en/discrete-mathematics-sets-logic-relations-graphs), and to the languages, grammars, and computation models studied in [Automata Theory and Formal Languages](/en/automata-theory-and-formal-languages). From an AI perspective, it is one of the programming-language-level expressions of the symbolic approach discussed in [Artificial Intelligence: Philosophy, Theory and Practice](/en/artificial-intelligence-philosophy-theory-practice).

## Unit 1: The Place of Logic Programming

### 1.1 Logic programming as a programming paradigm

Imperative programming usually describes state changes and execution order. Functional programming organizes computation around function composition. Logic programming first states which relations are valid and under which conditions new conclusions follow from them.

The central question therefore often changes from:

```text
How should this be done?
```

to:

```text
Which relations are true?
What follows from them?
```

This does not mean that control disappears. Logical meaning and execution strategy are separate layers. The relation being defined can be distinguished from the order in which possible solutions are explored.

### 1.2 Historical context of Prolog

The first version of Prolog emerged in 1972 from the work of Alain Colmerauer and colleagues in Marseille. Robert Kowalski's contributions to the theoretical foundations of logic programming were central to the development of Prolog as both a programming language and an inference environment.

Prolog developed in close connection with natural-language processing, automated theorem proving, expert systems, knowledge representation, and symbolic artificial intelligence. Statistical learning and neural networks later became dominant in many AI applications, yet logic-based methods remained relevant for explicit knowledge representation, rule-based inference, constraint solving, and formal verification.

### 1.3 Computation through relations

The basic unit in Prolog is usually a **relation**, rather than a function.

```prolog
connection(a, b).
connection(b, c).
connection(c, d).
```

These statements describe known facts rather than a sequence of operations.

A new relation can be defined from them:

```prolog
reachable(X, Y) :-
    connection(X, Y).

reachable(X, Y) :-
    connection(X, Z),
    reachable(Z, Y).
```

The definition states when reachability is true in a graph. When executed, Prolog searches for paths satisfying the relation.

## Unit 2: Facts, Rules, and the Logical Foundation

### 2.1 Terms, predicates, and atomic formulas

Prolog programs are built around terms and predicates. Constants represent particular objects, variables stand for as-yet unspecified values, and compound terms represent structured data.

```prolog
person(ali).
city(ankara).
lives_in(ali, ankara).
```

`lives_in/2` is a predicate with two arguments. Logically, it represents a relation; operationally, it is a queryable definition.

### 2.2 Facts, rules, and queries

A **fact** states information directly.

```prolog
active(service_a).
```

A **rule** specifies the conditions under which a conclusion holds.

```prolog
available(X) :-
    active(X),
    dependencies_ready(X).
```

A **query** asks whether a conclusion can be derived from the knowledge base.

```prolog
?- available(service_a).
```

Together they form the basic information flow of logic programming:

```text
fact + rule + query
        ↓
     inference
```

### 2.3 Horn clauses

The classical core of Prolog is largely based on Horn clauses. The head of a rule expresses a conclusion, while the body contains the subgoals required for the conclusion to hold.

```prolog
ancestor(X, Y) :-
    parent(X, Z),
    ancestor(Z, Y).
```

The logical meaning of the definition and the order in which it is executed are not identical. The former describes the relation; the latter affects how the search proceeds.

### 2.4 Declarative and operational meaning

A Prolog rule can be read in two ways.

Declaratively:

```text
X is suitable if X is active and authorized.
```

Operationally:

```text
To prove suitable(X), first solve active(X),
then solve authorized(X).
```

The distinction matters. Two logically equivalent definitions may exhibit different runtime or termination behavior because of search order.

## Unit 3: Unification, Resolution, and Backtracking

### 3.1 Logical variables

Prolog variables differ from ordinary imperative variables. Once a logical variable is bound to a term within a solution branch, it is not repeatedly reassigned to unrelated values in that branch.

```text
event(X, critical)
event(server_3, Y)
```

can be made compatible through:

```text
X = server_3
Y = critical
```

### 3.2 Unification

**Unification** finds variable bindings that make two terms structurally identical. It is more general than simple pattern matching and operates on nested terms and logical variables.

```prolog
record(person(Id), time(T))
```

and:

```prolog
record(person(42), time(1730))
```

unify with `Id = 42` and `T = 1730`.

Unification allows information to flow between predicates and data structures without explicit assignment.

### 3.3 Resolution and SLD resolution

When answering a query, Prolog matches a goal with suitable rules and replaces it with smaller subgoals. The logical basis of this process is **resolution**.

For definite clauses, goal-directed execution is commonly described through **SLD resolution**. A goal is selected, unified with an appropriate clause, a new goal list is produced, and the process continues until a proof succeeds or the branch fails.

```text
query
↓
matching rule
↓
subgoals
↓
further rules
↓
proof / failure
```

### 3.4 Backtracking

When a goal has multiple candidate solutions, Prolog creates a choice point. If the current branch fails, execution returns to an earlier choice point and tries another alternative. This behavior is called **backtracking**.

Backtracking makes search an intrinsic part of the language. The cost, however, grows with the search space. A correct program must therefore consider not only correctness but also unnecessary exploration.

### 3.5 Goal and clause order

These rule bodies can express the same logical conditions:

```prolog
p(X) :-
    a(X),
    b(X).
```

```prolog
p(X) :-
    b(X),
    a(X).
```

Yet their cost can differ substantially if `a/1` and `b/1` generate different numbers of candidates. In recursive definitions, ordering can also affect termination.

Logic programs therefore must be considered through:

```text
correctness
+
search order
+
termination
```

### 3.6 Cut and operational control

The `!` operator in Prolog is known as **cut**. It prevents certain choice points created before the cut from being reconsidered.

```prolog
classify(X, positive) :-
    X > 0, !.

classify(_, other).
```

Cut can reduce unnecessary search, but it also makes operational behavior more tightly coupled to the program's meaning. It should therefore be used deliberately.

## Unit 4: Recursion, Modes, and Tabling

### 4.1 Recursive relations

Much iteration in logic programming is expressed through recursion.

```prolog
member_of(X, [X|_]).
member_of(X, [_|Rest]) :-
    member_of(X, Rest).
```

The first clause is the base case; the second is recursive.

Lists, trees, and graphs are naturally recursive structures, so many relations can be expressed directly in this form.

### 4.2 Modes and reversibility

The binding state of predicate arguments can be described through **modes**.

```text
relation(+A, -B)
relation(-A, +B)
```

The same relation may compute an output in one direction and search for possible inputs in another. This is one source of the **reversibility** associated with logic programs.

Not every mode is equally efficient or guaranteed to terminate. Logical validity does not imply practical usefulness under every call pattern.

### 4.3 Tabling

Traditional depth-first evaluation may repeatedly solve the same subgoal or loop on cyclic recursion.

**Tabling** stores answers to previously evaluated subgoals and reuses them.

It is particularly important for:

- graph reachability,
- mutually recursive definitions,
- deductive databases,
- rule-based inference.

Tabling can improve both performance and termination behavior without changing the logical relation being defined.

### 4.4 Meta-programming

Prolog code can itself be represented as Prolog terms. Programs can therefore inspect, transform, or interpret other programs.

Meta-interpreters can be used for:

- proof-tree generation,
- rule tracing,
- program transformation,
- explanation generation,
- compact interpreters.

This feature places logic programming at an interesting point between programming-language theory and [Automata Theory and Formal Languages](/en/automata-theory-and-formal-languages).

## Unit 5: Negation, Incomplete Knowledge, and Constraints

### 5.1 Negation as failure

Classical logical negation:

```text
¬P
```

is not identical to the **negation as failure** commonly used in Prolog.

Operationally, the usual idea is:

```text
if P cannot be proved, not(P) succeeds
```

The absence of a proof must therefore be interpreted carefully.

### 5.2 Closed-world assumption

Many rule-based systems employ a **closed-world assumption**: under the chosen semantics, facts that cannot be established may be treated as false.

Open-world reasoning preserves the distinction:

```text
unknown ≠ false
```

This is important in domains such as law, security, medicine, and scientific reasoning, where incomplete information is normal.

### 5.3 Constraint Logic Programming

Instead of immediately binding a variable to one concrete value, a system may retain conditions that the value must satisfy.

```text
X > 0
Y < 20
X + Y = 15
```

**Constraint Logic Programming (CLP)** combines logical search with domain-specific constraint solvers.

Common domains include:

- finite domains,
- integers,
- rational numbers,
- real numbers,
- Boolean values.

CLP is useful for scheduling, configuration, resource allocation, verification, and combinatorial optimization.

### 5.4 Datalog and extended logic systems

Datalog is a restricted logic-programming language that is closely related to database querying and deductive databases. Answer Set Programming and systems such as s(CASP) extend the symbolic family toward defaults, exceptions, integrity constraints, and incomplete information.

These systems are not identical to Prolog, but they belong to neighboring regions of logic-based knowledge representation and reasoning.

## Unit 6: Grammars, Knowledge Representation, and Forms of Inference

### 6.1 Definite Clause Grammars

Natural-language processing played an important historical role in Prolog. **Definite Clause Grammars (DCGs)** translate grammar rules into executable predicate definitions.

```prolog
sentence --> noun_phrase, verb_phrase.
```

DCGs are useful not only for natural language but also for token streams, protocols, small domain-specific languages, and structured text.

### 6.2 Knowledge representation

Viewing Prolog only as a programming language misses an important aspect of the paradigm. A Prolog program can also be read as a **knowledge representation** in which higher-level relations are defined through lower-level ones.

```prolog
risky(X) :-
    critical(X),
    unverified(X).
```

This is executable code, but it is also an explicit statement of domain knowledge.

Such representations can make rules inspectable and can help expose the derivation leading to a conclusion.

### 6.3 Deduction

**Deduction** derives necessary consequences from general rules and known facts.

```text
A → B
A
∴ B
```

Classical Prolog usage is strongly associated with this direction.

### 6.4 Abduction

**Abduction** searches for possible explanations of an observation.

```text
A → B
B is observed
A may explain B
```

The explanation is a hypothesis rather than a logically necessary conclusion.

Abduction is relevant to diagnosis, scientific explanation, and hypothesis generation.

### 6.5 Induction and inductive logic programming

**Induction** attempts to derive general rules from individual examples.

Inductive Logic Programming uses examples together with background knowledge to learn logical rules. It therefore provides a direct bridge between logic programming and machine learning.

## Unit 7: Symbolic AI and Engineering Use

### 7.1 Expert systems and symbolic AI

Symbolic AI represents knowledge explicitly:

```text
symbols
↓
facts
↓
rules
↓
inference
```

This makes derivations easier to inspect.

The limitation is the cost of manually constructing large knowledge bases. High-dimensional and uncertain inputs such as images, audio, and unrestricted natural language are usually difficult to model through hand-written rules alone.

### 7.2 Formal methods and ProB

Formal methods are one of the contemporary engineering domains in which logic-oriented computation remains valuable. The Prolog-based ProB system provides animation, model checking, and constraint solving for high-level formal models.

The important idea is that a mathematical specification can become not only a document but an executable, queryable, and verifiable artifact.

### 7.3 Modern software ecosystems

The limited mainstream adoption of Prolog compared with Python, Java, JavaScript, or C# is not explained solely by language semantics. Library ecosystems, tooling, IDE support, developer familiarity, and integration with existing infrastructure strongly affect engineering choices.

A modern pattern is therefore to use Prolog as a specialized **reasoning component** rather than as the language of an entire application.

### 7.4 The SWI-Prolog perspective

SWI-Prolog is a widely used implementation with modules, tabling, constraint libraries, and foreign-language interfaces.

The implementation should nevertheless be distinguished from the paradigm.

The transferable core is:

```text
relations
facts and rules
logical variables
unification
resolution
backtracking
recursion
declarative meaning
```

Implementation-specific libraries extend this core.

## Unit 8: Relationship to Other Learning Approaches

### 8.1 Statistical learning

[Statistical Learning and Machine Learning](/en/statistical-learning-machine-learning) focuses on estimating models, decision boundaries, or probabilistic structures from observed data.

Logic programming generally derives conclusions from explicit knowledge and rules.

```text
statistical learning:
data → estimation → generalization

logic programming:
facts + rules → inference
```

A real system may contain both. A statistical model may process uncertain observations while a logical layer applies domain rules and constraints.

### 8.2 Artificial neural networks

[Artificial Intelligence and Neural Networks](/en/artificial-intelligence-and-neural-networks) and [Artificial Neural Networks and Learning Models](/en/artificial-neural-networks-and-learning-models) represent knowledge through distributed numerical parameters learned from examples.

Logic programming keeps knowledge more explicit:

```text
rule:
authorized(X) :- role(X, administrator).

neural model:
output produced through many learned parameters
```

Neural networks are strong at high-dimensional pattern learning; logic-based systems can be attractive when explicit rules, constraints, and inspectable inference are required.

### 8.3 Fuzzy logic

[Fuzzy Logic](/en/fuzzy-logic) represents concepts with graded membership rather than crisp boundaries.

```text
hot(x) = 0.8
```

Logic programming is primarily concerned with relations and inference structure.

```text
critical(X) :- hot(X), pressure_high(X).
```

The two address different problems and may be combined in suitable architectures.

### 8.4 Genetic algorithms

[Genetic Algorithms and Their Applications](/en/genetic-algorithms-and-applications) search a solution space through populations, selection, crossover, and mutation.

Logic programming also performs search, but the search usually concerns proofs or variable bindings satisfying declared relations.

```text
genetic algorithm → heuristic optimization
logic programming → proof / satisfying-solution search
```

The two families are not mutually exclusive. An evolutionary method may search for parameters or rule subsets while a logic layer enforces validity constraints.

## Unit 9: Large Language Models and Neuro-Symbolic Systems

### 9.1 Knowledge in large language models

Knowledge in a large language model is not stored as a directly readable collection of Prolog-like facts and rules. It is distributed across many parameters learned from large datasets.

The distinction:

```text
fluent output ≠ logical proof
```

must therefore be preserved.

### 9.2 Generation and verification

A large language model may generate a candidate answer, structure, or rule. A logic layer can then test whether the candidate is consistent with a trusted knowledge base and a defined constraint set.

A possible architecture is:

```text
natural language / image / audio
↓
learned model
↓
structured facts
↓
logical rules and constraints
↓
validated result
```

This does not solve every problem, but it is useful where learned representations and explicit validation are both required.

### 9.3 Neuro-symbolic systems

Neuro-symbolic approaches attempt to combine neural learning with symbolic reasoning.

Neural components are strong in:

- perception,
- pattern recognition,
- language processing,
- representation learning.

Symbolic components are useful for:

- explicit rules,
- integrity constraints,
- proof traces,
- formal validation,
- domain knowledge.

### 9.4 Limits

Logic programming does not solve hallucination in large language models by itself. Symbolic verification requires trusted facts, correct rules, and a suitable representation.

Likewise, the explainability of a rule base does not guarantee its correctness. An incorrect knowledge base can produce an explicit and fully traceable incorrect result.

## Unit 10: Conceptual Distinctions and Integration

### 10.1 Core distinctions

**Fact ≠ rule.** A fact directly states information; a rule expresses a conditional relation.

**Logical variable ≠ imperative variable.** A logical variable is bound within a solution branch rather than repeatedly reassigned as mutable state.

**Unification ≠ assignment.** Unification searches for structural bindings that make terms compatible.

**Resolution ≠ backtracking.** Resolution is an inference mechanism; backtracking explores alternative solution paths.

**Declarative meaning ≠ operational behavior.** The same logical relation can have very different execution costs.

**Negation as failure ≠ classical negation.** Failure to prove something is not universally equivalent to proving its falsity.

**Tabling ≠ merely a cache.** Besides avoiding repeated work, it can change termination behavior for some recursive relations.

**Constraint ≠ immediate assignment.** A constraint preserves admissible relationships among variables.

**Symbolic inference ≠ statistical prediction.** One derives consequences from explicit premises; the other estimates and generalizes from data.

**Explainability ≠ correctness.** A visible proof chain does not guarantee that its premises are true.

**Prolog ≠ all logic programming.** Prolog is a major implementation; Datalog, ASP, CLP, and related systems occupy different points in the broader family.

### 10.2 Problem selection

Logic programming is a natural candidate when a problem is dominated by:

```text
explicit relations
+
rules
+
multiple-solution search
+
constraints
+
proof / explanation requirements
```

Statistical or neural methods are generally more natural when the problem is dominated by:

```text
high-dimensional raw data
+
noise
+
pattern learning
+
relations that are difficult to encode manually
```

Problems containing both sets of requirements may motivate hybrid architectures.

### 10.3 Conceptual map across courses

[Discrete Mathematics](/en/discrete-mathematics-sets-logic-relations-graphs) provides the foundations in logic, relations, and graphs.

[Automata Theory and Formal Languages](/en/automata-theory-and-formal-languages) provides the formal-language, grammar, and computation-model perspective.

[Artificial Intelligence: Philosophy, Theory and Practice](/en/artificial-intelligence-philosophy-theory-practice) places symbolic and data-driven AI in a broader historical and conceptual context.

[Artificial Neural Networks and Learning Models](/en/artificial-neural-networks-and-learning-models) studies distributed numerical representation and learning from examples.

[Statistical Learning and Machine Learning](/en/statistical-learning-machine-learning) focuses on estimation, generalization, and learning models from data.

[Fuzzy Logic](/en/fuzzy-logic) adds graded membership and approximate reasoning.

[Genetic Algorithms and Their Applications](/en/genetic-algorithms-and-applications) contributes evolutionary search and optimization.

Logic programming contributes a different central question:

> **When knowledge is represented explicitly as relations and rules, how can a computer derive new conclusions from it?**

### 10.4 Conclusion

The primary reason to study Prolog is not to memorize the syntax of another programming language. Its value lies in exposing a different model of computation.

```text
imperative programming → state and execution order
functional programming → functions and transformations
statistical learning → data and generalization
neural networks → learned distributed representations
logic programming → explicit relations, rules, and inference
```

The center of gravity in AI shifted over time from symbolic systems toward statistical learning and neural models. Large language models are a visible contemporary expression of that transition. Explicit knowledge representation, constraints, formal verification, and inspectable inference nevertheless remain important.

Logic programming is therefore not merely an obsolete AI technique. It is a foundational computer-science paradigm for understanding the distinction between **representation, inference, search, and verification**.

## References

- David S. Warren; Veronica Dahl; Thomas Eiter; Manuel V. Hermenegildo; Robert Kowalski; Francesca Rossi (eds.). *Prolog: The Next 50 Years*. Lecture Notes in Artificial Intelligence, vol. 13900. Springer, 2023. https://doi.org/10.1007/978-3-031-35254-6
- David S. Warren. “Introduction to Prolog.” In *Prolog: The Next 50 Years*. Springer, 2023.
- Michael Genesereth. “Prolog as a Knowledge Representation Language: The Nature and Importance of Prolog.” In *Prolog: The Next 50 Years*. Springer, 2023.
- Manuel V. Hermenegildo; José F. Morales; Pedro López-García. “Some Thoughts on How to Teach Prolog.” In *Prolog: The Next 50 Years*. Springer, 2023.
- Michael Leuschel. “ProB: Harnessing the Power of Prolog to Bring Formal Models and Mathematics to Life.” In *Prolog: The Next 50 Years*. Springer, 2023.
- Gopal Gupta et al. “Logic-Based Explainable and Incremental Machine Learning.” In *Prolog: The Next 50 Years*. Springer, 2023.
- Paul Tarau. “Reflections on Automation, Learnability and Expressiveness in Logic-Based Programming Languages.” In *Prolog: The Next 50 Years*. Springer, 2023.

## Cite This Work

Köker, M. A. (2015). Logic Programming and Prolog. alikoker.com.tr. https://alikoker.com.tr/en/logic-programming-and-prolog

- BibTeX: https://alikoker.com.tr/en/logic-programming-and-prolog.bib
- RIS: https://alikoker.com.tr/en/logic-programming-and-prolog.ris
- CSL-JSON: https://alikoker.com.tr/en/logic-programming-and-prolog.csl.json