Lógica de descrição – Wikipédia, a enciclopédia livre
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:
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 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:
Linguagem atributiva. Esta é a linguagem base que permite: | |
| |
Quadro de linguagem de descrição de base,[1] permite: | |
| |
Permite: | |
|
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ções
[editar | editar código-fonte]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] |
Exemplos
[editar | editar código-fonte]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ó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 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.
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.
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 LCA
[editar | editar código-fonte]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.
Conceitos
[editar | editar código-fonte]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ógicos
[editar | editar código-fonte]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ção
[editar | editar código-fonte]- 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 conhecimento
[editar | editar código-fonte]A base de conhecimento (BC) é um par ordenado para TBox e ABox .
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 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
TBox
[editar | editar código-fonte]- se e somente se
- se e somente se para todo
ABox
[editar | editar código-fonte]- se e somente se
- se e somente se
- se e somente se para todo
Base de conhecimento
[editar | editar código-fonte]Tome como sendo a base de conhecimento.
- se e somente se e
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]LD | ML |
---|---|
K[3] | |
PDL[14] | |
DPDL (PDL determinístico)[14] | |
PDL[14] | |
DPDL (PDL determinístico)[14] |
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]- ↑ Levesque, Hector J.; Brachmann, Ronald J. (1987). «Expressiveness and tractability in knowledge representation and reasoning». Computational Intelligence (3)
- ↑ 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
- ↑ 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.
- ↑ a b Tsarkov, Dmitry; Horrocks, Ian (2006). 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
- ↑ 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
- ↑ 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
- ↑ 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.
- ↑ Web Ontology Working Group Charter, 2003
- ↑ W3C Press Release, 2004
- ↑ 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
- ↑ I. Horrocks; et al. «From SHIQ and RDF to OWL: the making of a Web Ontology Language». Journal of Web Semantics. doi:10.1016/j.websem.2003.07.001
- ↑ OWL Working Group Charter, 2007
- ↑ 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
- ↑ a b c d Schild, Klaus. «Correspondence theory for terminological logics: Preliminary Report» (PDF). KIT Report 91. KIT-BACK. Consultado em 25 de outubro de 2012
Referências
[editar | editar código-fonte]- F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider: The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK, 2003. ISBN 0-521-78176-0
- Ian Horrocks, Ulrike Sattler: Ontology Reasoning in the SHOQ(D) Description Logic, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.
- D. Fensel, F. van Harmelen, I. Horrocks, D. McGuinness, and P. F. Patel-Schneider: OIL: An Ontology Infrastructure for the Semantic Web. IEEE Intelligent Systems, 16(2):38-45, 2001.
- Ian Horrocks and Peter F. Patel-Schneider: The Generation of DAML+OIL. In Proceedings of the 2001 Description Logic Workshop (DL 2001), volume 49 of CEUR <http://ceur-ws.org/>, pages 30–35, 2001.
- Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen: From SHIQ and RDF to OWL: The Making of a Web Ontology Language. Journal of Web Semantics, 1(1):7-26, 2003.
- Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter Patel-Schneider, and Ulrike Sattler: OWL 2: The next step for OWL. Journal of Web Semantics, 6(4):309-322, November 2008.
- 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.
- Alessandro Artale and Enrico Franconi: Temporal Description Logics. In Handbook of Temporal Reasoning in Artificial Intelligence, 2005.
- Web Ontology (WebONT) Working Group Charter. W3C, 2003
- World Wide Web Consortium Issues RDF and OWL Recommendations. Press Release. W3C, 2004.
- OWL Working Group Charter. W3C, 2007.
- OWL 2 Connects the Web of Knowledge with the Web of Data. Press Release. W3C, 2009.
Leitura Complementar
[editar | editar código-fonte]- Markus Krötzsch, František Simančík, Ian Horrocks: A Description Logic Primer. CoRR abs/1201.4089. 2012. (PDF) A very first introduction for readers without a formal logic background.
- Sebastian Rudolph: Foundations of Description Logics. In Reasoning Web: Semantic Technologies for the Web of Data, 7th International Summer School, volume 6848 of Lecture Notes in Computer Science, pages 76–136. Springer, 2011. (springerlink)Introductory text with a focus on modelling and formal semantics. There are also slides.
- Franz Baader: Description Logics. In Reasoning Web: Semantic Technologies for Information Systems, 5th International Summer School, volume 5689 of Lecture Notes in Computer Science, pages 1–39. Springer, 2009. (springerlink) Introductory text with a focus on reasoning and language design, and an extended historical overview.
- Enrico Franconi: Introduction to Description Logics. Course materials. Faculty of Computer Science, Free University of Bolzano, Italy, 2002. Lecture slides and many literature pointers, somewhat dated.
- Ian Horrocks: Ontologies and the Semantic Web. Communications of the ACM, 51(12):58-67, December 2008. A general overview of knowledge representation in Semantic Web technologies.