Удовлетворенность

В математической логике, выполнимость и validity являются элементарными понятиями семантики. Формула является выполнимым, если можно найти интерпретацию (модель ), которая делает формулу истинной. Формула действительна, если все интерпретации делают формулу истинной. Противоположности этих понятий неудовлетворительность и недействительность, то есть формула является неудовлетворительной, если ни одна из интерпретаций не делает формулу истинной, и недействительной, если такая интерпретация делает формулу неверной se. Эти четыре концепции связаны друг с другом точно так же, как Аристотель квадрат оппозиции.

. Четыре концепции можно поднять для применения ко всем теориям : теория является выполнимой (действительной), если одна (все) интерпретации делают каждую из аксиом теории истинной, а теория является неудовлетворительной (недействительной), если все (одна) интерпретация делают (и) ложными каждую из аксиом теории.

Также возможно рассматривать только интерпретации, которые делают все аксиомы второй теории верными. Это обобщение обычно называется выполнимостью по модулю теорий.

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

• 1 Снижение достоверности до выполнимости
• 2 Выполнимость предложения
• 3 Выполнимость в логике первого порядка
• 4 Выполнимость в теории моделей
• 5 Конечная выполнимость
• 6 Числовые ограничения
• 7 См. Также
• 8 Примечания
• 9 Ссылки
• 10 Дополнительная литература

Для классической логики, как правило, можно переформулировать вопрос о действительности формулы до формулы, предполагающей выполнимость, из-за отношения между понятиями, выраженными в указанном квадрате оппозиции. В частности, φ действителен тогда и только тогда, когда ¬φ невыполнимо, то есть неверно, что ¬φ выполнимо. Другими словами, φ выполнимо тогда и только тогда, когда ¬φ неверно.

Для логики без отрицания, такой как положительное исчисление высказываний, вопросы валидности и выполнимости могут быть не связаны. В случае позитивного исчисления высказываний проблема выполнимости тривиальна, поскольку каждая формула выполнима, в то время как проблема достоверности co-NP полна.

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

Выполнимость - это неразрешимый, и на самом деле это даже не полуразрешимое свойство формул в логике первого порядка (FOL). Этот факт связан с неразрешимостью проблемы валидности FOL. Вопрос о статусе проблемы действительности был впервые поставлен Дэвидом Гильбертом как так называемая Entscheidungsproblem. Универсальность формулы - это полуразрешимая проблема. Если бы выполнимость была также полуразрешимой проблемой, то проблема существования контрмоделей была бы такой же (у формулы есть контрмодели, если и только если ее отрицание выполнимо). Таким образом, проблема логической достоверности была бы разрешимой, что противоречит теореме Чёрча-Тьюринга, что означает отрицательный ответ на проблему Entscheidungsprost.

В теории моделей атомарная формула является выполнимой, если существует набор элементов структуры , которые делают формулу верной. Если A - структура, φ - формула, а a - набор элементов, взятых из структуры, которые удовлетворяют φ, то обычно пишут, что

A ⊧ φ [a]

Если φ не имеет свободными переменными, то есть, если φ является атомарным предложением и ему удовлетворяет A, то пишут

A ⊧ φ

. В этом случае можно также сказать, что A является модель для φ, или что φ истинно в A. Если T - это совокупность атомарных предложений (теория), удовлетворяющая A, записывается

A ⊧ T

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

Тем не менее, конечная выполнимость и выполнимость не обязательно должны совпадать в целом. Например, рассмотрим формулу логики первого порядка, полученную как конъюнкция следующих предложений, где $a\; \{\backslash \; displaystyle\; a\}$и $b\; \{\backslash \; displaystyle\; b\}$- константы :

• $R\; (a\; 0,\; a\; 0)\; \{\backslash \; displaystyle\; R\; (a\_\; \{0\},\; a\_\; \{0\})\}$
• $R\; (\; a\; 0,\; a\; 1)\; \{\backslash \; displaystyle\; R\; (a\_\; \{0\},\; a\_\; \{1\})\}$
• $\forall \; ху\; (R\; (x,\; y)\; \to \; \exists \; z\; R\; (y,\; z))\; \{\backslash \; displaystyle\; \backslash \; forall\; xy\; (Р\; (Икс,\; Y)\; \backslash \; rightarrow\; \backslash \; существует\; zR\; (Y,\; z))\}$
• $\forall \; xyz\; (R\; (y,\; x)\; \wedge \; R\; (z,\; x)\; \to \; x\; =\; z))\; \{\backslash \; displaystyle\; \backslash \; forall\; xyz\; (R\; (y,\; x)\; \backslash \; wedge\; R\; (z,\; x)\; \backslash \; rightarrow\; x\; =\; z))\}$

Полученная формула имеет бесконечную модель $R\; (a\; 0,\; a\; 0),\; R\; (a\; 0,\; a\; 1),\; R\; (a\; 1,\; a\; 2),\dots \; \{\backslash \; displaystyle\; R\; (a\_\; \{0\},\; a\_\; \{0\}),\; R\; (a\_\; \{0\},\; a\_\; \{1\}),\; R\; (a\_\; \{1\},\; a\_\; \{2\}),\; \backslash \; ldots\}$, но можно показать, что у него нет конечной модели (начиная с факта $R\; (a,\; b)\; \{\backslash \; displaystyle\; R\; (a,\; b)\; \}$и следуя цепочке $R\; \{\backslash \; displaystyle\; R\}$атомов, которые должны существовать в соответствии с третьей аксиомой, конечность модели потребует наличие цикла, который нарушит четвертую аксиому, независимо от того, возвращается ли он в цикл на $a\; 0\; \{\backslash \; displaystyle\; a\_\; \{0\}\}$или на другом элементе).

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

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

Источник таблицы: Bockmayr and Weispfenning.

Для линейных ограничений представлена ​​более полная картина по следующей таблице.

Источник таблицы: Bockmayr and Weispfenning.

• 2-выполнимость
• Задача логической выполнимости
• Выполнимость схемы
• 21 NP-полная проблема Карпа
• Валидность
• Удовлетворение ограничений
• Удовлетворение

1. ^См., например, Boolos and Jeffrey, 1974, глава 11.
2. ^Франц Баадер ; Тобиас Нипков (1998). Изменение терминов и все такое. Кембридж University Press. С. 58–92. ISBN 0-521-77920-0.
3. ^Байер, Кристель (2012). «Глава 1.3 Неразрешимость FOL» (PDF). Конспект лекций - Продвинутая логика. Technische Universität Dresden - Институт технических компьютерных наук. С. 28–32. Проверено 21 июля 2012 года.
4. ^Wilifrid Hodges (1997). Более короткая модельная теория. Издательство Кембриджского университета. п. 12. ISBN 0-521-58713-1.
5. ^ Александр Бокмайр; Фолькер Вайспфеннинг (2001). «Решение числовых ограничений». В Джоне Алане Робинсоне; Андрей Воронков (ред.). Справочник по автоматическому мышлению Том I. Elsevier и MIT Press. ISBN 0-444-82949-0 (Elsevier) ISBN 0-262-18221-1 ( MIT Press).

• Boolos and Jeffrey, 1974. Вычислимость и логика. Cambridge University Press.

• Дэниел Кроенинг ; Офер Стрихман (2008). Процедуры принятия решений: алгоритмическая точка зрения. Springer Science Business Media. ISBN 978-3-540-74104-6.
• А. Biere; М. Хеул; Х. ван Маарен; Т. Уолш, ред. (2009). Справочник по выполнимости. IOS Press. ISBN 978-1-60750-376-7.