Circunscripción (lógica)

Lógica no monótona creada por John McCarthy

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]} McCarthy utilizó más tarde la circunscripción 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 de mundo cerrado de que lo que no se sabe que es verdadero 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 utilizando un bote que sólo puede llevar a 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, comidos). El problema considerado por McCarthy no era el de encontrar una secuencia de pasos para alcanzar la meta (el artículo sobre el problema de los misioneros y los caníbales contiene una de esas soluciones), sino más bien el de excluir condiciones que no están explícitamente enunciadas. Por ejemplo, la solución "ir media milla al sur y cruzar el río por el puente" es intuitivamente no válida porque el enunciado del problema no menciona tal puente. Por otra parte, la existencia de este puente tampoco está excluida por el enunciado del problema. Que el puente no exista es una consecuencia de la suposición implícita de que el enunciado del problema contiene todo lo que es relevante para su solución. Decir explícitamente que no existe un puente no es una solución a este problema, ya que hay muchas otras condiciones excepcionales que deberían excluirse (como la presencia de una cuerda para atar a los caníbales, la presencia de un barco más grande cerca, etc.)

La circunscripción fue utilizada posteriormente por McCarthy para formalizar el supuesto implícito de inercia : las cosas no cambian a menos que se especifique lo contrario. La circunscripción parecía ser útil para evitar especificar que las condiciones no cambian con 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 erróneos en algunos casos, como en el escenario del problema del tiroteo de Yale . Existen otras soluciones al problema del marco que formalizan correctamente el problema del tiroteo de Yale; algunas utilizan la circunscripción, pero de una manera diferente.

El caso proposicional

Si bien la circunscripción se definió inicialmente en el caso de la lógica 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 solo los modelos de que no asignan una variable a verdadera a menos que sea necesario. ${\displaystyle T}$ ${\displaystyle T}$

Formalmente, los modelos proposicionales pueden representarse 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 verdadero a está representado por el conjunto , porque y son exactamente las variables que este modelo asigna a verdadero. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \{a,c\}}$ ${\displaystyle a}$ ${\displaystyle c}$

Dados dos modelos y representados de esta manera, la condición es equivalente a poner como verdadera cada variable que se ponga como verdadera. En otras palabras, modela la relación de "poner como verdaderas menos variables". significa que pero estos dos modelos no coinciden. ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle N\subseteq M}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle \subseteq }$ ${\displaystyle N\subset M}$ ${\displaystyle N\subseteq M}$

Esto nos permite definir modelos que no asignan variables a true a menos que sea necesario. Un modelo de una teoría se llama minimal si y solo si no existe un modelo de para el cual . ${\displaystyle M}$ ${\displaystyle T}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle N\subset M}$

La circunscripción se expresa seleccionando únicamente los modelos mínimos. Se define de la siguiente manera:

${\displaystyle CIRC(T)=\{M~|~M{\mbox{ is a minimal model of }}T\}}$

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 definir la inferencia mínima como si y solo si cada modelo mínimo de es también un modelo de . ${\displaystyle CIRC(T)}$ ${\displaystyle CIRC}$ ${\displaystyle T\models _{M}Q}$ ${\displaystyle T}$ ${\displaystyle Q}$

A modo de ejemplo, la fórmula tiene tres modelos: ${\displaystyle T=a\land (b\lor c)}$

1. ${\displaystyle a}$, , son verdaderas, es decir ; ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \{a,b,c\}}$
2. ${\displaystyle a}$y son verdaderas, es falsa, es decir ; ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \{a,b\}}$
3. ${\displaystyle a}$y son verdaderas, es falsa, es decir . ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle \{a,c\}}$

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 para , que se asigna a falso y no a verdadero. Por lo tanto, el primer modelo no es mínimo. El segundo y el tercer modelo son incomparables: mientras que el segundo asigna verdadero a , el tercero asigna verdadero a en cambio. Por lo tanto, los modelos que se circunscriben son el segundo y el tercer modelo de la lista. Una fórmula proposicional que tiene exactamente estos dos modelos es la siguiente: ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle T}$

${\displaystyle a\land \neg (b\leftrightarrow c)}$

Intuitivamente, en la circunscripción una variable se asigna a verdadera solo si esto es necesario. Dualmente, si una variable puede ser falsa, debe ser falsa. Por ejemplo, al menos una de y debe asignarse a verdadera según ; en la circunscripción exactamente una de las dos variables debe ser verdadera. La variable no puede ser falsa en ningún modelo de y ninguno de la circunscripción. ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle T}$

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 ser falsadas si es posible. En particular, se pueden considerar dos tipos de variables:

diverso

Se trata de variables que no deben tenerse en cuenta en absoluto durante el proceso de minimización;

fijado

Estas son variables que se consideran fijas al realizar una minimización; en otras palabras, la minimización solo se puede realizar comparando modelos con los mismos valores de estas variables.

La diferencia es que simplemente se supone que el valor de las condiciones variables no importa. Las condiciones fijas, en cambio, caracterizan una situación posible, de modo que comparar dos situaciones en las que estas condiciones tienen valores diferentes no tiene sentido.

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 : ${\displaystyle P}$ ${\displaystyle Z}$ ${\displaystyle P\cup Z}$

${\displaystyle {\text{CIRC}}(T;P,Z)=\{M~|~M\models T{\text{ and }}\not \exists N{\text{ such that }}N\models T,~N\cap P\subset M\cap P{\text{ and }}N\cap Z=M\cap Z\}}$

En otras palabras, la minimización de las variables asignadas a true 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. ${\displaystyle P}$ ${\displaystyle Z}$

La solución al problema de los marcos propuesta por McCarthy se basa en una circunscripción sin condiciones fijas. En el caso proposicional, esta solución puede describirse de la siguiente manera: además de las fórmulas que codifican directamente lo que se sabe, se definen también nuevas variables que representan cambios en los valores de las condiciones; estas nuevas variables se minimizan.

Por ejemplo, del dominio en el que hay una puerta que está cerrada 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 se representa mediante las dos fórmulas:

${\displaystyle \neg {\text{open}}_{0}}$

${\displaystyle {\text{true}}\rightarrow {\text{open}}_{2}}$

El problema del marco se muestra en este ejemplo como un problema que no es consecuencia de las fórmulas anteriores, ya 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 definiendo nuevas variables para modelar los cambios y luego minimizándolos: ${\displaystyle \neg open_{1}}$ ${\displaystyle change\_open_{t}}$

${\displaystyle {\text{change open}}_{0}\equiv ({\text{open}}_{0}\not \equiv {\text{open}}_{1})}$

${\displaystyle {\text{change open}}_{1}\equiv ({\text{open}}_{1}\not \equiv {\text{open}}_{2})}$

...

Como lo demuestra el problema del tiroteo de Yale , este tipo de solución no funciona. Por ejemplo, todavía no está excluida por la circunscripción de las fórmulas anteriores: el modelo en el que es verdadero y es falso es incomparable con el modelo con los valores opuestos. Por lo 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. ${\displaystyle \neg {\text{open}}_{1}}$ ${\displaystyle {\text{change open}}_{0}}$ ${\displaystyle {\text{change open}}_{1}}$

Se han desarrollado otras formalizaciones de dominios dinámicos que no sufren estos problemas (véase el problema del marco para una descripción general). Muchas utilizan la circunscripción, pero de una manera diferente.

Circunscripción predicativa

La definición original de circunscripción propuesta por McCarthy se refiere a la lógica de primer orden. El papel de las variables en la lógica proposicional (algo que puede ser verdadero o falso) lo desempeñan en la lógica de primer orden los predicados. Es decir, una fórmula proposicional se puede expresar en la lógica de primer orden reemplazando cada variable proposicional por un predicado de aridad cero (es decir, un predicado sin argumentos). Por lo tanto, la minimización se realiza sobre los predicados en la versión de la circunscripción en la lógica de primer orden: la circunscripción de una fórmula se obtiene forzando 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 solo los modelos de en los que se asigna como verdadero en un conjunto mínimo de tuplas de valores. ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle T}$ ${\displaystyle P}$

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. Los modelos de primer orden de hecho incluyen la evaluación de cada símbolo de predicado; dicha evaluación indica 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 evalúa un valor, el modelo indica si es verdadero para cualquier tupla posible de valores . La extensión de en un modelo es el conjunto de tuplas de términos tales que es verdadero en el modelo. ${\displaystyle P(v_{1},\ldots ,v_{n})}$ ${\displaystyle \langle v_{1},\ldots ,v_{n}\rangle }$ ${\displaystyle P}$ ${\displaystyle P(v_{1},\ldots ,v_{n})}$

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, que difieren solo porque es verdadera en uno y falsa en el segundo, entonces solo se selecciona el segundo modelo. Esto se debe a que está en la extensión de en el primer modelo pero no en el segundo. ${\displaystyle P}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle P(v_{1},\ldots ,v_{n})}$ ${\displaystyle \langle v_{1},\ldots ,v_{n}\rangle }$ ${\displaystyle P}$

La definición original de McCarthy era sintáctica más que semántica. Dada una fórmula y un predicado , la circunscripción en es la siguiente fórmula de segundo orden: ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle T}$

${\displaystyle T(P)\wedge \forall p\neg (T(p)\wedge p<P)}$

En esta fórmula hay un predicado de la misma aridad que . Esta es una fórmula de segundo orden porque contiene una cuantificación sobre un predicado. La subfórmula es una abreviatura de: ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle p<P}$

${\displaystyle \forall x(p(x)\rightarrow P(x))\wedge \neg \forall x(P(x)\rightarrow p(x))}$

En esta fórmula, es una n-tupla de términos, donde n es la aridad de . Esta fórmula establece que se debe realizar una minimización de la extensión: para que se pueda realizar una evaluación de verdad en un modelo que se está considerando, debe darse el caso de que ningún otro predicado pueda asignar a falso cada tupla que asigna a falso y, sin embargo, es diferente de . ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle P}$

Esta definición sólo permite circunscribir un único predicado. Si bien la extensión a más de un predicado es trivial, minimizar la extensión de un único predicado tiene una aplicación importante: captar la idea de que las cosas suelen ser como se espera. Esta idea se puede formalizar minimizando un único predicado que exprese la anormalidad de las situaciones. En particular, cada hecho conocido se expresa en lógica con la adición de un literal que establece que el hecho se cumple sólo en situaciones normales. Minimizar la extensión de este predicado permite razonar bajo el supuesto implícito de que las cosas son como se espera (es decir, no son anormales), y que este supuesto se hace sólo si es posible (la anormalidad se puede suponer falsa sólo si esto es coherente con los hechos). ${\displaystyle \neg Abnormal(...)}$

Circunscripción puntual

La circunscripción puntual es una variante de la circunscripción de primer orden que fue introducida por Vladimir Lifschitz . ^[8] La razón de ser 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 , uno que establece y el otro que establece . Dado que 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 el caso proposicional, la circunscripción puntual y la circunscripción de predicado coinciden. ${\displaystyle P(a)\equiv P(b)}$ ${\displaystyle \{a,b\}}$ ${\displaystyle P(a)=P(b)=false}$ ${\displaystyle P(a)=P(b)=true}$ ${\displaystyle P}$ ${\displaystyle \emptyset }$ ${\displaystyle \{a,b\}}$

En la circunscripción puntual, cada tupla de valores se considera por separado. Por ejemplo, en la fórmula se consideraría el valor de por separado de . Un modelo es mínimo solo si no es posible convertir cualquier valor de este tipo de verdadero a falso sin dejar de satisfacer la fórmula. Como resultado, el modelo en el que se selecciona mediante la circunscripción puntual porque convertir solo en falso no satisface la fórmula, y lo mismo sucede con . ${\displaystyle P(a)\equiv P(b)}$ ${\displaystyle P(a)}$ ${\displaystyle P(b)}$ ${\displaystyle P(a)=P(b)=true}$ ${\displaystyle P(a)}$ ${\displaystyle P(b)}$

Circunscripción de dominio y fórmula

Una formulación anterior de la circunscripción de McCarthy se basa en la minimización del dominio de los modelos de primer orden, en lugar de la extensión de los predicados. Es decir, un modelo se considera menor que otro si tiene un dominio menor 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 de predicados.

La circunscripción de fórmulas fue un formalismo introducido posteriormente por McCarthy. Se trata de una generalización de la circunscripción en la que se minimiza la extensión de una fórmula, en lugar de la extensión de un predicado. En otras palabras, se puede especificar una fórmula de modo que el conjunto de tuplas de valores del dominio que satisfacen la fórmula sea lo más pequeño posible.

Teoría de la restricción

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, o en un área blanca, o en ambas. Sin embargo, hay una gran cantidad de otros lugares posibles donde se supone que la moneda no está; por ejemplo, está implícito que la moneda no está en el piso, o en el refrigerador, o en la superficie de la Luna. Por lo tanto, la circunscripción se puede utilizar para minimizar la extensión del predicado, de modo que sea falso incluso si esto no se afirma explícitamente. ${\displaystyle On}$ ${\displaystyle On({\text{coin}},{\text{moon}})}$

Por otra parte, la minimización del predicado conduce al resultado erróneo 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 verdadero solo en y solo en tienen una extensión mínima de , mientras que el modelo en el que la extensión de está compuesta por ambos pares no es mínima. ${\displaystyle On}$ ${\displaystyle On}$ ${\displaystyle ({\text{coin}},{\text{white area}})}$ ${\displaystyle ({\text{coin}},{\text{black area}})}$ ${\displaystyle On}$ ${\displaystyle On}$

La restricción teórica 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 tanto y son verdaderos, es un modelo de la fórmula que es mayor (con respecto a la extensión de ) que ambos modelos que se seleccionan. 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. La restricción teórica selecciona dichos modelos de límites superiores mínimos además de los seleccionados por la circunscripción. Esta inclusión se realiza hasta que el conjunto de modelos se cierra, en el sentido de que incluye todos los límites superiores mínimos de todos los conjuntos de modelos que contiene. ${\displaystyle On({\text{coin}},{\text{white area}})}$ ${\displaystyle On({\text{coin}},{\text{black area}})}$ ${\displaystyle On}$

Véase también

• Razonamiento derrotable  : razonamiento que es racionalmente convincente, aunque no deductivamente válido.
• Vinculación preferencial

Referencias

1. McCarthy, J. (febrero de 1986). "Aplicaciones de la circunscripción para formalizar el conocimiento de sentido común". Inteligencia artificial. 28 (1): 89–116. doi:10.1016/0004-3702(86)90032-9.
2. 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.
3. Eiter, T.; Gottlob, G. (junio de 1993). "La circunscripción proposicional y el razonamiento de mundo cerrado extendido son \Pi^p_2-completos". Ciencias de la Computación Teórica. 114 (2): 231–245. doi:10.1016/0304-3975(93)90073-3.
4. Cadoli, M.; Lenzerini, M. (abril de 1994). "La complejidad del razonamiento y la circunscripción de mundos cerrados proposicionales". Revista de Ciencias de la Computación y de Sistemas. 48 (2): 255–310. doi:10.1016/S0022-0000(05)80004-2.
5. 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.
6. 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 .
7. Cadoli, M. (noviembre de 1992). "La complejidad de la comprobación de modelos para fórmulas circunscriptivas". Information Processing Letters. 44 (3): 113–8. doi:10.1016/0020-0190(92)90049-2.
8. Lifschitz, V. (1986). "Circunscripción puntual". Actas de la AAAI-86 Quinta Conferencia Nacional sobre Inteligencia Artificial, 11-15 de agosto de 1986, Filadelfia, PA. págs. 406–410. ISBN 0934613133 . 
9. Eiter, T.; Gottlob, G.; Gurevich, Y. (1993). "CURB your theory!". En Bajcsy, Ruzena. IJCAI-93: actas de la Decimotercera Conferencia Conjunta Internacional sobre Inteligencia Artificial, Chambéry, Francia, 28 de agosto–3 de septiembre de 1993. IJCAII. págs. 634–9. ISBN 155860300X . 

Enlaces externos

• Circunscripción: una forma de razonamiento no monótono, un artículo de McCarthy.
• Una explicación en la enciclopedia de Stanford sobre filosofía