La circunscripción es una lógica no monótona creada por John McCarthy para formalizar la suposición de sentido común de que las cosas son como se espera a menos que se especifique lo contrario. [1] [2] La circunscripción fue utilizada más tarde por McCarthy en un intento de resolver el problema del marco . Para implementar la circunscripción en su formulación inicial, McCarthy aumentó la lógica de primer orden para permitir la minimización de la extensión de algunos predicados, donde la extensión de un predicado es el conjunto de tuplas de valores en los que el predicado es verdadero. Esta minimización es similar a la suposición del mundo cerrado de que lo que no se sabe que es cierto es falso.[3]
El problema original considerado por McCarthy era el de los misioneros y los caníbales : hay tres misioneros y tres caníbales en una orilla de un río; tienen que cruzar el río usando un bote que solo puede llevar dos, con la restricción adicional de que los caníbales nunca deben superar en número a los misioneros en ninguna de las orillas (ya que de lo contrario los misioneros serían asesinados y, presumiblemente, devorados). El problema considerado por McCarthy no fue el de encontrar una secuencia de pasos para alcanzar la meta (el artículo sobre el problema de los misioneros y caníbales contiene una de esas soluciones), sino más bien el de excluir condiciones que no están explícitamente declaradas. Por ejemplo, la solución “ir media milla al sur y cruzar el río por el puente” intuitivamente no es válida porque el planteamiento del problema no menciona tal puente. Por otro lado, la existencia de este puente tampoco se excluye del planteamiento del problema. Que el puente no existe es una consecuencia del supuesto implícito de que el enunciado del problema contiene todo lo que es relevante para su solución. Declarar explícitamente que no existe un puente no es una solución a este problema, ya que existen muchas otras condiciones excepcionales que conviene excluir (como la presencia de una cuerda para sujetar a los caníbales, la presencia de un barco más grande cerca, etc. )
Más tarde, McCarthy utilizó la circunscripción para formalizar el supuesto implícito de inercia : las cosas no cambian a menos que se especifique lo contrario. La circunscripción pareció ser útil para evitar especificar que las condiciones no son cambiadas por todas las acciones excepto aquellas que se sabe explícitamente que las cambian; esto se conoce como el problema del marco . Sin embargo, más tarde se demostró que la solución propuesta por McCarthy conducía a resultados incorrectos en algunos casos, como en el escenario del problema de disparos de Yale . Existen otras soluciones al problema del marco que formalizan correctamente el problema del rodaje de Yale; algunos usan la circunscripción pero de una manera diferente.
El caso proposicional
Si bien la circunscripción se definió inicialmente en el caso lógico de primer orden, la particularización al caso proposicional es más fácil de definir. [4] Dada una fórmula proposicional , su circunscripción es la fórmula que tiene sólo los modelos de que no asignan una variable a verdadero a menos que sea necesario.
Formalmente, los modelos proposicionales se pueden representar mediante conjuntos de variables proposicionales ; es decir, cada modelo está representado por el conjunto de variables proposicionales que asigna a verdadero. Por ejemplo, el modelo que asigna verdadero a, falso a y fiel a está representado por el conjunto , porque y son exactamente las variables que este modelo asigna como verdaderas.
Dados dos modelos y representado de esta manera, la condición es equivalente a establecer en verdadero cada variable que establece en verdadero. En otras palabras, modela la relación de "ajuste a verdaderas menos variables". significa que pero estos dos modelos no coinciden.
Esto nos permite definir modelos que no asignan variables a verdadero a menos que sea necesario. Un modelode una teoría se llama mínimo , si y solo si no hay modelo de para cual .
La circunscripción se expresa seleccionando solo los modelos mínimos. Se define de la siguiente manera:
Alternativamente, se puede definir como una fórmula que tiene exactamente el conjunto de modelos anterior; Además, también se puede evitar dar una definición de y solo define la inferencia mínima como si y solo si cada modelo mínimo de es también un modelo de .
Como ejemplo, la fórmula tiene tres modelos:
- , , son verdaderas, es decir ;
- y son verdaderas, es falso, es decir ;
- y son verdaderas, es falso, es decir .
El primer modelo no es mínimo en el conjunto de variables que asigna a verdadero. De hecho, el segundo modelo hace las mismas asignaciones excepto por, que se asigna a falso y no a verdadero. Por tanto, el primer modelo no es mínimo. El segundo y tercer modelo son incomparables: mientras que el segundo asigna fiel a, el tercero asigna fiel a en lugar de. Por tanto, los modelos que circunscribenson el segundo y tercer modelo de la lista. Una fórmula proposicional que tiene exactamente estos dos modelos es la siguiente:
Intuitivamente, en la circunscripción una variable se asigna a verdadero solo si es necesario. Doblemente, si una variable puede ser falsa, debe ser falsa. Por ejemplo, al menos uno de y debe asignarse a verdadero de acuerdo con ; en la circunscripción exactamente una de las dos variables debe ser verdadera. La variable no puede ser falso en ningún modelo de y ninguno de la circunscripción.
Predicados fijos y variables
La extensión de la circunscripción con predicados fijos y variables se debe a Vladimir Lifschitz . [5] La idea es que algunas condiciones no deben minimizarse. En términos de lógica proposicional, algunas variables no deben falsificarse si es posible. En particular, se pueden considerar dos tipos de variables:
- variar
- estas son variables que no deben tenerse en cuenta en absoluto en el curso de la minimización;
- reparado
- estas son variables consideradas fijas mientras se realiza una minimización; en otras palabras, la minimización solo se puede hacer comparando modelos con los mismos valores de estas variables.
La diferencia es que simplemente se supone que el valor de las diferentes condiciones no importa. En cambio, las condiciones fijas caracterizan una situación posible, de modo que no tiene sentido comparar dos situaciones en las que estas condiciones tienen un valor diferente.
Formalmente, la extensión de la circunscripción que incorpora variables variables y fijas es la siguiente, donde es el conjunto de variables a minimizar, las variables fijas, y las variables variables son aquellas que no están en :
En palabras, la minimización de las variables asignadas a verdadero solo se realiza para las variables en ; Además, los modelos solo se comparan si asignan los mismos valores a las variables de. Todas las demás variables no se tienen en cuenta al comparar modelos.
La solución al problema del marco propuesta por McCarthy se basa en la circunscripción sin condiciones fijas. En el caso proposicional, esta solución se puede describir de la siguiente manera: además de las fórmulas que codifican directamente lo conocido, también se definen nuevas variables que representan cambios en los valores de las condiciones; estas nuevas variables luego se minimizan.
Por ejemplo, del dominio en el que hay una puerta que se cierra en el tiempo 0 y en el que la acción de abrir la puerta se ejecuta en el tiempo 2, lo que se conoce explícitamente está representado por las dos fórmulas:
El problema del marco se muestra en este ejemplo como el problema que no es consecuencia de las fórmulas anteriores, mientras que se supone que la puerta debe permanecer cerrada hasta que se realice la acción de abrirla. La circunscripción se puede utilizar para este fin mediante la definición de nuevas variables. para modelar cambios y luego minimizarlos:
- ...
Como muestra el problema de disparo de Yale , este tipo de solución no funciona. Por ejemplo, todavía no está implicado por la circunscripción de las fórmulas anteriores: el modelo en el que es cierto y es falso es incomparable con el modelo con los valores opuestos. Por tanto, la situación en la que la puerta se abre en el momento 1 y luego permanece abierta como consecuencia de la acción no está excluida por la circunscripción.
Se han desarrollado varias otras formalizaciones de dominios dinámicos que no sufren tales problemas (consulte el problema del marco para una descripción general). Muchos utilizan la circunscripción pero de forma diferente.
Circunscripción de predicados
La definición original de circunscripción propuesta por McCarthy tiene que ver con la lógica de primer orden. El papel de las variables en la lógica proposicional (algo que puede ser verdadero o falso) lo juegan los predicados en la lógica de primer orden. Es decir, una fórmula proposicional se puede expresar en lógica de primer orden reemplazando cada variable proposicional con un predicado de aridad cero (es decir, un predicado sin argumentos). Por lo tanto, la minimización se realiza en predicados en la versión lógica de primer orden de la circunscripción: la circunscripción de una fórmula se obtiene obligando a los predicados a ser falsos siempre que sea posible. [6]
Dada una fórmula lógica de primer orden que contiene un predicado , circunscribir este predicado equivale a seleccionar sólo los modelos de en el cual se asigna a verdadero en un conjunto mínimo de tuplas de valores.
Formalmente, la extensión de un predicado en un modelo de primer orden es el conjunto de tuplas de valores que este predicado asigna a verdadero en el modelo. De hecho, los modelos de primer orden incluyen la evaluación de cada símbolo de predicado; tal evaluación dice si el predicado es verdadero o falso para cualquier valor posible de sus argumentos. [7] Dado que cada argumento de un predicado debe ser un término, y cada término se evalúa como un valor, los modelos indican si es cierto para cualquier posible tupla de valores . La extensión de en un modelo es el conjunto de tuplas de términos tales que es cierto en el modelo.
La circunscripción de un predicado en una fórmula se obtiene seleccionando solo los modelos de con una extensión mínima de . Por ejemplo, si una fórmula tiene solo dos modelos, difieren solo porquees verdadero en uno y falso en el segundo, entonces solo se selecciona el segundo modelo. Esto es porque está en la extensión de en el primer modelo pero no en el segundo.
La definición original de McCarthy era más sintáctica que semántica. Dada una fórmula y un predicado , circunscribiendo en es la siguiente fórmula de segundo orden:
En esta fórmula es un predicado de la misma aridad que . Ésta es una fórmula de segundo orden porque contiene una cuantificación sobre un predicado. La subfórmula es una abreviatura de:
En esta fórmula, es una n-tupla de términos, donde n es la aridad de . Esta fórmula establece que se debe hacer una minimización de la extensión: para una evaluación de la verdad en de un modelo que se está considerando, debe darse el caso de que ningún otro predicado puede asignar a falso cada tupla que asigna a falso y, sin embargo, es diferente de .
Esta definición solo permite circunscribir un único predicado. Si bien la extensión a más de un predicado es trivial, minimizar la extensión de un solo predicado tiene una aplicación importante: capturar la idea de que las cosas suelen ser como se esperaba. Esta idea se puede formalizar minimizando un solo predicado que exprese la anormalidad de las situaciones. En particular, cada hecho conocido se expresa en lógica con la adición de un literaldeclarando que el hecho es válido solo en situaciones normales. Minimizar la extensión de este predicado permite razonar bajo la suposición implícita de que las cosas son como se esperaba (es decir, que no son anormales), y que esta suposición se hace solo si es posible (la anormalidad se puede asumir como falsa solo si esto es consistente con el hechos.)
Circunscripción puntual
La circunscripción puntual es una variante de la circunscripción de primer orden que ha sido introducida por Vladimir Lifschitz . [8] En el caso proposicional, la circunscripción puntual y predicada coinciden. La lógica de la circunscripción puntual es que minimiza el valor de un predicado para cada tupla de valores por separado, en lugar de minimizar la extensión del predicado. Por ejemplo, hay dos modelos de con dominio , un escenario y el otro escenario . Desde la extensión de en el primer modelo es mientras que la extensión para el segundo es , la circunscripción solo selecciona el primer modelo.
En la circunscripción puntual, cada tupla de valores se considera por separado. Por ejemplo, en la fórmula uno consideraría el valor de por separado de . Un modelo es mínimo solo si no es posible convertir dicho valor de verdadero a falso sin dejar de satisfacer la fórmula. Como resultado, el modelo en el que se selecciona por circunscripción puntual porque girando sólo en falso no satisface la fórmula, y lo mismo ocurre con .
Circunscripción de dominio y fórmula
Una formulación anterior de la circunscripción de McCarthy se basa en minimizar el dominio de los modelos de primer orden, más que en la extensión de los predicados. Es decir, un modelo se considera menos que otro si tiene un dominio más pequeño y los dos modelos coinciden en la evaluación de las tuplas de valores comunes. Esta versión de la circunscripción se puede reducir a la circunscripción predicada.
La circunscripción de fórmulas fue un formalismo posterior introducido por McCarthy. Se trata de una generalización de la circunscripción en la que se minimiza la extensión de una fórmula, más que la extensión de un predicado. En otras palabras, se puede especificar una fórmula para que el conjunto de tuplas de valores del dominio que satisfacen la fórmula se haga lo más pequeño posible.
Frenar la teoría
La circunscripción no siempre maneja correctamente la información disyuntiva. Ray Reiter proporcionó el siguiente ejemplo: se lanza una moneda sobre un tablero de ajedrez y el resultado es que la moneda está en un área negra, en un área blanca o en ambas. Sin embargo, hay una gran cantidad de otros lugares posibles donde se supone que la moneda no debe estar encendida; por ejemplo, está implícito que la moneda no está en el suelo, ni en el frigorífico, ni en la superficie de la luna. Por tanto, la circunscripción se puede utilizar para minimizar la extensión de predicado, de modo que es falso incluso si no se indica explícitamente.
Por otro lado, la minimización de la El predicado conduce al resultado incorrecto de que la moneda está en un área negra o en un área blanca, pero no en ambas . Esto se debe a que los modelos en los que es cierto solo en y solo en tener una extensión mínima de , mientras que el modelo en el que la extensión de está compuesto por ambos pares no es mínimo.
El freno teórico es una solución propuesta por Thomas Eiter , Georg Gottlob y Yuri Gurevich . [9] La idea es que el modelo que la circunscripción no selecciona, aquel en el que ambos y son verdaderas, es un modelo de la fórmula que es mayor (wrt la extensión de ) que los dos modelos seleccionados. Más específicamente, entre los modelos de la fórmula, el modelo excluido es el límite superior mínimo de los dos modelos seleccionados. El encintado teórico selecciona los modelos de límites superiores mínimos además de los seleccionados por circunscripción. Esta inclusión se realiza hasta que se cierra el conjunto de modelos, en el sentido de que incluye todos los límites superiores mínimos de todos los conjuntos de modelos que contiene.
Ver también
Referencias
- ^ McCarthy, J. (febrero de 1986). "Aplicaciones de la circunscripción a la formalización del conocimiento de sentido común". Inteligencia artificial. 28 (1): 89-116. doi: 10.1016 / 0004-3702 (86) 90032-9.
- ^ McCarthy, J. (abril de 1980). "Circunscripción - una forma de razonamiento no monótono". Inteligencia artificial. 13: 27–39. doi: 10.1016 / 0004-3702 (80) 90011-9.
- ^ Eiter, T .; Gottlob, G. (junio de 1993). "La circunscripción proposicional y el razonamiento extendido del mundo cerrado son \ Pi ^ p_2-completos". Informática Teórica. 114 (2): 231–245. doi: 10.1016 / 0304-3975 (93) 90073-3.
- ↑ Cadoli, M .; Lenzerini, M. (abril de 1994). "La complejidad del razonamiento proposicional del mundo cerrado y la circunscripción". Revista de Ciencias de la Computación y Sistemas. 48 (2): 255–310. doi: 10.1016 / S0022-0000 (05) 80004-2.
- ^ Lifschitz, V. (noviembre de 1985). "Bases de datos de mundo cerrado y circunscripción". Inteligencia artificial. 27: 229-235. doi: 10.1016 / 0004-3702 (85) 90055-4.
- ^ Lifschitz, V. (1994). "Circunscripción". En Gabbay, DM; Hogger, CJ; Robinson, JA Razonamiento no monótono y razonamiento incierto. Manuales de Lógica en Informática e Inteligencia Artificial y Programación Lógica. 3. Oxford University Press. págs. 297–352. ISBN 0198537476 .
- ^ Cadoli, M. (noviembre de 1992). "La complejidad del modelo de comprobación de fórmulas circunscriptivas". Cartas de procesamiento de información. 44 (3): 113–8. doi: 10.1016 / 0020-0190 (92) 90049-2.
- ^ Lifschitz, V. (1986). "Circunscripción puntual". Actas AAAI-86 Quinta Conferencia Nacional sobre Inteligencia Artificial, 11-15 de agosto de 1986, Filadelfia, PA. págs. 406–410. ISBN 0934613133 .
- ^ Eiter, T .; Gottlob, G .; Gurevich, Y. (1993). "¡CURVA tu teoría!". En Bajcsy, Ruzena. IJCAI-93: actas de la Decimotercera Conferencia Internacional Conjunta sobre Inteligencia Artificial, Chambéry, Francia, 28 de agosto a 3 de septiembre de 1993. IJCAII. págs. 634–9. ISBN 155860300X .