Lógicas Descritivas & CARIN
Jacques Robin & Thiago Santos
Histórico

Redes Semânticas






Nós e associações;
Herança;
Confusão entre classe/sub-classe e classe/instâncias;
Falta de semântica clara das associações;
Nível do conhecimento diretamente mapeado para o nível da
implementação, sem nível lógico intermediário.
Frames

Redes Semânticas aumentadas com:




Valores default (raciocínio não monótono);
Procedimentos.
Mesmos problemas que redes semânticas.
Lógica Descritivas: emergiram para superar as limitações
destes.
Filosofia




Usar lógica para definir formalmente semântica de
formalismos de representação de conhecimento OO.
Estudar computabilidade e complexidade das
linguagens e serviços de inferência antes de
implementá-los.
Limitar expressividade para garantir esses serviços
sejam computacionalmente tratáveis.
SPIV invade a IA.
Lógicas Descritivas (LDs)


Formalismos lógicos para representação das informações sobre
classes de indivíduos e suas descrições.
Subconjunto da lógica de primeira ordem, trata de:

Relações unárias (conceitos)

Exemplo: Student


Relações binárias (papéis);

Exemplo: SUPERVISED


{(x,y) | SUPERVISED(x,y) }
Possui também:

Construtores sobre os conceitos (,, outros)

Exemplo: PdhStudent = Student  SUPERVISED.AcademicStaff


{ x | Student(x)  y.SUPERVISED(x,y)  AcademicStaff(y) }
Indivíduos, e instâncias dos conceitos



{x | Student(x)}
franklin, jacques, thiago;
Student(thiago), PhdStudent(franklin), Researcher(jacques)
Trade-offs entre expressividade e complexidade computacional
conhecidos.
Construtores
Semântica






Baseada na teoria dos conjuntos;
Semântica definida por uma interpretação (I,I);
Conjunto não-vazio, domínio I;
Função de interpretação I que mapeia:
I
 Todo conceito em um subconjunto de  ;
I
I
 Todo papel em um subconjunto de  x  ;
Unicidade de nome
I
I
 Se a  b então a  b
Um modelo para C é uma interpretação onde CI é
não-vazio
 Um conceito é satisfiable se ele possui pelo menos
um modelo.
Semântica dos construtores
Bases de conhecimento em LD


KB = Tbox + Abox
Tbox (Terminological part) = Descrições

Exemplos:



Student = Person   STUDIESAT.University
PhdStudent  Student  Researcher
Abox (Assertional part) = Instâncias

Exemplos:


PdhStudent (franklin)
STUDIESAT (franklin,UFPE)
Serviços de inferência

Dada uma base de conhecimento  = <Tbox,Abox>,
dois conceitos C e D, e um indivíduo a, chamamos:

Satisfiability:  |= C  



Subsumption:  |= C  D



Verificar se C é subsumed por D. CI  DI em todo modelo I de

Exemplo: Employee  Person  Student ?
Consistência:  |=



Verificar se há um modelo I de  tal que CI  
Exemplo: Student  Person ?
Verificar se a própria base tem um modelo.
Exemplo: Student = Person ?
Classificação de instância:  |= C(a)


Verificar se uma dada asserção é válida.
Exemplo: Person(franklin)
Raciocínio na Tbox

Tbox:



Syntax-based reasoning: Structural Comparison
Semantic-based reasoning: Constraint Systems
Expressividade Vs Complexidade

Expressividade é diretamente proporcional à complexidade
computacional.
Exemplo: Estrutura Acadêmica
LD para o exemplo

 = <Tbox,Abox>
Tbox – Conceitos
Student  Person
STUDIESAT  Student  University
Student =
Person   STUDIESAT.University
Employee  Person
AFILIATEDTO  Employee  Organization
Employee =
Person   AFILIATEDTO.Organization
AcademicSaff  Employee
SUPERVISES  AcademicStaff  PhdStudent
AcademicSaff =
Employee   SUPERVISES.PdhStudent
Researcher  AcademicStaff
PhdStudent  Student  Researcher
SUPERVISED  PhdStudent  AcademicStaff
PdhStudent =
Student   SUPERVISED.AcademicStaff

Abox – Instâncias
Student(thiago)
STUDIESAT(thiago,UFPE)
PhdStudent(franklin)
STUDIESAT(franklin,UFPE)
Researcher(jacques)
SUPERVISED(franklin,jacques)
AFILIATEDTO(jacques,UFPE)
Exemplos de serviços (1/4)  |= C  


 |= Student  Person   ?
Equivalente a:


Se já temos x Student(x)  Person(x)


Student  Person =  ?
x Student(x)  Person(x)  x Person(x)  Person(x) que é
impossível.
Logo o conjunto formado pela conjunção Student  Person é
. Não satisfiable.
Person
e1
e2
Student
e5
...
en
e14
Exemplos de serviços (2/4)  |= C  D


 |= AcademicStaff  Researcher ?
AcademicStaff  Researcher


Equivalente a: x Researcher(x)  AcademicStaff(x)
O conjunto de indivíduos do tipo Researcher está contido no do
conjunto de AcademicStaff.
AcademicStaff
e1
e2
Research
e5
...
en
e14
Exemplos de serviços (3/4)  |=

A base contém asserções/definições contraditórias?
Adicionando Person(franklin) mantém a base consistente ?

Raciocinando com as instâncias da Abox e conceitos da Tbox, temos:





Ao término das expansões da Abox temos:



PhdStudent(franklin) : Abox
Student(franklin)
: Regra PhdStudent  Student da Tbox
Person(franklin)
: Regra Person  Student da Tbox
Abox = Abox0 , Student(franklin), Person(franklin)
Ao adicionarmos Person(franklin) teríamos uma KB com contradições,
isto é, inconsistente onde franklin é Student e franklin não é Student.
Conclusão:

Uma KB que possua a Tbox anterior, não pode ter Abox com asserções do
tipo PhdStudent(franklin) e Person(franklin) pois se torna uma base
inconsistente.
Exemplos de serviços (4/4)  |= C(a)

 |= Person(franklin) ?

Raciocínio sobre a hierarquia definida na Tbox, gera:



Student(franklin)
Person(franklin)
Assim, Person(franklin) pode ser deduzido como uma instância
válida dentro da KB.
Aplicações

Ontologias





Terminologia médica;
Taxonomia biológica;
Baseadas na Web (OIL, DAML+OIL).
Configuração de sistemas
Bancos de dados




Modelagem de esquemas;
Otimização de consultas;
Interoperabilidade;
Verificação de consistência dos dados.
CARIN

Linguagem que combina:



Lógicas descritivas ( ALCNR )
Cláusulas de Horn ( Regras dedutivas)
KB = <T,R,A>




Uma Tbox da lógica descritiva (T);
Um conjunto de regras (R);
Um conjunto fatos para os conceitos, papéis e predicados que
estão em T e R (A).
Contribuições


Um mecanismo de inferência completo para declarações
não-recursivas em ALCNR;
Um algoritmo para determinar subsumption em ALCNR.
CARIN – Regras e Restrições

Lógica descritiva

Sejam C e D conceitos, pode-se:

Criar definições


Descrever inclusões


C=D
CD
Regras

X[p1(X1)    pn(Xn)  q(Y)], onde:




Y  {X1,,Xn)
p1,,pn são conceitos, papéis, expressões, ou ainda
predicados que não constam na Tbox.
q não pode ser um conceito ou papel. O raciocínio sobre
a estrutura deve estar na Tbox, não nas regras.
Um predicado q é dito dependente de um predicado p se
p é precedente em uma regra que gera q.
Regras em CARIN


Considerando a Tbox e Abox já apresentadas.
Adicionando ao componente de regras:



AcademicStaff(X)   7 SUPERVISES(X)  Overloaded(X)
Student(X)  AcademicStaff(Y)  SUPERVISED(X,Y)
SpecialStudent(X)
Poderíamos responder as perguntas:

Overloaded(jacques)?


Jacques está sobrecarregado? R: não
SpecialStudant(franklin)?

Franklin é um aluno especial? R: não
Referências

Curso de Lógicas Descritivas

Enrico Franconi, Department of Computer
Science, University of Manchester, UK
http://www.cs.man.ac.uk/~franconi/dl/course

Referências da aula “Ontologias na
Web”

http://www.cin.ufpe.br/~compint/aulas-IAS/mci2/taias-012