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

В математической логике формула является выполнимой , если она истинна при некотором присвоении значений ее переменным . Например, формула выполнима, потому что она верна при и , тогда как формула не выполнима для целых чисел. Двойственной концепцией выполнимости является валидность ; Формула действительна , если каждое присвоение значений ее переменным делает формулу истинной. Например, допустимо для целых чисел, но не является таковым. $x+3=y$ $x=3$ $y=6$ $x+1=x$ $x+3=3+x$ $x+3=y$

Формально выполнимость изучается относительно фиксированной логики, определяющей синтаксис разрешенных символов, таких как логика первого порядка , логика второго порядка или логика высказываний . Однако выполнимость является не синтаксическим свойством, а семантическим свойством, поскольку она связана со значением символов, например, со значением в такой формуле, как . Формально мы определяем интерпретацию (или модель ) как присвоение значений переменным и присвоение значения всем другим нелогическим символам, а формула считается выполнимой, если существует некоторая интерпретация, которая делает ее истинной. ^[1] Хотя это допускает нестандартные интерпретации таких символов, как , можно ограничить их значение, предоставив дополнительные аксиомы . Проблема выполнимости по модулю теорий рассматривает выполнимость формулы относительно формальной теории , которая представляет собой (конечный или бесконечный) набор аксиом. $+$ $x+1=x$ $+$

Выполнимость и обоснованность определяются для одной формулы, но могут быть обобщены на произвольную теорию или набор формул: теория выполнима, если хотя бы одна интерпретация делает каждую формулу теории истинной, и действительна, если каждая формула верна в любой интерпретации. . Например, теории арифметики, такие как арифметика Пеано, выполнимы, потому что они верны в натуральных числах. Эта концепция тесно связана с непротиворечивостью теории и фактически эквивалентна непротиворечивости логики первого порядка — результат, известный как теорема Гёделя о полноте . Отрицание выполнимости есть невыполнимость, а отрицание действительности — недействительность. Эти четыре понятия связаны друг с другом точно так же, как квадрат оппозиции Аристотеля .

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

Сведение валидности к выполнимости

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

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

Пропозициональная выполнимость классической логики

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

Выполнимость в логике первого порядка

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

Выполнимость в теории моделей

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

А ⊧ φ [а]

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

А ⊧ φ

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

А ⊧ Т

Конечная выполнимость

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

Конечная выполнимость и выполнимость, вообще говоря, не обязательно должны совпадать. Например, рассмотрим логическую формулу первого порядка , полученную соединением следующих предложений, где и — константы : $a_{0}$ $a_{1}$

$R(a_{0},a_{1})$
${\ displaystyle \ forall xy (R (x, y) \ rightarrow \ существует zR (y, z))}$
$\forall xyz (R(y,x)\wedge R(z,x)\rightarrow y=z))$
$\forall x\neg R (x,a_{0})$

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

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

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

Числовые ограничения

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

Источник таблицы: Бокмайр и Вайспфеннинг . ^[5]^{: 754}

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

Источник таблицы: Бокмайр и Вайспфеннинг . ^[5]^{: 755}

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

Примечания

^ Булос, Берджесс и Джеффри 2007, с. 120: «Набор предложений [...] выполним, если некоторая интерпретация [делает его истинным]».
^ Франц Баадер ; Тобиас Нипков (1998). Переписывание терминов и все такое. Издательство Кембриджского университета. стр. 58–92. ISBN 0-521-77920-0.
^ Байер, Кристель (2012). «Глава 1.3 Неразрешимость ВОЛС». Конспект лекций — Продвинутая логика . Technische Universität Dresden — Институт технической информатики. стр. 28–32. Архивировано из оригинала (PDF) 14 октября 2020 года . Проверено 21 июля 2012 года .
^ Уилифрид Ходжес (1997). Теория более коротких моделей . Издательство Кембриджского университета. п. 12. ISBN 0-521-58713-1.
^ аб Александр Бокмайр; Фолькер Вайспфеннинг (2001). «Решение числовых ограничений». У Джона Алана Робинсона; Андрей Воронков (ред.). Справочник по автоматизированному рассуждению, том I. Elsevier и MIT Press. ISBN 0-444-82949-0. (Эльзевир) (MIT Press).

дальнейшее чтение

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