Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 40 ยท Facts, Rules and Queries

Prolog Closed-World Assumption and Negation as Failure

Learn how Prolog treats missing facts as false, how \+ implements negation as failure, why goal order matters with negation, and how it differs from logical not.

Until now every goal either found a proof or did not. Real programs also need to say "not": a student who is not enrolled, a path that does not pass a closed door. Prolog's answer is a special form of negation that follows directly from how the system searches. Understanding it prevents the most surprising bugs beginners meet.

Prolog is read-only on this site. The runnable blocks use the Python mini-Prolog stand-in, which implements \+ the same way (it succeeds when the goal inside has no proof).

The closed-world assumption

Prolog only knows what is in its database. If it cannot prove a goal, it says false. Prolog does not say "I don't know"; it treats unprovable as false. This is the closed-world assumption: the database is assumed to describe everything that is true.

PROLOG
likes(mary, wine).

?- likes(mary, beer).
false.

This is a reasonable assumption for a flight timetable (a flight that is not listed does not exist), and a dangerous one for open-ended facts (the database may simply be incomplete). Keep it in mind when you read false: it means "not provable from this program".

Negation as failure: +

The operator \+ (read "not provable") takes a goal. \+ Goal succeeds if Goal has no proof and fails if Goal can be proved. This is called negation as failure.

PROLOG
?- \+ likes(mary, beer).
true.

?- \+ likes(mary, wine).
false.

A classic use is a rule with an exclusion:

PROLOG
person(ann). person(bob). person(cy).
married(ann). married(cy).

single(X) :- person(X), \+ married(X).
PROLOG
?- single(Who).
Who = bob.

First person(X) produces a candidate, and then \+ married(X) checks that it cannot be proved married. Bob passes. Older programs write not(Goal), which behaves the same in SWI-Prolog; prefer \+.

Goal order matters with negation

\+ is a test, not a generator. It never binds variables. Compare:

PROLOG
single_ok(X)  :- person(X), \+ married(X).    % bind X first, then test
single_bad(X) :- \+ married(X), person(X).    % test first with X unbound

In single_bad, X is unbound when \+ married(X) runs. The goal married(X) has a proof (X = ann), so \+ married(X) fails immediately. The whole query gives false, even though Bob is single. The meaning of \+ married(X) with unbound X is "there is no X that is married", which is not what you wanted. The rule of thumb: every variable in a negated goal must already be bound (be "safe") before \+ runs.

How + works

\+ G runs G as a sub-search. If G succeeds, the sub-search is thrown away and \+ G fails. If G fails for every possibility, \+ G succeeds. Either way no bindings from G survive.

flowchart LR
    A["\+ G"] --> B{"Does G have a proof?"}
    B -- "yes" --> C["\+ G fails (no bindings kept)"]
    B -- "no" --> D["\+ G succeeds"]

Negation as failure turns failure of the inner goal into success.

Not the same as logical negation

In logic, "not P" is true when P is false in the world. Prolog's \+ P is true when P cannot be proved. They agree when the database is complete, and they disagree when it is not. Add a fact and a negation flips: if later you add married(bob)., single(bob) stops being provable. Prolog is non-monotonic: adding facts can remove answers. That is a deliberate feature (it models "default" reasoning), but it means you should think about whether your program's completeness assumption holds.

Another trap: \+ \+ G ("not not G") succeeds if G has a proof but leaves no bindings. It is a way to test without binding, used inside larger programs.

  • X \= Y succeeds when X and Y cannot be unified. It is \+ X = Y.
  • once(G) runs G and keeps only its first solution.
  • ( Cond -> Then ; Else ) is if-then-else. If Cond succeeds, only the first solution of Cond is used and Then runs; otherwise Else runs.
PROLOG
classify(N, Class) :-
    (   N < 0  -> Class = negative
    ;   N =:= 0 -> Class = zero
    ;   Class = positive
    ).
PROLOG
?- classify(-5, C).
C = negative.

Use if-then-else rather than a pair of clauses with \+ when the two cases are exclusive; it states the intent and avoids testing the condition twice. You will meet more control constructs, including the cut, in chapter 5.

Try it

Python Negation as failure (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

single_bad gives false. because the negated goal ran with an unbound variable. Now watch a conclusion change when a fact is added: non-monotonic reasoning in action.

Python Adding a fact removes an answer (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Putting \+ before the goals that bind its variables.
  • Using \+ X = Y where X \= Y is clearer, or X \== Y when you mean "not identical" (see term comparison).
  • Reading false as "this is wrong in the real world".
  • Using negation on goals with side effects (printing, asserting): the effect still happens, but bindings vanish.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does + Goal do?

    Negation as failure: + G succeeds exactly when G cannot be proved.
  2. 2. Why does single_bad(X) :- + married(X), person(X). find nothing?

    + never binds variables. With X unbound, married(X) succeeds, so its negation fails.
  3. 3. What is the closed-world assumption?

    Prolog treats unprovable goals as false.
  4. 4. After adding the fact married(bob)., what happens to single(bob)?

    Adding facts can remove answers when negation is involved.

Summary

  • Prolog assumes the database is complete: unprovable goals are false.
  • \+ G succeeds when G has no proof; it binds nothing.
  • Bind variables before negating them: generate, then test.
  • Negation as failure is not classical logical negation, and adding facts can remove answers.
  • \=, once/1 and ( If -> Then ; Else ) are the nearby tools.

Next: Unification