Введение

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

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

Предикативная окружность

Оригинальное определение округления, предложенное Маккарти, относится к логике первого порядка. Роль переменных в пропозициональной логике (то, что может быть истинным или ложным) играет в логике первого порядка предикат. А именно, пропозициональную формулу можно выразить в логике первого порядка, заменив каждую пропозициональную переменную предикатом нулевой арности (т.е. предикатом без аргументов). Поэтому минимизация производится над предикатами в версии округления логики первого порядка: округление формулы получается, заставляя предикаты быть ложными, когда это возможно. При заданной формуле логики первого порядка, содержащей предикат, округление этого предиката сводится к выбору только тех моделей, в которых ему присвоено значение «истина» на минимальном наборе кортежей значений. Формально, расширение предиката в модели первого порядка – это множество кортежей значений, которым этот предикат присваивает значение «истина» в этой модели. Модели первого порядка действительно включают оценку каждого символа предиката; такая оценка показывает, является ли предикат истинным или ложным для любого возможного значения его аргументов. Поскольку каждый аргумент предиката должен быть термом, а каждый терм вычисляется в значение, модель показывает, истинно ли для любого возможного кортежа значений. Расширение в модели – это множество кортежей термов, для которых предикат истинен в модели. Округление предиката в формуле получается путем выбора только тех моделей, которые имеют минимальное расширение. Например, если формула имеет только две модели, отличающиеся только тем, что предикат истинен в одной и ложен в другой, то выбирается только вторая модель. Это потому, что предикат находится в расширении в первой модели, но не во второй. Оригинальное определение Маккарти было скорее синтаксическим, чем семантическим. При заданной формуле и предикате, округление в обозначается следующей формулой второго порядка:

В этой формуле – предикат той же арности, что и. Это формула второго порядка, потому что она содержит квантификацию над предикатом. Подформула является сокращением для:

В этой формуле – n-кортеж термов, где n – арность. Эта формула утверждает, что необходимо минимизировать расширение: для того чтобы оценка истинности в модели, которая рассматривается, была верной, должно быть так, что ни один другой предикат не может присвоить значение «ложь» каждому кортежу, который присваивает значение «ложь», и при этом отличаться от. Это определение позволяет округлять только один предикат. Хотя расширение на более чем один предикат тривиально, минимизация расширения одного предиката имеет важное применение: улавливание идеи, что вещи обычно происходят так, как ожидается. Эту идею можно формализовать, минимизируя один предикат, выражающий аномальность ситуаций. В частности, каждый известный факт выражается в логике с добавлением литерала, утверждающего, что факт верен только в нормальных ситуациях. Минимизация расширения этого предиката позволяет рассуждать, исходя из неявного предположения, что вещи происходят так, как ожидается (то есть, они не аномальны), и что это предположение делается только в том случае, если это возможно (аномальность можно считать ложной только в том случае, если это согласуется с фактами).

Ограничение по точке

Точечная окружность — это вариант окружности первого порядка, предложенный Владимиром Лифшицем. Идея точечной окружности заключается в том, что она минимизирует значение предиката для каждой кортежа значений по отдельности, а не минимизирует область определения предиката. Например, существуют две модели с областью определения D, в одной из которых P(a) истинно, а в другой — ложно. Поскольку область определения P в первой модели содержит a, а во второй — пуста, обычная окружность выбирает только первую модель. В пропозициональном случае точечная и предикатная окружности совпадают. При точечной окружности каждая кортежа значений рассматривается независимо. Например, в формуле P(a) ∨ A следует рассматривать значение P(a) отдельно от A. Модель считается минимальной только в том случае, если невозможно изменить какое-либо из этих значений с истинного на ложное, сохраняя при этом истинность формулы. В результате, модель, в которой P(a) истинно, выбирается точечной окружностью, поскольку изменение только P(a) на ложное не удовлетворяет формуле, и то же самое происходит с A.

Ограничение домена и формулы

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