2. A Linguagem
Prolog
A Cláusula Prolog
“se”
“e”
“ou”
a :- b1, b2... bi; bj... bn.
Cabeça,
Corpo,
Conclusão,
Condição,
Consequente.
Antecedente.
2
Introdução à Programação Prolog
Operadores Prolog
Linguagem
Natural
Cálculo de
Predicados
Programas
Prolog
E


,
;


:-
OU
SE
NÃO
not
3
Introdução à Programação Prolog
Fatos
Seja a árvore genealógica
mostrada abaixo...
Maria
que pode ser representada pelo
seguinte programa Prolog:
João
José
Júlia
Ana
Íris
progenitor(maria, josé).
progenitor(joão, josé).
progenitor(joão, ana).
progenitor(josé, júlia).
progenitor(josé, íris).
progenitor(íris, jorge).
Este programa representa a
relação progenitor/2, na forma de
um predicado, que contém 6
cláusulas, que são todas fatos.
Jorge
4
Introdução à Programação Prolog
Consultas
O programa pode ser pensado
como uma tabela em uma BD.
progenitor(maria, josé).
progenitor(joão, josé).
progenitor(joão, ana).
progenitor(josé, júlia).
progenitor(josé, íris).
progenitor(íris, jorge).
No caso de um programa
constituído unicamente de fatos, a
semântica é exatamente a mesma
de uma BD relacional...
Introdução à Programação Prolog
que pode ser consultada de várias
maneiras:
?- progenitor(joão, ana).
true
?- progenitor(joão, jorge).
fail
?- progenitor(joão, X).
X=josé;
X=ana.
fail
?- progenitor(X,Y).
X=maria, Y=josé;
X=joão, Y=josé;
...
X=íris,
Y=jorge.
fail
5
Ampliando a Base de Fatos
O programa pode ser ampliado
acrescentando-se novos fatos
que inclusive podem
estabelecer novas relações.
No exemplo ao lado
acrescentou-se ao programa
original as relações
masculino/1 e feminino/1.
Estas relações, que possuem
aridade 1, podem ser pensadas
como sendo atributos dos
objetos a que se aplicam.
progenitor(maria, josé).
progenitor(joão, josé).
progenitor(joão, ana).
progenitor(josé, júlia).
progenitor(josé, íris).
progenitor(íris, jorge).
masculino(joão).
masculino(josé).
masculino(jorge).
feminino(maria).
feminino(ana).
feminino(júlia).
feminino(íris).
6
Introdução à Programação Prolog
Regras
As relações pai/2 e mãe/2
podem agora ser definidas
da seguinte maneira:
X é pai de Y se
X é progenitor de Y e
X é masculino.
X é mãe de Y se
X é progenitor de Y e
X é feminino.
Em Prolog:
pai(X,Y) :progenitor(X,Y),
masculino(X).
mãe(X,Y) :progenitor(X,Y),
feminino(X).
7
Introdução à Programação Prolog
Mais Regras
As relações irmão/2 e
irmã/2 podem agora ser
definidas da seguinte
maneira:
X é irmão de Y se
Z é progenitor de X e
Z é progenitor de Y e
X é masculino.
X é irmã de Y se ...
Em Prolog:
irmão(X,Y) :progenitor(Z,X),
progenitor(Z,Y),
masculino(X).
irmã(X,Y) :- ...
mas, esta regra tem um
problema. (qual?)
8
Introdução à Programação Prolog
Exercício
Acrescentar ao programa da árvore
genealógica as seguintes relações
(em 10 minutos):
avô/2
tia/2
prima/2
9
Introdução à Programação Prolog
Representação Textual
Considere o seguinte texto:
nasceu(joão,pelotas).
nasceu(jean,paris).
“João nasceu em Pelotas e Jean
nasceu em Paris. Paris fica na
França, enquanto que Pelotas
fica no Rio Grande do Sul. Mas
só é gaúcho quem nasceu no Rio
Grande do Sul, tchê.”
fica(paris,frança).
fica(pelotas,rs).
Ao lado a codificação em
Prolog:
?- gaúcho(X).
X=joão;
no
gaúcho(X):nasceu(X,Y),
fica(Y,rs).
10
Introdução à Programação Prolog
Predicados Recursivos
Seja, por exemplo, a relação
antepassado/2:
Maria
progenitor
João
Uma tentativa de
codificar esta relação em
Prolog seria:
antepassado(X,Y) :progenitor(X,Y).
progenitor
Júlia
(a)
Íris
progenitor
antepassado direto
Jorge
(b)
antepassado indireto
antepassado(X,Y) :progenitor(X,Z),
progenitor(Z,Y).
... (indefinidamente).
Claramente, uma má
solução. (Por que?)
11
Introdução à Programação Prolog
Predicados Recursivos
Uma representação mais
geral:
João
antepassado(X,Y) :progenitor(X,Y).
progenitor
Íris
antepassado
antepassado
...
Uma codificação recursiva
para antepassado/2:
antepassado(X,Y) :progenitor(X,Z),
antepassado(Z,Y).
... (só!).
Y
Por que esta solução é
melhor que a anterior?
12
Introdução à Programação Prolog
Caminhos em Grafos
Seja o grafo direcionado abaixo:
B
2
1
3
E
2
D
4
A
F
4
5
5
conecta(a,b,3).
conecta(a,c,4).
...
conecta(e,f,2).
C
E as relações conecta(X,Y,K) e
caminho(X,Y,K), onde X e Y são
nodos e K é o custo entre eles.
Ao lado, em Prolog:
caminho(X,Y,K):conecta(X,Y,K).
caminho(X,Y,K):conecta(X,Z,K1),
caminho(Z,Y,K2),
K is K1+K2.
?- caminho(X,Y,K).
X=a, Y=b, K=3;
...
no
13
Introdução à Programação Prolog
Predicados Recursivos
• Referenciam a si próprios.
• Possuem, no mínimo, duas cláusulas, uma recursiva
e a outra não.
• A cláusula não-recursiva denomina-se cláusula
básica.
• As cláusulas básicas podem ser regras ou fatos.
• As cláusulas recursivas são sempre regras.
• O predicado recursivo somente é bem sucedido na
cláusula básica.
• A cláusula recursiva nunca é bem sucedida.
14
Introdução à Programação Prolog
Programa Prolog
Consulta:
?-pai(joão, X).
Teorema a
ser provado
É executado a
partir de uma
consulta ou
cláusula
objetivo
( A)
Programa
PROLOG
Sistema
PROLOG:
Regras de
Inferência
Método de
Dedução SLD
Conjunto de
axiomas
Resultado:
sim/não ou
instanciações
das variáveis
da consulta
que permitem
prová-la
verdadeira no
contexto do
programa.
Cada
predicado
denota uma
relação
O domínio do
problema é
representado
como um
conjunto de
relações em
notação clausal
Conjunto de
Predicados
Predicados são
conjuntos de
cláusulas com
o mesmo nome
e aridade (no.
de argumentos)
Um predicado é
verdadeiro se pelo
menos uma das
suas cláusulas é
verdadeira.
A é verdadeiro
Fatos:
Verdades
incondicionais
Regras:
Verdades
condicionais
A
A  B, C, D ...
A é verdadeiro
se B, C, D ...
são todos
verdadeiros
Fato:
pai(joão, josé).
Regra:
pai(X, Y) :masculino(X),
progenitor(X, Y).
Variáveis
começam com
maiúsculas e
constantes com
minúsculas
15
Introdução à Programação Prolog
Tema para Casa
Criar a base de fatos da sua árvore genealógica
(inicialmente só com as relações progenitor/2,
masculino/1 e feminino/1).
Enriquecer com outras relações de parentesco além
das apresentadas (por exemplo: bisavó/2,
cunhado/2, ... etc).
Testar! (por exemplo: quem é tio de X?)
Sugestão: Pedir a ajuda das pessoas mais velhas
da família.
16
Introdução à Programação Prolog