Lógica predeterminada

Tipo de lógica no monótona

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

La lógica predeterminada puede expresar hechos como “por defecto, algo es verdad”; por el contrario, la lógica estándar sólo puede expresar que algo es verdadero o que algo es falso. Esto es un problema porque el razonamiento a menudo involucra hechos que son ciertos en la mayoría de los casos, pero no siempre. Un ejemplo clásico es: “los pájaros normalmente vuelan”. Esta regla puede expresarse en la lógica estándar ya sea con “todos los pájaros vuelan”, lo que es inconsistente con el hecho de que los pingüinos no vuelan, o con “todos los pájaros que no son pingüinos ni avestruces y... vuelan”, lo que requiere que todos excepciones a la regla que se especificarán. La lógica predeterminada tiene como objetivo formalizar reglas de inferencia como ésta 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, denominada 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 {Prerequisite:Justification} _{1},\dots ,\mathrm {Justification} _{n}}{\mathrm {Conclusion} }}}$

De acuerdo con este valor predeterminado, si creemos que el Prerrequisito es verdadero y cada uno de ellos es consistente con nuestras creencias actuales, se nos lleva a creer que la Conclusión es verdadera. ${\displaystyle \mathrm {Justification} _{i}}$ ${\displaystyle i=1,\dots ,n}$

Originalmente se asumió que las fórmulas lógicas en W y todas las fórmulas en un valor predeterminado 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

La regla predeterminada “los pájaros normalmente vuelan” se formaliza mediante el siguiente valor predeterminado:

${\displaystyle D=\left\{{\frac {\mathrm {Bird} (X):\mathrm {Flies} (X)}{\mathrm {Flies} (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 básica que contiene algunos datos sobre las aves es la siguiente:

${\displaystyle W=\{\mathrm {Bird} (\mathrm {Condor} ),\mathrm {Bird} (\mathrm {Penguin} ),\neg \mathrm {Flies} (\mathrm {Penguin} ),\mathrm {Flies} (\mathrm {Bee} )\}}$.

Según esta regla por defecto, un cóndor vuela porque la condición previa Pájaro(Cóndor) es verdadera y la justificación Vuela(Cóndor) 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 del Bird(Penguin) predeterminado es verdadera, la justificación Flies(Penguin) es inconsistente con lo que se sabe. A partir de esta teoría de fondo y este valor predeterminado, 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 predeterminada común es que lo que no se sabe que sea verdadero se cree que es falso. Esto se conoce como el Supuesto del Mundo Cerrado y se formaliza en la lógica predeterminada utilizando un valor predeterminado como el 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 negación: si no se puede demostrar que un átomo negativo sea verdadero, entonces se supone que es falso. Tenga en cuenta, sin embargo, que Prolog utiliza la llamada negación como fracaso : cuando el intérprete tiene que evaluar el átomo , intenta demostrar que F es verdadero y concluye que es verdadero si falla. En cambio, en la lógica del default, un default que tiene como justificación sólo puede aplicarse 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 está libre de requisitos previos si no tiene ningún requisito previo (o, de manera equivalente, su requisito previo es tautológico ). Un incumplimiento es normal si tiene una única justificación que sea equivalente a su conclusión. Un valor predeterminado es sobrenormal si es a la vez categórico y normal. Un incumplimiento es seminormal si todas sus justificaciones implican su conclusión. Una teoría por defecto se llama categórica, normal, supernormal o seminormal si todos los valores por defecto 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 consistentes 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 por defecto a la teoría resultante. Cuando la teoría es tal que no se puede aplicar ningún otro valor predeterminado, la teoría se denomina extensión de la teoría predeterminada. Las reglas predeterminadas pueden aplicarse en diferente orden y esto puede dar lugar a diferentes extensiones. El ejemplo del diamante de Nixon es una teoría predeterminada con dos extensiones:

${\displaystyle \left\langle \left\{{\frac {\mathrm {Republican} (X):\neg \mathrm {Pacifist} (X)}{\neg \mathrm {Pacifist} (X)}},{\frac {\mathrm {Quaker} (X):\mathrm {Pacifist} (X)}{\mathrm {Pacifist} (X)}}\right\},\left\{\mathrm {Republican} (\mathrm {Nixon} ),\mathrm {Quaker} (\mathrm {Nixon} )\right\}\right\rangle }$

Dado que Nixon es a la vez republicano y cuáquero , se pueden aplicar ambas opciones. Sin embargo, la aplicación del primer defecto lleva a la conclusión de que Nixon no es pacifista, lo que hace que el segundo defecto no sea aplicable. De la misma manera, aplicando el segundo defecto obtenemos que Nixon es pacifista, por lo que el primer defecto no es aplicable. Esta particular teoría 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 todas las teorías son consistentes. La aplicación de este valor predeterminado 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\models \alpha }$ ${\displaystyle T\cup \{\beta _{i}\}}$ ${\displaystyle T\cup \{\gamma \}}$

T = W /* teoría actual */A = 0 /* conjunto de valores predeterminados aplicados hasta el momento */  /* aplicar una secuencia de valores predeterminados */mientras que hay una d predeterminada que no está en A y es aplicable a T sumar la consecuencia de d a T añadir d a A  /* verificación final de consistencia */si  por cada valor predeterminado d en A T es consistente con todas las justificaciones de dentonces salida T

Este algoritmo no es determinista , ya que alternativamente se pueden aplicar varios valores predeterminados a una teoría determinada T. En el ejemplo del diamante de Nixon, la aplicación del primer defecto conduce a una teoría a la que no se le puede aplicar el segundo defecto 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 verificació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 cuando esta verificación falla para cada secuencia posible de valores predeterminados aplicables. La siguiente teoría por defecto no tiene extensión:

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

Dado que es consistente con la teoría de fondo, se puede aplicar el valor predeterminado, lo que lleva a la conclusión de que es falso. Sin embargo, este resultado socava el supuesto 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 de incumplimiento normal, todos los incumplimientos son normales: cada incumplimiento tiene la forma . Se garantiza que una teoría de incumplimiento normal tendrá al menos una extensión. Además, las extensiones de una teoría normal del default 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 implicación de una fórmula a partir de una teoría predeterminada se puede definir de dos maneras:

Escéptico

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

Crédulo

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

Por tanto, 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 el pacifista (Nixon) ni el ¬pacifista (Nixon) están implicados escépticamente, mientras que ambos están implicados crédulamente. Como muestra este ejemplo, las crédulas consecuencias de una teoría del default pueden ser inconsistentes 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 incumplimiento si por ello el conjunto T se vuelve inconsistente con una justificación de un incumplimiento aplicado;

Conciso

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

Constreñido

un incumplimiento se aplica sólo 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 éste) es consistente;

Racional

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

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 lógica predeterminada

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

Variantes afirmativas

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 se ha supuesto que las fórmulas son consistentes para demostrar que p es verdadero. 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) llamada teoría de fondo y un conjunto de valores por defecto definidos como en la sintaxis original. Siempre que se aplica un defecto a una teoría asercional, 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 predeterminada acumulativa
• Compromiso con los supuestos de la lógica predeterminada.
• 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 incumplimientos aplicados, se verifica 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 subyacente; 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 simplemente porque, suponiendo que sea verdadera, la fórmula respalda el supuesto inicial. ${\displaystyle \Box x\rightarrow x}$ ${\displaystyle \Box x}$ ${\displaystyle \Box x\rightarrow x}$

Lógica predeterminada disyuntiva

la consecuencia de un incumplimiento 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 manera no determinista y se hace realidad.

Prioridades en materia de impagos

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

Variante estadística

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

Traducciones

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

Preservación de consecuencias

las teorías originales y traducidas tienen las mismas consecuencias (proposicionales);

Fiel

esta condición sólo 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 una correspondencia (típicamente, una biyección) entre las extensiones (o modelos) de las teorías original y traducida;

Modular

una traducción de una lógica por defecto a otra lógica es modular si los valores por defecto y la teoría de fondo se pueden traducir por separado; es más, la adición de fórmulas a la teoría de fondo sólo lleva a añadir 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

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 requiere que las traducciones sean fieles o al menos preserven las consecuencias, mientras que a veces se ignoran las condiciones de modularidad y 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 predeterminada;
• circunscripción.

Las traducciones existen o no dependiendo de las condiciones que se impongan. Las traducciones de la lógica proposicional predeterminada 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 polinómica colapse. Las traducciones a la lógica autoepistémica existen o no dependiendo de si se requiere modularidad o el uso de un 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 proposicional por defecto tiene al menos una extensión es completo; ${\displaystyle \Sigma _{2}^{P}}$

Vinculación escéptica

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

Implicación crédula

decidir si una teoría proposicional por defecto implica crédulamente una fórmula proposicional es completa; ${\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 modelos

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 que implementan lógicas predeterminadas son DeReS ^{[ enlace muerto permanente ]} , XRay, GADeL Archivado el 6 de abril de 2007 en Wayback Machine y Catala.

Ver también

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

Referencias

• G. Antoniou (1999). Un tutorial sobre lógicas predeterminadas. Encuestas de informática ACM , 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 . 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 Razonamiento y Representación 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 (principales) variantes. En Séptima Conferencia Europea sobre Enfoques Simbólicos y Cuantitativos para el 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 monótonas. Revista de Lógica y Computación , 2:397-425.
• G. Gottlob (1995). Traducir la lógica predeterminada a una lógica autoepistémica estándar. Revista de la 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émica, predeterminada y prioritaria, y la circunscripción paralela. En Actas del Sexto Taller Europeo sobre Lógica en Inteligencia Artificial (JELIA'98) , páginas 216-232.
• T. Janhunen (2003). Evaluación del efecto de la seminormalidad sobre la expresividad de los valores predeterminados. Inteligencia artificial , 144:233-250.
• SE 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 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 monótonas: razonamiento dependiente del contexto . Saltador.
• A. Mikitiuk y M. Truszczynski (1995). Lógicas de default restringidas y racionales. En Actas de la Decimocuarta Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI'95) , páginas 1509-1517.
• P. Nicolas, F. Saubion y I. Stéphan (2001). Heurística para un sistema de razonamiento lógico predeterminado Archivado el 7 de septiembre de 2017 en Wayback Machine . 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 demostrador de teoremas de tecnología de prólogo para el 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 limitada a recursos. En Actas del Décimo 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, Alan (1999). UMIST.ac.uk, Lógica predeterminada. Consultado el 10 de agosto de 2004.
• Stanford.edu, Razonamiento anulable, Enciclopedia de Filosofía de Stanford .