Lógica de descrição

(Redirecionado de Lógicas de descrição)

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çãoEditar

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.

NomenclaturaEditar

Diferenças de Lógica de Primeira OrdemEditar

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 terminologia de Lógica de primeira ordem [LPO] na descrição da modelagem conceitual do ambiente (diagrama de representação), apesar usar a lógica de descrição na implementação.

Convenção de nomenclaturaEditar

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:

  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
  Quadro de linguagem de descrição de base,[1] permite:
  • Interseção conceitual
  • Restrições universais
  • Quantificação existencial limitada
  • Restrição de papel
  Permite:
  • Interseção conceitual
  • Restrições existenciais (de quantificação existencial completa)

Seguido por qualquer uma das seguintes extensões:

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

ExceçõesEditar

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

  Uma abreviação para   com papéis transitivos.
  A sub-linguagem de  , que é obtido por não permitir restrição papel. Isso é equivalente a   sem negação atômica.
  A sub-linguagem de  , que é obtido, não permitindo quantificação existencial limitada.
  Torna-se  .[2]

ExemplosEditar

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

Um outro exemplo, a descrição lógica   é a lógica   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   pode ser referido como   e abreviaturas são feitas sempre que possível,   é usado em vez do equivalente  .

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

OWL 2 fornece a expressividade de  , OWL-LD é baseado em  , e para OWL-Lite é  .

HistóriaEditar

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 conhecimentoEditar

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ânticaEditar

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   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   de DL[10] com OWL LD e OWL-Lite baseadas em   and   respectivamente.[11]

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

ModelagemEditar

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 formalEditar

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.

SintaxeEditar

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çãoEditar

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

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

A descrição lógica LCAEditar

O protótipo LD Linguagem de conceito atributiva com Complementos ( ) 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  ,   e   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 ( ,  ,   ) é a assinatura.

ConceitosEditar

O conjuntos de conceitos   é o menor conjunto de tal modo que:

  • A seguir estão os conceitos:
    •   (top é um conceito)
    •   (bottom é um conceito)
    • Todo   (todo conceito atômico é um conceito)
  • Se   e   são conceitos e   então segue que são conceitos:
    •   (a intersecção de dois conceitos é um conceito)
    •   (a união de dois conceitos é um conceito)
    •   (o complemento de um conceito é um conceito)
    •   (A restrição universal de um conceito por um papel é um conceito)
    •   (A restrição existencial de um conceito por um papel é um conceito)

Axiomas terminológicosEditar

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

Axioma de afirmaçãoEditar

  • Uma asserção de conceito é uma afirmação da forma   onde   e C é um conceito.
  • Uma afirmação de papel é uma declaração da forma   onde   e R é um papel.

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

Base de conhecimentoEditar

A base de conhecimento (BC) é um par ordenado   para TBox   e ABox  .


SemânticaEditar

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 ALCEditar

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

A interpretação terminológica   sobre uma assinatura   consiste:

  • um conjunto não-vazio   chamado domínio
  • uma função de interpretação   que mapeia:
    • cada indivíduo   para um elemento  
    • cada conceito para um subconjunto de  
    • cada conceito para um subconjunto de  

de tal modo que:

  •  
  •  
  •  união forma disjunção
  •   intersecção forma disjunção
  •  complementos forma negação
  •  
  •  

Define   (ler I modelo) como se segue

TBoxEditar

  •   se e somente se  
  •   se e somente se   para todo  

ABoxEditar

  •   se e somente se  
  •   se e somente se  
  •   se e somente se   para todo  

Base de conhecimentoEditar

Tome   como sendo a base de conhecimento.

  •   se e somente se   e  

InferênciaEditar

Problemas de decisãoEditar

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ógicasEditar

Lógica de primeira ordemEditar

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 difusaEditar

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ógicoEditar

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.

ExemplosEditar

Variantes sintáticas
LD ML
  K[3]
  PDL[14]
  DPDL (PDL determinístico)[14]
  PDL[14]
  DPDL (PDL determinístico)[14]

Lógica de descrição TemporalEditar

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.


NotasEditar

  1. Levesque, Hector J.; Brachmann, Ronald J. (1987). «Expressiveness and tractability in knowledge representation and reasoning». Computational Intelligence (3) 
  2. Maier, Frederick; Mutharaju, Raghava; Hitzler, Pascal (2010). «Distributed Reasoning with EL++ Using MapReduce» (PDF). Technical Report, Kno.e.sis Center, Wright State University, Dayton, Ohio. Consultado em 25 de dezembro de 2011 
  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 Tsarkov, Dmitry; Horrocks, Ian (2006-08-17). Ulrich, ed. FaCT++ Description Logic Reasoner: System Description. [S.l.]: Springer Berlin Heidelberg. p. 292-297. ISBN 978-3-540-37187-8. doi:10.1007/11814771_26  Verifique data em: |ano= (ajuda)
  5. Sirin, Evren; Bijan (1 de junho de 2007). «Pellet: A practical OWL-DL reasoner». Web Semantics: Science, Services and Agents on the World Wide Web. 5 (2): 51-53. doi:10.1016/j.websem.2007.03.004 
  6. Fensel, D.; F. (1 de março de 2001). «OIL: an ontology infrastructure for the Semantic Web». IEEE Intelligent Systems. 16 (2): 38-45. ISSN 1541-1672. doi:10.1109/5254.920598 
  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. Horrocks, Ian; Peter F. (1 de dezembro de 2003). «From SHIQ and RDF to OWL: the making of a Web Ontology Language». Web Semantics: Science, Services and Agents on the World Wide Web. 1 (1): 7-26. doi:10.1016/j.websem.2003.07.001 
  11. Predefinição:Cite DOI
  12. OWL Working Group Charter, 2007
  13. Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph (25 de agosto de 2009). Foundations of Semantic Web Technologies. [S.l.]: CRCPress. ISBN 1-4200-9050-X 
  14. a b c d Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome CTTL

ReferênciasEditar

Leitura ComplementarEditar