Livro texto

Prolog interativo

Continuando prolog basico

vamos assumir o banco de dados

parent(alberto,beatriz).
parent(alberto,carlos).
parent(alberto,zeca).
parent(denise,beatriz).
parent(denise,zeca).
parent(elisa,carlos).
parent(beatriz,flavio).
parent(gustavo,flavio).

a primeira definição de (meio) irmao - pelo menos um parent em comum (neste caso o Z).

     irmao(X,Y) :- parent(Z,X),parent(Z,Y).

testando

      ?- irmao(beatriz,K).

respostas

K = beatriz
K = carlos
K = zeca

beatriz é meio irmã de beatriz? Sim segundo a definição, mas claramente queremos pessoas diferentes.

• so por que as variaveis X e Y tem nomes diferentes não significa que elas vao ter valores diferentes,
• por outro lado as variaveis X que aparecem na regra “são todas a mesma variável”
• precisamos uma definição/operação para diferente

o =

a operação = em prolog é a operação de unificação que dicutimos ate agora

pedro = antonio      -> falha
X = antonio          -> da certo e X passa a valer  antonio
antonio = X          ->  da certo e X passa a valer antonio
antonio = X, X = Y   -> da certo e X e Y valem anotonio
X = Y                -> da certo e X e Y terao o mesmo valor (quando um assumir um )
X = Y, Y = antonio, X = pedro   -> falha

unificação é uma mistura de teste de igualdade e atribuição (bidirecional)

o not +

Negaçao em prolog é complicada pois não há boleanos. Um predicado nao retorna True, e um not não transforma esse valor para False.

Negação em prolog indica se o predicado de dentro deu ou não certo. negation by failure

       not p(..)     ou \+ p(..)  
       

vai dar certo, se p(...) falhar

       \+ ( p(..), q(..) )

vai dar certo se (p(..),q(..) ) falhar

irmao

     irmao(X,Y) :- parent(Z,X), parent(Z,Y), \+ X=Y.
     

irmao cheio

        irmao_cheio(X,Y) :- parent(Pai,X), parent(Pai,Y),
                            parent(Mae,X), parent(Mae,Y),
                            \+ Mae = Pai,
                            \+ X=Y.

Avô

dado o predicados pai(a,b) se a é pai de b, e mae(a,b)

      avo(A,N) :- pai(A,Mae), mae(Mae,N).
      avo(A,N) :- pai(A,Pai), pai(Pai,N).

duas regras.

o ; ou

o ; é o operador ou.

   a(..), b(..), ( c(..) ; d(..) ).
   

vai tentar provar a depois b e depois c .

Se c falhar, ele vai tentar d antes de dar o backtraking.

Avo pode ser escrito com o ;

     avo(A,N) :- pai(Avo,X), ( mae(X,N) ; pai(X,N) ).

Descendente https://en.wikibooks.org/wiki/Prolog/Recursive_Rules

      descende(X,Ansestral) :- parent(Ansestral,X).
      descende(X,Ansestral) :- parent(Ansestral, Filho), descende(X,Filho).

Coloque o caso base antes.

o caso recursivo tambem poderia ser escrito como

      descende(X,Ansestral) :- parent(PAI, X), descende(PAI,Ansestral).

mas evite colocar a predicado recursivo antes

    NAO FACA
      descende(X,Ansestral) :- descende(PAI,Ansestral), parent(PAI, X),

próxima aula: números e listas. Ai vamos começar a fazer coisas “mais parecidas com programas tradicionais”

Exercícios

suponha que nos temos um predicado v(v1) que indica que v1 é um vertice num grafo e a(v1,v2) que indica que há uma aresta direcionada de v1 para v2

Implemente:

• fonte(V) se V é um vertice que aponta para outros vertices e ninguém aponta para ele

• boafonte(V) é uma fonte que aponta para pelo menos 2 vertices. Use o predicado fonte definido antes (para tornar o código mais simples)

• isolado(V) se é um vertice sem arestas saindo ou chegando

• reciproco(X,Y) se X aponta para Y e Y aponta para X

• balanceado(V) se V é reciproco com todos os seus vizinhos. Esse é mais difícil. Nao temos como dizer “para todos” em prolog. Mas podemos dizer que nao é verdade (\+) que existe um nao-reciproco. Para mostrar que algo falha, o Prolog precisa tentar tudo (usando backtracking) e isso numa certa forma equivale (ou é o dual de) “para todos”. Se todos sao P então nao existe nenhum que seja nao-P, ou seja, nao-P deve falhar, e \+ nao-P deve dar certo!

Voce poderá se sentir tentado a descrever alguns/todos algoritmos em grafos como expressões em lógica. Por exemplo, a existencia de um caminho entre 2 vertices é um predicado recursivo. Um grafo é conexo se existe um caminho entre todos os pares de vertices (para grafos não-direcionados), e isso pode ser escrito como um predicado em prolog (usando a dupla negação acima). Mas isso é um erro. Algoritimos em grafos sao inteligentes para se lembrar de tudo que podem a cada visita a um vertice. O prolog “nao se lembra de nada” que ele ja fez. Verificar que nao existe um caminho entre v1 e v2 significa tentar todas as possibilidades, que torna o problema exponencial.