Relações Transitivas em 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!