🤖 AI

Hybrid MKNF with Classical Negation in the Rule Component

Este artigo introduz uma extensão das bases de conhecimento Hybrid MKNF que incorpora a negação clássica no componente de regra para melhor suportar o raciocínio negativo explícito em aplicações de segurança crítica, fornecendo definições formais e um procedimento para computar o modelo bem fundamentado.

Autores originais: Arun Raveendran Nair Sheela, Christophe Rey, Florence De Grancey

Publicado 2026-07-24

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Arun Raveendran Nair Sheela, Christophe Rey, Florence De Grancey

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você esteja tentando construir um robô superinteligente que possa entender o mundo. Para fazer isso, você precisa ensinar a ele duas formas de pensar muito diferentes. A primeira é como um bibliotecário rigoroso que conhece cada fato em uma enciclopédia massiva; se o livro não diz que um dragão existe, ele assume que não existe, mas é cuidadoso para declarar apenas o que está explicitamente escrito. A segunda é como um detetive que resolve mistérios procurando por pistas; se o detetive não consegue encontrar evidências de um suspeito, ele pode assumir que o suspeito é inocente, mas apenas até que novas evidências apareçam.

Por anos, cientistas tentaram combinar esses dois pensadores em um único cérebro. Esse campo é chamado de "Representação de Conhecimento", e é a espinha dorsal de como os computadores raciocinam sobre coisas complexas, desde diagnósticos médicos até carros autônomos. O método específico que este artigo analisa é chamado de "Hybrid MKNF". Pense nisso como um casamento entre a enciclopédia do bibliotecário (chamada Lógicas de Descrição) e o livro de regras do detetive (chamado Programação Lógica). O objetivo é permitir que o computador use a enciclopédia para entender a estrutura do mundo enquanto usa o livro de regras para lidar com situações mutáveis, como o tráfego ou o clima. No entanto, há uma pegadinha: o livro de regras do detetive tem um ponto cego. Ele pode dizer "Eu não sei se está chovendo" (porque não há um relatório), mas tem dificuldade em dizer "Eu sei, de fato, que não está chovendo" (porque há um relatório dizendo que o céu está limpo). Isso é um grande problema para sistemas críticos de segurança, como pistas de aeroportos, onde saber que algo definitivamente não está quebrado é tão importante quanto saber que está quebrado.

Este artigo introduz uma atualização para esse livro de regras do detetive, permitindo que ele lide com a "negação clássica" — a capacidade de declarar explicitamente que algo é falso, em vez de apenas supor que é falso porque a informação está ausente. Os autores, Sheela, Rey e De Grancey, propõem um novo sistema chamado hMKNF¬. Eles não apenas sugeriram essa ideia; eles construíram um framework matemático completo para provar que funciona. Eles mostraram como definir as regras para este novo sistema e criaram uma receita passo a passo (um algoritmo) para o computador encontrar a "melhor" resposta, conhecida como o "modelo bem fundamentado" (well-founded model). Eles provaram que este novo método pode lidar com qualquer mistura de fatos e regras, mesmo quando ficam complicados, e forneceram uma maneira de computar a resposta em três fases distintas, garantindo que o robô nunca se confunda com informações ausentes ou pistas contraditórias.

O Novo Superpoder do Detetive

Imagine que você está gerenciando um aeroporto movimentado. Você tem um banco de dados gigante (a "Ontologia") que lista cada pista, cada aeroporto e cada avião. Este banco de dados é o "Bibliotecário". Ele sabe que a Pista 4 está no Aeroporto X. Mas o banco de dados não sabe sobre o clima agora. É aí que o "Detetive" entra. O Detetive usa um conjunto de regras para decidir se uma pista é segura para uso.

No sistema antigo, a regra do Detetive para uma pista segura era assim: "Se a pista estiver em um aeroporto, e não soubermos que ela está fechada, e não soubermos que há um obstáculo, então a pista está aberta."

Aqui está o problema: E se o relatório meteorológico estiver atrasado? O Detetive não sabe se há um obstáculo. No sistema antigo, como o Detetive não consegue encontrar um relatório de obstáculo, ele pode assumir que não há um e dizer: "A pista está aberta!". Mas e se houver uma rocha gigante na pista e o relatório simplesmente ainda não chegou? O sistema antigo cometeria um erro perigoso porque trata "informação ausente" como "prova de ausência".

O artigo argumenta que, em situações críticas de segurança, precisamos que o Detetive seja capaz de dizer: "Eu verifiquei, e eu sei que não há um obstáculo". Isso é chamado de "negação clássica". É a diferença entre dizer "Eu não vi um fantasma" e dizer "Eu verifiquei que não existem fantasmas".

O Fluxo de Trabalho de Três Fases do Detetive

Os autores perceberam que adicionar esse poder de "saber que é falso" torna a matemática muito mais difícil. Você não pode apenas adivinhar a resposta; você tem que ter certeza. Por isso, eles projetaram um processo de três fases para resolver esses enigmas, como um detetive trabalhando em um caso com níveis crescentes de escrutínio.

Fase 1: A Varredura Rápida (Computação de Ponto Fixo)
Primeiro, o sistema executa uma varredura automática rápida. Ele olha para todas as regras e fatos e pergunta: "O que podemos provar com certeza agora?". Ele constró de uma lista de coisas que são definitivamente verdadeiras e coisas que são definitivamente falsas. Se o enigma for simples, esta fase o resolve instantaneamente. O sistema usa um "operador bem fundamentado", que é como uma máquina que continua adicionando novos fatos até que não consiga adicionar mais nada. Se a máquina parar e a resposta fizer sentido, terminamos!

Fase 2: A Cadeia Lógica (Propagação de Unidade)
Às vezes, a Varredura Rápida fica travada. Ela encontra uma regra que diz: "Se A é verdadeiro, então B é falso", mas ela ainda não sabe se A é verdadeiro. No entanto, ela pode saber que, se A fosse verdadeiro, isso quebraria uma regra. Então, o sistema força uma decisão. Ele diz: "Ok, se o fato de A ser verdadeiro causar uma contradição, então A deve ser falso". Isso é chamado de "Propagação de Unidade". É como um detetive percebendo: "Se o mordomo o fez, o relógio estaria quebrado. O relógio não está quebrado, logo, o mordomo não o fez". Esta fase força o sistema a fazer deduções lógicas que a primeira fase perdeu.

Fase 3: O Adivinhar e Verificar (O Último Recurso)
Às vezes, mesmo após a Varredura Rápida e a Cadeia Lógica, o sistema ainda está travado. Há muitas possibilidades e as regras estão muito emaranhadas. É aqui que os autores admitem que, às vezes, você apenas tem que adivinhar. Eles propõem uma fase de "Adivinhar e Verificar" (Guess-and-Check). O sistema tenta todas as combinações possíveis de "Verdadeiro" e "Falso" para as incógnitas restantes. Ele verifica cada palpite para ver se cria uma história estável e consistente. Se encontrar uma história que funcione e que seja a "mais segura" (significando que deixa o mínimo de coisas indefinidas), essa é a resposta. O artigo observa que esta fase é a mais custosa computacionalmente — é como tentar todas as chaves em um chaveiro gigante — mas é necessária para garantir que o sistema nunca perca uma solução válida.

Por Que Isso Importa

Os autores não apenas inventaram um novo jogo; eles construíram uma prova matemática rigorosa de que este novo sistema funciona. Eles mostraram que seu método, hMKNF¬, pode lidar com qualquer mistura de fatos e regras, mesmo as bagunçadas onde as coisas podem se contradizer. Eles provaram que seu processo de três fases sempre encontrará o "modelo bem fundamentado" — a resposta mais confiável e menos arriscada possível.

Eles também compararam seu método com tentativas anteriores. Métodos antigos podiam lidar apenas com casos simples ou exigiam que as regras fossem muito específicas (como lidar apenas com itens individuais, não grupos complexos). Seu novo método é mais flexível e poderoso. No entanto, eles são honestos sobre a compensação: como permitem este poder extra (negação clássica), a fase de "Adivinhar e Verificar" pode demorar muito para problemas muito complexos. Mas para aplicações críticas de segurança, como garantir que um avião não decole de uma pista bloqueada, levar um pouco mais de tempo para ter 100% de certeza é um preço que vale a pena pagar.

Em resumo, este artigo dá aos computadores um novo superpoder: a habilidade de saber explicitamente o que não é verdade, não apenas o que está faltando. Ao combinar uma varredura rápida, uma cadeia lógica e um cuidadoso "adivinhar e verificar", eles construíram um sistema que pode raciocinar sobre o mundo com muito mais precisão e segurança.

Resumo Técnico: MKNF Híbrido com Negação Clássica no Componente de Regras

Definição do Problema
As bases de conhecimento MKNF híbridas integram Lógicas de Descrição (DLs) com Programação Lógica para suportar o raciocínio de mundo aberto e mundo fechado. Embora a semântica de fundação (well-founded semantics) para MKNF híbrido, conforme estabelecido no trabalho anterior [5], permita a computação eficiente em tempo polinomial do modelo de fundação, ela carece de suporte para negação clássica dentro do componente de regras. No arcabouço existente, a informação negativa é expressa exclusivamente através da negação por padrão (not), onde a ausência de uma derivação implica a negação de um fato. Essa limitação é crítica em domínios de segurança crítica, onde o conhecimento negativo explícito é necessário; confiar na ausência de informação pode levar a inferências inseguras (por exemplo, assumir que uma pista está livre simplesmente porque nenhum obstáculo foi relatado). Além disso, as transformações sintáticas existentes para simular a negação clássica são restritas a predicados unários e exigem engenharia de conhecimento adicional. Adicionalmente, os métodos de computação bottom-up anteriores [5] só garantem a produção do modelo de fundação correto para bases MKNF híbridas coerentes; para bases não coerentes, eles podem produzir modelos que diferem da semântica declarativa [7].

Metodologia
Os autores introduzem o hMKNF¬, uma extensão do MKNF híbrido que permite negação clássica irrestrita no componente de regras, mantendo a segurança de DL (DL-safety) para garantir a decidibilidade. A metodologia procede através das seguintes etapas:

Definição Formal: A sintaxe do hMKNF¬ permite regras da forma $K H \leftarrow b^+(r), b^-(r)$ , onde $b^-(r)$ contém átomos da forma not $\xi$ , sendo $\xi$ um átomo $A$ ou sua negação clássica $\neg A$ . A semântica é definida via uma estrutura MKNF de três valores $(I, M, N)$ , onde a avaliação de átomos modais classicamente negados (ex: $K\neg \phi$ e not $\neg \phi$ ) é adaptada da semântica padrão de MKNF.
Caracterização de Três Valores: O artigo adapta o conceito de partições estáveis de [7] para o hMKNF¬. Uma partição parcial $(T, F)$ do conjunto de átomos modais fundamentais é definida, onde $T$ representa átomos verdadeiros e $F$ representa átomos falsos. O modelo de fundação é caracterizado como a partição estável mínima única.
Procedimento de Computação: Um procedimento operacional de três fases é proposto para computar a partição de fundação:
- Fase 1 (Operador de Fundação): Uma computação de ponto fixo iterativa usando um operador de fundação $W_{KG}$ , que combina um operador de derivação ( $T^F_{KG}$ ) e um operador de conjunto infundado ( $F_{KG}$ ). Esta fase computa uma partição parcial $(T_\omega, F_\omega)$ .
- Fase 2 (Propagação de Unidade): Se a Fase 1 não resultar em uma partição estável, um operador de propagação de unidade $E_{KG}$ é aplicado. Esta fase lida com casos onde a cabeça de uma regra é falsa e seu corpo é indefinido, forçando o valor de verdade de átomos específicos para satisfazer a regra. Isso resulta em uma partição refinada $(T_E, F_E)$ .
- Fase 3 (Suposição e Verificação - Guess-and-Check): Se a partição ainda não for estável, o procedimento enumera todas as extensões da partição atual sobre os átomos indefinidos restantes. Ele verifica cada candidato contra as condições de estabilidade (Prop. 3.2) para identificar todas as partições estáveis e seleciona a mínima (a partição de fundação).

Principais Contribuições
O artigo apresenta três contribuições primárias:

Formalismo hMKNF¬: A introdução do hMKNF¬, uma extensão do MKNF híbrido que suporta formalmente a negação clássica no componente de regras, abordando as limitações da negação por padrão na representação de conhecimento negativo explícito.
Semântica de Três Valores: Uma caracterização formal de bases de conhecimento hMKNF¬ via partições estáveis, estabelecendo que o modelo de fundação corresponde à partição estável mínima única.
Procedimento Computacional: Um algoritmo de três fases para computar o modelo de fundação de bases hMKNF¬ arbitrárias. Este procedimento lida tanto com bases de conhecimento coerentes quanto não coerentes e integra o raciocínio de DL com regras de programação lógica contendo negação clássica.

Resultados e Complexidade
O artigo estabelece a correção teórica do procedimento proposto.

Correção: O Teorema 4.1 prova que a saída do algoritmo de três fases identifica corretamente a partição de fundação se ela existir, detecta inconsistência de MKNF (retornando $\bot$ ), ou identifica a ausência de um modelo de fundação único (retornando NoWFM).
Complexidade: A complexidade de dados depende da fase em que a partição estável é encontrada.
- Se encontrada na Fase 1 ou 2, a complexidade é polinomial em relação à complexidade de dados do raciocínio de DL e da computação do conjunto infundado ( $PTime^{C_1 \cup C_2}$ ).
- Se encontrada apenas na Fase 3, a complexidade é exponencial ( $EXPTime^{P^{C_1}}$ ) devido à enumeração de candidatos, embora as verificações de estabilidade individuais permaneçam polinomiais em relação ao raciocínio de DL.
Comparação: Diferente da abordagem em [5], que é limitada a bases de conhecimento coerentes e carece de negação clássica, o hMKNF¬ aplica-se a todas as bases de conhecimento MKNF híbridas e suporta negação clássica. Diferente do método geral de suposição e verificação em [7], o hMKNF¬ prioriza a computação determinística via Fases 1 e 2, recorrendo à suposição não determinística apenas quando necessário.

Significância
O artigo afirma que o hMKNF¬ aborda uma lacuna significativa na representação de conhecimento híbrido ao permitir a representação explícita de informação negativa dentro do componente de regras. Isso é particularmente significativo para aplicações de segurança crítica, onde o raciocínio deve depender de evidência explícita de ausência, em vez de apenas a mera falta de informação positiva. Ao fornecer um procedimento geral que funciona para bases de conhecimento coerentes e não coerentes, o trabalho estende a aplicabilidade do MKNF híbrido para cenários mais complexos e realistas. Os autores observam que, embora a fase de suposição e verificação introduza complexidade exponencial no pior caso, isso é inevitável para garantir a correção e completude do modelo de fundação para bases hMKNF¬ arbitrárias. O trabalho lança as bases para futuros sistemas de resposta a consultas baseados neste formalismo estendido.

O Novo Superpoder do Detetive

O Fluxo de Trabalho de Três Fases do Detetive

Por Que Isso Importa

Mais como este