Lógica de Descrições
Fred Freitas
CIn - UFPE
Problemas com frames:
ambigüidade [Brachman 79, Franconi 2003]
entre classes e instâncias
 em relações parte-todo
 em quantificação

Ambigüidade entre classes e
instâncias

29’er :
–
–
–
–

AGE : 29 ,
SEX : M,
HEIGHT : Number ,
WIFE : Person .
john :
–
–
–
–
AGE : 29 ,
SEX : M,
HEIGHT : Number ,
WIFE : Person .
Ambigüidade em quantificação
Sapo

tem-cor
Verde
O que signiifica?
–
–
–
–
–
–
Todo sapo é só verde
Todo sapo também é verde
Todo sapo é de algum tipo de verde
Tem um sapo que é só verde
...
Sapos são tipicamente verdes, mas há exceções.
Conclusão: Problemas...

Falta de semântica formal
– Interpretações ambíguas

Raciocínio depende do que o desenvolvedor
pretende
– Definições semelhantes levam a raciocínios bem
diferentes
Provadores de teoremas não eram necessários
 Complexidade computacional depende de cada
tipo de raciocínio


“It is unfortunately much easier to develop
some algorithm that appears to reason
over structures of a certain kind, than to
justify its reasoning by explaining what
the structures are saying about the
domain.”
Histórico

1ª. Geração (fins dos ’70 - 85)
– Linguagens terminológicas
– Representações com mais engajamento
ontológico,
– Mais riqueza: papéis, classificação

Sistemas:
– KL-ONE [Brachman & Schmolze 78]
– KRYPTON [Brachman et al 83]
 terminologia+regras
 Tbox vs ABox
2ª. Geração – Sistemas com DL

Ênfase em teoria
– Complexidade do raciocínio vs Expressividade
– Identificação das fontes de complexidade

Abordagens:
– Limitada+completa: P
 Ex: CLASSIC [Brachman 91]
– Expressiva+incompleta: NP
 Ainda ineficientes
 Ex: LOOM [McGregor 87] e BACK [Nebel 90]
Nova (atual) geração
Alvo: Expressiva+completa!
 Raciocínio baseado em tableaux, com
otimizações
 Estudo de relações com outras lógicas
 Ex: FACT e RACER [Horrocks 98 e 2000]

Lógica de Descrições

Fragmento de L2, Lógica de Predicados sem
funções, com até 2 variáveis

Separação entre:
– Terminologia (predicados): TBox
– Asserções (constantes, instâncias): ABox

Representação sem variáveis
– Interpretação como predicados, usando expressões-
– Student  x.Student(x)
Lógica de Descrições - Expressividade

Conceitos (predicados unários, classes, conjuntos
de indivíduos, subconjunto do domínio)
– Ex: Student
– Ex: Married

Papéis (predicados binários, relações, conjuntos de
pares de indivíduos)
– Ex: friend

{x|Student(x)}
{x|Married(x)}
{(x,y)|friend(x,y)}
Construtores para expressões de conceitos
– Ex: Student   friend.Married
– {x|Student(x)^y.friend(x,y)^Married(y)}

Indivíduos (instâncias)
– Ex: Student (zé), ...
Classe

Student
– Person
– name: [String]
– address: [String]
– enrolled: [Course]

Student  Person ^ name.String ^
address.String ^ enrolled.Course
Instância

s1: Student
– name: “John”
– address: “Abbey Road . . . ”
– enrolled: cs415

Student ( s1 ) ^ name ( s1 , “ john ”) ^
String(“ john ”)^address (s1 ,“abbey-road”)
^String(“abbey-road”)^enrolled(s1,cs415 )
^ Course ( cs415 )
Descrições (axiomas)
Student  enrolled.Course
 Professor  teaches.Course
 Working-student  Student
 Working-student  Professor

– Pode ser um professor e/ou estudante

As descrições sobre um item não são
agrupadas como nos frames, é um
classificador que as organiza
Voltando aos batráquios...
Sapo

tem-cor
Verde
Todo sapo é verde
– Sapo  tem-cor.Verde

Todo sapo é só verde
– Sapo  tem-cor.Verde

Tem um sapo que é verde
– Sapo ( x ) , tem-cor ( x, Verde )

...
Famílias de DLs
S = FL- +AL*+
papéis transitivos
– SHIQ
FL- (frame language), a caçula

Sintaxe



A : atomic- concept (indefinidos)
R : atomic- role
C, D : concept

C, D  A | C  D | R.C | R
concept ::= <atomic- concept> |
(<concept >  <concept> ) |
(<atomic- role > ) |
(<atomic- role>.<concept> )

Notação e Significado (Informal)
concept ::= <atomic- concept> |
( :and <concept > . . .<concept> ) |
(: some <atomic- role > ) |
(: all <atomic- role> <concept> )

R.C = indivíduos que estão na relação R e são do
conceito C
Interseção = conjunção
 União = disjunção
 Complemento = negação

Semântica (“a la” Tarski)

Baseada na Teoria de Modelos, construída sobre
a teoria de conjuntos de Cantor e ZermeloFrankel, onde:
–
–
–
–
–

 é o universo de discurso
os objetos são elementos de 
os conceitos são subconjuntos de 
as relações binárias são subconjuntos de 
a relação subclasse entre classes é interpretada como inclusão
de conjuntos
Uma interpretação na qual uma fórmula é
verdadeira é um modelo para esta fórmula
Interpretação

Uma interpretação é um par <I, .I>, onde:
– I é o universo de discurso (não-vazio)
– .I é uma função de interpretação, que mapeia:
 Conceitos para subconjuntos de I
 Papéis para subconjuntos de II
Exemplo
Exemplo (cont.)

Base de Conhecimento em DL

 A TBox tem axiomas
Uma ontologia em DL é
uma Base de conhecimento para
- S = <TBox, ABox>

A ABox tem axiomas de
instanciação de
– Conceitos
 xD
– Papéis
 <x,y>  R
 (Student U Professor)(paul)
– Conceitos:
 C  D (inclusão)
 C  D (equivalência)
– Papéis (ou
propriedades):
 R  S (inclusão)
 R  S (equivalência)
 R+  R (transitividade)
– nem toda DL tem…
Bases de conhecimento
Condições necessárias são expressas com 
 Condições necessárias e suficientes são expressas
com 

– Teaching-Assistant  Undergrad U Professor

Para uma interpretação satisfazer uma ontologia
(base de conhecimento)
– Precisa satisfazer TBox e ABox
– Então ela é um modelo desta ontologia

Uma ontologia é satisfatível se admite um modelo
ALC (linguagem atributiva) e FLs

AL = FL- (DL estrutural) + negação
– DL proposicional

FL0 = FL- + R.C (no lugar de R, que é R.T)
– Interpretação de R é a mesma de R.C, sem ^CI(y)

ALC = FL0 + negação (complemento)
Outras ALs

U – União (disjunção)
– Human  Male U Female
E – quantificação existencial (R.C)
 N – restrições numéricas (de cardinalidade) sobre
papéis (R, R)

– Busy-Woman  Woman  ( 3 child)
– Conscious-Woman  Woman  ( 5 child)
–  1 R  R
EU = C (U e E podem ser obtidos de FL- +C)
 Estudadas: ALC (ou ALUE) e ALCN (ou ALUEN)

O Q do SHIQ

Q – restrições numéricas (de cardinalidade)
sobre papéis qualificados (R.C, R.C)
– Worried-Woman  Woman  ( 3 child.Man)

Note que U,E,N,C,Q e interseção são
construtores de classes!
Classificação

Colocar um conceito/papel no devido lugar
dentro da hierarquia, de forma a que
– Abaixo dele, esteja o conceito mais geral que
é mais específico que ele
– Acima dele, esteja o conceito mais específico
que é mais geral que ele

Verifica estas relações por subsunção
– Quais conceitos “cabem”dentro de quais
Sobre o Raciocínio

Basicamente por subsunção (herança)
– Checar se um conceito/papel é contido por outro

Hipótese do Mundo Aberto
– Em contraste com quase todos os outros formalismos de
representação (Mundo Fechado)
– Em Frames, Presidente tem cardinalidade 1
– Presidente(Lula), Presidente(Líder-Sindical) dará erro
– Em DL, Lula e Líder-Sindical são a mesma pessoa
Tipos de Raciocínio em DLs
Consultas à ontologia
 Conseqüência Lógica
 Satisfatibilidade
 Checagem de consistência
 Checagem de instância
 Checagem de equivalência

Raciocínios com instâncias

Consultas à ontologia
– Recuperar instâncias que obedecem a expressões
 ?Aluno
– Daniel, Carol, Zé...

Checagem de instância
– Determina se um indivíduo é instância de um
conceito ou papel
– Se a asserção C(a) satisfaz todos os modelos da
ontologia
 Ver exemplo de conseqüência lógica
Raciocínios com conceitos

Checagem de consistência
– Checar se um conceito ou papel é vazio
– Senão, é satisfatível
 Student  Person

Checagem de equivalência
– Dois conceitos são equivalentes se todas as
instâncias dos dois forem comuns aos dois
– Duas instâncias podem ser a mesma
 Ciclos em definições
Conseqüência Lógica

Se todo modelo da BC A é também
modelo da BC B, então B é Conseqüência
Lógica de A
– TBox:
 teaches.Course  Undergrad U Professor
– ABox:
 teaches ( john , cs415 ) ; Course ( cs415 ) ;
 Undergrad ( john )
– Professor ( john )?
Satisfatibilidade

Checa se existe algum modelo que satisfaz
um axioma
 Student  Person
Complexidades das DLs
OWL: Construtores de Classes e
Axiomas
Referências
The Description Logic Handbook. F.
Baader et al. 2003. Cambridge Press.
 Curso de DL. Enrico Franconi, Univ.
Bozen-Bolzano, Itália.
 Curso de Ontologias. Virgínia Brilhante,
UFAM.
