Concurso/EncontroNacional
de Programação em Lógica
CeNPL’2002
Universidade de
Coimbra / Instituto Politécnico de Coimbra
11-13 de Abril de
2002
Problema nº 1
CAÇA ÀS HIPÓTESES
Introdução
Num sistema de conhecimento baseado em
modelos, o conhecimento causal é apresentado por regras do tipo
rN :: C <- A1 & A2 &
...& An
com o significado usual de que os
antecedentes A1, A2, ... An,
causam o consequente C (rN é apenas um
identificador para a regra). Para simplificar, assumiremos que os antecedentes
e os consequentes são proposições atómicas, representadas por átomos. Alguns
desses átomos podem ser conhecidos, o que é especificado através de factos do
tipo
fN ! F.
em que F é o facto observado e fN um identificador único. Num sistema deste tipo, a tarefa
de diagnóstico consiste em determinar hipóteses que juntamente com os factos e
as regras conhecidas “justifiquem” causalmente um determinado conjunto de
observações. Nem todas as hipóteses são interessantes, pelo que o sistema
apenas considera hipóteses especificadas através de declarações
hN ? H.
em que H é uma hipótese e hN um identificador único. De notar que o mesmo átomo pode ser declarado como hipótese e como facto (por exemplo, após ter sido validado).
Um exemplo de uma base de conhecimento
causal pode ser
r1 :: febre <- gripe.
r2 :: febre_alta <-
febre & fraqueza.
r3 :: dores <- gripe & febre_alta.
r4 :: febre <-
anginas.
r5 :: dor_de_garganta <- anginas.
r6 :: dor_de_garganta <- constipação.
f1 ! fraqueza.
h1 ? gripe.
h2 ? fraqueza.
h3 ? anginas.
h4 ? constipação.
Neste exemplo, a
observação de febre, pode ser justificada pelas hipóteses de gripe (pela regra r1) ou anginas (pela regra r4). Já
a observação de dores é justificada pela hipótese de gripe (em conjunto com o facto f1 e as regras r1 e r2).
Finalmente, a justificação das observações febre_alta e dor_de_garganta é justificada ou pela hipótese simples anginas (com o facto f1 e
as regras r2 e r4), quer pela hipótese dupla constipação e gripe (com o facto f1 e
as regras r1, r2 e r6).
O objectivo deste problema é implementar um
predicado diag(+O, -K, -H), com o seguinte
significado
1.
O é um conjunto de observações
que se pretende justificar, na forma O1 & O2 & ...& On (n >= 1).
2.
K retorna uma lista de
identificadores de factos e regras que justificam em conjunto com H (ver
abaixo) as observações O;
3.
H retorna uma lista com um
conjunto de hipóteses, com cardinalidade mínima, que
em conjunto com os factos e regras de K justificam as observações O.
De notar, que o predicado só deve retornar
hipóteses de cardinalidade mínima. Como a observação
de febre_alta e
dor_de_garganta pode ser justificada pela
hipótese simples anginas, o predicado diag/3
não deve retornar a hipótese dupla gripe e constipação. Por retrocesso, o predicado
deve retornar todas as hipóteses de cardinalidade
mínima, podendo repetir hipóteses se as regras e factos utilizados forem
diferentes.
Para a sua implementação do predicado diag/3 pode tomar em consideração que
a)
todas
as observações devem ter uma justificação com um máximo de 5 hipóteses
b)
as regras da sua base de
conhecimento não contêm dependências circulares.
Por exemplo, as regras abaixo não podem
co-existir, pois febre_alta
depende
de febre e febre depende de febre_alta.
rx ::
febre <- febre_alta.
r2 :: febre_alta <- febre, fraqueza.
Note bem, que o programa deverá permitir ler
ou dum ficheiro ou dum terminal o conjunto de regras e factos que constituem a
sua base de conhecimento, na sintaxe apresentada (poderá usar outra sintaxe,
mas sofrerá de uma penalização de 20% na avaliação).
Assumindo que o ficheiro “dados.pl” contem a base de conhecimento acima (regras r1 a r6, o facto f1 e as hipóteses h1 a h4), o predicado diag/3 deve produzir os diagnósticos seguintes:
?- diag(febre,
K, H).
K = [r1] , H = [gripe] ;
K = [r4] , H
= [anginas] ;
no.
?- diag(febre_alta & dor_de_garganta,
K, H).
K =
[r5,f1,r4,r2], [H] = anginas ;
no.
?- diag(dores
& dor_de_garganta, K, H).
K =
[r5,f1,r1,r2,r3] , H = [gripe,anginas] ;
K =
[r6,f1,r1,r2,r3] , H = [gripe,constipação] ;
K =
[r5,f1,r4,r2,r3] , H = [gripe,anginas] ;
no.