Lógica de descrição

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A Lógica de descrição (LD) é uma família de linguagens formais de representação do conhecimento. É mais expressiva do que a lógica proposicional , mas tem problemas de decisão mais eficientes do que a lógica de predicados de primeira ordem.

LD é usada em inteligência artificial para o raciocínio formal sobre os conceitos de um domínio de aplicação (conhecido como conhecimento terminológico). É de especial importância no provimento de um formalismo lógico para ontologias e Web Semântica. A aplicação mais notável fora da ciência da informação está em informática biomédica onde LD auxilia na codificação do conhecimento médico.

Introdução[editar | editar código-fonte]

A Lógica de descrição (LD) são modelos de conceitos, papéis e indivíduos, e seus relacionamentos. O conceito de modelagem fundamental de um LD é o axioma - uma lógica descritiva relacionando papéis e/ou conceitos. Esta é uma diferença fundamental do paradigma de frames onde uma especificação de frame declara e define completamente uma classe.

Nomenclatura[editar | editar código-fonte]

Diferenças de Lógica de Primeira Ordem[editar | editar código-fonte]

A comunidade da lógica de descrição usa uma terminologia diferente do que o predicado comunidade lógica de primeira ordem para noções operacionalmente equivalentes; alguns exemplos são a seguir:

Sinônimos
LPO LD
classe conceito
propriedade ou predicado papel
objeto indivíduo

A Linguagem Ontológica da Web ( Web Ontology Language - OWL ) usa principalmente terminologia a Lógica de primeira ordem [LPO], apesar de ser uma implementação de uma lógica de descrição.

Convenção de nomenclatura[editar | editar código-fonte]

Existem muitas variedades da Lógica de descrição e há uma convenção de nomenclatura informal, descrevendo grosseiramente os operadores autorizados. A expressividade está codificada na etiqueta para uma lógica de partida com um dos seguintes lógicas básicas:

\mathcal{LA} Linguagem atributiva. Esta é a linguagem base que permite:
  • Negação Atômica (negação do conceito nomes que não aparecem no lado esquerdo de axiomas)
  • Interseção conceitual
  • Restrições universais
  • Quantificação existencial limitada
\mathcal{QL} Quadro de linguagem de descrição de base,[1] permite:
  • Interseção conceitual
  • Restrições universais
  • Quantificação existencial limitada
  • Restrição de papel
\mathcal{EL} Permite:
  • Interseção conceitual
  • Restrições existenciais (de quantificação existencial completa)

Seguido por qualquer uma das seguintes extensões:

\mathcal{F} Propriedades funcionais, um caso especial de quantificação de unicidade.
\mathcal{E} Qualificação existencial completa (restrições existenciais que têm outras cargas que \top.
\mathcal{U} União conceitual.
\mathcal{C} Negação conceitual complexa.
\mathcal{H} Hierarquia de funções (subpropriedades - rdfs:subPropriedadeDe).
\mathcal{R} Papel complexo limitado de inclusão de axiomas; reflexividade e não reflexibilidade; papel de disjunção.
\mathcal{O} Nominais. (Classes enumeradas de restrições de valor do objeto - owl:oneOf, owl:hasValue).
\mathcal{I} Propriedades inversas.
\mathcal{N} Restrições de cardinalidade (owl:cardinalidade, owl:maxCardinalidade), um caso especial de quantificação de contagem.
\mathcal{Q} Restrições qualificadas de cardinalidade (disponíveis em OWL 2, restrições de cardinalidade que têm outros preenchedores que \top).
^\mathcal{(D)} Uso de propriedades de tipo de dados, os valores de dados ou tipos de dados.

Exceções[editar | editar código-fonte]

Alguns LDs canônicos que não se encaixam exatamente esta convenção são:

\mathcal{S} Uma abreviação para \mathcal{ALC} com papéis transitivos.
\mathcal{FL^-} A sub-linguagem de \mathcal{FL}, que é obtido por não permitir restrição papel. Isso é equivalente a \mathcal{AL} sem negação atômica.
\mathcal{FL}_o A sub-linguagem de \mathcal{FL^-}, que é obtido, não permitindo quantificação existencial limitada.
\mathcal{EL^{++}} Torna-se \mathcal{ELRO}.[2]

Exemplos[editar | editar código-fonte]

Como um exemplo, \mathcal{ALC} é uma lógica centralizada importante descrição da qual a comparação com outras variedades pode ser feita. \mathcal{ALC} é simplesmente \mathcal{AL} com complemento de qualquer conceito permitido, e não apenas conceitos atômicos.

Um outro exemplo, a descrição lógica \mathcal{SHIQ} é a lógica \mathcal{ALC} além de restrições de cardinalidade estendidos e transitiva e papéis inversos. As convenções de nomenclatura não são puramente sistemática de modo que a lógica \mathcal{ALCOIN} pode ser referido como \mathcal{ALCNIO} e abreviaturas são feitas sempre que possível, \mathcal{ALC} é usado em vez do equivalente \mathcal{ALUE}.

O editor ontológico protégé suporta \mathcal{SHOIN}^\mathcal{(D)}. Três principais bases biomédicas de terminologia da informática, SNOMED CT, Galeno e GO, é exprimível em \mathcal{EL} (com propriedades de função adicionais).

OWL 2 fornece a expressividade de \mathcal{SROIQ}^\mathcal{(D)}, OWL-LD é baseado em \mathcal{SHOIN}^\mathcal{(D)}, e para OWL-Lite é \mathcal{SHIF}^\mathcal{(D)}.

História[editar | editar código-fonte]

Lógica de descrição (LD) foi dado o seu nome atual em 1980. Antes disso ele foi chamado (por ordem cronológica): sistemas de terminologia e linguagens conceituais.


Representação do conhecimento[editar | editar código-fonte]

Quadros e redes semânticas falta semânticas (com base em lógica )formais.[3] LD foi introduzido pela primeira vez em Representação do Conhecimento de sistemas ( Knowledge Representation - KR) para superar essa deficiência.[3]

O primeiro sistema de base KR-LD foi KL-ONE (por Ronald J. Brachman e Schmolze, 1985). Durante os anos 80 outros sistemas baseados em LD usando algoritmos subsunção estrutural [3] foram desenvolvidos, incluindo KRYPTON (1983), Tear (1987), Back (1988), K-REP (1991) e clássicos (1991). Esta abordagem destaque LD com expressividade limitada, mas tem , relativamente, eficiente (tempo polinomial) raciocínio. [3]

No início dos anos 90, introduziu um novo quadro baseado em um paradigma algorítmico que permitiu raciocínio eficiente em LD mais expressivo [3] . Sistemas baseados em LD usando esses algoritmos -, Como KRIS (1991) - mostram desempenho aceitável de raciocínio sobre os problemas típicos de inferência mesmo embora o pior caso de complexidade já não é polinomial. [3]

Desde meados dos anos 90, pensadores criaram com bom desempenho prático sobre LD muito expressivo, com alta complexidade no pior caso.[3] Exemplos deste período incluem FaCt, [4] RACER (2001), CEL (2005), e KAON 2 (2005).

Raciocinadores LD, como a FaCt, FaCt ++, [4] RACER, DLP e Pellet,[5] implementam o Método dos Tableaux analítico. KAON2 é implementado por meio de algoritmos que reduzem a base de SHIQ (D) o conhecimento de um programa de registro de dados disjuntivo.

Web Semântica[editar | editar código-fonte]

A DARPA Agent Markup Language (DAML) e Camada de Inferência Ontológica (Ontology Inference Layer - OIL) são linguagens ontológicas para a web semântica que podem ser vistas como variantes sintáticas de LD. Em particular, os semântica formal e raciocínio em OIL usam o \mathcal{SHIQ} LD.[6] . O DAML + OIL LD foi desenvolvida como uma submissão a [7] - e constituiu o ponto de partida - Consórcio World Wide Web (W3C) Grupo de Trabalho Ontologia Web [8] . Em 2004, o Grupo Ontológico de Trabalho Web terminou o seu trabalho, emitindo a recomendação OWL [9] . O projeto da OWL é baseado na família \mathcal{SH} de DL[10] com OWL LD e OWL-Lite baseadas em \mathcal{SHOIN}^\mathcal{(D)} and \mathcal{SHIF}^\mathcal{(D)} respectivamente.[10]

O Grupo de Trabalho OWL W3C começou a trabalhar em 2007 em um refinamento - e extensão - OWL [11] . Em 2009, este foi concluído mediante a emissão da recomendação owl2. Owl2 é baseado na descrição lógica \mathcal{SROIQ}^\mathcal{(D)}.[12] . A experiência prática demonstrou que faltava na OWL LD várias características necessárias para modelar domínios complexos.

Modelagem[editar | editar código-fonte]

Em LD, é feita uma distinção entre a chamada TBox (caixa terminológica) e a ABox (caixa assercional). Em geral, o TBox contém frases que descrevem conceito e hierarquias (ou seja, as relações entre conceitos), enquanto a ABox contém sentenças básicas indicando onde na hierarquia os indivíduos pertencem (ou seja, as relações entre os indivíduos e conceitos). Por exemplo, a declaração:

(1) Cada funcionário é uma pessoa

pertence à TBox, enquanto a declaração:

(2) Bob é um empregado

pertence à ABox.

Note-se que a distinção TBox / ABox não é significativa, no mesmo sentido que os dois "tipos" de sentenças não são tratados de forma diferente em lógica de primeira ordem (que agrupa a maioria LD). Quando traduzido em lógica de primeira ordem, um axioma subsunção como (1) é simplesmente uma restrição condicional para predicados unários (conceitos) com apenas as variáveis ​​que aparecem nele. Claramente, a frase desta forma não é privilegiado ou especial sobre frases em que apenas constantes ("Grounded" valores) aparecem como (2).

Então, por que a distinção introduzida? A principal razão é que a separação pode ser útil ao descrever e formular-procedimentos de decisão para vários LD. Por exemplo, um pensador pode processar o TBox e ABox separadamente, em parte por causa de certos problemas fundamentais de inferência estão vinculados a um, mas não o outro ("classificação" está relacionada com a TBox, instância de controle à ABox). Outro exemplo é que a complexidade da TBox pode afetar grandemente o desempenho de um determinado procedimento de decisão para um certo LD, independentemente do ABox. Assim, é útil ter uma maneira de falar sobre essa parte específica da base de conhecimento.

O motivo secundário é que a distinção pode fazer sentido do ponto de vista da base da perspectiva do modulador. É plausível para distinguir entre a nossa concepção de termos / conceitos do mundo (axiomas classe na TBox) e manifestações particulares desses termos / conceitos (afirmações exemplo, no ABox). No exemplo acima: quando a hierarquia dentro de uma empresa é a mesma em todos os ramos, mas a atribuição aos funcionários é diferente em cada departamento (porque há outras pessoas que trabalham lá), faz sentido reutilizar o TBox para diferentes ramos que não fazer usar o mesmo ABox.

Há duas características de Descrição Logic que não são compartilhadas pela maioria dos outros formalismos de descrição de dados: não-LD não faz o Pressuposto de Nome original ( Unique Name Assumption - UNA) ou o Pressuposto de Mundo Fechado (Closed World Assumption - CWA). Não ter UNA significa que dois conceitos com nomes diferentes podem ser autorizados por uma inferência a ser mostrado para ser equivalentes. Não ter CWA, ou melhor, ter o Pressuposto de mundo aberto (Open World Assumption - OWA) significa que a falta de conhecimento de um fato não implica imediatamente no conhecimento da negação de um fato.

Descrição formal[editar | editar código-fonte]

Como a lógica de primeira ordem (LPO), uma sintaxe que define uma coleção de símbolos são expressões legais em uma Lógica de descrição (LD), e a semântica determinam o significado. Ao contrário do LPO, um LD pode ter diversas variantes sintáticas bem conhecidos.

Sintaxe[editar | editar código-fonte]

A sintaxe de um membro da família descrição lógica é caracterizado pela sua definição recursiva , em que os construtores que podem ser utilizados para formar termos de conceito são demonstrados. Alguns construtores estão relacionadas com construtores lógicos na lógica de primeira ordem (LPO), com a intersecção, união ou disjunção de conceitos, negação ou complemento de conceitos, a restrição universal e restrição existencial. Outros construtores não têm correspondentes obras em LPO , incluindo restrições sobre os papéis, por exemplo, inversa, transitividade e funcionalidade.

Notação[editar | editar código-fonte]

Seja C e D conceitos, a e b indivíduos, e R uma função.

Notação convencional
Símbolo Descrição Exemplo leitura
\top ⊤ é um conceito especial com cada indivíduo como uma instância \top top
\bot conceito vazio \bot bottom
\sqcap Intersecção ou conjunção de conceitos C \sqcap D C e D
\sqcup União ou disjunção de conceitos C \sqcup D C ou D
\neg negação ou complemento de conceitos \neg C não C
\forall Restrição universal \forall R.C todo R-sucessor é um C
\exists Restrição existencial \exists R.C Existe um R-sucessor em C
\sqsubseteq Conceitos inclusos C \sqsubseteq D C está contido em D
\equiv Conceitos equivalentes C \equiv D C é equivalente a D
\dot = Conceitos definidos C \dot = D C é definido como sendo equivalente a D
 : Conceitos afirmados a : C a é um C
 : Papel afirmados (a,b) : R a está R-relacionado com b

A descrição lógica LCA[editar | editar código-fonte]

O protótipo LD Linguagem de conceito atributiva com Complementos (\mathcal{ALC}) foi introduzido por Manfred Schmidt-SCHAUSS e Gert Smolka, em 1991, e é a base de muitos LD mais expressivo. As definições a seguir seguir o tratamento em Baader et al.

Tome N_C, N_R e N_O como sendo (respectivamente) conjuntos de nomes de conceito (também conhecidos como conceitos atômicos), nomes de funções e nomes individuais (também conhecidos como indivíduos, nominais ou objetos). Em seguida, o ordenado triplo (N_C, N_R, N_O ) é a assinatura.

Conceitos[editar | editar código-fonte]

O conjuntos de conceitos \mathcal{ALC} é o menor conjunto de tal modo que:

  • A seguir estão os conceitos:
    • \top (top é um conceito)
    • \bot (bottom é um conceito)
    • Todo A \in N_C (todo conceito atômico é um conceito)
  • Se C e D são conceitos e R \in N_R então segue que são conceitos:
    • C\sqcap D (a intersecção de dois conceitos é um conceito)
    • C\sqcup D (a união de dois conceitos é um conceito)
    • \neg C (o complemento de um conceito é um conceito)
    • \forall R.C (A restrição universal de um conceito por um papel é um conceito)
    • \exists R.C (A restrição existencial de um conceito por um papel é um conceito)

Axiomas terminológicos[editar | editar código-fonte]

Uma inclusão geral de conceitos (General Concept Inclusion - GCI) tem a forma C \sqsubseteq D onde C e D são conceitos. Escreva C \equiv D quando C \sqsubseteq D and D \sqsubseteq C. Uma TBox é qualquer conjunto finito de GCIs.

Axioma de afirmação[editar | editar código-fonte]

  • Uma asserção de conceito é uma afirmação da forma a : C onde a \in N_O e C é um conceito.
  • Uma afirmação de papel é uma declaração da forma (a,b) : R onde a, b \in N_O e R é um papel.

Uma 'ABox' é um conjunto finito de axiomas de asserção.

Base de conhecimento[editar | editar código-fonte]

A base de conhecimento (BC) é um par ordenado (\mathcal{T}, \mathcal{A}) para TBox \mathcal{T} e ABox \mathcal{A}.


Semântica[editar | editar código-fonte]

A semântica da lógica descritiva é definida interpretando conceitos como conjuntos de indivíduos e papéis como conjuntos de pares ordenados de indivíduos. Esses indivíduos são tipicamente assumidos a partir de um determinado domínio. A semântica de conceitos e papéis não-atômicos é, então, definida em termos de conceitos e funções atômicas. Isto é feito por meio de uma definição recursiva semelhante à sintaxe.

A descrição lógica ALC[editar | editar código-fonte]

As seguintes definições seguem o tratamento em Baader et al:

A interpretação terminológica \mathcal{I}=(\Delta^{\mathcal{I}}, \cdot^{\mathcal{I}}) sobre uma assinatura (N_C,N_R,N_O) consiste:

  • um conjunto não-vazio \Delta^{\mathcal{I}} chamado domínio
  • uma função de interpretação \cdot^{\mathcal{I}} que mapeia:
    • cada indivíduo a para um elemento a^{\mathcal{I}} \in \Delta^{\mathcal{I}}
    • cada conceito para um subconjunto de \Delta^{\mathcal{I}}
    • cada conceito para um subconjunto de \Delta^{\mathcal{I}}  \times \Delta^{\mathcal{I}}

de tal modo que:

  • \top^{\mathcal{I}} = \Delta^{\mathcal{I}}
  • \bot^{\mathcal{I}} = \emptyset
  • (C \sqcup D)^{\mathcal{I}} = C^{\mathcal{I}} \cup D^{\mathcal{I}}união forma disjunção
  • (C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}} intersecção forma disjunção
  • (\neg C)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus C^{\mathcal{I}} complementos forma negação
  • (\forall R.C)^{\mathcal{I}} = \{x \in \Delta^{\mathcal{I}} | \texttt{for} \; \texttt{every} \; y, (x,y) \in R^{\mathcal{I}} \;  \texttt{implies} \; y \in C^{\mathcal{I}} \}
  • (\exists R.C)^{\mathcal{I}} = \{x \in \Delta^{\mathcal{I}} | \texttt{there} \; \texttt{exists} \; y, (x,y) \in R^{\mathcal{I}} \; \texttt{and} \; y \in C^{\mathcal{I}}\}

Define \mathcal{I} \models (ler I modelo) como se segue

TBox[editar | editar código-fonte]

  • \mathcal{I} \models C \sqsubseteq D se e somente se C^{\mathcal{I}} \subseteq D^{\mathcal{I}}
  • \mathcal{I} \models \mathcal{T} se e somente se \mathcal{I} \models \Phi para todo \Phi \in \mathcal{T}

ABox[editar | editar código-fonte]

  • \mathcal{I} \models a : C se e somente se a^{\mathcal{I}} \in C^{\mathcal{I}}
  • \mathcal{I} \models (a,b) : R se e somente se (a^{\mathcal{I}},b^{\mathcal{I}}) \in R^{\mathcal{I}}
  • \mathcal{I} \models \mathcal{A} se e somente se \mathcal{I} \models \phi para todo \phi \in \mathcal{A}

Base de conhecimento[editar | editar código-fonte]

Tome \mathcal{K} = (\mathcal{T}, \mathcal{A}) como sendo a base de conhecimento.

  • \mathcal{I} \models \mathcal{K} se e somente se \mathcal{I} \models \mathcal{T} e \mathcal{I} \models \mathcal{A}

Inferência[editar | editar código-fonte]

Problemas de decisão[editar | editar código-fonte]

Além da capacidade de descrever conceitos formalmente, também gostaria de empregar a descrição de um conjunto de conceitos para fazer perguntas sobre os conceitos e exemplos descritos. Os problemas de decisão mais comuns são questões de banco de dados de consulta como básicas como instância de controle (é um caso particular (membro de uma caixa de transporte) um membro de um determinado conceito) e relação de controle (faz uma relação / função manter entre duas instâncias, em outras palavras, faz um tem a propriedade b), e os globais-database-perguntas mais como subsunção (é um conceito um subconjunto de um outro conceito), e o conceito de consistência (que não há contradição entre as definições ou cadeia de definições). O mais operadores inclui uma lógica e em um a mais complicado T-box (tendo ciclos, permitindo conceitos não-atômicas para incluir entre si), geralmente quanto maior a complexidade computacional é para cada um desses problemas.

Relacionamento com outras lógicas[editar | editar código-fonte]

Lógica de primeira ordem[editar | editar código-fonte]

Muitos modelos de Lógica de descrição (LDS) são fragmentos decidíveis da lógica de primeira ordem (FOL).e geralmente são fragmentos da lógica de duas variáveis​​. Alguns LDs agora incluem operações (por exemplo, fechamento transitivo de papéis) que permitem a inferência eficiente, mas não podem ser expressos em FOL.

Lógica de descrição difusa[editar | editar código-fonte]

Lógica de descrição difusa combina lógica difusa com LDs. Uma vez que muitos conceitos que são necessários para sistemas inteligentes não têm fronteiras bem definidas, ou critérios bem definidos de filiação, a lógica difusa é necessário para lidar com noções de incerteza e imprecisão. Isto oferece uma motivação para uma generalização da descrição lógica para lidar com conceitos imprecisos e vagos.

Modelo lógico[editar | editar código-fonte]

A Descrição Lógica está relacionado com o - mas desenvolvida de forma independente de - Modelo lógico (ML). Muitos - mas não todos - LD são variantes sintáticas do ML.

Em geral, um objecto corresponde a um mundo possível, um conceito corresponde a uma proposição modal, e um quantificador delimitada em função de um operador modal com o papel como a sua relação de acessibilidade.

Operações em papéis (como composição, inversão, etc) correspondem às operações modais utilizados na lógica dinâmica.

Exemplos[editar | editar código-fonte]

Variantes sintáticas
LD ML
\mathcal{ALC} K[3]
\mathcal{SR} PDL[13]
\mathcal{FSR} DPDL (PDL determinístico)[13]
\mathcal{TSL}, or \mathcal{SRI} PDL[13]
\mathcal{FSL}, or \mathcal{FSRI} DPDL (PDL determinístico)[13]

Lógica de descrição Temporal[editar | editar código-fonte]

Lógica de descrição Temporal representa - e permite raciocinar sobre - conceitos dependentes de tempo e muitas abordagens diferentes para este problema. Por exemplo, uma descrição lógica pode ser combinada com uma lógica temporal modal como lógica temporal linear.


Notas[editar | editar código-fonte]

  1. (1987) "Expressiveness and tractability in knowledge representation and reasoning". Computational Intelligence.
  2. Distributed Reasoning with EL++ Using MapReduce Technical Report, Kno.e.sis Center, Wright State University, Dayton, Ohio (2010). Visitado em 2011-12-25.
  3. a b c d e f g h Franz Baader, Ian Horrocks, and Ulrike Sattler Chapter 3 Description Logics. In Frank van Harmelen, Vladimir Lifschitz, and Bruce Porter, editors, Handbook of Knowledge Representation. Elsevier, 2007.
  4. a b doi:10.1007/11814771_26
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  5. doi:10.1016/j.websem.2007.03.004
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  6. doi:10.1109/5254.920598
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  7. Ian Horrocks and Peter F. Patel-Schneider The Generation of DAML+OIL. In Proceedings of the 2001 Description Logic Workshop (LD 2001), volume 49 of CEUR <http://ceur-ws.org/>, pages 30–35, 2001.
  8. Web Ontology Working Group Charter, 2003
  9. W3C Press Release, 2004
  10. a b Predefinição:Cite DOI
  11. OWL Working Group Charter, 2007
  12. Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph. Foundations of Semantic Web Technologies. [S.l.]: CRCPress, August 25, 2009. ISBN 1-4200-9050-X.
  13. Erro de citação: Tag <ref> inválida; não foi fornecido texto para as refs chamadas CTTL

Referências[editar | editar código-fonte]

Leitura Complementar[editar | editar código-fonte]