Formular definições para uma família representada
usando estrutura de árvores e operadores. Tome as relações
masculino, feminino e pais como básicas e defina outras com base
nestas. Defina um predicado de localização de um nó
na árvore. Suponha a base de dados abaixo:
:-op(500,xfx,’pai_de’).
a pai_de b.
a pai_de c.
.
.
.
?- localize(n).
a -> c -> h -> n.
Características Necessárias para a Resolução
O programa que resolve o problema em questão, possui as seguintes características:
:-op(prioridade,tipo,nome).
Há três grupos de tipos de operadores, sendo:
No programa familia.pro, são utilizados operadores infixos e posfixos. Os operadores infixos incluem:
:-op(500,xfx,'pai_de').
:-op(500,xfx,'ava_de').
:-op(500,xfx,'avo_de').
:-op(500,xfx,'mae_de').
:-op(500,xfx,'filha_de').
:-op(500,xfx,'filho_de').
:-op(500,xfx,'irma_de').
:-op(500,xfx,'irmao_de').
:-op(500,xfx,'tia_de').
:-op(500,xfx,'tio_de').
:-op(500,xfx,'predecessor').
:-op(500,xfx,'descendente').
Sendo que os operadores posfixos são:
:-op(500,xf,'masculino').
:-op(500,xf,'feminino').
Todos operadores, neste caso, com a mesma prioridade ("500"). Poderia utilizar-se de prioridades diferentes, entretanto neste programa não há necessidade disto, visto que não estamos tratando de um problema de ordem de expressões como a+b*4, onde a ordem é essencial para obter-se a exatidão.
Outra característica do programa familia.pro é a utilização de recursão no predicado "localize(X)". Por exemplo, para se definir a localização de um nó na árvore, devemos achar todos seus predecessores, como no exemplo da estrutura da árvore, para localizar n, temos que saber quem é pai de n, quem é pai do pai de n, e assim por diante. Desta forma, a utilização da recursividade é essencial para a formulação do predicado localize(X), de modo que seja permitido o acréscimo de novos nós na árvore sem afetar a resolução do problema.
Outro caso em que deve-se utilizar da recursão é para as definições de predecessor e descendente, onde são localizados todos os nós precedentes e descendentes de um determinado nó respectivamente.
Programa familia.pro
O programa abaixo resolve o problema em questão.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
Adriana Molina Centurion
%
% Primeiro trabalho
prático da disciplina I.A.
%
%
FAMILIA.PRO
%
% Este programa tem como objetivo formular definições
para
%
% uma família representada usando estrutura
de arvores
%
% e operadores. O programa define relações pais ("pai_de"),
masculino
%
% ("masculino"), feminino ("feminino") como relações
básicas, e constrói
%
% outras relações com base nessas relações,
sendo % elas: avô ("avo_de"), %
% avó ("ava_de"), mãe ("mae_de"), filha ("filha_de"),
filho ("filho_de"),
%
% irmã ("irma_de"), irmão ("irmao_de"), tia ("tia_de"),
tio("tio_de"),
%
% predecessor ("predecessor"), descendente ("descendente").
%
% Porem, a meta principal deste programa é a localização
de um de um nó %
% na arvore. Desta forma o programa define um predicado de localização
%
% ("localize(X)"), onde dado um elemento X, a arvore e pesquisada e
%
% é dada a localização de X na árvore.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definição do operador infixo pai_de (x pai_de x).
:-op(500,xfx,'pai_de').
% Definição do operador posfixo masculino (x masculino).
:-op(500,xf,'masculino').
% Definição do operador posfixo feminino (x feminino).
:-op(500,xf,'feminino').
% Definição do operador infixo ava_de, ou seja, avó
(x ava_de x).
:-op(500,xfx,'ava_de').
% Definição do operador infixo avo_de, ou seja, avô
(x avo_de x).
:-op(500,xfx,'avo_de').
% Definição do operador infixo mae_de (x mae_de x).
:-op(500,xfx,'mae_de').
% Definição do operador infixo filha_de(x filha_de x).
:-op(500,xfx,'filha_de').
% Definição do operador infixo filho_de(x filho_de x).
:-op(500,xfx,'filho_de').
% Definição do operador infixo irma_de(x irma_de x).
:-op(500,xfx,'irma_de').
% Definição do operador infixo irmao_de(x irmao_de x).
:-op(500,xfx,'irmao_de').
% Definição do operador infixo tia_de(x tia_de x).
:-op(500,xfx,'tia_de').
% Definição do operador infixo tio_de(x tio_de x).
:-op(500,xfx,'tio_de').
% Definição do operador infixo predecessor(x predecessor
x).
:-op(500,xfx,'predecessor').
% Definição do operador infixo descendente(x descendente
x).
:-op(500,xfx,'descendente').
%
% Relações de pais, onde os fatos x pai_de x, significa
que um argumento x é pai de
%outro argumento x, por exemplo: a pai_de b, significa que a é
pai de b.
%
a pai_de b.
a pai_de c.
a pai_de d.
b pai_de e.
b pai_de f.
c pai_de g.
c pai_de h.
c pai_de i.
d pai_de j.
e pai_de k.
f pai_de l.
f pai_de m.
h pai_de n.
i pai_de o.
i pai_de p.
j pai_de q.
j pai_de r.
j pai_de s.
m pai_de t.
%
% Relações que definem o sexo feminino ou masculino.
Onde x feminino significa que o
%argumento x é feminino, e x masculino, significa que o argumento
x é masculino. Ex: e
%feminino -> o nó e é feminino.
%
c feminino.
e feminino.
h feminino.
i feminino.
j feminino.
k feminino.
l feminino.
s feminino.
t feminino.
b masculino.
d masculino.
f masculino.
g masculino.
m masculino.
n masculino.
o masculino.
p masculino.
q masculino.
r masculino.
%
%Relação que determina qual nó é avó
de um determinado nó. Para isso, a avó X deve
%ser pai de Z, Z por sua vez deve ser pai de Y e X deve ser feminino.
%
X ava_de Y:- X pai_de Z, Z pai_de Y, X feminino.
%
%Relação que determina qual nó é avô
de um determinado nó. Para isso, o avó X deve
%ser pai de Z, Z por sua vez deve ser pai de Y e X deve ser masculino.
%
X avo_de Y:- X pai_de Z, Z pai_de Y, X masculino.
%
% Relação que determina qual nó é mãe
de um determinado nó. Para isso, a mãe X deve ser pai de
Y, e X deve ser feminino.
%
X mae_de Y:- X pai_de Y, X feminino.
%
% Relação que determina qual nó é filha
de um determinado nó. Para isso, a Y deve
%ser pai de X, e X deve ser feminino.
%
X filha_de Y:- Y pai_de X, X feminino.
%
% Relação que determina qual nó é filho
de um determinado nó. Para isso, a Y deve
%ser pai de X, e X deve ser masculino.
%
X filho_de Y:- Y pai_de X, X masculino.
%
% Relação que determina qual nó é irmã
de um determinado nó. Para isso, Z deve ser
%pai de X, como também pai de Y, X deve ser feminino e X deve
ser diferente de Y,
%para que X seja irmã de Y.
%
X irma_de Y:- Z pai_de X, Z pai_de Y, X feminino, X\==Y.
%
% Relação que determina qual nó é irmão
de um determinado nó. Para isso, Z deve ser
%pai de X, como também pai de Y, X deve ser masculino e X deve
ser diferente de Y,
%para que X seja irmão de Y.
%
X irmao_de Y:- Z pai_de X, Z pai_de Y, X masculino, X\==Y.
%
% Relação que determina qual nó é tia de
um determinado nó. Para isso, Z deve ser
%pai de Y e X deve ser irmã de Z, para que X seja tia de Y.
Note que este predicado
%utiliza o predicado acima "irma_de". Isto poderia também ser
feito da seguinte forma:
%X tia_de Y:- Z pai_de U, Z pai_de X, U pai_de Y, X feminino.
%
X tia_de Y:- Z pai_de Y, X irma_de Z.
%
% Relação que determina qual nó é tio de
um determinado nó. Para isso, Z deve ser
%pai de Y e X deve ser irmão de Z, para que X seja tio de Y.
Caso semelhante ao
%anterior ("tia_de").
%
X tio_de Y:- Z pai_de Y, X irmao_de Z.
%
%Relação que determina qual nó é predecessor
de um determinado nó. Para isso, temos
%duas regras: uma para predecessores diretos e uma para predecessores
indiretos (as
%regras são escritas juntas.
% X é predecessor de Y se X for pai de Y.
X predecessor Y :- X pai_de Y.
% X é predecessor de Y se há um Z a qual X é pai
de Z e Z é predecessor de Y.
X predecessor Y :- X pai_de Z,Z predecessor Y.
%
%Relação que determina qual nó é descendente
de um determinado nó. Para isso, temos
%duas regras: uma para descendentes diretos e uma para descendentes
indiretos (as
%regras são escritas juntas.
% X é descendente de Y se Y for pai de X.
X descendente Y :- Y pai_de X.
% X é descendente de Y se há um Z a qual Y é pai
de Z e X é descendente de Z.
X descendente Y:- Y pai_de Z, X descendente Z.
%
% Relação que determina a localização de
um determinado nó na árvore. Para isso temos
%duas regras: a primeira para localizar os nós anteriores de
um dado nó e a segunda é
%utilizada quando um nó não tem pai, ou seja, a raiz.
Isso é necessário pois ao percorrer
%o caminho de localização de um nó (de baixo para
cima), ao chegar no nó raiz o
%programa não ira encontrar nenhum pai do nó raiz, e
portanto ele deve parar a pesquisa.
%
% primeira regra: utiliza recursão para rastrear a árvore
e encontrar sua localização. Para %localizar X, se Y pai
de X entao localize Y.
localize(X) :- Y pai_de X, localize(Y), write(' -> '), write(X).
% segunda regra: se X não tem pai, ira entrar nesta regra e
escrever o nome do nó. Por %exemplo o nó a.
localize(X) :- write(X).
Caso de Testes
Abaixo são apresentadas os testes feitos com o programa familia.pro.