Universidade Católica de Pelotas
Centro Politécnico
Laboratório de Modelagem Computacional
Introdução à Modelagem Conceitual
3. Prolog
Luiz A M Palazzo
Abril, 2011
O que é
PROLOG ?
PROgrammation en LOGique
Alain Colmerauer
Univ. Aix-Marseille, 1972
Robert Kowalski
Univ. Edimburgo, 1974
Introdução à Modelagem Conceitual - 03 PROLOG
2
Programação em Lógica
Sócrates é homem.
Todo homem é mortal.
Quem é mortal?
Sócrates é mortal.
Introdução à Modelagem Conceitual - 03 PROLOG
homem(sócrates).
mortal(X)  homem(X).

?- mortal(Z).
Z = sócrates.
3
Fatos,
Regras e
Consultas
A programação em lógica
baseia-se em estruturas lógicas
denominadas Cláusulas de Horn,
que se apresentam em quatro
formas distintas:
Fatos
Regras
Consultas
Vazia
Introdução à Modelagem Conceitual - 03 PROLOG
a
ab
b

4
Fatos,
Regras e
Consultas
Introdução à Modelagem Conceitual - 03 PROLOG
• Fatos:
São verdades incondicionais:
pai(josé, joão).
pai(joão, júlio).
pai(júlio, jorge).
5
Fatos,
Regras e
Consultas
• Fatos:
São verdades incondicionais
:
pai(josé, joão).
pai(joão, júlio).
pai(júlio, jorge).
• Regras:
Podem ser verdadeiras ou não
:
filho(X, Y)  pai(Y, X).
avô(X, Y)  pai(X, Z), pai(Z, Y).
Introdução à Modelagem Conceitual - 03 PROLOG
6
Fatos,
Regras e
Consultas
• Fatos:
São verdades incondicionais:
pai(josé, joão).
pai(joão, júlio).
pai(júlio, jorge).
• Regras:
Podem ser verdadeiras ou não:
filho(X, Y)  pai(Y, X).
avô(X, Y)  pai(X, Z), pai(Z, Y).
• Consultas:
Provocam a execução do programa:
?- filho(júlio, X).
?- avô(X, jorge).
Introdução à Modelagem Conceitual - 03 PROLOG
X=joão
X=joão
7
Aplicações Avançadas em Prolog
•
•
•
•
•
•
•
•
•
Sistemas Especialistas,
Engenharia de Software,
Simulação,
Educação,
Suporte à Decisão,
Programação Científica,
Processamento da Linguagem,
Bases de Dados Dedutivas,
Programação da Web.
A Cláusula Prolog
“se”
“e”
“ou”
a :- b1, b2 ... bi ; bj ... bn.
Condição
Cabeça
Corpo
Introdução à Modelagem Conceitual - 03 PROLOG
9
Operadores Prolog
Linguagem
Natural
E
OU
SE
NÃO
Introdução à Modelagem Conceitual - 03 PROLOG
Cálculo de
Predicados

Programas
Prolog
,



;
:not
10
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
Introdução à Modelagem Conceitual - 03 PROLOG
11
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 à Modelagem Conceitual - 03 PROLOG
que pode ser consultada de várias
maneiras:
?- progenitor(joão, ana).
true
?- progenitor(joão, jorge).
false
?- progenitor(joão, X).
X=josé;
X=ana;
false
?- progenitor(X,Y).
X=maria, Y=josé;
X=joão, Y=josé;
...
X=íris,
Y=jorge;
false
12
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 (um só argumento),
podem ser pensadas como
sendo atributos dos objetos a
que se aplicam.
Introdução à Modelagem Conceitual - 03 PROLOG
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).
13
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.
Introdução à Modelagem Conceitual - 03 PROLOG
Em Prolog:
pai(X,Y) :progenitor(X,Y),
masculino(X).
mãe(X,Y) :progenitor(X,Y),
feminino(X).
14
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 ...
Introdução à Modelagem Conceitual - 03 PROLOG
Em Prolog:
irmão(X,Y) :progenitor(Z,X),
progenitor(Z,Y),
masculino(X).
irmã(X,Y) :- ...
mas, esta regra tem um
problema. (qual?)
15
Exercício
Acrescentar ao programa da árvore
genealógica as seguintes relações
(em 10 minutos):
avô/2
tia/2
prima/2
Introdução à Modelagem Conceitual - 03 PROLOG
16
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.
Agora, 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;
false
Introdução à Modelagem Conceitual - 03 PROLOG
gaúcho(X):nasceu(X,Y),
fica(Y,rs).
17
Predicados Recursivos
Seja, por exemplo, a relação
antepassado/2:
Uma tentativa de codificar
esta relação em Prolog seria:
antepassado(X,Y) :progenitor(X,Y).
Maria
progenitor
João
progenitor
Júlia
(a)
Íris
progenitor
antepassado(X,Y) :progenitor(X,Z),
progenitor(Z,Y).
... (indefinidamente).
antepassado direto
Jorge
(b)
Claramente, uma má solução.
(Por que?)
antepassado indireto
Introdução à Modelagem Conceitual - 03 PROLOG
18
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
Introdução à Modelagem Conceitual - 03 PROLOG
Por que esta solução é
melhor que a anterior?
19
Caminhos em Grafos
Seja o grafo direcionado abaixo:
B
2
1
3
E
2
D
4
A
F
4
5
5
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:
Introdução à Modelagem Conceitual - 03 PROLOG
conecta(a,b,3).
conecta(a,c,4).
...
conecta(e,f,2).
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;
...
false
20
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.
Introdução à Modelagem Conceitual - 03 PROLOG
21
Programa Prolog
Consulta:
?-pai(joão, X).
Teorema a
ser provado
Sistema
PROLOG
Dedução SLD
É executado a
partir de uma
consulta ou
cláusula
objetivo
( A)
Cada
predicado
denota uma
relação
Programa
PROLOG
Conjunto de
Predicados
Conjunto de
axiomas
Predicados são
conjuntos de
cláusulas com
o mesmo nome
e aridade
Resultado:
Instanciações
das variáveis
da consulta
que permitem
prová-la
verdadeira.
Introdução à Modelagem Conceitual - 03 PROLOG
Um predicado é
verdadeiro se pelo
menos uma das
suas cláusulas é
verdadeira
Problema
do
Mundo Real
O domínio do
problema é
representado
como um
conjunto de
relações
A é verdadeiro
Fatos:
Verdades
incondicionais
Regras:
Verdades
condicionais
A
pai(joão, josé).
A  B, C, D ...
pai(X, Y) :masculino(X),
progenitor(X, Y).
A é verdadeiro
se B, C, D ...
são todos
verdadeiros
Variáveis
começam com
maiúsculas e
constantes com
minúsculas
22
Exercício
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.
Introdução à Modelagem Conceitual - 03 PROLOG
23
Ponteiros
• Prolog na Wikipedia
http://pt.wikipedia.org/wiki/Prolog
•
• Programação em Lógica
http://vl.fmnet.info/logic-prog/
• SWI Prolog
http://www.swi-prolog.org
Introdução à Modelagem Conceitual - 03 PROLOG
24