Paradigma de Programação Lógico

Links relacionados: Linguagens de Programação

Introdução

Em 1958, MacCarthy propôs a ideia de programas que pudessem manipular sentenças baseadas em uma linguagem formal (tal como o cálculo de predicados), ou seja, o programa deve formular conclusões com base de um conjunto de premissas. Essas conclusões poderiam ser tanto declarativas quanto imperativas.

O objetivo da programação lógica é poder programar um computador utilizando um estilo de linguagem semelhante à lógica matemática. Matemáticos e filósofos encontram na lógica uma ferramenta eficaz para desenvolvimento de teorias. Vários problemas são naturalmente expressos como teorias. Dizer que um problema precisa de solução frequentemente equivale a perguntar se uma nova hipótese é consistente com uma teoria existente ou se é conseqüência dela. A lógica proporciona uma maneira de demonstrar se uma questão é verdadeira ou falsa.

O processo de construir uma demonstração é bem conhecido, portanto a lógica é um meio confiável de responder perguntas. Sistemas de programação lógica automatizam este processo. A inteligência artificial teve uma influência importante no desenvolvimento da programação lógica.

Exemplo

Observe o processo de verificação do seguinte argumento:

Se houve um assassinato, então Samanta é uma suspeita do crime. Samanta será interrogada se e somente se ela for suspeita do crime. Se Samanta ou Marcos forem interrogados, então teremos uma pista. Portanto, se ouve um assassinato e Ricardo e Jonas estiverem investigando, então teremos uma pista.

Primeiro, separa-se os predicados e dá-se um apelido para ele. Por exemplo, "Houve um assassinato" é representado pela letra A.

A: Houve um assassinato.
S: Samanta é suspeita do crime.
I: Samanta ser interrogada.
M: Marcos ser interrogado.
P: Ter uma pista.
R: Ricardo estar investigando.
J: Jonas estar investigando.

Em seguida, transforma o argumento acima em uma forma compacta:

A->S, I<->S, (IvM)->P |- (A^(R^J))->P

Por fim, executa o cálculo lógico:

PREMISSAS     REGRAS UTILIZADAS
1) A->S       [P: Premissa]
2) I<->S      [P: Premissa]
3) (IvM)->P   [P: Premissa
4) A^(R^J)    [PC: Prova do Condicional
5) A          [^E4: Eliminação da conjunção (^) da premissa 4]
6) S          [MP5,1: Modus Ponens nas premissas 5 e 1]
7) S->I       [<->E2: Eliminação do bicondicional (<->) da premissa 2]
8) I          [MP6,7: Modus Ponens nas premissas 6 e 7]
9) IvM        [vI8 : Inclusão da disjunção (v) na premissa 8]
10) P	      [MV9,3: Modus Ponens nas premissas 9 e 3 - CONCLUSÃO]

Ver mais sobre isso em Inteligência Artificial, mais especificamente em Introdução à Lógica.

Prolog

A linguagem de programação Prolog foi concebida por Colmerauer e Roussel em 1972. Sua utilização é direcionada para tarefas que necessitem trabalhar com representação de conhecimento e aplicações de computação simbólica, tais como banco de dados, compreensão de linguagem natural, automação de projetos, análise de estruturas bioquímicas e sistemas especialistas.

Um sistema especialista, por exemplo, realiza diagnósticos baseados na experiência humana de um especialista por meio de informações inseridas na forma uma base de conhecimentos e de regras de produção.

Características Básicas

O Prolog é baseado em Fatos que são criados pelo seguinte comando:

predicado(arg 1[,arg 2,...,arg n]).

tal que:

• predicado é a relação;
• arg i são os objetos que atuam na relação.

Por exemplo:

1amigo(joao, maria).

Dessa forma é definida uma relação de "amigo" entre os dois argumentos de entrada, joão e maria. Entretanto, também é possível haver um fato com apenas um argumento:

1homem(carlos).

Neste caso, a relação homem torna-se uma característica do objeto carlos.

Quando há mais de um argumento, a ordem da consistência é definida como sendo a última utilizada. Por exemplo:

1paga(patrao, salario, empregado).

À primeira vista, parece evidente que a relação (paga) é direta entre os dois primeiros objetos (patrao, salario) e indireta ao terceiro (empregado). Esse tipo de interpretação está dependente da ordenação dos objetos declarados nos fatos. Para manter uma coerência, é importante que todos os fatos sigam uma mesma estrutura de interpretação. Assim, no caso da relação amiga talvez fosse mais prudente a declaração bivalente:

1amigo(joana,maria).
2amigo(maria,joana).

demonstrando a relação amigo tanto no sentido do objeto joana-maria quanto maria-joana.

É importante salientar que um conjunto de fatos forma um banco de dados. Ou seja, várias afirmações compõem os dados existentes no sistema. Os fatos são a célula básica do banco de dados Prolog. sistema. Os fatos são a célula básica do banco de dados Prolog.

Questões

Existe uma certa variação em relação a sintaxe para definição de "questões" quanto ao compilador de prolog. Entretanto, uma questão é basicamente um fato antecedido por um ponto de interrogação ou comando que indique a formulação de uma questão. Com a utilização do gprolog, por exemplo:

1| ?- [user].
2compiling user for byte code...
3amigo(joao,maria).
4user compiled, 2 lines read - 256 bytes written, 20545 ms
5yes
6| ?- amigo(joao,maria).
7yes
8| ?- amigo(joao,tiao).
9no

A função da questão é basicamente testar a existência de uma relação sobre os argumentos propostos. No código acima:

• Linha 1: entra-se com "[user]." para poder adicionar uma base de dados do usuário.
• Linha 3: entra-se com a premissa de que joao é amigo de maria.
• Linha 4: pressiona-se CTRL-D para fechar a entrada de informações.
• Linha 5: verifica a questão joao é amigo de maria?
• Linha 7: verifica a questão joao é amigo de tião?

Variáveis

As variáveis são utilizadas de acordo com o comando:

1pred(arg 1,Var 1[,arg/Var 2,...,arg/Var n]).

ou

1pred(Var 1,arg 1[,arg/Var 2,...,arg/Var n]).

tal que Var é variável e deve começar com letra maiúscula.

A variável é um elemento de grande utilidade para a formulação de questões. Por exemplo:

1?- amiga(joana,Quem).
2Quem = maria

Em cima das questões com variáveis é que serão construídos os sistemas mais complexos de estruturação da representação de conhecimentos.

Conjunção

A conjunção permite a composição de fatos, formando o chamado e lógico:

1pred(arg/Var,arg/Var),pred(arg/Var,arg/Var).

A vírgula "," entre as questões determinam a validade mútua de ambas (ou do conjunto envolvido). O objetivo da conjunção é a realização de uma busca no banco de dados para a verificação da validade da questão ou busca dos objetos relacionados com os argumentos propostos. O mecanismo de busca é uma estratégia de controle do tipo busca em profundidade com retrocesso.

Assim, dados os seguintes fatos:

1amiga(joana,maria).
2amiga(clara,maria).

E a questão:

1?- amiga(joana,Quem),amiga(clara,Quem).
2Quem = maria

A consulta tem como objetivo obter o objeto (maria) que falta para validar a conjunção entre os dois objetivos. Objetivo, neste contexto, é cada um dos componentes da conjunção.

Há duas formas de validação de conjunções. A primeira ocorre caso todos os objetivos sejam fatos como, por exemplo:

1?- amiga(joana,antonia),amiga(maria,clara).
2no

todos os objetivos devem ser validados. A segunda forma ocorre, como já foi visto, caso hajam variáveis e existam correspondentes entre as variáveis dos objetivos.

Para facilitar a compreensão da construção da conjunção, ela pode ser vista como uma estrutura em árvore, onde os objetos são folhas das relações, as quais estão ligadas à questão, que torna-se a raiz da árvore. No caso da questão cujo objeto maria era a incógnita, temos como nodos filhos da raiz os predicados da relação amiga, e de cada relação partem duas folhas com os objetos. Através da varredura desta árvore podemos deduzir que a variável Quem referia-se ao objeto maria , comum em ambos objetivos, tornando, deste modo, a questão válida.

Regras

As regras são declaradas da seguinte forma:

1pred(arg/Var,arg/Var) :- pred(arg/Var,arg/Var).

Tal que o símbolo :- indica a uma condição (se) ou, no caso de compararmos com lógica de predicados, a uma implicação material.

A regra é o instrumento básico de organização do banco de conhecimentos e permite a construção de questões complexas (formas mais sofisticadas de consulta ao banco de dados). É ela que indica a validade de um conjunto de fatos, questões ou conjunções.

Para exemplificar o uso da regra, vamos inicialmente declarar alguns fatos:

1amigo(joana,maria).
2amigo(maria,joana).
3amigo(maria,clara).
4amigo(clara,maria).
5ama(joana,maria).
6ama(maria,joana).

E a regra amigo_intima:

1amiga_intima(Ela1,Ela2) :-
2   amiga(Ela1,Ela2),
3   amiga(Ela2,Ela1),
4   ama(Ela1,Ela2),
5   ama(Ela2,Ela1).

Desta forma, seria verdadeira a questão:

1?- amigo_intima(maria,joana).
2yes
3</prolog>
4
5E falsa a questão:
6
7<syntaxhighlight lang=prolog line>
8?- amigo_intima(maria,clara).
9no

Percebemos, então, que há a possibilidade de construção de produções complexas em cada regra, permitindo conceitos cada vez maiores e consultas com um maior nível de definição e de variáveis.

Disjunção

A disjunção é o oposto da conjunção, equivale ao "OU" lógico:

1pred(arg/Var,arg/Var) :- (pred(); atrib;...).

No exemplo:

1amigo(X) :- (X=maria; X=joana).

Uma consulta seria:

1?- amigo(celia).
2no

Ou:

1?- amiga(Quem).
2Quem = maria
3Quem = joana

Como podemos observar, o ponto-e-vírgula ( ; ) permite a aceitação de uma ou outra condição para a validação da cláusula, enquanto o operador de conjunção ( , ) implica na necessidade de aceitação de todas as condições.

Operadores Numéricos

Relacionais

Os operadores numéricos relacionais são aqueles usados para realizar testes quantitativos entre dois números. São eles:

=   : X é igual a Y?
\=  : X é diferente de Y?
<   : X é menor que Y?
>   : X é maior que Y?
=<  : X é menor ou igual a Y?
>=  : X é maior ou igual a Y?

Um exemplo da utilidade dos operadores relacionais:

1dentro_interv_aberto(K,X1,X2) :-
2   K > X1,
3   K < X2.

E a questão:

1?- dentro_interv_aberto(5,0,5).
2no

Como se vê, há diversas possibilidades de criação de regras matemáticas utilizando os operadores relacionais.

Aritméticos

Operadores aritméticos são os utilizados na aritmética básica:

+   : soma
-   : diminuição
*   : multiplicação
/   : divisão
mod : módulo (X mod Y)
is  : é um(a) (X is equacao)?

Por exemplo:

1ao_quadrado(X,Y) :-
2   Y is X*X.

E a questão:

1?- ao_quadrado(6,X).
2X = 36

Deste modo, percebemos que há a possibilidade de construção de diversas funções matemáticas mais complexas a partir de regras e operadores aritméticos. Há funções matemáticas mais complexas já implementadas em Prolog que serão analisadas posteriormente.

Estruturas de Dados

As estruturas de dados em prolog são declaradas da seguinte forma:

1pred(arg, estrut(atrib1,...,atrib n)).

ou

1pred(estrut(atrib1,...,atrib n), arg).

As estruturas servem para aninhar dados de forma organizada, estruturada. Elas permitem a distinção de atributos para um argumento. Um exemplo de uma estrutura simples seria:

1ficha(num,func(nome,end,cargo)).

Os átomos nome , end , cargo são os componentes da estrutura func , o que permite o armazenamento de atributos do funcionário de uma empresa, por exemplo. Mas podemos fazer mais níveis de aninhamento:

1ficha(num,func(dados_pes(nome,end),cargo(funcao,salario(basico,descontos,vantagens)))).

Nesta linha de código temos a definição de uma ficha cadastral, cuja chave é um número que permite o acesso aos dados de um funcionário: seus dados pessoais e seu cargo na empresa. Os dados pessoais resumem-se ao nome e endereço do funcionário. O cargo compõe-se da função exercida e do salário ganho. O salário é calculado em termos do vencimento básico, descontos e vantagens acumuladas.

Obviamente, este fato deve estar com os dados já preenchidos:

1ficha(001,func(dados_pes('Fulano de Tal','Rua Epa'),cargo('continuo',salario(100,30,10)))).

Assim, temos um exemplo exagerado de aplicação de estruturas Prolog. Obviamente que uma aplicação real para a produção de um sistema de gerenciamento de banco de dados teria uma maior preocupação com a clareza de distribuição dos dados, evitando o aninhamento excessivo.

Listas

A forma mais adequada para estruturação de dados em Prolog são as listas. Como o nome diz, são estruturas dinâmicas de armazenamento de dados. Elas são utilizadas na construção de vetores e matrizes dinâmicos de caracteres, números, e quaisquer outros dados utilizados. Apresentam-se na forma:

1pred([elem,...],[],[elem[elem,..],...],arg,...).

tal que elem pode ser qualquer tipo sintático.

Um conceito importante para a utilização das listas é o cabeça-corpo ( | ). Ele é usado para isolar membros de uma lista. Por exemplo, dada uma lista na forma:

1lista([a,b,c,d,e]).

Aplicando-se a questão:

1?- lista([X | Y]).
2X=a
3Y=[b,c,d,e]

Como podemos observar, o operador | permite a separação da cabeça da lista de seu corpo. Isso permite o isolamento dos membros da lista, facilitando sua análise.

As listas são tipos peculiares de estruturas de dados que também podem ser representadas através de árvores. Esse tipo de representação é muito útil quando trabalhamos com altos níveis de aninhamento. Como, por exemplo:

1ficha(123,func(dados_pes([["Silva","Fulano da"],["solteiro",0]],["rua Tal",99,301]),cargo( ["continuo"],[minimo,1]))).

Exemplo 1

Para implementarmos em prolog a verificação do seguinte silogismo lógico:

Todo homem é mortal.
Socrates é homem.
Logo, Socrates é mortal.

Devemos fazer da seguinte forma:

1| ?- [user].
2compiling user for byte code...
3homem(socrates).
4mortal(X) :- homem(X).
5user compiled, 3 lines read - 340 bytes written, 14729 ms
6(1 ms) yes
7| ?- mortal(socrates).
8yes

Temos que:

• Linha 3: socrates é homem.
• Linha 4: Se é homem, então é mortal.
• Linha 7: Estamos fazendo a seguinte pergunta: "socrates é mortal"?

Referencias

• Tutorial de Prolog