Lógica padrão - Default logic

A lógica padrão é uma lógica não monotônica proposta por Raymond Reiter para formalizar o raciocínio com suposições padrão.

A lógica padrão pode expressar fatos como “por padrão, algo é verdadeiro”; em contraste, a lógica padrão só pode expressar que algo é verdadeiro ou falso. Isso é um problema porque o raciocínio frequentemente envolve fatos que são verdadeiros na maioria dos casos, mas nem sempre. Um exemplo clássico é: “pássaros normalmente voam”. Esta regra pode ser expressa na lógica padrão por "todos os pássaros voam", o que é inconsistente com o fato de que os pinguins não voam, ou por "todos os pássaros que não são pinguins e nem avestruzes e ... voam", o que requer todos exceções à regra a ser especificada. A lógica padrão visa formalizar regras de inferência como esta sem mencionar explicitamente todas as suas exceções.

Sintaxe da lógica padrão

Uma teoria padrão é um par . W é um conjunto de fórmulas lógicas, chamadas de teoria de fundo , que formalizam os fatos que são conhecidos com certeza. D é um conjunto de regras padrão , cada uma tendo a forma: ${\ displaystyle \ langle W, D \ rangle}$

${\ displaystyle {\ frac {\ mathrm {Pré-requisito: Justificativa} _ {1}, \ dots, \ mathrm {Justificativa} _ {n}} {\ mathrm {Conclusão}}}}$

De acordo com esse padrão, se acreditarmos que o Pré - requisito é verdadeiro e cada um deles é consistente com nossas crenças atuais, somos levados a acreditar que a Conclusão é verdadeira. ${\ displaystyle \ mathrm {Justificativa} _ {n}}$

As fórmulas lógicas em W e todas as fórmulas em um default foram originalmente consideradas fórmulas lógicas de primeira ordem , mas podem ser fórmulas em uma lógica formal arbitrária. O caso em que são fórmulas em lógica proposicional é um dos mais estudados.

Exemplos

A regra padrão "pássaros normalmente voam" é formalizada pelo seguinte padrão:

${\ displaystyle D = \ left \ {{\ frac {\ mathrm {Bird} (X): \ mathrm {Flies} (X)} {\ mathrm {Flies} (X)}} \ right \}}$

Essa regra significa que, "se X é um pássaro, e pode-se supor que ele voa, então podemos concluir que ele voa". Uma teoria de fundo contendo alguns fatos sobre os pássaros é a seguinte:

${\ displaystyle W = \ {\ mathrm {Pássaro} (\ mathrm {Condor}), \ mathrm {Pássaro} (\ mathrm {Pinguim}), \ neg \ mathrm {Moscas} (\ mathrm {Pinguim}), \ mathrm {Moscas} (\ mathrm {Bee}) \}}$ .

De acordo com esta regra padrão, um condor voa porque a pré-condição Pássaro (Condor) é verdadeira e a justificativa Voa (Condor) não é inconsistente com o que é conhecido atualmente. Pelo contrário, Pássaro (Pinguim) não permite concluir Moscas (Pinguim) : mesmo que a pré-condição do padrão Pássaro (Pinguim) seja verdadeira, a justificativa Moscas (Pinguim) é inconsistente com o que é conhecido. A partir dessa teoria de fundo e desse default, Bird (Bee) não pode ser concluído porque a regra default só permite derivar Flies ( X ) de Bird ( X ) , mas não vice-versa. Derivar os antecedentes de uma regra de inferência das consequências é uma forma de explicação das consequências e é o objetivo do raciocínio abdutivo .

Uma suposição padrão comum é que o que não é conhecido como verdadeiro é considerado falso. Isto é conhecido como o Assunção Closed-Mundial , e é formalizada na lógica padrão usando um padrão como a seguinte para cada fato F .

${\ displaystyle {\ frac {: {\ neg} F} {{\ neg} F}}}$

Por exemplo, a linguagem de computador Prolog usa uma espécie de suposição padrão ao lidar com a negação: se um átomo negativo não pode ser provado como verdadeiro, então ele é considerado falso. Note, entretanto, que Prolog usa a chamada negação como falha : quando o interpretador tem que avaliar o átomo , ele tenta provar que F é verdadeiro e concluir que é verdadeiro se falhar. Na lógica padrão, em vez disso, um padrão tendo como justificativa só pode ser aplicado se for consistente com o conhecimento atual. ${\ displaystyle \ neg F}$${\ displaystyle \ neg F}$${\ displaystyle \ neg F}$${\ displaystyle \ neg F}$

Restrições

Um padrão é categórico ou livre de pré-requisitos se não tiver pré-requisitos (ou, equivalentemente, se seu pré-requisito for tautológico ). Uma inadimplência é normal se tiver uma única justificativa que seja equivalente à sua conclusão. Um padrão é supernormal se for categórico e normal. Um default é seminormal se todas as suas justificativas implicam em sua conclusão. Uma teoria padrão é chamada de categórica, normal, supernormal ou seminormal se todos os padrões que ela contém são categóricos, normal, supernormal ou seminormal, respectivamente.

Semântica da lógica padrão

Uma regra padrão pode ser aplicada a uma teoria se sua pré-condição for acarretada pela teoria e suas justificativas forem todas consistentes com a teoria. A aplicação de uma regra padrão leva ao acréscimo de sua consequência à teoria. Outras regras padrão podem então ser aplicadas à teoria resultante. Quando a teoria é tal que nenhum outro padrão pode ser aplicado, a teoria é chamada de extensão da teoria do padrão. As regras padrão podem ser aplicadas em ordem diferente e isso pode levar a extensões diferentes. O exemplo do diamante Nixon é uma teoria padrão com duas extensões:

${\ displaystyle \ left \ langle \ left \ {{\ frac {\ mathrm {Republicano} (X): \ neg \ mathrm {Pacifista} (X)} {\ neg \ mathrm {Pacifista} (X)}}, { \ frac {\ mathrm {Quaker} (X): \ mathrm {Pacifista} (X)} {\ mathrm {Pacifista} (X)}} \ direita \}, \ esquerda \ {\ mathrm {Republicano} (\ mathrm { Nixon}), \ mathrm {Quaker} (\ mathrm {Nixon}) \ right \} \ right \ rangle}$

Como Nixon é republicano e quacre , os dois padrões podem ser aplicados. No entanto, a aplicação da primeira inadimplência leva à conclusão de que Nixon não é pacifista, o que torna a segunda inadimplência não aplicável. Da mesma forma, aplicando a segunda inadimplência obtemos que Nixon é pacifista, tornando a primeira inadimplência não aplicável. Esta teoria padrão particular tem, portanto, duas extensões, uma em que Pacifist (Nixon) é verdadeiro e outra em que Pacifist (Nixon) é falso.

A semântica original da lógica padrão era baseada no ponto fixo de uma função. A seguir está uma definição algorítmica equivalente. Se um padrão contém fórmulas com variáveis ​​livres, ele é considerado como representando o conjunto de todos os padrões obtidos atribuindo um valor a todas essas variáveis. Um default é aplicável a uma teoria proposicional T se e todas as teorias forem consistentes. A aplicação desse padrão a T leva à teoria . Uma extensão pode ser gerada aplicando o seguinte algoritmo: ${\ displaystyle {\ frac {\ alpha: \ beta _ {1}, \ ldots, \ beta _ {n}} {\ gamma}}}$${\ displaystyle T \ models \ alpha}$${\ displaystyle T \ cup \ {\ beta _ {i} \}}$${\ displaystyle T \ cup \ {\ gamma \}}$

T = W         /* current theory */
A = 0         /* set of defaults applied so far */
 
              /* apply a sequence of defaults */
while there is a default d that is not in A and is applicable to T
    add the consequence of d to T
    add d to A
 
              /* final consistency check */
if 
    for every default d in A
        T is consistent with all justifications of d
then
    output T

Este algoritmo é não-determinística , tal como vários padrões podem, alternativamente, ser aplicada a uma determinada teoria T . No exemplo do diamante Nixon, a aplicação do primeiro padrão leva a uma teoria para a qual o segundo padrão não pode ser aplicado e vice-versa. Como resultado, duas extensões são geradas: uma em que Nixon é pacifista e outra em que Nixon não é pacifista.

A verificação final da consistência das justificativas de todos os padrões que foram aplicados implica que algumas teorias não têm extensões. Em particular, isso acontece sempre que essa verificação falha para todas as sequências possíveis de padrões aplicáveis. A seguinte teoria padrão não tem extensão:

${\ displaystyle \ left \ langle \ left \ {{\ frac {: A (b)} {\ neg A (b)}} \ right \}, \ emptyset \ right \ rangle}$

Uma vez que é consistente com a teoria de fundo, o padrão pode ser aplicado, levando à conclusão de que é falsa. Este resultado, no entanto, mina a suposição feita para a aplicação do primeiro default. Conseqüentemente, essa teoria não tem extensões. ${\ displaystyle A (b)}$${\ displaystyle A (b)}$

Em uma teoria de default normal, todos os default são normais: cada default tem a forma . Uma teoria de default normal tem garantia de pelo menos uma extensão. Além disso, as extensões de uma teoria padrão normal são mutuamente inconsistentes, ou seja, inconsistentes entre si. ${\ displaystyle {\ frac {\ phi: \ psi} {\ psi}}}$

Entailment

Uma teoria padrão pode ter zero, uma ou mais extensões. A inclusão de uma fórmula a partir de uma teoria padrão pode ser definida de duas maneiras:

Cético

uma fórmula é acarretada por uma teoria padrão se ela é acarretada por todas as suas extensões;

Crédulo

uma fórmula é acarretada por uma teoria padrão se for atribuída por pelo menos uma de suas extensões.

Assim, a teoria do exemplo do diamante de Nixon tem duas extensões, uma na qual Nixon é um pacifista e outra na qual ele não é um pacifista. Conseqüentemente, nem Pacifista (Nixon) nem ¬Pacifista (Nixon) são implicados com ceticismo, enquanto ambos estão implicitamente implicados. Como mostra este exemplo, as consequências crédulas de uma teoria padrão podem ser inconsistentes entre si.

Regras de inferência padrão alternativas

As seguintes regras alternativas de inferência para lógica padrão são todas baseadas na mesma sintaxe do sistema original.

Justificado

difere do original em que um default não é aplicado se assim o conjunto T tornar-se inconsistente com uma justificativa de um default aplicado;

Conciso

um default é aplicado apenas se sua consequência ainda não for acarretada por T (a definição exata é mais complicada do que esta; esta é apenas a ideia principal por trás dela);

Constrangido

uma inadimplência é aplicada somente se o conjunto composto pela teoria de background, as justificativas de todas as inadimplências aplicadas e as consequências de todas as inadimplências aplicadas (incluindo esta) for consistente;

Racional

semelhante à lógica padrão restrita, mas a consequência do padrão a ser adicionado não é considerada na verificação de consistência;

Cauteloso

padrões que podem ser aplicados, mas são conflitantes entre si (como os do exemplo do diamante Nixon) não são aplicados.

As versões justificadas e restritas da regra de inferência atribuem pelo menos uma extensão a cada teoria padrão.

Variantes da lógica padrão

As seguintes variantes da lógica padrão diferem da original na sintaxe e na semântica.

Variantes assercionais

Uma asserção é um par composto de uma fórmula e um conjunto de fórmulas. Esse par indica que p é verdadeiro, enquanto as fórmulas foram consideradas consistentes para provar que p é verdadeiro. Uma teoria padrão assertiva é composta de uma teoria assertiva (um conjunto de fórmulas assertivas) chamada de teoria de fundo e um conjunto de padrões definidos como na sintaxe original. Sempre que um default é aplicado a uma teoria assertiva, o par composto de sua consequência e seu conjunto de justificativas é adicionado à teoria. A semântica a seguir usa teorias assertivas: ${\ displaystyle \ langle p: \ {r_ {1}, \ ldots, r_ {n} \} \ rangle}$${\ displaystyle r_ {1}, \ ldots, r_ {n}}$

• Lógica padrão cumulativa
• Compromisso com suposições lógicas padrão
• Lógica quase padrão

Extensões fracas

em vez de verificar se as pré-condições são válidas na teoria composta pela teoria de fundo e as consequências dos padrões aplicados, as pré-condições são verificadas quanto à validade na extensão que será gerada; em outras palavras, o algoritmo para gerar extensões começa adivinhando uma teoria e usando-a no lugar da teoria de fundo; o que resulta do processo de geração de extensão é na verdade uma extensão apenas se for equivalente à teoria adivinhada no início. Essa variante da lógica padrão está relacionada, em princípio, à lógica autoepistêmica , onde uma teoria tem o modelo no qual x é verdadeiro apenas porque, assumindo verdadeiro, a fórmula apóia a suposição inicial. ${\ displaystyle \ Box x \ rightarrow x}$${\ displaystyle \ Box x}$${\ displaystyle \ Box x \ rightarrow x}$

Lógica padrão disjuntiva

a consequência de um padrão é um conjunto de fórmulas em vez de uma única fórmula. Sempre que o padrão é aplicado, pelo menos uma de suas consequências é escolhida de forma não determinística e tornada verdadeira.

Prioridades em padrões

a prioridade relativa dos padrões pode ser especificada explicitamente; entre os padrões aplicáveis ​​a uma teoria, apenas um dos mais preferidos pode ser aplicado. Algumas semânticas da lógica padrão não requerem que as prioridades sejam especificadas explicitamente; em vez disso, padrões mais específicos (aqueles que são aplicáveis ​​em menos casos) são preferidos aos menos específicos.

Variante estatística

um padrão estatístico é um padrão com um limite superior anexado em sua frequência de erro; em outras palavras, o padrão é considerado uma regra de inferência incorreta no máximo naquela fração de vezes em que é aplicada.

Traduções

Teorias padrão podem ser traduzidas em teorias em outras lógicas e vice-versa. As seguintes condições nas traduções foram consideradas:

Preservação de consequências

as teorias original e traduzida têm as mesmas consequências (proposicionais);

Fiel

esta condição só faz sentido ao traduzir entre duas variantes da lógica padrão ou entre a lógica padrão e uma lógica na qual existe um conceito semelhante à extensão, por exemplo, modelos na lógica modal ; uma tradução é fiel se existe um mapeamento (normalmente, uma bijeção) entre as extensões (ou modelos) das teorias original e traduzida;

Modular

uma tradução da lógica padrão para outra lógica é modular se os padrões e a teoria de fundo podem ser traduzidos separadamente; além disso, a adição de fórmulas à teoria de fundo apenas leva à adição de novas fórmulas ao resultado da tradução;

Mesmo Alfabeto

as teorias originais e traduzidas são construídas no mesmo alfabeto;

Polinomial

o tempo de execução da tradução ou o tamanho da teoria gerada devem ser polinomiais no tamanho da teoria original.

Normalmente, as traduções devem ser fiéis ou, pelo menos, preservadoras das consequências, enquanto as condições de modularidade e o mesmo alfabeto às vezes são ignoradas.

A traduzibilidade entre a lógica padrão proposicional e as seguintes lógicas foram estudadas:

• lógica proposicional clássica;
• lógica autoepistêmica;
• lógica padrão proposicional restrita a teorias seminormais;
• semântica alternativa de lógica padrão;
• circunscrição.

As traduções existem ou não dependendo das condições impostas. As traduções da lógica padrão proposicional para a lógica proposicional clássica nem sempre podem gerar uma teoria proposicional de tamanho polinomial, a menos que a hierarquia polinomial entre em colapso. Traduções para a lógica autoepistêmica existem ou não dependendo da necessidade de modularidade ou do uso do mesmo alfabeto.

Complexidade

A complexidade computacional dos seguintes problemas sobre a lógica padrão é conhecida:

Existência de extensões

decidir se uma teoria padrão proposicional tem pelo menos uma extensão é -completa; ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Envolvimento cético

decidir se uma teoria padrão proposicional ceticamente implica uma fórmula proposicional é -completo; ${\ displaystyle \ Pi _ {2} ^ {P}}$

Envolvimento crédulo

decidir se uma teoria padrão proposicional acarreta credulamente uma fórmula proposicional é -completo; ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Verificação de extensão

decidir se uma fórmula proposicional é equivalente a uma extensão de uma teoria default proposicional é -completa; ${\ displaystyle \ Delta _ {2} ^ {P [\ log]}}$

Verificação de modelo

decidir se uma interpretação proposicional é um modelo de uma extensão de uma teoria default proposicional é -completo. ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Implementações

Quatro sistemas que implementam lógicas padrão são DeReS , XRay , GADeL e Catala .

Veja também

• Programação do conjunto de respostas
• Lógica derrotável
• Lógica não monotônica

Referências

• G. Antoniou (1999). Um tutorial sobre lógicas padrão. ACM Computing Surveys , 31 (4): 337-359.
• M. Cadoli, FM Donini, P. Liberatore e M. Schaerf (2000). Eficiência espacial de formalismos de representação de conhecimento proposicional . Journal of Artificial Intelligence Research , 13: 1-31.
• P. Cholewinski, V. Marek e M. Truszczynski (1996). Sistema de raciocínio padrão DeReS. Em Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR'96) , páginas 518-528.
• J. Delgrande e T. Schaub (2003). Sobre a relação entre a lógica padrão de Reiter e suas (principais) variantes. Na Sétima Conferência Europeia sobre Abordagens Simbólicas e Quantitativas para Raciocinar com Incerteza (ECSQARU 2003) , páginas 452-463.
• JP Delgrande, T. Schaub e WK Jackson (1994). Abordagens alternativas para a lógica padrão. Artificial Intelligence , 70: 167-237.
• G. Gottlob (1992). Resultados de complexidade para lógicas não monotônicas. Journal of Logic and Computation , 2: 397-425.
• G. Gottlob (1995). Traduzindo a lógica padrão em lógica autoepistêmica padrão . Journal of the ACM , 42: 711-740.
• T. Imielinski (1987). Resultados na tradução de padrões para a circunscrição. Artificial Intelligence , 32: 131-146.
• T. Janhunen (1998). Sobre a intertradução de lógicas autoepistêmicas, default e prioritárias e circunscrição paralela . Em Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA'98) , páginas 216-232.
• T. Janhunen (2003). Avaliando o efeito da semi-normalidade na expressividade das inadimplências. Artificial Intelligence , 144: 233-250.
• HE Kyburg e CM. Teng (2006). Inferência Estatística e Lógica Não Monotônica. Computational Intelligence , 22 (1): 26-51.
• P. Liberatore e M. Schaerf (1998). A complexidade da verificação de modelo para lógicas de default proposicionais. Em Proceedings of the Thirteenth European Conference on Artificial Intelligence (ECAI'98) , páginas 18–22.
• W. Lukaszewicz (1988). Considerações sobre a lógica padrão: uma abordagem alternativa. Computational Intelligence , 4 (1): 1-16.
• W. Marek e M. Truszczynski (1993). Lógica Não Monotônica: Raciocínio Dependente do Contexto . Springer.
• A. Mikitiuk e M. Truszczynski (1995). Lógicas padrão restritas e racionais . Em Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95) , páginas 1509-1517.
• P. Nicolas, F. Saubion e I. Stéphan (2001). Heurísticas para um sistema de raciocínio lógico padrão . International Journal on Artificial Intelligence Tools , 10 (4): 503-523.
• R. Reiter (1980). Uma lógica para o raciocínio padrão. Artificial Intelligence , 13: 81-132.
• T. Schaub, S. Brüning e P. Nicolas (1996). XRay: Um provador de teorema de tecnologia de prólogo para raciocínio padrão: uma descrição do sistema. Em Anais da Décima Terceira Conferência Internacional sobre Dedução Automatizada (CADE'96) , páginas 293-297.
• G. Wheeler (2004). Uma lógica padrão limitada por recursos. Em Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR-04) , Whistler, British Columbia, 416-422.
• G. Wheeler e C. Damasio (2004). Uma implementação de lógica estatística padrão . Em Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA 2004) , LNCS Series, Springer, páginas 121-133.

links externos

• Schmidt, Charles F. RCI.Rutgers.edu , Default Logic. Recuperado em 10 de agosto de 2004.
• Ramsay, Allan (1999). UMIST.ac.uk , Lógica padrão. Recuperado em 10 de agosto de 2004.
• Stanford.edu , Defeasible raciocínio, Stanford Encyclopedia of Philosophy .