Lògica a la Informàtica
Lab 3 / Lab 4

March 13, 2026

PROgrammation en LOGique

  • Prolog is a declarative language.
    • A Prolog program describes the problem at hand, its structure with facts and rules, and the objective of the problem with queries
    • Very different from imperative languages (concerned on how to find a solution)
  • Prolog started in France (at Universitat Aix-Marseille, \sim 70s).
  • Prolog programs are text files with the extension .pl

Pro of Prolog

  • Programs are often short and expressive
  • Close to mathematical logic
  • Good for reasoning problems
  • Built-in search and backtracking
  • Natural manipulation of symbolic structures
  • Very useful for AI and symbolic reasoning

Contra of Prolog

  • Not suited for numerical or large-scale computations
  • Hard to control execution

Real world usage of Prolog

  • Computational linguistics
  • Constraint Solving
    • scheduling
    • resource allocation
    • timetabling
    • planning problems
  • IBM Watson (some rule-based components)
  • SWI-Prolog applications
  • NASA planning systems
  • telecom configuration systems
  • legal reasoning tools

The prolog interpret swipl

  • type swipl in a terminal
    • What version of swipl is installed?
    • ?- halt. stops the session (also Control+D, but it is uglier.)
  • make swipl aware of pizarraLaboProlog.pl
    • swipl pizarraLaboProlog.pl in a terminal, or
    • ?- [pizarraLaboProlog]., or
    • ?- consult('pizarraLaboProlog.pl').
  • what does the interpret know about padre?
    • ?- listing(padre).

Prolog syntax: An atom is either

  • A string of characters made of up of A, …, Z,a, …, z,0, …,9, and _, that begins with a lower-case letter.
  • An arbitrary sequence of characters (including space) between ' and '.

atom/1 to check

Prolog syntax: A variable is either

  • a string of upper-case letters, lower-case letters, digits and underscore characters that starts either with an upper-case letter or with _.
  • _ (the anonymous variable)

var/1 to check

Prolog syntax: A compund term is

  • an atom (the functor name) followed by ( and a sequence of arguments separated by , and ending with ). Arguments can be atoms, variables, numbers or compund terms.

The number of arguments that a compund term has is called its arity.

compound/1 or functor/3 to check

Prolog syntax: A clause is either

  • a fact, that is an atom or compund term followed by .
  • a rule, an atom or compund term (the head) followed by :- and then atoms or compunds terms separated by , (the body) and ending with .

A Prolog program is a sequence of clauses.

A query is a sequence of atoms or compund terms (separated by ,) and ending with .

Some predefined predicates we saw

  • true/0: always true
  • false/0: (or fail/0) always false
  • =/2: =(X,Y) (or X = Y) true iff X and Y can be unified
  • \=/2: X \= Y true iff X=Y is false
  • \+: \+ X true when X cannot be proved true
  • write(X): writes the term X and is true
  • nl/0: newline, and also true

display/1 to look into the internal representation of terms

What is ?- display(X = Y).?

Lists

The empty list is []. A list is a sequence (, separated) of compound terms (including lists). E.g. [a, b, [], f(a), g(f(a,X)), [a,b,c], X] is a list.

The first element of a list is the head, the rest the tail ([H | T])

What is the output of (and how you read) the following queries?

  • [H | T] = [a, b, [], f(a), g(f(a,X)), [a,b,c], X].
  • [H1,H2 | T] = [a, b, [], f(a), g(f(a,X)), [a,b,c], X].
  • [H1,H2,H3 | T] = [a, b].
  • [H | T]=[].
  • [H | T]=[a].

Predicate second/2 to obtain the second element of a list? second([_,Elem|_], Elem)

Examples

member(?Elem, ?List)
True if Elem is a member of List.

Let’s re-implement it as pert/2:

pert(X, [X | _]).  
pert(X, [_ | L]) :- pert(X,L).

How pert/2 definition differs from member/2?

append(?List1, ?List2, ?List1AndList2)
List1AndList2 is the concatenation of List1 and List2

Let’s re-implement it as conc/3:

conc([], L, L). 
conc([X|L1], L2, [X|L3]):- conc(L1, L2, L3).

How conc/3 definition differs from append/3?

last(?List, ?Last)
Succeeds when Last is the last element of List.

Let’s re-implement it as ultim/2:

ultim(L, X) :- conc(_, [X], L).

X is the last of the list L if L is the concatenation of some list and [X]

subset(+SubSet,+Set)
True if all elements of SubSet belong to Set as well.

Let’s re-implement it as subcjt/2:

subcjt([], _).
subcjt([X | R], T) :-
  pert(X, T),
  subcjt(R, T).

subconjunt/2 below does the same, but also allows to generate subsets in the first element

subconjunt([],[]).
subconjunt(S,[_|L]) :- subconjunt(S,L).
subconjunt([X|S],[X|L]) :- subconjunt(S,L).

Let’s re-implement it as permutacio/2

permutacio([], []).
permutacio([X | L], P) :-
  permutacio(L, Q),
  conc(Q1, Q2, Q),
  conc(Q1, [X | Q2], P).

Arithmetic

= is unification (aka mattern matching). So how we do arithmetic?

is/2
X is Expr where Expr is an expression that can be evaluated, if it has variables, all of them are instanciated.

Caution

Expr is X is not allowed. The expression always goes to the right and the variable to assign to the left.

Examples

length(?List,?Length)
True if Length represents the number of elements in List.

Let’s re-implement it as mida/2

mida([], 0).
mida([_ | L], N):- 
  mida(L, N1), 
  N is N1 + 1.

Why the next implementation is wrong?

mida([], 0).
mida([_ | L], N1+1):- 
  mida(L, N1), 
  N is N1 + 1.
fact(0, 1):- !.
fact(N, F):- 
  N1 is N - 1, 
  fact(N1, F1), 
  F is N * F1.
  • we do N1 is N - 1 before fact(N1, F1), because the latter needs N1 to be instanciated
  • we do F is N * F1 to force the evaluation of N * F1