PROLOG - Experimentos Iniciais com Programação em Lógica

Material de apoio:

RESOLUCAO: Provador de Teoremas Utilizando Resolução.

Neste projeto será implementado um provador de teoremas para a lógica proposicional, utilizando uma estratégia de resolução. As premissas e o teorema serão fornecidos pelo usuário, já na forma clausal. A estratégia de resolução será implementada através de busca em grafos, tanto em profundidade, quanto em largura. O software resultante desse projeto deverá permitir uma análise empírica das vantagens e desvantagens da utilização de busca em largura ou profundidade. Para isso, deverão ser apresentadas gráficamente as árvores de busca geradas durante a demonstração de um teorema.

Exemplo de Entrada:

Premissas: {t},{t',q'},{q,s'}
Teorema: {s'}

Exemplo de Saída:

                                                  Busca em Largura:

                                               {{t},{t',q'},{q,s'},{s}}

      {{q'},{q,s'},{s}}[R 1,2]                 {{t},{t',s'},{s}}[R 2,3]                      {{t},{t',q'},{q}} [R 3,4]

{{s'},{s}}[R 1,2]   {{q'},{q}}[R 2,3]      {{s'},{s}}[R 1,2]   {{s'},{s}} [R 2,3]      {{q'},{q}}[R 1,2]   {{t},{t'}} [R 2,3]

{{}}[R 1,2] 
                                                Busca em Profundidade:

                                               {{t},{t',q'},{q,s'},{s}}

      {{q'},{q,s'},{s}}[R 1,2]                   

{{s'},{s}}[R 1,2]   

{{}}[R 1,2] 

Autores:

Bruno Brandoli Machado - bmachado@ec.ucdb.br

Jonathan Andrade Silva - jsilva@ec.ucdb.br

Wesley Nunes Gonçalves - wnunes@ec.ucdb.br

EDG : Estruturas de Dados para Representação de Grafos

Considerações em relação à representação por matrizes de adjacências:
(1) - Utilizar o número -1 para indicar inexistência de aresta.
(2) - Em caso de arestas múltiplas, armazenar apenas a de menor valor.

Formato do arquivo de entrada:

Linha 1 - Nome do Grafo
Linha 2 - VG
Linha 3 ... n - Nome de cada vértice
Linha n+1 - AG
Linha n+2 ... - Arestas expressas através da seguinta tripla (vértice de origem, vértice de destino, valor)

Exemplo 1 - Entrada:
Grafo Konisberg
VG
M1
M2
I1
I2
AG
M1 I1 35
M1 I2 10
M1 I2 20
M2 I1 30
M2 I2 15
M2 I2 10

Saida: (Sugestão)

Grafo Konisberg - lista de adjacências

M1 -> [I1,35] -> [I2,10] -> [I2,20]
M2 -> [I1,30] -> [I2,15] -> [I2,10]
I1 -> [M1,35] -> [M2,30]
I2 -> [M1,10] -> [M1,20] -> [M2,15] -> [M2,10]

Matriz de adjacências
        M1   M2   I1   I2
       +------------+
M1  | -1    -1    35  10 |
M2  | -1    -1   30   10 |
I1    | 35    30   -1   -1 |
I2    | 10    10   -1   -1 |
       +------------+

Informações adicionais sobre o grafo
delta = 2
Delta = 4
O grafo é não simples, não regular e não Euleriano.

// Apresentar um menu para que o usuário possa obter informações sobre vizinhos.

CM : Caminho Mínimo

Links Auxiliares: