In this file, I have summarized all the prolog-related exam material. This includes all the lecture material about prolog, the literature, and some important examples.
This summary covered all the prolog-related material for the 2023 exam.
Of course, you still need to practice with every exam...
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
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tigovangerven. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.03. You're not tied to anything after your purchase.
