Introdução às Lógicas de
Descrições
Fred Freitas
CIn – UFPE
[email protected]
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
Tipos de formalismos de
representação

Formalismos orientados a predicados:
regras de produção e programação em
lógica
– Pioneiros - foco no processo, funcionamento

Formalismos orientados a domínios:
frames, redes semânticas, lógica de
descrições
– Classes, relações e restrições
– Facilitam a estruturação de conhecimento
sobre um domínio de aplicação
Exemplo de rede semântica
faz
Animal
Ako
Pássaro
Comer
Ako
tem
Mamífero
Pêlos
Ako
Cão
Is-a
Fido
(instanciação)
Expressividade dos Frames

Classes
– Herança múltipla,
– Instâncias

Atributos (slots)
– Slots podem ser instâncias de outras classes
(relações)

Facetas - Restrições sobre os slots
– Valor default, valores permitidos (allowedvalues), domínio (ex: 1..100), cardinalidade
máxima e mínima, tipo (inteiro, string,...),...
Definindo classes e instâncias
(defclass City "Cities are part of countries or states."
(is-a Location)
(multislot is-Part-Of
(type INSTANCE)
(allowed-classes Country State)
(inverse-slot has-Parts)
(cardinality 1 1))
(single-slot name
(type STRING)
(cardinality 1 1)))
([Locations_00427] of City
(is-Part-Of [WA])
(name "Washington"))
Problemas com RSs / frames:
ambigüidade [Brachman 79, Franconi 2003]
entre classes e instâncias
 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
[Franconi 2003]
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.”
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
Histórico

1ª. Geração (fins dos ’70 - 85)
– Linguagens terminológicas
– Representações com mais engajamento
ontológico e semântica definida
– 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
– Uso de tableaux para raciocínio / classificação

Abordagens:
– Limitada+completa: P
 Ex: CLASSIC [Brachman 91] – uso industrial
– 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]


Uso na Web semântica!
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
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

{x|Student(x)}
{x|Married(x)}
Papéis (predicados binários, relações, conjuntos de
pares de indivíduos)
– Ex: friend
{(x,y)|friend(x,y)}

Construtores para expressões de conceitos

Indivíduos (instâncias)
– Ex: Student ⊓  hasFriend.Married
– {x|Student(x)^y(hasFriend(x,y)^Married(y))}
– Ex: Student (zé), ...
Lógica de Descrições - Intuição

Significado da restrição existencial

Sintaxe de Manchester
– Ex: Student ⊓  hasFriend.Married
– {x|Student(x)^y(hasFriend(x,y)^Married(y))}
– Student and hasFriend some Married
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
Famílias de DLs
S = FL- +AL*+
papéis transitivos
– SHIQ
FL- (frame language)

Sintaxe



A : atomic- concept
R : atomic- role
C, D : concept

C, D  A | C ⊓ D | R.C | R
Notação e Significado (Informal)
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

Bases de conhecimento
KB = Tbox + Abox
 Tbox (Terminological part) = Descrições

– Exemplos:
 Student ≡ Person ⊓ studiesAt.University
 PhdStudent ⊑ Student ⊓ Researcher

Abox (Assertional part)
– Instâncias
– Exemplos:
 PhdStudent (filipe)
 studiesAt (filipe,UFPE)
Descrições (axiomas)
Student ⊑ enrolled.Course
 Professor ⊑ teaches.Course
 Working-student ⊑ Student
 Working-student ⊑ Professor

– Pode ser um professor e/ou estudante
– O mesmo que
 Working-student ⊑ Student ⊔ Professor

As descrições sobre um item não são
agrupadas como nos frames
– Um classificador as organiza por raciocínio
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
Semântica (“a la” Tarski)

Interpretação

Semântica dos construtores
Sintaxe e Semântica das DLs
Lógica de Descrições - Intuição

Significado da restrição existencial

Sintaxe de Manchester
– Ex: Student ⊓  hasFriend.Married
– {x|Student(x)^y(hasFriend(x,y)^Married(y))}
– Student and hasFriend some Married

Significado da restrição universal

Sintaxe de Manchester
– Ex: Student ⊓ ∀hasFriend.Married
– {x|Student(x)^∀y(hasFriend(x,y)Married(y))}
– Student and hasFriend only Married
Voltando aos batráquios...
Sapo

tem-cor
Verde
Todo sapo é (de algum tipo de) verde
– Sapo ⊑ tem-cor.Verde

Todo sapo é só (de algum tipo de) verde
– Sapo ⊑ tem-cor.Verde

Tem um sapo que é verde
– Sapo ( x ) , tem-cor ( x, verdeMusgo )

...
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
Exemplo
Exemplo (cont.)

Exemplo

[Baader 2012]
Suponha que tenhamos as instâncias:
?
Exemplo

[Baader 2012]
Suponha que tenhamos as instâncias:
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 = S o T (composição)
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 ⊔ 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
Exemplo - Subsunção

Famílias de DLs
S = FL- +AL*+
papéis transitivos
– SHIQ
ALC (DL atributiva) e FL’s

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 de 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
Sumário

Motivação
– Problemas em frames
e redes semânticas






Histórico
Definições básicas
Várias DLs
Semântica
Exemplos
Mundo aberto






Web semântica
Tarefas de raciocínio
Reduções
Tableaux
Complexidade
Outras soluções
– Autômatos
– Resolução

Comparação
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
– Um classificador DL, conclui que Lula e Líder-Sindical são
a mesma pessoa
Cuidados com mundo aberto
[Rector et al 2004]
Margheritta≡ Pizza ⊓ ∃has_topping.Mozza
⊓ ∃has_topping.Tomato
49
Pizza Vegetariana
Veg_Pizza≡Pizza ⊓ ¬(∃has_topping.Meat)
⊓ ¬(∃has_topping.Fish)
50
Margherita é Vegetariana?
Margherita é Vegetariana?
• NÃO!!
Por quê?

“A vegetarian pizza is any pizza that,
amongst
other things,
does not have any meat topping and
does not have any fish topping”
 “A margherita pizza is a pizza and,
amongst
other things,
has some tomato topping and
has some mozarella topping”
É preciso “fechar” o conj. imagem

54
“A Margherita pizza has tomato and cheese
toppings and only tomato and cheese toppings”
Margheritta≡ Pizza ⊓ ∃has_topping.Mozza
⊓ ∃has_topping.Tomato
⊓ ∀has_topping.(Tomato ⊔ Mozza)
Classificação correta, agora

55
Meat , Mozza e Tomato precisam ser
disjuntos
Porque DL foi adotada
pela Web Semântica?
Várias causas...

Por causa da Hipótese de Mundo Aberto
– Não se pode assumir que, se um fato não foi
encontrado na Web, então ele não existe

Igualdade de indivíduos é possível
– A dedução ou representação de que no
exemplo anterior Lula = Líder-Sindical

Representação lógica sem variáveis em
tese facilita o entendimento por usuários
OWA vs. CWA
[Staab 2006]
OWA: Open World Assumption (Mundo Aberto)
A existência de mais indivíduos é possível a não ser que isto
seja explicitamente colocado.
OWL uses OWA!
CWA: Closed World Assumption (Mundo Fechado)
Assume-se que a base de conheciemtno contém todos os
individuos que existem e todos os facts.
Todos os filhos de
Bill são homens?
child(Bill,Bob)
Man(Bob)
 1 child.T(Bill)
Não se sabe, pois
não se conhecem
todos os filhos de
Bill
Assumindo que
sabemos tudo sobre
Bill, todos os seus
filhos são homens.
? ⊨ child.Man(Bill)
DL
Não se sabe
Prolog
sim
? ⊨ child.Man(Bill)
sim Agora sabemos tudo sobre
os filhos de Bill em DL.
Do ponto de vista de raciocínio
A classificação é boa para a Web pois as
informações encontram-se espalhadas
 É preciso ainda garantir o raciocínio

– Lógica de 1ª ordem é semi-decidível
– Hoje, em OWL 2, as DLs são decidíveis
Exemplo em OWL
[Horrocks 2004]
Ontologies
DrAncestor ≡ Person ⊓ ∃hasChild.(Dr ⊔ ∃hasChild.Dr)
<owl:Class rdf:ID=“DrAncestor”>
<owl:intersectionOf rdf:parseType=" collection">
<owl:Class rdf:about="#Person"/>
<owl:Restriction>
<owl:onProperty rdf:resource="#hasChild"/>
<owl:toClass>
<owl:unionOf rdf:parseType=" collection">
<owl:Class rdf:about="#Dr"/>
<owl:Restriction>
<owl:onProperty rdf:resource="#hasChild"/>
<owl:hasClass rdf:resource="#Dr"/>
</owl:Restriction>
</owl:unionOf>
</owl:toClass>
</owl:Restriction>
</owl:intersectionOf>
</owl:Class>
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.

Bibliografia

NARDI, D.; BRACHMAN, R. “An Introduction to Description
Logics”. In: The Description Logic Handbook – Theory,
Implementation and Applications. Editedy by Franz Baader, Diego
Calvanese, Deborah McGuinness, Daniele Nardi and Peter PatelSchneider, 2003.

BAADER, F.; NUTT, W. “Basic Description Logics”. In: The
Description Logic Handbook – Theory, Implementation and
Applications. Editedy by Franz Baader, Diego Calvanese, Deborah
McGuinness, Daniele Nardi and Peter Patel-Schneider, 2003.

BAADER, F. “Description Logic Terminology”. In: The
Description Logic Handbook – Theory, Implementation and
Applications. Editedy by Franz Baader, Diego Calvanese, Deborah
McGuinness, Daniele Nardi and Peter Patel-Schneider, 2003.
Bibliografia

HORROCKS,
I.
“Implementation
and
Optimisation
Techniques”. In: The Description Logic Handbook – Theory,
Implementation and Applications. Editedy by Franz Baader, Diego
Calvanese, Deborah McGuinness, Daniele Nardi and Peter PatelSchneider, 2003a.

VIEIRA, R.; ABDALLA, D.; SILVA, D. M.; SANTANA, M. R. “Web
Semântica: Ontologias, Lógicas de Descrições e
Inferências”. In: Web e Multimídia: Desafios e Soluções. PUC
Minas, 2005.