Ограничение (логика)

Немонотонная логика, созданная Джоном Маккарти

Ограничение — это немонотонная логика, созданная Джоном Маккарти для формализации предположения здравого смысла о том, что все так, как и ожидалось, если не указано иное. ^{[1] [2]} Ограничение было позже использовано Маккарти в попытке решить проблему фрейма . Чтобы реализовать ограничение в его первоначальной формулировке, Маккарти расширил логику первого порядка , чтобы разрешить минимизацию расширения некоторых предикатов, где расширение предиката — это набор кортежей значений, для которых предикат истинен. Эта минимизация похожа на предположение замкнутого мира о том, что то, что неизвестно как истинно, ложно. ^[3]

Первоначальная задача, рассмотренная Маккарти, была о миссионерах и каннибалах : на одном берегу реки находятся три миссионера и три каннибала; им нужно пересечь реку, используя лодку, которая может вместить только двоих, с дополнительным ограничением, что каннибалы никогда не должны превосходить численностью миссионеров на любом берегу (иначе миссионеры будут убиты и, предположительно, съедены). Задача, рассмотренная Маккарти, заключалась не в поиске последовательности шагов для достижения цели (статья о задаче о миссионерах и каннибалах содержит одно такое решение), а скорее в исключении условий, которые явно не указаны. Например, решение «пройти полмили на юг и перейти реку по мосту» интуитивно недопустимо, поскольку в постановке задачи такой мост не упоминается. С другой стороны, существование этого моста также не исключается постановкой задачи. То, что моста не существует, является следствием неявного предположения, что постановка задачи содержит все, что имеет отношение к ее решению. Прямое указание на то, что моста не существует, не является решением этой проблемы, поскольку существует множество других исключительных условий, которые следует исключить (например, наличие веревки для крепления каннибалов, наличие поблизости более крупной лодки и т. д.).

Позднее Маккарти использовал ограничение для формализации неявного предположения об инерции : вещи не меняются, если не указано иное. Ограничение, по-видимому, было полезным, чтобы избежать указания того, что условия не изменяются всеми действиями, за исключением тех, которые явно известны тем, что изменяют их; это известно как проблема фрейма . Однако позже было показано, что решение, предложенное Маккарти, в некоторых случаях приводит к неверным результатам, как в сценарии задачи о стрельбе в Йеле . Существуют и другие решения задачи о фрейме, которые правильно формализуют задачу о стрельбе в Йеле; некоторые используют ограничение, но по-другому.

Пропозициональный падеж

Хотя ограничение изначально было определено в случае логики первого порядка, конкретизацию в пропозициональном случае определить проще. ^[4] Для пропозициональной формулы ее ограничение — это формула, имеющая только модели , которые не присваивают переменной значение true, если в этом нет необходимости. ${\displaystyle T}$ ${\displaystyle T}$

Формально пропозициональные модели могут быть представлены наборами пропозициональных переменных ; а именно, каждая модель представлена ​​набором пропозициональных переменных, которые она присваивает true. Например, модель, присваивающая true , false , и true , представлена ​​набором , поскольку и являются именно теми переменными, которые присваиваются true этой моделью. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \{a,c\}}$ ${\displaystyle a}$ ${\displaystyle c}$

При наличии двух моделей и представленных таким образом, условие эквивалентно установке в true каждой переменной, которая устанавливается в true. Другими словами, моделирует отношение "установки в true за вычетом переменных". означает, что но эти две модели не совпадают. ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle N\subseteq M}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle \subseteq }$ ${\displaystyle N\subset M}$ ${\displaystyle N\subseteq M}$

Это позволяет нам определять модели , которые не присваивают переменным значение true, если только это не необходимо. Модель теории называется минимальной , если и только если не существует модели , для которой . ${\displaystyle M}$ ${\displaystyle T}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle N\subset M}$

Ограничение выражается выбором только минимальных моделей. Оно определяется следующим образом:

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

В качестве альтернативы можно определить как формулу, имеющую в точности указанный выше набор моделей; более того, можно также избежать дачи определения и определить только минимальный вывод, как если и только если каждая минимальная модель также является моделью . ${\displaystyle CIRC(T)}$ ${\displaystyle CIRC}$ ${\displaystyle T\models _{M}Q}$ ${\displaystyle T}$ ${\displaystyle Q}$

Например, формула имеет три модели: ${\displaystyle T=a\land (b\lor c)}$

1. ${\displaystyle a}$, , истинны, т.е. ; ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \{a,b,c\}}$
2. ${\displaystyle a}$и истинны, ложны, т.е. ; ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \{a,b\}}$
3. ${\displaystyle a}$и истинны, ложны, т.е. . ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle \{a,c\}}$

Первая модель не минимальна в наборе переменных, которые она присваивает true. Действительно, вторая модель делает те же назначения, за исключением , которое присваивается false, а не true. Следовательно, первая модель не минимальна. Вторая и третья модели несравнимы: в то время как вторая присваивает true , третья присваивает true вместо этого. Следовательно, ограничивающими моделями являются вторая и третья модели списка. Пропозициональная формула, имеющая ровно эти две модели, имеет следующий вид: ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle T}$

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

Интуитивно, в circumscription переменная присваивается значение true только в случае необходимости. Двойственно, если переменная может быть false, она должна быть false. Например, по крайней мере, один из и должен быть присвоен true согласно ; в circumscription ровно одна из двух переменных должна быть true. Переменная не может быть false ни в одной модели и ни в одной из circumscription. ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle T}$

Фиксированные и изменяющиеся предикаты

Расширение ограничения с фиксированными и переменными предикатами принадлежит Владимиру Лифшицу . ^[5] Идея заключается в том, что некоторые условия не должны быть минимизированы. В терминах пропозициональной логики некоторые переменные не должны быть фальсифицированы, если это возможно. В частности, можно рассмотреть два вида переменных:

варьирующийся

это переменные, которые вообще не следует принимать во внимание в ходе минимизации;

зафиксированный

это переменные, которые считаются фиксированными при выполнении минимизации; другими словами, минимизация может быть выполнена только путем сравнения моделей с одинаковыми значениями этих переменных.

Разница в том, что значение изменяющихся условий просто предполагается не имеющим значения. Фиксированные условия вместо этого характеризуют возможную ситуацию, так что сравнение двух ситуаций, где эти условия имеют разное значение, не имеет смысла.

Формально расширение ограничения, включающее переменные и фиксированные переменные, выглядит следующим образом, где — набор переменных, которые необходимо минимизировать, фиксированные переменные, а переменные — это те, которые не входят в : ${\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\}}$

На словах минимизация переменных, которым присвоено значение true, выполняется только для переменных в ; более того, модели сравниваются только в том случае, если они присваивают одинаковые значения переменным из . Все остальные переменные при сравнении моделей не учитываются. ${\displaystyle P}$ ${\displaystyle Z}$

Решение проблемы фрейма, предложенное Маккарти, основано на ограничении без фиксированных условий. В пропозициональном случае это решение можно описать следующим образом: в дополнение к формулам, непосредственно кодирующим то, что известно, определяются также новые переменные, представляющие изменения значений условий; затем эти новые переменные минимизируются.

Например, в области, в которой есть дверь, закрытая в момент времени 0, и в которой действие по открытию двери выполняется в момент времени 2, то, что явно известно, представлено двумя формулами:

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

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

Проблема рамы показана в этом примере как проблема, которая не является следствием приведенных выше формул, в то время как дверь должна оставаться закрытой до тех пор, пока не будет выполнено действие по ее открытию. Для этой цели можно использовать ограничение, определив новые переменные для моделирования изменений и затем минимизировав их: ${\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})}$

...

Как показывает задача Йельского университета о стрельбе , такого рода решение не работает. Например, еще не следует из ограничения приведенных выше формул: модель, в которой является истинным, а является ложным, несравнима с моделью с противоположными значениями. Следовательно, ситуация, в которой дверь открывается в момент времени 1 и затем остается открытой в результате действия, не исключается ограничением. ${\displaystyle \neg {\text{open}}_{1}}$ ${\displaystyle {\text{change open}}_{0}}$ ${\displaystyle {\text{change open}}_{1}}$

Было разработано несколько других формализаций динамических областей, не страдающих от таких проблем (см. обзор проблемы фрейма ). Многие используют ограничение, но по-разному.

Предикатное ограничение

Первоначальное определение ограничения, предложенное Маккарти, относится к логике первого порядка. Роль переменных в пропозициональной логике (что-то, что может быть истинным или ложным) в логике первого порядка играют предикаты. А именно, пропозициональная формула может быть выражена в логике первого порядка путем замены каждой пропозициональной переменной предикатом нулевой арности (т. е. предикатом без аргументов). Таким образом, минимизация выполняется на предикатах в версии ограничения логики первого порядка: ограничение формулы получается, заставляя предикаты быть ложными, когда это возможно. ^[6]

Если задана логическая формула первого порядка , содержащая предикат , то ограничение этого предиката равносильно выбору только тех моделей, в которых присваивается значение true на минимальном наборе кортежей значений. ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle T}$ ${\displaystyle P}$

Формально расширение предиката в модели первого порядка — это набор кортежей значений, которые этот предикат присваивает true в модели. Модели первого порядка действительно включают оценку каждого символа предиката; такая оценка сообщает, является ли предикат истинным или ложным для любого возможного значения его аргументов. ^[7] Поскольку каждый аргумент предиката должен быть термином, а каждый термин оценивается в значение, модели сообщают, является ли истинным для любого возможного кортежа значений . Расширение в модели — это набор кортежей терминов, таких, что является истинным в модели. ${\displaystyle P(v_{1},\ldots ,v_{n})}$ ${\displaystyle \langle v_{1},\ldots ,v_{n}\rangle }$ ${\displaystyle P}$ ${\displaystyle P(v_{1},\ldots ,v_{n})}$

Ограничивание предиката в формуле получается путем выбора только моделей с минимальным расширением . Например, если формула имеет только две модели, отличающиеся только тем, что is true в одной и false во второй, то выбирается только вторая модель. Это происходит потому, что is в расширении в первой модели, но не во второй. ${\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}$

Первоначальное определение Маккарти было синтаксическим, а не семантическим. При наличии формулы и предиката , ограничение в является следующей формулой второго порядка: ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle T}$

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

В этой формуле есть предикат той же арности, что и . Это формула второго порядка, поскольку она содержит квантификацию по предикату. Подформула является сокращением для: ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle p<P}$

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

В этой формуле — это n-кортеж терминов, где n — арность . Эта формула утверждает, что необходимо выполнить минимизацию расширения: для того, чтобы оценка истинности рассматриваемой модели была выполнена, должно быть так, что никакой другой предикат не может присвоить значение false каждому кортежу, который присваивает значение false, и при этом отличаться от . ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle P}$

Это определение позволяет ограничить только один предикат. В то время как расширение на более чем один предикат является тривиальным, минимизация расширения одного предиката имеет важное применение: улавливание идеи, что вещи обычно такие, как ожидается. Эту идею можно формализовать, минимизировав один предикат, выражающий ненормальность ситуаций. В частности, каждый известный факт выражается в логике с добавлением литерала, утверждающего, что факт имеет место только в нормальных ситуациях. Минимизация расширения этого предиката позволяет рассуждать при неявном предположении, что вещи такие, как ожидается (то есть они не ненормальны), и что это предположение делается только если это возможно (ненормальность может считаться ложной, только если это согласуется с фактами). ${\displaystyle \neg Abnormal(...)}$

Точечная окружность

Поточечное ограничение — это вариант ограничения первого порядка, который был введен Владимиром Лифшицем . ^[8] Обоснование поточечного ограничения заключается в том, что оно минимизирует значение предиката для каждого кортежа значений по отдельности, а не минимизирует расширение предиката. Например, существуют две модели с доменом , одна с установкой , а другая с установкой . Поскольку расширение в первой модели равно , а расширение во второй — , ограничение выбирает только первую модель. В пропозициональном случае поточечное и предикатное ограничение совпадают. ${\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\}}$

В поточечном ограничении каждый кортеж значений рассматривается отдельно. Например, в формуле можно было бы рассматривать значение отдельно от . Модель минимальна только в том случае, если невозможно превратить любое такое значение из true в false, при этом удовлетворяя формуле. В результате модель, в которой выбирается поточечным ограничением, поскольку превращение только в false не удовлетворяет формуле, и то же самое происходит для . ${\displaystyle P(a)\equiv P(b)}$ ${\displaystyle P(a)}$ ${\displaystyle P(b)}$ ${\displaystyle P(a)=P(b)=true}$ ${\displaystyle P(a)}$ ${\displaystyle P(b)}$

Область и формула ограничения

Более ранняя формулировка ограничения Маккарти основана на минимизации области моделей первого порядка, а не на расширении предикатов. А именно, модель считается меньшей, чем другая, если она имеет меньшую область и две модели совпадают при оценке общих кортежей значений. Эту версию ограничения можно свести к ограничению предиката.

Формульное ограничение было более поздним формализмом, введенным Маккарти. Это обобщение ограничения, в котором минимизируется расширение формулы, а не расширение предиката. Другими словами, формула может быть определена так, что набор кортежей значений домена, удовлетворяющих формуле, будет сделан как можно меньше.

Теория сдерживания

Ограничивание не всегда правильно обрабатывает дизъюнктивную информацию. Рэй Рейтер привел следующий пример: монета брошена на доску, и в результате она оказывается либо на черной, либо на белой области, либо на обеих. Однако существует большое количество других возможных мест, где монета не должна находиться; например, подразумевается, что монета не находится на полу, на холодильнике или на поверхности Луны. Поэтому ограничение можно использовать для минимизации расширения предиката , так что это ложно, даже если это явно не указано. ${\displaystyle On}$ ${\displaystyle On({\text{coin}},{\text{moon}})}$

С другой стороны, минимизация предиката приводит к неверному результату, что монета находится либо на черной области, либо на белой области, но не на обеих . Это происходит потому, что модели, в которых верно только на и только на имеют минимальное расширение , в то время как модель, в которой расширение состоит из обеих пар, не является минимальной. ${\displaystyle On}$ ${\displaystyle On}$ ${\displaystyle ({\text{coin}},{\text{white area}})}$ ${\displaystyle ({\text{coin}},{\text{black area}})}$ ${\displaystyle On}$ ${\displaystyle On}$

Теория ограничения — это решение, предложенное Томасом Эйтером, Георгом Готтлобом и Юрием Гуревичем . ^[9] Идея заключается в том, что модель, которую ограничение не может выбрать, та, в которой оба и истинны, является моделью формулы, которая больше (по отношению к расширению ), чем обе выбранные модели. Более конкретно, среди моделей формулы исключенная модель является наименьшей верхней границей двух выбранных моделей. Теория ограничения выбирает такие наименьшие верхние границы моделей в дополнение к тем, которые выбраны ограничением. Это включение выполняется до тех пор, пока набор моделей не будет замкнут, в том смысле, что он включает все наименьшие верхние границы всех наборов моделей, которые он содержит. ${\displaystyle On({\text{coin}},{\text{white area}})}$ ${\displaystyle On({\text{coin}},{\text{black area}})}$ ${\displaystyle On}$

Смотрите также

• Опровержимое рассуждение  – рассуждение, которое рационально убедительно, но не дедуктивно обосновано.
• Преференциальное вытекание

Ссылки

1. Маккарти, Дж. (февраль 1986 г.). «Применение ограничения к формализации знаний здравого смысла». Искусственный интеллект. 28 (1): 89–116. doi:10.1016/0004-3702(86)90032-9.
2. Маккарти, Дж. (апрель 1980 г.). «Ограничение — форма немонотонных рассуждений». Искусственный интеллект. 13: 27–39. doi:10.1016/0004-3702(80)90011-9.
3. Эйтер, Т.; Готтлоб, Г. (июнь 1993 г.). «Пропозициональное ограничение и расширенное рассуждение о замкнутом мире являются \Pi^p_2-полными». Теоретическая информатика. 114 (2): 231–245. doi:10.1016/0304-3975(93)90073-3.
4. Кадоли, М.; Лензерини, М. (апрель 1994 г.). «Сложность пропозиционального рассуждения о замкнутом мире и его ограничение». Журнал компьютерных и системных наук. 48 (2): 255–310. doi:10.1016/S0022-0000(05)80004-2.
5. Лифшиц, В. (ноябрь 1985 г.). «Базы данных замкнутого мира и ограничение». Искусственный интеллект. 27: 229–235. doi:10.1016/0004-3702(85)90055-4.
6. Лифшиц, В. (1994). «Ограничение». В Габбее, Д.М.; Хоггере, К.Дж.; Робинсоне, Дж.А. Немонотонные рассуждения и неопределенные рассуждения. Справочники по логике в информатике и искусственном интеллекте и логическом программировании. 3. Oxford University Press. С. 297–352. ISBN  0198537476 .
7. Кадоли, М. (ноябрь 1992 г.). «Сложность проверки моделей для описательных формул». Information Processing Letters. 44 (3): 113–8. doi:10.1016/0020-0190(92)90049-2.
8. Лифшиц, В. (1986). «Точечная окружность». Труды AAAI-86 Пятой национальной конференции по искусственному интеллекту, 11–15 августа 1986 г., Филадельфия, Пенсильвания. С. 406–410. ISBN 0934613133 . 
9. Эйтер, Т.; Готтлоб, Г.; Гуревич, Ю. (1993). «ОБУЗДАЙТЕ свою теорию!». В Байчи, Ружена. IJCAI-93: труды Тринадцатой международной совместной конференции по искусственному интеллекту, Шамбери, Франция, 28 августа – 3 сентября 1993 г. IJCAII. стр. 634–9. ISBN 155860300X . 

Внешние ссылки

• Ограничение — форма немонотонного рассуждения, статья Маккарти.
• Объяснение в Стэнфордской энциклопедии по философии