выполнимые и общезначимые формулы

выполнимые и общезначимые формулы Проблемы разрешения для общезначимости и выполнимости формул Постановка проблемы и ее неразрешимость в общем виде В алгебре высказываний было установлено, что существует четкий алгоритм, позволяющий  для каждой формулы алгебры высказываний ответить на вопрос, будет ли данная формула  выполнима, тождественно истинна или тождественно ложна. Для этого нужно составить  таблицу истинности формулы и посмотреть на распределение нулей и единиц в ее последнем столбце. Аналогичная проблема возникает и для формул логики предикатов: существует ли  единый алгоритм, позволяющий для каждой формулы логики предикатов определить, будет  ли она выполнимой или общезначимой? Ответ отрицательный: общего такого алгоритма не  существует. Это было доказано в 1936 г. американским математиком А. Чёрчем. Тем не  менее для некоторых частных видов формул данная проблема допускает решение. В  настоящем параграфе покажем, как решается проблема разрешения для некоторых типов  формул. Решение проблемы для формул на конечных множествах Если формула логики предикатов рассматривается на конечном множестве, то вместо ее  предикатных переменных могут подставляться конкретные предикаты, определенные на  этом конечном множестве. Ввиду того что операции квантификации на конечном множестве сводятся к конъюнкции и дизъюнкции, задача о выполнимости и общезначимости формулы  логики предикатов на конечном множестве сводится к задаче о выполнимости или  общезначимости некоторой формулы алгебры высказываний. Последняя задача, как мы  знаем, эффективно разрешима. Продемонстрируем идею действия этого алгоритма на конкретном примере. Рассмотрим  формулу логики предикатов  выполнима или общезначима на двухэлементном множестве  на этом множестве высказывание  высказывание  формуле , а  , то данная формула равносильна   эквивалентно конъюнкции   и выясним, будет ли она  . Напомним, что поскольку  — дизъюнкции  которая, в свою очередь, равносильна формулеисходной формулы как бы распалась на   последней формулы, Одна двухместная предикатная переменная  четыре пропозициональных переменных    потому что при подстановке в исходную формулу вместо  определенного на множестве  высказывания (вообще говоря, различные). Так что последняя формула есть по сути дела  формула алгебры высказываний. Чтобы это увидеть совсем отчетливо, обозначим указанные четыре пропозициональные переменные буквами  полученная формула примет вид:  двухместного предиката,  , указанные четыре переменные превратятся в конкретные  соответственно. Тогда   и   и   — ложные.   подставить истинные высказывания, а вместо  Составив таблицу истинности данной формулы алгебры высказываний (или каким­либо  другим способом, как это делалось в алгебре высказываний), легко установить, что формула не является тавтологией, но выполнима: она превратится в истинное высказывание, если  вместо  Применительно к исходной формуле логики предикатов это означает, что она не  общезначима на двухэлементном множестве, но выполнима в нем: она превратится в  выполнимый предикат, если вместо предикатной переменной  такой конкретный двухместный предикат, который при одинаковых значениях его  предметных переменных  ложные.  и   превращается в истинные высказывания, а при разных — в   подставить в формулу  Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на  каком конечном Наличие такой формулы позволит сделать, в частности, следующий вывод относительно  проблемы разрешения для выполнимости формул логики предикатов: по выполнимости  формулы на некотором множестве нельзя судить о выполнимости этой формулы на его  подмножествах. Вот пример такой формулы:Можно сказать, что она характеризует нерефлексивность (второй член конъюнкции) и  транзитивность (третий член конъюнкции) некоего двухместного предиката  замкнутая формула превращается в истинное высказывание, если в нее вместо предикатной  переменной  на  , где  — множество всех натуральных чисел, т.е.  подставить, например, двухместный предикат " ", определенный  . Эта  Покажем, что эта формула не выполнима ни на каком конечном множестве. Допустим  противное, т.е. предположим, что существует конкретный предикат  на конечном множестве  , такой, что высказывание , определенный  (1) истинно. Тогда истинным высказыванием будет и каждый член конъюнкции (1). В частности, истинно высказывание  последнего высказывания следует вывод: существует такой элемент  высказывание   истинно. Далее, аналогично существует такой  , и т.д. Поскольку множество  высказывание  элементы  попарно различны. Пусть  высказываний , что  , что истинно  . Тогда из истинности  . Тогда из истинности   конечно, то не все  . Возьмем элемент  в силу истинности высказывания (третий член истинной конъюнкции (1)) заключаем, что истинно высказывание  противоречит истинности высказывания (второй член истинной конъюнкции  (1))  предикат, определенный на конечном множестве, не может превратить данную формулу в  истинное высказывание, т.е. данная формула невыполнима ни на каком конечном  множестве. . Полученное противоречие доказывает, что никакой конкретный  , т.е. высказывание  . Но этоПроблема разрешения выполнимости: влияние мощности множества и структуры  формулы Во­первых, нетрудно понять, что если некоторая формула выполнима или тождественно  истинна на некотором множестве, то тоже самое будет иметь место и на любом другом  множестве с тем же самым числом элементов, т.е. на любом другом множестве,  равномощном с исходным (это следует из наличия взаимно­однозначного отображения этих  множеств одного на другое). Поэтому проблема разрешимости выполнимости и  общезначимости формул логики предикатов состоит фактически в том, чтобы ответить на  вопрос, для каких множеств данная формула выполнима (соответственно общезначима), а  для каких — нет. В дополнение к уже установленным результатам укажем еще ряд результатов в этом  направлении. Так, теорема Лёвенгейма утверждает, что если формула выполнима на  каком­нибудь бесконечном множестве, то она выполнима и на счетно­бесконечном  множестве (доказательство можно найти, например, в книге П.С.Новикова). Дальнейшее  сведение проблемы разрешимости со счетно­бесконечных множеств на конечные, для  которых проблемы разрешимости решаются, невозможно. Примером формулы, выполнимой  на бесконечном множестве и не выполнимой ни на каком конечном множестве, может  служить формула (1), рассмотренная в предыдущем пункте. Далее, примеры формул Задачника показывают, что положительное решение проблемы  выполнимости формулы на некотором конечном множестве не влечет ее положительного  решения для этой формулы на множествах с меньшим числом элементов. Так, в Задачнике  подробно анализируется формула относительно которой доказывается, что она будет выполнима на множестве из трех  элементов (выполняющий предикат " элементов. ") и не выполнима на множестве из двух  В задачнике предлагается привести пример формулы, выполнимой на множестве из четырех  элементов и не выполнимой ни на каком множестве из трех элементов. Ясно, что она  строится по образу и подобию предыдущей формулы:Тем не менее проблема выполнимости обладает одним общим свойством. Теорема 23.1. Если некоторая формула логики предикатов выполнима в каком­нибудь  множестве, то она выполнима также и в каждом множестве с большим числом  элементов. ▼  Доказательство В заключение укажем ряд результатов, которые сводят (редуцируют) проблему  разрешимости для произвольных формул логики предикатов к проблеме разрешимости  формул некоторых специальных видов. Будем считать, не нарушая общности, что все  формулы, о которых идет речь, не имеют свободных предметных переменных, т.е. являются  замкнутыми. Во­первых, мы уже отмечали (см. теорему 21.5), что для всякой формулы логики  предикатов существует равносильная ей формула в предваренной нормальной форме. Более того, еще в 1930­е гг. Сколем доказал, что для каждой формулы логики предикатов можно  указать формулу в предваренной нормальной форме, кванторная приставка которой имеет  вид (так называемая нормальная форма Сколема), которая относительно выполнимости  равнозначна первой. Это означает, что при решении проблемы выполнимости, не уменьшая  общности, можно ограничиться рассмотрением лишь формул, имеющих кванторные  приставки указанного вида. Далее, для каждой формулы можно указать равнозначную ей в отношении выполнимости  формулу, в которой имеются только одноместные и двухместные предикатные переменные  (Лё­венгейм, 1915). Можно, далее, ограничиться даже такими формулами, в которых  встречается только один­единственный двухместный предикатный символ и, кроме того,  приставка имеет вид (Кальмар, 1936):При решении проблемы выполнимости можно также ограничиться формулами, приставки  которых имеют форму (Гёдель, 1933) или же форму   (Аккерман, 1936). Имеются и другие предложения редукции рассматриваемой проблемы либо к формулам с  кванторными приставками специфических видов, либо к формулам, содержащим  предикатные переменные от определенного числа переменных. Решение проблемы для формул, содержащих только одноместные предикатные  переменные В этом случае проблема сводится к проблеме разрешения выполнимости и общезначимости  формулы на некотором конечном множестве, которая, как установлено выше, имеет  эффективное решение. Такое сведение осуществляется на основе следующей теоремы и  следствия из нее. Теорема 23.2. Если формула логики предикатов, содержащая только одноместные  предикатные переменные, выполнима, то она выполнима на конечном множестве,  содержащем не более   элементов, где  входящих в рассматриваемую формулу.  — число различных предикатных переменных, ▼  Доказательство Следствие 23.3. Если замкнутая формула  одноместные предикатные переменные  множестве из   элементов, то она общезначима. , в которую входят только  , тождественно истинна на  Доказательство. Допустим, что рассматриваемая формула  общезначима. Тогда ее отрицание  Следовательно, по доказанной теореме, эта формула выполнима на конечном множестве из т элементов, причем  выполнима на множестве из  . Отсюда, на основании теоремы 23.1, заключаем, что она   не   есть выполнимая формула.   элементов. Значит, на таком множестве исходнаяформула  доказано. не тождественно истинна, что противоречит условию. Следствие  Таким образом, задача об общезначимости формулы, содержащей лишь одноместные  предикатные переменные, сводится к задаче о тождественной истинности этой формулы на  конечном множестве. В свою очередь, во втором пункте настоящего параграфа показано,  как последняя задача решается путем сведения ее к задаче о тождественной истинности  некоторой формулы алгебры высказываний, т. е. к задаче, имеющей алгоритмическое  решение. Следовательно, и наша исходная проблема разрешения общезначимости для класса формул логики предикатов, содержащих только одноместные предикаты, разрешима. Проблема разрешения общезначимости и мощность множества, на котором  рассматривается формула Обратимся к проблеме общезначимости. Теорема Лёвенгейма, отмеченная выше,  применительно к проблеме разрешения общезначимости звучит так: если формула  тождественно истинна в счетно­бесконечной области, то она общезначима. Но снова,  как и для проблемы выполнимости формул, переход от (счетно) бесконечных множеств к  конечным или обратно является качественным. Следующий пример показывает, что, в  отличие от проблемы выполнимости, разрешимость проблемы общезначимости на  некотором множестве не влечет ее разрешимости на множестве, объемлющем данное. Пример 23.4. Докажем, что следующая формула тождественно истинна на любом конечном  множестве, но не является таковой на бесконечном множестве: ▼  Решение Ситуация с проблемой разрешимости общезначимости, отмеченная в рассмотренном  примере, имеет место не только при переходе от конечного множества к бесконечному, но и при переходе от одного конечного к другому конечному, содержащему большее количество  элементов.Решение проблемы для ∀­формул и ∃­формул В заключение покажем, как решается проблема разрешения общезначимости еще для двух  классов формул логики предикатов — ∀­формул и ∃­формул: и в этих случаях она  сводится к тождественной истинности формул на конечных множествах. Под ∀­формулой  понимается формула у которой в предваренной нормальной форме кванторная часть содержит только кванторы  общности, а под ∃­формулой понимается формула у которой в предваренной нормальной форме кванторная часть содержит только кванторы  существования, причем Теорема 23.5. ∀­формула  тогда, когда она тождественно истинна на n­элементном множестве.  общезначима тогда и только  Доказательство.В самом деле, пусть данная формула тождественно истинна на некотором n­ элементном множестве. Тогда ясно, что она тождественно истинна на любом n­элементном  множестве (это следует из наличия взаимно­однозначного отображения этих множеств друг  на друга). Тогда на всяком n­элементном множестве будет тождественно истинна и  формула  множестве:  от  с n­элементным множеством, на котором этот предикат тождественно истинен. Значит, он  будет тождественно истинен и на всем данном множестве. Значит, формула    тождественно истинна на любом множестве, а вместе с ней тождественно истинна на любом  множестве, т. е. общезначима, и формула  , зависящий   переменных. Подставляя вместо них конкретные предметы, мы фактически имеем дело . . Рассмотрим теперь интерпретацию на произвольном  . Получим конкретный предикат  Теорема 23.6. ∃­формула  тогда, когда она тождественно истинна на одноэлементном множестве.  общезначима тогда и толькоДоказательство этой теоремы аналогично доказательству предыдущей теоремы. Проведите  его самостоятельно. Итак, рассмотрения настоящего параграфа красноречиво демонстрируют, что в то время  как в алгебре высказываний проблемы разрешимости выполнимости и общезначимости  формул решались сравнительно легко, в логике предикатов они представляют собой весьма  трудные и, в целом, отнюдь не решенные до конца проблемы.