Полные системы связок
Рассматриваемая нами система пропозициональных связок (, , , ) полна в следующем смысле:
Теорема 3 (Полнота системы связок). Любая булева функция аргументов может быть записана в виде пропозициональной формулы.
Проще всего пояснить это на примере. Пусть, например, булева функция задана таблицей 1.4
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
В таблице есть три строки с единицами в правой колонке — три случая, когда булева функция истинна (равна). Напишем три конъюнкции, каждая из которых покрывает один случай (а в остальных строках ложна), и соединим их дизъюнкцией. Нужная формула построена.
Ясно, что аналогичная конструкция применима для любой таблицы (с любым числом переменных).
Для формул подобного вида есть специальное название: формулы в дизъюнктивной нормальной форме. Более подробно: литералом называется переменная или отрицание переменной, конъюнктом называется произвольная конъюнкция литералов, а дизъюнктивной нормальной формой называется дизъюнкция конъюнктов. В нашем случае в каждый конъюнкт входит
литералов (где — число переменных), а число конъюнктов равно числу строк с единицами и может меняться от нуля (тогда, правда, получается не совсем формула, а "пустая дизъюнкция", и ее можно заменить какой-нибудь всегда ложной формулой типа ) до (если булева функция всегда истинна).
5. Длина построенной в доказательстве теоремы 3 формулы зависит от числа единиц: формула будет короткой, если единиц в таблице мало. А как написать (сравнительно) короткую формулу, если в таблице мало нулей, а в основном единицы?
Иногда полезна конъюнктивная нормальная форма, которая представляет собой конъюнкцию дизъюнктов. Каждый дизъюнкт состоит из литералов, соединенных дизъюнкциями. Теорему 3 можно теперь усилить так:
Теорема 4. Всякая булева функция может быть выражена формулой, находящейся в дизъюнктивной нормальной форме, а также формулой, находящейся в конъюнктивной нормальной форме.
Первая часть утверждения уже доказана. Вторая часть аналогична первой, надо только для каждой строки с нулем написать подходящий дизъюнкт.
Можно также представить функцию в дизъюнктивной нормальной форме, а затем воспользоваться законами Де Моргана, чтобы внести отрицание внутрь.
6. Проведите второй вариант рассуждения подробно.
Вообще говоря, определение нормальной формы не требует, чтобы в каждом конъюнкте (или дизъюнкте) встречались все переменные. (Повторять переменную больше одного раза смысла нет; если, например, переменная и ее отрицание входят в одну конъюнкцию, то эта конъюнкция всегда ложна и ее можно выбросить.)
7. Приведите пример булевой функции аргументов, у которой любая дизъюнктивная или конъюнктивная нормальная форма содержит лишь члены длины . (Указание: рассмотрите функцию, которая меняет свое значение при изменении значения любой переменной.)
Заметим, что при доказательстве теоремы 3 мы обошлись без импликации. Это и не удивительно, так как она выражается через дизъюнкцию и отрицание:
(проверьте!). Мы могли бы обойтись только конъюнкцией и отрицанием, так как
или только дизъюнкцией и отрицанием, так как
(обе эквивалентности вытекают из законов Де Моргана; их легко проверить и непосредственно). Как говорят, система связок , а также система связок
являются полными. (По определению это означает, что с их помощью можно записать любую булеву функцию.)
8. Докажите, что система связок полна. (Указание: как записать через них дизъюнкцию?)
А вот без отрицания обойтись нельзя. Система связок неполна — и по очень простой причине: если все переменные истинны, то любая их комбинация, содержащая только указанные связки, истинна. (Как говорят, все эти связки "сохраняют единицу".)
9. Легко понять, что любая формула, составленная только с помощью связок и , задает монотонную булеву функцию (в том смысле, что от увеличения значения любого из аргументов значение функции может только возрасти — или остаться прежним). Покажите, что любая монотонная булева функция может быть выражена формулой, содержащей только и.
10. Пусть — тавтология. Покажите, что найдется формула , которая включает в себя только общие для и переменные, для которой формулы и являются тавтологиями. (Более общий вариант этого утверждения, в котором рассматриваются формулы с кванторами, называется леммой Крейга.)
В принципе мы не обязаны ограничиваться четырьмя рассмотренными связками. Любая булева функция может играть роль связки. Например, можно рассмотреть связку , задаваемую эквивалентностью
(словами: ложно, лишь если
и истинны). Через нее выражается отрицание (), после чего можно выразить конъюнкцию, а затем, как мы знаем, и вообще любую функцию. (Знакомые с цифровыми логическими схемами малого уровня интеграции хорошо знакомы с этим утверждением: достаточно большой запас схем И-НЕ позволяет реализовать любую требуемую зависимость выхода от входов.)
Другая интересная полная система связок — сложение по модулю, конъюнкция и константа (которую можно считать -арной связкой, задающей функцию от нуля аргументов). Представленные в этой системе булевы функции становятся полиномами с коэффициентами в кольце вычетов по модулю . Идея рассматривать булевы функции как полиномы (оказавшаяся неожиданно плодотворной в последние годы) была высказана в 1927 г. российским математиком Иваном Ивановичем Жегалкиным.
Назовем мономом конъюнкцию любого набора переменных или константу (которую естественно рассматривать как конъюнкцию нуля переменных). Название это естественно, так как при наших соглашениях ( обозначает истину, — ложь) конъюнкция соответствует умножению.
Назовем полиномом сумму таких мономов по модулю (это значит, что , и ). Ясно, что два повторяющихся монома можно сократить (ведь сложение по модулю ), так что будем рассматривать только полиномы без повторяющихся мономов. При этом, естественно, порядок членов в мономе (как и порядок мономов в полиноме) роли не играет, их можно переставлять.
Теорема 5 (о полиномах Жегалкина). Всякая булева функция однозначно представляется таким полиномом.
Существование искомого полинома следует из теоремы 4, так как конъюнкция есть умножение, отрицание — прибавление единицы, а дизъюнкцию можно через них выразить (получится ). Надо только заметить, что степени не нужны: переменные принимают значения и, так что
можно заменить на.
Можно также сослаться на известное из алгебры утверждение о том, что всякая функция с аргументами из конечного поля (в данном случае это двухэлементное поле вычетов по модулю ) задается полиномом. (Отсюда, кстати, получается новое доказательство теоремы 3.)
Далее можно заметить, что полиномов столько же, сколько булевых функций, а именно . В самом деле, булева функция может принимать любое из двух значений в каждой из точек булева куба , а многочлен может включать или не включать любой из мономов. (Мономов ровно, потому что каждый моном включает или не включает любую из переменных.) Поэтому избытка полиномов нет, и если любая функция представима полиномом, то единственным образом.
Можно и не ссылаться на сведения из алгебры и теорему 4, а дать явную конструкцию. Это удобно сделать индукцией по . Пусть мы уже умеем представлять любую булеву функцию от аргументов с помощью полинома. Тогда можно представить как
(проверьте). Остается заметить, что правую часть можно представить полиномом по предположению индукции.
Для единственности также есть другое доказательство: пусть два многочлена (имеющие степень по каждой переменной) равны при всех значениях переменных. Тогда их сумма (или разность — вычисления происходят по модулю) является ненулевым многочленом (содержит какие-то мономы), но тождественно равна нулю. Так не бывает, и это легко доказать по индукции. В самом деле, любой многочлен можно представить в виде
где и — многочлены от меньшего числа переменных. Подставляя сначала , а затем , убеждаемся, что многочлены и равны нулю во всех точках, и потому (согласно предположению индукции) равны нулю как многочлены (не содержат мономов).
11. Пусть — произвольное поле.Назовем мультилинейной функцией полином от переменных с коэффициентами из, в котором все показатели степеней равны либо , либо. (Таким образом, каждый моном в ней есть произведение коэффициента и некоторого набора переменных без повторений.) Будем рассматривать как подмножество . Докажите, что всякая булева функция однозначно продолжается до мультилинейной функции , и коэффициенты мультилинейной функции можно считать целыми числами.
Если рассматривать произвольные булевы функции в качестве связок, возникает вопрос: в каком случае набор булевых функций образует полный базис? (Это значит, что любая булева функция представляется в виде композиции функций из набора, т. е. записывается в виде формулы, где связками служат функции набора.) Подобные вопросы вызывали в свое время большой интерес и были хорошо изучены. Начальным этапом явилось такое утверждение:
Теорема 6 (критерий Поста). Набор булевых функций является полным тогда и только тогда, когда он не содержится целиком ни в одном из пяти следующих "предполных классов":
монотонные функции;функции, сохраняющие нуль;функции, сохраняющие единицу;линейные функции;самодвойственные функции.
(Функция монотонна, если она монотонно неубывает по каждому из своих аргументов. Функция сохраняет нуль/единицу, если (соответственно ). Функция линейна, если она представима многочленом, в котором все мономы содержат не более одной переменной. Наконец, функция называется самодвойственной, если .)
Если набор содержится в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому набор не является полным. Докажем обратное утверждение. Пусть для каждого класса выбрана какая-то функция, в нем не лежащая. Убедимся, что с помощью комбинаций выбранных функций можно получить все булевы функции.
У нас есть функция, не сохраняющая нуль. Подставим вместо всех аргументов одну и ту же переменную. Получится функция от одного аргумента, отображающая нуль в единицу, то есть либо константа , либо отрицание. Сделав то же самое с функцией, не сохраняющей единицу, получим либо константу нуль, либо отрицание. Таким образом, у нас либо есть отрицание, либо обе константы и.
Если есть обе константы, то все равно можно получить отрицание. Возьмем немонотонную функцию. Легко понять, что она должна менять значение с единицы на нуль при изменении какого-то одного аргумента с нуля на единицу (в самом деле, будем увеличивать аргументы по одному, в какой-то момент значение функции уменьшится.) Зафиксировав значения остальных аргументов (ведь мы считаем, что константы есть), получаем отрицание.
Имея отрицание и несамодвойственную функцию, легко получить константы (если их не было). В самом деле, несамодвойственность означает, что
для каких-то значений . Вместо нулевых значений переменных подставим , вместо единиц подставим , получится одна из констант. Вторая получится отрицанием.
Теперь у нас есть константы, отрицание и нелинейная функция . Нелинейность означает, что в ее представлении в виде многочлена есть моном, состоящий более чем из одной переменной. Пусть, например, этот моном содержит переменные и . Сгруппируем члены по четырем группам и получим выражение
При этом многочлен заведомо отличен от нуля, поэтому можно так подставить константы вместо , чтобы первое слагаемое не обратилось в нуль. Тогда получим либо , либо , либо , либо . Свободный член можно менять, если нужно (у нас есть отрицание), так что получается либо
(конъюнкция, и все доказано), либо (убираем отрицание, получаем конъюнкцию, все доказано), либо (аналогично), либо (дизъюнкция, все доказано).
Высказывания и операции
"Если число рационально, то — алгебраическое число. Но оно не алгебраическое. Значит, не рационально." Мы не обязаны знать, что такое число, какие числа называют рациональными и какие алгебраическими, чтобы признать, что это рассуждение правильно — в том смысле, что из двух сформулированных посылок действительно вытекает заключение. Такого рода ситуации — когда некоторое утверждение верно независимо от смысла входящих в него высказываний — составляют предмет логики высказываний.
Такое начало (особенно если учесть, что курс логики входил в программу философского факультета, где также изучалась "диалектическая логика") настораживает, но на самом деле наши рассмотрения будут иметь вполне точный математический характер, хотя мы начнем с неформальных мотивировок.
Высказывания могут быть истинными и ложными. Например, "— простое число "— истинное высказывание, а "— простое число"— ложное (это число делится на ). Про высказывание " существует бесконечно много простых , для которых — также простое "никто не берется сказать наверняка, истинно оно или ложно. Заметим, что " делится на" в этом смысле не является высказыванием, пока не сказано, чему равно; при разных получаются разные высказывания, одни истинные (при четном), другие— ложные (при нечетном).
Высказывания можно соединять друг с другом с помощью " логических связок". Эти связки имеют довольно странные, но традиционные названия и обозначения (табл. 1.1). Отметим также, что в импликации высказывание называют посылкой, или антецедентом импликации, а — заключением, или консеквентом.
| и |
& and | конъюнкция | |||
| или |
or | дизъюнкция | |||
|
не неверно |
not | отрицание | |||
|
из следует если , то влечет — следствие |
then |
импликация следование |
Говорят также, что высказывание имеет истинностное значение И (истина), если оно истинно, или Л (ложь), если оно ложно. Иногда вместо И употребляется буква T (true) или число , а вместо Л — буква F (false) или число . (С первого взгляда идея произвольным образом выбрать числа и кажется дикой — какая бы польза могла быть от, скажем, сложения истинностных значений? Удивительным образом в последние годы обнаружилось, что такая польза есть, и если оперировать с истиной и ложью как элементами конечного поля, можно получить много неожиданных результатов.
Но это выходит за рамки нашей книги.)
Логические связки позволяют составлять сложные высказывания из простых. При этом истинность составного высказывания определяется истинностью его частей в соответствии с таблицей 1.2.
| Л | Л | Л | Л | И |
| Л | И | Л | И | И |
| И | Л | Л | И | Л |
| И | И | И | И | И |
| Л | И |
| И | Л |
истинно, если оба высказывания и истинны. Высказывание истинно, если хотя бы одно из высказываний и истинно. Высказывание ложно в единственном случае: если истинно, а ложно. Наконец, истинно в том и только том случае, когда Наложно.
Из всех связок больше всего вопросов вызывает импликация. В самом деле, не очень понятно, почему надо считать, скажем, высказывания "если , то "и "если , то " истинными. (Именно так говорят наши таблицы: .) Следующий пример показывает, что в таком определении есть смысл.
Общепризнано, что если число делится на , то оно делится на . Это означает, что высказывание истинно при всех . Подставим сюда : обе части ложны, а утверждение в целом истинно. При посылка импликации ложна, а заключение истинно, и вся импликация истинна. Наконец, при
посылка и заключение истинны и импликация в целом истинна. С другой стороны, обратное утверждение (если делится на , то делится на ) неверно, и число является контрпримером. При этом посылка импликации истинна, заключение ложно, и сама импликация ложна. Таким образом, если считать, что истинность импликации определяется истинностью ее частей (а не наличием между ними каких-то причинно-следственных связей), то все строки таблицы истинности обоснованы. Чтобы подчеркнуть такое узко-формальное понимание импликации, философски настроенные логики называют ее "материальной импликацией".
Теперь от неформальных разговоров перейдем к определениям. Элементарные высказывания (из которых составляются более сложные) мы будем обозначать маленькими латинскими буквами и называть пропозициональными переменными. Из них строятся пропозициональные формулы по таким правилам:
Всякая пропозициональная переменная есть формула.Если — пропозициональная формула, то — пропозициональная формула. Если и— пропозициональные формулы, то , и — пропозициональные формулы.
Можно еще сказать так: формулы образуют минимальное множество, обладающее указанными свойствами (слово "минимальное" здесь существенно: ведь если бы мы объявили любую последовательность переменных, скобок и связок формулой, то эти три свойства были бы тоже выполнены).
Пусть формула содержит пропозициональных переменных . Если подставить вместо этих переменных истинностные значения (И или Л), то по таблицам можно вычислить истинностное значение формулы в целом. Таким образом, формула задает некоторую функцию от аргументов, каждый из которых может принимать значения Л и И. Значения функции также лежат в множестве , которое мы будем обозначать. Мы будем следовать уже упоминавшейся традиции и отождествлять И с единицей, а Л — с нулем, тем самым есть. Формула задает отображение типа . Такие отображения называют также булевыми функциями аргументов.
Пример. Рассмотрим формулу . Она истинна в единственном случае — когда и
истинны, а ложно (см.таблицу 1.3).
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Пример. Формула является тавтологией (это можно проверить, например, составив таблицу). Она выражает такой логический закон: из конъюнкции утверждений следует первое из них.
1. Как выглядит симметричное утверждение для дизъюнкции и какая формула его выражает?
Две формулы называют эквивалентными,если они истинны при одних и тех же значениях переменных (другими словами, если они задают одну и ту же булеву функцию). Например, формула истинна лишь при , и потому эквивалентна формуле .
Рассмотрим формулу .
Она истинна, если переменная истинна, и ложна, если переменная
ложна. Хотелось бы сказать, что она эквивалентна формуле, но тут есть формальная трудность: она содержит две переменные и потому задает функцию от двух аргументов (типа ), в то время как формула задает функцию одного аргумента. Мы не будем обращать на это внимания и будем считать эти формулы эквивалентными. Вообще, если есть список переменных , содержащий все переменные некоторой формулы (и, возможно, еще какие-то переменные), можно считать, что формула задает функцию от аргументов, возможно, на деле зависящую не от всех аргументов (постоянную по некоторым аргументам)
После сделанных оговорок легко проверить следующий факт: формулы и эквивалентны тогда и только тогда, когда формула является тавтологией. Используя сокращение для , можно записывать утверждения об эквивалентности формул в виде тавтологий. Вот несколько таких эквивалентностей:
Теорема 1. Формулы являются тавтологиями.
Первые четыре эквивалентности выражают коммутативность и ассоциативность конъюнкции и дизъюнкции. Проверим, например, вторую: левая и правая части истинны в единственном случае (когда все переменные истинны), и потому эквивалентны. (Для дизъюнкции удобнее смотреть, когда она ложна.)
Две следующие эквивалентности утверждают дистрибутивность— заметим, что в отличие от сложения и умножения в кольцах здесь верны оба свойства дистрибутивности. Проверить эквивалентность легко, если отдельно рассмотреть случаи истинного и ложного.
Следующие два свойства, законы Де Моргана, легко проверить, зная, что конъюнкция истинна, а дизъюнкция ложна лишь в одном случае. Эти свойства иногда выражают словами: "конъюнкция двойственна дизъюнкции".
Далее следуют два очевидных закона поглощения (один из них мы уже упоминали).
За ними идет правило контрапозиции, которое говорит, в частности, что утверждения "если совершенно, то четно"и "если нечетно, то несовершенно"равносильны. Хотя оно и очевидно проверяется с помощью таблиц истинности, с ним связаны любопытные парадоксы.
Вот один из них.
Биолог А выдвинул гипотезу: все вороны черные. Проверяя ее, он вышел во двор и обнаружил на дереве ворону. Она оказалось черной. Биолог А радуется — гипотеза подтверждается. Биолог Б переформулировал гипотезу так: все не-черные предметы — не вороны (применив наше правило контрапозиции) и не стал выходить во двор, а открыл холодильник и нашел там оранжевый предмет. Он оказался апельсином, а не вороной. Биолог Б обрадовался — гипотеза подтверждается — и позвонил биологу А. Тот удивляется — у него тоже есть апельсин в холодильнике, но с его точки зрения никакого отношения к его гипотезе апельсин не имеет...
Другой парадокс: с точки зрения формальной логики утверждения "кто не с нами, тот против нас"и "кто не против нас, тот с нами"равносильны.
Последнее (и очевидное) правило
называется снятием двойного отрицания.
2. Перечисленные эквивалентности соответствуют равенствам для множеств: например, первая гарантирует, что
для любых множеств и. Какие утверждения соответствуют остальным эквивалентностям?
3. Две формулы, содержащие только переменные и связки , и , эквивалентны. Докажите, что они останутся эквивалентными, если всюду заменить на и наоборот.
Далеко не все тавтологии имеют ясный интуитивный смысл. Например, формула является тавтологией (если одно из утверждений и ложно, то из него следует все, что угодно; если оба истинны, то тем более формула истинна), хотя и отчасти противоречит нашей интуиции — почему, собственно, из двух никак не связанных утверждений одно влечет другое? Еще более загадочна тавтология (хотя ее ничего не стоит проверить с помощью таблиц истинности).
Отступление о пользе скобок.На самом деле наше определение истинности содержит серьезный пробел. Чтобы обнаружить его, зададим себе вопрос: зачем нужны скобки в формулах? Представим себе, что мы изменим определение формулы, и будем говорить, что и
являются формулами для любых и. Останутся ли наши рассуждения в силе?
Легко понять, что мы столкнемся с трудностью при определении булевой функции, соответствующей формуле.
В этом определении мы подставляли нули и единицы на место переменных и затем вычисляли значение формулы с помощью таблиц истинности для связок. Но теперь, когда мы изменили определение формулы, формула может быть получена двумя способами — из формул и с помощью операции и из формул и спомощью операции . Эти два толкования дадут разный результат при попытке вычислить значение.
Из сказанного ясно, что скобки нужны, чтобы гарантировать однозначность синтаксического разбора формулы. Точнее говоря, верно такое утверждение:
Теорема 2 (однозначность разбора). Пропозициональная формула, не являющаяся переменной, может быть представлена ровно в одном из четырех видов , ,
или , где и — некоторые формулы, причем
и (в первых трех случаях) восстанавливаются однозначно.
Формальное доказательство можно провести так: назовем скобочным итогом разницу между числом открывающихся и закрывающихся скобок. Индукцией по построению формулы легко доказать такую лемму:
Лемма. Скобочный итог формулы равен нулю. Скобочный итог любого начала формулы неотрицателен и равен нулю, лишь если это начало совпадает со всей формулой, пусто или состоит из одних символов отрицания.
Слова "индукцией по построению"означают, что мы проверяем утверждение для переменных, а также доказываем, что если оно верно для формул и , то оно верно и для формул , , и .
После того как лемма доказана, разбор формулы проводится так: если она начинается с отрицания, то может быть образована лишь по третьему правилу. Если же она начинается со скобки, то надо скобку удалить, а потом искать непустое начало, имеющее нулевой скобочный итог и не оканчивающееся на знак логической операции. Такое начало единственно (как легко проверить, используя лемму). Это начало и будет первой частью формулы. Тем самым формула разбирается однозначно.
Нет смысла вдаваться в подробности этого (несложного) рассуждения: вообще-то алгоритмы разбора формул — это отдельная большая и практически важная тема (в первую очередь в связи с компиляторами).Приведенный нами алгоритм далеко не оптимален. С другой стороны, мы вообще можем обойти эту проблему, потребовав, чтобы при записи формул левая и правая скобки, окружающие формулу, связывались линией — тогда однозначность разбора формулы не вызывает вопросов, и больше ничего нам не надо.
В дальнейшем мы будем опускать скобки, если они либо не играют роли (например, можно написать конъюнкцию трех членов, не указывая порядок действий в силу ассоциативности), либо ясны из контекста.
4. Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелов и разделителей). Например, в его обозначениях запишется как . Эту запись еще называют польской записью. Обратная польская запись отличается от нее тем, что знак операции идет после операндов. Покажите, что в обоих случаях порядок действий восстанавливается однозначно.
Схемы из функциональных элементов
Формулы представляют собой способ записи композиции функций. Например, если мы сначала применяем функцию, а потом функцию, это можно записать формулой . Но есть и другой способ: можно изобразить каждую функцию в виде прямоугольника с "входом"и "выходом"и соединить выход функции со входом функции (рис. 2.1).
Рис. 2.1. Два способа изобразить композицию g°f
Такое представление отнюдь не является чисто теоретическим. В течении нескольких десятков лет электронная промышленность выпускает микросхемы, которые выполняют логические операции. Такая микросхема имеет электрические контакты, напряжение на которых кодирует логические значения И и Л. Конкретное напряжение зависит от типа схемы, но обычно это несколько вольт, и высокий потенциал (относительно заземления) считается единицей, а низкий нулем.
Одной из типичных схем является схема И-НЕ, она имеет два входа и один выход. Сигнал на выходе является отрицанием конъюнкции сигналов на входе. Другими словами, на выходе появляется высокий потенциал (сигнал ) тогда и только тогда, когда на одном из входов потенциал низкий (). Из такой схемы легко получить схему НЕ (изменяющую уровень сигнала на противоположный), соединив проводом два входа. При этом на оба входа поступает один и тот же сигнал, и операция И его не меняет (), а НЕ меняет на противоположный. Взяв два элемента И-НЕ и используя второй из них в качестве элемента НЕ, инвертирующего сигнал с выхода первого элемента, получаем схему, которая реализует функцию И. А если поставить два элемента НЕ перед каждым из входов элемента И-НЕ, получим схему, реализующую функцию ИЛИ: .
Теорема 3 о полноте системы связок теперь гарантирует, что любую булеву функцию можно реализовать в виде схемы. Надо иметь в виду, однако, что предлагаемая в ее доказательстве конструкция (дизъюнктивная нормальная форма) имеет скорее теоретический интерес, поскольку приводит к схемам очень большого размера даже для простых функций (если число аргументов велико). Например, схема, сравнивающая два -битных числа, должна иметь входа и поэтому в ее реализации с помощью дизъюнктивной нормальной формы будет порядка
элементов — что мало реально. (Между тем такую схему можно построить гораздо проще, из нескольких сотен элементов.)
Поэтому вопрос о том, сколько элементов нужно для реализации той или иной функции, представляет большой интерес — как практический, так и философский. (Одна из центральных проблем математики и информатики, так называемая "проблема перебора", может быть сформулирована в этих терминах.)
Мы сейчас дадим более формальное определение схемы и реализуемой ей булевой функции. Но прежде всего ответим на такой вопрос — почему мы вообще говорим о схемах? Ведь можно записать композицию булевых функций в виде формулы, не будет ли это то же самое?
Оказывается, не совсем, и разницу легко увидеть на примере (рис. 2.2).
Рис. 2.2. Элемент входит в формулу дважды
Здесь один и тот же элемент схемы () приходится указывать в формуле дважды, поскольку его выход используется в качестве входа двух других элементов. Схемы, в которых такого ветвления нет (на практике ветвление вполне возможно, хотя и ограничено "нагрузочной способностью выхода", как говорят инженеры), как раз и соответствуют формулам. Но в общем случае полученная из данной схемы формула может быть длинной, даже если схема содержит небольшое число элементов, поскольку число копий может расти экспоненциально с ростом глубины схемы.
Хотя идея образования схемы из функциональных элементов, реализующих булевы функции, достаточно наглядна, дадим более формальное определение. Фиксируем некоторый набор булевых функций . Пусть имеется булевых (принимающих значения
и ) переменных , называемых входами. Пусть также имеется некоторое число булевых переменных , называемых проводниками. Пусть для каждого проводника схемы задана булева функция из , выражающая его значение через другие проводники и входы. При этом требуется, чтобы не было циклов (цикл образуется, когда зависит от , которое зависит от , которое зависит от ). Пусть, кроме того, среди проводников выделен один, называемый выходом. В таком случае говорят, что задана схема из функциональных элементов в базисе
с входами. Число называют размером схемы. (С точки зрения инженера размер — это число использованных элементов, а базис — это ассортимент доступных ему элементов.)
Отсутствие циклов гарантирует, что есть проводник, зависящий только от входов (иначе можно было бы найти цикл: возьмем какой-то проводник, затем возьмем тот проводник, от которого он зависит и т. д.). Значение этого проводника, таким образом, однозначно определяется сигналами на входах. Среди оставшихся проводников также нет цикла, поэтому можно найти один из них, зависящий только от уже известных, и определить его значение. Перенумеровав проводники в таком порядке, мы можем записать последовательность присваиваний
в правых частях которых стоят функции из , примененные ко входам и уже найденным значениям. При этом можно считать, что результат схемы есть
(все последующие присваивания уже не нужны). Такая программа определяет при известных значениях входов, и тем самым вычисляет некоторую булеву функцию.
Теперь набор булевых функций можно назвать полным, если любая булева функция может быть задана схемой из -элементов (существует программа, ее вычисляющая, при этом в правых частях присваиваний стоят функции из). Ясно, что это определение полноты равносильно прежнему, то есть возможности записать булеву функцию в виде формулы со связками из (как мы говорили, разница только в том, что один и тот же элемент будет фигурировать в формуле многократно).
Сложностью булевой функции относительно называют минимальный размер схемы из - элементов, вычисляющей функцию. Его обозначают.
Теорема 7. Пусть и — два полных набора булевых функций. Тогда соответствующие меры сложности отличаются не более чем на постоянный множитель: найдется такое число , что и
для любой функции.
Утверждение почти очевидно: поскольку наборы и полны, то каждая функция одного из наборов может быть вычислена какой-то схемой, составленной из элементов другого набора. Теперь можно взять в качестве наибольший размер таких схем, и неравенства будут выполняться: каждую строку программы можно заменить на (или меньше) строк с использованием функций другого набора.
Что можно сказать о сложности произвольной булевой функции
аргументов? Следующая теорема показывает, что она экспоненциально зависит от (для "наугад взятой"функции).
Теорема 8.(а) Пусть . Тогда сложность любой булевой функции аргументов не превосходит для всех достаточно больших. (б) Пусть. Тогда сложность большинства булевых функций аргументов не меньше для всех достаточно больших.
Прежде всего заметим, что по предыдущей теореме не имеет значения, какой полный базис выбрать (изменение значения более существенно, чем умножение сложности на константу).
Первое утверждение теоремы очевидно: размер схемы, реализующей дизъюнктивную нормальную форму с переменными, есть , поскольку имеется не более конъюнктов размера . (Напомним смысл -обозначений: означает, что существует верхняя оценка вида для некоторой константы .) Осталось заметить, что при достаточно больших (напомним, что).
Чтобы доказать второе утверждение, оценим число различных схем (скажем, в базисе И, ИЛИ, НЕ) размера с аргументами. Каждая такая схема может быть описана последовательностью из присваиваний, выражающих одну из переменных через предыдущие. Для каждого присваивания есть не более вариантов (три типа операций — конъюнкция, дизъюнкция, отрицание, и каждый из не более чем двух аргументов выбирается среди не более чем вариантов). Отсюда легко получить оценку на число всех функций сложности не более (считая ).
Всего булевых функций с аргументами имеется . Из сравнения этих формул видно, что что при и при достаточно больших булевы функции сложности меньше
составляют меньшинство, так как
много меньше .
12. Проведите вторую часть рассуждения более подробно и покажите, что при некотором сложность большинства булевых функций с аргументами не меньше .
Верхнюю оценку в теореме 8 можно усилить и показать, что сложность любой булевой функции аргументов не превосходит.
13. (a) Покажите, что можно построить схему размера с выходами, реализующую все возможных конъюнктов длины (для каждого— свой выход). (Указание: такую схему можно построить индуктивно.) (б) Покажите, что можно построить схему размера с выходами, реализующую все булевых функций аргументов. (Указание: эту схему также можно построить индуктивно.) (в) Пусть — булева функция, аргументы которой разбиты на две группы. Покажите, что ее можно записать в виде дизъюнкции членов, каждый из которых имеет вид , где — конъюнкт, а — произвольная булева функция. Вывести отсюда упомянутую выше оценку . (Указание: разумно положить , . См. также [9] и [33].)
Теорема 8, однако, ничего не говорит о сложности конкретных булевых функций. Ситуация здесь такова. Есть разнообразные методы и приемы получения верхних оценок. Но про нижние оценки неизвестно практически ничего. Про многие функции мы подозреваем, что их сложность велика (экспоненциально зависит от числа входов), но доказать это пока не удается. Весьма нетривиальные идеи позволяют доказывать экспоненциальные нижние оценки для некоторых специальных классов схем, например, схем из монотонных элементов или схем ограниченной глубины (использующих элементы И и ИЛИ с произвольным числом входов). Получение экспоненциальных оценок для более общих схем — один из возможных подходов к знаменитой проблеме перебора, центральной проблеме теории сложности вычислений.
Мы не будем углубляться в эту теорию, а приведем лишь несколько верхних оценок для конкретных задач. При этом мы не претендуем на полноту, а хотим лишь показать несколько интересных идей и приемов.
Рассмотрим функцию сравнения двух -битовых чисел. Она имеет аргументов ( для одного числа и для другого); ее значение равно , если первое число больше второго, и в противном случае.
Обозначим эту функцию.
Теорема 9. Пусть — полный набор функций. Существует такая константа , что .
Заметим, что поскольку в формулировке теоремы оценка размера проводится с точностью до константы, то выбор конкретного базиса не имеет значения. Другими словами, мы можем предполагать, что любое конечное число необходимых нам функций в этом базисе есть.
Схема сравнения чисел будет рекурсивной (чтобы сравнить два числа, мы отдельно сравниваем их левые и правые половины, а затем объединяем результаты). При этом, как часто бывает, надо усилить утверждение, чтобы индукция прошла. А именно, мы будем строить схему с входами и двумя выходами, которая указывает, какой из трех случаев , или имеет место. (Здесь — числа, записываемое в двоичной системе как и .) Два выходных бита кодируют четыре возможности, а нужно только три, так что есть некоторый запас. Для определенности можно считать, что первый выходной бит истинен, если числа равны, а второй — если . Тогда возможны три варианта сигналов на выходе: (равенство),
(при ) и (при .
Объясним теперь, как собрать, скажем, схему сравнения двух -разрядных чисел. Соберем отдельно схему сравнения старших разрядов и младших разрядов. Каждая из них даст ответ в форме двух битов. Теперь из этих четырех битов надо собрать два. (Если в старших разрядах неравенство, то оно определяет результат сравнения; если старшие разряды равны, то результат сравнения определяется младшими разрядами.) Написанная в скобках фраза определяет булеву функцию с четырьмя битами на входе и двумя битами на выходе, и может быть реализована некоторой схемой фиксированного размера. Таким образом, если через обозначить размер схемы, сравнивающей -битовые числа, то получаем оценку
где — некоторая константа, зависящая от выбора базиса. Отсюда следует, что
при некотором. Всамом деле, для достаточно большого можно доказать по индукции, что
(мы должны усилить неравенство, вычтя из правой части , чтобы индуктивный шаг прошел; база индукции остается верной, если достаточно велико).
Ту же самую оценку можно объяснить и наглядно. Наша схема имеет вид иерархического дерева. На каждом уровне из двух двухбитовых сигналов получается один. Остается вспомнить, что в полном двоичном дереве число внутренних вершин (которое определяет размер схемы) на единицу меньше числа листьев. (В турнире по олимпийской системе число игр на единицу меньше числа команд, так как после каждой игры одна команда выбывает.)
Все внутренние вершины и все листья (где сравниваются два бита) представляют собой схемы ограниченного размера, откуда и вытекает оценка .
Осталось лишь сказать, что делать, если размер чисел (который мы обозначали через) не есть точная степень двойки. В этом случае можно увеличить размер до ближайшей сверху степени двойки (не более чем в два раза) и подать на старшие разряды входов нули. Оба действия приводят к увеличению размера схемы не более чем в константу раз.
Перейдем к сложению двух -разрядных чисел. (Строго говоря, тут возникает не булева функция, а функция , но все наши определения очевидно переносятся на этот случай.)
Теорема 10. Существует схема размера , осуществляющая сложение двух -битовых чисел.
Напомним смысл обозначения : нам надо построить схему сложения -битовых чисел, имеющую размер не более для некоторого и для всех.
Вспомним, как складывают числа в столбик:
Верхняя строка — биты переноса, нижняя — результат. Заметим, что каждый из битов переноса или результата определяется тремя другими битами (бит результата равен сумме двух битов слагаемых и бита переноса по модулю, а бит переноса равен , если хотя бы два из этих трех битов равны). Поэтому можно составить схему, которая вычисляет эти биты справа налево и имеет размер .
Заметим, что теорему 9 легко вывести из теоремы 10: чтобы сравнить числа и , сложим число (то есть число , в котором все единицы заменены нулями и наоборот) и число. Если в старшем разряде появится единица, то , а если нет, то . Остается заметить, что и сложение, и обращение битов в числе
требуют схем линейного размера. Таким образом, сравнение чисел сводится к вычислению бита переноса. Верно и обратное: вычисление бита переноса сводится к сравнению двух чисел (обратим в одном из слагаемых все биты).
Тем не менее конструкция, использованная при доказательстве теоремы 9, имеет некоторые преимущества. Назовем глубиной схемы максимальное число элементов на пути от входа к выходу. Если представить себе, что сигнал на выходе элемента появляется не сразу после подачи сигналов на входы, а с некоторой задержкой, то глубина схемы определяет суммарную задержку. Легко понять, что рекурсивная схема сравнения имела глубину (число уровней пропорционально логарифму размера входа), в то время как построенная только что схема сложения имеет глубину, пропорциональную (биты переноса вычисляются последовательно, справа налево). Но можно соединить эти два результата:
Теорема 11. Существует схема сложения двух -битовых чисел размера и глубины .
Как мы видели, проблема в том, что биты переноса вычисляются последовательно, а не параллельно. Если удастся их все вычислить схемой размера и глубины , то дальнейшее очевидно.
Как мы упоминали, вычисление битов переноса равносильно сравнению, так что для доказательства теоремы достаточно научиться сравнивать параллельно все "суффиксы"двух -битовых чисел и , т. е. для каждого сравнить числа и .
Вспомним, что мы делали при сравнении чисел (скажем, длины). На нижнем уровне мы сравнивали биты:
На следующем уровне мы сравнивали двузначные числа
затем четырехзначные
и, наконец, восьмизначные:
Таким образом, для суффиксов длины, , и
результаты сравнения уже есть. Для суффикса длины результат можно получить, комбинируя результат сравнения
и . После этого у нас есть информация о суффиксах всех четных длин, и соединяя ее с информацией с первого этапа, получаем сведения про все суффиксы. Например, для сравнения суффиксов длины, то есть и , мы соединяем результаты сравнения и с результатами сравнения суффиксов длины , то есть и .
В общем случае картина такая: после "сужающегося дерева" мы строим "расширяющееся"; за шагов до конца мы знаем результаты сравнения всех суффиксов, длины которых кратны . Это дерево имеет размер и глубину , что завершает доказательство.
14. Покажите, что вычитание двух -битовых чисел по модулю выполняется схемой размера и глубины . (Указание: вычитание легко сводится к сложению, если заменить нули на единицы и наоборот.)
Теперь займемся умножением. Схема умножения двух -разрядных чисел имеет входов (по для каждого множителя) и выходов для произведения.
Посмотрим, какие оценки дает обычный способ умножения чисел столбиком. В нем умножение двух -разрядных чисел сводится к сложению копий первого числа (частично замененных на нули в зависимости от цифр второго числа) со сдвигами.
Получение этих копий требует схемы размера (общее число цифр в копиях) и глубины . Сложение двух -разрядных чисел мы можем выполнить с помощью схемы размера и глубины , так что необходимые сложений можно выполнить схемой размера и глубины (если складывать сначала попарно, потом результаты снова попарно и т. д.). Оказывается, этот результат можно улучшить. Наиболее экономные способы основаны на преобразовании Фурье (о них можно прочесть в книге [1]). С их помощью, например, можно построить схему умножения -битовых чисел, имеющую размер .
Эти методы далеко выходят за рамки нашего обсуждения, но два улучшения мы приведем.
Теорема 12. Существует схема умножения двух -разрядных чисел размера и глубины .
Как мы уже говорили, умножение двух -разрядных чисел сводится к сложению таких чисел, и остается выполнить такое сложение схемой размера и глубины . Ключевым моментом здесь является сведение сложения трех чисел к сложению двух с помощью простой схемы размера и глубины. В самом деле, пусть есть три числа , и . Если мы будем складывать отдельно в каждом разряде, то в разряде может накопиться любая сумма от до, то есть в двоичной записи от до . Сформируем из младших битов этих двухбитовых сумм число , а из старших (сдвинутых влево) — число . Тогда, очевидно, . Получение цифр числа и происходит параллельно во всех разрядах и требует размера и глубины.
Теперь, если надо сложить чисел, можно разбить их на тройки и из каждых трех чисел получить по два. В следующий круг, таким образом, выйдут чисел (примерно — граничные эффекты большой роли не играют). Их снова можно сгруппировать по тройкам и т. д. С каждым уровнем число слагаемых убывает в полтора раза, так что глубина схемы будет логарифмической. Каждое преобразование трех слагаемых в два требует схемы размера
и уменьшает число слагаемых на единицу, так что потребуется
таких преобразований. Итак, эта конструкция имеет общий размер и глубину . Надо только отметить, что в конце у нас получается не одно число, а два, и их напоследок надо сложить — что мы умеем делать с глубиной и размером .
15. Докажите, что схема, вычисляющая булеву функцию от аргументов, у которой ни один аргумент не является фиктивным, имеет размер не менее и глубину не менее , где — некоторая константа, зависящая от выбранного набора элементов. (Аргумент функции называют фиктивным, если от него значение функции не зависит.)
Эта задача показывает, что если в процессе умножения двух -разрядных чисел мы суммируем слагаемых размера, то оценки для размера и для глубины, полученные при доказательстве теоремы 12, существенно улучшить нельзя.
Однако никто не обязывает нас следовать традиционному способу умножения столбиком — отказавшись от него, мы можем уменьшить размер схемы.
Теорема 13. Существует схема умножения двух -разрядных чисел размера и глубины .
Начнем с такого замечания. Вычисляя произведение двух комплексных чисел
обычным способом, мы делаем четыре умножения. Но можно обойтись и тремя с помощью такого трюка: вычислить , и , а потом найти как разность .
Аналогичный фокус можно проделать и для целых чисел. Разобьем -битовое число на две -битовые части, то есть представим его в виде . Теперь запишем произведение двух таких чисел:
Теперь видно, что достаточно найти три произведения , и , чтобы определить все три слагаемых в правой части равенства. Получается, что умножение двух -разрядных чисел сводится к трем умножениям -разрядных и к нескольким сложениям и вычитаниям. (На самом деле при умножении на
сомножители могут быть -разрядными, но это не страшно, так как обработка лишнего разряда сводится к нескольким сложениям.)
Для размера схемы, таким образом, получается рекурсивная оценка
из которой следует, что . В самом деле, для умножения -разрядных чисел требуется дерево рекурсивных вызовов глубины и степени ветвления. Заметим, что размер схемы в вершине пропорционален числу складываемых битов. При переходе от одного уровня к следующему (более близкому к корню) размер слагаемых растет вдвое, а число вершин уменьшается втрое, поэтому общее число элементов на этом уровне уменьшается в полтора раза. Таким образом, при движении по уровням от листьев к корню получается убывающая геометрическая прогрессия со знаменателем , сумма которой всего лишь втрое превосходит ее первый член. Остается заметить, что число листьев равно .
Оценка глубины также очевидна: на каждом уровне мы имеем схему сложения глубины , а число уровней есть .
На этом мы завершаем знакомство со схемами из функциональных элементов, выполняющими арифметические операции. О них можно прочесть в главе 29 учебника Кормена, Лейзерсона и Ривеста [18]
и в книге Ахо, Хопкрофта и Ульмана [1].
Рассмотрим теперь функцию "голосования"(majority).Она имеет нечетное число аргументов, и значение ее равно или в зависимости от того, какое из двух значений чаще встречается среди входов.
Теорема 14. Существует схема размера и глубины , вычисляющая функцию голосования.
На самом деле можно даже вычислить общее число единиц среди входов. Это делается рекурсивно: считаем отдельно для каждой половины, потом складываем. Получается логарифмическое число уровней. На верхнем уровне надо складывать числа размера , на следующем— размера и так до самого низа, где складываются однобитовые числа (то есть биты входа). Какой средний размер складываемых чисел? Половина вершин в дереве приходится на нижний уровень (числа длины), четверть — на следующий (числа длины) и т. д. Вспоминая, что ряд сходится, видим, что средний размер складываемых чисел есть и общий размер схемы есть . А общая глубина есть , так как на каждом из
уровней стоит схема глубины .
Заметим, что хотя функция голосования монотонна, построенная схема ее вычисления содержит немонотонные элементы (поскольку операция сложения не монотонна). Мы уже говорили, что всякую монотонную функцию можно составить из конъюнкций и дизъюнкций. Для функции голосования есть очевидный способ это сделать: написать дизъюнкцию всех конъюнкций размера (напомним, что число входов предполагается нечетным). Однако при этом получится схема экспоненциального по размера.
Теорема 15. Существует схема размера и глубины , составленная только из элементов И и ИЛИ (с двумя входами), вычисляющая функцию голосования.
Для начала заметим, что ограничение на размер является следствием ограничения на глубину, так как элементы И и ИЛИ имеют только два входа и число элементов в схеме глубины
есть .
Схема будет строиться из элементов большинства с тремя входами. (Каждый из них можно собрать из конъюнкций и дизъюнкций по формуле .) Выход схемы будет большинством из трех значений, каждое из которых есть большинство из трех значений и т. д. (рис. 2.3).
Рис. 2.3. Дерево из элементов 3-большинства
Продолжая эту конструкцию на уровнях, мы получим схему с входами. (Отметим, что эта схема не будет вычислять большинство среди своих входов — по той же причине, по которой результат непрямого голосования может отличаться от мнения большинства.) Но мы сделаем вот какую странную вещь: возьмем
равным при достаточно большом коэффициенте пропорциональности (при этом число входов такой схемы будет полиномиально зависеть от ) и напишем на входах случайно выбранные переменные из данного нам набора . (Переменные, записываемые на разных входах, выбираются независимо.) Оказывается, что с ненулевой вероятностью эта схема будет вычислять функцию большинства среди , если константа достаточно велика. Следовательно, искомая схема существует.
Обратите внимание: нам удастся доказать существование интересующей нас схемы, не предъявив ее явно. (Такое использование вероятностных методов в комбинаторных рассуждениях часто бывает полезно.)
Итак, почему же схема с положительной вероятностью вычисляет функцию большинства? Это доказывается так: рассмотрим какой-то один набор значений на входах и докажем, что на этом конкретном наборе случайная схема выдает правильный ответ с вероятностью, очень близкой к единице (равной при очень малом).
Если число настолько мало, что остается меньшим единицы даже после умножения на число возможных входов (), то получаем требуемое (каждое из событий имеет вероятность не меньше , значит их пересечение имеет вероятность не меньше ).
Итак, осталось оценить вероятность того, что случайная схема даст правильный ответ на данном входе. Пусть доля единиц среди всех входов равна. Тогда на каждый входной провод схемы подается единица с вероятностью и нуль с вероятностью (выбор случайной переменной дает единицу с вероятностью ), причем сигналы на всех входах независимы.
Если на трех входах элемента -большинства сигналы независимы, и вероятность появления единицы на каждом входе есть , то вероятность появления единицы на выходе есть . На следующих уровнях вероятность появления единицы будет равна График функции на отрезке
(рис. 2.4) показывает, что при итерациях функции дисбаланс (отклонение от середины) нарастает и последовательность стремится к краю отрезка. Надо только оценить число шагов.
Рис. 2.4. Итерируемая функция
Если вначале единицы составляют большинство из аргументов (напомним, нечетно), то их как минимум , так что . Таким образом, начальный дисбаланс составляет как минимум . А в конце нам нужно приблизиться к краю отрезка на расстояние .
Итак, нам осталось доказать такую лемму (относящуюся скорее к математическому анализу):
Лемма. Пусть последовательность задана рекуррентной формулой , где
Пусть . Тогда последовательность монотонно возрастает и приближается к на расстояние за
шагов. [Симметричное утверждение верно и при .]
Идея доказательства: посмотрим на функцию вблизи точки и у краев отрезка. В точке производная больше , поэтому удаление от растет как геометрическая прогрессия, и точка перейдет какую-то фиксированную границу (например, ) не позднее чем за
шагов. Затем потребуется шагов, чтобы дойти, скажем, до . В единице первая производная функции равна нулю, поэтому расстояние до единицы каждый раз примерно возводится в квадрат, и потому для достижения погрешности потребуется шагов (как в методе Ньютона отыскания корня). Всего получается шагов, что и требовалось.
На самом деле справедливо гораздо более сильное утверждение: существует схема размера и глубины , состоящая только из элементов И и ИЛИ, которая имеет входов и выходов и осуществляет сортировку последовательности нулей и единиц (это означает, что на выходе столько же единиц, сколько на входе, причем выходная последовательность всегда невозрастающая). Ясно, что средний бит выхода в такой ситуации реализует функцию большинства.
При кажущейся простоте формулировки единственная известная конструкция такой схемы (сортирующая сеть AKS, придуманная Айтаи, Комлошом и Сцемереди сравнительно недавно, в 1983 году) весьма сложна, и появление какой-то более простой конструкции было бы замечательным достижением.
Многие нетривиальные результаты теории алгоритмов можно переформулировать в терминах сложности каких-то булевых функций. Например, есть вероятностный алгоритм проверки простоты большого числа (применяемый в системах шифрования для проверки простоты чисел из нескольких тысяч цифр). Используя этот алгоритм, можно доказать такой факт: существует схема проверки простоты -битового числа (на вход подаются цифр, на выходе появляется единица, если число простое, и нуль, если число составное), размер которой ограничен полиномом от.
Вернемся к общим утверждениям о схемах и формулах. Мы уже говорили, что с точки зрения измерения размера схемы и формулы — это разные вещи (схемы экономичнее, так как в них одинаковые подформулы учитываются только один раз). Оказывается, что размер формулы можно связать с глубиной схемы.
Будем называть размером формулы число логических связок в ней. Мы предполагаем, что формула использует конъюнкции, дизъюнкции и отрицания, и в схемах будем использовать такие же элементы. Напомним, что размером схемы мы называли число элементов, а сложностью булевой функции — минимальный размер схемы, ее вычисляющей. Сложность функции обозначалась (точнее , где — набор разрешенных функциональных элементов, но сейчас мы договорились использовать конъюнкции, дизъюнкции и отрицания и опускаем индекс ).
Минимальный размер формулы, выражающей функцию , будем обозначать . Очевидно, . Более интересно, однако, следующее утверждение, связывающее размер схемы с глубиной формулы. Обозначим через
минимальную глубину схемы, вычисляющей функцию .
Теорема 16. Имеют место оценки и (для некоторых констант и и для всех ). Другими словами, меры сложности и отличаются не более чем в константу раз.
Первая оценка очевидна: если мы скопируем повторяющиеся фрагменты схемы, чтобы развернуть ее в дерево, то глубина не изменится. Если она равна, то в полученном дереве будет не больше элементов и соответствующая формула имеет размер не более . (Напомним, что элементами являются конъюнкции, дизъюнкции и отрицания, и потому ветвление не больше.)
То же самое можно сказать индуктивно. Пусть глубина схемы равна . Выход схемы является выходом некоторого элемента. Тогда на его входы подаются булевы функции глубины не больше . По предположению индукции их можно записать формулами размера . Таких формул максимум две, так что общий размер не превосходит .
Вторая оценка сложнее. Если мы будем преобразовывать формулу в схему естественным образом (введя вспомогательную переменную для каждой подформулы), то глубина получившейся схемы может быть близка к размеру формулы, а не к его логарифму. Например, если формула имеет вид , то у нас получится цепочка элементов И, у которых каждый следующий подвешен к левому входу предыдущего, и глубина равна . Конечно, если использовать ассоциативность конъюнкции, скобки можно переставить и получить более сбалансированное дерево глубины примерно, как и требуется. Но как выполнить такое преобразование в случае произвольной формулы?
Обозначим данную нам формулу через . Выберем у нее некоторую подформулу (как именно, мы объясним позже). Рассмотрим формулу , которая получится, если вместо
подставить (ложь), а также формулу , которая получится, если подставить. Легко понять, что равносильна формуле
Если теперь удастся заменить формулы схемами глубины не больше , то для получится схема глубины не больше.
Такое преобразование полезно, если все три формулы
имеют заметно меньший размер, чем исходная формула .
Лемма. У любой формулы размера (при достаточно больших ) есть подформула размера от до .
Доказательство. Каждая формула есть конъюнкция двух подформул, дизъюнкция двух подформул или отрицание подформулы. Начав со всей формулы, будем переходить к ее подформулам, на каждом шаге выбирая из двух подформул наибольшую. Тогда на каждом шаге размер убывает не более чем в два раза, и потому мы не можем миновать промежуток , концы которого отличаются втрое. (На самом деле тут есть небольшая неточность: размер формулы может убывать чуть быстрее, чем вдвое, так как размер формулы на единицу больше суммы размеров частей, но у нас есть запас, поскольку концы промежутка отличаются втрое, а не вдвое.) Лемма доказана.
Выбирая подформулу с помощью этой леммы, мы гарантируем, что размер всех трех формул не превосходит размера исходной формулы (подстановка нуля или единицы может только уменьшить размер формулы — некоторые части можно будет выбросить).
Применим ко всем трем формулам , и тот же прием, выделим в них подформулы среднего размера и так далее, пока мы не спустимся до формул малого размера, которые можно записать в виде схем как угодно. В итоге получится дерево с логарифмическим числом уровней, на каждом из которых стоят схемы глубины, а в листьях находятся схемы глубины .
Другими словами, индукцией по размеру формулы, выражающей некоторую функцию, легко получить оценку .
16. Определим глубину формулы как максимальное число вложенных пар скобок; для единообразия будем окружать отрицание скобками и писать вместо . Покажите, что при этом не получится ничего нового: минимальная глубина формулы, записывающей некоторую функцию , совпадает с минимальной глубиной схемы, вычисляющей.
Определение формульной сложности зависит от выбора базиса. Оказывается, что здесь (в отличие от схемной сложности) выбор базиса может изменить более чем в константу раз.
17. Объясните, почему доказательство теоремы 7 не переносится на случай формул.
Так происходит с функцией (знак обозначает сложение по модулю). Эта функция имеет формульную сложность , если сложение по модулю входит в базис. Однако в базисе И, ИЛИ, НЕ она имеет большую сложность, как доказала Б.А.Субботовская. Идея доказательства такова: если заменить случайно выбранную переменную в формуле с конъюнкциями и дизъюнкциями на случайно выбранное значение или, то формула упростится (не только эта переменная пропадет, но с некоторой вероятностью пропадут и другие). Если делать так многократно, то от формулы останется небольшая часть — с другой стороны, эта часть все равно должна реализовывать сложение оставшихся аргументов по модулю.
18. Докажите, что функция большинства может быть вычислена не только схемой, но и формулой полиномиального размера, содержащей только связки И и ИЛИ.
19. Докажите, что значения и для одной булевой функции и различных полных базисов полиномиально связаны: существует полином (зависящий от выбора базисов), для которого при всех . (Указание: использовать теорему 16.)
Исчисление высказываний
Напомним, что тавтологией мы называли пропозициональную формулу, истинную при всех значениях переменных. Оказывается, что все тавтологии можно получить из некоторого набора "аксиом" с помощью "правил вывода", которые имеют чисто синтаксический характер и никак не апеллируют к смыслу формулы, ее истинности и т. д. Эту задачу решает так называемое исчисление высказываний. В этой лекции мы перечислим аксиомы и правила вывода этого исчисления, и приведем несколько доказательств теоремы о полноте (которая утверждает, что всякая тавтология выводима в исчислении высказываний).
Исчисление высказываний (ИВ)
Каковы бы ни были формулы , следующие формулы называют аксиомами исчисления высказываний:
|
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
|
(8) |
|
(9) |
|
(10) |
|
(11) |
Как говорят, мы имеем здесь одиннадцать "схем аксиом"; из каждой схемы можно получить различные конкретные аксиомы, заменяя входящие в нее буквы на пропозициональные формулы.
Единственным правилом вывода исчисления высказываний является правило со средневековым названием "modus ponens" (MP). Это правило разрешает получить (вывести) из формул и формулу .
Выводом в исчислении высказываний называется конечная последовательность формул, каждая из которых есть аксиома или получается из предыдущих по правилу modus ponens.
Вот пример вывода (в нем первая формула является частным случаем схемы (1), вторая — схемы (2), а последняя получается из двух предыдущих по правилу modus ponens):
Пропозициональная формула называется выводимой в исчислении высказываний, или теоремой исчисления высказываний, если существует вывод, в котором последняя формула равна . Такой вывод называют выводом формулы . (В принципе можно было бы и не требовать, чтобы формула была последней — все дальнейшие формулы можно просто вычеркнуть.)
Как мы уже говорили, в исчислении высказываний выводятся все тавтологии и только они. Обычно это утверждение разбивают на две части: простую и сложную. Начнем с простой:
Теорема 17 (О корректности ИВ). Всякая теорема исчисления высказываний есть тавтология.
Несложно проверить, что все аксиомы — тавтологии. Для примера проделаем это для самой длинной аксиомы (точнее, схемы аксиом) — для второй. В каком случае формула
(где — некоторые формулы) могла бы быть ложной? Для этого посылка должна быть истинной, а заключение — ложным. Чтобы заключение было ложным, формула должна быть истинной, а формула — ложной. Последнее означает, что истинна, а
ложна. Таким образом, мы знаем, что , и истинны. Отсюда следует, что и истинны, и потому истинна — противоречие. Значит, наша формула не бывает ложной.
Корректность правила MP также очевидна: если формулы
и всегда истинны, то по определению импликации формула также всегда истинна. Таким образом, все формулы, входящие в выводы (все теоремы) являются тавтологиями.
Гораздо сложнее доказать обратное утверждение.
Теорема 18 (О полноте ИВ). Всякая тавтология есть теорема исчисления высказываний.
Мы предложим несколько альтернативных доказательств этой теоремы. Но прежде всего мы должны приобрести некоторый опыт построения выводов и использования аксиом.
Лемма 1. Какова бы ни была формула , формула является теоремой.
Докажем лемму, предъявив вывод формулы в исчислении высказываний.
[аксиома 2 при , , ]; [аксиома 1]; [из 1 и 2 по правилу MP]; [аксиома 1]; [из 3 и 4 по правилу MP].
Как видно, вывод даже такой простой тавтологии, как , требует некоторой изобретательности. Мы облегчим себе жизнь, доказав некоторое общее утверждение о выводимости.
Часто мы рассуждаем так: предполагаем, что выполнено какое-то утверждение , и выводим различные следствия. После того как другое утверждение доказано, мы вспоминаем, что использовали предположение , и заключаем, что мы доказали утверждение . Следующая лемма, называемая иногда "леммой о дедукции", показывает, что этот подход правомерен и для исчисления высказываний.
Пусть — некоторое множество формул. Выводом из называется конечная последовательность формул, каждая из которых является аксиомой, принадлежит или получается из предыдущих по правилу MP. (Другими словами, мы как бы добавляем формулы из к аксиомам исчисления высказываний — именно как формулы, а не как схемы аксиом.) Формула выводима из , если существует вывод из , в котором она является последней формулой. В этом случае мы пишем . Если пусто, то речь идет о выводимости в исчислении высказываний, и вместо пишут просто .
Лемма 2 (о дедукции). Пусть — множество формул. Тогда тогда и только тогда, когда .
В одну сторону утверждение почти очевидно: пусть . Тогда и . (Для краткости мы опускаем фигурные скобки и заменяем знак объединения запятой.) По определению , откуда по MP получаем .
Пусть теперь . Нам надо построить вывод формулы из . Возьмем вывод формулы из . Припишем ко всем формулам этого вывода слева посылку : Эта последовательность оканчивается на . Сама по себе она не будет выводом из , но из нее можно получить такой вывод, добавив недостающие формулы, и тем самым доказать лемму о дедукции.
Будем добавлять эти формулы, двигаясь слева направо. Пусть мы подошли к формуле . По предположению формула либо совпадает с , либо принадлежит , либо является аксиомой, либо получается из двух предыдущих по правилу MP. Рассмотрим все эти случаи по очереди.
(1) Если есть , то очередная формула имеет вид . По лемме 1 она выводима, так что перед ней мы добавляем ее вывод.
(2) Пусть принадлежит . Тогда мы вставляем формулы и (аксиома 1). Применение правила MP к этим формулам дает , что и требовалось.
(3) Те же формулы можно добавить, если является аксиомой исчисления высказываний.
(4) Пусть, наконец, формула получается из двух предыдущих формул по правилу MP. Это значит, что в исходном выводе ей предшествовали формулы и . Тогда в новой последовательности (с добавленной посылкой ) уже были формулы и . Поэтому мы можем продолжить наш -вывод, написав формулы
(аксиома 2);
(modus ponens);
(modus ponens).
Итак, во всех четырех случаях мы научились дополнять последовательность до вывода из , так что лемма о дедукции доказана.
20. Докажите, что для любых формул формула выводима в исчислении высказываний. (Указание: используйте лемму о дедукции и тот факт, что .)
21. Докажите, что если и , то . (Это свойство иногда называют "правилом сечения" (cut);говорят, что формула
"отсекается" или "высекается". Сходные правила играют центральную роль в теории доказательств, где формулируется и доказывается "теорема об устранении сечения" для различных логических систем.)
22. Добавим к исчислению высказываний, помимо правила modus ponens, еще одно правило, называемое правилом подстановки. Оно разрешает заменить в выведенной формуле все переменные на произвольные формулы (естественно, вхождения одной переменной должны заменяться на одну и ту же формулу).
Покажите, что после добавления такого правила класс выводимых формул не изменится, но теорема о дедукции перестанет быть верной.
Заметим, что мы пока что использовали только две первые аксиомы исчисления высказываний. Видно, кстати, что они специально подобраны так, чтобы доказательство леммы о дедукции прошло.
Другие аксиомы описывают свойства логических связок. Аксиомы
и говорят, какие следствия можно вывести из конъюнкции ( и ). Напротив, аксиома 5 говорит, как можно вывести конъюнкцию. Из нее легко следует такое правило: если и , то (применяем эту аксиому и дважды правило MP). Часто подобные правила записывают так: (над чертой пишут "посылки" правила, а снизу — его "заключение", вытекающее из посылок).
23. Докажите, что формула , так же как и обратная к ней формула (в которой посылка и заключение переставлены), являются теоремами исчисления высказываний. Докажите аналогичное утверждение про формулы и .
Аксиомы 6-7 позволяют утверждать, что и . Аксиома 8 обеспечивает такое правило: Оно соответствует такой схеме рассуждения: "Пусть выполнено . Разберем два случая. Если выполнено , то и потому . Если выполнено , то и потому . В обоих случаях верно . Значит, влечет ."
Обоснование: дважды воспользуемся леммой о дедукции, получив и , а затем дважды применим правило MP к этим формулам и аксиоме . Получив формулу , опять применим правило MP к ней и формуле .
24. Докажите, что следующие формулы, а также обратные к ним (меняем местами посылку и заключение) являются теоремами исчисления высказываний:
У нас остались еще три аксиомы, касающиеся отрицания. Аксиома 9 гарантирует, что из противоречивого набора посылок можно вывести что угодно: если и , то для любого . Аксиома 10, напротив, объясняет, как можно вывести отрицание некоторой формулы : надо допустить и вывести два противоположных заключения и . Точнее говоря, имеет место такое правило: (в самом деле, дважды применяем лемму о дедукции, а затем правило MP с аксиомой 10).
Аксиомы 9 и 10 позволяют вывести некоторые логические законы, связанные с отрицанием.
Докажем, например, что (для любых формул и ) формула ("закон контрапозиции") является теоремой исчисления высказываний. В самом деле, по лемме о дедукции достаточно установить, что
Для этого, в свою очередь, достаточно вывести из посылок какую-либо формулу и ее отрицание (в данном случае формулы и ).
25. Выведите формулы и с помощью аналогичных рассуждений.
Последняя аксиома, называемая "законом исключенного третьего", и иногда читаемая как "третьего не дано" (tertium non datur в латинском оригинале), вызвала в первой половине века большое количество споров. (См. раздел об интуиционистской логике,в которой этой аксиомы нет.)
Из нее можно вывести закон "снятия двойного отрицания", имеющий вид . В самом деле, достаточно показать, что . По правилу разбора случаев, достаточно установить, что (это очевидно) и что (а это верно, так как из двух противоречащих друг другу формул выводится что угодно с помощью аксиомы 8).
26. Докажите, что формула является теоремой исчисления высказываний. (Указание: используйте закон исключенного третьего.)
27. Исключим из числа аксиом исчисления высказываний закон исключенного третьего, заменив его на закон снятия двойного отрицания. Покажите, что от этого класс выводимых формул не изменится.
28. Докажите, что при наличии аксиомы исключенного третьего (11) аксиома (10) является лишней — ее (точнее следовало бы сказать: любой частный случай этой схемы аксиом) можно вывести из остальных аксиом.
Теперь уже можно доказать теорему о полноте: всякая тавтология выводима в исчислении высказываний. Идея доказательства состоит в разборе случаев. Поясним ее на примере. Пусть — произвольная формула, содержащая переменные . Предположим, что истинна, когда все три переменные истинны. Тогда, как мы докажем, Вообще каждой строке таблицы истинности для формулы
соответствует утверждение о выводимости. Например, если
ложна, когда и ложны, а истинно, то
Если формула является тавтологией, то окажется, что она выводима из всех восьми возможных вариантов посылок.
Пользуясь законом исключенного третьего, можно постепенно избавляться от посылок. Например, из и
можно получить , то есть (поскольку является аксиомой).
Проведем это рассуждение подробно. Для начала докажем такую лемму:
Лемма 3. Для произвольных формул и
Эта лемма говорит, что если принять в качестве гипотез истинность или ложность формул и , являющихся частями конъюнкции, дизъюнкции или импликации, то можно будет доказать или опровергнуть всю формулу (в зависимости от того, истинна она или ложна). Последняя часть содержит аналогичное утверждение про отрицание.
После предпринятой нами тренировки доказать эти утверждения несложно. Например, убедимся, что . Для этого достаточно вывести два противоположных утверждения из — ими будут утверждения и .
Проверим еще одно утверждение: . Нам надо вывести два противоположных утверждения из . Покажем, что из следует все, что угодно. По правилу разбора случаев достаточно убедиться, что из и из следует все, что угодно — но это мы знаем.
Утверждения, касающиеся импликации, просты: в самом деле, мы знаем, что благодаря аксиоме 1, а благодаря аксиоме 9.
Остальные утверждения леммы столь же просты.
Теперь мы можем сформулировать утверждение о разборе случаев для произвольной формулы.
Лемма 4. Пусть — произвольная формула, составленная из переменных . Тогда для каждой строки таблицы истинности формулы имеет место соответствующее утверждение о выводимости: если , и значение формулы есть при , то где обозначает при и при (напомним, что
обозначает истину, а — ложь).
Лемма очевидно доказывается индукцией по построению формулы . Мы имеем посылки, утверждающие истинность или ложность переменных, и для всех подформул (начиная с переменных и идя ко всей формуле) выводим их или их отрицания с помощью леммы 3.
Если формула является тавтологией, то из всех вариантов посылок выводится именно она, а не ее отрицание. Тогда правило разбора случаев и закон исключенного третьего позволяют избавиться от посылок: сгруппируем их в пары, отличающиеся в позиции (в одном наборе посылок стоит , в другом ), по правилу разбора случаев заменим их на посылку , которую можно выбросить (она является аксиомой).Сделав так для всех пар, получим выводов, в посылках которых нет ; повторим этот процесс с посылками ,
и т. д. В конце концов мы убедимся, что формула
выводима без посылок, как и утверждает теорема о полноте.
Второе доказательство теоремы о полноте
Это доказательство, в отличие от предыдущего, обобщается на более сложные случаи (исчисление предикатов, интуиционистское исчисление высказываний).
Начнем с такого определения: множество формул
называется совместным,если существует набор значений переменных, при которых все формулы из истинны. Заметим, что формула является тавтологией тогда и только тогда, когда множество, состоящее из единственной формулы , не является совместным. Для случая одной формулы есть специальный термин: формула выполнима, если существуют значения переменных, при которых она истинна, то есть если множество совместно. Тавтологии — это формулы, отрицания которых не выполнимы.
Множество формул называется противоречивым, если из него одновременно выводятся формулы и . Мы знаем, что в этом случае из него выводятся вообще все формулы. (В противном случае называется непротиворечивым.)
Теорема 19 (корректность исчисления высказываний, вторая форма).
Всякое совместное множество формул непротиворечиво.
В самом деле, пусть совместное множество противоречиво. Так как оно совместно, существуют значения переменных, при которых все формулы из истинны. С другой стороны, из выводится некоторая формула и ее отрицание. Может ли так быть?
Оказывается, что нет. Мы уже видели, что всякая выводимая формула истинна при всех значениях переменных (является тавтологией). Справедливо и несколько более общее утверждение: если и при некоторых значениях переменных все формулы из истинны, то и формула истинна при этих значениях переменных. (Как и раньше, это легко доказывается индукцией по построению вывода из .)
В нашей ситуации это приводит к тому, что на выполняющем наборе значений переменных для должны быть истинны обе формулы и , что, разумеется, невозможно.
Мы называем это утверждение другой формой теоремы о корректности исчисления высказываний, поскольку из него формально можно вывести, что всякая теорема является тавтологией: если — теорема, то множество противоречиво (из него выводятся и ), потому несовместно, значит, всегда ложна, поэтому всегда истинна.
Теорема 20 (полнота исчисления высказываний, вторая форма). Всякое непротиворечивое множество совместно.
Нам дано непротиворечивое множество , а надо найти такие значения переменных, при которых все формулы из
истинны. (Вообще говоря, множество может быть бесконечно и содержать бесконечное число разных переменных.)
Пусть есть какая-то переменная , встречающаяся в формулах из семейства . Нам надо решить, сделать ли ее истинной или ложной. Если оказалось так, что из выводится формула , то выбора нет: она обязана быть истинной в тех наборах, где формулы из истинны (как мы видели при доказательстве корректности). По тем же причинам, если из выводится , то в выполняющем наборе переменная обязательно будет ложной.
Если оказалось так, что для любой переменной либо она сама, либо ее отрицание выводятся из , то выполняющий набор значений определен однозначно, и надо только проверить, что он действительно будет выполняющим. А если для каких-то переменных нельзя вывести ни их, ни их отрицание, то мы пополним наш набор так, чтобы они, как теперь модно говорить, "определились".
Проведем это рассуждение подробно. Рассмотрим все переменные, входящие в какие-либо формулы из множества ; обозначим множество этих переменных через . Зафиксируем это множество и до конца доказательства теоремы о полноте будем рассматривать только формулы с переменными из множества , не оговаривая этого особо.
Назовем непротиворечивое множество полным, если для любой формулы имеет место либо , либо (одновременно этого быть не может, так как непротиворечиво).
Утверждение теоремы о полноте очевидно следует из двух лемм:
Лемма 1. Всякое непротиворечивое множество
содержится в непротиворечивом полном множестве .
Лемма 2. Для всякого непротиворечивого полного множества существует набор значений переменных (из , напомним), при котором все формулы из истинны.
Доказательство леммы 1. Основную роль здесь играет такое утверждение: если — непротиворечивое множество, а — произвольная формула, то хотя бы одно из множеств и
непротиворечиво. В самом деле, если оба множества и противоречивы, то и , но множество предполагалось непротиворечивым.
Если множество переменных конечно или счетно, то доказательство леммы легко завершить: множество всех формул тогда счетно, и просматривая их по очереди, мы можем добавлять к либо саму формулу, либо ее отрицание, сохраняя непротиворечивость. Получится, очевидно, полное множество. Чуть менее очевидна его непротиворечивость: оно было непротиворечиво на каждом шаге, но почему предельное множество (объединение возрастающей последовательности) будет непротиворечиво? Дело в том, что в выводе двух противоречащих друг другу формул может быть задействовано только конечное число формул из (по определению выводимости: вывод есть конечная последовательность формул). Поэтому все эти формулы должны появиться на некотором конечном шаге конструкции, а это невозможно (на всех шагах множество непротиворечиво).
Для случая произвольного набора переменных рассуждение можно завершить ссылкой на лемму Цорна: рассмотрим частично упорядоченное множество, элементами которого будут непротиворечивые множества формул, а порядком — отношение "быть подмножеством". Рассуждение предыдущего абзаца показывает, что всякая цепь в этом множестве имеет верхнюю границу (объединение линейно упорядоченного по включению семейства непротиворечивых множеств является непротиворечивым множеством). Следовательно, для любого непротиворечивого множества найдется содержащее его максимальное непротиворечивое множество. А оно обязано быть полным (иначе его можно расширить, добавив или ).
Лемма 1 доказана.
Доказательство леммы 2. Пусть — непротиворечивое полное множество. Тогда для каждой переменной (из множества ) ровно одна из формул и выводима из . Если первая, будем считать переменную истинной, если вторая — ложной. Тем самым появляется некоторый набор значений переменных, и надо только проверить, что любая формула из при таких значениях переменных истинна. Это делается так: индукцией по построению формулы мы доказываем, что
Базис индукции (когда — переменная) обеспечивается определением истинности переменных. Для шага индукции используется та же лемма, что и при доказательстве полноты с помощью разбора случаев. Пусть, например, имеет вид . Тогда есть четыре возможности для истинности и . В одном из них (когда и истинны на ) по предположению индукции мы имеем и , откуда , то есть . В другом ( истинна, ложна) предположение индукции дает и , откуда , то есть . Аналогично разбираются и все остальные случаи и логические связки. Лемма 2 доказана, и тем самым завершено доказательство теоремы 20.
Мы доказали, что всякое непротиворечивое множество формул совместно. Отсюда легко следует, что всякая тавтология является теоремой. В самом деле, если — тавтология, то множество несовместно, поэтому из
выводится противоречие, поэтому , и по закону снятия двойного отрицания .
Кроме того, теорема о полноте во второй формулировке имеет такое очевидное следствие:
Теорема 21 (теорема компактности для исчисления высказываний).
Пусть — множество формул, всякое конечное подмножество которого совместно. Тогда и все множество совместно.
Как мы знаем, несовместность равносильна противоречивости, а вывод противоречия по определению может использовать лишь конечное число формул.
Поскольку в формулировке теоремы компактности нет упоминания об исчислении высказываний (речь идет лишь об истинности формул, а не о выводимости), возникает вопрос, нельзя ли ее доказать непосредственно.
29. Дайте прямое доказательство теоремы компактности для случая, когда переменных в множестве конечное число. (Указание: в этом случае любое несовместное множество имеет несовместное подмножество мощности не больше .)
Для случая счетного числа переменных можно воспользоваться компактностью (в топологическом смысле слова) канторовского пространства. Его элементами являются бесконечные последовательности нулей и единиц. Если две последовательности отличаются в -й позиции, а все предыдущие члены совпадают, то расстояние между ними считается равным . Это метрическое пространство компактно.
Пусть содержит счетное число переменных. Последовательность значений переменных будем рассматривать как точку канторовского пространства; формуле соответствует область, состоящая из точек, где формула истинна. Поскольку формула содержит лишь конечное число переменных, эта область является замкнутым и открытым множеством одновременно. Пусть имеется множество формул, любое конечное подмножество которого совместно. Это значит, что соответствующие формулам подмножества канторовского пространства образуют, как говорят, центрированную систему (любое конечное их число имеет общую точку). А в компактном пространстве любое центрированное семейство замкнутых множеств имеет общую точку (иначе их дополнения образуют открытое покрытие, у которого нет конечного подпокрытия). Эта их общая точка и будет набором значений, на котором все формулы истинны.
То же самое рассуждение годится и для несчетного множества переменных, но тогда возникает несчетное произведение двухточечных пространств, которое является топологическим пространством (но не метрическим); надо заметить, что это пространство компактно по теореме Тихонова, после чего наше рассуждение проходит.
Для счетного набора переменных теорема компактности связана с так называемой леммой Кенига. Конечные последовательности нулей и единиц (включая пустую последовательность) мы называем двоичными словами. Двоичным деревом мы называем множество двоичных слов, которое вместе со всяким словом содержит все его начала (начальные отрезки). Бесконечной ветвью двоичного дерева мы называем бесконечную последовательность нулей и единиц, любое конечное начало которой принадлежит .
Теорема 22 (лемма Кенига).
Любое бесконечное дерево имеет бесконечную ветвь.
Говоря о бесконечности дерева, мы имеем в виду, что соответствующее множество бесконечно. Отсюда следует, что оно содержит слова сколь угодно большой длины. Пусть — счетное множество переменных, которые принимают значения или . Для каждого рассмотрим формулу , которая утверждает, что слово принадлежит дереву (это возможно, так как любая булева функция выразима формулой). Поскольку — дерево, влечет при . Любое конечное множество формул вида равносильно, таким образом, одной формуле с максимальным и потому совместно. Следовательно, и множество всех формул совместно, и выполняющий набор определяет бесконечную ветвь.
(Конечно, мы "бьем из пушек по воробьям": достаточно индукцией по строить слово длины , которое имеет бесконечное число продолжений в дереве .)
Обычно утверждение леммы Кенига формулируют так: если колония бактерий, возникшая из одной бактерии, никогда не вымирает полностью, то существует бесконечная последовательность бактерий, каждая следующая из которых получается при делении предыдущей. [Аналогичная формулировка про людей осложняется возможностью клонирования, наличием двух полов и проблемами политкорректности.]
Интуиционистская пропозициональная логика
Исключим из числа аксиом закон исключенного третьего . Полученное исчисление называется интуиционистским исчислением высказываний. (Обычное исчисление высказываний называют классическим, чтобы избежать путаницы при его сравнении с интуиционистским. Вообще математические рассуждения, опирающиеся на аксиому исключенного третьего, называют "классическими", а избегающие ее — "интуиционистскими".)
Конечно, сразу же возникают естественные вопросы. Почему именно эта аксиома вызывает сомнения? Вообще-то аксиом много, и можно было бы исключить любую и смотреть, что получится без нее — но ясно, что скорее всего получится что-то странное. Как понять, какие формулы останутся теоремами без закона исключенного третьего? Раньше у исчисления высказываний была "сверхзадача" — вывести все тавтологии и только их, а теперь?
Интуиционистская логика возникла как попытка (сделанная Гейтингом) формализовать (пусть частично) методы рассуждений, практикуемые в "интуиционистской математике". Голландский математик Брауэр широко известен как автор классической (во всех смыслах) теоремы Брауэра о неподвижной точке (она утверждает, что любое непрерывное отображение многомерного шара в себя имеет неподвижную точку). Но одновременно он создал целую школу в области оснований математики — математический интуиционизм. Отчего, спрашивал Брауэр, в теории множеств возникли парадоксы? Можно считать, что это оттого, что мы стали рассуждать о каких-то уж очень абстрактных объектах, которые существуют лишь в нашей (порой противоречивой) фантазии, так что следует проявлять осторожность и не подходить к опасной черте. Но Брауэр пошел дальше, говоря, что противоречия лишь симптом болезни, а надо устранить ее причину. Причину он видел в том, что математические рассуждения и понятия утратили интуитивный смысл, и нужно вернуться к основам и пересмотреть смысл самих логических связок.
Что мы имеем в виду (или должны иметь в виду), говоря о том, что мы установили, что " или "? Это значит, по Брауэру, что либо мы установили , либо установили . Когда мы устанавливаем, что " и ", это значит, что мы установили и , и . "Если , то " означает, что мы располагаем каким-то общим рассуждением, которое позволит нам установить , как только кто-то установит нам . Отрицание означает, что мы располагаем рассуждением, которое приводит к противоречию предположение, что установлено. (Как с точки зрения интуиционизма, так и с классической точки зрения, во всех смыслах эквивалентно , где — заведомо ложное утверждение. Можно было бы вообще не использовать отрицания, а иметь константу — это не очень привычно, но технически удобно.)
Интуиционизм отвергает идею о том, что все высказывания делятся на истинные и ложные (пусть неизвестным нам образом). С этой точки зрения закон исключенного третьего совершенно безоснователен: означает, что для произвольного утверждения мы можем установить либо , либо его отрицание (то есть объяснить, почему в принципе не может быть установлено) — а почему, собственно?
Обычно, говоря об интуиционизме, приводят следующий пример рассуждения, неприемлемого с точки зрения интуиционизма. Докажем, что существуют иррациональные числа и , для которых рационально. В самом деле, рассмотрим два случая. Если рационально, то можно положить . Если же иррационально, то положим и ; легко проверить, что . Интуиционист скажет, что это рассуждение некорректно: доказать существование чего-то означает построить этот объект, а мы так и не построили чисел и , поскольку не установили, какой из двух случаев имеет место. (Заметим в скобках, что специалисты по алгебраической теории чисел знают, что
иррационально и даже трансцендентно. Кроме того, не нужно быть специалистом, чтобы заметить, что можно положить и .) Этот пример можно критиковать и с другой точки зрения, говоря, что само понятие действительного числа не является интуитивно ясным и требует обоснования.
Вообще интуиция — дело тонкое: если долго рассуждать, скажем, о действительных числах, то начинает казаться, что они в каком-то смысле существуют независимо от наших рассуждений. Именно поэтому психологически оправдан вопрос о том, скажем, как обстоят дела с континуум-гипотезой "на самом деле": существует ли несчетное множество действительных чисел, не равномощное всем действительным числам, или не существует?
Мы не будем говорить о философских предпосылках интуиционизма подробно. Вкратце упрощенная история вопроса такова. Брауэр наметил планы переустройства математики на интуиционистских принципах и отстаивал их настолько горячо, что однажды Гильберт в раздражении заметил: отменить закон исключенного третьего — это все равно что отнять у астрономов телескоп или запретить боксерам пользоваться кулаками. Но, продолжал он, никто не может изгнать математиков из рая, который создал Кантор.
В планы Брауэра не входила формализация интуиционистской логики и математики, скорее наоборот. Тем не менее анализ принципов интуиционизма пошел именно по этому пути, когда Гейтинг стал изучать пропозициональную логику без закона исключенного третьего. Различные спорные интуиционистские принципы стали предметом изучения с точки зрения формальной логики; были построены интуиционистские варианты формальной арифметики, теории множеств, логики предикатов, а также генценовские варианты интуиционистских систем. Были предложены различные интерпретации интуиционистской логики. Колмогоров предложил трактовать ее как "логику задач", Клини предложил понятие "реализуемости", использующее теорию алгоритмов для толкования формул; были предложены топологические модели для интуиционистской логики и т. д. В СССР знамя Брауэра подхватила школа Маркова, написав на нем, впрочем, "конструктивизм" вместо идеологически сомнительного "интуиционионизма" и более последовательно ограничиваясь конечными объектами. Крипке в 1960-е годы предложил некоторую семантику (определение истинности), согласованную с интуиционистским исчислением высказываний и весьма естественную (даже странно, что ее не придумали раньше); замечательным образом оказалось, что она в некотором смысле близка к методу форсинга, который примерно в это же время придумал Коэн, чтобы доказать независимость аксиомы выбора и континуум-гипотезы в теории множеств.
Возвращаясь к интуиционистскому исчислению высказываний, приведем несколько выводимых формул.
Чтобы понять смысл формулы , вспомним, что отрицание можно толковать как , где — заведомо ложное утверждение. Эта формула говорит, что если из следует , а из следует заведомо ложное утверждение, то из следует заведомо ложное утверждение (частный случай транзитивности отношения следования). Вывод ее не использует закона исключенного третьего. В самом деле, по лемме о дедукции (доказательство которой остается тем же и для интуиционистского исчисления высказываний) достаточно доказать, что из и выводится . Для этого, в свою очередь, достаточно доказать, что из , и
выводятся две противоречащие друг другу формулы (что очевидно: это формулы
и ). Чтобы вывести формулу , надо показать, что из
выводится , для чего достаточно из и
вывести две противоречащие друг другу формулы (что тривиально — годятся сами формулы и ). Формула получается из двух предыдущих: положим равным в первой из них. Формула , с другой стороны, есть частный случай второй формулы, так что три отрицания равносильны одному. Коммутативность и ассоциативность операций
и , так же как и два свойства дистрибутивности, не опирались на закон исключенного третьего. По-прежнему равносильно (импликации в обе стороны, связывающие эти формулы, выводимы в интуиционистском исчислении высказываний). Взяв в качестве в предыдущих формулах, мы видим, что один из законов Де Моргана (а именно, закон ) не опирается на закон исключенного третьего (что легко проверить и непосредственно). Формулу сохранившийся закон де Моргана позволяет переписать в виде , и нужно лишь вывести из две противоположные формулы, что очевидно.
31. Провести подробно доказательство выводимости в интуиционистском исчислении высказываний всех перечисленных формул.
С другой стороны, многие законы классической логики перестают быть выводимыми без закона исключенного третьего. Таковы, например, формулы
Мы пишем здесь переменные и , а не произвольные формулы, поскольку результат подстановки некоторых формул вместо и может быть выводимой формулой. Например, если вместо в первую из перечисленных формул подставить формулу , то получится выводимая формула .
Довольно ясно, что эти формулы не согласуются с интуиционистским подходом. Например, в предпоследней формуле говорится, что если мы опровергли предположение , то мы можем указать на одно из предположений и и предъявить его опровержение. Вряд ли такой переход можно считать обоснованным с интуиционистской точки зрения. Но, разумеется, формальный вопрос о выводимости требует формального ответа.
Начнем с закона исключенного третьего.
Теорема 24.Формула не выводима в интуиционистской логике.
В классической логике каждая пропозициональная переменная может принимать два значения — истина (И) и ложь (Л). В зависимости от значений переменных каждой формуле также приписывается значение И или Л. Расширим множество истинностных значений, добавив новое значение Н (если угодно, можно считать это сокращением слова "неизвестно"). Мы отождествляли И с единицей, а Л — с нулем, так что логично отождествить Н с числом .
Мы докажем, что интуиционистски выводимые формулы всегда принимают значение И, а формула не такова, и потому не выводима.
Чтобы определить значения формул в трехзначной логике, необходимо задать таблицы истинности для всех пропозициональных связок. Конъюнкцию определим как минимум из двух значений (так что, например, , а ), а дизъюнкцию — как максимум. Отрицание действует так: , , . (Последнее может показаться странным: почему бы не считать, что ? Оказывается, так нельзя — например, потому, что тогда формула , которая выводима в интуиционистской логике, будет иметь значение при .)
Сложнее всего определение истинности для импликации. Мы полагаем, что
для любого истинностного значения , а также что
Назовем формулу -тавтологией, если она принимает значение И при любых значениях переменных из множества . Теперь надо проверить две вещи: (1) все аксиомы интуиционистского исчисления являются -тавтологиями; (2) если посылка импликации и вся импликация являются - тавтологиями, то и заключение тоже является -тавтологией. Второе сразу ясно из определения импликации, а первое надо аккуратно проверять, составив таблицы для всех аксиом. Мы не будем этого подробно делать, поскольку это чисто механическая проверка и поскольку чуть позже мы сможем вывести это из более общего утверждения.
Следовательно, всякая интуиционистски выводимая формула является -тавтологией. Теперь заметим, что формула
принимает значение Н при и потому не является -тавтологией — значит, невыводима.
32. Покажите, что всякая -тавтология является тавтологией в обычном смысле.
Использованный нами прием годится не всегда. Например, интуиционистски невыводимая формула
является -тавтологией, поскольку (согласно нашему определению) формула может принимать только значения И и Л.
33. Какие из перечисленных нами интуиционистски невыводимых формул являются -тавтологиями?
Более общий способ установления недоказуемости (невыводимости) различных формул доставляют шкалы Крипке (или модели Крипке, как еще говорят).
Чтобы задать шкалу Крипке, нужно:
указать частично упорядоченное множество , называемое множеством миров; для каждого мира указать, какие из пропозициональных переменных считаются истинными в этом мире (остальные переменные считаются ложными в этом мире). Если переменная истинна в мире , мы пишем .
При этом требуется, чтобы было выполнено следующее: если и , то (область истинности любой переменной наследственна вверх).
Когда шкала задана, можно определить истинность любой формулы (в данном мире) индукцией по построению формулы. Мы пишем , если в мире истинна формула . Вот индуктивное определение:
, если и ; , если или ; , если в любом мире , в котором истинна формула , истинна также и формула ; , если ни в каком мире
формула не является истинной.
Формула, не являющаяся истинной (в данном мире), называется ложной (в нем).
Определение истинности для отрицания, как легко проверить, согласовано с пониманием как , где — тождественно ложная (во всех мирах) формула.
Именно определение импликации (и отрицания) использует порядок на множестве миров. Если формула содержит лишь конъюнкции и дизъюнкции, то ее истинность по существу определяется отдельно в каждом мире.
Индукцией по построению формулы легко проверить, что если она истинна в каком-то мире, то истинна и во всех больших мирах. В самом деле, пересечение и объединение двух наследственных вверх множеств также обладает этим свойством, так что для случая конъюнкции и дизъюнкции можно сослаться на предположение индукции. А для импликации даже и этого не нужно, достаточно посмотреть на определение.
Философский смысл шкал Крипке иногда объясняют так. Пусть
есть множество возможных состояний цивилизации (миров);
означает, что мир может получиться из мира в результате развития цивилизации. Утверждение означает, что в мире установлено, что высказывание истинно. (При этом оно останется истинным и при дальнейшем развитии цивилизации.) Истинность в мире означает, что ни при каком развитии цивилизации из состояния высказывание
не станет истинным.
Определение истинности отрицания в шкалах Крипке предвосхитил Пушкин, когда писал "нет правды на земле. Но правды нет и выше," (Моцарт и Сальери).
34.Во что превращается определение истинности в шкале Крипке, если в ней только один мир? если в ней никакие два мира не сравнимы?
Теорема 25 (корректность интуиционистского исчисления высказываний относительно шкал Крипке).
Формула, выводимая в интуиционистском исчислении высказываний, истинна во всех мирах всех шкал Крипке.
Надо проверить, что все аксиомы истинны во всех мирах, а также что правило modus ponens сохраняет это свойство. Второе очевидно: если истинна во всех мирах и истинна во всех мирах, то по определению истинности импликации будет истинна во всех мирах.
Осталось проверить истинность всех аксиом. Чтобы установить, что импликация истинна во всех мирах, надо проверить, что в тех мирах, где истинна формула , истинна и формула . Для первой аксиомы : если формула истинна в некотором мире, то в силу монотонности она истинна и выше, так что также истинна.
Проверим вторую аксиому . Пусть . Надо убедиться, что . Это означает, что если и , то . Последнее, в свою очередь, значит, что если и , то . Но в силу монотонности мы знаем, что и . Поэтому из следует , , и, наконец, , что и требовалось.
Остальные аксиомы проверяются еще проще.
Таким образом, чтобы доказать, что некоторая формула не выводима в интуиционистском исчислении высказываний, достаточно предъявить шкалу Крипке, в одном из миров которой она ложна.
35. Покажите, что в этом случае есть шкала, в которой среди миров есть наименьший и в нем формула ложна.
Для формулы такая шкала строится легко. Возьмем два мира, первый меньше второго. Пусть истинна только во втором мире. Тогда не будет истинна нигде, а будет истинна только во втором мире.
На самом деле это доказательство в сущности совпадает с приведенным выше (с трехзначной логикой). В самом деле, в этой шкале для формулы есть три возможности: она истинна в обоих мирах, она истинна только во втором мире, или она не истинна ни в одном из миров. Эти три возможности соответствуют трем значениям И, Н и Л в рассмотренной нами трехзначной интерпретации. Легко проверить, что таблицы операций как раз соответствуют определению истинности в модели Крипке.
Теперь мы можем установить, что все перечисленные выше формулы невыводимы в интуиционистском исчислении высказываний. Для формулы годится та же самая шкала ( истинно только в большем мире). Она же годится для формулы , если истинно в обоих мирах, а — только в большем. Для трех оставшихся формул можно рассмотреть шкалы с тремя мирами: начальным миром , из которого можно попасть в и в ; миры и не сравнимы. Если формула истинна только в мире , то формула истинна только в мире , a истинна только в мире , так что в мире обе формулы и ложны и дизъюнкция ложна. Чтобы построить контрмодель для формулы , будем считать, что истинна только в мире , а истинна только в мире . Та же шкала годится и для формулы .
Оказывается, что этот прием универсален, как показывает следующая теорема.
Теорема 26 (полноты интуиционистского исчисления высказываний относительно шкал Крипке).
Для любой невыводимой в интуиционистском исчислении формулы можно подобрать шкалу Крипке, в которой ложна в некотором мире.
Напомним схему доказательства полноты классического исчисления высказываний, приведенного в разделе "Второе доказательство теоремы о полноте". Пусть формула невыводима. Мы хотим найти значения переменных, при которых формула ложна, то есть формула
истинна. Само по себе требование истинности не определяет значения переменных однозначно. Чтобы избавиться от произвола, мы расширяем непротиворечивое множество до полного множества и объявляем истинными те переменные, которые входят в .
Для интуиционистского случая в этой схеме требуются некоторые изменения. Раньше ложность формулы была равносильна истинности формулы . В шкалах Крипке это уже не так, и мы будем отдельно говорить об истинных и ложных (не истинных) формулах.
Пусть и — конечные множества пропозициональных формул. Будем говорить, что пара совместна, если существует шкала Крипке и ее мир, в котором все формулы из
истинны, а все формулы из ложны. Будем говорить, что пара противоречива, если в интуиционистском исчислении высказываний выводима формула
где — формулы множества , а — формулы множества . (Без ограничения общности можно считать, что перечислены все формулы множеств и , поскольку пропущенные формулы можно добавить, не нарушив выводимость.)
Пример: если одна и та же формула входит в обе части пары, то такая пара противоречива.
Легко проверить, что противоречивая пара не может быть совместна. В самом деле, если в некотором мире все формулы из истинны, а все формулы из ложны, то посылка импликации в этом мире истинна, а заключение ложно. Поэтому импликация ложна, что противоречит ее выводимости (теорема о корректности).
Мы докажем, что верно и обратное: всякая непротиворечивая пара совместна. В частности, когда состоит из единственной формулы, получается утверждение теоремы о полноте. (Мы предполагаем, как это обычно делается, что конъюнкция пустого множества формул есть тождественно истинная формула, а дизъюнкция — тождественно ложная. Поэтому противоречивость пары означает выводимость формулы . Заметим кстати, что противоречивость пары означает выводимость формулы .)
Итак, пусть имеется непротиворечивая пара . Как доказать ее совместность? Как и в классическом случае, мы устраним произвол, расширив и . Основным средством здесь является такая лемма.
Лемма 1. Пусть — непротиворечивая пара, а — произвольная формула. Тогда хотя бы одна из пар и непротиворечива.
Доказательство леммы 1. Пусть обе пары с добавленным
противоречивы. Надо доказать, что противоречива исходная пара. Другими словами, надо показать, что если в интуиционистском исчислении высказываний выводимы формулы
то выводима и формула (для простоты мы отождествляем множества и с конъюнкцией и дизъюнкцией их элементов и считаем и формулами).
В самом деле, по лемме о дедукции достаточно доказать, что . Для этого достаточно установить, что
поскольку в предположении у нас уже есть. Для этого, в свою очередь, достаточно установить, что и . Первое очевидно (и посылка не нужна), второе равносильно выводимости формулы , которая нам дана по условию леммы. Лемма 1 доказана.
Проведенное рассуждение, как говорят, устанавливает допустимость (в интуиционистской логике) правила сечения, позволяющего "иссечь" формулу из формул и и получить формулу .
Возвращаясь к доказательству теоремы, рассмотрим произвольную непротиворечивую пару . Рассматривая по очереди различные формулы , мы будем добавлять их к левой или правой части. Чтобы этот процесс ("пополнение") был конечным, мы ограничимся формулами из некоторого множества.
Фиксируем некоторое конечное множество формул , которое содержит все формулы из и замкнуто относительно перехода к подформулам (если формула входит в , то все ее подформулы входят в ). Например, можно включить в все подформулы всех формул из и из .
Пару , у которой , будем называть полной, если она непротиворечива и любая формула из
входит либо в , либо в (то есть ). Заметим, что из непротиворечивости следует, что , так что полная пара задает разбиение на две части. (Более точно полные пары следовало бы называть "полными относительно ", но у нас множество
фиксировано.)
Лемма 2. Исходная пара может быть расширена до полной: существует полная пара , для которой , .
Доказательство очевидно: применяем по очереди лемму 1 ко всем формулам из .
Точно так же любую непротиворечивую пару, составленную из формул множества , можно расширить до полной. (Это замечание нам впоследствии понадобится.)
Для завершения доказательства теоремы 26. нам осталось показать, что всякая полная пара совместна (существует шкала и мир, в котором формулы из истинны, а формулы из ложны). В отличие от классического случая построение будет использовать не только пару , но и все полные пары.
Шкала Крипке строится так. Мирами будут полные пары (то есть всевозможные непротиворечивые разбиения множества на левую и правую части). Истинность переменных определяется естественным образом: всякая переменная , входящая в одну из формул множества , сама принадлежит множеству
(замкнутость относительно подформул); если входит в левую часть полной пары , то истинна в мире , если в правую — то ложна. (Впоследствии это свойство мы распространим на все формулы: любая формула из окажется истинной в мире , а любая формула из — ложной.)
Осталось определить порядок на множестве пар. Считаем, что , если . (Такое определение не удивительно, если вспомнить, что истинность формул наследуется вверх.)
Лемма 3. В построенной шкале в мире истинны все формулы из и ложны все формулы из .
Доказательство леммы 3 проводится индукцией по построению формул. Для переменных она верна по определению истинности. Пусть некоторая формула из не является переменной. Тогда она есть конъюнкция, дизъюнкция, импликация или отрицание и для ее частей утверждение леммы верно по предположению индукции. Рассмотрим все случаи по очереди, начав с конъюнкции и дизъюнкции (истинность которых не зависит от других миров).
() Пусть формула входит в . Тогда формулы и не могут входить в , иначе пара была бы противоречивой (из выводится и ). Значит, и входят в (полнота), поэтому они истинны (предположение индукции), и потому истинна (определение истинности).
() Пусть формула входит в . Могут ли обе формулы и входить в ? Нет, так как в этом случае пара была бы противоречивой. Значит, хотя бы одна из формул входит в , тогда по предположению индукции она ложна, и потому формула ложна в мире .
() Если формула входит в , то формулы и не могут одновременно входить в , и потому хотя бы одна из них истинна, так что и вся формула истинна.
() Если формула входит в , то формулы и не могут входить в , поэтому обе они ложны и формула ложна.
() Пусть формула входит в . Проверим, что она истинна в . Это значит, что в любом мире , который выше нашего (то есть ) и в котором истинна формула , должна быть истинна и формула . В самом деле, если истинна в , то она входит в (предположение индукции). С другой стороны, и входит в , поскольку . Теперь ясно, что формула не может входить в , так как в этом случае пара была бы противоречивой (из и выводится ). Значит,
входит в и потому истинна в по предположению индукции.
() Это наиболее интересный случай, где нам снова потребуется пополнение. Пусть формула входит в . Мы должны доказать, что она ложна в мире . Согласно определению, это означает, что найдется мир , для которого и в котором формула
истинна, а формула ложна (то есть и , согласно предположению индукции). Как найти такой мир? Рассмотрим пару . Эта пара непротиворечива. В самом деле, если бы формула была бы выводима, то и формула была бы выводима (лемма о дедукции), и потому пара была бы противоречива. Теперь можно расширить непротиворечивую пару
до полной пары , которая и будет искомым миром.
Отрицание рассматривается аналогично импликации (как мы уже говорили, можно вместо отрицания ввести тождественную ложь и вообще его не рассматривать).
() Пусть формула входит в . Надо доказать, что формула ложна в любом мире
выше мира . Формула не может входить в , так как в входит формула (напомним, что ), а из
выводится любая формула. Значит, входит в и по индуктивному предположению формула ложна в .
( Пусть формула входит в . В этом случае пара непротиворечива (если из и выводится противоречие, то из выводится ). Расширив ее до полной, получаем высший мир , в котором формула истинна (по индуктивному предположению). Следовательно, формула ложна в мире .
Лемма 3 доказана. Она завершает доказательство теоремы 26. Напомним еще раз его схему. Пусть формула не выводима в интуиционистском исчислении высказываний. Тогда пара
непротиворечива. Фиксируем множество всех подформул формулы . Расширим нашу непротиворечивую пару до полной (относительно ). Эта полная пара будет одним из миров шкалы Крипке (в которой мирами являются полные пары). Именно в этом мире и будет ложной формула .
36. Покажите, что если формулы и ложны в некоторых мирах некоторых шкал Крипке, то можно построить шкалу Крипке и мир в ней, для которого формула будет ложной. (Указание: соединим шкалы, в которых ложны формулы
и , в одну, добавив новый мир, который меньше миров, где и ложны.)
Из этой задачи и из теоремы о полноте вытекает такое следствие: если дизъюнкция двух формул выводима в интуиционистском исчислении высказываний, то хотя бы одна из формул тоже выводима. Это свойство выполнено для многих интуиционистских исчислений и соответствует начальной идее: доказать
означает доказать одну из формул или . Подобные свойства можно доказывать и синтаксически, используя генценовские варианты интуиционистских исчислений.
37. (а) Покажите, что формула
выводима в интуиционистском исчислении высказываний. (б) Покажите, что если формулы и
выводимы в интуиционистском исчислении высказываний, то и формула выводима в интуиционистском исчислении высказываний. (в) Докажите, что если формула выводима в классическом исчислении высказываний, то формула выводима в интуиционистском исчислении высказываний (теорема Гливенко) (г) Покажите, что для формул, содержащих лишь конъюнкцию и отрицание, разницы между классическим и интуиционистским исчислениями нет: из классической выводимости следует интуиционистская (теорема Геделя).
Покажите, что интуиционистское исчисление высказываний разрешимо: существует алгоритм, который по произвольной формуле определяет, выводима ли она в интуиционистском исчислении высказываний. (Указание: оцените мощность контрмодели Крипке; можно обойтись и без этого, заметив, что и множество выводимых формул, и множество формул, имеющих конечные контрмодели, перечислимы.)
Поиск контрпримера и исчисление секвенций
В этом разделе мы построим другой вариант исчисления высказываний — так называемое исчисление секвенций. Такого рода исчисления изучаются в теории доказательств. Они оказываются более удобными для анализа синтаксической структуры выводов. Их называют исчислениями генценовского типа (по имени Генцена, который начал их изучать). Ранее приведенный вариант исчисления высказываний называют исчислением гильбертовского типа (по имени Гильберта, который использовал подобные исчисления в своей программе формального построения математики).
Для начала мы вообще не будем говорить ничего об аксиомах и правилах вывода, а рассмотрим задачу поиска контрпримера. Пусть дана некоторая формула , про которую мы подозреваем, что она не является тавтологией, и хотим найти значения переменных, при которых она ложна. Как это делать? Естественно посмотреть на структуру формулы . Например, если имеет вид , то надо найти значения переменных, при которых формула истинна, а ложна. Если имеет вид , то надо найти значения переменных, при которых обе формулы и
ложны. Если имеет вид , то надо найти либо значения переменных, при которых ложна, либо значения переменных, при которых ложна. Тем самым задача поиска контрпримера для формулы сводится к одной или нескольким задачам такого же или более общего вида (надо обеспечить истинность или ложность одной или нескольких формул).
Введем необходимую терминологию и обозначения. Будем называть секвенцией выражение , где
и — некоторые конечные множества формул. (Пока что знак не имеет ничего общего с выводимостью, а только разделяет два множества формул.) С каждой секвенцией будем связывать задачу поиска таких значений переменных, при которых все формулы из истинны, а все формулы из ложны. Такой набор значений мы по некоторым причинам будем называть контрпримером к секвенции . Легко проверить, что контрпримеры к секвенции — это контрпримеры к формуле
( обозначает конъюнкцию формул из , а — дизъюнкцию формул из ), то есть те наборы значений, при которых эта формула ложна.
При этом конъюнкцию пустого множества формул мы считаем тождественно истинной, а дизъюнкцию — тождественно ложной.
Наша исходная задача поиска контрпримера к формуле может быть теперь сформулирована как задача поиска контрпримера к секвенции . (Мы позволяем себе писать так для краткости; полностью следовало бы написать .)
Задачу поиска контрпримера к секвенции можно решать с помощью следующих правил. В каждом из приведенных правил нижний заказ на контрпример выполним, если и только если выполним один из верхних заказов, т. е. нижняя секвенция имеет контрпример тогда и только тогда, когда хотя бы одна из верхних секвенций имеет контрпример.
Каждое из правил соответствует анализу одной из формул нижней секвенции. Правила разделены на группы в зависимости от главной связки анализируемой формулы, и согласованы с таблицами истинности для этой связки (что легко проверить). Запятая в правилах используется как сокращение: обозначает и т. д.
Как пользоваться этими правилами? Возьмем секвенцию, к которой мы ищем контрпример. Выберем в ней одну из формул слева или справа, посмотрим на главную связку и применим соответствующее правило (написав одну или две секвенции над исходной). Затем к каждой из них снова применим одно из правил и т. д. Постепенно будет расти "дерево поиска контрпримера", причем исходная секвенция будет иметь контрпример тогда и только тогда, когда одна из верхних секвенций (стоящих в "листьях") этого дерева имеет контрпример.
Когда этот процесс обрывается? Это происходит в том случае, если все формулы в оставшихся секвенциях представляют собой переменные, тогда ни одно из наших правил поиска контрпримера не применимо. Но к этому моменту все становится ясным: если в левой и правой части секвенции есть общая переменная, то к ней нет контрпримера (одна и та же переменная не может быть одновременно истинной и ложной). Если же левая и правая часть такой секвенции не пересекаются, то контрпример есть.
Вот как это делается с секвенцией :
Контрпример найден: и ложны (он является контрпримером к секвенции ).
Напротив, попытка поиска контрпримера к секвенции
не дает результата:
Здесь обе секвенции и не имеют контрпримеров. Следовательно, формула
является тавтологией.
Построенный алгоритм можно одновременно рассматривать как доказательство полноты некоторого "исчисления секвенций".
Аксиомами исчисления секвенций будем называть секвенции, в левых и правых частях которых встречаются только переменные, причем некоторая переменная встречается в обеих частях.
Правилами вывода в исчислении секвенций являются правила нашей таблицы. Каждое из этих правил объявляет выводимой нижнюю секвенцию, если выводимы все верхние. (Процесс вывода естественно представлять в виде дерева, как в наших примерах, но можно развернуть и в последовательность секвенций.)
Теорема 23 (корректность и полнота исчисления секвенций).
Секвенция выводима тогда и только тогда, когда она не имеет контрпримера.
Аксиомы не имеют контрпримера. Если все верхние секвенции какого-то правила вывода не имеют контрпримера, то и нижняя секвенция не имеет контрпримера. (Именно так мы подбирали правила: контрпример к нижней секвенции будет контрпримером к одной из верхних.) Следовательно, все выводимые секвенции не имеют контрпримера.
Обратно, пусть секвенция не имеет контрпримера. Тогда описанный процесс поиска контрпримера обрывается на аксиомах и тем самым дает ее вывод.
В частности, если формула является тавтологией, то секвенция выводима в исчислении секвенций. Это обстоятельство можно использовать для еще одного доказательства полноты исчисления высказываний (в стандартной, гильбертовской форме). В самом деле, для каждой секвенции рассмотрим представляющую ее формулу, то есть формулу (в левой и правой частях стоят конъюнкция и дизъюнкция формул из и
соответственно). Теперь индукцией по построению вывода в исчислении секвенций надо доказать такой факт: если секвенция выводима в исчислении секвенций, то представляющая ее формула выводима в (обычном) исчислении высказываний.
Это требует довольно хлопотной проверки, впрочем.
Сначала надо проверить, что конъюнкция и дизъюнкция доказуемо ассоциативны, и потому все равно, как расставлять скобки в формуле, представляющей секвенцию. Затем полезно убедиться, что правила, связанные с отрицанием (два последних правила таблицы) можно применять в обе стороны, не меняя выводимости соответствующей формулы. Другими словами, надо проверить, что формулы
а также формулы
выводимы одновременно (здесь и можно считать формулами, а не множествами формул, расставив скобки надлежащим образом). После этого мы можем переносить формулы из одной части в другую (меняя их на противоположные), и потому можем считать одно из множеств и пустым, если это нам удобно. Теперь ссылка на лемму о дедукции и уже известные нам свойства выводимости завершает рассуждение.
30. Провести это рассуждение подробно.
Естественно возникает вопрос — чем уж так интересно исчисление секвенций? Какая, собственно говоря, разница — иметь дело с секвенциями или с формулами, раз всякую секвенцию можно представить формулой? Принципиальное различие тут в следующем. Правила вывода в исчислении секвенций таковы, что в их верхнюю часть входят только подформулы формул, встречающихся в нижней части. Поэтому в выводе какой-то секвенции не может встретиться ничего принципиально нового, чего не было в самой секвенции. В гильбертовском исчислении это далеко не так: мы можем вывести формулу из формул и , при этом формула может быть совершенно произвольной. Это же различие объясняет, почему поиск вывода снизу вверх (как можно теперь называть то, что раньше называлось поиском контрпримера — мы находим либо контрпример, либо вывод) для исчисления секвенций происходит сравнительно однозначно (мы можем по-разному выбирать расчленяемую формулу, но и только), в то время как искать вывод в обычном исчислении высказываний, начав с интересующей нас формулы и смотря, из чего бы она могла получиться, не удается (если только не перебирать все формулы подряд).
Заметим, что добавление к исчислению секвенций уже упоминавшегося правила сечения
нарушает свойство "подформульности", так как формула
может быть никак не связана с нижней секвенцией. Отметим, что добавление правила сечения не нарушает корректности, как легко проверить, и не может нарушить полноты.
Задачи о поиске вывода и анализе его структуры, хотя и были одно время модными в связи с "искусственным интеллектом", представляют большой интерес, и про них есть целая наука, в которой исчисления генценовского типа играют центральную роль. Мы рассмотрели один из вариантов исчисления секвенций для классического исчисления высказываний; бывают исчисления для интуиционистских и модальных логик, для исчисления предикатов и т. д. Исходной мотивацией для рассмотрения такого рода исчислений было желание доказать непротиворечивость арифметики. Согласно знаменитой второй теореме Геделя о неполноте без дополнительных аксиом этого сделать нельзя, но если принять схему аксиом для трансфинитной индукции по ординалу , это удается сделать, как показал Генцен.
Формулы и интерпретации
Начнем с примера. Пусть — некоторое непустое множество, а — бинарное отношение на нем, то есть подмножество декартова произведения . Вместо мы будем писать . Рассмотрим формулу
Эта формула выражает некоторое свойство бинарного отношения
(для любого элемента найдется элемент, находящийся с ним в отношении ) и может быть истинна или ложна. Например, если есть множество натуральных чисел , а — отношение "строго меньше" (другими словами, есть множество всех пар , для которых ), то эта формула истинна. А для отношения "строго больше" (на том же множестве) эта формула ложна.
Вопрос о том, будет ли истинна формула
для данного множества и для данного бинарного отношения на нем, не имеет смысла, пока не уточнено, каково значение переменной . Например, если и есть , то эта формула будет истинной при и ложной при . Для данных и она задает некоторое свойство элемента и тем самым определяет некоторое подмножество множества .
Перейдем к формальным определениям. Пусть — непустое множество. Множество состоит из всех последовательностей длины , составленных из элементов множества . Назовем -местной функцией на множестве любое отображение в (определенное на всем ). Синонимы: "функция аргументов", "функция валентности ", "функция местности " и даже "функция арности " (последнее слово происходит от слов "унарная" для функций одного аргумента, "бинарная" (операция) для функций двух аргументов и "тернарная" для трех аргументов).
Назовем -местным предикатом на множестве любое отображение в множество . Такой предикат будет истинным на некоторых наборах множества и ложным на остальных наборах. Поставив ему в соответствие множество тех наборов, где он истинен, мы получаем взаимно однозначное соответствие между -местными предикатами на и подмножествами множества . Говоря о предикатах, также употребляют термины "валентность", "число аргументов" и др.
Мы будем рассматривать также функции и предикаты валентности нуль.
Множество одноэлементно (содержит единственную последовательность длины ). Поэтому функции
отождествляются с элементами множества , а нульместных предикатов ровно два — истинный и ложный.
Естественно, что в формулы будут входить не сами функции и предикаты, а обозначения для них, которые называют функциональными и предикатными символами. В качестве символов можно использовать любые знаки. Важно лишь, что каждому символу приписана валентность, которая определяет, со сколькими аргументами он может встречаться в формуле. Произвольный набор предикатных и функциональных символов, для каждого из которых указано неотрицательное число, называемое валентностью, мы будем называть сигнатурой.
Остается определить три вещи: что такое формула данной сигнатуры, что такое интерпретация данной сигнатуры и когда формула является истинной (в данной интерпретации).
Фиксируем некоторый набор символов, называемых индивидными переменными. Они предназначены для обозначения элементов множества, на котором определены функции и предикаты; обычно в таком качестве используют латинские буквы с индексами. В каждой формуле будет использоваться конечное число переменных, так что счетного набора переменных нам хватит. Мы предполагаем, что переменные отличны от всех функциональных и предикатных символов сигнатуры (иначе выйдет путаница).
Определим понятие терма данной сигнатуры. Термом называется последовательность переменных, запятых, скобок и символов сигнатуры, которую можно построить по следующим правилам:
Индивидная переменная есть терм.Функциональный символ валентности есть терм.Если — термы, а — функциональный символ валентности , то есть терм.
В принципе можно было не выделять функциональные символы валентности (которые также называют константами) в отдельную группу, но тогда бы после них пришлось писать скобки (как это делается в программах на языке Си).
Если — предикатный символ валентности , а — термы, то выражение
считается атомарной формулой. Кроме того, любой предикатный символ валентности считается атомарной формулой.
Формулы строятся по таким правилам:
Атомарная формула есть формула.Если — формула, то — формула.Если и — формулы, то выражения , , также являются формулами.Если есть формула, а — индивидная переменная, то выражения и
являются формулами.
Во многих случаях в сигнатуру входит двуместный предикатный символ , называемый равенством. По традиции вместо пишут .
Итак, понятие формулы в данной сигнатуре полностью определено. Иногда такие формулы называют формулами первого порядка данной сигнатуры, или формулами языка первого порядка с данной сигнатурой.
Наш следующий шаг — определение интерпретации данной сигнатуры. Пусть фиксирована некоторая сигнатура . Чтобы задать интерпретацию сигнатуры , необходимо:
указать некоторое непустое множество , называемое носителем интерпретации;для каждого предикатного символа сигнатуры указать предикат с соответствующим числом аргументов, определенный на множестве (как мы уже говорили, -местным предикатным символам ставится в соответствие либо И, либо Л);для каждого функционального символа сигнатуры
указать функцию соответствующего числа аргументов с аргументами и значениями из (в частности, для -местных функциональных символов надо указать элемент множества , с ними сопоставляемый).
Если сигнатура включает в себя символ равенства, то среди ее интерпретаций выделяют нормальные интерпретации, в которых символ равенства интерпретируется как совпадение элементов множества .
Приведем несколько примеров сигнатур, используемых в различных теориях.
Сигнатура теории упорядоченных множеств включает в себя два двуместных предикатных символа (равенство и порядок) и не имеет функциональных символов. Здесь также вместо по традиции пишут .
Аксиомы порядка (рефлексивность, антисимметричность, транзитивность) могут быть записаны формулами этой сигнатуры. Например, требование антисимметричности записывается так:
Иногда в сигнатуру теории упорядоченных множеств вместо символа включают символ ; большой разницы тут нет.
39. Как записать с помощью формулы свойство линейной упорядоченности? свойство не иметь наибольшего элемента? свойство плотности (отсутствия соседних элементов)? свойство фундированности (отсутствия бесконечных убывающих последовательностей — или, что эквивалентно, наличия минимального элемента в любом подмножестве)? свойство полной упорядоченности? (Указание: не для всех перечисленных свойств это возможно.)
Сигнатуру теории групп можно выбирать по-разному. Можно считать, что (помимо равенства) она имеет двуместный функциональный символ (который по традиции записывают между множителями), константу (нульместный функциональный символ) и одноместный функциональный символ для обращения. Тогда аксиомы теории групп записываются с использованием лишь кванторов всеобщности:
Если не включать операцию обращения в сигнатуру, придется использовать квантор существования и переписать последнюю аксиому так:
40. Как записать аксиомы теории групп, если в сигнатуре нет константы ? (Указание: аксиома о существовании обратного станет частью аксиомы о существовании единицы.)
41. Как записать в виде формулы требование коммутативности группы? утверждение о том, что любой элемент (кроме единицы) имеет порядок ? конечность группы? (Указание: не все из перечисленного можно записать, хотя пока у нас нет средств это установить.)
Сигнатура теории множеств содержит два двуместных предикатных символа: для принадлежности и для равенства. Аксиомы теории множеств можно записывать в виде формул этой сигнатуры. Чаще всего рассматривают вариант аксиоматической теории множеств, называемый теорией Цермело-Френкеля и обозначаемый ZF. Приведем для примера одну из аксиом теории ZF, называемую аксиомой объемности, или экстенсиональности:
42. Сформулировать словесно эту аксиому.
43. Записать в виде формулы аксиому регулярности, или фундирования, которая говорит, что у всякого множества есть минимальный (с точки зрения отношения ) элемент, то есть элемент, не пересекающийся с самим множеством.
44. Какова естественная сигнатура для теории полей? Можно ли записать в виде формулы этой сигнатуры утверждение о том, что поле имеет характеристику ? конечную характеристику? алгебраически замкнуто?
Языки первого порядка
Помимо логических связок, в математических рассуждениях часто встречаются кванторы "для любого" () и "существует" (). Например, определение непрерывности начинается словами "для любого положительного найдется положительное , для которого, ...". А одна из аксиом теории групп (существование обратного элемента) записывается так: .
Можно сформулировать различные логические законы, включающие в себя кванторы. Например, высказывание "существует такое , что " (где — некоторое свойство объекта ) логически эквивалентно высказыванию "не для всех верно ".
Мы будем записывать такого рода законы с помощью формул, дадим определение истинности формул (при данной интерпретации входящих в них символов) и исследуем, какого рода свойства можно выражать с помощью формул и какие нельзя.
Определение истинности
Из приведенных выше примеров, вероятно, понятен смысл формулы, то есть ясно, в каких интерпретациях данной сигнатуры и для каких элементов формула истинна. Тем не менее для любителей строгости мы приведем формальное определение истинности. (Его детали понадобятся, когда мы будем проверять истинность выводимых формул, см. раздел "Корректность исчисления предикатов"
Прежде всего, определим формально понятие параметра формулы (переменной, от значения которой может зависеть истинность формулы). Согласно этому определению, скажем, формула
не имеет параметров, а формулы
и
имеют единственный параметр . Вот как выглядит это определение:
Параметрами терма являются все входящие в него индивидные переменные.Параметрами атомарной формулы являются параметры всех входящих в нее термов.Параметры формулы те же, что у формулы .Параметрами формул , и являются все параметры формулы , а также все параметры формулы .Параметрами формул и
являются все параметры формулы , кроме переменной .
Параметры иногда называют свободными переменными формулы. Заметим, что формула может иметь одновременно параметр и использовать (в другом месте) квантор . Как говорят в этом случае, одна и та же переменная имеет свободные и связанные вхождения. Свободное вхождение переменной — это такое вхождение, которое не входит в область действия одноименного квантора. Если аккуратно определить эту область действия, несложно проверить, что параметры формулы — это как раз переменные, имеющие свободные вхождения.
Теперь мы хотим определить понятие формулы, истинной в данной интерпретации при данных значениях параметров. Технически проще считать, что всем индивидным переменным приписаны какие-то значения, а потом доказать, что переменные, не являющиеся параметрами, не влияют на истинность формулы.
Итак, пусть фиксирована сигнатура и некоторая интерпретация этой сигнатуры. Оценкой назовем отображение, которое ставит в соответствие каждой индивидной переменной некоторый элемент множества, являющегося носителем интерпретации.
Этот элемент будем называть значением переменной при данной оценке.
Определим индуктивно значение терма при данной оценке , которое мы будем обозначать .
Для переменных оно уже определено.Если является константой (нульместным функциональным символом), то не зависит от и равно значению этой константы при данной интерпретации (напомним, в интерпретации с каждой константой сопоставляется некоторый элемент носителя).Если имеет вид , где — функциональный символ валентности , а — термы, то есть , где есть функция, соответствующая символу в нашей интерпретации, а есть значение терма
при оценке .
Теперь можно определить значение формулы при данной оценке в данной интерпретации, которое обозначается и может быть равно И или Л; в первом случае формула называется истинной, во втором — ложной. Это определение также индуктивно:
Значение атомарной формулы определяется как , где — предикат, соответствующий предикатному символу в рассматриваемой интерпретации. Если формула представляет собой нульместный предикатный символ, то ее значение не зависит от оценки и есть значение этого символа. определяется как , где понимается как операция в . Другими словами, формула истинна при оценке тогда и только тогда, когда формула ложна при этой оценке. определяется как , где в правой части понимается как операция в . (Другими словами, формула истинна при оценке
тогда и только тогда, когда обе формулы и истинны при этой оценке.) Аналогичным образом определяется как , а — как .Формула истинна на оценке тогда и только тогда, когда формула истинна на любой оценке , которая совпадает с всюду, кроме значения переменной (которое в оценке
может быть любым). Другими словами, если обозначить через
оценку, при которой значение переменной равно , а остальные переменные принимают те же значения, что и в оценке , то
(В правой части стоит бесконечная конъюнкция, которая истинна, если все ее члены истинны.)Формула истинна на оценке тогда и только тогда, когда формула истинна на некоторой оценке , которая совпадает с всюду, кроме значения переменной (которое в оценке
может быть любым). Другими словами,
( В правой части стоит бесконечная дизъюнкция, которая истинна, если хотя бы один из ее членов истинен.)
Заметим, что в двух последних пунктах значение переменной
в оценке не играет роли. Это позволяет легко доказать (индукцией по построению формулы) такое утверждение: если две оценки и придают одинаковые значения всем параметрам формулы , то . Другими словами, истинность формулы определяется значениями ее параметров.
45. Проведите это индуктивное рассуждение подробно.
46. Приведенные выше определения применимы к любой формуле, в том числе и к странной формуле . Какие у нее параметры? При каких значениях параметров она истинна? (Ответ: она имеет единственный параметр и эквивалентна формуле .)
47. В каком случае будет истинна формула ? Тот же вопрос для формулы . (Ответ: первая из этих формул эквивалентна формуле , а вторая — формуле .)
Формула называется замкнутой, если она не имеет параметров. Замкнутые формулы называют также суждениями. Как мы доказали, истинность замкнутой формулы определяется выбором интерпретации (и не зависит от значений переменных).
Выразимые предикаты
Пусть фиксирована некоторая сигнатура и ее интерпретация с носителем . Мы хотим определить понятие выразимого (с помощью формулы данной сигнатуры в данной интерпретации) -местного предиката.
Выберем переменных . Рассмотрим произвольную формулу , все параметры которой содержатся в списке . Истинность этой формулы зависит только от значений переменных . Тем самым возникает отображение , то есть некоторый - местный предикат на . Говорят, что этот предикат выражается формулой . Все предикаты, которые можно получить таким способом, называются выразимыми. (Ясно, что конкретный выбор списка переменных роли не играет.) Соответствующие им подмножества множества (области истинности выразимых предикатов) также называют выразимыми.
48. Докажите, что пересечение, объединение и разность двух выразимых множеств являются выразимыми. Докажите, что проекция - мерного выразимого множества вдоль одной из "осей координат" является -мерным выразимым множеством.
Пример. Сигнатура содержит одноместный функциональный символ и двуместный предикатный символ равенства (). Рассмотрим интерпретацию этой сигнатуры. В качестве носителя выберем натуральный ряд . Символ будет обозначать функцию прибавления единицы (можно считать
сокращением от слова successor — последователь). Знак равенства интерпретируется как совпадение элементов.
Легко проверить, что одноместный предикат "быть нулем" выразим в этой интерпретации, несмотря на то, что константы для нуля в сигнатуре не предусмотрено. В самом деле, он выражается формулой
с единственным параметром .
Еще проще выразить в этой сигнатуре двуместный предикат "быть больше на ", при этом даже не нужны кванторы: .
Любопытно, что уже в такой простой ситуации можно сформулировать содержательную задачу: выразить предикат , где — большое число (скажем, миллиард), с помощью существенно более короткой формулы, чем . Как ни удивительно, это вполне возможно, и соответствующую формулу вполне можно уместить на листе бумаги.
49. Докажите, что предикат можно выразить формулой указанной сигнатуры, длина которой есть . (Указание. Если мы научились выражать , можно выразить с помощью формулы
(в которой через и обозначены соответствующие формулы). Это само по себе ничего не дает, так как длина формулы увеличилась вдвое, но можно использовать такой трюк:
Далее можно воспользоваться записью числа в двоичной системе счисления.)
Можно доказать, что в этой сигнатуре кванторы почти не увеличивают набор выразимых предикатов: всякий выразимый предикат будет выражаться бескванторной формулой (возможно, гораздо более длинной), если добавить к сигнатуре константу . Мы вернемся к этому вопросу в разделе "Элиминация кванторов".
Чтобы привыкнуть к понятию выразимости, рассмотрим еще один пример. Пусть сигнатура содержит предикат равенства и трехместный предикат . Рассмотрим интерпретацию, в которой носителем является множество точек плоскости, равенство интерпретируется как совпадение точек, а означает, что точки и равноудалены от точки . Оказывается, что этого предиката достаточно, чтобы выразить более или менее все традиционные понятия элементарной геометрии.
Как, например, записать, что три различные точки лежат на одной прямой? Вот как: "не существует другой точки , которая находилась бы на тех же расстояниях от и , что и точка ".
50. Напишите соответствующую формулу указанной сигнатуры.
Теперь легко выразить такое свойство четырех точек : "точки и различны, точки и различны и прямые и параллельны". В самом деле, надо написать, что нет точки, которая бы одновременно лежала на одной прямой с и , а также на одной прямой с и .
После этого можно выразить свойство четырех точек "быть вершинами параллелограмма". Это позволяет переносить отрезок параллельно себе. После этого несложно выразить такое свойство: "расстояние равно расстоянию ".
51. Запишите соответствующую формулу.
Аналогичным образом можно двигаться и дальше.
52. Выразите свойство трех точек , , . (Указание. Напишите, что все прямые, проходящие через , пересекаются с окружностью радиуса с центром в .)
53. Запишите в виде формулы:(а) равенство треугольников; (б) равенство углов;(в) свойство угла быть прямым.
54. Рассмотрим естественную интерпретацию сигнатуры на множестве целых чисел. Как выразить предикат ?
55. Рассмотрим множество действительных чисел как интерпретацию сигнатуры . Как выразить трехместный предикат ?
56. Рассмотрим множество целых положительных чисел как интерпретацию сигнатуры, содержащей равенство и двуместный предикат "
делит ". Выразите свойства "равняться единице" и "быть простым числом".
57. Рассмотрим плоскость как интерпретацию сигнатуры, содержащей предикат равенства (совпадение точек) и двуместный предикат "находиться на расстоянии ". Выразите двуместные предикаты "находиться на расстоянии " и "находиться на расстоянии не более ". Выразите двуместный предикат "находиться на расстоянии .
Элиминация кванторов: элиминация кванторов
При всей простоте метод доказательства невыразимости с помощью автоморфизмов страдает очевидным недостатком: очень часто требуемого автоморфизма нет. Например, натуральные числа с операцией прибавления единицы вообще не допускают никакого нетривиального автоморфизма. (Тем не менее там выразимо очень немногое, как мы вскоре увидим.) Целые числа с операцией прибавления единицы допускают автоморфизмы (сдвиги), но эти автоморфизмы не позволяют доказать, что отношение порядка невыразимо (поскольку оно устойчиво относительно сдвигов).
Более прямой метод доказательства состоит в том, что мы предъявляем некоторый класс
предикатов, который содержит все выразимые предикаты и не содержит интересующего нас предиката. При этом мы доказываем, что содержит все выразимые предикаты, таким способом: проверяем, что содержит все предикаты, выразимые атомарными формулами, а также замкнут относительно логических операций (объединение, пересечение, дополнение) и операции проекции (соответствующей навешиванию квантора существования; квантор всеобщности выражается через квантор существования). Часто класс совпадает с классом всех предикатов, выразимых бескванторными формулами (иногда надо расширить сигнатуру), и потому этот метод называют методом "элиминации кванторов". (Это краткое описание, возможно, станет яснее из приводимых далее примеров.)
Начнем с такого примера. Пусть сигнатура содержит равенство, одноместную функцию (прибавление единицы) и константу . Носителем интерпретации будет множество целых чисел, символы сигнатуры интерпретируются естественным образом. В этой ситуации изоморфизмов не существует, так что предыдущий способ доказательства невыразимости здесь неприменим.
Тем не менее класс выразимых предикатов весьма ограничен: это предикаты, выразимые бескванторными формулами. Будем называть две формулы (рассматриваемой нами сигнатуры) эквивалентными (в данной интерпретации), если они выражают один и тот же предикат, то есть истинны при одних и тех же значениях переменных.
Теорема 28. Для всякой формулы рассматриваемой нами сигнатуры существует эквивалентная ей бескванторная формула.
Будем доказывать индукцией по построению (или, если угодно, по длине) формулы существование эквивалентной ей в
бескванторной формулы. Для удобства (чтобы рассматривать один случай, а не два) будем считать, что наша формула может содержать только кванторы существования, но не всеобщности. Это законно, так как формулы и эквивалентны.
Случай, когда есть атомарная формула, очевиден — она и так бескванторная. Если является конъюнкцией, дизъюнкцией или импликацией двух частей, достаточно заменить каждую часть на эквивалентную бескванторную (что можно сделать по предположению индукции).
Единственный содержательный случай — когда формула
начинается с квантора существования, то есть имеет вид (пусть под квантором стоит переменная ). Мы рассуждаем по индукции, поэтому можем считать, что формула — бескванторная. Она имеет (возможно) и другие параметры, скажем, . Чтобы подчеркнуть это, обычно вместо
пишут . Нам надо найти бескванторную формулу нашей сигнатуры, эквивалентную формуле
Формула представляет собой булеву комбинацию атомарных формул. Посмотрим на те атомарные формулы, которые содержат переменную . Атомарная формула представляет собой равенство двух термов ; здесь и — либо переменные, либо константа . Если переменная
входит и в левую, и в правую часть, то (в этой интерпретации) такая атомарная формула либо всегда истинна, либо всегда ложна, и ее можно заменить на какую-нибудь тождественно истинную или тождественно ложную формулу, не содержащую . После этого останутся атомарные формулы, которые можно записать как
Здесь — либо целая константа, либо выражение вида , где — какая-то другая переменная, а — целое число. Мы позволили себе слегка отступить от канонов, разрешив прибавлять и вычитать целые константы вместо того, чтобы применять функцию
в левой и правой частях равенства. Ясно, что это не меняет класса выразимых формул, зато позволяет оставить в левой части, а константу перенести в правую.
Теперь сравним формулу
с формулой
которую мы будет обозначать . Формула представляет собой дизъюнкцию формул, полученных в результате подстановки различных вместо в бескванторную формулу . (После подстановки можно вернуться к обычному виду записи формулы, заменив прибавление констант на нужное количество применений функции с той или другой стороны равенства.)
Очевидно, что если для каких-то значений переменных формула истинна, то для этих значений истинна и формула . В самом деле, если истинен -й член дизъюнкции, то в формуле в качестве можно взять значение выражения .
Верно ли обратное? Не обязательно. Вполне возможно, что тот , который существует и делает формулу истинной, отличается от всех . Но мы пропустили по существу только один случай — все такие в некотором смысле одинаковы, так как они делают все атомарные формулы, содержащие , ложными, поэтому все равно, какой из таких выбрать. Отметим также, что хотя бы один такой найдется, поскольку
бесконечно, а выражений лишь конечное число.
Обозначим через формулу, которая получится из
заменой всех атомарных формул, содержащих , на тождественно ложные формулы. Сказанное выше объясняет, почему формула
эквивалентна дизъюнкции . Мы достигли цели — нашли бескванторную формулу, эквивалентную формуле .
Легко понять, что отношение порядка не выражается бескванторной формулой нашей сигнатуры, поскольку такая формула может включать лишь атомарные формулы вида и для нее случай, когда сильно больше , неотличим от случая, когда сильно меньше . Тем самым мы доказали (чего нельзя было сделать методом автоморфизмов), что отношение невыразимо (в данной интерпретации данной сигнатуры).
Немного более сложное рассуждение понадобится, если добавить к сигнатуре отношение порядка.
Теорема 29. Всякая формула в (где — функция прибавления единицы) эквивалентна некоторой бескванторной формуле. (Как говорят, допускает элиминацию кванторов.)
Полностью утверждение теоремы звучит так: для всякой формулы сигнатуры, содержащей равенство, порядок и символ , найдется бескванторная формула той же сигнатуры, которая эквивалентна ей в интерпретации, где носителем является , а символы сигнатуры интерпретируются естественным образом. (В дальнейшем мы будем опускать такие пояснения.)
Доказательство следует прежней схеме. Правда, теперь атомарных формул больше — помимо формул у нас будут формулы . Поэтому нельзя рассчитывать на то, что все значения , не встречающиеся среди , ведут себя одинаково, и наш прием с выделением случая, когда все равенства ложны, более не проходит.
Как же быть? Для данных значений числа делят числовую ось (точнее, множество целых чисел) на промежутки, и для выяснения истинности формулы нам надо попробовать (помимо всех ) хотя бы по одному числу из каждого промежутка. Это будет гарантировано, если мы напишем дизъюнкцию, в которую, помимо всех формул , войдут также формулы и . Это позволяет нам обойтись без формулы и благополучно завершить доказательство.
63. Проверьте, что добавление константы к этой сигнатуре не препятствует элиминации кванторов.
Что будет, если мы из этой сигнатуры удалим функцию ? Легко понять, что класс выразимых множеств не изменится, так как можно выразить как " является наименьшим элементом, большим ". Однако при этом мы использовали кванторы, так что для элиминация кванторов невозможна.
64. Убедитесь, что в самом деле формула не эквивалентна никакой бескванторной формуле этой сигнатуры.
Часто такой переход приходится выполнять в обратном направлении: у нас есть некоторая ситуация, в которой элиминация кванторов не проходит. Мы обходим эту трудность, добавив некоторые выразимые предикаты и функции в нашу сигнатуру, после чего элиминация кванторов удается. В этом случае мы получаем описание всех выразимых предикатов (предикат выразим, если он записывается бескванторной формулой расширенной сигнатуры). Мы встретимся с такой ситуацией дальше, говоря об арифметике Пресбургера.
В некоторых случаях рассуждение упрощается, если использовать приведение бескванторной формулы к дизъюнктивной нормальной форме. Вот один из таких примеров.
Теорема 30. Всякая формула в эквивалентна некоторой бескванторной формуле.
Как всегда, достаточно рассмотреть случай формулы вида
где — бескванторная формула. Формулу
можно считать формулой в дизъюнктивной нормальной форме (теорема 4). Напомним, это означает, что представляет собой дизъюнкцию конъюнкций, а каждая конъюнкция соединяет несколько литералов (атомарных формул или их отрицаний).
В данном случае можно избавится от отрицаний, заменив на , а — на . После этого надо воспользоваться дистрибутивностью и вновь придти к дизъюнктивной нормальной форме — с большим числом членов, но уже без отрицаний.
Теперь надо воспользоваться тем, что квантор существования (который есть "бесконечная дизъюнкция") можно переставлять с дизъюнкцией. Точнее говоря, мы пользуемся тем, что формулы и
эквивалентны. (Белый или черный единорог существует тогда и только тогда, когда существует белый единорог или существует черный единорог.) Это обстоятельство позволяет заменить формулу
на
и дальше разбираться с каждой из формул поодиночке.
Итак, нам осталось преобразовать к бескванторному виду формулу
где каждая из формул соединяет какие-то две переменные знаком или (напомним, что от отрицаний мы уже избавились).
Некоторые из формул не содержат переменной . Тогда их можно вынести за квантор: если не является параметром формулы , то формулы и эквивалентны (если истинно для некоторых значений параметров, то в обеих формулах его можно опустить; если ложно, то обе формулы ложны при этих значениях параметров).
Вынеся такие формулы, можно считать, что под квантором остались лишь формулы вида , и , сравнивающие переменную с какими-то другими переменными. Если там есть хоть одно равенство, то квантор существования вырождается — его можно удалить вместе с переменной , заменив ее на ту переменную, которой она равна. Например, формулу можно заменить на .
Итак, остался случай, когда переменная встречается лишь в неравенствах. Другими словами, нас спрашивают, найдется ли значение , большее каких-то переменных и меньшее каких-то других. Если все ограничения на одного знака (только снизу или только сверху), то такое значение
существует при любых значениях других переменных (поскольку в множестве нет ни наибольшего, ни наименьшего элементов). Что делать, если есть ограничения разных знаков? Пусть наша формула, например, имеет вид
Как записать условия на , при которых это верно, не используя кванторов? Надо написать такую формулу:
Мы хотим написать, что наибольшая из нижних границ меньше наименьшей из верхних, но поскольку заранее неизвестно, какая будет наибольшей и какая наименьшей, мы пишем, что любая нижняя граница меньше любой верхней. Поскольку множество
является плотным (между любыми двумя элементами найдется третий), то эта формула равносильна исходной.
Так, постепенно сводя дело ко все более простым случаям, мы завершили рассуждение.
Заметим, что в этом доказательстве из свойств рациональных чисел мы использовали лишь отсутствие наибольшего и наименьшего элемента и плотность. Поэтому все наши преобразования остаются эквивалентными для любого упорядоченного множества с такими свойствами, а не только для . Применив эти преобразования к замкнутой формуле (формуле без параметров), мы получим или тождественно истинную формулу, или тождественно ложную (только надо добавить в язык константы для истины и лжи, чтобы не использовать фиктивных переменных, когда надо написать тождественно истинное или тождественно ложное выражение). Отсюда мы заключаем, что во всех плотных упорядоченных множествах без первого и последнего элемента справедливы одни и те же формулы нашей сигнатуры. Как говорят, все такие множества элементарно эквивалентны с точки зрения нашей сигнатуры. (Другое доказательство этого факта можно получить, используя теорему Левенгейма-Сколема о счетной подмодели и теорему об изоморфизме счетных плотных линейно упорядоченных множеств без первого и последнего элементов.)
В частности, мы доказали, что для рациональных и действительных чисел истинны одни и те же формулы сигнатуры .
Еще одним побочным продуктом нашего рассуждения (как и других рассуждений об элиминации кванторов) является способ выяснить, будет ли данная замкнутая формула истинной или ложной в рассматриваемой интерпретации. Для этого надо привести ее к бескванторному виду и посмотреть, получится ли И или Л. Другими словами, элиминация кванторов устанавливает разрешимость элементарной теории рациональных чисел с отношениями равенства и порядка.
Элиминация кванторов остается возможной (и рассуждение даже немного упрощается), если рациональные (или действительные) числа рассматривать не только с равенством и порядком, но и со сложением и рациональными константами. В этом случае можно воспользоваться приведенной ранее схемой с конечным представительным набором термов. В самом деле, пусть — переменная, которую (вместе с квантором существования по ней) мы хотим элиминировать. Все атомарные формулы, ее содержащие, можно "разрешить" относительно , получив некоторое количество формул вида , и , где — линейные комбинации остальных переменных с рациональными коэффициентами. (Разрешение рациональных коэффициентов вместо целых ничего не меняет, так как можно привести все к общему знаменателю и получить целые коэффициенты, затем перенести отрицательные коэффициенты в другую часть, а положительные заменить многократным сложением.)
Затем в качестве представительного набора надо взять набор, состоящий, во-первых, из всех , во-вторых, из всех средних арифметических , и, наконец, из выражений и . Ясно, что как бы ни расположились точки на числовой оси, этот набор захватит как минимум по одной точке из каждого промежутка (средние арифметические нужны для интервалов, а прибавление и вычитание единицы — для лучей по краям).
65. Провести это рассуждение подробно.
Возможность элиминации кванторов в только что рассмотренной ситуации ( , рациональные константы) имеет интересное геометрическое применение.
Теорема 31. Пусть единичный квадрат разрезан на несколько меньших квадратов. Тогда все они имеют рациональные стороны.
Пусть дано такое разрезание с меньшими квадратами. Напишем формулу с параметрами ( из которых соответствуют размерам меньших квадратов, а — координатам их левых верхних углов), которая говорит, что эти параметры действительно задают разрезание квадрата (квадраты содержатся внутри единичного, не имеют общих точек и всякая точка единичного квадрата покрывается хотя бы одним из меньших квадратов). Навесив кванторы существования по переменным, задающим координаты, получим формулу с параметрами , которая истинна, когда из квадратов размеров можно составить единичный квадрат.
Элиминация кванторов позволяет считать, что формула
бескванторная, то есть представляет собой логическую комбинацию равенств и неравенств вида
и с различными рациональными коэффициентами. Посмотрим на все выражения, стоящие в левой части таких равенств и неравенств. Подставим в них числа , соответствующие данному нам разрезанию. При этом получится истинная формула , в которой некоторые из левых частей равенств и неравенств будут равны нулю, а другие нет. Временно забудем про те, которые не равны нулю, а равные нулю будем воспринимать как левые части уравнений с неизвестными (с нулем в правой части) независимо от того, входили ли они в как левые части уравнений или неравенств. Получится система уравнений, для которой числа будут решениями. Если эти числа являются единственными ее решениями, то они рациональны (например, потому, что правила Крамера для решения системы уравнений содержат отношения определителей с рациональными элементами). Покажем, что другого быть не может.
В самом деле, если решение не единственно, то есть целая прямая, проходящая через точку и лежащая в множестве решений системы. Все точки прямой, достаточно близкие к , неотличимы от с точки зрения формулы и потому делают формулу истинной. В самом деле, левые части, равные нулю в , равны нулю на всей прямой, а левые части, отличные от нуля в точке , сохраняют знак в некоторой окрестности этой точки. Пусть — направляющий вектор этой прямой. Тогда при всех достаточно малых значениях из квадратов размеров
можно составить единичный квадрат. Но это невозможно. Чтобы убедиться в этом, достаточно оставить логику и вернуться к геометрии: площади этих квадратов в сумме должны равняться , но площадь каждого есть многочлен второй степени по , и коэффициент при положителен, поэтому сумма таких многочленов не может тождественно равняться единице ни на каком интервале.
Насколько существенна в этом рассуждении ссылка на возможность элиминации кванторов? В принципе можно было бы рассуждать так. Пусть дано разрезание квадрата. Посмотрим на конфигурацию, образуемую меньшими квадратами, и напишем равенства и неравенства на размеры частей, которые гарантируют, что в этой конфигурации нет щелей и перекрытий. (Далее продолжаем рассуждение как раньше.) Конечно, возникает вопрос: почему мы уверены, что такую систему уравнений и неравенств можно написать? Глядя на конкретную конфигурацию, это сделать легко, но как провести это рассуждение строго для общего случая, не вполне понятно.
Изложенные методы позволяют провести элиминацию кванторов и описать выразимые множества во многих ситуациях; несколько простых примеров такого рода предлагаются в качестве задач. Два более сложных примера (арифметика Пресбургера и теория сложения и умножения действительных чисел) разбираются в двух следующих разделах.
66. Описать выразимые предикаты, проведя элиминацию кванторов (и расширив сигнатуру, если нужно) для (а), где — произвольное бесконечное множество; (б); (в), где — операция прибавления единицы; (г), где — операция прибавления единицы; (д), где — операция прибавления единицы, а — одноместный предикат "быть степенью двойки".
Невыразимые предикаты: автоморфизмы
Мы видели, как можно доказать выразимость некоторых свойств. Сейчас мы покажем, каким образом можно доказывать невыразимость.
Начнем с такого примера. Пусть сигнатура содержит двуместный предикат равенства () и двуместную операцию сложения (). Рассмотрим ее интерпретацию, носителем которой являются целые числа, а равенство и сложение интерпретируются стандартным образом. Оказывается, что предикат не является выразимым.
Причина очевидна: с точки зрения сложения целые числа устроены симметрично, положительные ничем не отличаются от отрицательных. Если мы изменим знак у всех переменных, входящих в формулу, то ее истинность не может измениться. Но при этом заменится на , и потому это свойство не является выразимым.
Формально говоря, надо доказывать по индукции такое свойство: если формула указанной сигнатуры истинна при оценке , то она истинна и при оценке , в которой значения всех переменных меняют знак. (Подробно мы объясним это в общей ситуации дальше.)
Сформулируем общую схему, которой следует это рассуждение. Пусть имеется некоторая сигнатура и интерпретация этой сигнатуры, носителем которой является множество . Взаимно однозначное отображение называется автоморфизмом интерпретации, если все функции и предикаты, входящие в интерпретацию, устойчивы относительно . При этом -местный предикат
называется устойчивым относительно , если
для любых элементов . Аналогичным образом -местная функция называется устойчивой относительно , если
Это определение обобщает стандартное определение автоморфизма для групп, колец, полей и т. д.
Теорема 27. Предикат, выразимый в данной интерпретации, устойчив относительно ее автоморфизмов.
Проведем доказательство этого (достаточно очевидного) утверждения формально.
Пусть — некоторая оценка, то есть отображение, ставящее в соответствие всем индивидным переменным некоторые элементы носителя. Через обозначим оценку, которая получится, если к значению каждой переменной применить отображение ; другими словами, для любой переменной .
Первый шаг состоит в том, чтобы индукцией по построению терма доказать такое утверждение: значение терма при оценке получается применением к значению терма при оценке :
Для переменных это очевидно, а шаг индукции использует устойчивость всех функций интерпретации относительно .
Теперь индукцией по построению формулы легко доказать такое утверждение:
Мы не будем выписывать эту проверку; скажем лишь, что взаимная однозначность используется, когда мы разбираем случай кванторов. (В самом деле, если с одной стороны изоморфизма берется какой-то объект, то взаимная однозначность позволяет взять соответствующий ему объект с другой стороны изоморфизма.)
Теорема 27 позволяет доказать невыразимость какого-то предиката, предъявив автоморфизм интерпретации, относительно которого интересующий нас предикат неустойчив. Вот несколько примеров:
Сигнатура содержит равенство и отношение порядка. Интерпретация: целые числа. Невыразимый предикат: . Автоморфизм: .
Сигнатура содержит равенство, отношение порядка и операцию сложения. Интерпретация: рациональные числа. Невыразимый предикат: . Автоморфизм: .
Заметим, что сложение позволяет выразить предикат . Кроме того, отметим, что вместо рациональных чисел можно взять действительные (но не целые, так как в этом случае единица описывается как наименьшее число, большее нуля).
Сигнатура содержит равенство, порядок и константы
и . Интерпретация: действительные числа. Невыразимый предикат: . (Автоморфизм упорядоченного множества , сохраняющий и , но не , построить легко.) \end{specialparenv}
Сигнатура содержит равенство, сложение, константы
и . Интерпретация: действительные числа. Одноместный предикат выразим для рациональных и невыразим для иррациональных .
В самом деле, выразимость для рациональных очевидна. Невыразимость для иррациональных следует из того, что для любых двух иррациональных и
существует автоморфизм, переводящий в . (В самом деле, рассмотрим как бесконечномерное векторное пространство над . Векторы линейно независимы и потому их можно дополнить до базиса Гамеля (подробности смотри в книжке по теории множеств [6]). Сделаем то же самое с векторами . Получатся равномощные базисы, после чего мы берем -линейный оператор, переводящий в и в .)
В сигнатуру входят предикат равенства, операции сложения и умножения, а также константы и . Интерпретация: комплексные числа. Предикат , где — некоторое комплексное число, выразим для рациональных и невыразим для иррациональных .
В самом деле, если иррационально, то оно может быть алгебраическим или трансцендентным. В первом случае рассмотрим многочлен из минимальной степени, обращающийся в в точке ; по предположению он имеет степень больше и потому имеет другой корень . В алгебре доказывается (с использованием трансфинитной индукции или леммы Цорна, а также базисов трансцендентности), что существует автоморфизм
над , переводящий в .
В случае трансцендентного мы используем такой факт: для любых трансцендентных
существует автоморфизм поля над , который переводит в .
Отметим, что для поля вместо такое рассуждение не проходит, так как это поле не имеет нетривиальных автоморфизмов. (Отношение порядка выразимо: положительные числа суть квадраты, поэтому любой автоморфизм сохраняет порядок. Поскольку автоморфизм оставляет на месте все рациональные числа, он должен быть тождественным.)
В этом случае предикат выразим тогда и только тогда, когда — алгебраическое число. Это легко следует из теоремы Тарского-Зайденберга.
61. Покажите, что предикат невыразим в интерпретации , где — одноместная функция .
62. Покажите, что предикат невыразим в множестве целых положительных чисел с предикатами равенства и " делит ".
Выразимость в арифметике
Рассмотрим сигнатуру, имеющую два двуместных функциональных символа — сложение и умножение (как обычно, мы будем писать вместо и т. д.) и двуместный предикатный символ равенства. Рассмотрим интерпретацию этой сигнатуры, носителем которой является множество натуральных чисел, а сложение, умножение и равенство интерпретируются стандартным образом.
Выразимые с помощью формул этой сигнатуры предикаты называются арифметическими и играют в математической логике важную роль. Соответствующие множества также называются арифметическими. О них подробно рассказано в другой нашей книжке [5]; оказывается, что почти всякое множество, которое можно описать словами, является арифметическим.
58. Докажите, что существует множество натуральных чисел, не являющееся арифметическим. (Указание: семейство всех подмножеств множества несчетно, а арифметических множеств счетное число.)
Для начала мы установим арифметичность довольно простых предикатов.
Предикат является арифметическим. В самом деле, его можно записать как .Предикаты и являются арифметическими. В самом деле, тогда и только тогда, когда для любого (а также когда ). А тогда и только тогда, когда представляет собой наименьшее число, отличное от нуля. (Можно также воспользоваться тем, что при любом .)Вообще для любого фиксированного числа предикат является арифметическим. (Например, можно написать сумму из большого числа единиц.)Полезно такое общее наблюдение: если мы уже установили, что какой-то предикат является арифметическим, то в дальнейшей его можно использовать в формулах, как если бы он входил в сигнатуру, поскольку его всегда можно заменить на выражающую его формулу.Предикат (число является делителем числа ), очевидно, арифметичен (формула ).Предикат " — простое число" арифметичен. В самом деле, число просто, если оно отлично от и любой его делитель равен или самому числу. Это сразу же записывается в виде формулы.Операции частного и остатка арифметичны (в том смысле, что трехместные предикаты " есть частное при делении на " и " есть остаток при делении на " арифметичны.
Например, первый из них записывается формулой
( как мы уже говорили, использование арифметического предиката не создает проблем).Этот список можно продолжать: для многих предикатов их определение по существу уже является нужной формулой. Например, свойства "быть наибольшим общим делителем", "быть наименьшим общим кратным", "быть взаимно простыми" все относятся к этой категории.Предикат "быть степенью двойки" является арифметическим (хотя это и не столь очевидно, как в предыдущих примерах). В самом деле, это свойство можно переформулировать так: любой делитель либо равен единице, либо четен.
Последнее из наших рассуждений годится для степеней тройки и вообще для степеней любого простого числа. Однако, скажем, для степеней шестерки оно не проходит, и, пожалуй, мы подошли к границе, где без некоторого общего метода не обойтись.
Два наиболее известных способа доказывать арифметичность основаны на возможности "кодирования" конечных множеств и последовательностей. Один восходит к Геделю (так называемая -функция Геделя), второй изложен в книге "Теория формальных систем" [24]. Ее написал Р.Смаллиан, известный также как автор популярных сборников "логических задач" и анекдотов. (Один из таких сборников имеет парадоксальное название "Как же называется эта книга?" [23].)
В некоторых отношениях метод Геделя предпочтительней, и мы рассказываем о нем в книжке о вычислимых функциях [5], но сейчас для разнообразия рассмотрим другой способ. Зафиксируем взаимно однозначное соответствие между натуральными числами и двоичными словами:
Это соответствие задается так: чтобы получить слово, соответствующее числу , надо записать в двоичной системе и удалить первую единицу. Например, нулю соответствует пустое слово , числу — слово и т. д. Теперь можно говорить об арифметичности предикатов, определенных на двоичных словах, имея в виду арифметичность соответствующих предикатов на .
Предикат "слово состоит из одних нулей" арифметичен.
В самом деле, при переходе к числам ему соответствует предикат " есть степень двойки", который (как мы видели) арифметичен.Предикат "слова и имеют одинаковую длину" арифметичен. В самом деле, это означает, что найдется степень двойки , для которой (именно такой промежуток заполняют числа, которым соответствуют слова одной длины).Предикат "слово является конкатенацией слов и " (проще говоря, получается приписыванием справа к слову ) арифметичен. В самом деле, его можно выразить так: найдется слово из одних нулей, имеющее ту же длину, что и слово , при этом (умножение на соответствует дописыванию нулей, а добавление заменяет нули на буквы слова ).Предикат "слово является началом слова " арифметичен. В самом деле, это означает, что существует слово , при котором есть конкатенация и .То же самое верно для предикатов " есть конец слова ", " есть подслово слова " (последнее означает, что найдутся слова и , для которых
есть конкатенация , и ; конкатенация трех слов выразима через конкатенацию двух).
Существует арифметический трехместный предикат с такими свойствами: (а) для любых и
множество
конечно; (б) среди множеств при различных парах встречаются все конечные множества. Например, в качестве такого предиката можно взять " есть подслово слова " (здесь есть конкатенация трех слов: , и снова ).
В самом деле, ясно, что слово не длиннее слова , и потому множество всегда конечно. С другой стороны, пусть имеется некоторое конечное множество слов . Положим , где число нулей больше длины любого из слов , и .
Последнее утверждение не упоминает явно о словах, и больше они нам не понадобятся: достаточно знать, что конечные множества натуральных чисел можно кодировать парами натуральных чисел в описанном смысле.
Теперь мы можем выразить, что число является степенью числа , следующим образом: существует конечное множество , которое содержит число и обладает таким свойством: всякий элемент либо равен , либо делится на и
также принадлежит . Теперь надо везде заменить множество на его код , а утверждение на , где — построенный нами кодирующий предикат.
Немного сложнее выразить двуместный предикат . Здесь нам хотелось бы сказать так: существует последовательность , для которой , каждый следующий член вчетверо больше предыдущего () и . Как научиться говорить о последовательностях, если мы умеем говорить о множествах? Вспомним, что в терминах теории множеств последовательность есть функция, определенная на начальном отрезке натурального ряда, то есть конечное множество пар . Пары можно кодировать числами. Например, можно считать кодом пары число , поскольку по нему арифметически восстанавливается (как наибольшее число, квадрат которого не превосходит ), а затем и . Теперь конечное множество пар можно заменить конечным множеством их кодов, которое в свою очередь можно закодировать парой чисел.
59. Проведите это рассуждение подробно.
60. Покажите, что двуместный предикат " есть -ое по порядку простое число" арифметичен.
Арифметика Пресбургера
В этом разделе мы описываем выразимые множества в . Отметим сразу же, что с такой сигнатурой элиминация кванторов невозможна. В самом деле, формула
истинная для четных , не эквивалентна никакой бескванторной формуле. Поэтому нам нужно, прежде чем проводить элиминацию кванторов, расширить сигнатуру. Приведенный пример формулы подсказывает, какое расширение нам необходимо. Рассмотрим счетное семейство двуместных предикатных символов Символ будет интерпретироваться как равенство по модулю . Другими словами, формула будет истинна в нашей интерпретации, если сравнимо с по модулю (остатки по модулю равны; кратно ).
Важно иметь в виду, что индекс в не является переменной: у нас не трехместный предикат, а счетное семейство двуместных предикатов.
Такое расширение не меняет класса выразимых предикатов, поскольку, например, можно выразить как . Зато после этого всякая формула эквивалентна бескванторной, как показывает следующая теорема (называемая теоремой об элиминации кванторов в арифметике Пресбургера).
Теорема 32. В выполнима элиминация кванторов.
Мы будем применять метод, опробованный в предыдущем разделе: выбор представительного множества термов (после некоторых преобразований формулы).
Напомним, как это делается. Мы хотим доказать, что всякая формула эквивалентна бескванторной. Рассуждая по индукции, мы должны лишь проверить, что всякая формула вида
где обозначает бескванторную формулу, все переменные которой содержатся среди , эквивалентна некоторой бескванторной формуле (с теми же переменными, не считая ).
Посмотрим, какие атомарные формулы, содержащие переменную , входят в . Перенося члены в одну сторону, эти атомарные формулы можно записать в одном из трех видов: , или , где представляет собой линейную комбинацию переменных с целыми коэффициентами и целочисленным свободным членом. (В отличие от ситуации в , здесь нельзя делить на коэффициент при .) Перенося в левую часть, а все остальное — в правую, получаем соотношение одного из четырех видов:
где — положительное целое число (разное для разных атомарных формул), а — линейная комбинация переменных с целыми коэффициентами и свободным членом.
Как мы говорили, коэффициенты в левой части ( а также, разумеется, правые части) у разных атомарных формул разные. Однако мы можем их унифицировать, перейдя к общему кратному. В самом деле, неравенства и равенства можно умножать на число, сравнения — тоже, если модуль сравнения (индекс в ) умножить на то же самое число. Поэтому можно считать, что наша формула имеет вид , понимая под этим, что появляется только в левых частях и везде с коэффициентом . Такую формулу можно переписать как Таким образом, без ограничения общности можно считать, что , поскольку новая формула имеет тот же самый вид
что и исходная, но уже безо всякого коэффициента при (и с модифицированной формулой ). Пусть — выражения, стоящие в правых частях равенств, неравенств и сравнений с левой частью .
Мы хотим, как и в предыдущем разделе, указать представительный набор значений . Каждое из представляет собой линейную комбинацию переменных с целыми коэффициентами и свободным членом. "Представительность" означает, что если для каких-то найдется , для которого
то такой можно найти и среди значений (при тех же ).
Чтобы указать представительный набор, разделим все атомарные формулы в , содержащие , на два типа — сравнения по модулю и остальные (равенства и неравенства). Посмотрим, по каким модулям проводятся сравнения. Пусть — общее кратное всех этих модулей. В этом случае изменение значения переменной на величину, кратную , не влияет на результаты сравнений. Теперь возьмем все выражения, встречающиеся в правых частях равенств или неравенств, и будем прибавлять к ним всевозможные целые числа из отрезка от до . Это и будет представительный набор. Другими словами, в представительный набор входят все выражения , где — одна из правых частей равенств или неравенств, содержащих в левой части, а — целое число, не превосходящее по абсолютной величине.
Покажем, что полученный набор действительно будет представительным. Пусть при данных найдется некоторое , для которого . Посмотрим, какие значения принимают правые части равенств и неравенств при данных .
Если значение попало в объединение - окрестностей этих значений, то доказывать нечего. Если же нет, начнем смещать , двигаясь шагами размера в направлении какой-то точки из этого объединения. Миновать мы ее не можем (ширина окрестности равна , а размер шага равен ), поэтому в какой-то момент мы впервые попадем в это объединение. Обозначим эту точку (первую попавшую в объединение) через . Тогда при подстановке в дает те же самые результаты, что и . В самом деле, для сравнений это гарантировано, потому что сдвиг кратен модулю сравнений. Но это верно и для равенств и неравенств, поскольку на предыдущем шаге мы были вне -окрестности всех правых частей и потому не могли перейти с одной стороны на другую.
Таким образом, среди представительного набора есть значение (а именно, ), удовлетворяющее формуле , что и требовалось доказать.
Итак, мы получили ответ на интересующий нас вопрос: выразимые в арифметике Пресбургера предикаты — это предикаты, выразимые бескванторными формулами, содержащими целые константы, сложение, равенство, отношение порядка и сравнения по любым фиксированным модулям.
Элементарная эквивалентность
Пока что мы в основном использовали технику элиминации кванторов для какой-то одной интерпретации (формула заменялась на бескванторную, которая эквивалентна исходной в данной интерпретации). Однако, этот метод позволяет сравнивать различные интерпретации. Мы приведем несколько примеров такого рода.
Начнем с определения. Пусть фиксирована некоторая сигнатура . Две интерпретации этой сигнатуры называются элементарно эквивалентными, если в них истинны одни и те же замкнутые формулы этой сигнатуры.
Легко доказать, что изоморфные интерпретации будут элементарно эквивалентны — надо только дать формальное определение изоморфизма для двух интерпретаций данной сигнатуры.
Пусть и — две интерпретации сигнатуры . Биекция (взаимно однозначное отображение) называется изоморфизмом этих интерпретаций, если она сохраняет все функции и предикаты сигнатуры. Это означает, что если и — два -местных предиката в и , соответствующих одному предикатному символу сигнатуры, то
для всех . Аналогичное условие для функций: если -местные функции и соответствуют одному функциональному символу, то
для всех .
Две интерпретации называются изоморфными, если между ними существует изоморфизм.
Легко понять, что это определение обобщает обычные определения изоморфизма для групп, колец, упорядоченных множеств и т. д.
73. Докажите, что тождественное отображение есть изоморфизм. Докажите, что отображение, обратное изоморфизму, есть изоморфизм. Докажите, что композиция двух изоморфизмов есть изоморфизм. (Отсюда следует, что отношение изоморфности есть отношение эквивалентности на интерпретациях данной сигнатуры.)
Теперь можно сформулировать и доказать обещанное утверждение:
Теорема 35. Изоморфные интерпретации элементарно эквивалентны.
Естественно доказывать это утверждение по индукции. Для этого его надо обобщить на произвольные формулы (не только замкнутые). Вот это обобщение: пусть — изоморфизм, а — произвольная формула нашей сигнатуры. Тогда она истинна в при оценке тогда и только тогда, когда она истинна в при оценке .
Обычно истинность формулы в интерпретации
обозначают как . Если формула имеет параметры , ее часто обозначают ; при этом запись (где ) означает, что формула истинна при оценке, которая ставит в соответствие параметру значение . После всех этих приготовлений доказываемое по индукции утверждение можно записать так:
для любой формулы и для любых элементов .
После такого обобщения доказательство по индукции становится очевидным.
74. В каком месте индуктивного рассуждения существенно, что — взаимно однозначное соответствие? (Ответ: сюръективность используется, когда мы рассматриваем формулу, начинающуюся с квантора существования, и из ее истинности в выводим истинность в . Инъективность не используется, но она автоматически следует из определения изоморфизма, если сигнатура содержит равенство и интерпретации нормальны, то есть равенство интерпретируется как совпадение элементов.)
75. Рассуждение, использованное при доказательстве теоремы 35, нам по существу уже встречалось. Где?
Изоморфные интерпретации — это по существу одна и та же интерпретация, только ее элементы названы по-разному. Интересны скорее примеры, когда интерпретации не изоморфны, но тем не менее элементарно эквивалентны. Один такой пример мы уже коротко обсуждали раньше, сформулируем его более подробно.
Теорема 36. Естественные интерпретации сигнатуры в множестве рациональных и действительных чисел элементарно эквивалентны.
Для начала заметим, что эти интерпретации не изоморфны (поскольку мощности различны). Однако формулы этой сигнатуры допускают, как мы видели , элиминацию кванторов.При этом получающаяся формула будет эквивалентна исходной в обеих интерпретациях. Начав с замкнутой формулы, мы получим бескванторную формулу без переменных (или с фиктивными переменными, от значений которых ничего не зависит, тогда вместо них можно подставить, скажем, нули). Эта формула будет содержать только рациональные константы и потому будет одинаково истинной в и в .
Заметим, что при уменьшении сигнатуры элементарная эквивалентность сохраняется (по очевидным причинам), так что из теоремы 36 очевидно следует, что и
элементарно эквивалентны как упорядоченные множества (этот факт мы отмечали).
В этом примере элементарно эквивалентные, но не изоморфные структуры имеют различную мощность. В следующем примере это уже не так.
Теорема 37. Упорядоченные множества и (второе состоит из двух копий множества , причем все элементы первой копии считаются меньшими всех элементов второй копии) элементарно эквивалентны как интерпретации сигнатуры .
Здесь также можно применить элиминацию кванторов, только надо добавить одноместные функции взятия последующего и предыдущего элементов. После этого надо заметить, что стандартная процедура элиминации кванторов (см. доказательство теоремы 29) состоит из преобразований, сохраняющих эквивалентность в обеих интерпретациях.
76. Можно ли построить счетную интерпретацию сигнатуры , в которой равенство интерпретируется как совпадение элементов (такие интерпретации называют нормальными), элементарно эквивалентную множеству , но не изоморфную ему? Тот же вопрос для множества неотрицательных рациональных чисел. Почему существенна нормальность интерпретации?
77. Существует ли упорядоченное множество, элементарно эквивалентное упорядоченному множеству , но имеющее большую мощность?
78. Существуют ли два несчетных неизоморфных элементарно эквивалентных упорядоченных множества одинаковой мощности?
79. Будут ли упорядоченные множества
и
(пары целых чисел; сравниваются сначала вторые компоненты пар, а при их равенстве — первые) изоморфны? элементарно эквивалентны?
80. Будет ли упорядоченное множество элементарно эквивалентно ? Будет ли элементарно эквивалентно ?
Рассуждение, использованное при доказательстве теоремы Тарского-Зайденберга, также можно приспособить для доказательства элементарной эквивалентности. Сейчас мы рассмотрим более простой случай алгебраически замкнутых полей, соответствующий элиминации кванторов в ; к вещественному случаю мы вернемся.
Поле называется алгебраически замкнутым, если всякий многочлен, отличный от константы, имеет в нем хотя бы один корень. (Отсюда легко следует, что любой многочлен разлагается на линейные множители.) Характеристикой поля называют минимальное число слагаемых в сумме вида , при котором она обращается в нуль. Если никакая сумма такого вида не равна нулю, то поле называют полем характеристики .
В алгебраически замкнутых полях характеристики
справедливы все обычные свойства многочленов с комплексными коэффициентами. В частности, корень является кратным тогда и только тогда, когда он будет корнем производной, сумма корней с учетом кратности равна степени многочлена и т. д. Это позволяет заметить, что все преобразования, которые выполнялись при элиминации кванторов, являются эквивалентными в произвольных алгебраически замкнутых полях характеристики . Тем самым мы получаем такую теорему:
Теорема 38 (о полноте теории алгебраически замкнутых полей характеристики нуль) Любые два алгебраически замкнутых поля характеристики
элементарно эквивалентны.
(Название этой теоремы станет понятным, когда мы будем говорить о полных теориях.)
81. Покажите, что любые два алгебраически замкнутых поля одной и той же конечной характеристики элементарно эквивалентны.
Теорему 38 можно несколько усилить. Для этого нам понадобится понятие "элементарного расширения".
Пусть фиксирована сигнатура и две интерпретации этой сигнатуры с носителями и . Пусть при этом и интерпретации предикатных и функциональных символов в и согласованы, то есть на аргументах из символы интерпретируются одинаково. (Заметим, что отсюда следует замкнутость относительно сигнатурных операций.) В этом случае иногда называют подструктурой в , а — расширением .
Например, если мы рассматриваем группы как интерпретации сигнатуры , то подструктуры — это подгруппы.
82. Почему здесь важно, что операция обращения включена в сигнатуру?
Интерпретацию называют элементарным расширением ее подструктуры , если выполнено такое свойство: для всякой (не обязательно замкнутой формулы) и для всякой оценки со значениями в формула истинна в на этой оценке тогда и только тогда, когда она истинна в на той же оценке.
В частности, если формула замкнута (не содержит параметров), то ее истинность не зависит от оценки и мы получаем, что и элементарно эквивалентны.
83. Пусть сигнатура содержит константы для всех элементов интерпретации , которая является подструктурой интерпретации . Покажите, что если интерпретации
и элементарно эквивалентны, то является элементарным расширением .
Нам понадобится такой пример: пусть имеется поле и его расширение . Мы будем рассматривать поля
и как две интерпретации сигнатуры . Пусть имеется некоторая система полиномиальных уравнений с несколькими переменными с коэффициентами из . Тогда утверждение о том, что она имеет решение, записывается в виде формулы (содержащей кванторы существования по переменным и конъюнкцию уравнений; коэффициенты многочленов являются параметрами этой формулы). Поэтому если является элементарным расширением , то всякая система уравнений с коэффициентами в , имеющая решение в , имеет решение и в .
Теорема 39. Пусть — подполе поля , причем оба они алгебраически замкнуты и имеют характеристику . Тогда
(как интерпретация указанной сигнатуры) является элементарным расширением интерпретации .
В самом деле, элиминация кванторов преобразует любую формулу (с параметрами или без) в эквивалентную ей бескванторную, причем эквивалентность имеет место в обоих полях. А для бескванторной формулы ее истинность при оценке со значениями в никак не может зависеть от того, внутри какого поля эта истинность вычисляется.
Эту теорему называют теоремой о модельной полноте теории алгебраически замкнутых полей характеристики нуль. Из нее с учетом замечания перед ее формулировкой вытекает такой хорошо известный алгебраистам факт:
Теорема 40 (Гильберта о нулях). Всякая система полиномиальных уравнений с коэффициентами в алгебраически замкнутом поле характеристики нуль, имеющая решение в некотором расширении этого поля, имеет решение и в самом поле.
В самом деле, расширение можно еще расширить до алгебраически замкнутого (при этом решение не пропадет), а затем воспользоваться теоремой 39.
84. Другой вариант теоремы Гильберта о нулях формулируется так: пусть дана система уравнений
где все — многочлены с комплексными коэффициентами, причем эта система не имеет решения в . Тогда можно найти такие многочлены , что
тождественно равно единице.
Выведите это утверждение из доказанного нами варианта теоремы Гильберта о нулях. (Указание: рассмотрим в кольце
идеал, порожденный многочленами ; если он содержит единицу, то все доказано, если нет, то расширим его до максимального идеала ; тогда факторкольцо
будет полем, расширяющим , и в этом поле классы многочленов составляют решение нашей системы.)
Теорема Тарского-Зайденберга
В этом разделе мы покажем, что в элементарной теории действительных чисел со сложением и умножением выполнима элиминация кванторов. Более точно, рассмотрим сигнатуру, содержащую предикаты и , константы и , а также операции сложения и умножения. Рассмотрим интерпретацию этой сигнатуры, носителем которой является множество действительных чисел, а предикаты и операции понимаются естественным образом. Тогда для каждой формулы существует эквивалентная (выражающая тот же предикат) бескванторная формула. Это утверждение называют теоремой Тарского-Зайденберга.
Прежде чем доказывать эту теорему, сделаем несколько комментариев:
Свойство можно выразить как "существует ненулевое , для которого ". Таким образом, класс выразимых предикатов не изменится, если мы удалим символ из сигнатуры. (Но предикатов, выразимых бескванторными формулами, станет меньше: свойство , как легко понять, не эквивалентно никакой бескванторной формуле, содержащей константы, сложение, умножение и равенство.)Бескванторную формулу нашей сигнатуры можно привести к дизъюнктивной нормальной форме, после чего она превратится в совокупность систем уравнений вида и неравенств вида . В самом деле, в конъюнкциях могут еще быть отрицания, то есть отношения и , но можно разбить на , а на , после чего воспользоваться дистрибутивностью.Подмножества , задаваемые уравнениями вида и неравенствами вида (где — произвольный многочлен от нескольких переменных с целыми коэффициентами), а также множества, получаемые из них любым числом операций объединения и пересечения, называют полуалгебраическими. Предыдущее замечание показывает, что всякая бескванторная формула задает полуалгебраическое множество. (Полуалгебраические множества являются обобщениями алгебраических множеств, задаваемых системами полиномиальных уравнений.)Из теоремы Тарского-Зайденберга вытекает, что проекция полуалгебраического множества вдоль одной из осей является полуалгебраическим подмножеством пространства . В самом деле, переход к проекции приводит к добавлению квантора существования, который можно затем элиминировать. (Утверждение о полуалгебраичности проекции полуалгебраического множества по существу равносильно теореме Тарского-Зайденберга, так как элиминация квантора существования является единственным нетривиальным шагом в доказательстве этой теоремы.)Пример: равенство задает полуалгебраическое (и даже алгебраическое) множество троек .
Какова будет его проекция вдоль оси на плоскость ? Как учат в школе, это будет множество , которое оказывается полуалгебраическим в полном согласии с теоремой Тарского-Зайденберга. Про аналогичные критерии разрешимости уравнений большей степени в школе не учат, но теорема Тарского-Зайденберга гарантирует их существование.Как и во всех предыдущих случаях элиминации кванторов, преобразование формулы в бескванторную формулу эффективно (выполняется некоторым алгоритмом). В частности, этот алгоритм можно применить к замкнутой формуле (формуле без параметров). Тогда получится бескванторная формула без параметров (формально говоря, там могут быть параметры, от значений которых ничего не зависит, но их можно заменить, скажем, нулями). Истинность такой формулы можно алгоритмически проверить. Тем самым можно алгоритмически проверить истинность любого утверждения о действительных числах, выраженного формулой нашей сигнатуры. Как говорят, элементарная теория действительных чисел со сложением и умножением разрешима.Большинство утверждений школьного курса геометрии с помощью метода координат можно записать как утверждения о действительных числах в нашей сигнатуре. (Исключение, впрочем, составляют утверждения, где речь идет не о треугольниках и четырехугольниках, а о - угольниках без указания конкретного ). Записав теоремы в виде замкнутых формул нашей сигнатуры, можно алгоритмически проверить их истинность. Тем самым мы получаем общий метод доказательства большинства теорем школьной геометрии (впрочем, он имеет лишь теоретическое значение, так как алгоритм работает необозримо долго на сколько-нибудь сложных формулах).
Теорема 33 (Тарского-Зайденберга). Для всякой формулы сигнатуры существует бескванторная формула, задающая тот же предикат на множестве действительных чисел.
Как обычно, достаточно рассматривать формулу с единственным квантором существования, то есть формулу вида
где — бескванторная формула, включающая в себя только переменные из числа . Надо доказать, что найдется эквивалентная формуле
бескванторная формула .
Посмотрим на атомарные формулы, входящие в формулу . Перенося все переменные в одну часть, можно считать, что каждая атомарная формула имеет вид или , где — некоторый многочлен с целыми коэффициентами от переменных . Кольцо многочленов с целыми коэффициентами от переменных обозначается через . Группировка членов по степеням переменной дает многочлен от , коэффициенты которого представляют собой многочлены от . Символически это записывается так:
(многочлены от переменных можно рассматривать как многочлены от одной переменной, коэффициенты которых лежат в кольце многочленов от переменных).
При фиксации значений переменных входящие в многочлены превращаются в многочлены от одной переменной с числовыми коэффициентами. Формула выражает тогда какое-то свойство этих многочленов и может быть истинной или ложной. Нам надо доказать, что те , при которых она истинна, образуют полуалгебраическое множество.
Для этого введем понятие диаграммы семейства многочленов. Пусть — многочлены от
с действительными коэффициентами. Диаграммой набора будет таблица, которая строится так. Возьмем все корни всех многочленов (не считая нулевых многочленов) и расположим их в порядке возрастания. Получим некоторый набор чисел . Эти числа разбивают числовую ось на промежутков (два луча и
интервалов), на каждом из которых знаки всех постоянны. Составим таблицу, в которой будет строк (по одной для каждого из многочленов) и столбцов, соответствующих
корням и промежуткам (столбцы идут в порядке возрастания, так что корни чередуются с промежутками). В каждой ячейке таблицы запишем один из трех символов , или в зависимости от того, является ли многочлен положительным, отрицательным или нулевым на соответствующем промежутке (или в соответствующем корне).
Пример. Выпишем диаграмму для системы многочленов , , . Корнями здесь будут числа , , , так что столбцы соответствуют четырем промежуткам и трем разделяющим их корням.
Отметим, что значения корней не являются частью диаграммы, так что, например, система многочленов , , имеет точно такую же диаграмму.
Если ни один из многочленов не имеет корней, то они сохраняют знак на всей прямой, и диаграмма состоит из единственного столбца, в котором записаны все эти знаки.
Теперь рассмотрим набор многочленов . При фиксированных значениях переменных мы получаем набор многочленов от одной переменной с действительными коэффициентами и можем построить его диаграмму. Эта диаграмма будет зависеть от выбора значений . Число строк в диаграмме равно , а ширина ее зависит от числа различных корней и может меняться, однако во всех случаях не превосходит , где — сумма степеней всех многочленов (рассматриваются степени по , то есть степени соответствующих многочленов от с коэффициентами в ).
Таким образом, число возможных диаграмм конечно, и пространство возможных значений переменных
разбивается на конечное число частей: каждая часть соответствует одному из возможных значений диаграммы.
Для доказательства теоремы Тарского-Зайденберга достаточно доказать, что эти части будут полуалгебраическими множествами. В самом деле, если в качестве многочленов
взять многочлены, входящие в формулу , то область истинности формулы
будет объединением нескольких частей соответствующего разбиения. В самом деле, если мы двигаем точку
в пределах одной части разбиения, то диаграмма не меняется, значит, и истинность формулы не меняется (по диаграмме можно определить истинность формулы, перепробовав значения , соответствующие всем столбцам).
Итак, нам осталось доказать, что для любого набора многочленов части пространства , соответствующие различным значениям диаграммы, являются полуалгебраическими множествами. Начнем с такого очевидного наблюдения: если это верно для какого-то набора , то это останется верным и для любого меньшего набора. В самом деле, диаграмму меньшего семейства многочленов можно получить из диаграммы большего семейства: выкидывая многочлен, надо выбросить соответствующую строку, а также столбцы, которые соответствовали корням этого многочлена (если они не были корнями других многочленов).
При выбрасывании столбца два окружающих его столбца сливаются в один.
Поэтому мы имеем право для удобства расширить данный нам набор многочленов и доказывать полуалгебраичность частей для расширенного набора. Расширение будет состоять в замыкании относительно некоторых операций, которые мы сейчас опишем.
Напомним еще раз, что мы рассматриваем семейство многочленов из , которые разложены по степеням , то есть записаны как многочлены от с коэффициентами в . Рассмотрим следующие операции:
отбрасывание старшего члена (с наибольшей степенью переменной ); эта операция понижает степень (по ) на единицу;взятие старшего коэффициента (коэффициента при наибольшей степени переменной ); эта операция понижает степень (по ) до нуля;дифференцирование по ; эта операция понижает степень (по ) на единицу;взятие модифицированного остатка при делении одного многочлена на другой.
Говоря о "модифицированном остатке", мы имеем в виду следующее. При делении "уголком" многочлена на многочлен с остатком нам неоднократно приходится делить на старший коэффициент многочлена . Поэтому в общем случае коэффициенты частного и остатка представляют собой дроби, в знаменателях которых стоят некоторые степени старшего коэффициента многочлена .
Тем самым при вычислении остатка от деления
на мы выходим за пределы кольца . Этого не случится, если старший коэффициент многочлена равен единице. Но в общем случае мы должны принять какие-то меры, если хотим оставаться в указанном кольце. Меры эти состоят в следующем: прежде чем делить на , мы умножаем на старший коэффициент многочлена в достаточно большой степени. Если вспомнить процедуру деления уголком, легко сообразить, что достаточно взять степень , где и — степени многочленов и (по переменной ). Например, при требуется всего один шаг деления, и достаточно умножить на старший коэффициент многочлена в первой степени.
Итак, операция модифицированного остатка применима к любым двум многочленам степеней и (по ) и дает третий многочлен этого кольца, который есть остаток от деления на
(здесь — старший коэффициент многочлена ). Заметим, что степень этого многочлена меньше степени многочлена . Мы будем предполагать, что (иначе остаток совпадает с и деление не дает ничего нового). Таким образом, результат этой операции имеет меньшую степень, чем оба операнда.
Заметим, что определение модифицированного остатка имеет смысл для многочленов с коэффициентами из произвольного кольца (не только ).
Лемма 1. Для всякого конечного множества
многочленов из существует его конечное расширение, замкнутое относительно указанных четырех операций.
Это утверждение верно для любого кольца коэффициентов и почти очевидно следует из того, что степень результата операции меньше степени (любого) операнда. Более формально рассуждать надо так. Рассмотрим выражения, составленные из элементов с помощью четырех указанных операций. Глубина такого выражения не превосходит максимальной степени многочленов из , поскольку каждая операция уменьшает степень. Поэтому таких выражений конечное число, и их множество очевидным образом замкнуто относительно указанных операций. Лемма 1 доказана.
Доказанная лемма позволяет без ограничения общности считать, что данное нам конечное множество многочленов замкнуто относительно четырех указанных выше операций.
Лемма 2. Пусть — конечное множество многочленов из , замкнутое относительно перечисленных операций. Пусть — его часть, состоящая только из многочленов степени по (они представляют собой многочлены из ). Тогда диаграмма множества
при данных полностью определяется диаграммой множества при тех же .
Заметим, что диаграмма множества имеет всего один столбец, указывающий, какие из многочленов положительны, какие отрицательны и какие равны нулю при данных . Поэтому различным вариантам диаграммы для множества
соответствуют полуалгебраические подмножества в , и из леммы 2 следует, что те же самые множества составят искомое разбиение для полной системы . Таким образом, нам осталось лишь доказать лемму 2.
Будем добавлять в множество многочлены по одному, в порядке возрастания (неубывания) их степеней, пока не получим все множество .
Достаточно показать, что на каждом шаге диаграмма расширенного множества (с новым многочленом) может быть однозначно восстановлена по диаграмме предыдущего множества. Мы сейчас опишем, как это делается.
Пусть добавляется многочлен , при этом многочлены всех меньших степеней из уже есть в диаграмме. В силу замкнутости старший коэффициент многочлена содержится в и, имея меньшую (нулевую) степень, уже представлен в диаграмме. (Соответствующая строка состоит из одинаковых знаков, так как он не зависит от .) Если там стоят нули, то (при данных ) старший коэффициент равен нулю, и многочлен совпадает с многочленом, получающимся при отбрасывании старшего члена. Этот многочлен тоже есть в и в диаграмме, так что надо лишь продублировать соответствующую строку.
Итак, достаточно рассмотреть случай, когда старший коэффициент многочлена (при данных ) не равен нулю. Пополнение диаграммы включает в себя два шага: сначала мы должны определить знаки многочлена в точках (корнях), уже входящих в диаграмму. Затем надо пополнить диаграмму корнями многочлена
(при этом число столбцов в ней увеличится).
Как найти знак многочлена в одной из старых точек? По определению диаграммы в этой точке (обозначим ее ) один из старых многочленов равен нулю. Пусть — такой многочлен. Можно считать, что старший коэффициент (как многочлена от ) отличен от нуля при данных . Если это не так, заменим на многочлен, получающийся отбрасыванием старшего члена. Мы знаем, что множество замкнуто относительно четырех операций и что все многочлены из , имеющие меньшую степень, уже входят в диаграмму. Поэтому вся необходимая информация для отбора подходящего у нас есть.
Кроме того, по тем же причинам нам известен знак старшего коэффициента многочлена . Применим операцию модифицированного деления с остатком к и :
(здесь — старший коэффициент многочлена ). Подставим в это равенство число . При этом обратится в нуль, так как является корнем по построению. Многочлен входит в диаграмму в силу наших предположений, так что его знак в точке нам известен, как и знак .
Тем самым можно найти знак .
Итак, мы определили знак нового многочлена в старых корнях. Покажем, что этого достаточно, чтобы предсказать, на каких участках диаграммы появятся новые корни (многочлена ). При этом нам пригодится (пока что не использованная) операция дифференцирования.
Если в двух соседних старых корнях ,
многочлен имеет один и тот же знак (скажем, положителен), то между ними нет нового корня. В самом деле, если бы на интервале многочлен
обращался в нуль, то минимум многочлена на
достигался бы в некоторой внутренней точке, в которой производная равнялась бы нулю. Но производная
входит в множество и представлена в диаграмме, так что тогда и не были бы соседними корнями диаграммы.
Если в одной из точек и
многочлен
обращается в нуль, то на интервале он корней иметь не может (по теореме Ролля такой корень повлек бы за собой корень производной).
Наконец, если и имеют разные знаки, то по теореме о промежуточном значении многочлен имеет на интервале хотя бы один корень. При этом по уже понятным нам причинам (теорема Ролля) двух корней он иметь не может. Это позволяет вставить столбец для этого корня в диаграмму. При этом соответствующий интервал диаграммы разобьется на два, которые будут отличаться лишь в строке для многочлена .
Осталось провести аналогичное рассуждение для лучей, стоящих с края диаграммы. Поведение многочлена на бесконечности определяется его старшим коэффициентом (который, напомним, не равен нулю — сейчас мы впервые используем это предположение). Поэтому если стремится, скажем, к при , а значение в самом правом корне было отрицательным, то на этом луче появляется новый корень (только один по теореме Ролля). Если же значение в самом правом корне равно нулю или имеет тот же знак, что и старший коэффициент, то мы повторяем рассуждение из предыдущего абзаца и убеждаемся, что корней на правом луче нет. Аналогично определяется и поведение слева от самого левого корня.
На этом доказательство леммы 2, а с ней и теоремы Тарского-Зайденбрега, завершается.
67. Докажите, что множество троек , при которых многочлен имеет ровно два положительных корня, является полуалгебраическим.
Подобного рода задачи рассматривались в алгебре еще в прошлом веке (число перемен знака, правило Штурма и др.).
68. Докажите, что предикат , где — некоторое действительное число, выразим тогда и только тогда, когда является алгебраическим.
Разобравшись с действительными числами, можно перейти к комплексным. На самом деле (как часто бывает) здесь ситуация проще.
На комплексных числах нет естественного отношения порядка, поэтому рассмотрим сигнатуру . Будем, как всегда, считать две формулы эквивалентными, если они истинны при одних и тех же значениях параметров (в естественной интерпретации с носителем ).
Теорема 34 (элиминация кванторов в поле комплексных чисел).
Всякая формула этой сигнатуры эквивалентна бескванторной.
Эта теорема имеет много разных доказательств, но после доказательства теоремы Тарского-Зайденберга нам проще всего модифицировать его.
Теперь в диаграммах будут стоять не знаки , а только знаки и (поскольку порядка на нет). По той же причине мы не можем упорядочить корни, так что диаграмма будет состоять из неупорядоченных столбцов, соответствующих корням, и одного столбца, соответствующего дополнению к множеству корней (в котором будут стоять знаки для всех многочленов, кроме нулевых). Говоря о неупорядоченных столбцах, мы имеем в виду, что не различаем диаграммы, отличающиеся лишь порядком столбцов.
Основной шаг в доказательстве теоремы Тарского-Зайденберга (единственный, где важен порядок на действительных числах) состоял в пополнении диаграммы новым многочленом. Что будет с ним теперь?
Как и раньше, мы можем определить, в каких старых корнях новый многочлен равен нулю. Более того, мы можем определить кратность этих нулей, так как знаем все необходимое про его производные (которые уже включены в диаграмму). Поэтому основная теорема алгебры говорит нам, сколько будет новых корней (заметим, что все новые корни имеют кратность , так как иначе они были бы корнями производной и не были бы новыми).
Поскольку порядка на корнях нет, больше никакой информации нам и не нужно.
69. Провести доказательство элиминации кванторов в поле , не использующее диаграмм (это можно сделать, начав с приведения бескванторной формулы к дизъюнктивной нормальной форме, а затем применяя разные соображения из алгебры о наибольшем общем делителе многочленов). Для теоремы Тарского-Зайденберга это несколько сложнее; рассуждение такого рода приведено в книжке Энгелера [32]
70. Докажите, что множество тех четверок комплексных чисел , при которых многочлены и
имеют общий корень, задается бескванторной формулой. Найти эту формулу.
Задача 70 хорошо знакома алгебраистам. Ответ в ней можно записать в виде , где — многочлен, называемый результантом и равный определителю матрицы
71. Докажите, что множество всех пар комплексных чисел , при которых многочлен имеет хотя бы один кратный корень, задается бескванторной формулой. Найти эту формулу. Как выглядит аналогичная формула для многочлена ?
(Ответ к задаче тоже хорошо известен в алгебре; соответствующий многочлен называется дискриминантом.)
72. Обобщить утверждение предыдущей задачи на многочлены произвольной степени со старшим коэффициентом и найти выражение дискриминанта в виде определителя.
