Обход (логика) - Circumscription (logic)

Обход - это немонотонная логика, созданная Джоном Маккарти для формализации предположения здравого смысла о том, что все происходит так, как ожидалось, если не указано иное. Позже Маккарти использовал обходной путь в попытке решить проблему фрейма . Чтобы реализовать ограничение в своей первоначальной формулировке, Маккарти дополнил логику первого порядка, чтобы позволить минимизировать расширение некоторых предикатов, где расширение предиката - это набор кортежей значений, для которых предикат истинен. Эта минимизация похожа на предположение замкнутого мира о том, что то, что неизвестно как истинное, ложно.

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

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

Пропозициональный случай

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

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

Учитывая две модели и представленные таким образом, условие эквивалентно установке значения true для каждой переменной, для которой установлено значение true. Другими словами, моделирует отношение «установки к истинному меньшему количеству переменных». значит, но эти две модели не совпадают. ${\ displaystyle M}$ ${\ displaystyle N}$ ${\ Displaystyle N \ substeq M}$ ${\ displaystyle M}$ ${\ displaystyle N}$ ${\ displaystyle \ substeq}$ ${\ Displaystyle N \ подмножество M}$ ${\ Displaystyle N \ substeq M}$

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

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

{\ displaystyle CIRC (T) = \ {M ~ | ~ M {\ mbox {- минимальная модель}} T \}}

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

Например, формула имеет три модели: ${\ Displaystyle Т = а \ земля (Ь \ лор с)}$

${\ displaystyle a}$ , , Истинны, то есть ; ${\ displaystyle b}$ ${\ displaystyle c}$ ${\ Displaystyle \ {а, б, в \}}$
${\ displaystyle a}$ и истинны, является ложным, то есть ; ${\ displaystyle b}$ ${\ displaystyle c}$ ${\ Displaystyle \ {а, Ь \}}$
${\ displaystyle a}$ и истинно, ложно, то есть . ${\ displaystyle c}$ ${\ displaystyle b}$ ${\ Displaystyle \ {а, с \}}$

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

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

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

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

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

различный: это переменные, которые вообще не нужно учитывать при минимизации;

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

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

Формально расширение ограничения, которое включает изменяющиеся и фиксированные переменные, выглядит следующим образом, где - набор переменных, которые необходимо минимизировать, фиксированные переменные, а переменные переменные не входят в : ${\ displaystyle P}$ ${\ displaystyle Z}$ ${\ Displaystyle P \ чашка Z}$

{\ displaystyle {\ text {CIRC}} (T; P, Z) = \ {M ~ | ~ M \ models T {\ text {and}} \ not \ exists N {\ text {такой, что}} N \ модели 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}}$

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

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

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

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

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

Ограниченность предиката в формуле получается путем выбора только моделей с минимальным расширением . Например, если формула имеет только две модели, различающиеся только тем, что одна из них истинна, а вторая ложна, то выбирается только вторая модель. Это потому, что в первой модели есть расширение, а во второй нет. ${\ 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) \ клин \ forall p \ neg (T (p) \ клин p <P)}

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

{\ Displaystyle \ forall x (п (x) \ rightarrow P (x)) \ клин \ 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 Ненормальное (...)}$

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

Точечная описанность - это вариант описанности первого порядка, введенный Владимиром Лифшицем . В пропозициональном случае поточечная описанность и предикатная описанность совпадают. Обоснование поточечного ограничения состоит в том, что оно минимизирует значение предиката для каждого кортежа значений отдельно, а не минимизирует расширение предиката. Например, есть две модели с доменом : одна настройка и другая настройка . Поскольку расширение в первой модели есть, а расширение для второй есть , ограничение выбирает только первую модель. ${\ Displaystyle Р (а) \ эквив Р (б)}$ ${\ Displaystyle \ {а, Ь \}}$ ${\ Displaystyle P (a) = P (b) = false}$ ${\ Displaystyle P (a) = P (b) = верно}$ ${\ displaystyle P}$ ${\ displaystyle \ emptyset}$ ${\ Displaystyle \ {а, Ь \}}$

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

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

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

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

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

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

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

Теория сдерживания - решение, предложенное Томасом Эйтером , Георгом Готтлобом и Юрием Гуревичем . Идея состоит в том, что модель, которую не удалось выбрать в описании, та, в которой оба и истинны, является моделью формулы, которая больше (по сравнению с расширением ), чем обе две выбранные модели. В частности, среди моделей формулы исключенная модель является наименьшей верхней границей из двух выбранных моделей. Теория ограничения выбирает такие модели с наименьшими верхними границами в дополнение к моделям, выбранным по описанию. Это включение выполняется до тех пор, пока набор моделей не будет замкнут, в том смысле, что он включает в себя все наименьшие верхние границы всех наборов моделей, которые он содержит. ${\ displaystyle On ({\ text {coin}}, {\ text {белая область}})}$ ${\ displaystyle On ({\ text {coin}}, {\ text {черная область}})}$ ${\ displaystyle On}$

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

Ссылки

внешняя ссылка

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

Languages

In other projects