Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.
Vamos usar a programação em lógica com a finalidade de resolver problemas. Cada problema consistirá num certo número de questões referentes a certos objectos. Esses objectos verificam certas propriedades e conservam entre si certas relações. Os objectos, com as suas propriedades e relações, constituem o universo do problema.
O problema consiste em estudar as relações de parentesco. Os objectos do universo serão certos humanos.
O programa em lógica exprimirá o conhecimento que temos das propriedades e relações do universo. Ao descrevermos o universo do problema, pretendemos depois obter, de um modo automático, a solução do problema, quer dizer, as respostas às questões.
O conhecimento associado a um problema é potencialmente infinito, mas para o formular, bem como para formular as questões, deveremos utilizar recursos finitos, mais precisamente, uma linguagem lógica. Aos constituintes elementares da linguagem chamamos símbolos.
Certos símbolos são chamados de constantes. Estes são os símbolos que representam os objectos ``previligiados'' do universo. Exemplos de constantes para o Problema no 1 podem ser:
ana zulmira luis eusebio
Utilizamos também outros símbolos chamados variáveis. As variáveis são os símbolos que representam qualquer objecto do universo. Uma variável servirá numa questão, por exemplo, para representar um objecto desconhecido. Elas serão também necessárias para formular propriedades que se verificam para todos os objectos do universo. Por convenção, as variáveis serão os símbolos que começam por uma letra maiúscula. Seguem-se exemplos de variáveis para o Problema no 1:
Filho F Mae M
Constantes e variáveis são dois casos particulares de termos.
Os termos representam os objectos do universo. Contudo, um termo que é uma variável, não representa um objecto bem determinado do universo, a não ser que fixemos uma certa afectação. Uma afectação, em lógica, é uma função que associa (``afecta'') uma variável a um objecto fixo do universo, ao qual chamamos então de valor da variável por essa afectação.
Um termo que é uma constante, tem também um valor, valor esse independente de toda a afectação: é sempre o objecto do universo representado por essa constante. Por exemplo, o termo ana tem por valor uma rapariga, ou uma senhora, bem determinada (pressupondo a linguagem bem escolhida...).
É importante notar que os objectos do universo não são necessariamente todos os valores das constantes. Por exemplo, para o nosso problema no 1, podem existir humanos que não têm o ``privilégio'' de estar representados pelas constantes da linguagem. No entanto, um qualquer objecto do universo pode sempre ser o valor de uma variável. Basta fixar convenientemente uma afectação.
Em lógica, chamamos às propriedades e relações predicados. Certos símbolos da linguagem são designados símbolos de predicados: são os símbolos que representam os predicados do universo. Eis alguns exemplos de símbolos de predicados para o nosso Problema 1:
feminino
para representar a propriedade ``é do sexo feminino'';
pai
para representar a relação ``é pai de''.
Dizemos que a relação ``é pai de'' é uma relação binária, ou de aridade 2, porque ela relaciona 2 objectos. Por outro lado, uma propriedade como ``é do sexo feminino'', é de aridade 1. Cada símbolo de predicado tem portanto uma certa aridade. Para tornar explícita a aridade, escrevemos: feminino/1, pai/2.
Com os símbolos dos predicados e dos termos, construimos os átomos. Alguns exemplos de átomos para o Problema 1, são:
feminino(ana)
pai(luis, eusebio)
pai(P,F)
De maneira geral, um átomo escreve-se com um símbolo de predicado e um número de termos igual à aridade do símbolo do predicado em questão (bem como parêntesis curvos e eventualmente vírgulas). Estes termos são os argumentos do átomo.
Um átomo fechado é um átomo que não contém qualquer variável. No universo, das duas uma: ou ele é verdadeiro ou então falso. Por exemplo, para o problema considerado, o átomo pai(luis,eusebio) é verdadeiro se e sómente se o humano representado pela constante luis é o pai do humano representado pela constante eusebio (estamos a usar a convenção, arbitrária, que o primeiro argumento (aqui luis) corresponde ao pai e que o segundo argumento (aqui eusebio) corresponde ao filho).
De um modo geral, um átomo fechado é verdadeiro no universo considerado, se os valores dos seus termos verificam o predicado representado pelo símbolo de predicado do átomo em questão.
Para um átomo não fechado, quer dizer, com pelo menos uma variável, tudo isto não faz sentido senão para uma afectação fixa, que determina um valor para cada variável.
Para o Problema no 1, consideremos um predicado de aridade 3, denotado por progenitores, para representar a seguinte relação: o átomo
progenitores(M,P,F)
é verdadeiro, para uma certa afectação, se, e sómente se, o valor da variável F for filho da mãe representada pelo valor da variável M e do pai representado pelo valor da variável P.
Consideremos, também, dois símbolos de predicados de aridade 2: mae e progenitor, para representar, respectivamente, as relações ``é a mãe de'' e ``é um dos dois progenitores de''.
Com os átomos, construímos as cláusulas (a terminologia exacta é a de ``cláusulas definidas'', mas como são as únicas cláusulas consideradas neste curso, serão denotadas simplesmente por cláusulas). Alguns exemplos de clásulas para o problema considerado são:
progenitores(M,P,F) :- mae(M,F), pai(P,F).
progenitor(B,A) :- mae(B,A).
progenitor(B,A) :- pai(B,A).
pai(luis,ana) :-.
Uma cláusula começa sempre por um átomo, chamado de cabeça da cláusula, seguida de :- e de uma sucessão finita de átomos, apelidada de corpo da cláusula. Uma cláusula termina sempre com um ponto. Os átomos do corpo são separados por vírgulas. Pode no entanto acontecer o corpo ser vazio como a última cláusula acima.
As cláusulas com corpo vazio são chamadas de factos enquanto às outras apelidamos de regras. Para simplificar a notação escrevemos pai(luis,ana). em vez de pai(luis,ana) :-.
Para uma afectação fixa, cada átomo de uma cláusula é, ou verdadeiro, ou falso, no universo considerado. A cláusula, ela mesma, terá, no universo, um valor lógico, ou verdadeiro ou falso:
a cláusula é falsa se, e sómente se, a cabeça é falsa e todos os átomos do corpo são verdadeiros.
Isto não é mais do que uma maneira rigorosa de dizer que :- deve ser visto como o sinal de implicação Ü da lógica, a vírgula como o Ù lógico, e a cláusula como a seguinte implicação: Se todos os átomos do corpo são verdadeiros Então o átomo da cabeça é verdadeiro. No entanto, é importante notar que quando o corpo é vazio, a cláusula (facto) é verdadeira se, e sómente se, a cabeça é verdadeira.
No universo do Problema no 1, a cláusula
progenitores(M,P,F) :- mae(M,F), pai(P,F).
é verdadeira (não importa qual a afectação).
Uma cláusula é válida no universo em questão, se ela é sempre verdadeira independentemente da afectação: em lógica dizemos que as variáveis da cláusula são quantificadas universalmente. A cláusula precedente é então válida no universo contextual do Problema 1.
De modo semelhante, um átomo é válido no universo, se ele for verdadeiro qualquer que seja a afectação considerada. Um facto é então válido se, e somente se, o seu átomo de cabeça é válido.
Para um átomo ou uma cláusula que não possuam variáveis (átomo fechado, cláusula fechada) ser verdadeira ou falsa não depende absolutamente nada das afectações e, por conseguinte, o conceito de validade no universo não faz intervir o de afectação. Por exemplo, no nosso Problema 1, a cláusula
pai(luis, ana) :- .
isto é, o facto
pai(luis, ana).
e o átomo pai(luis, ana) são válidos no universo se, e sómente se, o humano (valor de) luis é o pai do humano (valor de) ana.
Para o Problema 1, consideramos agora um símbolo de predicado de aridade 2, chamado avo, para representar a relação ``é um dos avós de''. No universo do problema, a cláusula seguinte é válida:
avo(A,N) :- progenitor(A,P), progenitor(P,N).
Do que foi dito, esta cláusula pode ser lida como:
``Qualquer que sejam A, P e N, se progenitor(A,P) e progenitor(P,N) são ambos verdadeiros então avo(A,N) é verdadeiro''.
O mesmo é dizer:
``Qualquer que sejam A e N, se existe um P tal que progenitor(A,P) e progenitor(P,N) são ambos verdadeiros então avo(A,N) é verdadeiro''.
Esta dupla leitura (mudando ``qualquer que seja P'' para ``existe um P'') pode ser justificada rigorosamente (logicamente) sempre que uma variável (no nosso caso P) aparecer no corpo da cláusula sem aparecer na cabeça.
Chamamos programa em lógica (em Prolog) a uma sucessão finita de cláusulas. Na prática essas cláusulas são agrupadas do seguinte modo: juntamos aquelas que começam pelo mesmo símbolo de predicado na cabeça.
Eis o nosso primeiro programa em Prolog para o Problema 1:
mae(aldina,ana).
mae(aldina,eusebio).
mae(rosa,luis).
mae(ines,aldina).
pai(luis,ana).
pai(luis,eusebio).
pai(paulo,luis).
pai(gustavo,aldina).
progenitores(M,P,F) :- mae(M,F), pai(P,F).
progenitor(P,F) :- mae(P,F).
progenitor(P,F) :- pai(P,F).
avo(A,N) :- progenitor(A,B), progenitor(B,N).
O universo de que falamos é o universo contextual do problema, que comporta um conjunto (não vazio!) de questões às quais procuramos responder. Uma questão pode ser representada recorrendo aos átomos. Segue-se um exemplo de uma possível questão no universo do Problema 1:
?- avo(rosa,X).
O significado é: ``Quais são os objectos X, do universo, para os quais o átomo avo(rosa,X) é verdadeiro?'' O mesmo é dizer, numa linguagem mais natural: ``Quem são os netos de rosa?''
Suponhamos que sabemos que os átomos avo(rosa,ana) e avo(rosa,eusebio) são válidos no universo. Então uma resposta possível à questão é
X = ana
e uma outra é
X = eusebio
Consideremos agora a questão
?- avo(Y,ana).
Uma resposta possível é
Y = rosa
Se a questão for
?- avo(rosa,ana).
a resposta é uma simples confirmação:
yes
Podemos então considerar que temos uma solução do problema, se soubermos quais são os átomos válidos no universo. O que esperamos de um programa em lógica (o que esperamos do interpretador Prolog) é que ele seja capaz de produzir esses átomos.
Falta definir o que entendemos por ``átomos produzidos por um programa''. Para tal, necessitamos dar um significado, uma semântica, ao programa. Iremos dar várias definições deste significado, começando pelo mais natural no contexto da lógica e acabando com a mais operacional. No entanto estas definições serão, num certo sentido, equivalentes.
A noção de consequência lógica é uma noção intuitivamente clara e é rigorosamente definida em lógica. Intuitivamente, um átomo A é consequência lógica de um programa P, se podermos demonstrar que A é válido, qualquer que seja a interpretação dos símbolos, com o único pressuposto que as cláusulas de P são válidas. Limitamo-nos aqui a esta ideia intuitiva de consequência lógica.
Alguns exemplos de átomos que são consequência lógica do programa Prolog acima são:
mae(rosa,luis), pai(paulo,luis),
progenitores(rosa,paulo,luis), progenitor(rosa,luis),
pai(luis,ana), progenitor(luis,ana), avo(rosa,ana).
Podemos achar estes átomos, aplicando a definição de ``consequência lógica'' dada na cadeira de ``Lógica de Predicados de Primeira Ordem''. Será, no entanto, mais cómodo com a definição construtiva, equivalente, que damos à frente.
Denotamos por CL(P), o conjunto de átomos que são consequência lógica do programa P. É precisamente este conjunto CL(P), que consideramos como sendo o conjunto dos átomos ``produzidos'' por P. Desta maneira, damos um significado lógico a um programa.
Nos exercícios que se seguem, descreva o universo do discurso, identificando os objectos/entidades, as suas propriedades e relações, ¼ Defina depois os símbolos de predicados (não se esquecendo de indicar as respectivas aridades), as constantes, ¼ Especifique, por fim, um programa Prolog. Dê depois exemplos de questões e possíveis respostas.
Para construir um Sistema de Informação para uma Unidade de Arqueologia, foram
identificados as seguintes Entidades e Relações:
o Arqueólogo (descrito pelo código interno, nome e
instituição onde trabalha) que fez uma Escavação
(caracterizada por um identificador, local onde se situa e sector onde se está a escavar)
e o Achado (descrito por um identificador, uma classe (tipo
de objecto), o material e o estado de conservação) que é encontrado pelo
Arqueólogo nessa Escavação.
Antes de se criar a Base de Dados Relacional, que servirá de suporte ao sistema informático final, está-se a pensar fazer um protótipo do sistema num ambiente de programação declarativo, lógico.
Escolha os predicados (indique o seu nome e todos os seus argumentos) que deve usar em Prolog para modelar as entidades e as relações entre elas (para concretizar a sua resposta, mostre, como exemplo, 1 ou 2 factos concretos para cada um desses predicados).
Numa empresa fabricante de equipamento eléctrico para cozinhas, encontram-se as seguintes proposições sobre a constituição de um fogão:
Responda, então, às alíneas seguintes:
Para construir um Sistema de Informação para uma Biblioteca, foram identificados as
seguintes Entidades e Relações:
o Livro (descrito pelo ISBN, titulo, assunto e editora) que é
escrito por um Autor (caracterizado por um nome, o
país de onde é natural, e o estilo principal) e o Utente
(descrito por um código, o nome, a classe (docente, aluno, externo), e o telefone) que requisita
um livro numa data para leitura interna, ou domiciliária.
Antes de se criar a Base de Dados Relacional, que servirá de suporte ao sistema informático final, está-se a pensar fazer um protótipo do sistema num ambiente de programação declarativo, lógico.
Escolha os predicados (indique o seu nome e todos os seus argumentos) que deve usar em Prolog para modelar as entidades e as relações entre elas (para concretizar a sua resposta, mostre, como exemplo, 1 ou 2 factos concretos para cada um desses predicados).
No livro 100 Jogos Lógicos da colecção O Prazer da Matemática da Gradiva, pode ser encontrado o jogo que se segue.
Um motorista exprime as suas impressões sobre automóveis da seguinte forma:
- Uma tracção à frente dá boa estabilidade;
- Uma viatura pesada deve ter bons travões;
- Todas as viaturas de motor muito potente são caras;
- As viaturas ligeiras não têm boa estabilidade;
- Uma viatura de motor pouco potente não pode ter bons travões.
Admitirá ele a existência de uma viatura de tracção à frente que seja cara?
Responda, então, às alíneas seguintes:
Para gerir uma Central de Reservas de Automóveis e de Hóteis portugueses foram
identificadas as seguintes Entidades e Relações:
a Viatura (especificada pela marca, modelo, matrícula,
cilindrada e número de lugares), o Hotel (descrito pelo
nome, classificação (em número de estrelas), localização, telefone), o Cliente (caracterizado por um nome, bilhete de identidade,
profissão, telefone), e a Reserva que é feita por um
Cliente para uma Viatura, ou para um Hotel, e que é descrita por: um código de reserva;
número de pessoas; data de aluguer (dia, mês); número de dias da ocupação; e, caso se
trate de um Hotel, regista-se ainda o número de quartos e respectivo tipo (duplo,
simples, ou suite).
Antes de se criar a Base de Dados Relacional, que servirá de suporte ao sistema informático final, está-se a pensar fazer um protótipo do sistema num ambiente de programação declarativo, lógico.
Escolha os predicados (indique o seu nome e todos os seus argumentos) que deve usar em Prolog para modelar as entidades e as relações entre elas (para concretizar a sua resposta, mostre, como exemplo, 1 ou 2 factos concretos para cada um desses predicados).
No regresso duma longa viagem por Portugal, Timóteo passou pela Central de Reservas (modelada no problema anterior) e fez, dos Hotéis que frequentou, as seguintes observações1:
A dita Central de Reservas pretende, obviamente, incorporar na BC do seu sistema de prototipagem em Prolog estas informações preciosas. Responda então às alineas seguintes:
Escreva um programa para que eu possa saber de quem é que eu gosto. (Os critérios são deixados ao seu gosto!)
Acrescente depois uma cláusula que traduza o seguinte conhecimento:
Eu convido para jantar quem eu gosto ou então quem preciso de convidar.
Defina, depois, o predicado ``preciso de convidar''. (Os critérios são, também aqui, deixados a seu gosto ¼)
1 Problema inspirado no Jogo 49 da livro 100 Jogos Lógicos da colecção O Prazer da Matemática da Gradiva.