Lógica predeterminada - Default logic

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"; por el contrario, la lógica estándar solo puede expresar que algo es verdadero o que algo es falso. Esto 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: “los pájaros suelen volar”. Esta regla puede expresarse en la lógica estándar ya sea por "todos los pájaros vuelan", que es incompatible 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 especificar. La lógica predeterminada tiene como objetivo formalizar reglas de inferencia como esta sin mencionar explícitamente todas sus excepciones.

Sintaxis de la lógica predeterminada

Una teoría predeterminada 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 certeza. D es un conjunto de reglas predeterminadas , cada una de las cuales tiene la forma: ${\ Displaystyle \ langle W, D \ rangle}$

${\ displaystyle {\ frac {\ mathrm {Requisito previo: Justificación} _ {1}, \ dots, \ mathrm {Justificación} _ {n}} {\ mathrm {Conclusión}}}}$

De acuerdo con este valor predeterminado, si creemos que el Requisito previo es verdadero, y cada uno de ellos es consistente con nuestras creencias actuales, se nos hace creer que la Conclusión es verdadera. ${\ displaystyle \ mathrm {Justificación} _ {n}}$

Originalmente se asumió que las fórmulas lógicas en W y todas las fórmulas predeterminadas eran 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 de

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

${\ Displaystyle D = \ left \ {{\ frac {\ mathrm {Pájaro} (X): \ mathrm {Moscas} (X)} {\ mathrm {Moscas} (X)}} \ right \}}$

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

${\ displaystyle W = \ {\ mathrm {Pájaro} (\ mathrm {Cóndor}), \ mathrm {Pájaro} (\ mathrm {Pingüino}), \ neg \ mathrm {Moscas} (\ mathrm {Pingüino}), \ mathrm {Moscas} (\ mathrm {Abeja}) \}}$ .

De acuerdo con esta regla por defecto, un cóndor vuela porque la condición previa Pájaro (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 concluir Flies (Penguin) : incluso si la condición previa del Bird (Penguin) predeterminado es verdadera, la justificación Flies (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 Flies ( 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 predeterminada común es que lo que no se sabe que es cierto se cree que es falso. Esto se conoce como la asunción cerrado Mundial , y se formaliza en la lógica predeterminada utilizando un defecto como la siguiente para cada hecho F .

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

Por ejemplo, el lenguaje informático Prolog utiliza una especie de suposición predeterminada cuando se trata de la negación: si no se puede probar que un átomo negativo es verdadero, entonces se supone que es falso. Sin embargo, tenga en cuenta que Prolog usa la llamada negación como falla : cuando el intérprete tiene que evaluar el átomo , intenta probar que F es verdadera y concluye que es verdadera si falla. En la lógica por defecto, en cambio, un que tiene como justificación por defecto solo se puede aplicar si es consistente con el conocimiento actual. ${\ Displaystyle \ neg F}$${\ Displaystyle \ neg F}$${\ Displaystyle \ neg F}$${\ Displaystyle \ neg F}$

Restricciones

Un valor predeterminado es categórico o sin prerrequisitos si no tiene prerrequisitos (o, de manera equivalente, su prerrequisito es tautológico ). Un defecto es normal si tiene una única justificación que equivale 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 predeterminada

Se puede aplicar una regla por defecto a una teoría si su condición previa está implícita en la teoría y sus justificaciones son todas coherentes con la teoría. La aplicación de una regla por defecto conduce a la adición de su consecuencia a la teoría. A continuación, 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 valor por defecto, la teoría se denomina una extensión de la teoría por defecto. Las reglas predeterminadas se pueden aplicar en un orden diferente y esto puede dar lugar a extensiones diferentes. El ejemplo del diamante de Nixon es una teoría predeterminada con dos extensiones:

${\ 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)}} \ right \}, \ left \ {\ mathrm {Republicano} (\ mathrm { Nixon}), \ mathrm {Quaker} (\ mathrm {Nixon}) \ right \} \ right \ rangle}$

Dado que Nixon es republicano y 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 forma, aplicando el segundo default obtenemos que Nixon es pacifista, por lo que el primer default no es aplicable. Esta teoría particular por defecto tiene, por tanto, dos extensiones, una en la que Pacifista (Nixon) es verdadera y otra en la que Pacifista (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 dar un valor a todas estas variables. Un valor predeterminado es aplicable a una teoría proposicional T si y todas las teorías son consistentes. La aplicación de este valor por defecto a T conduce a la teoría . Se puede generar una extensión aplicando el siguiente algoritmo: ${\ Displaystyle {\ frac {\ alpha: \ beta _ {1}, \ ldots, \ beta _ {n}} {\ gamma}}}$${\ Displaystyle T \ modelos \ 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 no es determinista , ya que se pueden aplicar alternativamente varios valores predeterminados a una teoría T dada . En el ejemplo del 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 pacifista y otra en la que Nixon no es pacifista.

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

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

Dado que es coherente con la teoría de fondo, se puede aplicar el valor predeterminado, lo que lleva a la conclusión de que es falsa. Sin embargo, este resultado socava la suposición que se ha hecho para aplicar el primer incumplimiento. En consecuencia, esta teoría no tiene extensiones. ${\ Displaystyle A (b)}$${\ Displaystyle A (b)}$

En una teoría normal de los valores predeterminados, todos los valores predeterminados son normales: cada valor predeterminado tiene la forma . Se garantiza que una teoría por defecto 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í. ${\ Displaystyle {\ frac {\ phi: \ psi} {\ psi}}}$

Vinculación

Una teoría predeterminada puede tener cero, una o más extensiones. La vinculación de una fórmula a partir de una teoría predeterminada se puede definir de dos formas:

Escéptico

una fórmula está implicada por una teoría por defecto si está implicada por todas sus extensiones;

Crédulo

una fórmula está implicada por una teoría predeterminada si está implicada por al menos una de sus extensiones.

Así, la teoría del ejemplo del diamante de Nixon tiene dos extensiones, una en la que Nixon es pacifista y otra en la que no es pacifista. En consecuencia, ni Pacifista (Nixon) ni ¬Pacifista (Nixon) están implicados con escepticismo, mientras que ambos están implicados con credulidad. Como muestra este ejemplo, las consecuencias crédulas de una teoría por defecto pueden ser incompatibles entre sí.

Reglas de inferencia predeterminadas alternativas

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

Justificado

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

Conciso

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

Constreñido

un valor predeterminado se aplica solo si el conjunto compuesto por la teoría de fondo, las justificaciones de todos los incumplimientos aplicados y las consecuencias de todos los incumplimientos aplicados (incluido este) es coherente;

Racional

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

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 predeterminada

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

Variantes asertivas

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 verdadero. Una teoría afirmativa por defecto se compone de una teoría afirmativa (un conjunto de fórmulas afirmativas) llamada teoría de fondo y un conjunto de valores predeterminados definidos como en la sintaxis original. Siempre que se aplica un valor por defecto a una teoría asertiva, el par compuesto por su consecuencia y su conjunto de justificaciones se agrega a la teoría. La siguiente semántica utiliza teorías asertivas: ${\ Displaystyle \ langle p: \ {r_ {1}, \ ldots, r_ {n} \} \ rangle}$${\ Displaystyle r_ {1}, \ ldots, r_ {n}}$

• Lógica acumulativa predeterminada
• Compromiso con los supuestos lógicos predeterminados
• Lógica casi predeterminada

Extensiones débiles

en lugar de comprobar 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, se comprueba la validez de las condiciones previas en la extensión que se generará; en otras palabras, el algoritmo para generar extensiones comienza adivinando una teoría y usándola en lugar de la teoría de fondo; lo que resulta del proceso de generación de extensiones es en realidad una extensión sólo si es equivalente a la teoría adivinada al principio. Esta variante de la lógica predeterminada 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 que es verdadera, la fórmula respalda la suposición inicial. ${\ Displaystyle \ Box x \ rightarrow x}$${\ Displaystyle \ Box x}$${\ Displaystyle \ Box x \ rightarrow x}$

Lógica disyuntiva predeterminada

la consecuencia de un valor predeterminado es un conjunto de fórmulas en lugar de una única fórmula. Siempre que se aplica el valor predeterminado, al menos una de sus consecuencias se elige de forma no determinista y se hace verdadera.

Prioridades sobre 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 (los que son aplicables en menos casos) a los menos específicos.

Variante estadística

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

Traducciones

Las teorías predeterminadas se pueden traducir en teorías en otras lógicas y viceversa. Se han considerado las siguientes condiciones para las traducciones:

Conservación de consecuencias

las teorías original y traducida tienen las mismas consecuencias (proposicionales);

Fiel

esta condición solo tiene sentido cuando se traduce entre dos variantes de la lógica predeterminada o entre la 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 biyecció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 conduce a agregar las nuevas fórmulas al resultado de la traducción;

Mismo alfabeto

las teorías original y traducida 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.

Por lo general, se requiere que las traducciones sean fieles o al menos 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 proposicional predeterminada y las siguientes lógicas:

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

Las traducciones existen o no dependiendo de las condiciones que se impongan. Las traducciones de la lógica proposicional por defecto 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 colapse. 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 -completo; ${\ Displaystyle \ Sigma _ {2} ^ {P}}$

Vinculación escéptica

decidir si una teoría por defecto proposicional implica escépticamente una fórmula proposicional es -completo; ${\ Displaystyle \ Pi _ {2} ^ {P}}$

Vinculación crédula

decidir si una teoría por defecto proposicional implica crédulamente una fórmula proposicional es -completo; ${\ Displaystyle \ Sigma _ {2} ^ {P}}$

Comprobación de extensión

decidir si una fórmula proposicional es equivalente a una extensión de una teoría proposicional por defecto es -completo; ${\ Displaystyle \ Delta _ {2} ^ {P [\ log]}}$

Comprobación de modelo

decidir si una interpretación proposicional es un modelo de una extensión de una teoría proposicional por defecto es -completo. ${\ Displaystyle \ Sigma _ {2} ^ {P}}$

Implementaciones

Cuatro sistemas de aplicación lógica por defecto son deres , radiografía , GADEL y Catala .

Ver también

• Programación del conjunto de respuestas
• Lógica derrotable
• Lógica no monótona

Referencias

• G. Antoniou (1999). Un tutorial sobre lógicas predeterminadas. Encuestas de computación de ACM , 31 (4): 337-359.
• M. Cadoli, FM Donini, P. Liberatore y M. Schaerf (2000). Eficiencia espacial de los formalismos proposicionales de representación del conocimiento . Revista de investigación en inteligencia artificial , 13: 1-31.
• P. Cholewinski, V. Marek y M. Truszczynski (1996). Sistema de razonamiento predeterminado DeReS. En Actas de la Quinta Conferencia Internacional sobre los Principios de Representación y Razonamiento del Conocimiento (KR'96) , páginas 518-528.
• J. Delgrande y T. Schaub (2003). Sobre la relación entre la lógica predeterminada de Reiter y sus variantes (principales). En la Séptima Conferencia Europea sobre Enfoques Simbólicos y Cuantitativos del Razonamiento con Incertidumbre (ECSQARU 2003) , páginas 452-463.
• JP Delgrande, T. Schaub y WK Jackson (1994). Enfoques alternativos a la lógica predeterminada. Inteligencia artificial , 70: 167-237.
• G. Gottlob (1992). Resultados de complejidad para lógicas no monotónicas. Revista de lógica y computación , 2: 397-425.
• G. Gottlob (1995). Traducir la lógica predeterminada en lógica autoepistémica estándar . Revista de la ACM , 42: 711-740.
• T. Imielinski (1987). Resultados de la traducción de los valores predeterminados a la circunscripción. Inteligencia artificial , 32: 131-146.
• T. Janhunen (1998). Sobre la intertraducibilidad de lógicas autoepistémicas, predeterminadas y prioritarias, y circunscripción paralela . En Actas del Sexto Taller Europeo sobre Lógica en Inteligencia Artificial (JELIA'98) , páginas 216-232.
• T. Janhunen (2003). Evaluar el efecto de la semi-normalidad sobre la expresividad de los incumplimientos. Inteligencia artificial , 144: 233-250.
• HE Kyburg y CM. Teng (2006). Inferencia estadística y lógica no monotónica. Inteligencia computacional , 22 (1): 26-51.
• P. Liberatore y M. Schaerf (1998). La complejidad de la verificación del modelo para las lógicas proposicionales predeterminadas. En Actas de la Decimotercera Conferencia Europea sobre Inteligencia Artificial (ECAI'98) , páginas 18–22.
• W. Lukaszewicz (1988). Consideraciones sobre la lógica predeterminada: un enfoque alternativo. Inteligencia computacional , 4 (1): 1-16.
• W. Marek y M. Truszczynski (1993). Lógicas no monotónicas: razonamiento dependiente del contexto . Saltador.
• A. Mikitiuk y M. Truszczynski (1995). Lógicas predeterminadas limitadas y racionales . En Actas de la Decimocuarta Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI'95) , páginas 1509-1517.
• P. Nicolas, F. Saubion e I. Stéphan (2001). Heurística para un sistema de razonamiento lógico predeterminado . Revista internacional sobre herramientas de inteligencia artificial , 10 (4): 503-523.
• R. Reiter (1980). Una lógica para el razonamiento por defecto. Inteligencia artificial , 13: 81-132.
• T. Schaub, S. Brüning y P. Nicolas (1996). XRay: un prólogo que prueba el teorema de la tecnología del razonamiento predeterminado: una descripción del sistema. En Actas de la Decimotercera Conferencia Internacional sobre Deducción Automatizada (CADE'96) , páginas 293-297.
• G. Wheeler (2004). Una lógica predeterminada delimitada por recursos. En Actas del X Taller Internacional sobre Razonamiento No Monotónico (NMR-04) , Whistler, Columbia Británica, 416-422.
• G. Wheeler y C. Damasio (2004). Una implementación de la lógica estadística predeterminada . En Actas de la 9ª Conferencia Europea sobre Lógica en Inteligencia Artificial (JELIA 2004) , Serie LNCS, Springer, páginas 121-133.

enlaces externos

• Schmidt, Charles F. RCI.Rutgers.edu , lógica predeterminada. Consultado el 10 de agosto de 2004.
• Ramsay, Allan (1999). UMIST.ac.uk , lógica predeterminada. Consultado el 10 de agosto de 2004.
• Stanford.edu , razonamiento derribable, enciclopedia de filosofía de Stanford .