«И. Н. Пономарёв ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ И РОДЫ СТРУКТУР Учебное пособие Москва МФТИ 2007 УДК 510.6+510.22(075) ББК 22.12я73 П56 Р е ц е н з е н т ы: кафедра Криптология и дискретная математика Московского ...»

Таким образом, каждая булева функция может быть представлена полиномом Жегалкина. Но не равных между собой полиномов 18 Гл. 1. Элементы математической логики Жегалкина не больше, чем возможных комбинаций значений коэффициентов. Для случая переменных имеется всего 2 коэффициентов и 22 комбинаций, т. е. ровно столько, сколько булевых функций. Отсюда следует однозначность представления булевой функции полиномом Жегалкина.

Упр. 7. Постройте полиномы Жегалкина для дизъюнкции, импликации и функции из упр. 6. Ответы: ( & ), 11. Итак, мы показали, что, используя, к примеру, одни только операции &,, ¬, можно построить любую булеву функцию. Но из законов де Мргана сразу следует, что, вообще говоря, для этого достаточно набора операций ¬, & или ¬,, из которых можно выразить все остальные.

Наборы {¬, &}, {¬, } и {t, f, &, } — примеры базисов логических операций, т. е. суперпозицией входящих в них операций возможно построение любой булевой функции. Интересно, что базис может состоять и всего из одной двухместной логической операции (для этого достаточно выразить через неё операции ¬, & или ¬, ).

Упр. 8. Докажите, что наборы операций {|}, {}, {¬, } являются базисами.

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

В то же время набор операций &, не является базисом по следующей причине: если все пропозициональные переменные принимают значение f, то любая формула, содержащая только связки &,, тоже примет значение f, а значит, операция ¬ невыразима через &, (говорят, что эти операции «сохраняют нуль»). Вообще, любое доказательство того, что предложенная система операций не является базисом, должно основываться на том, что суперпозиция этих операций не выводит конструируемые булевы функции за пределы некоторого подкласса булевых функций. В более поИсчисление высказываний дробных руководствах (напр., [6]) рассматривается общий критерий (Поста), определяющий, является ли набор операций базисом.

Упр. 9. [2]. Докажите, что набор операций {&,,, } не является базисом, {¬} не является базисом.

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

К примеру, & можно было бы определить как сокращение для ( | ) | ( | ). Однако формулы такого языка было бы довольно трудно воспринимать (в этом можно убедиться при выполнении упр. 8). Поэтому традиционно математическая логика пользуется четырьмя связками: ¬, &,, — которые, как уже отмечалось, соотносятся с союзами естественного языка. В дальнейшем мы также будем применять в формулах в основном только эти связки.

§ 1.2. Исчисление высказываний 1. В предыдущем параграфе мы показали, как при помощи таблиц истинности можно механическим образом решать задачи, касающиеся свойств любой пропозициональной формулы. К примеру, чтобы доказать общезначимость, достаточно вычислить истинностное значение формулы при всех комбинациях аргументов. Однако, когда мы дойдём до формул, содержащих кванторы и, подобных простых методов уже не окажется в нашем распоряжении, поэтому нам необходимо познакомиться с другим, более общим подходом к работе с логическими формулами. Рассмотрим множество пропозициональных формул, построенных только при помощи связок, &,, ¬, пока безотносительно их интерпретации в булевых функциях. Введём десять схем аксиом:

20 Гл. 1. Элементы математической логики 10) ¬¬.

На первый взгляд этот список может показаться длинным и с трудом поддающимся запоминанию. Всё становится проще, если заметить, что схемы аксиом делятся на группы: первые две схемы задают свойства импликации, схемы 3–5 — конъюнкции, 6–8 — дизъюнкции, 9–10 — отрицания. Самая длинная вторая схема задат транзитивность импликации. Схемы 3–5 и 6–8 — симметричны и состоят из правил, одни из которых говорят, что можно получить из конъюнкции (дизъюнкции), а другие — как их можно получить. Девятая схема имеет отношение к способу рассуждения, известному как «сведение к противоречию». Наконец, самая простая десятая схема говорит о том, как избавиться от двух знаков отрицания, стоящих подряд.

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

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

Выводом формулы будем называть такую последовательность формул 1,..., в которой каждая формула либо является аксиомой, либо следует из двух предшествующих формул предъявленной последовательности по modus ponens, и где совпадает Лемма 3. Для любой формулы имеет место.

Продемонстрируем вывод:

1) ( ) — схема 1 ( заменено на ), схема 2 ( заменено на, заменено на ), 5) — modus ponens из шагов 2, 4.

2. На нынешнем уровне развития теории тот факт, что для формулы найден вывод, можно считать случайностью.

Проявив изобретательность, мы, наверное, могли бы найти вывод и для некоторых других формул, но такой неформальный процесс поиска вывода не имел бы ничего общего с механической работой по построению таблиц истинности (к примеру, нам не составило бы труда доказать тот факт, что |= ). Естественно поставить 22 Гл. 1. Элементы математической логики вопрос: как определить доказуемость или недоказуемость формулы в общем случае? Ответ даёт утверждение, которое мы докажем в этой главе: пропозициональная формула доказуема тогда и только тогда, когда она общезначима, т. е. в действительности знаки и |= взаимозаменяемы, а поиск вывода можно заменить построением таблиц истинности. Доказать это в одну сторону мы можем уже сейчас.

Теорема 4. Всякая доказуемая формула общезначима.

Пусть и дан вывод 1,.... Покажем по индукции, что все формулы в выводе общезначимы, а следовательно, общезначимо.

Всякая аксиома общезначима. Действительно: формулы, выражающие схемы аксиом 1–10 — общезначимы, в чём можно убедиться при помощи таблиц истинности. Следовательно, будут общезначимы и все формулы, получаемые из схем аксиом подстановкой других формул вместо букв,,.

Заметим, что 1 обязана быть аксиомой, следовательно, |= 1.

Каждая ( > 1) является либо аксиомой (и тогда |= ), либо получена по modus ponens из предшествующих формул, которые можно считать общезначимыми по предположению индукции.

Если |= ( < ), то, по определению импликации, исключается случай, когда — истинно, а — ложно. Но |= означает, что — истинно на любом наборе пропозициональных переменных. Следовательно, |=.

Следствие. Ни для какой формулы B не может быть одновременно и ¬.

Пусть — доказуема, тогда по теореме 4 столбец значений таблицы истинности для содержит только единицы, а формулы ¬ — только нули. Но если допустить, что ¬ также доказуема, то столбец значений формулы ¬ должен содержать только единицы. Противоречие.

Доказать утверждение, обратное теореме 4, гораздо сложнее, и нам для этого потребуется развить навыки работы с выводом и рассмотреть ряд вспомогательных теорем.

3. В обычных рассуждениях мы часто применяем такой метод: допускаем, что какие-то утверждения истинны, и смотрим, какие логические следствия получаются из этого допущения. Введём такую возможность в исчисление высказываний. Будем говорить, что формула выводима из посылок 1,... и писать 1,..., если мы можем предоставить последовательность формул 1,..., в которой каждая формула либо является одной из посылок 1,..., либо аксиомой, либо непосредственно следует из двух предшествующих формул предъявленной последовательности по modus ponens, и где совпадает с.

Упр. 10. Используя определение, докажите, что если имеет место 1 и 2,, то 1, 2, где, — произвольные формулы, 1, 2 — произвольные последовательности формул.

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

В одну сторону утверждение является, по сути, переформулировкой правила modus ponens. Действительно: пусть, т. е. существует вывод формулы из посылок. Тогда, если добавить к числу посылок, будет выводима из и по modus ponens.

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

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

1) Если есть, то по лемме 3 доказуемо (безо всяких посылок), поэтому мы добавляем перед её вывод.

2) Если принадлежит, то по первой схеме ( ), применяя modus ponens к и последней формуле, получаем 3) То же самое, если является аксиомой.

4) Наконец, пусть получается по modus ponens из и, <. По второй схеме аксиом имеем Построим вывод левой части импликации. По первой схеме Упр. 12. [6]. Докажите, что для любых,, имеет место (указание: используйте теорему 5 и результат упражнения 11).

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

Теорема 6 (правила введения и удаления). Для любых формул,, и списка формул справедливы следующие правила вывода:

(reductio ad absurdum) Действительно:

26 Гл. 1. Элементы математической логики -введение и -удаление доказаны теоремой 5;

&-введение: продемонстрируем сокращённый вывод:

&-удаление есть результат -удаления из схем 3, 4;

-введение есть результат -удаления из схем 6, 7;

доказательство разбором случаев:

1) — -введение к первому соотношению, 2) — -введение ко второму соотношению, ¬-введение:

1) — -введение к первому соотношению, 2) ¬ — -введение ко второму соотношению, ¬¬-удаление есть результат -удаления из схемы 10;

¬-удаление:

Обратим особое внимание на то, что правило ¬-удаления, по сути, гласит: при наличии противоречивых посылок доказуемо всё, что угодно.

5. Правила введения и удаления дают нам новый и очень эффективный способ построения вывода формул: даже если формула выводится безо всяких посылок, мы можем начать с утверждений о выводимости из посылок, а затем «перебросить» все посылки направо от знака выводимости. Примером применения этой методики служит доказательство следующей леммы.

Лемма 7 (закон исключённого третьего). ¬.

Продемонстрируем вывод:

1) ¬( ¬), ¬ — -введение, 3) ¬( ¬) ¬ — ¬-введение к шагам 1, 2, 4) ¬( ¬), ¬ ¬ — -введение, 6) ¬( ¬) ¬¬ — ¬-введение к шагам 4, 5, 7) ¬¬( ¬) — ¬-введение к шагам 3, 6, 8) ¬ — ¬¬-удаление.

28 Гл. 1. Элементы математической логики Упр. 13. Используя правила введения и удаления, докажите (указание: достаточно получить противоречие из посылок ( ), ¬, ).

Упр. 14. Используя правила введения и удаления, докажите законы де Моргана (необходимо доказать четыре соотношения: ¬( ) ¬ & & ¬, ¬( & ) ¬ ¬ и обратные им).

Частичное решение. Докажем ¬( ) ¬ & ¬:

3) ¬( ) ¬ — ¬-введение к шагам 1, 2, 4) ¬( ) ¬ (аналогично шагам 1–3), 5) ¬( ) ¬ & ¬ — &-введение к шагам 3, 4.

1) ¬, & — &-удаление, 3) ¬, ¬( & ) — ¬-введение к шагам 1, 2, 4) ¬ ¬( & ) (аналогично шагам 1–3), 5) ¬ ¬ ¬( & ) — -удаление к шагам 3, 4.

Упр. 15. [6]. Используя правила введения и удаления, докажите (указание: при необходимости воспользуйтесь законами де Моргана).

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

Лемма 8. Для произвольных формул A и B имеют место следующие 14 утверждений о выводимости:

Какие-то из этих утверждений уже доказаны теоремой 6, сокращённые доказательства большинства остальных просты и не превышают трёх-четырёх строк, например:

3), ¬ ¬( ) — reductio ad absurdum из шагов 1, 2.

Изобретательности, пожалуй, требует только доказательство утверждения ¬, ¬ ¬( ):

2) ¬, ¬, — ¬-удаление (противоречивы ¬, ), 3) ¬, ¬, — разбор случаев из шагов 1, 2, 6) ¬, ¬, ¬ — разбор случаев из шагов 4, 5, 7) ¬, ¬ ¬( ) — reductio ad absurdum из шагов 3, 6.

(Но если использовать закон де Моргана, то и в этом случае доказательство будет тривиальным: ¬, ¬ ¬&¬ ¬( ).) Упр. 16. Докажите остальные 12 утверждений леммы 8.

30 Гл. 1. Элементы математической логики Лемма 9. Пусть — произвольная формула, построенная из пропозициональных переменных 1,.... Тогда для каждой строки таблицы истинности формулы имеет место соответствующее утверждение о выводимости: если (1,... ) =, Как и в доказательстве теоремы 1, ¬ обозначает формулу, если = t, и ¬, если = f.

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

Теорема 10 (о полноте исчисления высказываний). Всякая общезначимая формула исчисления высказываний доказуема.

Пусть построена из пропозициональных переменных. Если |=, то в силу леммы 9 из 2 наборов посылок выводится она, а не её отрицание. Покажем, что можно вывести безо всяких посылок.

Сгруппируем соотношения выводимости в 21 пар вида По правилу разбора случаев получим 21 соотношений вида и в силу леммы где фигурируют только 1 посылок. Повторив процесс раз, получим, что и требовалось.

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

Из школьного курса грамматики известно, что обычным образом построенное предложение имеет подлежащее и сказуемое, или, если пользоваться латинскими терминами, субъект и предикат. К примеру, в предложении «Сократ — человек» слово «Сократ» является субъектом, а «человек» — предикатом. Мы будем понимать термины «субъект» и «предикат» несколько шире, чем лингвисты: всё то, о чём говорится в высказывании, мы назовём субъектами, а всё то, что говорится — предикатом.

Таким образом, для нас часть высказывания, выражаемая шаблоном « — человек», будет представлять собой предикат, из которого получится истинное высказывание, если в качестве субъекта (вместо переменной ) подставить «Сократ», и ложное, если субъект — «Хирон» (кентавр). Можно рассмотреть предикат « в нормальных условиях кипит при 100 C», дающий истинное высказывание, если субъект — «вода», и ложное, если субъект — «олово». Таким образом, мы приходим к пониманию предиката как функции, принимающей значения t и f в зависимости от подставляемых в неё аргументов. Мы рассматривали предикаты только одного аргумента (одноместные), вот пример двухместного предиката: « муж », дающий истинное высказывание, если в качестве первого и второго субъектов выступают соответственно «Сократ»

и «Ксантиппа», и ложное, скажем, в случае субъектов «Вронский»

и «Анна Каренина». Пример трёхместного предиката: « + = », дающий t для набора субъектов «2, 2, 4» и f для «1, 1, 1». Наконец, можно рассмотреть и нуль-местные предикаты: предикаты, не требующие субъектов; различных между собой нуль-местных предикатов всего два: t и f.

32 Гл. 1. Элементы математической логики Подведём итог. Пусть дано непустое множество, которое назовём предметной областью. -местным предикатом на множестве называется функция, ставящая в соответствие каждому упорядоченному набору элементов множества одно из значений t или f. Предикаты, таким образом, принимают те же значения, что и булевы функции, но коренное отличие в том, что предикат может быть определён на произвольном множестве.

На данном этапе мы можем воспринимать множества и функции как некие умозрительные объекты: множество — как совокупность объектов, рассматриваемую как единое целое, и функцию — как некоторый закон, согласно которому каждому объектуаргументу (или набору объектов-аргументов) поставлен в соответствие один единственный результат. Разумеется, это нельзя считать определением понятий «множество» и «функция», более формальный разговор о которых пойдёт в гл. 2. Но там потребуется определённый навык вывода в исчислении предикатов, приобрести который на практике, по-видимому, невозможно без начальных рассуждений о предметных областях, моделях и оценках, так или иначе задействующих термин «множество».

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

2. Сигнатурой называется произвольный набор термов 1,... (предметных констант), а также предикатных символов 1,..., обладающих целыми неотрицательными валентностями 1,... 2. Определим, какие цепочки символов Для упрощения изложения намеренно игнорируются «функциональные символы», традиционно входящие в определение сигнатуры, т. к. для построЯзык логики предикатов являются формулами (или соотношениями) сигнатуры, пока что не рассматривая их смысл:

1) Константы сигнатуры 1,... и буквы 1,..., называемые индивидными переменными, являются термами сигнатуры.

Предполагается, что, глядя на выражение, всегда можно различить, где малая латинская буква в нём обозначает константу, а где — переменную.

2) Если — предикатный символ валентности сигнатуры, а 1,... — термы, то цепочка символов называется атомарной формулой сигнатуры. Кроме того, любой предикатный символ нулевой валентности есть атомарная формула сигнатуры. Атомарная формула сигнатуры есть формула сигнатуры.

3) Если — формула сигнатуры, то ¬ — формула сигнатуры.

4) Если и — формулы, а — какая-либо из логических связок, &,, то ( ) — формула сигнатуры.

5) Если — формулы сигнатуры, — индивидная переменная, а Q — какой-либо из кванторов,, то Q — формула сигнатуры.

6) Других формул не существует.

К примеру, если содержит предикатные символы, и валентностей 2, 1 и 2 соответственно, то цепочка символов ения аксиоматической теории множеств и аппарата родов структур без функциональных символов можно обойтись.

34 Гл. 1. Элементы математической логики является корректной формулой.

Упр. 17. Найдите все подформулы указанной формулы.

Легко видеть (ср. определение пропозициональной формулы на с. 12), что из любой пропозициональной формулы можно построить формулу сигнатуры, если вместо пропозициональных переменных подставить формулы сигнатуры. Применяя соглашения о приоритете логических операций, введённые на с. 12, в формулах сигнатур мы также будем опускать избыточные скобки, когда это не ведёт к разночтениям. Примем, кроме того, соглашение, по которому при отсутствии группирующих скобок квантор действует только на первую следующую за ним подформулу, т. е. выражение () & () интерпретируется как ( ()) & ().

Упр. 18. [2]. Покажите, что выражение 1... ( (1 ) &... & & ( )), где — одноместный предикат, не является формулой. Указание: является ли индивидной переменной?

3. Теперь мы можем определить, что такое модель M сигнатуры, оценка в модели M и истинностное значение формулы сигнатуры на оценке.

Моделью M сигнатуры называются: непустое множество (предметная область), набор элементов этого множества, соответствующих предметным константам 1,..., и такой набор определённых на данном множестве предикатов, что каждому предикатному символу валентности из соответствует один и только один -местный предикат из M. Ясно, что сигнатура может иметь много моделей. Например, если в сигнатуре содержится один предикатный символ валентности 3, то её моделями могут быть, например, такие: — множество натуральных чисел, предикат для символа есть « + = »; — множество точек плоскости, предикат для символа есть «точки, и лежат на одной прямой».

Оценкой в модели M называется набор элементов множества, поставленный в соответствие индивидным переменным таким образом, что каждой индивидной переменной соответствуЯзык логики предикатов ет один и только один элемент множества. Другими словами, задавая оценку, мы указываем, каким именно элементам соответствуют переменные, участвующие в рассматриваемых нами формулах. Для того чтобы сослаться на элемент, обозначаемый буквой на оценке, будем пользоваться, как в книге [6], обозначением []. (Естественно, константы будут обозначать один и тот же элемент на любой оценке — их значения задаются уже моделью.) Наконец, истинностное значение формулы сигнатуры на оценке, равное t или f и обозначаемое [], определяется следующим образом:

1) Истинностное значение атомарной формулы (1,... ) есть результат подстановки в предикат, соответствующий символу, элементов [1 ], ... [ ], т. е. [ (1,... )] = 2) [¬] = ¬([]).

3) [ ] = [] [] (пп. 2 и 3, по-видимому, в комментариях не нуждаются).

4) Формула (которая читается «существует такой, что ») является истинной тогда и только тогда, когда существует хотя бы одна оценка, отличающаяся от только значением переменной, такая, что [] = t.

Когда предметная область состоит из конечного числа элементов 1,..., формула сводится к обычной дизъюнкции по всем элементам : [] = []( + 1 ) Здесь + обозначает, как в книге [6], оценку, отличающуюся от только значением переменной, такую, что []( + ) =. Для случая, когда состоит из произвольного (возможно, бесконечного) количества элементов, 36 Гл. 1. Элементы математической логики нам потребуется «всеобщая дизъюнкция»:

5) Аналогично, истинность формулы («для всех имеет место ) определяется как Когда даны модель и оценка, истинностное значение имеет каждая формула сигнатуры. Здесь ситуация несколько сложнее, чем в алгебре высказываний, где достаточно было задать истинностные значения пропозициональных переменных.

4. Заметим, что по определению истинности истинностные значения формул, не зависят от индивидной переменной, «пробегающей значения» по предметной области. Легко указать аналогию с другими математическими формулами: к примеру, обозначают соответственно вектор, индексируемый переменной, и функцию, зависящую от, не зависимые и соответственно.

В приведённых примерах переменные и являются связанными, а и — свободными. Одна и та же буква может входить в формулу и в качестве свободной, и в качестве связанной переменной.

В формуле свободна, а для ситуация сложнее: первые два её вхождения связаны, а третье — свободно. Аналогичную ситуацию имеем в формуле (, ) (), где два первых вхождения «подпадают под действие» квантора, а последнее — «не подпадает».

Упр. 19. [2]. Определите свободные и связанные вхождения переменных в формулах Рассмотрим формулу 0 2 + 3. Функция двух переменных и, выражаемая этой формулой, не изменится, если все связанные вхождения переменной заменить, например, буквой :

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

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

Для наглядной иллюстрации свободных и связанных вхождений переменных удобно пользоваться надстрочными линиями, демонстрирующими, какой квантор связывает какие вхождения переменных. К примеру, Обратим внимание, что в третьей формуле переменная в (, ) связывается с ближайшим к ней слева квантором, 38 Гл. 1. Элементы математической логики а не более далёким. Если теперь стереть все связанные переменные и заменить их пустыми «окнами», получим схему формулы, содержащую всю существенную информацию о ней:

Конгруэнтными, или подобными, называются формулы, схемы которых совпадают. В приведённом примере первая и третья формулы конгруэнтны. Кажется интуитивно очевидным, что конгруэнтные формулы «обозначают одно и то же», и далее (теорема 16 на с. 53) будет строго доказана эквивалентность конгруэнтных формул.

Упр. 20. [3]. Какие из этих формул конгруэнтны?

5. Введём классификацию формул сигнатуры :

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

Формула называется невыполнимой, если она ложна на любой оценке любой модели. Ясно, что формула невыполнима тогда и только тогда, когда её отрицание является тавтологией, т. е.

имеет место |= ¬.

Формула называется выполнимой, если можно указать хотя бы одну модель и оценку, на которой эта формула истинна, т. е. имеет место |= ¬.

Соотношение между общезначимыми, выполнимыми, опровержимыми и невыполнимыми формулами показывает следующая диаграмма:

невыполнимые общего вида общезначимые Упр. 21. [2]. Докажите, что выполнимы следующие формулы (дайте модели и оценки, на которых они истинны):

6. Чтобы доказать выполнимость (опровержимость) формулы логики предикатов, достаточно придумать хотя бы одну модель и оценку, в которых формула истинна (ложна). Как определить, что формула логики предикатов является общезначимой (невыполнимой)? Для этого необходим новый метод рассуждения. Здесь мы рассмотрим некоторые классы общезначимых формул, а в § 1. построим исчисление предикатов, которое будет порождать все общезначимые формулы логики предикатов и только их.

Теорема 11. Если формула логики высказываний является пропозициональной тавтологией, то подстановка в неё вместо пропозициональных переменных любых формул сигнатуры будет давать общезначимую формулу логики предикатов.

40 Гл. 1. Элементы математической логики Возьмём некоторую модель и оценку. Тогда каждая из формул сигнатуры, подставленная в пропозициональную тавтологию, примет значение t или f. Однако результирующая формула примет значение t, т. к. она даёт истину вне зависимости от истинностных значений своих переменных. Это будет иметь место для произвольной модели и оценки; следовательно, результирующая формула является общезначимой в логике предикатов.

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

7. В то же время заметим, что, например, должна быть общезначимой формула () (), где — одновалентный предикатный символ: если в выбранной модели () истинен для каждого значения, то он должен быть истинным и для произвольного значения, если же [ ()] = f, то вся импликация будет истинной уже в силу того, что её левая часть ложна. Можно ли обобщить это наблюдение для произвольной формулы вместо () и произвольного терма (переменной или константы) вместо ? По традиции Бурбаки [15], результат текстовой замены на в формуле обозначим следующим образом: ( | ). Мы стремимся доказать общезначимость чего-то вроде где — произвольная формула, — произвольная переменная, — произвольный терм.

В общем виде это, однако, не имеет места. Например, если формула имеет вид () & (), то результатом простой замены всех вхождений переменной на константу будет синтаксически некорректная последовательность символов ()&() (за квантором всегда должна следовать переменная, квантор по константе недопустим). Таким образом, первое условие на корректную подЯзык логики предикатов становку терма вместо переменной формулируется следующим образом: корректная подстановка ( | ) должна выполнять замену только свободных вхождений переменной.

Но и первого ограничения недостаточно, как показывает следующий пример: замена свободного вхождения на в формуле (, ) приведёт к тому, что переменная подпадёт под действие квантора, в результате чего частный случай схемы ( | ) — формула (, ) (, ) — не будет общезначимым.

Упр. 22. Проверьте, что формула (, ) (, ) не общезначима.

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

Упр. 23. Допустим, что подстановка ( | ) корректна. Всегда ли при этом будет корректна обратная подстановка ( | )( | )? (Ответ: нет, как, например, в случае (, ) (, ).) Для дальнейшего нам понадобится лемма, использующая свойства, заложенные в определение корректной подстановки.

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

42 Гл. 1. Элементы математической логики Доказательство проведём индукцией по построению формулы. Для атомарных формул корректная подстановка есть простая текстовая замена, поэтому [( | ) (...,,...)] = В случае формулы вида доказательство прямолинейно:

[( | )()] = [( | )( | )] = [( | )][( | )] = Случай ¬ аналогичен предыдущему.

Остаётся случай, когда формула начинается с квантора. Пусть, например, формула имеет вид, — её параметр (отсюда В силу корректности подстановки не является, поэтому значение не изменится, если оценку + заменить просто на.

Далее, т. к. не совпадает с, два изменения оценки можно поменять местами, откуда [( | )] = []( + [] + + ) = []( + []), что и требовалось доказать. Для случая доказательство то же, только дизъюнкцию необходимо заменить на конъюнкцию.

Теорема 13. Для произвольных формулы и терма, если подстановка ( | ) корректна, справедливо Докажем первое утверждение. Если на некоторой оценке ложна, то вся импликация будет истинна. Если в некоторой оценке истинна, то по определению истинности формула будет истинна на всякой оценке, отличающейся только лишь значением переменной. Значит, формула будет истинна и на оценке + + [], откуда по лемме 12 следует, что [( | )] = t, и вся импликация принимает значение t.

Упр. 24. Докажите второе утверждение теоремы 13.

Упр. 25. Приведите пример случая, когда некорректная подстановка даёт не общезначимую формулу вида ( | ). (Ответ:

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

§ 1.4. Исчисление предикатов 1. В этом параграфе мы, по аналогии с проделанным в § 1.2, построим исчисление, позволяющее выводить все тавтологии языка логики предикатов (и только их) из аксиом при помощи правил вывода. Основным результатом, как и тогда, станет доказательство эквивалентности понятия общезначимости формулы и её выводимости в построенном исчислении.

Прежде, однако, обсудим один принципиальный вопрос.

Доказуемость формулы исчисления высказываний эквивалентна её общезначимости, то же самое (как будет доказано ниже) имеет место для исчисления предикатов. Чтобы проверить, является ли тавтологией формула алгебры высказываний, достаточно подставить в неё все возможные комбинации переменных. Эту работу можно «поручить», например, компьютеру, который за конечное (хотя, может быть, и большое) время гарантированно выдаст ответ. Можно ли нечто подобное придумать для формул логики предикатов? Т. е. возможно ли «раз и навсегда» построить такой алгоритм, подавая на вход которого произвольную формулу произвольной сигнатуры, мы гарантированно получали бы на выходе ответ на вопрос: является ли эта формула выполнимой? (В этом 44 Гл. 1. Элементы математической логики случае можно было бы определять и общезначимость, для чего достаточно было бы проверить выполнимость и ¬.) Ответ на этот вопрос — отрицательный: в общем виде такого алгоритма не существует. Соответствующая теорема была доказана Чёрчем в 1936 г. (см. напр. [3]). Алгоритмы можно предложить лишь для некоторых очень ограниченных классов сигнатур:

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

Упр. 26. [6]. Пусть сигнатура состоит из одноместных предикатных символов. Докажите, что если формула такой сигнатуры выполнима, то она также выполнима в некоторой модели с множеством, состоящим из 2 элементов. Придумайте на основании этого алгоритм установления выполнимости формулы данной сигнатуры.

Не имея возможности в общем случае установить общезначимость формулы алгоритмическим путём, мы тем не менее всегда можем алгоритмически проверить корректность вывода формулы, если таковой предоставлен.

2. Для построения исчисления предикатов естественно взять десять схем аксиом и правило modus ponens исчисления высказываний (см. § 1.2), применив их для нового понятия формулы (§ 1.3, с. 33). Как мы уже знаем (см. теорему 4 и теорему 11), их применение будет давать общезначимые формулы сигнатуры. Добавим, кроме того, следующие схемы и правила вывода, касающиеся кванторов:

-схема: для любой формулы, переменной и терма, если подстановка (|) корректна, (|).

-правило Бернайса: если не входит в свободно, то -схема: для любой формулы, переменной и терма, если подстановка (|) корректна, (|).

-правило Бернайса: если не входит в свободно, то В этих схемах и правилах вновь проявляется «родство» квантора с конъюнкцией и квантора с дизъюнкцией. К примеру, -схема схожа со схемами &, & (они говорят о том, что можно получить из конъюнкции и квантора всеобщности), а -правило схоже со схемой ( ) (( ) ( & )) (они говорят о том, как можно получить конъюнкцию и квантор). Отметим также, что только лишь - и -схем нам было бы недостаточно: исчисление, не содержащее правил Бернайса, согласовывалось бы, например, с такой интерпретацией, при которой формула вида всегда истинна, а всегда ложна.

Упр. 27. [2]. Являются ли выводами в исчислении предикатов следующие последовательности формул:

() (() ())?

Ответы: 1) нет: попытка воспользоваться -схемой, но некорректная подстановка, 2) да:

-схема, -правило, 3) да:

-схема, первая схема исчисления высказываний, modus ponens.

Упр. 28. Докажите, что для произвольной формулы выводимо Теорема 14. Всякая выводимая в исчислении предикатов формула является общезначимой (если, то |= ).

Как и при доказательстве теоремы 4, необходимо проверить, что схемы дают общезначимые формулы, а правила вывода сохраняют общезначимость. Схемы, перенесённые из исчисления высказываний, являются пропозициональными тавтологиями; следовательно, в силу теоремы 11 при подстановке в них вместо букв, 46 Гл. 1. Элементы математической логики, произвольных формул сигнатуры они будут давать общезначимые формулы.

Теорема 13 показывает, что - и -схемы дают общезначимые формулы.

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

Остаются правила Бернайса. Пусть |= и не входит в свободно. Пусть истинна на некоторой оценке. В силу того, что она не зависит от, она истинна также и на любой оценке, отличающейся от значением переменной. В силу |=, в этих случаях также является истинной, а значит, является истинной. Значит, истинность в некоторой оценке является достаточным условием истинности в той же оценке; следовательно, |=, что и требовалось доказать.

Для второго правила Бернайса рассуждение симметричное.

Пусть |= и не входит свободно в. Пусть истинна на некоторой оценке. Это значит, что существует оценка, отличающаяся от только значением переменной, на которой истинна. В силу |= на оценке также должна быть истинна и. Но отличается от только значением переменной, от которой не зависит; следовательно, будет истинным и в оценке. Значит, истинность в некоторой оценке является достаточным условием истинности в той же оценке; следовательно, |=, что и требовалось доказать.

Как и в случае с исчислением высказываний, тут же вытекает Следствие. Не существует формулы, такой, что одновременно и ¬ в исчислении предикатов.

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

3. Будем говорить, что формулы и доказуемо эквивалентИсчисление предикатов ны, и писать если одновременно имеет место и. (Это определение с учётом теоремы о полноте исчисления высказываний согласуется с данным на с. 14 для пропозициональных формул.) Таким образом, установление доказуемой эквивалентности сводится к поиску вывода двух указанных импликаций.

4. Ниже рассматриваются некоторые наиболее употребимые на практике классы выводимых формул логики предикатов. Прежде всего отметим, что запас навыков, набранный при изучении исчисления высказываний, пригодится и при решении задач формального вывода в исчислении предикатов. Если известно, что — формула, выводимая в исчислении высказываний, то замена в ней пропозициональных переменных на формулы исчисления предикатов будет формулой, выводимой в исчислении предикатов (из аксиом по правилу modus ponens). Кроме того, можно пользоваться теоремой о полноте исчисления высказываний и считать выводимой любую формулу, полученную из пропозициональной тавтологии.

Мы пока что не ввели понятие вывода из посылок для исчисления предикатов и не будем пользоваться приёмами вывода из посылок по причине, которая станет ясна ниже. Но это ни в коем случае не «дисквалифицирует» формулы, выведенные в исчислении высказываний с помощью таких приёмов, т. к. для всех них можно эффективно построить и обычный вывод из аксиом по правилу modus ponens.

5. Правило обобщения. Докажем, что для любой формулы, если она выводима, то выводима также, т. е. справедливо правило вывода Возьмём какую-нибудь замкнутую (т. е. не содержащую свободных переменных) выводимую формулу. Такая формула существует: например, можно воспользоваться формулой, 48 Гл. 1. Элементы математической логики где получена из навешиванием любых кванторов по всем свободным переменным. Тогда 3) — -правило к шагу 2, которое допустимо применить в силу замкнутости формулы, 4) — modus ponens к шагу 3 и, что и требовалось.

6. Законы коммутативности кванторов формулируются следующим образом: если — произвольная формула, то справедливы следующие соотношения:

Заметим, что в последнем случае импликация верна только в одну сторону.

Докажем первое утверждение.

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

Теперь обоснуем обещанное правило вывода, которым будем пользоваться и в дальнейшем. Пусть и. Тогда 5) — modus ponens к шагам 4 и 2, что и требовалось доказать.

Упр. 30. Докажите второй и третий законы коммутативности кванторов. Указание: доказывая, докажите сперва Упр. 31. Обоснуйте правила вывода 7. Законы де Мргана для кванторов: для произвольной формулы, 50 Гл. 1. Элементы математической логики Действительно: докажем, например, что ¬¬. Т. к.

правая часть импликации не содержит, то достаточно доказать ¬¬, откуда можно было бы перейти к требуемой формуле по правилу Бернайса. По закону контрапозиции достаточно доказать ¬ ¬, но это аксиома. Переписывая наше рассуждение в обратном порядке, получим вывод для ¬¬.

Остальные импликации, составляющие содержание законов де Моргана, доказываются аналогично. Докажем, что ¬¬. Имея в виду закон контрапозиции, достаточно доказать ¬ ¬, имея в виду -правило — ¬ ¬. Применяя контрапозицию ещё раз, достаточно доказать, но это аксиома. Переписывая формулы в обратном порядке, получим вывод для ¬¬.

Упр. 32. Докажите второй закон де Моргана.

При помощи контрапозиции мы можем перейти и к такой форме законов де Моргана: ¬ ¬, ¬ ¬.

8. Пусть для некоторых формул, имеет место.

В силу -схемы,, откуда. Т. к. не входит в свободно, то. Аналогично, в силу -схемы Отсюда легко доказывается следующая важная лемма.

Лемма 15 (о замене подформулы). Замена подформулы на доказуемо эквивалентную даёт формулу, доказуемо эквивалентную исходной.

Проведём доказательство индукцией по построению, начиная с заменённой подформулы и рассматривая всё более длинные части формулы. Заменённая подформула эквивалентна исходной подформуле по условию. Теперь аналогично для других пропозициональных связок, 9. Законы пронесения квантора всеобщности через конъюнкцию и пронесения квантора существования через дизъюнкцию формулируются следующим образом: для любых формул, & и аналогично &. Воспользовавшись схемой аксиом ( ) (( ) ( & )) и правилом modus ponens, имеем Но переменная не входит свободно в левую часть доказанной конъюнкции, поэтому можно воспользоваться правилом Бернайса и заключить что и требовалось. В обратную сторону: от ( & ) доказываем импликацию к &, затем по отдельности к и, затем по правилу обобщения — к и и объединяем в конъюнкцию с помощью аксиомы (( & ) ) ((( & ) ) Упр. 33. Докажите по аналогии закон пронесения квантора существования через дизъюнкцию.

52 Гл. 1. Элементы математической логики Заметим, что нельзя аналогичным образом выносить квантор в начало формул вида и &. Обдумайте это3.

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

10. Корректное переименование связанных переменных. Пусть — формула. Рассмотрим две последовательности формул:

Чтобы эти последовательности были корректными выводами, требуется, во-первых, чтобы подстановка ( | ) была корректной (и тогда первый шаг станет аксиомой), а во-вторых — чтобы переменная не содержалась свободно в (и тогда второй шаг будет получаем из первого по правилу Бернайса).

Если оба условия выполняются, то мы можем утверждать, что будут верны и в обратную сторону! В самом деле: т. к. подстановка ( | ) заменяет все свободные вхождения на, то формула ( | ) не содержит свободно. Может ли быть некорректной обратная подстановка ( | )( | ), т. е. возможно ли, чтобы переменная, подставленная вместо какого-либо из свободных вхождений в формулу ( | ), подпала под действие одноимённого квантора? Т. к. переменная не входила свободно в формулу, то все свободные вхождения в формулу ( | ) есть результат В книге [6] при обсуждении законов пронесения кванторов авторы приводят такой пример: «В одном из выступлений начала перестройки М. С. Горбачёв сказал, что нужны преданные делу социализма, но квалифицированные специалисты“... Так вот, их существование не следует из отдельного существования тех и других.»

текстовой замены свободных, т. е. не связанных кванторами, вхождений буквы в формулу. Обратная подстановка вновь заменит все эти свободные вхождения в формуле ( | ) на, и в силу только что сказанного все эти будут свободными. Таким образом, обратная подстановка ( | )( | ) корректна и в результате её мы получим исходную формулу.

Условия «подстановка ( | ) корректна и не входит в свободно» мы будем называть условиями на корректное переименование связанной переменной. Из изложенного следует, что если эти условия выполняются, то Только что доказанное и лемма 15 о замене подформулы дают нам возможность строго обосновать эквивалентность конгруэнтных формул.

Теорема 16. Конгруэнтные формулы доказуемо эквивалентны.

Заметим, что переименование связанных переменных, сохраняющее схему формулы, является корректным. В самом деле, пусть формула имеет, например, вид Нарушение условия на корректность подстановки привело бы к появлению новых связей в формуле ( | ):

54 Гл. 1. Элементы математической логики а нарушение условия на отсутствие свободных вхождений — к связыванию прежде свободных переменных:

Используя ранее не использованные ни в, ни в переменные для замены связанных, мы можем две конгруэнтные формулы и привести к третьей формуле, которая будет конгруэнтна и доказуемо эквивалентна формулам и. Т. к. обе формулы и эквивалентны, то они эквивалентны и друг другу.

11. Навешивание фиктивных кванторов. Если не входит свободно в формулу, то Доказательство простое. Если не входит в свободно, то из выводимой формулы (вспомним лемму 3!) по - и правилам Бернайса.

12. Законы пронесения кванторов в общем виде: для любой формулы и формулы, такой, что не содержится в свободно, справедливы следующие восемь утверждений об эквивалентности:

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

Утверждения с пятого по восьмое доказать уже не так просто — без использования сведения к противоречию не обойтись.

Докажем пятое и шестое утверждения в одну сторону. Для краткости обозначим буквой формулу доказуемо эквивалентную формуле ¬( & ( & )).

Выведем из противоречие, т. е. докажем сначала, а затем ¬, откуда будет следовать ¬ и & ( & ), что нам и требуется.

Формула выводится элементарно — двойным применением схемы &. Выведем теперь ¬.

Действительно, из можно последовательно вывести импликации к формулам ¬( & ), ¬( & ) — закон де Моргана, ¬(&) —-схема, наконец, в силу того что ¬(&) ( ¬), имеем С другой стороны,, по второй схеме ( ) (( ( ¬)) ( ¬)) и, применяя дважды modus ponens, имеем Но не содержит свободно (вот где мы задействовали тот факт, что не содержится в свободно), поэтому можно применить правило Бернайса и заключить ¬, ¬, но это противоречие с. Доказательство не изменится, если поменять местами и. Тем самым пятое и шестое утверждения в одну сторону доказаны.

56 Гл. 1. Элементы математической логики Докажем пятое и шестое утверждения в обратную сторону. Теперь обозначим через формулу доказуемо эквивалентную ¬(( & ) & ). Выведем противоречие: ( & ) и ¬( & ), откуда будет Для произвольных формул и имеет место а от формулы ¬ можно последовательно вывести импликации к: ¬ — -схема, ¬ ¬ — схема для дизъюнкции, ¬( & ) — закон де Моргана для высказываний. Итак, для произвольных и имеет место Воспользовавшись соответствующей схемой, имеем и, применив дважды modus ponens с учётом уже выведенных формул, получим Т. к. не входит свободно в левую часть (опять играет роль соглашение, принятое относительно формулы !), можно воспользоваться правилом Бернайса и вывести последовательно ¬ Но от формулы можно последовательно вывести импликацию к ¬( & ) и ¬ ¬, откуда окончательно и мы пришли к искомому противоречию.

Используя законы де Моргана и эквивалентности 5 и 6, не составляет труда доказать оставшиеся две эквивалентности 7 и 8.

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

13. Будем говорить, что формула находится в предварённой, или пренексной, нормальной форме, если она имеет вид где каждый Q — квантор или , а формула не содержит кванторов. Выведенные в этом параграфе законы позволяют доказать следующее утверждение:

Теорема 17. Для любой формулы логики предикатов имеется эквивалентная ей формула в предварённой нормальной форме (ПНФ).

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

Атомарные формулы находятся в ПНФ в соответствии с определением.

Пусть формула имеет вид, и в соответствии с предположением индукции имеется, где — формула в предварённой нормальной форме. Тогда также находится в ПНФ, и в силу леммы 15 о замене подформулы.

То же самое для случая.

58 Гл. 1. Элементы математической логики Пусть формула имеет вид ¬, и — ПНФ для. Последовательно применяя законы де Моргана ¬ ¬ и ¬ ¬, мы можем «продвинуть» знак отрицания вплоть до бескванторной части формулы, по ходу меняя кванторы на сопряжённые, получив в итоге ПНФ для формулы ¬.

Пусть формула имеет вид &, и имеются, — ПНФ для формул, соответственно. Последовательно применяя законы пронесения, мы можем один за другим перенести все кванторы в начало формулы. При этом на каждом шаге, возможно, потребуется переименование связанных переменных, чтобы создать условия применимости законов пронесения кванторов.

Если на каком-то этапе оба аргумента конъюнкции начинаются с квантора всеобщности, то переименованием связанных переменных приводим конъюнкцию к виду &, что эквивалентно ( & ). Во всех остальных случаях переименовываем связанную переменную одной из формул так, чтобы она не входила свободно в другую формулу, и пользуемся соответствующим законом пронесения в общем виде. На каждом шаге количество не перенесённых кванторов уменьшается на один или два, поэтому за конечное число шагов процесс завершится.

Аналогично для случая.

Если формула имеет вид, то заменяем её на эквивалентную ¬, чем сводим задачу к уже рассмотренным Упр. 35. [2, 6]. Привести к предварённой нормальной форме следующие формулы:

Частичное решение:

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

Прежде всего обобщим понятие выводимости из посылок на исчисление предикатов. Пусть формулы 1,... замкнуты, т. е.

не имеют свободных переменных. Будем говорить, что формула выводима из посылок 1,... и писать 1,..., если можно предоставить последовательность формул 1,..., в которой каждая формула либо является одной из посылок 1,..., либо аксиомой, либо следует из двух предшествующих формул по modus ponens, либо следует из одной из предшествующих по -правилу или -правилу и где совпадает с. Условие замкнутости формул 1,... является существенным: без него невозможно распространить теорему о дедукции на исчисление предикатов. Действительно: по правилу обобщения (с. 47) из произвольной формулы выводится формула, но формула, если не требовать замкнутости, необщезначима и потому невыводима. Если же потребовать замкнутость, то проблем нет: можно применить правило Бернайса к.

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

60 Гл. 1. Элементы математической логики Как и прежде, в одну сторону утверждение является, по сути, переформулировкой правила modus ponens. Пусть существует вывод формулы из посылок. Тогда, если добавить к числу посылок, будет выводима из и по modus ponens.

Обратное утверждение доказывается по той же схеме, что и в теореме 5 о дедукции в исчислении высказываний. Пусть 1,... — вывод формулы из набора посылок и посылки.

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

Для каждой из формул 1,... имеет место один из шести случаев:

1) есть.

2) принадлежит.

3) является аксиомой.

4) получается по modus ponens из и, <.

Случаи 1–4 доказываются так же, как и в теореме 5.

5) выводится по -правилу Бернайса, т. е.,, переменная не входит свободно в, и есть формула По предположению индукции ( ), а нам требуется доказать, что ( ). Для этого воспользуемся тем фактом, что (проверьте!) Из этой эквивалентности вытекает, что &, где не входит свободно в, а формула — замкнута. Следовательно, не входит свободно в &, и мы можем воспользоваться -правилом Бернайса: &.

Воспользовавшись той же эквивалентностью в обратную сторону, получаем ( ), что и требовалось.

6) выводится по -правилу Бернайса, т. е.,, переменная не входит свободно в, и есть формула Теперь нам, имея предположение индукции ( ), требуется доказать, что ( ). Воспользуемся следующей эквивалентностью (проверьте её):

Из этой эквивалентности вытекает, что ( ), где не входит свободно в, а формула — замкнута. Следовательно, не входит свободно в, и мы можем воспользоваться -правилом Бернайса: ( ).

Воспользовавшись той же эквивалентностью в обратную сторону, получаем ( ), что и требовалось.

Теорема 19. Для любой формулы, замкнутых формул, и множества замкнутых формул справедливы правила введения и удаления, сформулированные в теореме 6 (табл. на с. 25).

Почти все доказательства, данные для теоремы 6, справедливы и в исчислении предикатов, т. к. основаны на теореме о дедукции и не допускают появления формул со свободными переменными слева от знака. Единственное исключение составляет ¬-удаление: в процессе его обоснования формула оказывается в числе посылок. Но это несущественно: мы можем сначала вывести вместо формулы её замыкание кванторами всеобщности, а потом воспользоваться аксиомой и modus ponens.

2. Назовём моделью множества замкнутых формул такую модель M, на которой все формулы из одновременно истинны.

Множество может и не иметь модели (например, если состоит из формул () и ¬ ()), тогда оно называется несовместным.

Если у есть модель, то называется совместным множеством.

62 Гл. 1. Элементы математической логики Теорема 20. Если и все формулы из одновременно истинны в некоторой модели M, то формула также истинна в модели M.

Пусть состоит из формул 1,.... Тогда по теореме о дедукции В модели M все истинны, а в силу теоремы 14 вся формула также должна быть истинной в M. Но это возможно только тогда, когда также истинна в M, что и требовалось доказать.

Набор замкнутых формул сигнатуры может рассматриваться как набор аксиом — изначальных утверждений, из которых, следуя логическим правилам, выводятся производные утверждения, или теоремы. Именно поэтому также называют теорией. Теория называется противоречивой, если существует такая формула, что одновременно и ¬. Если — замкнута, то, как известно, в этом случае по правилу ¬-удаления выводится вообще всё, что угодно, любая формула. Но и если — не замкнута, ситуация не меняется. По правилу обобщения, и (¬), где штрих означает замыкание формулы кванторами всеобщности по всем свободным переменным. Воспользовавшись тем, что, где означает замыкание формулы кванторами существования по всем свободным переменным. Для справедливо ¬-удаление и из возможно вывести любую формулу.

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

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

Теорема 21. Любая теория, имеющая модель, непротиворечива.

Пусть — множество замкнутых формул, имеющее модель M. Выберем любую замкнутую формулу. Если бы было противоречивым, то имело бы место и ¬. Но по теореме 20, все формулы, выводимые из, должны быть истинны в модели M — следовательно, должна быть одновременно истинной и ложной, чего быть не может.

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

Нам понадобится ещё понятие полного множества замкнутых формул и две леммы.

Будем говорить, что множество формул полное, если для любой замкнутой формулы сигнатуры имеет место либо, либо ¬. Ясно, что всякое противоречивое множество полно, но интерес представляют только полные непротиворечивые множества замкнутых формул.

Лемма 22 (Линденбаума). Любое непротиворечивое множество формул целиком содержится в некотором непротиворечивом полном множестве формул.

Пусть — непротиворечивое множество замкнутых формул.

Заметим, что для любой замкнутой формулы либо,, либо, ¬ — непротиворечивое множество. Предположим обратное, тогда существуют такие формулы и, что, и, ¬;

64 Гл. 1. Элементы математической логики, ¬ и, ¬ ¬. Тогда из первой пары утверждений по ¬введению следует ¬, а из второй пары — ¬¬. Но по условию — непротиворечивое множество формул.

Занумеруем всё множество формул сигнатуры так, что будет обозначать -ю по порядку формулу. Сделать это можно, например, так: любая формула есть конечная строка в алфавите из конечного числа символов, и потому может быть проинтерпретирована как натуральное число, записанное в -ичной системе счисления.

Тогда номер формулы есть количество формул сигнатуры среди строк, соответствующих числам в -ичной системе счисления, меньшим или равным.

Обозначим также через 1 и будем на каждом -м шаге добавлять к формулу, равную или ¬, таким образом, чтобы +1, полученное добавлением формулы ко множеству, было непротиворечивым. Докажем, что результат добавления всех формул к (обозначим его как ) будет искомым полным непротиворечивым множеством.

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

Важно заметить, что только что приведённое доказательство леммы Линденбаума имеет принципиальное отличие от доказательств, рассматривавшихся нами до сих пор. Прежде, обосновывая существование какого-нибудь объекта, мы давали «рецепт», буквально следуя которому этот объект можно было бы построить в любом конкретном случае. К примеру, доказательство теоремы о дедукции содержит в себе алгоритм построения вывода из предъявленного вывода,, а доказательство теоремы 10 о полноте исчисления высказываний даёт способ построения (пусть не самого изящного) вывода любой общезначимой пропозициональной формулы. Доказательство же леммы Линденбаума бесполезно для практического построения полного непротиворечивого надмножества над данным непротиворечивым множеством формул. Почему? На каждом шаге требуется принимать решение, какую из формул, ¬ добавлять к множеству, и, хотя известно, что одну из них, действительно, можно добавить, сохранив непротиворечивость (иначе было бы противоречивым), мы не имеем никакого представления о том, какую именно из формул надо добавлять. Поэтому ниже мы докажем существование вывода любой общезначимой формулы логики предикатов, не зная, как этот вывод построить. (Заметим ещё, что бесконечность множества тут роли не играет: в конечном итоге нас интересует не само, а возможность определения принадлежности той или иной формулы к.

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

Лемма 23. Если множество содержит замкнутую формулу и непротиворечиво, а константа не входит ни в одну из формул множества, то добавление формулы ( | ) к оставляет это множество непротиворечивым.

Прежде всего заметим, что формула ( | ) замкнута: в силу замкнутости единственным параметром формулы может быть переменная, но она заменяется на константу. Поэтому добавлять ( | ) к посылкам допустимо.

Теперь проведём доказательство от противного. Если добавление формулы ( | ) к делает множество противоречивым, то это означает (¬-введение), что из выводится ¬( | ). Возьмём вывод формулы ¬( | ) из и текстуально заменим в нём 66 Гл. 1. Элементы математической логики все вхождения константы на новую переменную, такую, что не встречается ни в одной формуле из (в т. ч. в ). При этом вывод останется выводом: аксиомы и правила вывода не различают констант и переменных, а формулы не изменятся и останутся замкнутыми (тут мы впервые использовали тот факт, что не входит в формулы из ).

Таким образом, имеет место ¬( | ), откуда по правилу обобщения ¬( | ) и по закону де Моргана ¬( | ).

Но не входит в формулу — и это значит, что выполняется условие корректного переименования связанных переменных (см.

с. 52). Поэтому ( | ) и окончательно ¬.

Но содержит формулу, следовательно, должно быть противоречивым, но это противоречит условию.

Теорема 24 (Гёделя). Любая непротиворечивая теория сигнатуры имеет модель.

Мы ограничимся случаем, когда сигнатура имеет конечное количество предикатных символов и констант, хотя теорема обобщается и на бесконечные сигнатуры.

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

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

Кроме того, для каждого натурального числа, начиная с 4, мы добавим в исходную сигнатуру по новой константе. У нас, таким образом, получится новая сигнатура, которая содержит все символы из и счётно-бесконечное множество констант, каждая из коИли с + 1 — это зависит от того, считать ли нуль натуральным числом.

По традиции в руководствах по математической логике и теории множеств нуль включают в множество натуральных чисел.

торых интерпретируется уникальным натуральным числом. Осталось проинтерпретировать предикатные символы.

Теперь мы будем действовать примерно так же, как и при доказательстве леммы Линденбаума (на самом деле, нам нужна была не она сама, а способ рассуждений при её доказательстве). Занумеруем всё множество формул сигнатуры так, что будет обозначать -ю по порядку формулу. Обозначим также через 1 и будем на каждом -м шаге добавлять к формулы ¬, если добавление к ведёт к противоречию, Результатом всех этих добавлений будет полное непротиворечивое множество формул : его полнота следует из построения, непротиворечивость на каждом -м шаге следует из леммы 23, а непротиворечивость всего доказывается так же, как в лемме Линденбаума. К тому же, множество обладает тем свойством, что если, то найдётся такая константа, что Рассмотрим все замкнутые атомарные формулы, т. е. формулы вида где — предикатный символ валентности, а — -я константа сигнатуры. В силу полноты и непротиворечивости для каждой такой формулы возможны всего два варианта: либо она сама, либо её отрицание выводятся из. Естественно предложить такую в противном случае — [ (1,..., )] = f. Т. к. нашей сигнатуре константы имеются для всех элементов предметной области, мы тем самым полностью задаём интерпретацию всех предикатных символов на множестве натуральных чисел. Построение модели M завершено.

68 Гл. 1. Элементы математической логики Теперь нам необходимо доказать, что все формулы из, рассматриваемые как формулы сигнатуры, одновременно истинны в M. Для этого нам достаточно доказать, что все замкнутые формулы, выводимые из в сигнатуре, истинны в M. Для начала будем действовать в терминах расширенного множества формул расширенной сигнатуры и докажем, что для любой замкнутой формулы сигнатуры имеет место пара утверждений:

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

Итак, индукция по построению. Для всякой замкнутой формулы имеет место один из перечисленных случаев:

1) Формула является атомарной. В этом случае оба утверждения верны по построению интерпретации M.

2) Формула имеет вид ¬. Если ¬, то в силу непротиворечивости. В этом случае, по предположению индукции, — ложна и, следовательно, ¬ — истинна. Если ¬, то в силу полноты. По предположению индукции, — истинна и, следовательно, ¬ — ложна.

3) Формула имеет вид, где — логическая связка. Возможны только четыре комбинации выводимостей для формул (Тут мы воспользовались утверждениями леммы 8 из § 1.2.) Пусть, например,. В силу непротиворечивости исключён случай, когда, ¬, во всех же остальных случаях должна быть истинной по предположению индукции. Пусть теперь. Это возможно только в ситуации, ¬, в которой, по предположению индукции, — истинна, — ложна и, следовательно, ложна.

Аналогично разбираются случаи для всех остальных логических связок.

4) Формула имеет вид. По построению имеется такая константа, что ( | ). В силу замкнутости параметром может являться только переменная, поэтому ( | ) замкнута и имеет меньшее количество логических связок, чем. Поэтому можно применить предположение индукции, в силу которого ( | ) истинна в M. Тогда по лемме из § 1.3 формула истинна на оценке ( ) и истинна.

Пусть. Утверждение о ложности в этом случае докажем от противного. Если предположить, что истинна, то найдётся элемент предметной области, а с ним и константа, для которой ( | ) истинна. По предположению индукции, все более простые истинные формулы обязаны быть выводимыми, поэтому ( | ). Но по -схеме ( | ) (), и по modus ponens — противоречие.

5) Пусть формула имеет вид и выводима из. Формула ( | ) является аксиомой для любой константы, поэтому и ( | ) выводима из для любой константы.

По предположению индукции каждая формула ( | ) истинна в M, значит, истинна на любой оценке ( ) и (т. к.

множество констант в «покрывает» всю предметную область) истинна.

70 Гл. 1. Элементы математической логики Покажем, наконец, что если, то ложна в M.

Действительно, если не выводима, то выводимо её отрицание, доказуемо эквивалентное ¬. По построению имеется такая константа, что выводима формула ¬( | ), истинная по предположению индукции. Поэтому истинна не при всех значениях, и формула ложна.

Итак, мы показали, что всякая замкнутая формула, выводимая из (в частности, принадлежащая множеству исходных посылок, являющемуся частью ), истинна в M. Т. е. M действительно является моделью для непротиворечивого множества замкнутых формул.

Заметим, что, доказывая теорему 24, мы построили модель на множестве натуральных чисел. Отсюда следует ещё одно утверждение, являющееся вариантом теоремы Лёвенгейма–Сколема.

Теорема 25 (Лёвенгейма–Сколема). Если теория конечной сигнатуры имеет модель, то она также имеет модель на множестве натуральных чисел в качестве предметной области.

Упр. 36. Докажите, что если формула истинна в любой модели на множестве натуральных чисел, то она общезначима.

Упр. 37. Следует ли общезначимость формулы из её истинности на любой модели с конечным числом элементов предметной области?

(Попробуйте привести контрпример.) Теперь для нас уже не составит труда доказать главный результат этого параграфа.

Теорема 26 (Гёделя о полноте исчисления предикатов). Всякая общезначимая формула выводима в исчислении предикатов: если |=, то.

Сначала рассмотрим только случай замкнутых формул.