Lógica predeterminada

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

La lógica por defecto puede expresar hechos como «por defecto, algo es verdadero»; en cambio, la lógica estándar solo puede expresar que algo es verdadero o falso. Esto representa un problema, ya que el razonamiento suele implicar hechos que son verdaderos en la mayoría de los casos, pero no siempre. Un ejemplo clásico es: «las aves suelen volar». Esta regla puede expresarse en lógica estándar como «todas las aves vuelan», lo cual es inconsistente con el hecho de que los pingüinos no vuelan, o como «todas las aves que no son pingüinos ni avestruces y... vuelan», lo cual requiere especificar todas las excepciones a la regla. La lógica por defecto busca 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 $\langle W,D\rangle$ W es un conjunto de fórmulas lógicas, denominadas 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:

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

Según este valor predeterminado, si creemos que $Prerequisite$ es verdadero, y cada $\mathrm {Justificación} _ {i}$ para $i=1,\dots ,n$ es coherente con nuestras creencias actuales, nos vemos llevados 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 de lógica 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 suelen volar" se formaliza mediante el siguiente valor predeterminado:

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

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

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

.

Según esta regla predeterminada, un cóndor vuela porque la condición previa $Bird(Condor)$ es verdadera y la justificación $Flies(Condor)$ no es inconsistente con lo que se sabe actualmente. Por el contrario, $Bird(Penguin)$ no permite concluir $Flies(Penguin)$ : incluso si la condición previa de la regla predeterminada $Bird(Penguin)$ es verdadera, la justificación $Flies(Penguin)$ es inconsistente con lo que se sabe. A partir de esta teoría de fondo y esta regla predeterminada, no se puede concluir $Bird(Bee)$ 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 común por defecto es que lo que no se sabe que es verdadero se cree que es falso. Esto se conoce como la suposición del mundo cerrado y se formaliza en la lógica por defecto utilizando un valor por defecto como el siguiente para cada hecho $F.$

{\frac {:{\neg }F}{{\neg }F}}

Por ejemplo, el lenguaje de programación Prolog utiliza una especie de suposición por defecto al tratar con la negación: si no se puede demostrar que un átomo negativo es verdadero, entonces se asume que es falso. Sin embargo, tenga en cuenta que Prolog utiliza la llamada negación como fallo : cuando el intérprete tiene que evaluar el átomo. $\neg F$ , intenta demostrar que $F$ es verdadero y concluir que $\neg F$ es verdadero si falla. En la lógica predeterminada, en cambio, un valor predeterminado que tenga $\neg F$ como justificación solo se puede aplicar si $\neg F$ es coherente con el conocimiento actual.

Restricciones

Un defecto es categórico o libre de prerrequisitos si no tiene prerrequisitos (o, equivalentemente, si su prerrequisito es tautológico ). Un defecto es normal si tiene una única justificación equivalente a su conclusión. Un defecto es supernormal si es a la vez categórico y normal. Un defecto es seminormal si todas sus justificaciones implican su conclusión. Una teoría de defecto se denomina categórica, normal, supernormal o seminormal si todos los defectos que contiene son categóricos, normales, supernormales o seminormales, respectivamente.

Semántica de la lógica por defecto

Una regla de defecto puede aplicarse a una teoría si su precondición se deduce de la teoría y sus justificaciones son consistentes con ella. La aplicación de una regla de defecto conlleva la adición de su consecuencia a la teoría. Posteriormente, pueden aplicarse otras reglas de defecto a la teoría resultante. Cuando la teoría es tal que no se puede aplicar ninguna otra regla de defecto, se la denomina extensión de la teoría de defecto. Las reglas de defecto pueden aplicarse en distinto orden, lo que puede dar lugar a distintas extensiones. El ejemplo del diamante de Nixon es una teoría de defecto con dos extensiones:

\left\langle \left\{{\frac {\mathrm {Republicano} (X):\neg \mathrm {Pacifista} (X)}{\neg \mathrm {Pacifista} (X)}},{\frac {\mathrm {Cuáquero} (X):\mathrm {Pacifista} (X)}{\mathrm {Pacifista} (X)}}\right\},\left\{\mathrm {Republicano} (\mathrm {Nixon} ),\mathrm {Cuáquero} (\mathrm {Nixon} )\right\}\right\rangle

Dado que Nixon es republicano y cuáquero , se pueden aplicar ambas suposiciones. Sin embargo, al aplicar la primera, se concluye que Nixon no es pacifista, lo que invalida la segunda. Del mismo modo, al aplicar la segunda, se concluye que Nixon es pacifista, invalidando así la primera. Por lo tanto, esta teoría de suposiciones tiene dos extensiones: una en la que $Pacifista(Nixon)$ es verdadero y otra en la que $Pacifista(Nixon)$ es falso.

La semántica original de la lógica de valores predeterminados 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 valor predeterminado ${\displaystyle {\frac {\alpha$ es aplicable a una teoría proposicional $T$ si $T\models \alpha$ y todas las teorías $T\cup \{\beta _{i}\}$ son consistentes. La aplicación de este valor predeterminado a $T$ conduce a la teoría $T\cup \{\gamma \}$ Se puede generar una extensión aplicando el siguiente algoritmo:

T = W /* teoría actual */ A = 0 /* conjunto de valores predeterminados aplicados hasta el momento */   /* aplicar una secuencia de valores predeterminados */ mientras que existe un valor predeterminado d que no está en A y es aplicable a T agregar la consecuencia de d a T agregar d a A   /* comprobación final de consistencia */ si para cada valor predeterminado d en A T es consistente con todas las justificaciones de d entonces la salida 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, y viceversa. Como resultado, se generan dos extensiones: una en la que Nixon es pacifista y otra en la que no lo es.

La verificación final de la coherencia de las justificaciones de todas las opciones predeterminadas aplicadas implica que algunas teorías no tienen extensiones. En particular, esto ocurre cuando esta verificación falla para cada posible secuencia de opciones predeterminadas aplicables. La siguiente teoría de opciones predeterminadas no tiene extensiones:

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

Desde $A(b)$ es consistente con la teoría de fondo, se puede aplicar el valor predeterminado, lo que lleva a la conclusión de que $A(b)$ Esto es falso. Sin embargo, este resultado socava el supuesto que se hizo para aplicar la primera condición por defecto. Por consiguiente, esta teoría no tiene extensiones.

En una teoría de valores predeterminados normales, todos los valores predeterminados son normales: cada valor predeterminado tiene la forma ${\displaystyle {\frac {\phi$ . Una teoría de defecto normal tiene garantizada al menos una extensión. Además, las extensiones de una teoría de defecto normal son mutuamente inconsistentes, es decir, inconsistentes entre sí.

Vinculación

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

Escéptico: Una fórmula se deduce de una teoría por defecto si se deduce de todas sus extensiones;

Crédulo: Una fórmula se deduce de una teoría por defecto si se deduce de 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 lo es. Por consiguiente, ni $Pacifista(Nixon)$ ni $\neg Pacifista(Nixon)$ se derivan de forma escéptica, mientras que ambas se derivan de forma creíble. Como muestra este ejemplo, las consecuencias creíbles 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 por defecto 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 una justificación de un valor predeterminado aplicado;

Conciso: Se aplica un valor predeterminado 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 que hay detrás);

Constreñido: Se aplica una norma por defecto solo si el conjunto compuesto por la teoría de fondo, las justificaciones de todas las normas por defecto aplicadas y las consecuencias de todas las normas por defecto aplicadas (incluida esta) es coherente;

Racional: similar a la lógica predeterminada restringida, pero la consecuencia de la adición predeterminada no se considera en la verificación de consistencia;

Precavido: Los valores predeterminados que se pueden aplicar pero que entran en conflicto entre sí (como los del ejemplo del diamante de Nixon) no se aplican.

Las versiones justificada y restringida de la regla de inferencia asignan al menos una extensión a cada teoría por defecto.

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 $\langle p:\{r_{1},\ldots ,r_{n}\}\rangle$ compuesto por una fórmula y un conjunto de fórmulas. Dicho par indica que $p$ es verdadero mientras que las fórmulas $r_{1},\ldots ,r_{n}$ Se ha asumido que son consistentes para probar que $p$ es verdadero. Una teoría asertiva por defecto se compone de una teoría asertiva (un conjunto de fórmulas asertivas) llamada teoría de fondo y un conjunto de valores por defecto 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. Las siguientes semánticas utilizan teorías asertivas:

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

Extensiones débiles: En lugar de comprobar si las precondiciones son válidas en la teoría compuesta por la teoría de fondo y las consecuencias de los valores predeterminados aplicados, las precondiciones se comprueban para comprobar su validez 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 la extensión es realmente una extensión solo si es equivalente a la teoría adivinada al principio. Esta variante de la lógica de valores predeterminados está relacionada en principio con la lógica autoepistémica , donde una teoría $\Box x\rightarrow x$ tiene el modelo en el que $x$ es verdadero simplemente porque, suponiendo $\Box x$ cierto, la fórmula $\Box x\rightarrow x$ respalda la suposición inicial.

Lógica predeterminada disyuntiva: La consecuencia de una configuración predeterminada es un conjunto de fórmulas en lugar de una sola fórmula. Siempre que se aplica la configuración predeterminada, al menos una de sus consecuencias se elige de forma no determinista y se hace verdadera.

Prioridades en caso de incumplimiento: La prioridad relativa de los valores predeterminados puede especificarse explícitamente; entre los valores predeterminados aplicables a una teoría, solo se puede aplicar uno de los preferidos. ^{[ 1 ]} Algunas semánticas de la lógica de valores predeterminados 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 asociado a su frecuencia de error; en otras palabras, se supone que el valor predeterminado es una regla de inferencia incorrecta como máximo en esa fracción de las veces que se aplica.

Traducciones

Las teorías por defecto pueden traducirse a teorías en otras lógicas y viceversa. Se han considerado las siguientes condiciones para las traducciones:

Preservación de las consecuencias: Las teorías originales y traducidas tienen las mismas consecuencias (proposicionales);

Fiel: Esta condición solo tiene sentido al traducir 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 una correspondencia (típicamente, una biyección ) entre las extensiones (o modelos) de las teorías originales y traducidas;

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

Misma letra del alfabeto: Las teorías originales y traducidas se basan en el mismo alfabeto;

Polinomio: Se requiere que el tiempo de ejecución de la traducción o el tamaño de la teoría generada sean polinomiales en el tamaño de la teoría original.

Por lo general, se exige que las traducciones sean fieles o, al menos, que conserven las consecuencias, mientras que en ocasiones se ignoran las condiciones de modularidad y de utilizar el mismo alfabeto.

Se ha estudiado la traducibilidad entre la lógica proposicional por defecto y las siguientes lógicas:

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

La existencia de traducciones depende de las condiciones que se impongan. Las traducciones de la lógica proposicional por defecto a la lógica proposicional clásica no siempre generan una teoría proposicional de tamaño polinomial, a menos que la jerarquía polinomial colapse. La existencia de traducciones a la lógica autoepistémica depende de si se requiere modularidad o el uso del mismo alfabeto.

Complejidad

Se conoce la complejidad computacional de los siguientes problemas sobre lógica por defecto:

Existencia de extensiones: decidir si una teoría proposicional por defecto tiene al menos una extensión es $\Sigma _{2}^{P}$ -completo;

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

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

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

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

Implementaciones

Cuatro sistemas que implementan lógicas predeterminadas son DeReS, XRay , GADeL Archivado el 6 de abril de 2007 en Wayback Machine y Catala .

Véase también

Referencias

↑ Horty, John (2007). "Defaults with Priorities" . Journal of Philosophical Logic . 36 (4): 367– 413. doi : 10.1007/s10992-006-9040-0 .

G. Antoniou (1999). Un tutorial sobre lógicas predeterminadas. ACM Computing Surveys , 31(4):337-359.
M. Cadoli, FM Donini, P. Liberatore y M. Schaerf (2000). Eficiencia espacial de los formalismos de representación del conocimiento proposicional. Archivado el 9 de mayo de 2013 en Wayback Machine . Journal of Artificial Intelligence Research , 13:1-31.
P. Cholewinski, V. Marek y M. Truszczynski (1996). Sistema de razonamiento por defecto DeReS. En Actas de la Quinta Conferencia Internacional sobre los Principios de Representación del Conocimiento y Razonamiento (KR'96) , páginas 518-528.
J. Delgrande y T. Schaub (2003). Sobre la relación entre la lógica por defecto de Reiter y sus variantes (principales). En 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 por defecto. Inteligencia Artificial , 70:167-237.
G. Gottlob (1992). Resultados de complejidad para lógicas no monótonas. Journal of Logic and Computation , 2:397-425.
G. Gottlob (1995). Traducción de la lógica por defecto a la lógica autoepistémica estándar . Journal of the ACM , 42:711-740.
T. Imielinski (1987). Resultados sobre la traducción de valores predeterminados a circunscripción. Inteligencia Artificial , 32:131-146.
T. Janhunen (1998). Sobre la intertraducibilidad de las lógicas autoepistémicas, por defecto y de prioridad, y la circunscripción paralela . En Actas del Sexto Taller Europeo sobre Lógicas en Inteligencia Artificial (JELIA'98) , páginas 216-232.
T. Janhunen (2003). Evaluación del efecto de la seminormalidad en la expresividad de los valores predeterminados. Inteligencia Artificial , 144:233-250.
HE Kyburg y CM. Teng (2006). Lógica no monótona e inferencia estadística. Inteligencia computacional , 22(1): 26-51.
P. Liberatore y M. Schaerf (1998). La complejidad de la verificación de modelos para lógicas proposicionales por defecto. En Actas de la Decimotercera Conferencia Europea sobre Inteligencia Artificial (ECAI'98) , páginas 18-22.
W. Lukaszewicz (1988). Consideraciones sobre la lógica por defecto: un enfoque alternativo. Inteligencia Computacional , 4(1):1-16.
W. Marek y M. Truszczynski (1993). Lógicas no monótonas: razonamiento dependiente del contexto . Springer.
A. Mikitiuk y M. Truszczynski (1995). Lógicas por defecto restringidas y racionales . En Actas de la Decimocuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI'95) , páginas 1509-1517.
P. Nicolas, F. Saubion e I. Stéphan (2001). Heurísticas para un sistema de razonamiento lógico por defecto. Archivado el 7 de septiembre de 2017 en Wayback Machine . International Journal on Artificial Intelligence Tools , 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 demostrador de teoremas basado en tecnología Prolog para el razonamiento por defecto: 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 con recursos limitados. En Actas del 10.º Taller Internacional sobre Razonamiento No Monótono (NMR-04) , Whistler, Columbia Británica, 416-422.
G. Wheeler y C. Damasio (2004). Una implementación de la lógica de defecto estadística . En Actas de la 9ª Conferencia Europea sobre Lógicas en Inteligencia Artificial (JELIA 2004) , Serie LNCS, Springer, páginas 121-133.

Enlaces externos

Schmidt, Charles F. RCI.Rutgers.edu , Lógica por defecto. Consultado el 10 de agosto de 2004.
Ramsay, Allan (1999). UMIST.ac.uk , Lógica predeterminada. Recuperado el 10 de agosto de 2004.
Stanford.edu , Razonamiento refutable, Enciclopedia de Filosofía de Stanford .

[1] Horty, John (2007). "Defaults with Priorities" . Journal of Philosophical Logic . 36 (4): 367– 413. doi : 10.1007/s10992-006-9040-0 .

[ 1 ]