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

Не путать с очертанием .

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

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

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

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

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

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

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

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

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

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

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

В качестве примера формула $T=a\land (b\lor c)$ имеет три модели:

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

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

$a\land \neg (b\leftrightarrow c)$

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

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

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

меняющийся

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

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

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

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

Формально расширение ограничения, включающее изменяющиеся и фиксированные переменные, выглядит следующим образом: $P$ это набор переменных, которые нужно минимизировать, $Z$ фиксированные переменные, а изменяющиеся переменные – это те, которые не входят в $P\cup Z$:

${\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, выполняется только для переменных в $P$; более того, модели сравниваются только в том случае, если они присваивают одинаковые значения переменным $Z$. Все остальные переменные не учитываются при сравнении моделей.

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

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

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

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

Проблема фрейма в этом примере показана как проблема, $\neg open_{1}$ не является следствием приведенных выше формул, а дверь должна оставаться закрытой до тех пор, пока не будет выполнено действие по ее открытию. Ограничение можно использовать для этой цели путем определения новых переменных. $change\_open_{t}$ для моделирования изменений и их последующей минимизации:

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

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

...

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

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

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

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

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

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

Ограничение сказуемого $P$ в формуле $T$ получается путем выбора только моделей $T$ с минимальным расширением $P$. Например, если формула имеет только две модели, отличающиеся только тем, что $P(v_{1},\ldots ,v_{n})$ истинно в одном и ложно во втором, то выбирается только вторая модель. Это потому, что $\langle v_{1},\ldots ,v_{n}\rangle$ находится в расширении $P$ в первой модели, но не во второй.

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

$T(P)\wedge \forall p\neg (T(p)\wedge p<P)$

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

$\forall x(p(x)\rightarrow P(x))\wedge \neg \forall x(P(x)\rightarrow p(x))$

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

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

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

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

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

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

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

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

Теория ограничения

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

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

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

См. также

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

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

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