Prolog: Framework
1: Knowledge base
- Facts
- Rules
- Stored in .pl files
2: Query's
- Posted from script
Prolog Syntax
:- defines an implication (A → B corresponds to B :- A).
, defines a conjunction
; defines a disjunction
An atom:
1. A sequence of letters, digits, or underscores started with a lower-case letter
2. A sequence of letters, digits or underscores in single quotes ‘’
3. A string of special characters, e.g. :- or ,
A number is any sequence of numbers, possibly containing a dot.
Both atoms and numbers are called constants
A variable is a sequence of letters, digits or underscores starting with an upper-case letter
or an underscore
- The variable _ is called the anonymous variable.
A term is defined recursively:
1. Each constant and variable is a term
2. f(t1,...,tk) is a term if each ti is a term and f is an atom.
- This is called a compound term with functor f and arity k, which is often referred to
in the notation f/k e.g. woman/1
- A term is ground when it contains no variables.
Any constant or compound term is known as a predicate.
If immediately followed by a dot (.), it is called a fact (knowledge).
It can be a rule if:
- Given by A 0 :- A 1, …, A n. with n >= 0 and each A i a predicate.
A0 is called the head of the rule, A 1, …, A n the body.
A clause is any fact or rule.
- p(X) :- f(X), r(X) (Prolog)
- f(X) ^ r(X) → p(X) (FOL)
Clauses are always universal, i.e. here p(X) holds for all C
22 constant, term, predicate p(X) :- f(X), z(Y). rule
Robert variable, term, predicate f(x(A),z(B)). fact, compound term, predicate
A query is defined as’?-p.’, where p is some predicate, known then as a goal.
Query ?-p(X) corresponds to ∃X p(X) in FOL
, Prolog - Unification
- Matching is Prolog’s method for unification.
Two terms t1 and t2 match iff:
1. t1 and t2 are identical constants.
2. If t1 is a variable and t2 is not, then t1 is instantiated with t2
same applies for the reverse or when both are variables.
3. If t1 and t2 are compound terms, they match if:
- They have the same outermost functor, i.e. , t1= f(r1, …,rk) and t2 = f(s1, …, sk)
- Each term ri matches with each term si
- The variable instantiations are compatible, i.e., a variable can’t be assigned
different terms which are not variables.
=/2 is the built in matching predicate → It binds variables using the most general unifier
\=/2 can be used to check for terms that do not match
?- ab = ab. true. ?- f(X, a) = f(b, Y). X = b, Y = a.
?- X = a. X = a. ?- X+3 = 5 +Y. X = 5, Y = 3.
?- X = f(a). X = f(a). ?- X + 2 = 5. false.
?- f(X,g(a)) = f(b,g(Z)). X = b, Z = a. ?- term(X) = term(Y). X = Y.
?- f(X, a) = f(b, X). false. ?- term(X, X) = term(Y,Z). Y= Z.
Prolog - Search
Deduction
- match p(a) with p(X)
- start with deriving body of rule: q(a), r(a)
- both goals are facts in the knowledge base.
Searching for Proofs
1. Ask a query
2. Find appropriate rule
3. Prove body of rule
4. Continue until no alternatives remain
Three Principles
1. backward chaining: start from the current goal and select the rule/fact which allows
to derive the goal. If a rule is matched, try to derive the rule’s body (from left to right).
2. linear: traverse the logic program from top to bottom (select appropriate rules).
3. backtracking: if the current goal cannot further be matched with any rule, try other
alternative rules in step 2
Backward chaining compound queries
- Find the first topmost rule such
that the head of rule matches with
goal1(t1) for an instantiation 𝞂.
- Continue with new query (body replacement):
- ?- p1(t4)𝞂, p2(t5)𝞂 , goal2(t2).
- Note: (sub)goals are treated from left to right.
We can stop a query if there are no more goals to deduce (empty
query) or when there is success.
