Substituição de variaveis por constantes em expressões lógicas de 1ª ordem

[taviroquai]

Olá a todos,

Estou a desenvolver uma coisinha que parece simples mas penso seja muito poderosa...

Preciso de um algoritmo que receba como input expressões lógicas e quando efectuar uma query, me devolva um conjunto de soluções.

O exemplo mais simples:

Input 1: "x is mortal if x is man"

Input 2: "Socrates is man"

Até aqui não devolve nada.

A palavra reservada "if" serve de operador "=>"

A palavra reservada "is" serve de construtor de uma relação P(x) que vem a ser uma formula bem-formada na Lógica de 1ª ordem, em que "x is y" se traduz em y(x) para um termo unário, e "x is y z" se traduz em y(x, z) para termos binários.

Input 3: "Socrates is mortal ?"

Aqui devolve "true" ou "false"

O lógico seria definir o construtor de igualdade "=" e dar um 3º input do tipo: "x = Socrates" para que ele efectuasse a substituição directa no 1º input.

Estou a usar grafos acíclicos directos para estruturar as expressões, portanto, todos os inputs ficam numa arvore em que os nós são ANDs para mergir as árvores de cada input.

Sem uso de variáveis, eu faço uma busca na árvore final por uma subarvore com equivalência ao 2º input e mediante a operação lógica if consigo devolver "true".

Com o uso de variáveis penso que tenho que aplicar uma estratégia de resolução, por exemplo uma brute force para testar cada subarvore com os valores constantes, neste caso, Socrates é uma constante que "cabe" em x, dados ambos terem a mesma relação P(x): Mortal(x) e Mortal(Socrates).

Isto em Prolog é quase directo, mas gostava de conhecer um algoritmo que fizesse este tipo de busca, substituição e operação lógica, usando um grafo directo acíclico, ou arvore.

Sei fazer a estrutura, substituição e operação, mas como crio uma estratégia para testar as variáveis das relações contra as constantes desse mesmo tipo de relações?

Espero ter me explicado bem...

[Warrior]

Percebi o que queres fazer, não percebi o que já fizeste.

Posso-te explicar a forma como eu modelava o problema, parece-me ligeiramente diferente da tua:

Comecei por pensar em modelar o problema como um grafo, tal como tu, mas as relações binárias complicam a propagação de "atributos".

Eu faria o seguinte: mantinha um conjunto de atributos, e de todas as formas de eles serem gerados. Por exemplo:

((Mortal,Man), (Man), (VejoSol,(NaoNuvens,Dia),Espaco))

Isto pode representar que se for Man, é Mortal, que para ser Man é preciso ser definido como tal à nascença (não depende de nada) e que para ver o sol, ou não à nuvens e é de dia, ou estou no espaço.

Agora, para fazer uma pesquisa:

Começo com um dado elemento e os atributos que ele possui.

Enquanto existirem alterações nos seus atributos, percorro todos os atributos que ele ainda não possuir. Se uma das condições se verificar, adiciono esse atributo. No final, acabo com todos os atributos de um dado elemento.

Isto dá uma complexidade de O(V*max(V,R)) sendo V os atributos e R as relações, se implementado convenientemente.

Acredito que seja possível adaptar isto que referi num grafo e usar um algoritmo qualquer standard, mas assim de repente não estou a ver.

Possivelmente implica adicionar "dummy node" para lidar com as relações binárias, ou então já chegaste à sua estruturação e eu não percebi o que disseste.

[taviroquai]

((Mortal,Man), (Man), (VejoSol,(NaoNuvens,Dia),Espaco))

Isto pode representar que se for Man, é Mortal, que para ser Man é preciso ser definido como tal à nascença (não depende de nada) e que para ver o sol, ou não à nuvens e é de dia, ou estou no espaço.

Percebi o teu modelo mas parece-me que te faltava definires as relações lógicas AND, OR etc... e como estruturar os atributos com variáveis.

O que estou a tentar desenvolver deve permitir variáveis no input, e desta forma, possibilitar vários conjuntos de output, se não houver apenas um conjunto, ou não houver solução (conjunto vazio).

Outro exemplo:

"Existem duas pessoas. Estas duas pessoas não são iguais. Existem duas cadeiras. Estas duas cadeiras não são iguais. Se um pessoa se sentar numa cadeira, a outra pessoa não se pode sentar nessa cadeira"

Usando as palavras reservadas (relações predefinidas) IS, OR, AND, IF, ONLYIF, EQUAL, o input deverá ser:

x IS person AND y IS person AND w IS chair AND z IS chair

x IS NOT EQUAL y AND z IS NOT EQUAL w

x IS sit w IF ( x IS NOT sit z IF y IS sit z )

A seguir dou duas pessoas e duas cadeiras (ou posso dar só uma cadeira ou só uma pessoa...):

Manel IS person

Maria IS person

CadeiraAzul IS chair

CadeiraVerde IS chair

NOT ( Manel IS equal Maria )

NOT ( CadeiraAzul IS equal CadeiraVerde )

e digo que o Manel está sentado na CadeiraVerde:

Manel IS sit CadeiraVerde

Isto tudo traduzido para formulas de 1º ordem é:

Person(x) AND Person(y) AND Chair(z) AND Chair(w)

NOT equal(x, y) AND NOT equal(z, w)

(sit(z, z) => NOT sit(x, z)) => sit(x, w)

e ainda tenho que lhe dar a condição de que se existe uma pessoa então essa pessoa está sentada numa cadeira:

person(x) AND chair(w) => sit(x, w)

O algoritmo deverá verificar todas as combinações das relações possíveis, e devolver as combinações em que não existem "duvidas" ou seja relações que tenham como resultado "true". As relações com variáveis, à partida, podem ter os valores "true" ou "false" enquanto que as relações com constantes só tem o valor "true".

Se perguntar:

"Manel IS sit CadeiraAzul ?"

Deve devolver "false", porque se está sentado na cadeira verde não pode estar sentado na cadeira azul e só outra pessoa pode estar sentada na cadeira azul!

Se perguntar:

"Maria IS sit CadeiraAzul ?"

Deve devolver "true" pela mesmo conjunto de relações definidos anteriormente.

Outro exemplo sem variáveis:

Manel IS man AND NOT ( Manel IS man )

true AND false

false

Devolve "false"

O problema é arranjar um algoritmo que substitua (e verifique se possível) TODAS as relações com variáveis pelas respectivas relações com constantes!

Estarei a tentar fazer um interpretador do tipo ProLog?!?!? Ai maezinha...

[Warrior]

Sim, estás. Essa ideia das variáveis parece-me algo como herança de classes, o manuel pode herdar as características das pessoas.. Atenção que se pode fazer, mas é algo que dá trabalho.

[taviroquai]

Está aqui um interpretador do tipo Prolog desenvolvido em Pascal

http://www.csse.monash.edu.au/~lloyd/tildeLogic/Prolog.toy/

Eu vou tentar fazê-lo em Java... uma coisinha destas é super útil para resolver problemas lógicos como os encontrados neste site http://www.puzzlersparadise.com/page1034.html ou uma outra aplicação mais seria, investigação criminal.

Obrigado pela ajuda  🙂

[Warrior]

Há vários, lembro-me de ser usado um nas aulas teóricas de matemática discreta.

[MX+]

Estás a querer fazer algo que o prolog já faz por ti, só tens é de converter as tuas frases:

Já traduziste as frases para lógica de primeira ordem, mas os teus "objectivos" (perguntas) não estão traduzidas. O prolog já é muito bom a fazer isto:

Se perguntar:

"Manel IS sit CadeiraAzul ?"

Sit(Manel, CadeiraAzul).

Se perguntar:

"Maria IS sit CadeiraAzul ?"

Sit(Maria, CadeiraAzul).

Acho que não deves dar-te ao trabalho de estar a reprogramar algo só para resolver esses problemas. Deixo aqui um PDF do Prof. Pavão (IST) que fala exatamente sobre problemas parecidos aos apresentados no site.

http://www.scribd.com/doc/3279445/Capitulo5 (Pag 34)

Espero que ajude.

[taviroquai]

Obrigado MX+, o pdf é muito bom e já estive a ler mais umas coisinhas sobre interpretadores do tipo prolog...

Parece que a resposta que procuro está no algoritmo de unificação que o prolog usa. Este algoritmo de unificação usa uma árvore de clausulas... alguém sabe como funciona este algoritmo e podia expor aqui em pseudo-codigo?

Ainda não consegui entender bem...

[Baderous]

Parece que a resposta que procuro está no algoritmo de unificação que o prolog usa. Este algoritmo de unificação usa uma árvore de clausulas... alguém sabe como funciona este algoritmo e podia expor aqui em pseudo-codigo?

Ainda não consegui entender bem...

Não sei se será isto:

[taviroquai]

É isso mesmo... apartir desse texto dá para construir um pseudo-codigo... vou tentar  ?