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 del mundo cerrado de que lo que no se sabe que sea verdadero es falso. ^[3]

El problema original considerado por McCarthy fue 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 sólo 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 (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 expresamente establecidas. Por ejemplo, la solución "vaya media milla al sur y cruce el río por el puente" intuitivamente no es válida porque el planteamiento del problema no menciona dicho puente. Por otra parte, la existencia de este puente tampoco queda excluida por el planteamiento del problema. Que el puente no exista es consecuencia del supuesto implícito de que el planteamiento del problema contiene todo lo que es relevante para su solución. Afirmar 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 sujetar a los caníbales, la presencia de un barco más grande cerca, etc. )

McCarthy utilizó más tarde 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 parecía ser útil para evitar especificar que las condiciones no cambian con todas las acciones excepto aquellas que explícitamente se sabe 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 en Yale . Existen otras soluciones al problema del marco que formalizan correctamente el problema del rodaje de Yale; algunos usan la circunscripción pero de manera diferente.

El caso proposicional

Si bien la circunscripción se definió inicialmente en el caso de lógica de primer orden, la particularización en el 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 equivale a establecer como verdadera cada variable que se establece como verdadera. En otras palabras, modela la relación de "establecer menos variables verdaderas". 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 verdadero a menos que sea necesario. Un modelo de una teoría se llama mínimo si y sólo si no existe un modelo para la cual . ${\displaystyle M}$ ${\displaystyle T}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle N\subset M}$

La circunscripción se expresa seleccionando sólo 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 realiza las mismas asignaciones excepto , que se asigna a falso y no a verdadero. Por 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 . Por tanto, los modelos que lo circunscriben son el segundo y 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 circunscripción una variable se asigna a verdadera sólo si es necesario. Dualmente, si una variable puede ser falsa, debe ser falsa. Por ejemplo, al menos uno de y debe asignarse a verdadero 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 tampoco de la circunscripción. ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle T}$

Predicados fijos y variables

La ampliació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

éstas son variables que no deben tenerse en cuenta en absoluto durante la minimización;

fijado

estas son variables que se consideran fijas al hacer una minimización; en otras palabras, la minimización sólo puede realizarse 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. Las condiciones fijas, en cambio, caracterizan una situación posible, por lo 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 está el conjunto de variables a minimizar, las variables fijas, y las variables variables son las 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 palabras, la minimización de las variables asignadas a verdadero solo se realiza para las variables en ; además, los modelos sólo 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 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 que se sabe, 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 sabe explícitamente está representado por 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 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 objetivo 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 en Yale , este tipo de solución no funciona. Por ejemplo, aún no está comprendido en la circunscripción de las fórmulas anteriores: el modelo en el que es verdadero y 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 circunscripción. ${\displaystyle \neg {\text{open}}_{1}}$ ${\displaystyle {\text{change open}}_{0}}$ ${\displaystyle {\text{change open}}_{1}}$

Se han desarrollado varias otras formalizaciones de dominios dinámicos que no sufren tales problemas (consulte el problema del marco para obtener una descripción general). Muchos usan la circunscripción pero de manera diferente.

Circunscripción de predicados

La definición original de circunscripción propuesta por McCarthy trata sobre 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 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 sobre 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 in que se asignan a 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 como verdadero en el modelo. De hecho, los modelos de primer orden 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 se evalúa como un valor, el modelo indica 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 son verdaderos 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 sólo los modelos de con una extensión mínima de . Por ejemplo, si una fórmula tiene sólo dos modelos, que difieren sólo porque es verdadera en uno y falsa en el segundo, entonces sólo se selecciona el segundo modelo. Esto se debe a que está en la extensión del 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 más sintáctica que semántica. Dadas una fórmula y un predicado , se circunscribe a 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 considere una evaluación de verdad de un modelo, debe darse el caso de que ningún otro predicado pueda asignar a falso cada tupla que se asigna a falso y, sin embargo, ser 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 solo predicado tiene una aplicación importante: captar la idea de que las cosas suelen ser como se espera. Esta idea puede formalizarse minimizando un predicado único 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 indica 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 asumir falsa sólo si esto es consistente con el hechos.) ${\displaystyle \neg Abnormal(...)}$

Circunscripción puntual

La circunscripción puntual es una variante de la circunscripción de primer orden introducida por Vladimir Lifschitz . ^[8] La razón fundamental 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, existen dos modelos de dominio , uno de configuración y otro de configuración . Dado que la extensión de en el primer modelo es mientras que la extensión del segundo es , la circunscripción solo selecciona el primer modelo. En el caso proposicional coinciden la circunscripción puntual y la circunscripción predicativa. ${\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 sólo si no es posible convertir dicho valor de verdadero a falso sin dejar de cumplir la fórmula. Como resultado, el modelo en el que se selecciona por circunscripción puntual porque convertirse solo en falso no satisface la fórmula, y lo mismo ocurre 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 circunscripción de McCarthy se basa en minimizar el 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 circunscripción se puede reducir a 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 de modo que el conjunto de tuplas de valores del dominio que satisfacen la fórmula sea 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 muchos otros lugares posibles donde se supone que no debe estar la moneda; 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 lo tanto, la circunscripción se puede utilizar para minimizar la extensión del predicado, de modo que sea falso incluso si no se indica explícitamente. ${\displaystyle On}$ ${\displaystyle On({\text{coin}},{\text{moon}})}$

Por otro lado, 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 limitación de la teoría 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 y son verdaderos, es un modelo de la fórmula que es mayor (con 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. La limitación teórica 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. ${\displaystyle On({\text{coin}},{\text{white area}})}$ ${\displaystyle On({\text{coin}},{\text{black area}})}$ ${\displaystyle On}$

Ver 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 a la formalización del conocimiento del 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". Informática 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 proposicionales del mundo cerrado". 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 y circunscripción del mundo cerrado". 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. Prensa de la Universidad de Oxford. págs. 297–352. ISBN  0198537476 .
7. Cadoli, M. (noviembre de 1992). "La complejidad de la verificación de modelos para fórmulas circunscritas". Cartas de procesamiento de información. 44 (3): 113–8. doi:10.1016/0020-0190(92)90049-2.
8. Lifschitz, V. (1986). "Circunscripción puntual". Actas AAAI-86 Quinta Conferencia Nacional sobre Inteligencia Artificial, 11 al 15 de agosto de 1986, Filadelfia, PA. págs. 406–410. ISBN 0934613133 . 
9. Eiter, T.; Gottlob, G.; Gurevich, Y. (1993). "¡FRINA tu teoría!". En Bajcsy, Ruzena. IJCAI-93: actas de la Decimotercera Conferencia Internacional Conjunta sobre Inteligencia Artificial, Chambéry, Francia, 28 de agosto al 3 de septiembre de 1993. IJCAII. págs. 634–9. ISBN 155860300X . 

enlaces externos

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