Lógica predeterminada

Tipo de lógica no monótona

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 cierto”; en cambio, la lógica estándar solo puede expresar que algo es cierto o que algo es falso. Esto es un problema porque el razonamiento a menudo implica 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 se puede expresar en lógica estándar ya sea por “todos los pájaros vuelan”, lo cual es incompatible con el hecho de que los pingüinos no vuelan, o por “todos los pájaros que no son pingüinos ni avestruces y… vuelan”, lo que requiere que se especifiquen todas las excepciones a la regla. La lógica por defecto 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 por defecto es un par de reglas . 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 por defecto , 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 Requisito previo es verdadero, y cada condición es consistente con nuestras creencias actuales, llegamos a creer que la Conclusión es verdadera. ${\displaystyle \mathrm {Justification} _{i}}$ ${\displaystyle i=1,\dots ,n}$

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

Ejemplos

La regla por defecto “los pájaros suelen volar” 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 de fondo que contiene algunos hechos sobre los pájaros 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 precondición Pájaro(Cóndor) es verdadera y la justificación Vuela(Cóndor) no es inconsistente con lo que se conoce actualmente. Por el contrario, Pájaro(Pingüino) no permite concluir Vuela(Pingüino) : incluso si la precondición del defecto Pájaro(Pingüino) es verdadera, la justificación Vuela(Pingüino) es inconsistente con lo que se conoce. A partir de esta teoría de fondo y este defecto, Pájaro(Abeja) no puede concluirse porque la regla por defecto solo permite derivar Vuela( X ) de Pájaro( X ) , pero no viceversa. 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 verdad se cree que es falso. Esto se conoce como la suposición 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 de programación Prolog utiliza una especie de suposición por defecto cuando se trata de la negación: si no se puede demostrar que un átomo negativo es verdadero, entonces se supone que es falso. Nótese, sin embargo, que Prolog utiliza la llamada negación como fallo : cuando el intérprete tiene que evaluar el átomo , intenta demostrar que F es verdadero, y concluye que es verdadero si falla. En la lógica por defecto, en cambio, un defecto que tiene como justificación 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 defecto es categórico o libre de prerrequisitos si no tiene prerrequisitos (o, equivalentemente, su prerrequisito es tautológico ). Un defecto es normal si tiene una única justificación que es equivalente a su conclusión. Un defecto es supernormal si es tanto categórico como normal. Un defecto 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 prerrequisitos que contiene son categóricos, normales, supernormales o seminormales, respectivamente.

Semántica de la lógica por defecto

Una regla por defecto puede aplicarse 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. Otras reglas por defecto pueden entonces aplicarse a la teoría resultante. Cuando la teoría es tal que no puede aplicarse ninguna otra regla por defecto, la teoría se denomina extensión de la teoría por defecto. Las reglas por defecto pueden aplicarse en un orden diferente, y esto puede llevar a diferentes extensiones. El ejemplo del diamante de Nixon es una teoría por defecto 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 republicano y cuáquero , se pueden aplicar ambos supuestos por defecto. Sin embargo, la aplicación del primer supuesto por defecto lleva a la conclusión de que Nixon no es pacifista, lo que hace que el segundo supuesto por defecto no sea aplicable. De la misma manera, la aplicación del segundo supuesto por defecto nos lleva a la conclusión de que Nixon es pacifista, lo que hace que el primer supuesto por defecto no sea aplicable. Por tanto, esta teoría por defecto en particular tiene 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 por defecto se basaba en el punto fijo de una función. La siguiente es una definición algorítmica equivalente. Si un defecto contiene fórmulas con variables libres, se considera que representa el conjunto de todos los defectos obtenidos al dar un valor a todas estas variables. Un defecto es aplicable a una teoría proposicional T si y todas las teorías 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: ${\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 existe un d predeterminado que no está en A y es aplicable a T Añade la consecuencia de d a T añadir d a A  /* comprobación final de consistencia */Si  por cada defecto d en A T es consistente con todas las justificaciones de dentonces salida T

Este algoritmo no es determinista , ya que se pueden aplicar alternativamente varios valores predeterminados a una teoría dada T. 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 valores predeterminados que se han aplicado implica que algunas teorías no tienen ninguna extensión. En particular, esto sucede cuando esta comprobación falla para cada posible secuencia de valores predeterminados aplicables. La siguiente teoría predeterminada no tiene ninguna 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 base, se puede aplicar la regla por defecto, lo que lleva a la conclusión de que es falsa. Sin embargo, este resultado socava el supuesto que se ha hecho para aplicar la primera regla por defecto. En consecuencia, esta teoría no tiene extensiones. ${\displaystyle A(b)}$ ${\displaystyle A(b)}$

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

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 puede definirse de dos maneras:

Escéptico

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

Crédulo

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

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

Reglas de inferencia alternativas predeterminadas

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

Justificado

se diferencia del original en que no se aplica un valor predeterminado si con ello el conjunto T se vuelve inconsistente con una justificación de un valor predeterminado aplicado;

Conciso

un valor predeterminado se aplica sólo si su consecuencia no está ya implícita en 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 valor predeterminado se aplica sólo 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 éste) es consistente;

Racional

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

Precavido

Los valores predeterminados que se pueden aplicar pero que son conflictivos 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 asertivas

Una aserción es un par compuesto por una fórmula y un conjunto de fórmulas. Dicho par indica que p es verdadero, mientras que las fórmulas se han asumido 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 predeterminados definidos como en la sintaxis original. Siempre que se aplica un valor predeterminado 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 por defecto
• Compromiso con supuestos de lógica predeterminada
• Lógica cuasidefectiva

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, se comprueba la validez de las precondiciones en la extensión que se generará; en otras palabras, el algoritmo para generar extensiones comienza adivinando una teoría y utilizá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 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 verdadero solo porque, suponiendo que es verdadero, la fórmula respalda el supuesto inicial. ${\displaystyle \Box x\rightarrow x}$ ${\displaystyle \Box x}$ ${\displaystyle \Box x\rightarrow x}$

Lógica disyuntiva por defecto

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 manera no determinista y se hace verdadera.

Prioridades en los impagos

La prioridad relativa de los valores predeterminados puede especificarse 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 de los valores predeterminados no requieren que se especifiquen explícitamente las prioridades; más bien, se prefieren los valores predeterminados más específicos (aquellos que son aplicables en menos casos) sobre 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 la fracción de veces que se aplica.

Traducciones

Las teorías por defecto pueden traducirse a teorías de otras lógicas y viceversa. Se han tenido en cuenta las siguientes condiciones de traducción:

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 la lógica por defecto o entre la lógica por defecto y una lógica en la que existe un concepto similar a la extensión, por ejemplo, los modelos en lógica modal ; una traducción es fiel si existe una correspondencia (normalmente, una biyección) entre las extensiones (o modelos) de las teorías originales y traducidas;

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; además, la adición de fórmulas a la teoría de fondo sólo conduce a agregar las nuevas fórmulas al resultado de la traducción;

Mismo alfabeto

Las teorías originales y traducidas se construyen sobre 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 preserven las consecuencias, mientras que a veces se ignoran las condiciones de modularidad y de 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.

Existen o no traducciones según 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 según se requiera 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 -completo; ${\displaystyle \Sigma _{2}^{P}}$

Implicación escéptica

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

Implicación crédula

Decidir si una teoría proposicional por defecto 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 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.

Véase también

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

Referencias

• 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 y Razonamiento del Conocimiento (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 (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. 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 de la traducción de valores predeterminados a circunscripciones. Inteligencia artificial , 32:131-146.
• T. Janhunen (1998). Sobre la intertraducibilidad de las lógicas autoepistémicas, por defecto y prioritarias, 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 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. Computational Intelligence , 22(1): 26-51.
• P. Liberatore y M. Schaerf (1998). La complejidad de la comprobació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. Computational Intelligence , 4(1):1-16.
• W. Marek y M. Truszczynski (1993). Lógica no monótona: razonamiento dependiente del contexto . Springer.
• A. Mikitiuk y M. Truszczynski (1995). Lógicas por defecto racionales y restringidas. 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ísticas para un sistema de razonamiento lógico por defecto 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 prolog para razonamiento por defecto: 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 por defecto limitada por recursos. 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 estadística por defecto. En Actas de la 9.ª Conferencia Europea sobre Lógica en Inteligencia Artificial (JELIA 2004) , LNCS Series, Springer, páginas 121-133.

Enlaces externos

• Schmidt, Charles F. RCI.Rutgers.edu, Default Logic. Consultado el 10 de agosto de 2004.
• Ramsay, Allan (1999). UMIST.ac.uk, Default Logic. Consultado el 10 de agosto de 2004.
• Stanford.edu, Razonamiento derrotable, Enciclopedia de Filosofía de Stanford .