1 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

Universidade Federal de São CarlosDepartamento de Computação

Programação Lógica

Prof. Dr. Antonio Francisco do Pradoe-mail: [email protected]

2

Entrada e Saída

Manipulando Base de Dados

Outros Exemplos

Operadores e Listas

Fatos, Regras e Controle de Corte


Linguagem PROLOG

Metodologia de Programação

Lógica Fuzzy

Exercícios

3


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;

4

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.

5

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".

6

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.

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.

Características da Programação Lógica

7

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.

Aplicações da Programação Lógica

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

Linguagens Convencionais x Lógicas

8

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

9

Linguagem PROLOG

Linguagens Funcionais x Lógicas

Funcional Lógica

Programação orientada para funções

Programação orientada para objetivos (“goal”)

Diz “como fazer” para atingir um objetivo

Diz “o que fazer” para atingir um objetivo

Mais voltada para algoritmos que exploram o conhecimento

Mais voltada para o conhecimento

Preocupa-se com aspectos relacionados com a construção de listas, tipos, padrão de comparação, estruturas de dados, etc.

Mais declarativa do que procedural

Camada mais baixa de suporte para as aplicações

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.

10

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

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).

Programação Prolog

Histórico

11

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.

12

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 entreoutros.

Também é importante que o aluno tente resolver os exercícios propostos no ultimo

capítulo, para consolidar o seu aprendizado.

13

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

14


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.

Introdução

Um objeto de dados em Prolog é definido de acordo com a seguinte árvore :

objetos

objetos simples estruturas

constantes variáveis

átomos números

15

• Á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)

16

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.

pam tom

bob liz

ann pat

jim


17

?-progenitor(bob,pat).yes

?-progenitor(liz,pat).no

?-progenitor(X,liz).X=tom ; no

?-progenitor(bob,X).X=annX=pat

?-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 ;

progenitor(pam,bob). %pam é um dos progenitores de bobprogenitor(tom,bob).progenitor(tom,liz). %tom é um dos progenitores de lizprogenitor(bob,ann).progenitor(bob,pat).progenitor(pat,jim).

Em Prolog usam-se maiúsculas para variáveis e minúsculas para átomos.

átomo variável

Questões:

18

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

Y

jim

Progenitor

Progenitor

Avos

"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.

19

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).

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.

se corpocabeça(conclusão) (condição)

20

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 se corpo

(conclusão) (condição)

21

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

22

Exemplos:

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

?-avos(pam,X).X=ann ;X=pat

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.

conjunção e

amiga(X):-(X = maria; X = joana).

disjunção ou

Conjunção e Disjunção

23

Definição de uma regra irmã:irma(X,Y):-progenitor(Z,X),progenitor(Z,Y),mulher(X).

Questões:?-irma(ann,pat).yes

Z

X Y

progenitor progenitor

mulherirmã

?-irma(X,pat).X=ann ;X=pat ;no

Definição de uma regra diferente:diferente(X,Y):-X\==Y. %X é diferente de Y

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

24

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

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

Recursão

Definição de uma regra antepassado

Necessita de duas regras: antepassados diretos e antepassados indiretos.

Antepassados diretos

bob

pat

jim

Antepassados indiretos

25

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).

....

26

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.

A segunda regra fica:

antepassado(X, Z) :- progenitor(X, Y),

antepassado(Y, Z).

Z

X

Y

Progenitor

Antepassado

Antepassado

Questões:?-antepassado(X,liz).X=tom ;no

?-antepassado(X,pat).X=bob ;X=pam ;X=tom ;no

27

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 pela exclamação (“!”).

Seu 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);Economiza memória (corta a ávore de pesquisa).

28

Questões:?- minimo(10,3,Min).Min = 3

Mínimo entre dois números:minimo(X,Y,X):-X =< Y, !.minimo(X,Y,Y):-X > Y, !.

?- minimo(12,56,Min).Min = 12

Exemplos:

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).X = joana

?- um_unico_amigo(pedro,X).X = jose

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)

29

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.

Neste caso fail força um backtracking e repete a a impressão.

Questões:?-executa.ana tem conta 123 na agencia bradescojose tem conta 456 na agencia itauno

Fail

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.

O operador unário not define uma forma particular de negação denominada "negação por falha”.

Not (X)

30

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?

r(a).

q(b).

p(X) :- not r(X).

?-q(X), p(X).

X = b.

?-p(X), q(X).

no

Questões:

31

Definição das regras positivo e negativo:positivo(X):-X>=0. %X é maior ou igual a 0negativo(X):-X<0. %X é menor que 0

Questões:?-positivo(7).yes

?-negativo(10).no

Outros Exemplos de Regra

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).

yes

?-impar(6).

no

32

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.

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

0 1 2 3 4 5 6 7 8 9 10

X

0

1

2

3

4

Y=F(X)Y=f(X)

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

33

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).

Passo 1 :fatorial(4, F) { N = 4, N1 =3, F = F1 * 4, fatorial(N1, F1) }




Passo 5 :fatorial(0, F) {F = 1 }

F = 1

F = 2

F = 1

F = 6

F = 24

34

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

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.

35

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

36

Operadores Aritméticos

+ Adição

- Subtração

* Multiplicação

/ Divisão

mod Módulo, o resto inteiro da divisão

is Atribuição

Questão:?- ao_quadrado(6,X).X=36

Exemplo:

Cálculo de um número elevado ao quadrado:ao_quadrado(X,Y):-Y is X*X.

Operadores e Listas

37

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

Questões:?- interv_aberto(5,0,5).no

Exemplo:

Definição de uma regra intervalo aberto:interv_aberto(K,X1,X2):-K > X1,K < X2.

?- interv_aberto(2,0,5).yes

38

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 Cabeça Cauda

[gosto,de, vinho] gosto [de, vinho] [X,Y|Z] X [Y|Z] [[o,gato]] [o,gato] []

39

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 Lista 2 Unificação[mesa] [X|Y] X / mesa Y / [ ][a,b,c,d] [X,Y|Z] X / a Y / b Z / [c,d][[ana, Y] | Z] [[X, foi], [ao, cinema]] X / ana Y / foi Z / [[ao, cinema]][ano, bissexto] [X,Y|Z] X / ano Y/ bissexto Z / [ ]

40

Busca recursiva

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

Lista 1 Lista 2 Unificação[ano, bissexto] [X,Y,Z] não unifica (aridade diferente) [data(7,Z,W), hoje] [X,Y] X / data(7,Z,W) Y / hoje[data(7,W,1993), hoje] [data(7,X,Y), Z] X / W Y / 1993 Z / hoje

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:

41

Goal

?- X = [1,2,3],pertence(a,X). no

?- pertence( a, X),X = [1,2,3].X = [a |_] %pode ser o 1º elemento de XX = [_ , a | _] %pode ser o 2º elemento de XX = [_ , _ , 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].

42

Controle em Prolog

1. Iniciar pelo goal2. Enquanto o goal corrente não é vazio faça

2.1. Comece pelo subgoal mais à esquerda2.2. Se uma regra aplica ao subgoal então

2.2.1. Para esta regra, usando unificadores genéricos, volte

para 2.1Senão backtrack

fim-sefim-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).

43

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 ] ;

44

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(? , +).

45

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

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,c],[d,e,f]). yes

?-nao_pertence([a,b],[b,c]).no

Outros Exemplos de Lista

46

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([ ]).yes

?- eh_lista( 2 )no

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]

47

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 elementomax([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

48

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). ?-inverter([1,2,3,4,5,6],L).L = [c,b,a] 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

49

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 = dY = e ;X = eY = f ;X = fY = g ;no

50

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

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]

51

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

52

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 = 1Y = [2, 3] ; X = 2Y = [1, 3] ; X = 3Y = [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

53

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]).S = [ ] ;S = [a] ;S = [a,b] ;S = [a,b,c] ;S = [b] ;S = [b,c] ;S = [c] ;no

?- sublista([c,d,e], [a,b,c,d,e,f]). yes

?-sublista([c,e],[a,b,c,d,e,f]).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]

54

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, umacom 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]

55

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

56

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

57

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

58

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: olayes

?-oi.Ola.Resposta: _00A0yes

% 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

59

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).16yes

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 é 125Próximo item, por favor: 12.Cubo de 12 é 1728Próximo item, por favor: stop.yes

60

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.

tab(X)

Escreve uma quantidade X de caracteres “espaço” na saída.

579

Deseja calcular novamente (s/n): n.

61

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 cMove um disco de a para bMove um disco de c para bMove um disco de a para cMove um disco de b para aMove um disco de b para cMove um disco de a para cyes

62

Criação e Escrita em Arquivo

?- fcreate(arq,'c:\saida.pl',2).yes

?- output(arq). yes

?- hanoi(3).yes

?- fclose(arq).yes

Move o disco de a para cMove o disco de a para bMove o disco de c para bMove o disco de a para cMove o disco de b para aMove o disco de b para cMove o disco de a para c

Arquivo saida.pl

Nota: Caso o arquivo já exista, utilize o comando fopen(arq,’c:\saida.pl’,2) no lugar de fcreate(arq,’saida.pl’,2).

63

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

64


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óriaY = café ,L = [maria] ;

X = _00E4 ,Y = cha ,L = [jose] ;

X = _00E4 ,Y = coca ,L = [jose] ;

65

X = _00E4 ,Y = guarana ,L = [ana] ;

X = _00E4 ,Y = vinho ,L = [pedro, maria] ; no

?-bagof(X,Y^gosta(Y,X),L). %Lista únicaX = _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]

66

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

67

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.

Questões:?- consult(‘c:\quad.pl’).yes

?- quadrado.5.25yes

quadrado:-read(A),B is A * A,write(B).

Arquivo quad.pl

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

68

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.

69

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.

Questões:?- retract( lento(X) ).X = tom ; X = pat ;no

rapido(ann).lento(tom).lento(pat).

Base de Dados antes da remoção:

?- maisrapido(A, B).no

70

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

71

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 esquerdaCe = número de canibais na margem esquerdaBte = 1 se o bote está na margem esquerda, 0 na direita

Logo, o estado inicial é (5, 5, 1) e o final (0, 0, 0)

72

Representação do Espaço de Estados do Problema

(5,4,0)

(5,5,1)

(5,3,0) (5,2,0) (4,4,0)

(5,4,1) (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,5,1)

(0,1,0) (0,2,0) (0,4,0)

(1,1,1) (0,3,1) (2,2,1) (0,2,1)

(0,0,0)

73

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 estadosmove([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]).

74

move([5,3,0],[5,4,1]). move([0,1,0],[0,3,1]).move([5,3,1],[3,3,0]). move([0,1,0],[1,1,1]).move([5,3,1],[5,0,0]). move([0,3,1],[0,0,0]).move([5,3,1],[5,1,0]). move([1,1,1],[0,0,0]).move([5,4,1],[3,3,0]). move([0,2,1],[0,0,0]).move([5,4,1],[5,1,0]). move([5,0,0],[5,2,1]).move([5,0,0],[5,1,1]). move([3,3,0],[4,4,1]).move([5,1,0],[5,2,1]). move([5,2,1],[2,2,0]).move([2,2,0],[3,3,1]). move([3,3,1],[0,3,0]).move([0,3,0],[0,4,1]). move([0,3,0],[0,5,1]).move([0,4,1],[0,2,0]). move([0,4,1],[0,1,0]).move([0,5,1],[0,2,0]). move([0,5,1],[0,4,0]).move([0,2,0],[2,2,1]). 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.

75

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).

76

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]

77

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).

78

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 ;

79

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 mdc(12, 06) 01 --- 12 | 06 06 12 02 mdc(18, 12) = 6

--- 00

80

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

81

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]

82

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).

83

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.

84

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]

85

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, c, 100).distancia(b, e, 100). distancia(b, f, 100). distancia(c, f, 100).distancia(d, e, 100). distancia(e, g, 300). distancia(e, i, 400).distancia(f, i, 100). distancia(g, h, 300). distancia(h, i, 200).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).

86

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

87

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 lista2) Expande-se (gera-se todos os seus filhos) o primeiro elemento da lista e coloca-se o resultado no final da lista3) 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.

88

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]

89

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).

90

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

91

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(q0, b, q1). transicao(q1, a, q4).transicao(q1, b, q2). transicao(q2, a, q5). transicao(q3, a, q6).transicao(q3, b, q4). transicao(q4, a, q7). transicao(q4, b, q5).transicao(q5, a, q8). transicao(q6, a, q3). transicao(q6, b, q7).transicao(q7, a, q4). transicao(q7, b, q8). transicao(q8, a, q5).

92

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([], []) :- !.

93

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.

94

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]

Representação gráfica da MEF

95

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

96

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).

97

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.

98

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

99

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

100

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]).

101

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.

102

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]) ] ;

103

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]) ] ;

104

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.

105

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 hora- extra 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]]).

106

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.

107

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

108

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

109


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;

110

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.

111

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“;

112

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).

113

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).

114

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

X Y

progenitor(Z,X) progenitor(Z,Y)

mulher(X)

irmã (X,Y)

irmã(X,Y) :-

progenitor(Z,X),

progenitor(Z,Y),

mulher(X).

115

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;

116

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].

117

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 podem ser observadas para uma boa programação:

Organização tabular de procedimentos longos, e;

Utilização de comentários.

118

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

119

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

O que é Lógica Fuzzy?

120

.

• 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.

O que é Lógica Fuzzy? (Cont.)

121

LógicaClássica

ConjuntosFuzzy

ConjuntosClássicos

Lógica Infinito

Valorada

LógicaFuzzy

CorrespondênciaCorrespondênciaEstá para

Números Fuzzy

Figura F1. Envolvimento da Lógica Fuzzy com a lógica tradicional

Elementos da lógica Fuzzy

Estende

Estende

• 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:

a1 b10

1

x

F(x)

Gráfico F2: exemplode número fuzzy

122

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 necessariamentesempre incluindo o 0 e o 1, requisitos obrigatórios para um númerofuzzy.Exemplos de um conjunto fuzzy:

0

1

x

µ

• 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 doque 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 valoresverdadeiros compreende todos os números reais em [0, 1], entãochamamos a lógica multivalorada de Lógica Infinito-valorada

Gráfico F3: exemplo de conjunto fuzzy

123

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.

1

x

µ

0 30 40 50 8075 115 15060 95

devagar normal rápido

Meio-rápidoMeio-devagar

Gráfico F4: conjuntos fuzzy descrevendo velocidade

124

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.

Por que se usa 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;

Aplicações da Lógica Fuzzy

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)

125

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.

Estrutura de um programa Fuzzy

126

120Km/h

VELOCIDADE

RAPIDO

DEVAGAR

NORMAL

MEIO RAPIDO

MEIO DEVAGAR

REGRASREGRAS

FUZZYFUZZY

PRESSÃO DAACELERAÇAO

FUZZIFICAÇÃO PROPAGAÇÃO DE-FUZZIFICAÇÃO

10PSI

MAXIMA

MEDIA

MINIMA

VARIÁVEIS REGRAS VARIÁVEISFUZZY FUZZY FUZZY

Exemplo (viagem de carro)

127

Existem muitas ferramentas especializadas para o desenvolvimento de programas usando fuzzy, entre elas o FLINT (Fuzzy Logic Inference Toolkit), para o Win-Prolog.

Ferramentas para 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)

128

\ [A, B] descida de rampa/ [A, B] subida de rampa/\ [A, B, C] triângulo para cima\/ [A, B, C] 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

Qualificadores de variáveis Fuzzy

Exemplos de Qualificadores

A B

Exemplo de subida de rampa (símbolo‘/’) com pontos A e B e curvatura linear

AC

Exemplo de descida de trapézio (símbolo‘\-/’) com pontos A, B, C e D com curvatura linear

BD

Exemplo de forma livre (representada por‘?’). Os pontos V1/M1 é um dos segmentos de reta que compoem o gráfico.

V1/M1

129

•Linear (ex: triângulos, trapézios)•Curve

•Menor que 1•Igual a 1•Maior que 1

Tipos de Curvatura

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 resultanteExpressão definida pelo usuário

Métodos de De-fuzzificação

130

Exemplo de variável fuzzy no FLINT

fuzzy_variable(velocidade) :- [0, 200]; rápido, / , linear, [ 80, 150];meio-rápido, /\, linear, [75, 95, 115];normal, /\, linear, [40, 60, 80];meio-devagar, /\, linear, [30, 40, 50];devagar, \, linear, [ 0, 40 ];peak.

Nome da variável fuzzyFaixa da variável fuzzy (opcional)

Nome do qualificador

Formas Curvatura

Pontos do gráfico

Método

de-fuzzy

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 processochamado “Propagação”

131

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 da regra fuzzy

Nome do qualificador de condição

Nome de variável de condição

Nome de variável de conclusão

Nomes de qualificador de conclusão

Exemplo de declaração de regra no FLINT

Programa exemplo

Implementando um sistema controlador de turbina

132

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, negative-small, 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.

133

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:

cold cool normal warm hot

temperature

110 165 220 275 3300

1

134


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 ].


weak low ok strong high

pressure

10 70 130 190 2500

1

135


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, 0 ];

zero, /\, linear, [ -15, 0, 15 ];

positive_small, /\, linear, [ 0, 15, 30 ];

positive_medium, /\, linear, [ 15, 30, 45 ];

positive_large, /, linear, [ 30 , 45 ];

centroid .


Negative_large

Negative_medium

Negative_small

zero

throttle

10 70 130 190 2500

1

Positive_small

Positive_medium

positive_large

136

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 * pressure -> throttle ; cold * weak -> positive_large ; cold * low -> positive_medium; cold * ok -> positive_small ; cold * strong -> negative_small ; cold * high -> negative_medium; cool * weak -> positive_large ; cool * low -> positive_medium; cool * ok -> zero ; cool * strong -> negative_medium;

(continuna na próxima página).

137

(continuação da matriz de regras)

cool * high -> negative_medium; normal * weak -> positive_medium; normal * low -> positive_small ; normal * ok -> zero ; normal * strong -> negative_small ; normal * high -> negative_medium; warm * weak -> positive_medium; warm * low -> positive_small ; warm * ok -> negative_small ; warm * strong -> negative_medium; warm * high -> negative_large ; hot * weak -> positive_small ; hot * low -> positive_small ; hot * ok -> negative_medium; hot * strong -> negative_large ; hot * high -> negative_large .

Definindo as Regras Fuzzy (Continuação)

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).

138

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.

139

Entrada e Saída


Outros Exemplos

Operadores e Listas



Linguagem PROLOG


Lógica Fuzzy

Exercícios

140

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 pelomenos cinco estruturas do tipo :

livro( nome(‘C completo’), autor(‘Schildt’),pal_chave([linguagemc, programacao, computacao]))

141

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 depalavras chave, encontrar nome e autor dos livros quetem pelo menos uma das palavras chave fornecidas. Oslivros 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 ímparde 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 predicadosdo exercício anterior?

7. Defina o predicado between(N1, N2, L), tal que, paradois números inteiros dados N1 e N2, guarde na lista Ltodos os valores X tal que N1 <= X <= N2.

142

8. Escreva um programa Prolog que possa responder a seguinte pergunta : “Eu sou meu próprio avô?”, criandoum conjunto de relações que representem a seguintesituação :

“Eu me casei com uma viúva(W) que tem uma filhaadulta(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 enteadatornou – se minha madrasta. Alguns meses depois,minha mulher teve um filho(S1), que se tornou cunhadodo 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 oexemplo da regra de Fibonacci recursiva. Procure deixarbem 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 executebusca em profundidade. Dica : É necessário apenas umapequena modificação no algoritmo de busca em largura.

11. Faça, sem olhar em slides anteriores, um programaProlog 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.

143

13. Considere o seguinte problema :

“Um fazendeiro está na margem norte de um rio comuma 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 loboe a cabra ficarem sozinhos numa margem, o lobo comeráa cabra. Se a cabra e o repolho ficarem sozinhos em umamargem, a cabra comerá o repolho. Como transportarcom 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.

Documents

1 Universidade Federal de São Carlos Departamento de Computação Programação Lógica Prof. Dr. Antonio Francisco do Prado e-mail: [email protected]