Universidade Federal de São Carlos
Departamento de Computação
Programação Lógica
Prof. Dr. Antonio Francisco do Prado
e-mail: [email protected]
1
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
2
Programação Lógica
Raízes
O uso da lógica na representação do raciocínio
remonta os estudos de Boole (1815-1864) e de De
Morgan (1806-1871) sobre a “Álgebra de Boole”;
Em 1879 surge a primeira versão do “Cálculo de
Predicados” com o matemático alemão Göttlob Frege,
onde era oferecida uma representação adequada para a
formalização do raciocínio dedutivo;
Em 1930, em estudos simultâneos, o alemão Kurt
Gödel e o francês Jacques Herbrand demonstraram que
o mecanismo de prova do Cálculo de Predicados
poderia oferecer uma prova formal de toda proposição
logicamente verdadeira;
Ainda na década de 30 diversos estudos, entre eles os
de Alan Turing e Alonzo Church, aproximaram muito o
Cálculo de Predicado com a forma como hoje é
conhecido;
Em 1939 toda fundamentação teórica básica da
lógica computacional já estava pronta, faltava apenas
uma meio prático para realizar o imenso volume de
computações necessárias aos procedimentos de prova;
3
Somente nos meados da década de 50 que o
desenvolvimento
dos
computadores
permitiu
experiências mais significativas com o Cálculo de
Predicados;
Em 1958 uma forma simplificada do Cálculo de
Predicados denominada forma Clausal começou a
despertar o interesse dos estudiosos. Nessa forma de
cálculo era empregado um tipo muito simples de
sentença lógica, a Cláusula;
Também nessa época (1960) Dag Prawitz propôs um
novo tipo de operação sobre os objetos do Cálculo de
Predicados, que foi mais tarde conhecido como
Unificação;
 Apesar de toda base teórica para a Programação
Lógica estar pronta, ela somente se tornou possível a
partir da pesquisa sobre prova matemática de
teoremas, particularmente no desenvolvimento do
Princípio da Resolução por J.A. Robinson (1965);
A expressão “Programação Lógica” (Logic
Programming) surge com Robert Kowalski (1974) e
designa o uso da lógica como uma linguagem de
programação de computadores.
OBS: muitos outros pesquisadores colaboraram para o
aparecimento da Programação Lógica. No texto apenas foram
relatados alguns deles.
4
Conceitos da Programação Lógica
Uma das principais idéias em Programação Lógica é
que um algoritmo é constituído por dois elementos
disjuntos:
Lógica: corresponde à definição do que deve ser
solucionado;
Controle: estabelece como a solução pode ser
obtida;
A tarefa do programador é somente descrever
(especificar) o componente lógico do algoritmo,
deixando o controle da execução para ser exercido
pelo sistema de programação em lógica utilizado;
Um Programa em Lógica é então a representação de
determinado problema ou situação expressa através
de um conjunto finito de um tipo especial de sentenças
lógicas, denominadas cláusulas;
O paradigma fundamental da programação em
lógica é o da Programação Declarativa, em oposição à
Programação Procedimental típica das linguagens
convencionais;
O ponto focal da Programação em Lógica consiste
em identificar a noção de computação com a noção de
dedução, onde a execução de programas se reduzem à
pesquisa da refutação das sentenças do programa em
conjunto com a negação da sentença que expressa a
consulta, seguindo a regra: "uma refutação é a
dedução de uma contradição".
5
Os termos "programação em lógica" e "programação
Prolog" tendem a ser empregados indistintamente.
Deve-se, entretanto, destacar que a linguagem Prolog é
apenas uma particular abordagem da Programação em
Lógica;
Pode-se expressar conhecimento (programas e/ou
dados) em Prolog por meio de cláusulas de dois tipos:
Fatos: denota uma verdade incondicional;
Regras: definem as condições que devem ser
satisfeitas para que uma certa declaração seja
considerada verdadeira.
Características da Programação Lógica
Os sistemas de Programação em Lógica em geral e a
linguagem Prolog em particular possuem as seguintes
propriedades:
 Funcionam simultaneamente como linguagem de
programação e de especificação;
Possuem capacidade dedutiva;
Operam de forma não-determinística;
Permitem a representação de relações reversíveis;
Permitem interpretação declarativa, operacional e
procedimental;
São naturalmente recursivas.
6
Aplicações da Programação Lógica
As principais aplicações da Programação em Lógica
são:
Sistemas Baseados em Conhecimento (SBCs)
Sistemas de Bases de Dados (BDs);
Sistemas Especialistas (SEs);
Processamento da Linguagem Natural (PLN);
Educação;
Modelagem de Arquiteturas Não-Convencionais.
Linguagens Convencionais x Lógicas
PROGRAMAS
CONVENCIONAIS
PROGRAMAS EM
LÓGICA
Processamento
Numérico
Processamento
Simbólico
Soluções Algorítmicas
Soluções Heurísticas
Estruturas de Controle
e Conhecimento
Integradas
Estruturas de Controle
e Conhecimento
Separadas
Difícil Modificação
Fácil Modificação
Somente Respostas
Totalmente Corretas
Incluem Respostas
Parcialmente Corretas
Somente a Melhor
Solução Possível
Incluem Todas as
Soluções Possíveis
7
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
8
Linguagem PROLOG
Linguagens Funcionais x Lógicas
Funcional
Lógica
Programação orientada
para funções
Diz “como fazer” para
atingir um objetivo
Mais voltada para
algoritmos que exploram o
conhecimento
Preocupa-se com aspectos
relacionados com a
construção de listas, tipos,
padrão de comparação,
estruturas de dados, etc.
Camada mais baixa de
suporte para as aplicações
Programação orientada
para objetivos (“goal”)
Diz “o que fazer” para
atingir um objetivo
Mais voltada para o
conhecimento
Mais declarativa do que
procedural
Nível mais elevado de
abstração na solução dos
problemas
Conclusão
Tanto as linguagens Funcionais como Lógicas são
importantes e empregadas principalmente em Sistemas
Transformacionais, Inteligência Artificial (IA) e
Robótica.
9
Histórico
Criado por Alain Colmerauer por volta de 1970 na
Universidade de Marselha, França.
Seu objetivo inicial era servir de apoio a sistemas de
Linguagem Natural.
Algol 60
Algol 68
Prolog
Programação Prolog
Para executar um programa em prolog, primeiro deve-se
criar um arquivo com a extensão correspondente do
interpretador ( .ari, .pl, etc). Depois, execute no
interpretador correspondente. Em seu menu acione a
opção File e Consult para carregar o programa no
interpretador. Se houver algum erro no programa, este
será mostrado na tela, senão o programa está pronto para
ser executado (interpretado).
10
A programação Prolog consiste fundamentalmente em:
 Declarar fatos ou assertivas;
 Estabelecer regras ou procedimentos; e
 Fazer perguntas.
Os fatos e as regras são fornecidos e a linguagem usa
dedução para obter respostas para as questões.
11
Considerações sobre o aprendizado do aluno
Temos observado que o estilo procedimental de
programação, talvez por ser o primeiro a ser
ensinado, interfere de certa forma, na correta
aprendizagem de linguagens como Lisp ou
Prolog por parte dos estudantes.
Tentaremos minimizar essa interferência
submetendo o aluno a resolução de conjuntos
de problemas semelhantes, principalmente
problemas envolvendo listas.
É essencial que o aluno tente compreender a
lógica de programação Prolog, entendendo
mecanismos de unificação, backtracking entre
outros.
Também é importante que o aluno tente
resolver os exercícios propostos no ultimo
capítulo, para consolidar o seu aprendizado.
12
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
13
Fatos, Regras e Controle de
Corte
Introdução
Um programa Prolog consiste de :
• Definição de fatos a respeito de objetos de dados e
suas relações;
• Definição de regras a respeito de objetos de dados e
suas relações;
• Interrogação a respeito de objetos de dados e suas
relações.
Um objeto de dados em Prolog é definido de acordo
com a seguinte árvore :
objetos
objetos simples
constantes
átomos
números
estruturas
variáveis
14
• Átomo é a estrutura mais simples do Prolog, eles
são construídos por cadeias de letras, dígitos e
caracteres especiais( _, +, *). Todo átomo deve
possuir a primeira letra minúscula. Exemplos de
átomos : x_y, maria, copa2002.
• Números em Prolog incluem números inteiros e
números reais. A sintaxe é bem simples : 1, -20.
• Variáveis são cadeias de letras, dígitos e caracteres
sempre começando com letra maiúscula.
• Estruturas são objetos de dados que têm vários
componentes, podendo cada um deles, por sua vez,
ser uma outra estrutura.
Por exemplo, uma data pode ser vista como um
conjunto de dia, mês e ano. Embora composta por
vários componentes, estruturas são tratadas no
programa como objetos simples. A combinação dos
componentes de um objeto simples é feita através de
seu funtor. No caso de data, o funtor pode ser data e
pode – se escrever 7 de setembro de 2002 da seguinte
maneira :
data(7, setembro, 2002)
Note que os componentes 7, setembro e 2002 são
todos constantes(2 inteiros e 1 átomo)
15
Fatos, Regras e Controle de
Corte
Fatos
Um Fato denota uma verdade incondicional. Uma relação
pode ser especificada por um fato.
Sintaxe : predicado(arg1[,arg2,...,arg n]).
Argumentos (arg1...arg n) são objetos quaisquer e
Predicado é a relação que une esses objetos.
tom
pam
liz
bob
pat
ann
jim
16
progenitor(pam,bob).
progenitor(tom,bob).
progenitor(tom,liz).
progenitor(bob,ann).
progenitor(bob,pat).
progenitor(pat,jim).
%pam é um dos progenitores de bob
%tom é um dos progenitores de liz
Em Prolog usam-se maiúsculas para variáveis e
minúsculas para átomos.
Questões:
átomo
?-progenitor(bob,pat).
yes
?-progenitor(liz,pat).
no
?-progenitor(X,liz).
X=tom ;
no
?-progenitor(bob,X).
X=ann
X=pat
variável
?progenitor(X,Y).
X=pam ,
Y=bob ;
X=tom ,
Y=bob ;
X=tom ,
Y=liz ;
X=bob ,
Y=ann ;
X=bob ,
Y=pat ;
X=pat ,
Y=jim ;
17
 Quem são os avós de Jim?
(1) Quem é progenitor de Jim? (Por exemplo, Y) e
(2) Quem é progenitor de Y? (Por exemplo, X).
X
Progenitor
Y
Avos
Progenitor
jim
"Encontre X e Y tais que X é progenitor de Y e Y é
progenitor de Jim".
Questões:
?-progenitor(X, Y), progenitor(Y, jim).
X=bob Y=pat ;
 Quem é neto de Tom?
Questões:
?-progenitor(tom, X), progenitor(X, Y).
X=bob Y=ann;
X=bob Y=pat.
18
 Definição de uma extensão da base anterior
(característica do objeto):
mulher(pam).
homem(tom).
homem(bob).
mulher(liz).
mulher(pat).
mulher(ann).
homem(jim).
Regras
As regras definem as condições que devem ser satisfeitas
para que uma certa declaração seja considerada
verdadeira.
Sintaxe : pred(arg/Var,arg/Var) :- pred(arg/Var,arg/Var).
cabeça
se
(conclusão)
corpo
(condição)
Onde o símbolo :- indica uma condição (se) e separa a
regra em conclusão ou cabeça da regra e condição ou
corpo da regra.
19
 Definir a relação filho.
 Poderia ser definida como:
filho(bob,tom).
filho(bob,pam).
...
 Entretanto existe uma maneira mais elegante, que
seguiria a seguinte declaração:
Para todo X e Y
Y é filho de X se
X é progenitor de Y.
filho(Y, X) :- progenitor(X, Y).
"Para todo X e Y, se X é progenitor de Y, então Y é filho
de X".
Questões:
?-filho(jim,pat).
yes
filho(Y, X) :- progenitor(X, Y)
cabeça 
(conclusão)
se
 corpo
(condição)
20
Frases Compostas
robo(peter).
capaz_de_fazer(peter,armas).
machuca(armas,pedro).
homem(pedro).
proibido_fazer(R,B):-robo(R),capaz_de_fazer(R,B),
machuca(B,H),humano(H).
Questão
? - proibido_fazer(R,B).
R = peter ,
B = armas
Significa: R está proibido de fazer um ato B se R for um robô
e R for capaz de fazer B e B machuca H e H for humano.
Para todo R e B proibido_fazer(R,B) se existe H tal que
robo(R) e capaz_de_fazer(R,B) e machuca(B,H) e humano(H).
humano(H):-homem(H).
Hífen
Usa-se o hífen para indicar irrelevância de um objeto
Exemplo:
aniversario(maria,data(25,janeiro,1979)).
aniversario(joao,data(5,janeiro,1956)).
signo(Pessoa,aquario):-aniversario(Pessoa,data(Dia,janeiro,_)),
Dia >= 20.
? - signo(Pessoa,aquario).
Pessoa = maria;
no
21
Conjunção e Disjunção
Em prolog o operador de conjunção e ( , ) implica na
necessidade de aceitação de todas as condições, enquanto
o operador de disjunção ou ( ; ) permite a aceitação de
uma ou outra condição. Estes operadores permitem a
composição de fatos.
Exemplos:
amiga(X):-(X = maria; X = joana).
disjunção ou
 Definição de uma regra avos:
Usando-se a conjunção podemos definir o predicado
avos seguindo a seguinte declaração:
Para todo X e Z
X é progenitor de Y e
Y é progenitor de Z.
"Para todo X e Z, se X é progenitor de Y, e Y é
progenitor de Z, então X é um dos avos de Z".
avos(X,Z):-progenitor(X,Y) , progenitor(Y,Z).
Questões:
?-avos(bob,jim).
yes
?-avos(liz,jim).
no
conjunção e
?-avos(pam,X).
X=ann ;
X=pat
22
 Definição de uma regra mãe:
mae(X,Y):-progenitor(X,Y),mulher(X).
Questões:
?-mae(pat,jim).
yes
?-mae(bob,ann).
no
 Definição de uma regra irmã:
irma(X,Y):-progenitor(Z,X),progenitor(Z,Y),mulher(X).
Z
progenitor
mulher
Questões:
?-irma(ann,pat).
yes
X
progenitor
irmã
Y
?-irma(X,pat).
X=ann ;
X=pat ;
no
 Definição de uma regra diferente:
diferente(X,Y):-X\==Y.
%X é diferente de Y
23
 Definição de uma regra irmã usando a regra
diferente:
irma(X,Y):-progenitor(Z,X),progenitor(Z,Y),diferente(X,Y).
Questão:
?-irma(X,pat).
X=ann ;
no
 Definição de uma regra tia:
tia(X,Y):-progenitor(Z,Y),irma(X,Z).
Questão:
?-tia(liz,X).
X=ann ;
X=pat ;
no
Recursão
Definição de uma regra antepassado
Necessita de duas regras: antepassados diretos e
antepassados indiretos.
bob
Antepassados
diretos
pat
Antepassados
indiretos
jim
24
Primeira regra bastante simples:
Para todo X e Z
X é antepassado de Z se
X é progenitor de Z.
antepassado(X, Z) :- progenitor(X, Z).
Segunda regra complicada. A cadeia de progenitores
pode se estender indefinidamente:
antepassado(X, Z) :- progenitor(X, Y),
progenitor(Y, Z).
antepassado(X, Z) :- progenitor(X, Y1),
progenitor(Y1, Y2),
progenitor(Y2, Z).
antepassado(X, Z) :- progenitor(X, Y1),
progenitor(Y1, Y2),
progenitor(Y2, Y3),
progenitor(Y3, Z).
....
25
 Solução: definir a regra recursivamente
Para todo X e Z
X é antepassado de Z se
existe um Y tal que
X é progenitor de Y e
Y é antepassado de Z.
X
Progenitor
Y
Antepassado
Antepassado
Z
A segunda regra fica:
antepassado(X, Z) :- progenitor(X, Y),
antepassado(Y, Z).
Questões:
?-antepassado(X,liz).
X=tom ;
no
?-antepassado(X,pat).
X=bob ;
X=pam ;
X=tom ;
no
26
Controle de Corte
Há ocasiões em que, por um ou outro motivo, desejamos
controlar a execução do programa. Para isso, utilizamos
o mecanismo de corte.
Operador Cut
Algumas
das principais aplicações do cut são as
seguintes:
Unificação de padrões, de forma que quando
um padrão é encontrado os outros padrões
possíveis
são
descartados
(quando
uma
determinada regra é a última a ser analisada e haveria
problemas na continuidade da verificação das demais
regras);
Para eliminar da árvore de pesquisa soluções
alternativas quando uma só é suficiente;
Especificar regras mutuamente exclusivas,
expressas na forma: Se P então Q senão R;
Como indicativo do caso limite ou para evitar que a
pesquisa prossiga indefinidamente através do
backtracking.
Simbolizado
Seu
pela exclamação (“!”).
uso deve ser considerado pelas seguintes
razões:
Execução mais rápida do programa (não
desperdiça tempo tentanto satisfazer objetivos
que não contribuirão para a solucão desejada);27
Economiza
memória (corta a ávore de
pesquisa).
Exemplos:
Podemos simular a programação procedimental em
Prolog. Aqui simularemos a estrutura if-then-else:
ifThenElse(X,Y,Z)
"Se X for verdadeiro, então execute Y, senão execute Z".
ifThenElse(X, Y, _) :- X, !, Y.
ifThenElse(_, _, Z) :- Z.
Questão:
?-ifThenElse(X, Y is Z+1, Y is 0).
OBS: este programa emprega meta-variáveis (variáveis que podem ser
instanciadas com chamadas a predicados)
 Exemplo do operador Cut:
amigo(joana,ana).
amigo(maria,ana).
amigo(pedro,jose).
amigo(pedro,ana).
um_unico_amigo(X,Y):-amigo(X,Y),!.
Questões:
?- um_unico_amigo(X,ana). ?- um_unico_amigo(pedro,X).
X = joana
X = jose
 Mínimo entre dois números:
minimo(X,Y,X):-X =< Y, !.
minimo(X,Y,Y):-X > Y, !.
Questões:
?- minimo(10,3,Min).
?- minimo(12,56,Min).
Min = 3
Min = 12
28
Fail
O predicado Fail, força um retrocesso, como se indicasse
uma falha. Junto com o corte (Cut), acelera a avaliação
de regras economizando memória.
Exemplos:
 Exemplo do operador Fail:
cliente(ana,123,bradesco).
cliente(jose,456,itau).
executa :- cliente(Nome,Conta,Agencia),
write(Nome),write(’ tem conta ’),write(Conta),
write(’ na agencia ’),write(Agencia),nl,fail.
 Neste caso fail força um backtracking e repete a
a impressão.
Questões:
?-executa.
ana tem conta 123 na agencia bradesco
jose tem conta 456 na agencia itau
no
Not (X)
O operador unário not define uma forma particular de
negação denominada "negação por falha”.
29
 Definição de uma regra para exemplificar o not:
estudante(jorge).
casado(jose).
estudante_solteiro(X):-not casado(X), estudante(X).
Questões:
?-estudante_solteiro(jorge).
yes
?-estudante_solteiro(jose).
no
Cuidados com o Cut e a Negação
O uso do cut pode levar a perda da correspondência
entre o significado declarativo e a interpretação
operacional do programa:
Se não houver cuts no programa pode-se trocar a
ordem das cláusulas e objetivos que seu significado
declarativo não será alterado (há apenas uma
possível perda de performance);
Se houver cuts essa alteração pode afetar o
significado declarativo levando a resultados
inesperados.
O uso da negação também pode levar a
resultados inesperados. Qual o problema do
programa abaixo?
Questões:
r(a).
q(b).
?-q(X), p(X).
?-p(X), q(X).
p(X) :- not r(X).
X = b.
no
30
Outros Exemplos de Regra
 Definição das regras positivo e negativo:
positivo(X):-X>=0.
%X é maior ou igual a 0
negativo(X):-X<0.
%X é menor que 0
Questões:
?-positivo(7).
?-negativo(10).
yes
no
 Máximo entre 2 números:
max(X,Y,X):-X>=Y.
max(X,Y,Y):-X<Y.
 Máximo entre 2 números usando corte:
max(X,Y,X):-X>=Y,!.
max(X,Y,Y).
Questão:
?-max(10,3,Max).
Max=10
 Definição das regras par e impar:
par(X):-X mod 2 =:=0
% o mod de 2 é igual a 0
impar(X):-par(X),!,fail.
impar(X).
Questões:
?-par(6).
?-impar(6).
yes
no
31
 Definição de uma função f(X):
f(X, 0):- X < 3.
f(X, 2):- 3=< X, X < 6.
f(X, 4):- 6 =< X.
4
3
Y=F(X) 2
Y=f(X)
1
0
0
1
2
3
4
5
6
7
8
9 10
X
 Definição de uma função f(X) com corte:
f(X, 0):- X < 3, ! .
f(X, 2):- 3 =< X, X < 6, ! .
f(X, 4).
Questões:
?-f(1,Y),2<Y.
no
?-f(7,Y).
Y=4
 Definição de uma regra para fatorial:
fatorial(0, 1):- !.
fatorial(N, F):- N1 is N - 1,
%Atribuição
fatorial(N1, F1),
F is F1 * N.
Questão:
?- fatorial(4, F).
F = 24
32
Exemplo de recursividade
Para o exemplo anterior da regra do Fatorial recursivo,
é mostrado a execução passo a passo, note que em todos
os passos(com excessão do 5) há unificação com a
segunda regra. (primeira regra é critério de parada).
Questão:
?- fatorial(4, F).
F = 24
Passo 1 :
fatorial(4, F)
{ N = 4, N1 =3, F = F1 * 4, fatorial(N1, F1) }
F=6
Passo 2 :
fatorial(3, F)
{ N = 3, N1 =2, F = F1 * 3, fatorial(N1, F1) }
F=2
Passo 3 :
fatorial(2, F)
{ N = 2, N1 =1, F = F1 * 2, fatorial(N1, F1) }
F=1
Passo 4 :
fatorial(1, F)
{ N = 1, N1 =0, F = F1 * 1, fatorial(N1, F1) }
F=1
Passo 5 :
fatorial(0, F)
{F = 1 }
33
 Definição de uma regra para fatorial com recursão de
cauda:
fact(N,Fn):-fact(N,Fn,0,1).
fact(N,Fn,N,Fn):-!.
fact(N,Fn,I,P):-Novoi is I+1,Novop is P*Novoi,
fact(N,Fn,Novoi,Novop).
Questão:
?- fact(6, F).
F = 720
Recursão de cauda. A
recursividade é a última.
 Definição de uma regra para fibonacci:
fib(1, 1).
fib(2, 1).
fib(N, F):- N > 2,
N1 is N - 1, fib(N1, F1),
N2 is N - 2, fib(N2, F2),
F is F1 + F2.
Questão:
?- fib(6, F).
F=8 ;
no
34
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
35
Operadores e Listas
Operadores Aritméticos
+
Adição
-
Subtração
*
Multiplicação
/
Divisão
mod
is
Módulo, o resto inteiro da divisão
Atribuição
Exemplo:
 Cálculo de um número elevado ao quadrado:
ao_quadrado(X,Y):-Y is X*X.
Questão:
?- ao_quadrado(6,X).
X=36
36
Operadores de Comparação
X>Y
X é maior que Y
X<Y
X é menor que Y
X >= Y X é maior ou igual a Y
X =< Y X é menor ou igual a Y
X =:= Y Os valores de X e Y são iguais
X \== Y Os valores de X e Y são diferentes
Exemplo:
 Definição de uma regra intervalo aberto:
interv_aberto(K,X1,X2):-K > X1,K < X2.
Questões:
?- interv_aberto(5,0,5).
no
?- interv_aberto(2,0,5).
yes
37
Listas
As listas são estruturas de dados dinâmicas com as quais
é possível a construção de vetores e matrizes.
Sintaxe : pred([elem,...],[],[elem[elem,...],...],arg,...).
Onde elem pode ser qualquer tipo sintático.
Listas são compostas por cabeça e cauda. A cabeça de
uma lista pode ser qualquer objeto Prolog e a cauda
deve ser uma lista. Como a cauda, por sua vez, é uma
lista, ela á a lista vazia ou tem sua própria cabeça e
cauda.
Sintaxe para Listas
A lista vazia é denotada por [] ; a lista que tem cabeça
X e cauda Y é denotada por [X|Y] . Dentro das listas, os
elementos são separados por vírgula. Exemplo :
Lista
[gosto,de, vinho]
[X,Y|Z]
[[o,gato]]
Cabeça
Cauda
gosto
X
[o,gato]
[de, vinho]
[Y|Z]
[]
38
Unificação em listas
Em Prolog, a mais importante operação envolvendo
termos é chamada unificação. Dois termos T e S
unificam se :
1. Se T e S são constantes, então unificam se e só se S e
T são o mesmo objeto.
2. Se S for uma variável e T qualquer termo, então
unificam, e S é instanciado com T ; vicer – versa, com a
variável T instanciada com S.
3. Se S e T são estruturas, eles unificam se e só se S e T
tem o mesmo funtor principal e todos os elemtentos
correspondentes unificam.
A seguir são mostrados vários exemplos de unificação
em listas :
Lista 1
[mesa]
[a,b,c,d]
[[ana, Y] | Z]
[ano, bissexto]
Lista 2
[X|Y]
Unificação
X / mesa
Y/[]
[X,Y|Z]
X/a
Y/b
Z / [c,d]
[[X, foi], [ao, cinema]] X / ana
Y / foi
Z / [[ao, cinema]]
[X,Y|Z]
X / ano
Y/ bissexto
39
Z/[]
Lista 1
[ano, bissexto]
Lista 2
[X,Y,Z]
[data(7,Z,W), hoje]
[X,Y]
[data(7,W,1993), hoje]
[data(7,X,Y), Z]
Unificação
não unifica
(aridade diferente)
X / data(7,Z,W)
Y / hoje
X/W
Y / 1993
Z / hoje
Busca recursiva
Freqüentemente é necessário procurar por algum
termo Prolog ; isto resulta em uma busca recursiva.
Para verificar se um elemento pertence à uma lista,
usamos o seguinte predicado:
pertence(X, [X | _]). % verifica se X esta na cabeça
pertence(X, [_ | Y]):- pertence(X, Y). % verifica se X
% esta na cauda
Questões:
?- pertence(a, [h, a, b]).
yes
?- pertence( a, [hoje, amanha]).
no
?- pertence(X, [a, b, c]).
X = a;
X = b;
X = c;
no
40
Goal
?- X = [1,2,3],pertence(a,X).
no
?- pertence( a, X),X = [1,2,3].
X = [a |_]
%pode ser o 1º elemento de X
X = [_ , a | _]
%pode ser o 2º elemento de X
X = [_ , _ , a | _]
%pode ser o 3º elemento de X
. . .
%computação infinita!
Sequência de ligação -> da esquerda para a direita
Conclusão
Escolha o “subgoal” com o menor número de soluções
como “goal” a adivinhar.
No caso anterior o “goal” a adivinhar correto é X = [1,2,3],
porque tem apenas uma solução e esta solução não satisfaz
pertence(a,X), porque “a” não está na lista [1,2,3].
41
Controle em Prolog
1. Iniciar pelo goal
2. Enquanto o goal corrente não é vazio faça
2.1. Comece pelo subgoal mais à esquerda
2.2. Se uma regra aplica ao subgoal então
2.2.1. Para esta regra, usando
unificadores genéricos, volte
para 2.1
Senão
backtrack
fim-se
fim-enquanto
Exemplo:
anexa([ ],Y,Y ).
anexa([H | X],Y,[H| Z]):- anexa(X, Y,Z).
prefix(X,Z):-anexa(X,Y,Z).
sufix(Y,Z):-anexa(X,Y,Z).
42
 1º Subgoal
?- sufix ( [ a ] , L ) , prefix ( L , [ a , b , c ] ).
L=[ a] ;
%sem backtraing X = [ ] Y = [ b , c ]
 O fato sufix ( Y´ , Z´ ) :- anexa ( X´ , Y´ , Z´ ) aplica ao
subgoal mais à esquerda sufix ( [ a ] , L )
 A substituição Y´ -> [ a ] , Z´ -> L
Unifica a cabeça da regra com o subgoal sufix ( [ a ] , L )
Tem-se então: sufix ( [ a ] , L ) if anexa ( _1 , [ a ] , L )
nome Prolog
 Substituindo pela condição tem-se:
anexa ( _1 , [ a ] , L ) , prefix ( L , [ a , b , c ] )
 O fato
anexa ( [ ] , Y´´ , Y´´ ) aplica ao novo subgoal
mais á esquerda:
[ ] -> _1 , Y´´ -> [ a ] , Y´´ -> L
 Uma vez que o fato consiste de uma cabeça e
nenhuma condição, o novo goal corrente torna-se:
prefix ( [ a ] , [ a , b , c ] )
substituída -> L
 Tem-se então:
prefix ( [ a ] , [ a , b , c ] ) if anexa ( [ a ] , _2 , [ a , b , c ] ) .
anexa ( [ a ] , _2 , [ a , b , c ] ) if
anexa ( [ ] , _2 , [ b , c ] ).
anexa ( [ ] , _2 , [ b , c ] )
2 -> [ b , c ] anexa ( [ ] , [ b , c ] , [ b , c ] ) .
L=[ a] ;
43
Modos de Chamada
Usando o exemplo do pertence([arg1], [arg2])
mostrado anteriormente, o que aconteceria se as
interrogações fossem :
?- pertence(a,X) % ou
?- pertence(X,Y)
Pode – se observar que cada uma delas tem “infinitas”
respostas, uma vez que existem infinitas listas que
validam estas interrogações para o programa pertence.
Portanto, é necessário definir se os argumentos devem
estar ou não instanciados. Usaremos a seguinte notação
para documentar as formas corretas de interrogação :
modo(<arg – 1>, <arg – 2>, .....,<arg – n>) onde :
<arg – i > = + se <arg – i > deve estar instanciado.
<arg – i > = - se <arg – i > deve ser variável livre.
<arg – i > = ? se <arg – i > puder ser qualquer um dos
casos.
Exemplo : o exemplo pertence ([arg1], [arg2]) tem o
modo(? , +).
44
Outros Exemplos de Lista
 Verificação se um elemento de uma lista não pertence a
outra lista, modo(+, +) :
nao_pertence(X,Y):- \+ (pertence(Z,X),pertence(Z,Y)).
Questões:
?-nao_pertence([a,b],[b,c]).
?- nao_pertence([a,b,c],[d,e,f]). no
yes
 Soma dos elementos de uma lista, modo(+, ?) :
soma([ ], 0).
soma( [Elem | Cauda], S):- soma(Cauda, S1),
S is S1 + Elem.
Questão:
?- soma([1, 2, 3, 4, 5, 6], S).
S = 21
 Verificação se uma lista está ordenada, modo(+) :
ordenada([ ]).
ordenada([X,Y | Resto]):-X=<Y,ordenada([Y | Resto]).
Questões:
?-ordenada([1,5,6,6,9,12]).
yes
?-ordenada([3,2,1]).
no
45
 Verificação se um termo é uma lista, modo(+) :
eh_lista([ ]).
eh_lista(X):- not var(X),
not atom(X).
Onde os predicados:
 var(X) - Verdadeiro se o termo X é uma variável
 atom(X) - Verdadeiro se o termo X é um átomo
Questões:
?- eh_lista([a, b, c, d, e, f]).
yes
?- eh_lista( 2 )
no
?- eh_lista([ ]).
yes
 Duplicação dos elementos de uma lista, modo(+,?) :
duplica([ ], [ ]).
duplica( [X | L], [X, X | L1]):- duplica(L, L1).
Questão:
?- duplica([1, 2, 3], L).
L = [1, 1, 2, 2, 3, 3]
46
 Concatenação de duas listas, modo(+,?,?) :
concatena([ ], Lista, Lista).
concatena([ Elem | Lista1], Lista2, [Elem | Lista3]):concatena(Lista1, Lista2, Lista3).
Questão:
?- concatena([um, dois], [tres, quatro], L).
L = [um, dois, tres, quatro]
Também pode – se usar o modo modo(-,-,+) para
decompor uma lista em duas sublistas.
 Maior elemento de uma lista numérica, modo(+,?) :
max([X], X). % Maior elemento de uma lista com 1
% elemento é o próprio elemento
max([X, Y | Cauda], Max):- X >= Y, ! ,
max([X | Cauda], Max).
max([X, Y | Cauda], Max):- max([Y | Cauda], Max).
Questão:
?- max([1, 10, 100, -1, 20], M).
M = 100 ;
no
 N_ésimo elemento de uma lista, modo(?,?,+) :
n_esimo(1, Elem, [Elem | _]).
n_esimo(N, Elem, [ _ | Cauda]):- n_esimo(M, Elem, Cauda),
N is M + 1.
Questão:
?- n_esimo(4, Elem, [a, b, c, d, e]).
Elem = d ;
no
47
 Inversão de uma lista, modo(+,?) :
inverter([ ],[ ]).
inverter([Elem | Lista1], Lista3):-inverter(Lista1,Lista2),
concatena(Lista2,[Elem], Lista3).
Questões:
?- inverter([a,b,c], L).
L = [c,b,a]
?-inverter([1,2,3,4,5,6],L).
L = [6,5,4,3,2,1]
 Número de elementos em uma lista, modo(+,?) :
tamanho([ ],0).
tamanho([_ | R], N):-tamanho(R, N1),N is N1+1.
Questão:
?- tamanho([a,b,c,d,e], N).
N=5
 Seleção de determinados elementos de uma lista, em
uma lista separada, identificados pela sua posição,
modo(+,+,?) :
seleciona([ ], _, [ ]).
seleciona([M | N], L, [X | Y]):-n_esimo(M, X, L),
seleciona(N, L, Y).
Questão:
?- seleciona([2, 4], [a, b, c, d, e], L).
L = [b, d] ;
no
48
 Ultimo elemento de uma lista, modo(+,?) :
ultimo([Elem], Elem).
ultimo([_|Cauda], Elem) :- ultimo(Cauda, Elem).
Questões:
?- ultimo([casa, bola, carro], X)
X = carro ;
no
 Elementos consecutivos em uma lista, modo(?,?,+) :
consecutivos(E1,E2, [E1, E2|_]).
consecutivos(E1, E2, [_|Cauda]) :consecutivos(E1, E2, Cauda).
Questões:
?- consecutivos(a, b, [d, e, f, g, a, b]).
yes
?- consecutivos(X, Y, [d, e, f, g]).
X=d
Y=e ;
X=e
Y=f;
X=f
Y=g;
no
49
 Inserção de um elemento na 1ª posição de uma lista,
modo(?,?,?) :
inserir(Elem, Lista, [Elem | Lista]).
Questão:
?- inserir(a, [b, c, d], L).
L = [a, b, c, d]
 Exclusão de um elemento de uma lista, modo(?,+,?) ou
modo(+,?,+) :
del(X,[X | Corpo],Corpo).
del(X,[Y | Corpo], [Y | Corpo1]):-del(X,Corpo,Corpo1).
Questão:
?- del(b,[a,b,c], L).
L = [a,c] ;
no
 Permutação de uma lista, modo(+,?) :
permuta([ ],[ ]).
permuta(L,[X | P]):-del(X,L,L1),permuta(L1,P).
Questão:
?- permuta([vermelho,azul,verde], L).
L = [vermelho,azul,verde] ;
L = [vermelho,verde,azul] ;
L = [azul,vermelho,verde] ;
L = [azul,verde,vermelho] ;
L = [verde,vermelho,azul] ;
L = [verde,azul,vermelho] ;
no
50
 Retirar todas as ocorrências de um elemento em uma
lista, modo(+,+,?) :
retirar_todas(_, [], []).
retirar_todas(Elem, [Elem|Cauda], L):retirar_todas(Elem, Cauda, L).
retirar_todas(Elem, [Elem1|Cauda1], [Elem1|Cauda1]) :Elem \== Elem1,
retirar_todas(Elem, Cauda, Cauda1).
Questões:
?- retirar_todas(a, [c,a, s, a], L).
L = [c, s] ;
no
 Retirar elementos repetidos de uma lista, modo(+,?) :
retirar_rep([], []).
retirar_rep([Elem|Cauda], [Elem|Cauda1]):retirar_todas(Elem, Cauda, Lista),
retirar_rep(Lista, Cauda1).
Questões:
?- retirar_rep([a, b, a, b, a, b, a, a, b, a], L).
L = [a, b] ;
no
retirar_rep([a, b, c, d, a, a, a], [a, b, c, d]).
yes
51
 Inserção do elememento em qualquer posição da lista,
modo(?,?,+) ou modo(+,+,?) :
Inserir_2(Elem, Lista, Lista1) :retirar_elemento(Elem, Lista1, Lista).
Questões: modo(+,+,?)
? – inserir_2(ana, [pedro, maria], L).
L = [ana, pedro, maria] ;
L = [ pedro, ana, maria] ;
L = [ pedro, maria, ana] ;
no
modo(?,?,+) :
? – inserir_2(X, Y, [1, 2, 3]).
X=1
Y = [2, 3] ;
X=2
Y = [1, 3] ;
X=3
Y = [1, 2] ;
no
 Substituir um elemento em uma lista por outro
elemento, modo(?,?,+,?) :
substitui(X, Y, [], []).
substitui(X, Y, [X|L], [Y|L1]) : - substitui(X, Y, L, L1).
substitui(X, Y, [Z|L], [Z|L1]) :- X \== Z,
substitui(X, Y, L, L1).
Questões:
? – substitui(2, 1000, [0, 4, 2, 2],L).
L = [0, 4, 1000, 1000] ;
no
52
 Verificação se uma lista é sublista de outra, modo(?,+) :
sublista(S, L) :-concatena(L1, L2, L),concatena(S, L3,
L2).
Questões:
?-sublista(S,[a,b,c]).
?- sublista([c,d,e], [a,b,c,d,e,f]).
S=[] ;
yes
S = [a] ;
S = [a,b] ;
?-sublista([c,e],[a,b,c,d,e,f]).
S = [a,b,c] ;
no
S = [b] ;
S = [b,c] ;
S = [c] ;
no
 Intersecção de duas listas em uma terceira, modo(+,?,?) :
intersec([X | Y],L,[X | Z]):-pertence(X, L),intersec(Y, L,
Z).
intersec([_ | X], L, Y):-intersec(X, L, Y).
intersec(_, _, [ ]).
Questão:
?-intersec([a,b,c,d],[aa,b,d],L).
L = [b,d] ;
 Deslocamento de uma lista para a esquerda, modo(+,?) :
desloca([Elem | Cauda], Lista):concatena(Cauda, [Elem], Lista).
Questão:
?- desloca([1, 2, 3, 4, 5], L).
L = [2, 3, 4, 5, 1]
53
 Seleção dos elementos diferentes da 1ª lista em relação a
2ª lista, armazenando-os em uma lista separada,
modo(+,+,?) :
diferente([ ],_,[ ]).
diferente([X | L1],L2,L):-pertence(X,L2),!,
diferente(L1,L2,L).
diferente([X | L1],L2,[X | L):-diferente(L1,L2,L).
Questão:
?-diferente([a,b,c,d],[b,d,e,f],L).
L = [a,c]
 Divisão de uma lista numérica em duas listas, uma
com números positivos outra com negativos, modo(+,?,?)
ou modo(?,+,+) :
divide([ ], [ ], [ ]).
divide([Elem | Cauda], [Elem | Positivos], Negativos):Elem >= 0, ! ,
divide(Cauda, Positivos, Negativos).
divide([Elem | Cauda], Positivos, [Elem | Negativos]):divide(Cauda, Positivos, Negativos).
Questão:
?- divide([1, 4, -1, 0, -2, 6], Pos, Neg).
Pos = [1, 4, 0, 6]
Neg = [-1, -2]
54
 Achatar uma lista, modo(+,?) :
achatar([], []).
achatar([Cab|Caud], ListaA) :eh_lista(Cab),
achatar(Cab, CabA),
achatar(Caud, CaudA),
concatenar(CabA, CaudA, ListaA).
achatar([Cab|Caud], [Cab,CaudA]) :- not lista(Cab),
achatar(Caud, CaudA).
Questões:
? – achatar([a, [b, [c, d]],[[e, f, g], h], i], L).
L = [a, b, c, d, e, f, g, h, i] ;
no
 Verificar se intersecção entre 2 conjuntos é não vazia,
modo(+,+) :
nao_vazia(L1, L2) :- pertence(Elem, L1),
pertence(Elem, L2).
 Verificar se 2 conjuntos são disjuntos, modo(+,+) :
conj_disjuntos(L1, L2) :- not nao_vazia(L1, L2).
Questões:
? – conj_disjuntos([a, b, c, d], [d, c, b, a]).
no
55
 Verificar se 2 conjuntos são iguais, modo(+,+) :
conj_iguais([], []).
conj_iguais([X|L1], L2) :- del(X, L2, L3),
conj_iguais(L1, L3).
Questões:
? – conj_iguais([a, b, c], [c, b, a]).
yes
 União de 2 conjuntos, modo(+,+,?) :
uniao(L1, L2, U) :- concatenar(L1, L2, L3),
retirar_rep(L3, U).
Questões:
? – uniao([a, b, c], [b, c, d], L).
L = [a, b, c, d] ;
no
56
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
57
Entrada e Saída
read(X)
Este predicado destina-se à leitura de termos do teclado.
Todo o termo escrito deve terminar com um ponto ( . ).
Este termo pode ser uma palavra isolada, uma lista de
letras ou ainda uma string de caracteres.
 Definição de uma regra para exemplificar o predicado
read:
oi:-read(X),write(‘Resposta: ’),write(X).
Questões:
?-oi.
ola.
Resposta: ola
yes
?-oi.
Ola.
Resposta: _00A0
yes
% variável de memória
?- oi.
‘Ola, como vai?’.
Resposta: Ola, como vai?
yes
?- oi.
“Ola, como vai?”.
Resposta:[79,108,97,44,32,
99,111,109,111,32,
118,97,105,63]
yes
%lista de caracteres ASCII
58
write(X)
Imprime termos associados a X. São válidas as mesmas
observações feitas para read.
 Definição de uma regra quadrado:
quadrado:-read(N),Result is N*N,write(Result).
Questão:
?-quadrado.
(4).
16
yes
 Definição de uma regra cubo:
cubo:-write(‘Próximo item, por favor: ’),
read(X),
calculocubo(X).
Calculocubo(stop):- !.
Calculocubo(N):-C is N * N * N,
write(‘Cubo de ’),write(N),write(‘ é ’),
write(C),nl,cubo.
Questão:
?-cubo.
Próximo item, por favor: 5.
Cubo de 5 é 125
Próximo item, por favor: 12.
Cubo de 12 é 1728
Próximo item, por favor: stop.
yes
59
tab(X)
Escreve uma quantidade X de caracteres “espaço” na
saída.
 Definição de uma regra para exemplificar o predicado
tab:
escrevetab:-tab(15),write(‘Soma de 2 Elementos’),nl,nl,
tab(1),write(‘Entre com o 1º elemento: ’),read(X),
tab(1),write(‘Entre com o 2º elemento: ’),read(Y),
tab(25),write(‘________’),nl,Total is X+Y,
tab(28),write(Total),nl,nl,confirma.
confirma:-tab(1),write(‘Deseja calcular novamente (s/n): ’),
read(Resp),
Resp = s , escrevetab, ! .
Questão:
?-escrevetab.
Soma de 2 Elementos
Entre com o 1º elemento: 123.
Entre com o 2º elemento: 456.
579
Deseja calcular novamente (s/n): n.
60
 Torre de Hanói:
hanoi(N):-move(N,a,b,c).
move(1,A,_,C):-informa(A,C),!.
move(N,A,B,C):N1 is N-1,
move(N1,A,C,B),
informa(A,C),
move(N1,B,A,C).
informa(Loc1, Loc2):-write( ‘Move um disco de ’) ,
write(Loc1),write(‘ para ’), write(Loc2),nl.
Questão:
?-hanoi(3).
Move um disco de a para c
Move um disco de a para b
Move um disco de c para b
Move um disco de a para c
Move um disco de b para a
Move um disco de b para c
Move um disco de a para c
yes
61
Criação e Escrita em Arquivo
?- fcreate(arq,'c:\saida.pl',2).
yes
?- output(arq).
yes
?- hanoi(3).
yes
?- fclose(arq).
yes
Arquivo saida.pl
Move o disco de a para c
Move o disco de a para b
Move o disco de c para b
Move o disco de a para c
Move o disco de b para a
Move o disco de b para c
Move o disco de a para c
Nota:
Caso o
arquivo
já exista, utilize
o
comando
fopen(arq,’c:\saida.pl’,2) no lugar de fcreate(arq,’saida.pl’,2).
62
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
63
Manipulando Base de Dados
 Definição de uma Base de Dados:
gosta(maria, cafe).
gosta(jose, cha).
gosta(ana, guarana).
gosta(pedro, vinho).
gosta(jose, coca).
gosta(maria, vinho).
bagof(X,P,L)
Recupera da Base de Dados. L é uma lista formada por
todo X que satisfaz a condição P.
Questões:
?-bagof(X,gosta(X,Y),L).
X = _00E4 , % variável de memória
Y = café ,
L = [maria] ;
X = _00E4 ,
Y = cha ,
L = [jose] ;
X = _00E4 ,
Y = coca ,
L = [jose] ;
64
X = _00E4 ,
Y = guarana ,
L = [ana] ;
X = _00E4 ,
Y = vinho ,
L = [pedro, maria] ;
no
?-bagof(X,Y^gosta(Y,X),L).
%Lista única
X = _00E4 ,
Y = _00F4 ,
L = [cafe, cha, guarana, vinho, coca, vinho]
setof(X,P,L)
Recupera da Base de Dados. L é uma lista ordenada, sem
repetição, formada por todo X que satisfaz a condição P.
Similar ao predicado bagof.
Questão:
?- setof(X, Y^gosta(Y, X), L).
X = _00E4 ,
Y = _00F4 ,
L = [cafe, cha, coca, guarana, vinho]
65
findall(X,P,L)
L é uma lista formada por todo X que satisfaz a condição
P. A diferença com o bagof é que todos os objetos X são
coletados mesmo que as variáveis em P não sejam parte de
X.
 Definição de uma Base de Dados:
pessoa(joao,itau,30).
pessoa(jose,nacional,35).
pessoa(maria,real,30).
Questões:
?- findall(Idade,pessoa(_,_,Idade),Lista).
Idade = _0084 ,
Lista = [30, 35, 30] %Lista com todas as idades
?- findall(Idade/Quem,pessoa(Quem,_,Idade),Lista).
Idade = _ ,
Quem = _ ,
Lista = [30 / joao,35 / jose,30 / maria]
?- findall(Idade,pessoa(Quem,_,Idade),Lista).
Idade = _ ,
Quem = _ ,
Lista = [30,35,30]
?-findall(Quem,pessoa(Quem,_,30),Lista).
Quem = _0084 ,
Lista = [joao,maria] %Lista de nomes com 30 anos
66
consult(X)
Realiza uma consulta a um determinado Banco de Dados .
Consult(X) carrega o conteúdo do Banco de Dados para a
memória. Uma vez carregado o Banco de Dados, os fatos e
regras nele contidos poderão ser utilizados.
Arquivo quad.pl
quadrado:read(A),
B is A * A,
write(B).
Questões:
?- consult(‘c:\quad.pl’).
yes
?- quadrado.
5.
25
yes
listing(X)
Permite a listagem de um determinado predicado que está
sendo utilizado.
Questão:
?- listing(quadrado).
quadrado:read(A),
B is A * A,
write(B).
yes
67
 Definição de uma Base de Dados:
rapido(ann).
lento(tom).
lento(pat).
assert
Adiciona cláusulas na Base de Dados.
Questões:
?- assert( ( maisrapido(X, Y):- rapido(X), lento(Y))).
X = _0084 ,
Y = _0098
?- maisrapido(A, B).
A = ann ,
B = tom ;
A = ann ,
B = pat
asserta e assertz
asserta(C) = Adiciona C no começo da Base de Dados.
assertz(C) = Adiciona C no fim da Base de Dados.
68
Questões:
?- assert( p(a) ), assertz( p(b) ), asserta( p(c) ).
yes
?- p(X).
X=c ;
X=a ;
X=b
retract
Remove dados e predicados da Base de Dados em memória.
Base de Dados antes da remoção:
rapido(ann).
lento(tom).
lento(pat).
Questões:
?- retract( lento(X) ).
X = tom ;
X = pat ;
no
?- maisrapido(A, B).
no
69
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
70
Outros Exemplos
Problema dos Missionários e Canibais
Na margem esquerda de um rio há 5 missionários e 5
canibais, que querem atravessá-lo para a outra margem .
Há um bote que pode transportar no máximo 3 pessoas ao
mesmo tempo. Os missionários não podem ficar em menor
número que os canibais em qualquer margem, caso
contrário serão devorados. Como fazer para que todos
cheguem a salvo na outra margem do rio?
Resolução:
Consideraremos a seguinte descrição para o conjunto de
estados possíveis utilizados para representar o problema
(Me, Ce, Bte)
onde,
Me = número de missionários na margem esquerda
Ce = número de canibais na margem esquerda
Bte = 1 se o bote está na margem esquerda, 0 na direita
Logo, o estado inicial é (5, 5, 1) e o final (0, 0, 0)
71
Representação do Espaço de Estados do Problema
(5,5,1)
(5,4,0)
(5,3,0)
(5,2,0)
(5,4,1)
(4,4,0)
(5,3,1)
(3,3,0)
(5,1,0)
(5,0,0)
(4,4,1)
(5,2,1)
(5,1,1)
(2,2,0)
(3,3,1)
(0,3,0)
(0,4,1)
(0,1,0)
(1,1,1)
(0,5,1)
(0,2,0)
(0,3,1)
(0,4,0)
(2,2,1)
(0,2,1)
(0,0,0)
72
O programa prolog que encontra a solução para este
problema usando busca em largura é mostrado abaixo.
largura([ ],_,_):- write('Solução não encontrada!'),nl.
largura([G|T],_,G):- write('Solução encontrada!'),nl.
largura([S|T],C,G):write('Listas a Percorrer: '),write([S|T]),nl,
write('Listas Percorridas: '), write(C),nl,
bagof(X,movelargura( S, T, C, X ),Lista),
append(T,Lista,O ),!,
largura(O, [S|C],G ).
largura([S|T],C,G):- largura(T,[S|C],G).
movelargura(S,T,C,X):- move(S,X),
X \== S,
not member(X,T),
not member(X,C).
% representação do espaço de estados
move([5,5,1],[5,2,0]).
move([5,5,1],[5,4,0]).
move([5,5,1],[4,4,0]).
move([5,5,1],[5,3,0]).
move([5,2,0],[5,3,1]).
move([5,2,0],[5,4,1]).
move([4,4,0],[5,4,1]).
move([0,1,0],[0,2,1]).
73
move([5,3,0],[5,4,1]).
move([5,3,1],[3,3,0]).
move([5,3,1],[5,0,0]).
move([5,3,1],[5,1,0]).
move([5,4,1],[3,3,0]).
move([5,4,1],[5,1,0]).
move([5,0,0],[5,1,1]).
move([5,1,0],[5,2,1]).
move([2,2,0],[3,3,1]).
move([0,3,0],[0,4,1]).
move([0,4,1],[0,2,0]).
move([0,5,1],[0,2,0]).
move([0,2,0],[2,2,1]).
move([0,1,0],[0,3,1]).
move([0,1,0],[1,1,1]).
move([0,3,1],[0,0,0]).
move([1,1,1],[0,0,0]).
move([0,2,1],[0,0,0]).
move([5,0,0],[5,2,1]).
move([3,3,0],[4,4,1]).
move([5,2,1],[2,2,0]).
move([3,3,1],[0,3,0]).
move([0,3,0],[0,5,1]).
move([0,4,1],[0,1,0]).
move([0,5,1],[0,4,0]).
move([0,2,0],[0,3,1]).
?- largura([[5,5,1]],[ ],[0,0,0]).
Neste caso partiu-se com o Estado Inicial, a Lista
dos Percorridos e o Estado Final.
74
Organização de uma Lista
Bubblesort
bubblesort(List,Sorted):-swap(List,List1),!,
bubblesort(List1,Sorted).
bubblesort(Sorted,Sorted).
swap([X,Y|Rest],[Y,X|Rest]):-gt(X,Y).
swap([Z|Rest],[Z|Rest1]):-swap(Rest,Rest1).
gt(X,Y):-X>Y.
Questão:
?- bubblesort([9,5,3,8],L).
L = [3,5,8,9]
Quicksort
quicksort([],[]).
quicksort([X|Tail],Sorted):-split(X,Tail,Small,Big),
quicksort(Small,Sortedsmall),quicksort(Big,Sortedbig),
conc(Sortedsmall,[X|Sortedbig],Sorted).
75
split(X,[],[],[]).
split(X,[Y|Tail],[Y|Small],Big):-gt(X,Y),!,
split(X,Tail,Small,Big).
split(X,[Y|Tail],Small,[Y|Big]):-split(X,Tail,Small,Big).
conc([],L,L).
conc([X|L1],L2,[X|L3]):-conc(L1,L2,L3).
gt(X,Y):-X>Y.
Questão:
?- quicksort([5,8,0,2,7],L).
L = [0,2,5,7,8] ;
no
Permutation Sort
psort(Xs,Ys) :- permutation(Xs,Ys), ordenado(Ys).
permutation(Xs,[Z|Zs]) :- select(Z,Xs,Ys),
permutation(Ys,Zs).
permutation([],[]).
ordenado([]).
ordenado([X]).
ordenado([X,Y|Ys]) :- X <= Y, ordenado([Y|Ys]).
Questão:
?- psort([3,4,2,1],Y).
Y = [1,2,3,4]
76
Insertion Sort
isort([X|Xs],Ys) :- isort(Xs,Zs), insert(X,Zs,Ys).
isort([],[]).
insert(X,[],[X]).
insert(X,[Y|Ys],[Y|Zs]) :- X > Y, insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]) :- X <= Y.
Questão:
?- isort([3,2,1],A).
A = [1,2,3]
Investigando um Crime
 Definição de uma base de dados:
possivel_suspeito(fred).
possivel_suspeito(mary).
possivel_suspeito(jane).
possivel_suspeito(george).
crime(roubo,john,terca,parque).
crime(roubo,robin,quinta,bar).
crime(assalto,jim,quarta,bar).
estava(fred,terca,parque).
inveja(fred,john).
77
principal_suspeito(Pessoa,Crime):crime(Crime,Vitima,Dia,Lugar),
possivel_suspeito(Pessoa),
estava(Pessoa,Dia,Lugar),
tem_motivo_contra(Pessoa,Vitima).
principal_suspeito(desconhecido,Crime).
tem_motivo_contra(Pessoa,Vitima):inveja(Pessoa,Vitima).
Questões:
?- principal_suspeito(Quem,roubo).
Quem = fred ;
Quem = desconhecido
?- crime(Crime,Vitima,Dia,bar).
Crime = roubo ,
Vitima = robin ,
Dia = quinta ;
Crime = assalto ,
Vitima = jim ,
Dia = quarta ;
78
Calculando o M.D.C. de uma Lista de Números
Uma das formas de calcularmos o m.d.c de dois números
é fatorarmos os dois e selecionarmos os fatores primos com
os menores expoentes em cada um deles, por exemplo:
18 = 2^1 * 3^2
12 = 2^2 * 3^1
mdc(12, 18) = 2^1 * 3^1 = 6
Outra forma de calcularmos o m.d.c. de dois números é
seguindo a seguinte regra:
1) Se a divisão do maior número pelo menor for exata então
o mdc é igual ao menor número.
2) Senão o processo é repetido usando o menor número e o
resto da divisão do maior pelo menor.
Ex:
mdc(18, 12)
18 | 12
01
--06
mdc(12, 06)

12 | 06
12 02
--00

mdc(18, 12) = 6
79
Nosso programa PROLOG utiliza o segundo método com
a diferença que o estendemos para uma lista de números e
não apenas para dois números:
mdc([A|[]], A) :- !.
mdc([A|Calda], N) :- mdc(Calda, B), mdc2(A, B, N), !.
mdc2(A, B, B) :- X is A mod B, X is 0, !.
mdc2(A, B, N) :- X is A mod B, mdc2(B, X, N).
O predicado mdc possui duas clausulas, a primeira existe
para determinarmos qual o mdc de uma lista com apenas
um elemento, e a segunda clausula determina o mdc de uma
lista com dois ou mais elementos, calculando recursivamente
o mdc da calda desta lista e em seguida o mdc da cabeca da
lista com o mdc da calda da lista já calculado.
As clausulas do predicado mdc2 aplicam os passos 1 e 2 do
segundo método mostrado acima.
Abaixo mostramos alguns exemplos de execução do
programa:
?- mdc([18,30,12,60], R).
R=6
?- mdc([18,30,10,60], R).
R=2
?- mdc([15,6,12,9], R).
R=3
?- mdc([15,30,20,12], R).
R=1
?- mdc([16,8,32,64], R).
R=8
80
O Problema das Damas no Tabuleiro de Xadrez
O enunciado do problema é o seguinte: “Em um tabuleiro
de xadrez, ou de um modo mais geral um tabuleiro de N*N
casas, queremos posicionar N damas de modo que nenhuma
das damas ataca qualquer outra”.
A resolução do problema está diretamente relacionada à
movimentação exercida pela dama; No jogo de xadrez a
dama caminha nas verticais, horizontais e diagonais, deste
modo já eliminamos a possibilidade de haver duas ou mais
damas numa mesma coluna ou numa mesma linha, restando
apenas verificar se todas elas não se atacam nas diagonais.
Podemos mapear o problema da seguinte maneira: Para
um tabuleiro de N linhas por N colunas colocamos uma dama
em cada coluna, cada uma em uma linha diferente da outra e
então começamos a permutar cada dama de uma certa
coluna com cada outra dama de outra coluna, desta forma
realizaremos N! permutações, entre estas permutações
eventualmente encontraremos situações onde nenhuma dama
ataca nenhuma outra, esta situação representa uma solução.
A figura abaixo representa uma das 82 soluções encontrada
pelo programa PROLOG para um tabuleiro de 8*8 com 8
damas:
?- damas(8,R).
R = [1,5,8,6,3,7,2,4]
81
Na figura contamos as linhas de baixo para cima, por
exemplo o número 5 da resposta corresponde a dama da
segunda coluna colocada na quinta linha. A baixo mostramos
o código em PROLOG.
damas(NumDamas,Solucao) :- intervalo(1,NumDamas,Lista),
permuta(Lista,Solucao), seguro(Solucao).
intervalo(A,A,[A]).
intervalo(A,B,[A|Calda]) :- A < B, Proximo is A+1,
intervalo(Proximo,B,Calda).
permuta([],[]).
permuta(Lista,[Elemento|Calda]) :retira(Elemento,Lista,NovaLista),
permuta(NovaLista,Calda).
retira(X,[X|Calda],Calda).
retira(X,[Y|Calda],[Y|NovaCalda]) :- retira(X,Calda,NovaCalda).
seguro([]).
seguro([Cabeca|Calda]) :- seguro(Calda),
not ataca(Cabeca,Calda).
ataca(Cabeca,Calda) :- ataca(Cabeca,1,Calda).
ataca(X,Distancia,[Y|Calda]) :- X is Y+Distancia; X is Y-Distancia.
ataca(X,Distancia,[Y|Calda]) :- N1 is Distancia+1,
ataca(X,N1,Calda).
O predicado damas é composto de dois argumentos
NumDamas (número de damas) e Solucao (lista que contém
a solução), e dos predicados intervalo (que cria uma lista do
tipo [1, 2 ,3 , 4 ,5 ,6 ,7 ,8]), permuta (que realiza todas as
permutações na lista que criamos) e seguro (que testa se uma
dada situação gerada a partir de uma permutação é uma
situação aceitável, ou seja nenhuma dama ataca nenhuma
outra).
82
Calculando Números Primos
Os números primos são aqueles divisíveis por si e pelo
número um, desta forma poderíamos determinar se um
número é primo dividindo-o por todos os números anteriores
a ele e contando quantos números conseguiram dividi-lo sem
deixar resto. Este processo seria muito demorado,
principalmente se desejássemos calcular uma lista de
números primos. Podemos resolver este problema de uma
maneira diferente:
1) Criamos uma lista de números consecutivos que começa
em 2 e vai até o maior número do intervalo no qual
queremos encontrar os números primos.
2) Pegamos o primeiro número da lista e cortamos todos os
seus múltiplos.
3) Repetimos o processo para cada novo elemento na lista.
No final do processo a lista restante contém apenas
elementos que não possuem divisores diferente do número 1,
ou seja, apenas números primos. A figura seguir ilustra o
processo para os números de 2 a 100.
83
O código PROLOG é mostrado a seguir:
primos(Limite, Primos) :- geraLista(2, Limite, Lista),
geraPrimos(Lista, Primos).
geraLista(Menor, Maior, [Menor|Lista]) :- Menor =< Maior, N is
Menor+1, geraLista(N, Maior, Lista), !.
geraLista(_, _, []).
geraPrimos([], []) :- !.
geraPrimos([Primo|Lista], [Primo|MaisPrimos]) :removeMultiplos(Primo, Lista, NovaLista),
geraPrimos(NovaLista, MaisPrimos).
removeMultiplos(Num, [], []) :- !.
removeMultiplos(Num, [Cabeca|Lista], [Cabeca|NovaLista]) :not(0 is Cabeca mod Num),
removeMultiplos(Num, Lista, NovaLista), !.
removeMultiplos(Num, [Cabeca|Lista], NovaLista) :0 is Cabeca mod Num,
removeMultiplos(Num, Lista, NovaLista).
O predicado removeMultiplos gera uma lista que possui
apenas números que não são múltiplos de um certo número
dado. O predicado geraLista constrói uma lista com todos os
números entre um número menor e um maior. O predicado
geraPrimos pega o primeiro número de uma lista e arranca
todos os múltiplos deste elemento, então pega a esta nova lista
e repete o processo. O predicado primos gera uma lista
inicialmente com todos os números num intervalo dado e
após isto chama o predicado geraPrimos. A seguir mostramos
uma execução:
?- primo(100,L).
L = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
79,83,89,97]
84
Encontrando o Menor Caminho Entre Duas Cidades
Quando desejamos encontrar o menor caminho entre duas
cidades devemos primeiramente conhecer todos os caminhos
que nos levam da cidade origem até a cidade destino, para isso
devemos montar um grafo onde os nós são as cidades e os
arcos são as distâncias entre uma cidade e outra. O grafo
abaixo representa um exemplo:
Nosso programa PROLOG deve encontrar todos os caminhos
possíveis entre a cidade origem e a cidade destino e escolher
aquele cuja a soma das distâncias correspondesnte às viagens
de uma cidade para outra é a menor. O programa é o seguinte:
distancia(a, d, 200). distancia(a, e, 500).
distancia(b, e, 100). distancia(b, f, 100).
distancia(d, e, 100). distancia(e, g, 300).
distancia(f, i, 100). distancia(g, h, 300).
vizinho(X, Y, Dist) :- distancia(X, Y, Dist).
vizinho(X, Y, Dist) :- distancia(Y, X, Dist).
pertence(X, [X|_]).
pertence(X, [_|L]) :- pertence(X,L).
distancia(b, c, 100).
distancia(c, f, 100).
distancia(e, i, 400).
distancia(h, i, 200).
85
caminho(Origem, Origem, _, [], 0).
caminho(Origem, Destino, CidadesVisitadas,
[Intermediario|Caminho], Distancia) :vizinho(Origem, Intermediario, Dist1),
not(pertence(Intermediario, CidadesVisitadas)),
caminho(Intermediario, Destino,
[Intermediario|CidadesVisitadas], Caminho, Dist2),
Distancia is Dist1 + Dist2.
primeiro([[Caminho,Distancia]|Lista], Caminho, Distancia).
resolve(Origem, Destino, [Origem|Caminho], Distancia) :bagof([Camin,Dist], caminho(Origem, Destino, [Origem],
Camin, Dist), Lista),
sort(Lista,ListaOrdenada,[2]),
primeiro(ListaOrdenada, Caminho, Distancia).
O predicado distancia determina as distâncias entre as
cidades, o predicado vizinho determina que se uma cidade dista
x de outra então esta segunda dista x da primeira, o predicado
pertence determina se uma elemento já pertence a uma lista ou
não (no nosso caso se uma cidade já pertence a uma lista de
cidades), o predicado caminho encontra o caminho de uma
cidade até outra bem como a distância total do percurso, o
predicado primeiro pega o primeiro elemento de uma lista e o
predicado resolve é o responsável por pegar todos os caminhos
encontrados e escolher o de menor distância. A seguir
mostramos um exemplo para o grafo anterior:
?- resolve(a, h, Caminho, Distancia).
Caminho = [a,d,e,b,f,i,h] ,
Distancia = 800
86
Busca em Largura em Árvore Binária
Freqüentemente necessitamos realizar buscas em árvores
para solucionar problemas, como por exemplo quando
queremos verificar todos os estados de um jogo de dama
para chegar a uma posição vitoriosa. O backtracking de
PROLOG nos permite realizar buscas em profundidade com
certa facilidade, no entanto, para alguns problemas
necessitamos realizar buscas em largura, o que não é uma
tarefa tão simples. A busca é feita da seguinte forma:
1) Coloca-se o nó raiz em uma lista
2) Expande-se (gera-se todos os seus filhos) o primeiro
elemento da lista e coloca-se o resultado no final da lista
3) Repete-se o processo para o segundo da lista, terceiro da
lista, etc..., até que não haja mais elementos para expandir.
No final teremos uma lista de nós cuja ordem é a ordem
da busca em largura. A figura abaixo mostra uma árvore
exemplo e os passos do processo descrito acima.
87
O código PROLOG é mostrado a seguir:
buscaLargura([], []).
buscaLargura([tree(No, Esq, Dir)|Calda], [No|Resultado]) :bagof(X, filho(tree(No, Esq, Dir), X), Lista),
append(Calda, Lista, NovaLista),
buscaLargura(NovaLista, Resultado), !.
buscaLargura([tree(No, Esq, Dir)|Calda], [No|Resultado]) :buscaLargura(Calda, Resultado), !.
filho(tree(No, Esq, Dir), Esq) :- Esq \== null.
filho(tree(No, Esq, Dir), Dir) :- Dir \== null.
O predicado buscaLargura realiza o processo de expandir o
primeiro nó da lista, criar uma nova lista que contém também
os nós expandidos e repetir o processo para cada nó sucessivo
da lista. O predicado filho é usado para retornar cada filho de
um certo nó. A seguir mostramos a execução:
?- buscaLargura( [tree(3, tree(1, null, tree(2, null, null)), tree(7,
tree(5, tree(4, null, null), tree(6, null, null)), tree(8, null, null)))],R).
R = [3,1,7,2,5,8,4,6]
88
Verificação de Árvores AVL
Neste exemplo mostraremos como verificar se uma dada
árvore é uma árvore AVL. Árvores AVL são árvores binárias
de busca que possuem altura mínima, ou seja, em uma árvore
de N nós a distância máxima da raiz a qualquer folha é no
máximo log(N). Árvores de altura mínima são chamadas
árvores balanceadas.
Portanto devemos verificar duas condições:
1)A árvore binária deve ser uma árvore de busca.
2)A árvore binária deve estar balanceada.
Dizemos que uma árvore binária é de busca se todos os
elementos da subárvore esquerda de qualquer nó são
menores que este nó e todos os elementos da subárvore direita
de qualquer nó são maiores que este nó.
Dizemos que uma árvore é balanceada se a diferença de
altura da subárvore esquerda para a subárvore direita não
exceder em módulo a unidade.
Desta forma o teste de árvores AVL fica como mostrado a
seguir:
ehAVL(Arvore) :- arvoreBusca(Arvore), balanceada(Arvore).
arvoreBusca(null).
arvoreBusca(tree(Raiz, ArvoreEsq, ArvoreDir)) :- maior(Raiz,
ArvoreEsq), menor(Raiz, ArvoreDir).
maior(_, null).
maior(Maior, tree(Raiz, ArvoreEsq, ArvoreDir)) :- Maior > Raiz,
maior(Raiz, ArvoreEsq), menor(Raiz, ArvoreDir),
maior(Maior, ArvoreDir).
89
menor(_, null).
menor(Maior, tree(Raiz, ArvoreEsq, ArvoreDir)) :Maior < Raiz, maior(Raiz, ArvoreEsq),
menor(Raiz, ArvoreDir), menor(Maior, ArvoreEsq).
balanceada(null).
balanceada(tree(_, ArvoreEsq, ArvoreDir)) :balanceada(ArvoreEsq), balanceada(ArvoreDir),
altura(ArvoreEsq, HE), altura(ArvoreDir, HD),
DIF is HE - HD, abs(DIF) =< 1.
altura(null, 0).
altura(tree(_, ArvoreEsq, ArvoreDir), Altura) :altura(ArvoreEsq, HE), altura(ArvoreDir, HD),
Altura is max(HE, HD) + 1.
Na chamada ao predicado ehAVL devemos passar uma
estrutura de árvore como a mostrada nos exemplos a seguir:
?- ehAVL(tree(3, tree(1, null, tree(2, null, null)), tree(7, tree(5,
tree(4, null, null), tree(6, null, null)), tree(8, null, null)))).
yes
?- ehAVL(tree(3, tree(1, null, tree(2, null, null)), tree(7, tree(5,
tree(0, null, null), tree(6, null, null)), tree(8, null, null)))).
no
?- ehAVL(tree(3, tree(1, null, tree(2, null, null)), tree(7, tree(5,
tree(4, null, null), tree(6, null, null)), null))).
no
90
Reconhecendo Cadeias de Símbolos Através de MEFs
Máquinas de Estados Finita (MEF) podem ser
representadas de modo simplificado por um conjunto de
estados e um conjunto de transições de estados, além dos
estados finais e do estado inicial. Freqüentemente desejamos
verificar se uma certa cadeia de símbolos pertence a
linguagem determinada por uma MEF, para isso devemos
aplicar uma seqüência de transições correspondentes aos
símbolos dessa seqüência que nos levarão de um estado inicial
a um estado final. Caso o estado final pertença ao conjunto de
estados finais dizemos que a seqüência de entrada pertence a
linguagem determinada pela MEF.
Existem ainda MEFs que possuem transições de um
determinado estado para mais de um estado, estas MEFs são
chamadas MEF indeterminísticas (MEF_ind), diferentemente
da primeira conhecida como MEF determinística (MEF_det).
Quando trabalhamos com MEFs_ind devemos ser capazes de
determinar qual o conjunto de estados resultante da
aplicação de uma transição sobre vários estados da MEF e
não apenas um único estado resultante da aplicação de uma
única transição sobre um único estado. O programa que
implementamos em PROLOG aceita MEFs_ind embora o
exemplo escolhido represente uma MEF_det.
terminal(q8).
transicao(q0, a, q3).
transicao(q1, b, q2).
transicao(q3, b, q4).
transicao(q5, a, q8).
transicao(q7, a, q4).
transicao(q0, b, q1).
transicao(q2, a, q5).
transicao(q4, a, q7).
transicao(q6, a, q3).
transicao(q7, b, q8).
transicao(q1, a, q4).
transicao(q3, a, q6).
transicao(q4, b, q5).
transicao(q6, b, q7).
transicao(q8, a, q5).
91
verifica(Estados, Entradas, []) :- aplicaTransicoes(Estados,
Entradas, []), write('Nao ha transicao prevista, a MEF para: '), !.
verifica(Estados, Entradas, Resposta) :aplicaTransicoes(Estados, Entradas, Resposta),
temTerminal(Resposta), write('Sequencia valida: '), !.
verifica(Estados, Entradas, Resposta) :aplicaTransicoes(Estados, Entradas, Resposta),
write('Sequencia invalida: '), !.
aplicaTransicoes([], Entradas, []) :- !.
aplicaTransicoes([Estado|[]], [], [Estado]) :- !.
aplicaTransicoes([Estado|[]], [Entrada|Sequencia],
EstadosFinais) :- transicoes(Estado, Entrada, ListaEstados),
aplicaTransicoes(ListaEstados, Sequencia, EstadosFinais), !.
aplicaTransicoes([Estado|MaisEstados], Entradas,
EstadosFinais) :- aplicaTransicoes([Estado], Entradas, ListaA),
aplicaTransicoes(MaisEstados, Entradas, ListaB),
uniao(ListaA, ListaB, EstadosFinais).
temTerminal([Estado|_]) :- terminal(Estado), !.
temTerminal([_|Estados]) :- temTerminal(Estados).
transicoes(Estado, Entrada, ListaEstados) :bagof(NovoEstado, transicao(Estado, Entrada,
NovoEstado), ListaEstados), !.
transicoes(Estado, Entrada, []).
uniao([], [], []) :- !.
uniao([], Lista, NovaLista) :- tiraRepetidos(Lista, NovaLista), !.
uniao(Lista, [], NovaLista) :- tiraRepetidos(Lista, NovaLista), !.
uniao([Elem|ListaA], ListaB, NovaLista) :- pertence(Elem, ListaB),
uniao(ListaA, ListaB, NovaLista), !.
uniao([Elem|ListaA], ListaB, NovaLista) :- pertence(Elem, ListaA),
uniao(ListaA, ListaB, NovaLista), !.
uniao([Elem|ListaA], ListaB, [Elem|NovaLista]) :- uniao(ListaA,
ListaB, NovaLista).
tiraRepetidos([], []) :- !.
92
tiraRepetidos([Elem|[]], [Elem]) :- !.
tiraRepetidos([Elem|Calda], Saida) :- pertence(Elem, Calda),
tiraRepetidos(Calda, Saida), !.
tiraRepetidos([Elem|Calda], [Elem|Saida]) :tiraRepetidos(Calda, Saida).
pertence(Elem, [Elem|_]) :- !.
pertence(Elem, [_|Lista]) :- pertence(Elem, Lista).
Os fatos terminal e transicao determinam a estrutura da
MEF (estados, transições e estado final). O predicado verifica
possui três argumentos: uma lista de estados, uma lista
representando a seqüência de símbolos de entrada e uma lista
de estados finais da MEF correspondente às transições
realizadas após a verificação. No processo de verificação
devemos aplicar transições correspondentes aos símbolos de
entrada, esta tarefa é realizada pelo predicado
aplicaTransicoes, neste predicado encontramos um conjunto
de estados resultantes das transições correspondentes a uma
determinada entrada e repetimos este processo até que se
esgotem os símbolos de entrada. No final do processo de
aplicação de transições teremos duas listas com estados finais
da MEF (uma gerada a partir do primeiro estado da lista de
estados e outra gerada a partir dos estados restantes).
Devemos agora unir estas duas listas em uma (tarefa realizada
pelo predicado uniao) retirando as possíveis repetições de
estados através do predicado tiraRepetidos. Por fim
determinamos se o conjunto de estados finais possui ao menos
um elemento terminal, esta tarefa é realizada pelo predicado
temTerminal. A estrutura da MEF é mostrada na figura
abaixo e aceita as cadeias de ‘a’s e ‘b’s que possuem número
par de ‘a’s (2, 4, ..) e exatamente 2 ‘b’s em qualquer ordem.
93
Representação gráfica da MEF
Algumas possíveis execuções seriam:
?- verifica([q0], [a,b,a,a,b,a,a,a], R).
Sequencia valida: R = [q8]
?- verifica([q0], [b,a,a,b,b,a,a], R).
Nao ha transicao prevista, a MEF para: R = []
?- verifica([q0], [a,b,a,a], R).
Sequencia invalida: R = [q4]
Poderiamos ainda iniciar a MEF a partir de mais de um
estado como por exemplo q0 e q4, isso acarretaria no
reconhecimento de seqüências com um único ‘b’ e um número
impar de ‘a’s (1, 3, ...) além das seqüências reconhecidas
anteriormente a partir de q0.
?- verifica([q0,q4], [a,b,a,a], R).
Sequencia valida: R = [q4,q8]
?- verifica([q0,q4], [a,b,b,a,a], R).
Sequencia invalida: R = [q5]
?- verifica([q0,q4], [a,a,b,b,a,a], R).
Sequencia valida: R = [q8]
94
O Problema das Jarras D’água
O problema das jarras d’água tradicional consiste de duas
jarras de capacidades 3 e 5 litros (inicialmente vazias) e uma
fonte d’água para encher as jarras. O objetivo do problema é
deixar 4 litros na jarra de capacidade 5 litros, para isso
podemos realizar as seguintes ações: encher uma jarra,
esvaziar uma jarra ou despejar o conteúdo de uma jarra na
outra. Poderíamos representar a seqüência de transições que
nos conduzem à resposta representando os estados das jarras
(através de pares) entre cada ação tomada. A solução seria a
seguinte: (0,0), (0,5), (3,2), (0,2), (2,0), (2,5), (3,4).
Outra maneira de representarmos a solução seria
reportando a seqüência de passos a serem tomados: encher a
2o. jarra, virar a 2o. jarra na 1o., esvaziar a 1o. jarra, virar a
2o. jarra na 1o., encher a 2o. jarra, virar a 2o. jarra na
primeira.
Esquema das transições que levam o estado inicial a um estado final
95
O problema que mostramos a seguir estende o problema
tradicional das jarras d’água para qualquer número de
jarras, com qualquer configuração inicial, qualquer
capacidade e qualquer configuração final da jarras. Além
disso impomos um limite de transições para alcançarmos o
estado final, isto significa que eventualmente podemos não
encontrar uma solução, não porque esta solução não existe,
mas sim porque ela necessita de mais transições do que o
limite que colocamos.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is CapacA, NovoB is JarraB, JarraA\=CapacA.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is 0, NovoB is JarraB, JarraA\=0.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is 0, NovoB is JarraA+JarraB,
NovoB<CapacB, JarraA\=0.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is JarraA-(CapacB-JarraB), NovoB is CapacB,
CapacB-JarraB=<JarraA, JarraB\=CapacB.
altera([Cabeca|Calda], 0, Valor, [Valor|Calda]).
altera([Cabeca|Calda], Posicao, Valor, [Cabeca|NovaCalda]) :NovaPosicao is Posicao-1,
altera(Calda, NovaPosicao, Valor, NovaCalda).
pegaItem([Cabeca|Calda], Cabeca, 0).
pegaItem([_|Calda], Elemento, NovoContador) :pegaItem(Calda, Elemento, Contador),
NovoContador is Contador+1.
pegaJarra(Configuracao, Jarra, Posicao) :pegaItem(Configuracao, Jarra, Posicao).
pegaCapacidade(Capacidades, Capac, Posicao) :pegaItem(Capacidades, Capac, Posicao).
pertence(X, [X|_]) :- !.
pertence(X, [_|Z]) :- pertence(X, Z).
96
transicao(ConfFinal, ConfFinal, Capacidades, Lista, Contador)
:- reverse(Lista, NovaLista), write(NovaLista), !.
transicao(ConfInicial, ConfFinal, Capacidades, Lista,
Contador) :- Contador>0, NovoContador is Contador-1,
pegaJarra(ConfInicial, JarraA, PosicaoA),
pegaCapacidade(Capacidades, CapacA, PosicaoA),
pegaJarra(ConfInicial, JarraB, PosicaoB),
pegaCapacidade(Capacidades, CapacB, PosicaoB),
PosicaoA\=PosicaoB,
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB),
altera(ConfInicial, PosicaoA, NovoA, ConfTemp),
altera(ConfTemp, PosicaoB, NovoB, NovaConf),
not(pertence(NovaConf, Lista)),
transicao(NovaConf, ConfFinal, Capacidades,
[NovaConf|Lista], NovoContador), !.
resolve(Inicial, Final, Capacidade, Contador) :caminho(Inicial, Final, Capacidade, [Inicial], Contador).
Os predicados move representam as transições que
podemos realizar entre duas jarras: encher, esvaziar e virar
uma em outra (virando até encher ou virando todo o
conteúdo). O predicado altera recebe uma lista, uma posição
e um valor e retorna uma nova lista igual, exceto na posição
recebida, onde o valor será alterado para o valor recebido. O
predicado pegaItem recebe uma lista e devolve um valor e sua
posição correspondente na lista, caso a posição já esteja
definida pegaItem retorna apenas o valor associado à
posição. Os predicados pegaJarra e pegaCapacidade apesar de
possuírem nomes diferentes realizam a mesma tarefa,
selecionam um valor e uma posição em uma lista dada.
97
O predicado transicao é o coração do algoritmo, no
primeiro predicado representamos um estado solução, ou seja,
a configuração atual do problema é igual a configuração final
do problema. Neste caso mostramos na tela a seqüência de
estados que representam a solução. No segundo predicado,
primeiramente testamos e decrementamos um contador para
que possamos garantir que não iremos procurar soluções que
possuam mais que um determinado número de transições,
após isso selecionamos duas jarras (na verdade todas as
combinações de duas jarras) e suas respectivas capacidades,
então conferimos se não pegamos duas vezes a mesma jarra.
Caso não tenhamos pego, criamos uma nova lista parecida
com a lista que possui a configuração atual, mas com os
conteúdos das duas jarras alterados, após isso verificamos se a
nova configuração que construímos não é um estado que já
faz parte de nossa lista de transições. Caso afirmativo,
continuamos o processo procurando agora chegar à
configuração final à partir do novo estado que geramos (com
a possibilidade de realizarmos uma transição a menos e com
um estado a mais na lista de estados que constituem o
caminho solução). O predicado resolve recebe uma lista que
representa a configuração inicial das jarras, uma lista que
representa o estado final, uma lista que representa a
capacidade das jarras e o número máximo de transições que
desejamos realizar. A seguir mostramos algumas execuções.
?- resolve( [0,1,2], [2,2,4], [2,3,5], 4 ).
[ [0,1,2], [1,0,2], [1,2,0], [1,2,5], [2,2,4] ] yes
?- resolve( [3,4], [1,0], [5,7], 4 ).
no
98
Note que no último exemplo não conseguimos encontrar
uma solução com 4 transições ou menos. No entanto, se
estipularmos 5 transições o problema já passa a ser solúvel.
?- resolve( [3,4], [1,0], [5,7], 5 ).
[ [3,4], [3,0], [0,3], [5,3], [1,7], [1,0] ] yes
Outro aspecto importante do problema é que podemos
omitir partes do estado solução quando não estamos
interessados em alguma jarra em específico:
?- resolve( [0,1], [3,2], [6,4], 10 ).
no
?- resolve( [0,1], [3,_], [6,4], 5 ).
[ [0,1], [6,1], [3,4] ] yes
Também podemos estabelecer relações de igualdade entre
os conteúdos finais das jarras:
?- resolve( [1,1,3,2], [X,2,X,1], [2,4,5,3], 3 ).
[ [1,1,3,2], [0,2,3,2], [0,2,2,3], [2,2,2,1] ] X = 2
99
O Problema da Coloração de Mapas
Quando estamos colorindo um mapa queremos que cada
país, ou estado, possua uma cor diferente de qualquer um de
seus vizinhos para que possa ser bem delimitado.
Matematicamente está provado que em um plano não
podemos interconectar totalmente mais que 4 elementos, ou
seja, teremos no máximo 4 países que fazem fronteira um com
o outro sem possibilidade de repetirmos cores. Se inserirmos
um quinto país, onde quer que seja, haverá sempre uma cor
que já usamos e assim poderemos repeti-la. Desta forma nosso
programa de coloração de mapas necessita apenas 4 cores.
Uma das diversas resoluções é a que se segue:
1) Definimos os países e as fronteiras entre eles.
2) Escolhemos um país e damos uma cor a ele
temporariamente.
3) Preenchemos os seus vizinhos com as cores restantes,
também temporariamente.
4) Pegamos outro país e repetimos o processo.
5) Caso não seja possível distribuir as cores para o país e
seus vizinhos, voltamos no Backtracking de PROLOG e
escolhemos outras combinações de cores.
OBS: Como sempre pintamos um país com uma cor e os
vizinhos com as restantes, sempre que conseguirmos pintar o
último país teremos certeza que ele não tem a mesma cor que
nenhum de seus vizinhos, e portanto todos ou outros países já
estão pintados corretamente. O código PROLOG é o seguinte:
cores([vermelho, amarelo, azul, verde]).
100
mapa([ fronteira(paisA, A, [B, C, D, F]),
fronteira(paisB, B, [A, C, D, E, F]),
fronteira(paisC, C, [A, B, D]),
fronteira(paisD, D, [A, B, C, E, F]),
fronteira(paisE, E, [B, D, F]),
fronteira(paisF, F, [A, B, D, E]) ] ).
pintaMapa(Solucao) :- mapa(Solucao), coloreMapa(Solucao).
coloreMapa([Pais|PaisesRestantes]) :- coloreRegiao(Pais),
coloreMapa(PaisesRestantes).
coloreMapa([]).
coloreRegiao(fronteira(Pais, Cor, Vizinhos)) :- cores(Cores),
seleciona(Cor, Cores, CoresRestantes),
preenche(Vizinhos, CoresRestantes).
seleciona(Elem, [Elem|Calda], Calda).
seleciona(Elem, [ElemDifer|Calda], [ElemDifer|NovaLista]) :seleciona(Elem, Calda, NovaLista).
preenche([Elem|Calda], Lista) :- member(Elem, Lista),
preenche(Calda, Lista).
preenche([], Lista).
O predicado mapa possui informações sobre os nomes dos
países, suas cores e as cores de seus vizinhos, servindo com
uma base de dados de países. Note que a cor de cada país bem
como a cor de seus vizinhos são representadas por variáveis
(letras maiúsculas), isto é, não estão instanciadas e portanto
poderão assumir diversos valores durante a execução do
programa. O predicado pintaMapa lê este mapa que definimos
e o colore. O predicado coloreMapa pega o primeiro país e
atribui uma cor a ele e aos seus vizinhos, após isso repete o
processo aos países restantes. O predicado coloreRegiao
seleciona uma cor para um país e utiliza as cores restantes
para preencher os países restantes.
101
O predicado seleciona pega uma cor entre as 4 cores e
retorna uma lista com as cores restantes, e o predicado
preenche atribui cores aos países não permitindo que um país
possua uma cor diferente das cores passadas no segundo
argumento deste predicado. A saída do programa contém os
nomes dos países, suas respectivas cores e a listas de cores
correspondentes aos países vizinhos. Note que para cada saída
do programa a cor do país nunca pertence a sua lista de cores
de países vizinhos.
A seguir mostramos 3 dos 24 modos diferentes de colorir o
mapa do nosso exemplo, e um mapa ilustrativo para cada caso.
?- pintaMapa(R).
R = [ regiao(paisA, vermelho, [amarelo, azul, verde, azul]),
regiao(paisB, amarelo, [vermelho, azul, verde, vermelho, azul]),
regiao(paisC, azul, [vermelho, amarelo, verde]),
regiao(paisD, verde, [vermelho, amarelo, azul, vermelho, azul]),
regiao(paisE, vermelho, [amarelo, verde, azul]),
regiao(paisF, azul, [vermelho, amarelo, verde, vermelho]) ] ;
R = [ regiao(paisA, amarelo, [azul, verde, vermelho, verde]),
regiao(paisB, azul, [amarelo, verde, vermelho, amarelo, verde]),
regiao(paisC, verde, [amarelo, azul, vermelho]),
regiao(paisD, vermelho, [amarelo, azul, verde, amarelo, verde]),
regiao(paisE, amarelo, [azul, vermelho, verde]),
regiao(paisF, verde, [amarelo, azul, vermelho, amarelo]) ] ;
102
R = [ regiao(paisA, verde ,[amarelo, vermelho, azul, vermelho]),
regiao(paisB, amarelo ,[verde, vermelho, azul, verde, vermelho]),
regiao(paisC, vermelho, [verde, amarelo, azul]),
regiao(paisD, azul, [verde, amarelo, vermelho, verde, vermelho]),
regiao(paisE, verde, [amarelo, azul, vermelho]),
regiao(paisF, vermelho, [verde, amarelo, azul, verde]) ] ;
103
Sistema Especialista no Planejamento Empresarial
Os sistemas especialistas são aplicações computacionais
capazes de simular o comportamento de um especialista
humano, em um determinado assunto, a fim de descobrir ou
resolver um determinado problema. Os sistemas especialistas
estão presentes em vários ramos da computação como:
OCRs, reconhecimento de voz, diagnóstico médico, jogo de
xadrez, sistema de computação de bordo de carros, sistema de
controle de robôs, etc. Nosso exemplo de sistema especialista
identifica alguns dos vários problemas que uma empresa tem
que resolver do ponto de vista estratégico. No exemplo
colhemos do usuário informações sobre o estado da empresa
bem como as condições gerais do mercado e, através destas
informações, inferimos outras coisas (assim como um
especialista humano faria). As informações que colhemos
devem estar relacionadas, ou encadeadas, de forma a
podermos construir grafos de causa-conseqüência. O grafo
abaixo representa três possíveis problemas que devemos
verificar e seus relacionamentos de causa-conseqüência.
104
Podemos dizer por exemplo que se: Funcionarios fazem
hora-extra frequentemente for verdadeiro e Projetos estao
atrasados for verdadeiro então concluímos (inferimos) que
Servico esta sobrecarregado é verdadeiro.
Nosso programa deve verificar cada um dos três problemas
que representamos fazendo perguntas quando necessário
(texto em preto), tirando conclusões (texto em azul) e
identificando o problema (texto em vermelho). O código
PROLOG é o seguinte:
conclusao(‘Ha necessidade de contratar pessoal’, [[‘Servico
esta sobrecarregado’, 1], [‘As vendas aumentaram’, 1],
[‘Nivel de informatizacao e bom’, 1]]).
conclusao(‘Ha necessidade de informatizar o setor’, [[‘Servico
esta sobrecarregado’, 1], [‘As vendas aumentaram’, 1],
[‘Nivel de informatizacao e bom’, 0]]).
conclusao(‘Ha necessidade de terceirizar o servico’, [[‘Ha
viabilidade em terceirizar o servico’, 1],
[‘Determinado servico esta custando caro para a empresa’, 1],
[‘Investir em tecnologia ao inves de terceirizar o servico nao e
viavel’, 1]]).
regra(‘Servico esta sobrecarregado’, [[‘Funcionarios fazem horaextra frequentemente’, 1], [‘Projetos estao atrasados’, 1]]).
regra(‘Nivel de informatizacao e bom’, [[‘Hardware e software estao
atualizados’, 1], [‘Numero de computadores e satisfatorio’, 1]]).
regra(‘Ha viabilidade em terceirizar o servico’, [[‘Existe uma
empresa especializada no servico a ser terceirizado’, 1],
[‘Transporte e comunicacao com a empresa de
terceirizacao e caro’, 0],
[‘O servico da empresa de terceirizacao e caro’, 0]]).
regra(‘Investir em tecnologia ao inves de terceirizar o servico nao e
viavel’, [[‘Novas tecnologias para o setor a ser terceirizado sao
caras’, 1], [‘Pesquisa com os funcionarios aponta rejeicao
com a tecnologia da empresa de terceirizacao’, 1]]). 105
pergunta(Frase, Resposta) :- write(Frase), display(' ? (s ou n)
: '), read(SimOuNao),
trata_resposta(Frase, SimOuNao, Resposta).
trata_resposta(Frase, s, 1) :- assert(fato(Frase, 1)), !.
trata_resposta(Frase, _, 0) :- assert(fato(Frase, 0)).
conhecido(Frase) :- fato(Frase, _).
nao_perguntavel(Frase) :- conclusao(Frase, _).
nao_perguntavel(Frase) :- regra(Frase, _).
calcula_regra([], 1) :- !.
calcula_regra([[Frase, Esperado]|Calda], Resultado) :fato(Frase, Esperado), calcula_regra(Calda, Resultado), !.
calcula_regra([[Frase, Esperado]|Calda], Resultado) :regra(Frase, Condicoes), calcula_regra(Condicoes,
PreResultado), Esperado==PreResultado,
calcula_regra(Calda, Resultado), !.
calcula_regra([[Frase, Esperado]|Calda], Resultado) :not(conhecido(Frase)), not(nao_perguntavel(Frase)),
pergunta(Frase, PreResultado), Esperado==PreResultado,
calcula_regra(Calda, Resultado), !.
calcula_regra(_, 0).
resolve(Problema) :- retractall(fato(_, _)), conclusao(Problema,
Condicoes), calcula_regra(Condicoes, 1), !.
resolve('Não consegui chegar a nenhuma conclusão') :- !.
O predicado conclusao relaciona as informações que
podemos inferir para chegar a uma conclusão final do
problema bem como os fatores que determinam esta
inferência. O predicado regra relaciona todos as informações
que podemos inferir, exceto as inferências que nos levam a
uma conclusão. O predicado pergunta é utilizado quando
precisamos de uma informação mas não a temos, neste caso,
o predicado pergunta lê a resposta do usuário e trata esta
resposta.
106
O predicado trata_resposta utiliza a predicado assert de
PROLOG para inserir uma nova clausula chamada fato em
tempo de execução, esta clausula fato relaciona uma pergunta
e uma resposta dada pelo usuário. O predicado conhecido
verifica se já existe um fato (uma resposta do usuário)
relacionado a uma determinada pergunta. O predicado
nao_perguntavel verifica se uma certa pergunta não é do tipo
que o usuário pode responder, ou seja, se ela não é uma
pergunta e sim o resultado de uma inferência. O predicado
calcula_regra retorna o valor de uma certa inferência feita
através de um fato existente, do processamento de outras
regras ou de uma pergunta ao usuário. O predicado resolve
busca cada um dos problemas possíveis e verifica se algum está
ocorrendo. A seguir algumas execuções do programa:
?- resolve(Problema).
Funcionarios fazem hora-extra frequentemente ? (s ou n) : ? s.
Projetos estao atrasados ? (s ou n) : ? s.
As vendas aumentaram ? (s ou n) : ? s.
Hardware e software estao atualizados ? (s ou n) : ? s.
Numero de computadores e satisfatorio ? (s ou n) : ? n.
Problema = 'Ha necessidade de informatizar o setor’
Podemos verificar também se um determinado problema
está ocorrendo, a resposta será então do tipo yes ou no.
?- resolve('Ha necessidade de terceirizar o servico').
Existe uma empresa especializada no servico a ser terceirizado
? (s ou n) : ? s.
Transporte e comunicacao com a empresa de terceirizacao e
caro ? (s ou n) : ? n.
O servico da empresa de terceirizacao e caro ? (s ou n) : ? s.
no
107
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
108
Metodologia de Programação
Critérios de Qualidade de Programação
Para o desenvolvimento de Programas Procedimentais
Convencionais de boa qualidade diversos critérios de
Engenharia de Software devem ser observados, assim
como técnicas e práticas;
Para um bom estilo de programação em Prolog esses
critérios também devem ser observados. Cabe salientar
que os critérios de Correção e Eficiência são os mais
importantes para a construção de programas de boa
qualidade.
Princípios Gerais de uma Boa Programação
Critérios de avaliação:
Correção;
Eficiência;
Transparência e Legibilidade;
Modificabilidade;
Robustez;
Documentação;
109
A importância de cada critério vai depender do
problema e das circunstâncias em que o programa é
desenvolvido, e do ambiente em que será utilizado (o
critério mais importante sem dúvida é o da correção);
Uma das regras gerais para se atingir esses critérios é
primeiro “pensar” sobre o problema a ser resolvido e
somente iniciar a codificação depois de se ter
formulado uma idéia clara sobre o que deve ser feito;
O processo de conversão dessa idéia pode ser difícil.
Uma abordagem consagrada é a de utilizar o "princípio
dos refinamentos sucessivos“. Essa estratégia apresenta
as seguintes vantagens:
Permite a formulação de uma solução inicial nos
termos mais relevantes ao problema;
Essa solução inicial é, por conseguinte, mais
simples e sucinta, sendo a sua correção facilmente
verificável, e;
Se cada passo de refinamento for pequeno o
suficiente para ser manejado intelectualmente,
preserva mais facilmente a sua correção.
No caso da linguagem Prolog, pode-se pensar em tal
processo como sendo o de refinamento de relações. Ou
pensar em refinamentos de algoritmos, adotando então
a visão procedimental do Prolog.
110
Como Pensar em PROLOG
Uma característica importante da linguagem Prolog
é permitir que seus programas sejam pensados tanto
declarativa quanto procedimentalmente;
Normalmente as souções declarativas são mais fáceis
de desenvolver e possuem a clareza e limpidez da pura
lógica;
Durante o processo de desenvolvimento de uma
solução, deve-se buscar as idéias adequadas para
decompor um problema em subproblemas de solução
mais fácil.
"Como encontrar os subproblemas apropriados?"
Uso de Recursão
Na solução de problemas envolvendo o
processamento sequencial por meio de recursão, é
uma boa heurística aplicar pensamento indutivo e
resolver os seguintes dois casos separadamente:
Os casos triviais, ou básicos, em que o
argumento é uma lista vazia ou unitária, e
Os casos gerais, em que o argumento é uma
lista [Cabeça|Corpo] e o problema é assumido
resolvido para "Corpo“;
111
Exemplo:
 Processar uma lista de itens de tal maneira que
cada item seja operado por uma mesma regra de
transformação:
transforma(Lista, F, NovaLista)
onde Lista é a lista original, F é uma regra de
transformação e NovaLista é a lista de todos os itens
transformados.
O problema de transformar Lista em NovaLista
pode ser subdividido em dois casos:
Caso Básico: Lista = []
Se Lista = [],
então NovaLista = [],
independentemente de F.
Caso Geral: Lista = [X | Resto]
Para transformar uma lista do tipo [X | Resto] em
uma lista do tipo [NovoX | NovoResto], transforme
Resto, obtendo NovoResto e transforme X, obtendo
NovoX.
Em Prolog:
transforma([], _, []).
transforma([X | Resto], F, [NovoX | NovoResto])
:- G =.. [F, X, NovoX], call(G),
transforma(Resto, F, NovoResto).
112
Generalização
 Uma boa idéia é generalizar o problema original,
de forma a permitir que a solução do problema
generalizado seja formulada recursivamente;
A generalização de uma relação envolve
tipicamente a introdução de um ou mais argumentos
extras.
"Como encontrar a generalização correta?“
Exemplo:
 Problema das oito damas. Temos a relação:
oitoDamas(Posição)
que será verdadeira se Posição representar uma
posição do tabuleiro tal que nenhuma dama ataque
as restantes.
 Uma idéia interessante, nesse caso é generalizar o
número de damas de oito para N, de forma que o
número de damas se torna o argumento adicional;
nDamas(Posição, N)
A vantagem dessa generalização é que há uma
formulação recursiva imediata para a relação
nDamas/2.
Uma vez que o problema generalizado está
solucionado, a solução do problema original é
imediata:
oitoDamas(Posição) :- nDamas(Posição, 8).
113
Represetação Gráfica de Problemas
Na busca por idéias para solucionar um dado
problema, frequentemente é de grande utilidade
introduzir alguma representação gráfica do mesmo.
No caso do Prolog, essa técnica parece ser
especialmente produtiva, pois:
Prolog é particularmente adequado para
problemas envolvendo objetos e relações entre
objetos. De modo geral tais problemas podem
ser naturalmente ilustrados por meio de grafos,
onde os nodos correspondem a objetos e os arcos
a relações;
Os objetos estruturados em Prolog são
naturalmente representados por meio de
árvores;
O significado declarativo dos programas
Prolog facilita a tradução de representações
gráficas porque, em princípio, a ordem na qual
o desenho é feito não constitui um fator
importante.
Exemplo:
 Definição de uma regra irmã (X é irmã de Y):
Z
progenitor(Z,X)
irmã(X,Y) :progenitor(Z,Y)
progenitor(Z,X),
progenitor(Z,Y),
mulher(X)
X
Y
irmã (X,Y)
mulher(X).
114
Regras Gerais para uma Boa Programação
As cláusulas do programa devem ser curtas. Seu
corpo não deve conter mais que uns poucos objetivos.
Exemplo:
proc1A :- a, b, c.
proc1B :- d, e, f.
ao invés de
proc1 :- a, b, c, d, e, f.
Os procedimentos do programa devem também ser
curtos (conter poucas cláusulas);
Adotar nomes mnemônicos para procedimentos e
variáveis;
O lay-out dos programas é importante, incluindo
um bom espaçamento, uso de linhas em branco, e
identação;
É importante que as mesmas convenções sejam
usadas de forma consistente em todo o programa;
 O operador cut deve ser usado com cuidado. Seu
uso deve ser evitado quando não for absolutamente
necessário;
O operador not, devido a sua relação com o
cut também pode apresentar comportamento
inesperado. Se entretanto estivermos em dúvida
entre usar o not ou o cut, o primeiro é preferível;
115
 A modificação do programa por meio dos
predicados assert/1 e retract/1 pode degradar em
grande escala a transparência do seu
comportamento;
A legibilidade pode ser algumas vezes incrementada
pela divisão da cláusula que contém o “;”
(correspondendo ao conetivo "ou") em duas.
Exemplo
 Para ilustrar os pontos discutidos até aqui, vamos
considerar a seguinte relação:
merge(L1, L2, L3)
onde L1 e L2 são listas ordenadas que são reunidas
ordenadamente em L3.
A abaixo é apresentada uma implementação sem
muitos critérios:
merge(L1, L2, L3) :L1 = [], !, L3 = L2;
L2 = [], !, L3 = L1;
L1 = [X | Resto1],
L2 = [Y | Resto2],
(X < Y, !, Z = X, merge(Resto1, L2, Resto3);
(Z = Y, merge(L1, Resto2, Resto3))),
L3 = [Z | Resto3].
116
Agora uma outra implementação é apresentada,
mas observando-se as regras apresentadas:
merge([], L, L).
merge(L, [], L).
merge([X | R1], [Y | R2], [X | R3]) :X < Y, !, merge(R1, [Y | R2], R3).
merge(L1, [Y | R2], [Y | R3]) :merge(L1, R2, R3).
Além dessas regras, duas outras
observadas para uma boa programação:
podem
ser
Organização tabular de procedimentos longos, e;
Utilização de comentários.
117
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
118
Lógica Fuzzy
O que é Lógica Fuzzy?
Apostadores como Blaise Pascal inventaram a estatística para
calcular as probabilidades de resultados precisos -- que um dado,
digamos, venha a cair mostrando o quatro. Os meteorologistas na
TV usam números para prever se vai, ou não, chover amanhã.
Mas, de fato, o próprio conceito de "chuva" é difuso. Se dois
pingos de água caem do céu, isso é chuva? E o que dizer de
cinqüenta pingos? E de mil? Suponhamos que a neblina esteja
espessa e baixa, e você sinta gotas de água em seu rosto. Isso é
chuva? Onde passa a linha divisória? Quando a não-chuva se
torna chuva?
Assim, uma definição precisa para Lógica Fuzzy não existe,
mas o significado pode ser explicado. Enquanto a Teoria dos
Conjuntos e a lógica matemática divide o mundo com “branco” e
“preto”, conjuntos fuzzy definem os tons de “cinza” entre o
“branco” e o “preto”. Seu uso é significativo quando aplicado à
fenômenos complexos que não são facilmente descritos pelos
métodos matemáticos tradicionais, especialmente quando o
objetivo é obter uma resposta aproximada.
Se a "lógica difusa" tem uma origem, esta reside na tentativa da
Lógica de se adaptar aos paradoxos de Russel e à incerteza de
Heisenberg. O lógico polonês Jan Lukasiewicz desenvolveu uma
lógica "multivalente" nos anos de 1920, refinando a lógica binária
do sim-não, da física newtoniana, para permitir estados
indeterminados. Em 1965, o matemático Lotfi Zadeh, de
Berkeley, aplicou essa nova lógica à teoria dos conjuntos, em seu
artigo "Conjuntos Difusos", que depois emprestou seu nome à
lógica
119
O que é Lógica Fuzzy? (Cont.)
.
• Os conjuntos difusos são a chave para as máquinas difusas.
A maioria dos artefatos com os quais você está familiarizado
são "burros" — isto é, rigidamente programados. Um sistema
de aquecimento controlado por termostato é o exemplo
clássico da máquina burra. Quando a temperatura cai abaixo
de determinado ponto, o aquecedor é ligado; quando ela
ultrapassa uma outra determinada temperatura, o aquecedor é
desligado. O mecanismo é binário: o aquecedor está "ligado"
ou "desligado", e quando está ligado, está sempre aquecendo o
ambiente com a mesma intensidade.
• As máquinas difusas, por outro lado, usam conjuntos difusos
para produzir respostas mais flexíveis, permitindo que se
estabeleça um determinado grau de quente ou frio. Se
decidimos que 20° é a temperatura perfeita, podemos dizer a
um aquecedor/condicionador de ar para modular seu
comportamento, dependendo de quanto a temperatura atual
difere de 20° . O aparelho nunca estaria só ligado ou desligado
— ele estaria sempre ligado em um grau variável de
aquecimento.
• Concluindo, os conjuntos Fuzzy são uma generalização dos
Conjuntos Clássicos, assim como a Lógica Infinito-Valorada é
uma generalização da Lógica Clássica. Lógica Fuzzy é uma
incorporação dos Conjuntos Fuzzy e pode ser visto como uma
extensão da Lógica Infinito-Valorada por aplicá-la aos
conjuntos fuzzy.
120
Lógica
Clássica
Estende
Lógica
Infinito
Valorada
Correspondência
Lógica
Fuzzy
Está para
Conjuntos
Clássicos
Estende
Conjuntos
Fuzzy
Números Fuzzy
Figura F1. Envolvimento da Lógica Fuzzy com a lógica tradicional
Elementos da lógica Fuzzy
• Um número Fuzzy é uma função F(x) composta por várias
outras funções contínuas tal que os valores de retorno estão
entre 0 e 1, obrigatoriamente, em um intervalo [a1, b1], e os
valores em F(a1) e F(b1) são 0 (zero). Exemplo:
F(x)
1
0
a1
b1
x
Gráfico F2: exemplo
de número fuzzy 121
Elementos da lógica Fuzzy (continuação)
• Números Fuzzy é um caso particular dentro dos Conjuntos
Fuzzy, cujo o conjunto é definido como um par ordenado (x, (x))
onde (x) devolve um valor entre [0, 1] mas não necessariamente
sempre incluindo o 0 e o 1, requisitos obrigatórios para um número
fuzzy.
Exemplos de um conjunto fuzzy:
µ
1
x
0
Gráfico F3: exemplo de conjunto fuzzy
• Enquanto isso, na Lógica Clássica, uma proposição é uma
sentença que é, logicamente, ou verdade, denotada por 1, ou
falsa, denotada por 0. O conjunto T={0, 1} é chamado de
conjuntos de valores verdadeiros. Exemplo: a proposição
o número 3 é um inteiro é verdadeira.
• Já na Lógica Multivalorada é permitida a proposição ter mais do
que um valor verdadeiro que esteja entre [0, 1], como por
exemplo T8 = {0, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1} representa um
conjunto com 8 valores verdadeiros. Se o conjunto de valores
verdadeiros compreende todos os números reais em [0, 1], então
chamamos a lógica multivalorada de Lógica Infinito-valorada
122
Elementos da lógica Fuzzy (continuação)
•A Lógica Fuzzy tem foco em variáveis linguísticas da linguagem
natural e visa prover fundamentos para resultados aproximados
com proposições imprecisas. Exemplo:
•Velocidade, na linguagem natural, trata de quão rápido algo
se move, mas dizer se ele é rápido depende de cada
indivíduo. Assim, podemos definir velocidade como sendo
uma variável lingüística consistindo de conjuntos fuzzy como
rápido, meio-rápido, normal, meio-devagar e devagar.
devagar
µ
rápido
normal
Meio-devagar
Meio-rápido
1
0
30
40 50 60 75 80
95
115
150
x
Gráfico F4: conjuntos fuzzy descrevendo velocidade
123
Por que se usa Lógica Fuzzy
Porque facilita o desenvolvimento de softwares baseados em
situações onde a imprecisão pode responder melhor às necessidades.
Engenheiros acusam uma redução de metade do tempo de
desenvolvimento dos sistemas, aproximadamente. No início, foram
usados sistemas com fuzzy para inúmeros produtos comerciais, como
lavadoras, chuveiros, aspiradores de pó, etc. Por exemplo, a cidade
Sendai, Japão, vem usando lógica fuzzy para controle de seus trens do
metrô desde 1986.
Aplicações da Lógica Fuzzy
• O emprego de Controle de Fuzzy é recomendável:
•1 - Para processos muito complexos, quando não há
modelo matemático simples;
2 - Para processos altamente não lineares;
•O emprego do Controle de Fuzzy não é recomendável se:
•1 - A teoria convencional de controle dá resultados
satisfatórios;
2 - Um modelo matemático adequado e de fácil
resolução já existe;
Exemplos de aplicações
Controle simplificado de robôs (Fuji Eletric, Toshiba), Prevencão contra
flutuações de temperatura em sistemas de ar condicionado (Mitsubishi,
Sharp), Controle eficiente e estável de fábrica de carros (Nissan),
Planejamento otimizado de tabelas de controle de horários de ônibus
(Toshiba), Combinação de Lógica Fuzzy e Redes Neurais (Matsushita),
Desenvolvimento de sistemas anti-vibração para câmera filmadora
(Matsushita)
124
Estrutura de um programa Fuzzy
 Os estágios de fuzzificação, aplicação das regras
fuzzy e de-fuzzificação correspondem ao fato do
programa ler um dado do meio, digamos a
velocidade do carro, descobrir quão “rápido”,
“meio-rápido”,
“normal”,
“meio-devagar”,
“devagar” (fuzzificação - transformar um dado do
meio em uma variável lingüística), aplicando em
seguida as regras fuzzy para chegar em outra
variável lingüística, por exemplo, pressão da
aceleração, com valores “máxima”, “média” e
“mínima”. Depois disso tudo, a variável resultado
(pressão da aceleração) é transformada em um valor
real (de-fuzzificação) a ser enviado de volta para o
meio.
Por exemplo, nosso sistema obteria a velocidade
atual do carro, digamos de 120 Km/h, e
transformaria esse valor em uma variável lingüística
velocidade, que, pelo gráfico F4, podemos concluir
que esta será 57,14% rápida e 0% para as outras
definições (meio-rápida, normal, meio-devagar e
devagar). Aplicando as regras fuzzy (serão
abordadas mais à frente) podemos chegar numa
outra variável lingüística pressão da aceleração com
valores, digamos de 50% em mínima, e 0% em média
e máxima.
125
Exemplo (viagem de carro)
VARIÁVEIS
FUZZY
REGRAS
FUZZY
VARIÁVEIS
FUZZY
PRESSÃO DA
ACELERAÇAO
VELOCIDADE
RAPIDO
MAXIMA
MEIO RAPIDO
120
REGRAS
MEDIA
NORMAL
Km/h
10
PSI
FUZZY
MEIO DEVAGAR
DEVAGAR
FUZZIFICAÇÃO PROPAGAÇÃO
MINIMA
126
DE-FUZZIFICAÇÃO
Ferramentas para Prolog
 Existem muitas ferramentas especializadas para o
desenvolvimento de programas usando fuzzy, entre
elas o FLINT (Fuzzy Logic Inference Toolkit), para o
Win-Prolog.
Variáveis Fuzzy no FLINT
• Pertencem a uma faixa de valores (ex: 0 a 100)
• Armazenam um único valor (ex: velocidade)
• Possuem qualificadores, que subdividem a faixa
de valores, compostos de:
• um nome (qualificador lingüístico - rápido)
• uma função membro que define o grau de
pertinência do valor para este qualificador. A
função membro é definida por:
•Forma ( /, \, /\, /-\, \-/, \/ ou ?)
•Curvatura (linear ou curve)
•Pontos Relevantes (pontos da forma)
• Possuem ainda a definição do tipo de método de
De-fuzzificação a ser usado (ex: peak, centroid ou
uma expressão definida pelo usuário)
127
Qualificadores de variáveis Fuzzy
\
/
/\
\/
[A,
[A,
[A,
[A,
B]
B]
B, C]
B, C]
descida de rampa
subida de rampa
triângulo para cima
triângulo para embaixo
/-\
\-/
?
[A, B, C, D] trapezóide para cima
[A, B, C, D] trapezóide para baixo
[V1/M1, V2/M2, Vk/Mk] forma livre
Exemplos de Qualificadores
Exemplo de subida de rampa (símbolo
‘/’) com pontos A e B e curvatura linear
A
B
Exemplo de descida de trapézio (símbolo
‘\-/’) com pontos A, B, C e D com
curvatura linear
B C
D
A
Exemplo de forma livre (representada por
‘?’). Os pontos V1/M1 é um dos
segmentos de reta que compoem o
gráfico.
V1/M1
128
Tipos de Curvatura
•Linear (ex: triângulos, trapézios)
•Curve
•Menor que 1
•Igual a 1
•Maior que 1
Métodos de De-fuzzificação
Centroid - centro de gravidade (default) obtém o
valor final calculando o centro da área do gráfico gerado
pela variável fuzzy resultante.
Peak - maior nível da função. Obtém o valor final
calculando a média dos picos da função resultante
Expressão definida pelo usuário
129
Exemplo de variável fuzzy no FLINT
Faixa da variável fuzzy
(opcional)
Nome da variável fuzzy
fuzzy_variable(velocidade)
[0, 200];
rápido,
/ , linear,
meio-rápido, /\, linear,
normal,
/\, linear,
meio-devagar, /\, linear,
devagar,
\, linear,
peak.
:[
[75,
[40,
[30,
[ 0,
80, 150];
95, 115];
60, 80];
40, 50];
40
];
Pontos do
gráfico
Método
de-fuzzy
Nome do
qualificador
Formas
Curvatura
Definição de Regra Fuzzy
•Consistem de conjuntos de condições IF (usando
conectivos and e or)
•Uma conclusão (then)
•Uma conclusão opcional (else)
•São aplicadas às variáveis através de um processo
chamado “Propagação”
130
Exemplo de declaração de regra no FLINT
Nome da regra
fuzzy
Nome de
variável
de
condição
Nome do qualificador
de condição
fuzzy_rule(risco1)
if velocidade is rápida
then pressão_da_aceleração is mínima
else pressão_da_aceleração is média.
Nome de variável
de conclusão
Nomes de qualificador de
conclusão
Programa exemplo
Implementando um sistema controlador de turbina
131
Variáveis Fuzzy
São usadas Throttle, Pressure e Temperature como variáveis
fuzzy para representar as características da turbina, além de
podermos definir que Pressure e Temperature serão variáveis
de entrada enquanto Throttle será de saída. Para a variável
Temperature definiremos os seguintes modificadores: cold,
cool, normal, warm, hot. Para a variável Pressure defineremos
os modificadores: high, low, medium. Para a variável Throttle,
os modificadores negative-large, negative-medium, negativesmall, zero, positive-small, positive-medium, positive-large.
Operadores Linguísticos
É necessário definir alguns operadores linguísticos (sempre
definidos dessa maneira para todo programa que usa o FLINT):
:- op( 1200, xfy, ( if )
),
op( 1200, xfy, ( then ) ),
op( 1200, xfx, ( else ) ),
op( 1100, xfy, ( or
)
),
op( 1000, xfy, ( and )
),
op(
700, xfx, ( is
)
),
op(
600,
fy, ( not )
).
Estes são os operadores para as regras fuzzy, definindo
condição, conclusão, conjunção, disjunção e negação.
132
Definindo as Variáveis Fuzzy
Definindo a variável temperature:
fuzzy_variable( temperature ) :[ 0 , 500 ];
cold,
\, linear, [ 110 , 165
cool,
];
/\, linear, [ 110 , 165 , 220 ];
normal, /\, linear, [ 165 , 220 , 275 ];
warm,
/\, linear, [ 220 , 275 , 330 ];
hot,
/,
linear, [
275 , 330 ].
O gráfico da função seria equivalente a:
1
cold
0
110
cool
normal
warm
165
220
275
hot
330
temperature
133
Definindo as Variáveis Fuzzy
Definindo a variável pressure:
fuzzy_variable( pressure ) :[ 0 , 300 ] ;
weak,
\, linear, [ 10 , 70
low,
/\, linear, [ 10 , 70 , 130
ok,
/\, linear, [ 70 , 130 , 190
strong, /\, linear, [ 130 , 190 , 250
high,
/ , linear, [
190 , 250
];
];
];
];
].
O gráfico da função seria equivalente a:
1
weak
0
10
low
ok
70
130
strong
190
high
250
pressure
134
Definindo as Variáveis Fuzzy
Definindo a variável throttle:
fuzzy_variable( throttle ) :[ -60 , 60 ];
negative_large,
\, linear, [ -45, -30
];
negative_medium, /\, linear, [ -45, -30, -15 ];
negative_small,
/\, linear, [ -30, -15,
zero,
/\, linear, [ -15,
positive_small,
/\, linear, [
positive_medium, /\, linear, [
positive_large,
/,
0 ];
0,
15 ];
0,
15,
30 ];
15,
30,
45 ];
linear, [
30 , 45 ];
centroid .
O gráfico da função seria equivalente a:
Negative_medium
Positive_medium
1
Negative_small
Positive_small
Negative_large
positive_large
zero
0
10
70
130
190
250
throttle
135
Definindo as Regras Fuzzy
Pode-se definir as regras fuzzy através de decisões, como por exemplo :
’se a temperatura é fria e a pressão é fraca então aumente a
válvula em grandes quantidaddes’
pode ser definida por:
fuzzy_rule(throttle1)
if temperature is cold
and pressure is weak
then throttle is positive_large.
Mas como estas regras irão sempre se aplicar às variáveis fuzzy
temperature, pressure e throttle, podemos então colocar todas as regras
dentro de uma única matriz (onde a primeira linha indica quais as
variáveis a serem usadas, o símbolo ‘*’ é equivalente ao símbolo
‘and’ da regra fuzzy acima, assim como o símbolo ‘->’ equivale ao
‘then’):
fuzzy_matrix( t ) :temperature
cold
cold
cold
cold
cold
cool
cool
cool
cool
*
*
*
*
*
*
*
*
*
*
pressure
weak
low
ok
strong
high
weak
low
ok
strong
->
->
->
->
->
->
->
->
->
->
throttle
;
positive_large ;
positive_medium;
positive_small ;
negative_small ;
negative_medium;
positive_large ;
positive_medium;
zero
;
negative_medium;
(continuna na próxima página).
136
Definindo as Regras Fuzzy (Continuação)
(continuação da matriz de regras)
cool
normal
normal
normal
normal
normal
warm
warm
warm
warm
warm
hot
hot
hot
hot
hot
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
high
weak
low
ok
strong
high
weak
low
ok
strong
high
weak
low
ok
strong
high
->
->
->
->
->
->
->
->
->
->
->
->
->
->
->
->
negative_medium;
positive_medium;
positive_small ;
zero
;
negative_small ;
negative_medium;
positive_medium;
positive_small ;
negative_small ;
negative_medium;
negative_large ;
positive_small ;
positive_small ;
negative_medium;
negative_large ;
negative_large .
Definindo a Propagação
Definindo uma nova prograpação das regras fuzzy, ou seja, dados
as variáveis de entrada (temperature e pressure), como obter a
variável de saída, throttle, através dos predicados
fuzzy_propagate e fuzzy_variable_value (obtenção dos valores) e
o predicado fuzzy_reset_membership para garantir que não
haverá velhos valores armazenados
(continuna na próxima página).
137
Definindo a Propagação (Continuação)
Exemplo:
find_throttle(Temperature, Pressure, Throttle):fuzzy_reset_membership( throttle ),
fuzzy_variable_value( temperature, Temperature),
fuzzy_variable_value( pressure,
Pressure ),
fuzzy_propagate( minimum, maximum, complement,[t]),
fuzzy_variable_value( throttle,
Throttle ).
Rodando o exemplo
Após declarado os operadores lingüísticos, as
variáveis fuzzy, a matriz de regras e
finalmente, a propagação, todos listados
acima, usaremos o predicado find_throttle para
a execução:
?- find_throttle( 300, 150, Throttle ) .
Throttle = -26.040413058933
E assim termina nosso exemplo de como usar lógica fuzzy no
Win-Prolog com o módulo FLINT.
138
Programação Lógica
Linguagem PROLOG
Fatos, Regras e Controle de
Corte
Operadores e Listas
Entrada e Saída
Manipulando Base de Dados
Outros Exemplos
Metodologia de Programação
Lógica Fuzzy
Exercícios
139
Exercícios
1. Um programa Prolog tem as seguintes cláusulas :
vertical(Seg(ponto(X,Y), ponto(X,Y1)).
horizontal(Seg(ponto(X,Y), ponto(X1,Y)).
Dê os resultados das seguintes consultas :
?- vertical(seg(ponto(1,1), ponto(1,2))).
?- vertical(seg(ponto(1,1), ponto(2,Y))).
?- horizontal(seg(ponto(1,1), ponto(2,Y))).
?- vertical(seg(ponto(2,3),P)).
2. Dê o resultado das seguintes instanciações :
a) point(A,B) = point(1,2)
b) point(A,B) = point(X,Y,Z)
c) [a, b, c, [ab], [], [[a], c]] = [X, Y|Z]
d) [p, [seg], t, q] = [X, [Y], Z|S]
e) [X, Y|Z] = [2, [3,4]]
f) [lista, de, exercicios, de, PL] = [X, de|W]
3. Construa uma base de dados sobre livros com pelo
menos cinco estruturas do tipo :
livro( nome(‘C completo’), autor(‘Schildt’),
pal_chave([linguagemc, programacao, computacao]))
140
a) Escreva consultas para encontrar :
•
•
•
•
Nome do autor, dado o nome do livro.
Nome do livro, dado o nome do autor.
As palavras chave, dado o nome do livro.
Nome do autor e nome do livro, dado uma palavra
chave.
b) Escreva um programa Prolog para, dada uma lista de
palavras chave, encontrar nome e autor dos livros que
tem pelo menos uma das palavras chave fornecidas. Os
livros encontrados devem ser dados um de cada vez.
4. Defina os predicados n_par(Lista) e n_impar(Lista)
dara determinar se uma lista tem número par ou ímpar
de elementos.
5. Defina a relação traduz(L1,L2) para traduzir uma lista
de números entre 0 e 9 para a palavra correspondente.
Por exemplo :
traduz([1,2,3], L).
L = [um, dois, tres]
Use a relação auxiliar : t(0, zero), t(1, um)..........
6. Quais seriam os modos de chamada para os predicados
do exercício anterior?
7. Defina o predicado between(N1, N2, L), tal que, para
dois números inteiros dados N1 e N2, guarde na lista L
todos os valores X tal que N1 <= X <= N2.
141
8. Escreva um programa Prolog que possa responder a
seguinte pergunta : “Eu sou meu próprio avô?”, criando
um conjunto de relações que representem a seguinte
situação :
“Eu me casei com uma viúva(W) que tem uma filha
adulta(D). Meu pai(F), que nos visitava frequentemente,
se apaixounou por minha enteada e casou – se com ela.
Logo, meu pai se tornou meu enteado e minha enteada
tornou – se minha madrasta. Alguns meses depois,
minha mulher teve um filho(S1), que se tornou cunhado
do meu pai, assim como meu tio. A mulher do meu pai,
isto é, minha enteada, também teve um filho(S2).”
9. Mostre a execução de um programa Prolog para o
exemplo da regra de Fibonacci recursiva. Procure deixar
bem claro os passos onde ocorrem unificação e
backtracking.
10. Baseando – se no programa que faz busca em largura
apresentado no slide 62, faça um programa que execute
busca em profundidade. Dica : É necessário apenas uma
pequena modificação no algoritmo de busca em largura.
11. Faça, sem olhar em slides anteriores, um programa
Prolog que resolva o problema dos missionários e
canibais.
12. Faça, sem olhar em slides anteriores, um programa
Prolog que resolva o problema das rainhas em um
tabuleiro de xadrez.
142
13. Considere o seguinte problema :
“Um fazendeiro está na margem norte de um rio com
uma cabra, um lobo e um repolho. Existe um bote
através do qual o fazendeiro pode transportar um
elemento por vez para a outra margem do rio. Se o lobo
e a cabra ficarem sozinhos numa margem, o lobo comerá
a cabra. Se a cabra e o repolho ficarem sozinhos em uma
margem, a cabra comerá o repolho. Como transportar
com segurança os três elementos, considerando o
respolho um passageiro?”
Crie as cláusulas move da busca em largura para
resolver esse problema.
14. Crie uma representação qualquer em Prolog para
árvores.
a) Faça um código que verifica se um dado elemento
pertence à uma árvore.
b) Faça um código que mostra todos os elementos de uma
árvore(ou guarda todos os elementos em uma lista).
c) Faça um código que verifica se a árvore é uma AVL.
d) Faça códigos de inserção e remoção de elementos da
árvore.
143