prolog

Uma relação transitiva é aquela em que, se r(x,y) e r(y,z) são verdadeiras, então r(x,z) também é verdadeira. Em Prolog, podemos modelar relações transitivas de forma elegante usando recursão, permitindo navegar por cadeias de relacionamentos como ancestralidade, hierarquias e conexões em grafos.

O que é uma Relação Transitiva?

Formalmente, uma relação R é transitiva se:

Por exemplo, se “x é pai de y” e “y é pai de z”, então “x é avô de z”. A relação “ancestral” é o fecho transitivo da relação “pai”.

Programa 4.3: Ancestral

Vamos construir uma base de fatos sobre relações familiares e definir a regra ancestral/2:

Estrutura da Regra Ancestral

A regra ancestral/2 tem dois componentes:

1. Caso base: ancestral(X, Y) :- pai(X, Y). — X é ancestral direto de Y (pai).
2. Passo recursivo: ancestral(X, Y) :- pai(X, Z), ancestral(Z, Y). — X é ancestral de Y se existe um intermediário Z, onde X é pai de Z e Z é ancestral de Y.

Diagrama da Árvore Genealógica

Visualize a estrutura familiar:

Fluxo de Execução: ancestral(X, enos)

Quando consultamos ?- ancestral(X, enos)., o Prolog busca todos os ancestrais de Enos:

Resultado: X = seth ; X = adao ; false.

Navegando pela Árvore

O Prolog navega pela árvore genealógica da seguinte forma:

Programa 4.4: Acima (Relação Espacial)

Agora, um exemplo diferente: objetos empilhados uns sobre os outros.

Diagrama da Relação “Acima”

Visualize a pilha de objetos:

Consultas com Acima

1. Quem está acima de a?

2. Quem está abaixo de d?

Recursão “Para Frente” e “Para Trás”

Observe a diferença na direção da recursão:

• Ancestral (para cima): ancestral(X, Y) :- pai(X, Z), ancestral(Z, Y).
  Percorre a árvore para cima (dos mais novos para os mais velhos).
• Descendente (para baixo): Se quiséssemos encontrar descendentes, faríamos:
  descendente(X, Y) :- pai(Y, X). (base)
  descendente(X, Y) :- pai(Y, Z), descendente(X, Z). (passo)
  Percorre a árvore para baixo (dos mais velhos para os mais novos).

A direção da recursão é determinada por onde colocamos a variável fixa na chamada recursiva.

Exercícios Propostos

1. Descendente: Implemente descendente(X, Y) que é verdadeiro se X é descendente de Y (filho, neto, bisneto, etc.). Use a base de fatos pai/2.
2. Irmãos: Implemente irmao(X, Y) que é verdadeiro se X e Y têm o mesmo pai.
3. Primos: Implemente primo(X, Y) que é verdadeiro se X e Y são primos (têm um ancestral em comum, mas não são irmãos).
4. Caminho em grafo: Dada uma base de fatos aresta(X, Y), implemente caminho(X, Y) que é verdadeiro se existe um caminho de X até Y.
5. Desafio: Implemente parente(X, Y) que é verdadeiro se X é parente de Y (ancestral ou descendente). Dica: use a união de duas regras.

Conclusão

As relações transitivas são um dos usos mais poderosos da recursão em Prolog. Com apenas algumas linhas de código, podemos modelar:

• Árvores genealógicas (ancestralidade, descendência)
• Hierarquias espaciais (acima, abaixo, dentro)
• Grafos (caminhos, conexões)
• Redes de dependência (pré-requisitos, requisitos)

A elegância da solução está na simplicidade da definição: uma regra base e uma regra recursiva que “anda” pela relação. O Prolog cuida do resto — navegando pela árvore, encontrando todos os caminhos e retornando as soluções uma a uma.

A chave para dominar relações transitivas é entender a direção da recursão: a posição da variável fixa determina se você está subindo ou descendo na hierarquia. Pratique com os exercícios e explore as infinitas possibilidades que essa técnica oferece!

A recursividade é um dos conceitos mais fundamentais e poderosos da programação — e em Prolog, ela é ainda mais natural, pois a linguagem foi projetada para suportar definições recursivas de forma elegante. O princípio é simples: resolver um problema usando uma instância menor (mais simples) dele mesmo. Para que isso funcione, precisamos de dois elementos essenciais: um caso base (que para a recursão) e um passo recursivo (que reduz o problema e chama a si mesmo).

Exemplo Matemático: Potência (Programa 4.1)

Vamos calcular potência: B^N (base elevada ao expoente). Sabemos que:

• Caso base: B^0 = 1 (qualquer número elevado a 0 é 1).
• Passo recursivo: B^N = B * B^(N-1) (para N > 0).

Estrutura de um Predicado Recursivo

Observe a estrutura:

1. Caso base: pot(_, 0, 1). — a condição mais simples, que não chama a si mesmo.
2. Passo recursivo: pot(B, N, P) :- N > 0, M is N-1, pot(B, M, R), P is B * R. — reduz o problema (N diminui), chama recursivamente e depois combina o resultado.

A guarda N > 0 garante que a recursão não seja chamada com expoente negativo, evitando loops infinitos.

Fluxo de Execução: pot(2, 3, P)

Veja como o Prolog processa a consulta passo a passo:

Interpretação:

• O Prolog expande as chamadas recursivas até atingir o caso base.
• Depois, retorna os resultados de baixo para cima, combinando os valores.
• No final, P é unificado com 8 (que é 2^3).

Exemplo do Fatorial (Programa 4.2)

O fatorial é outro exemplo clássico:

A estrutura é idêntica à da potência: um caso base (0! = 1) e um passo recursivo que reduz N até chegar a 0.

Fluxo para fat(3, F):

A Hipótese da Recursividade

Ao escrever um predicado recursivo, você faz uma suposição fundamental: assumir que a chamada recursiva funciona corretamente para uma instância menor do problema. Essa é a hipótese da recursividade. No caso da potência, assumimos que pot(B, M, R) realmente calcula B^M corretamente, e então usamos esse resultado para calcular B^N. Essa confiança na chamada recursiva é o que torna a recursão poderosa e elegante.

Importante: A condição de parada (caso base) é obrigatória para evitar recursão infinita. Sem ela, o Prolog entraria em um loop até estourar a pilha de chamadas. A guarda N > 0 no passo recursivo garante que nunca chamaremos pot com um expoente negativo.

Exercícios Propostos

1. Fibonacci: Implemente fib(N, F) que calcula o N-ésimo termo da sequência de Fibonacci (F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2)). Use dois casos base.
2. Soma de lista: Implemente soma_lista([], 0). e soma_lista([H|T], S) :- soma_lista(T, R), S is H + R.
3. Inverter lista: Crie inverter([], []). e inverter([H|T], Inv) :- inverter(T, R), append(R, [H], Inv).
4. Pertencimento: Implemente membro(X, [X|_]). e membro(X, [_|T]) :- membro(X, T).
5. Desafio: Implemente max_lista([X], X). e max_lista([H|T], M) :- max_lista(T, R), M is max(H, R).

Conclusão

A recursividade é o coração da programação lógica. Em Prolog, ela é expressa de forma natural através de regras que se referem a si mesmas, com um caso base que encerra a cadeia e um passo recursivo que reduz o problema. Esse padrão aparece em cálculos matemáticos (potência, fatorial), manipulação de listas, definição de estruturas de dados e muito mais. Dominar a recursividade é dominar o pensamento declarativo e estrutural que o Prolog exige. Pratique com os exercícios acima e explore a beleza da auto-referência lógica!

---