Lógica por defecto

La lógica predeterminada es una lógica no monótona propuesta por Raymond Reiter para formalizar el razonamiento con supuestos predeterminados.

La lógica predeterminada puede expresar hechos como «por defecto, algo es cierto»; en contraste, la lógica estándar solo puede expresar que algo es verdadero o que algo es falso. Este es un problema porque el razonamiento a menudo involucra hechos que son verdaderos en la mayoría de los casos, pero no siempre. Un ejemplo clásico es: «las aves típicamente vuelan». Esta regla puede ser expresada en la lógica estándar ya sea por «todas las aves vuelan», lo cual es inconsistente con el hecho de que los pingüinos no vuelan, o por «todas las aves que no son pingüinos y no avestruces y … vuelan», que requiere todo excepciones a la regla a ser especificada. La lógica predeterminada apunta a formalizar reglas de inferencia como esta sin mencionar explícitamente todas sus excepciones.

Sintaxis de la lógica por defecto.
Una teoría por defecto es un par  . W es un conjunto de fórmulas lógicas, llamadas teoría de fondo, que formalizan los hechos que se conocen con seguridad. D es un conjunto de reglas predeterminadas, cada una de las cuales tiene el formato:

De acuerdo con este valor predeterminado, si creemos que el requisito previo es verdadero, y cada uno de  es consistente con nuestras creencias actuales, nos llevan a creer que la conclusión es verdadera.

Las fórmulas lógicas en W y todas las fórmulas en un valor predeterminado se asumieron originalmente como fórmulas lógicas de primer orden, pero potencialmente pueden ser fórmulas en una lógica formal arbitraria. El caso en el que son fórmulas en lógica proposicional es uno de los más estudiados.

Ejemplos
La regla predeterminada «las aves normalmente vuelan» se formaliza mediante la siguiente configuración predeterminada:

Esta regla significa que, si X es un ave, y se puede suponer que vuela, podemos concluir que vuela.Una teoría de fondo que contiene algunos datos sobre las aves es la siguiente:
.

De acuerdo con esta regla predeterminada, un cóndor vuela porque la condición previa del ave (cóndor) es verdadera y la justificación Moscas (cóndor) no es inconsistente con lo que se conoce actualmente. Por el contrario, Bird (Penguin) no permite la conclusión de Moscas (Penguin): incluso si la condición previa del Bird (Penguin) predeterminado es verdadera, la justificación de Moscas (Penguin) es inconsistente con lo que se conoce. A partir de esta teoría de fondo y este valor predeterminado, Bird (Bee) no se puede concluir porque la regla predeterminada solo permite derivar Moscas (X) de Bird (X), pero no al revés. Derivar los antecedentes de una regla de inferencia a partir de las consecuencias es una forma de explicación de las consecuencias, y es el objetivo del razonamiento abductivo.

Una suposición por defecto común es que lo que no se sabe que es verdadero se cree que es falso.Esto se conoce como Supuesto del mundo cerrado y se formaliza en la lógica predeterminada utilizando un valor predeterminado como el siguiente para cada hecho F.

Por ejemplo, el lenguaje de computadora Prolog utiliza una especie de suposición predeterminada al tratar con la negación: si un átomo negativo no puede demostrarse que es verdadero, entonces se supone que es falso. Tenga en cuenta, sin embargo, que Prolog utiliza la llamada negación como falla: cuando el intérprete tiene que evaluar el átomo  , trata de probar que F es verdadera, y concluye que  es cierto si falla En la lógica predeterminada, en su lugar, un valor predeterminado que tiene  Como justificación solo puede aplicarse si  Es consistente con el conocimiento actual.

Restricciones
Un valor predeterminado es categórico o libre de requisitos previos si no tiene ningún requisito previo (o, de manera equivalente, su requisito previo es tautológico). Un valor predeterminado es normal si tiene una única justificación que es equivalente a su conclusión. Un valor predeterminado es supernormal si es tanto categórico como normal. Un defecto es seminormal si todas sus justificaciones implican su conclusión. Una teoría predeterminada se denomina categórica, normal, supernormal o seminormal si todos los valores predeterminados que contiene son categóricos, normales, supernormales o seminormales, respectivamente.

Semántica de la lógica por defecto.
Se puede aplicar una regla predeterminada a una teoría si su precondición está relacionada con la teoría y sus justificaciones son compatibles con la teoría. La aplicación de una regla por defecto lleva a la adición de su consecuencia a la teoría. Luego se pueden aplicar otras reglas predeterminadas a la teoría resultante. Cuando la teoría es tal que no se puede aplicar ningún otro defecto, la teoría se llama una extensión de la teoría por defecto. Las reglas predeterminadas pueden aplicarse en un orden diferente, y esto puede llevar a diferentes extensiones. El ejemplo de diamante de Nixon es una teoría predeterminada con dos extensiones:

Dado que Nixon es tanto republicano como cuáquero, se pueden aplicar ambos valores predeterminados. Sin embargo, la aplicación del primer valor predeterminado lleva a la conclusión de que Nixon no es un pacifista, lo que hace que el segundo valor predeterminado no sea aplicable.De la misma manera, aplicando el segundo valor predeterminado obtenemos que Nixon es un pacifista, por lo que el primer valor predeterminado no es aplicable. Esta teoría predeterminada particular tiene, por lo tanto, dos extensiones, una en la que Pacifist (Nixon) es verdadera y otra en la que Pacifist (Nixon) es falsa.

La semántica original de la lógica predeterminada se basaba en el punto fijo de una función. La siguiente es una definición algorítmica equivalente. Si un valor predeterminado contiene fórmulas con variables libres, se considera que representa el conjunto de todos los valores predeterminados obtenidos al asignar un valor a todas estas variables. Un defecto  es aplicable a una teoría proposicional T si  y todas las teorias  son consistentes. La aplicación de este defecto a T conduce a la teoría.  . Se puede generar una extensión aplicando el siguiente algoritmo:

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 no es determinista, ya que varios valores predeterminados pueden aplicarse alternativamente a una teoría determinada T. En el ejemplo de diamante de Nixon, la aplicación del primer valor predeterminado conduce a una teoría a la que no se puede aplicar el segundo valor predeterminado y viceversa. Como resultado, se generan dos extensiones: una en la que Nixon es un pacifista y otra en la que Nixon no es un pacifista.

La comprobación final de la coherencia de las justificaciones de todos los valores predeterminados que se han aplicado implica que algunas teorías no tienen ninguna extensión. En particular, esto sucede cuando falla esta comprobación para cada secuencia posible de valores predeterminados aplicables. La siguiente teoría por defecto no tiene extensión:

Ya que  es coherente con la teoría de fondo, se puede aplicar el defecto, lo que lleva a la conclusión de que  Es falso. Sin embargo, este resultado socava la suposición que se ha hecho para aplicar el primer valor predeterminado. En consecuencia, esta teoría no tiene extensiones.

En una teoría predeterminada normal, todos los valores predeterminados son normales: cada valor predeterminado tiene la forma  . Se garantiza que una teoría predeterminada normal tiene al menos una extensión. Además, las extensiones de una teoría por defecto normal son mutuamente inconsistentes, es decir, inconsistentes entre sí.

Vinculación
Una teoría predeterminada puede tener cero, una o más extensiones. La incorporación de una fórmula a partir de una teoría por defecto se puede definir de dos maneras:

Escéptico
una fórmula está implícita en una teoría por defecto si está implicada en todas sus extensiones;

Crédulo
una fórmula está relacionada con una teoría predeterminada si está relacionada con al menos una de sus extensiones.

Por lo tanto, la teoría del ejemplo del diamante de Nixon tiene dos extensiones, una en la que Nixon es un pacifista y otra en la que no es un pacifista. En consecuencia, ni Pacifist (Nixon) ni ¬Pacifist (Nixon) están implicados escépticamente, mientras que los dos están implicados de manera creíble.Como muestra este ejemplo, las consecuencias crédulas de una teoría por defecto pueden ser inconsistentes entre sí.

Reglas de inferencia predeterminadas alternativas
Las siguientes reglas de inferencia alternativas para la lógica predeterminada se basan en la misma sintaxis que el sistema original.

Justificado
difiere del original en que no se aplica un valor predeterminado si, por lo tanto, el conjunto T se vuelve inconsistente con la justificación de un valor predeterminado aplicado;

Conciso
solo se aplica un valor predeterminado si su consecuencia no está ya implicada por T (la definición exacta es más complicada que esta; esta es solo la idea principal detrás de ella);

Constreñido
solo se aplica un valor predeterminado si el conjunto compuesto por la teoría de fondo, las justificaciones de todos los valores predeterminados aplicados y las consecuencias de todos los valores predeterminados aplicados (incluido este) son coherentes;

Racional
similar a la lógica predeterminada restringida, pero la consecuencia del valor predeterminado para agregar no se considera en la verificación de consistencia;

Cauteloso
los valores predeterminados que se pueden aplicar pero que están en conflicto entre sí (como los del ejemplo del diamante de Nixon) no se aplican.

Las versiones justificadas y restringidas de la regla de inferencia asignan al menos una extensión a cada teoría predeterminada.

Variantes de la lógica por defecto.
Las siguientes variantes de la lógica predeterminada difieren de la original tanto en la sintaxis como en la semántica.

Variantes de aserción
Una afirmación es un par  Compuesto por una fórmula y un conjunto de fórmulas. Tal par indica que p es verdadero mientras que las fórmulas  Se han asumido consistentes para probar que p es cierto. Una teoría de aserción por defecto se compone de una teoría de aserción (un conjunto de fórmulas de aserción) denominada teoría de fondo y un conjunto de valores por defecto definidos como en la sintaxis original. Cada vez que se aplica un defecto a una teoría de la afirmación, el par compuesto por su consecuencia y su conjunto de justificaciones se agrega a la teoría. Las siguientes semánticas utilizan teorías asertivas:

Lógica por defecto acumulativa
Compromiso con las suposiciones por defecto de la lógica.
Lógica cuasi predeterminada

Extensiones débiles
en lugar de verificar si las condiciones previas son válidas en la teoría compuesta por la teoría de fondo y las consecuencias de los valores predeterminados aplicados, las condiciones previas se verifican para la validez en la extensión que se generará; en otras palabras, el algoritmo para generar extensiones comienza por adivinar una teoría y usarla en lugar de la teoría de fondo; lo que resulta del proceso de generación de extensión es en realidad una extensión solo si es equivalente a la teoría adivinada al principio. Esta variante de la lógica por defecto está relacionada en principio con la lógica autoepistémica, donde una teoría  tiene el modelo en el que x es verdadera solo porque, asumiendo  cierto, la formula  apoya el supuesto inicial.

Lógica disyuntiva por defecto.
La consecuencia de un valor predeterminado es un conjunto de fórmulas en lugar de una sola fórmula. Cada vez que se aplica el valor predeterminado, al menos una de sus consecuencias se elige de forma no determinista y se hace realidad.

Prioridades en los incumplimientos
la prioridad relativa de los valores predeterminados se puede especificar explícitamente; Entre los valores predeterminados que son aplicables a una teoría, solo se puede aplicar uno de los más preferidos. Algunas semánticas de la lógica predeterminada no requieren que las prioridades se especifiquen explícitamente; más bien, se prefieren los valores predeterminados más específicos (aquellos que son aplicables en menos casos) a los menos específicos.

Variante estadística
un valor predeterminado estadístico es un valor predeterminado con un límite superior adjunto en su frecuencia de error; en otras palabras, se asume que el valor predeterminado es una regla de inferencia incorrecta como máximo en la fracción de veces que se aplica.

Traducciones
Las teorías predeterminadas se pueden traducir a teorías en otras lógicas y viceversa. Se han considerado las siguientes condiciones de traducción:

Consecuencia-Preservación
El original y las teorías traducidas tienen las mismas consecuencias (proposicionales);

Fiel
esta condición solo tiene sentido cuando se traduce entre dos variantes de lógica predeterminada o entre lógica predeterminada y una lógica en la que existe un concepto similar a la extensión, por ejemplo, modelos en lógica modal; una traducción es fiel si existe un mapeo (típicamente, una bijección) entre las extensiones (o modelos) de las teorías original y traducida;

Modular
una traducción de la lógica predeterminada a otra lógica es modular si los valores predeterminados y la teoría de fondo se pueden traducir por separado; además, la adición de fórmulas a la teoría de fondo solo lleva a agregar las nuevas fórmulas al resultado de la traducción;

Mismo alfabeto
Las teorías originales y traducidas se basan en el mismo alfabeto;

Polinomio
El tiempo de ejecución de la traducción o el tamaño de la teoría generada deben ser polinomiales en el tamaño de la teoría original.

Normalmente se requiere que las traducciones sean fieles o, al menos, que preserven las consecuencias, mientras que las condiciones de modularidad y el mismo alfabeto a veces se ignoran.
Se ha estudiado la traducibilidad entre la lógica predeterminada proposicional y las siguientes lógicas:

lógica proposicional clásica;
Lógica autoepistémica;
lógica por defecto proposicional restringida a teorías seminormales;
semántica alternativa de la lógica por defecto;
circunscripción.

Las traducciones existen o no dependiendo de qué condiciones se impongan. Las traducciones de la lógica predeterminada proposicional a la lógica proposicional clásica no siempre pueden generar una teoría proposicional de tamaño polinomial, a menos que la jerarquía polinomial se derrumbe.Las traducciones a la lógica autoepistémica existen o no dependiendo de si se requiere modularidad o el uso del mismo alfabeto.

Complejidad
Se conoce la complejidad computacional de los siguientes problemas sobre la lógica predeterminada:

Existencia de extensiones.
decidir si una teoría por defecto proposicional tiene al menos una extensión es  -completar;

Vinculación escéptica
decidir si una teoría por defecto proposicional implica escépticamente una fórmula proposicional es  -completar;

Vinculación crédula
Decidir si una teoría por defecto proposicional conlleva de manera creíble una fórmula proposicional es  -completar;

Comprobación de la extensión
decidir si una fórmula proposicional es equivalente a una extensión de una teoría predeterminada proposicional es  -completar;

Control de modelos
decidir si una interpretación proposicional es un modelo de una extensión de una teoría predeterminada proposicional es  -completar.

Implementaciones
Tres sistemas que implementan lógicas predeterminadas son DeReS, XRay y GADeL