Математическая логика: Учебное пособие

Министерство Образования Российской Федерации Уральский государственный педагогический университет

А.П. Ильиных

МАТЕМАТИЧЕСКАЯ ЛОГИКА

Учебное пособие

Екатеринбург 2002

Лекция 1. Аксиоматический метод в математике и формализация математических теорий Логика — наука о построение правильных умозаключений. Математическая логика является разделом математики, посвященном изучению математических доказательств и вопросов оснований математики. Курс математической логики имеет своей целью изложить основы этой науки, познакомить студентов с формализованным аксиоматическим методом построения математических теорий, охватывающим также и логические средства; его основными составными частями: языком, аксиомами, правилами вывода; проблемами непротиворечивости, полноты, разрешимости теорий. Аксиоматический метод в математике. Характерной чертой математики является использование доказательств, а не наблюдений. Физик может выводить физические законы из других физических законов, но окончательным подтверждение справедливости физического закона является его согласованность с данными эксперимента. Математик может произвольное число раз подтвердить какую-либо формулу, но признать ее как математический закон можно лишь с помощью доказательства. Такое понимание математического факта возникло лишь на некотором этапе развития математики. Истоки математики можно проследить в древних цивилизациях Египта, Вавилона, Индии и Китая, где математика носила эмпирический характер: имеется способ для решения какого-либо класса задач, однако задача обоснования этого способа с помощью доказательства не рассматривается. Математика, признающая необходимость доказательства утверждений, возникла в древней Греции. В книгах Евклида «Начала» (3 в. до н.э.) уже фигурируют аксиомы, теоремы, доказательства. Опишем кратко построение аксиоматической теории. Если нам требуется доказать утверждение A, то в процессе доказательства мы ссылаемся на ранее полученные утверждения A1, A2, . . .. Аналогично, для доказательства утверждений A1, A2, . . . нужны ранее доказанные утверждения B1, B2, . . . Чтобы процесс не был бесконечным, мы должны выбрать некоторые начальные законы, называемые аксиомами, которые принимаются без доказательства. Остальные законы, называемые теоремами, доказываются, исходя из аксиом. На каком основании мы принимаем аксиомы? Мы выбираем в качестве аксиом такие законы, которые, как мы полага-

ем, очевидны по самой природе рассматриваемых объектов. Например, рассматривая N — множество натуральных чисел, мы приписываем ему следующее свойство. Во множестве N существует элемент 1, который не следует ни за каким элементом. При этом мы должны разъяснить, что означает понятие «следовать за». Необходимо выразить это понятие, через другие, ранее разъясненные понятия. Снова, чтобы процесс не был бесконечным, мы должны выбрать некоторые основные понятия, которые остаются неопределяемыми. Остальные понятия, называемые производными понятиями, определяются в терминах основных. К основным понятиям, так же как и к аксиомам, предъявляется требование: они должны быть столь просты и ясны, что мы можем понимать их без точного определения. Теперь можно описать процесс развертывания аксиоматической теории. Вначале мы вводим некоторые основные понятия и аксиомы об этих понятиях. Далее переходим к определению производных понятий и доказываем теоремы об основных и производных понятиях. Здание, которое мы строим, состоящее из основных понятий, производных понятий, аксиом и теорем, называется аксиоматической теорией. Это может быть, например, аксиоматическим построением теории групп, планиметрии или теории натуральных чисел. Однако в понимании сущности аксиоматического метода есть принципиально важный момент. До определенного этапа в развитии математики неявно предполагалось, что мы описываем какие-то заранее подразумеваемые, фиксированные объекты. Например, какое-то однозначно определенное множество точек, прямых плоскости. В этом случае мы говорим о классическом аксиоматическом методе. Но и в этом случае можно придумать другие объекты, для которых наши аксиомы истинными. И тогда все доказанные теоремы будут истинными и для этих новых объектов. Это приводит к пониманию, что все, что нами получено, справедливо и для других объектов. Тем самым мы рассматриваем в аксиоматической теории целый класс объектов и все теоремы применимы к этим объектам. Мы называем такие аксиоматические системы современными, в противоположность классическим аксиоматическим системам. Типичным примером является теория групп. До сих пор нами не затрагивались те логические правила, которые используются при выводе математических теорем. В значительной мере к рассмотрению этих правил и более глубокому пониманию сущно-

сти аксиоматического метода подтолкнули некоторые парадоксы в теории множеств. На рубеже 19–20 веков аксиоматический метод продемонстрировал значительные достижения, например, Р.Дедекиндом (1888 г.) и Дж.Пеано (1891 г.) разработана аксиоматическая теория натуральных чисел, Д.Гильбертом (1899 г.) получено аксиоматическое построение евклидовой геометрии. Как основа большинства математических дисциплин в это время уже выступает теория множеств. Однако в это же время в теории множеств были обнаружены парадоксы; приведем один из них. Парадокс Рассела (1903 г.) Рассмотрим всевозможные множества M и разделим их на два вида. 1) Множества, которые не являются элементом самого себя, т.е. M ∈ / M. 2) Множества, которые являются элементом самого себя, т.е. M ∈ M. Например, если M — множество жителей Екатеринбурга, то M ∈ / M; если M — множество всех множеств, то M ∈ M. Ясно, что для любого множества M выполнено одно и только одно из условий 1) или 2). Рассмотрим множество X, элементами которого являются все множества вида 2). Поэтому X состоит из всех множеств, не являющихся элементом самого себя X = {M | M ∈ / M}. (1) Тогда множество X нельзя отнести к типу 2). Допустив, что X типа 2), мы получим: X является элементом самого себя, т.е. X = {A, B, . . . , X, . . .}. Это противоречит правилу (1) задания множества X. Поэтому множество X типа 1). Тогда X не является элементом самого себя, X ∈ / X. Однако X состоит из всех множеств, не являющихся элементом самого себя и запись X ∈ / X по правилу задания множества X вынуждает включение X ∈ X. Получили одновременно X ∈ / X и X ∈ X, противоречие. В итоге, не выполнено ни 1), ни 2) — парадокс в основаниях теории множеств. После ряда исследований этого парадокса выработано понимание, что здесь нет противоречия с интуитивным понятием множества. Действительно, для образования множества X мы собираем вместе некоторые объекты, которые в своей совокупности и составляют единственный объект, являющийся множеством X. Следовательно, перед тем, как множество X образовано, мы должны иметь в распоряжении все объекты, которые являются элементами из X. Отсюда следует, что множество X всегда не является элементом для X и парадокс Рассела исчезает. Хотя и

данный парадокс получил разумное объяснение, среди математиков возникло убеждение о необходимости анализа логических средств, применяемых при построении аксиоматических теорий. Формализация математических теорий. Любое предложение в математике может обсуждаться с двух позиций: смысла этого утверждения и символической записи предложения. Рассмотрим, например, предложение «сумма углов треугольника равна 180◦» и обсудим смысл этого утверждения. Можно также объяснить смысл первой аксиомы Пеано «имеется число без предшествующего элемента», но можно исследовать символическую запись этого предложения. Проанализируем средства необходимые для выражения этого предложения в виде последовательности символов. Символическая запись имеет вид: ∃ 1 ∀ x S(x) = 1

(2)

При этом переменная x предназначена обозначать произвольное натуральное число, S есть знак для изображения функции, про которую мы воображаем, что S(1) = 2, S(2) = 3, . . .. Знак S — унарный функциональный символ. Нам потребовались также логические знаки: ∃ — квантор существования и ∀ — квантор всеобщности. Если x — переменная, а S — унарный функциональный символ, то конструкция S(x) называется термом. Знак 1 — знак для обозначения конкретного предмета также является термом. Выражение S(x) = 1 можно записать с использованием знака отрицания ¬ в виде: ¬S(x) = 1. Сначала составляем формулу S(x) = 1. Она отображает мысль «предмет S(x) равен предмету 1», Затем составляем отрицание для предложения «предмет S(x) равен предмету 1» и спомощью кванторов получим окончательную формулу. Таким образом мы выразили в виде последовательности символов языка теории натуральных чисел предложение «имеется число без предшествующего элемента». Аналогичным образом можно записывать в виде формул произвольные утверждения про объекты какой-либо теории. Итак, для формализации некоторой математической теории нужно выполнить следующие шаги: 1) Создать язык теории, т.е. ввести символы, которые необходимы для записи предложений теории. 2) С помощью этих символов графически изобразить предложения теории в виде строк символов (формул). При этом некоторые из этих фор-

мул — аксиомы теории. Следующий шаг более трудный. Мы должны полностью описать те средства логики (правила вывода), которые применяются для получения теорем. Все теоремы должны выводится из аксиом, а аксиомы у нас просто строки символов. Поэтому данные правила должны описывать действия со строками и указывать, как из ранее полученных теорем получаются новые теоремы. Эти правилам вывода будут иметь следующий вид A1 , A2 , . . . , An B

(3)

При этом A1, A2, . . . , An — посылки, а B— заключение правила вывода. Правило вывода утверждает: если A1, A2, . . . An — теоремы теории, то B также является теоремой. После этого определение теоремы можно сформулировать следующим образом. 1. Всякая аксиома является теоремой. 2. Если имеется некоторое правило вывода (3), и A1, A2, . . . An — теоремы, то B также теорема. 3. То, что выражение является теоремой, устанавливается несколькими применениями правил 1) и 2). Если мы представим аксиомы теории и правила вывода в указанном выше виде и перечислим правила вывода, то получим формализованную аксиоматическую теорию. Программа Гильберта Идею формализации математики предложил немецкий математик Давид Гильберт. Его программа перестройки оснований математики включала следующие задачи. а) Представить существующую математику, в частности теорию множеств, в виде формальной теории. б) Доказать непротиворечивость полученной теории, т.е. доказать, что в этой теории никакое утверждение не может быть доказано вместе со своим отрицанием. Одно из достоинств такого подхода — возможность доказывать непротиворечивость аксиоматических теорий, не прибегая к методу нахождения модели теории. Другое важнейшее свойство — возможность

компьютерного доказательства теорем формализованных теорий. В настоящее время имеется ряд компьютерных программ, предназначенных для доказательства теорем. Выдвинутая Гильбертом программа обоснования математики стимулировала активные исследования в области оснований математики. В 30 годах XX века австрийский математик Курт Гедель получил фундаментальные результаты, характеризующие сущность аксиоматического метода в математике. Он показал, что первоначальный замысел Гильберта нельзя реализовать в полном объеме. Эти результаты будут сформулированы в заключительных разделах курса.

Лекция 2. Алгебра высказываний Напомним основные сведения о высказываниях и логических операциях над ними, рассмотренные во вводном курсе математики. Высказывание в математике — это повествовательное предложение, относительно которого можно сказать истинно оно или ложно. Рассмотрим следующие предложения. 1. Число 6 является четным числом. 2. Екатеринбург — город в Европе. 3. Какое сегодня число? 4. x > 3. Первое предложение является высказыванием, причем истинным. Второе предложение также высказывание, но ложное. Относительно предложений 3 и 4 нельзя сказать, истинны они или ложны. Поэтому они не является высказываниями. Высказывание будем обозначать латинскими буквами. Рассмотрим логические знаки ∧, ∨, →, ↔, ¬, с помощью которых из высказываний A и B можно составлять следующие сложные высказывания: A ∧ B — читается «A и B » или « A конъюнкция B»; A ∨ B – читается « A или B» или «A дизъюнкция B»; A → B — читается « A влечет B» или «A импликация B»; A ↔ B — читается «A тогда и только тогда, когда B» или «A эквивалентно B»; ¬A — читается «не A». Правила приписывания этим сложным высказываниям значения «истина» или «ложь» следующие. • Высказывание A ∧ B является истинным тогда и только тогда, когда истинны оба высказывания A и B. • Высказывание A ∨ B истинно тогда и только тогда, когда истинно хотя бы одно из высказываний A и B.

• Высказывание A → B ложно только в одном случае, когда высказывание A истинно, а B — ложно, в остальных случаях высказывание A → B истинно. • Высказывание A ↔ B истинно тогда и только тогда, когда A и B оба истинны или оба ложны. • Высказывание ¬A имеет значение истинности, противоположное значению истинности для A. Эти определения отражены в следующих таблицах истинности. В них высказываниям A и B придаются значения И или Л ( истина или ложь) и приводится значение составного высказывания. A И И Л Л

B A∧B A∨B A→B A↔B И И И И И Л Л И Л Л И Л И И Л Л Л Л И И

A ¬A И Л Л И

Таким образом можно составить таблицу истинности для произвольной формулы. Напомним определение тождественно истинной формулы ( тавтологии ). О ПРЕДЕЛЕНИЕ 1 Формула A называется тождественно истинной формулой, если при подстановке значений И (истина) или Л (ложь) в качестве значений входящих в формулу букв, значение формулы A всегда равно И. Тождественно истинные формулы — это законы логики. Существуют две причины, по которым мы считаем какое-либо суждение истинным. Рассмотрим, например, предложение «Екатеринбург — город в Европе». Мы объявляем это высказывание ложным. Значение «ложь» приписывается исходя из свойств обсуждаемых объектов. Точно также в случае высказывания «2·3 = 6 » значение «истина» установлено из свойств объектов 2 и 3. Однако существует случаи, когда приписывание предложению значение «истина» или «ложь» не учитывает свойств обсуждаемых объектов, а имеет другую природу — логическую истинность. Рассмотрим предложение «верно, что студент Иванов сдал зачет по логике или он не сдал зачет». Любой человек может объявить, что это

утверждение истинно, даже не зная конкретной информации про Иванова. Почему это так? Мы понимаем, что имеем дело с предложением вида ¬A ∨ A, где A — «Иванов сдал зачет». Поскольку формула ¬A ∨ A является тождественно истинной, то независимо от значения A, значение наше предложение истинно. Мы можем заменить предложение «Иванов сдал зачет» на предложение «Екатеринбург — город в Европе», и снова получим истинное высказывание ¬A ∨ A. Можно постепенно обнаруживать все новые и новые законы логики, подобные закону ¬A ∨ A, например, ¬¬A → A или (A → B) ↔ (¬A ∨ B). Поэтому возникает вопрос, как получить достаточно простой способ конструирования всех таких законов логики. Мы получим ответ в разделе «Исчисление высказываний». В данный момент рассмотрим способ для проверки тождественной истинности конкретных формул.

Лекция 3. Конъюнктивная и дизъюнктивная нормальные формы О ПРЕДЕЛЕНИЕ 2 Элементарной дизъюнкцией называется формула, являющаяся дизъюнкцией нескольких переменных X, Y, Z, . . . или их отрицаний. Пример. A = X ∨ ¬Y ∨ Z ∨ Y ∨ ¬X О ПРЕДЕЛЕНИЕ 3 Элементарной конъюнкцией называется формула, являющаяся конъюнкцией нескольких переменных X, Y, Z, . . . или их отрицаний. Пример. B = Y ∧ ¬Y ∧ Z ∧ Y ∧ ¬X Отметим, что в формуле A входит буква Y вместе со своим отрицанием ¬Y . Придадим любые значения И, Л буквам X, Y, Z в формуле A. Тогда одно из значений Y или ¬Y в A будет истинно. Поэтому значение формулы A всегда равно И. Следовательно, A является тождественно истинной формулой. Т ЕОРЕМА 1 Элементарная дизъюнкция является тождественно истиной, тогда и только тогда, когда в нее входит некоторая буква вместе со своим отрицанием. Доказательство. Предположим, что в элементарную дизъюнкцию A входит некоторая буква вместе со своим отрицанием. Как и выше получим, что A — тождественно истинна. Обратно, пусть A — тождественно истинна. Предположим противное, что в A нет буквы, входящей вместе со своим отрицанием. Построим набор значений букв, при которых A ложна, это противоречит условию и завершит доказательство. Правило построения набора следующее. Просматриваем слева направо буквы в формуле A. Если буква входит в формулу без отрицания, то присваиваем ей значение Л, если с отрицанием – значение И. Тогда значение формулы A имеет вид Л∨ Л∨ . . . ∨Л и равно Л. Заметим, что осуществимость процедуры присваивания возможна лишь тогда, когда в A нет буквы, входящей вместе со своим отрицанием. Иначе, нам пришлось бы одной и той же букве присваивать одновременно значение И и значение Л. Теорема доказана.

Т ЕОРЕМА 2 Элементарная конъюнкция является тождественно ложной, тогда и только тогда, когда в нее входит некоторая буква вместе со своим отрицанием. Доказательство. Предположим, что в элементарную конъюнкцию A входит некоторая буква вместе со своим отрицанием. Очевидно, что A – тождественно ложная формула. Обратно, пусть A тождественно ложна. Предположим противное, в A нет буквы, входящей вместе со своим отрицанием. Найдем набор значений букв, при которых A истинна, это противоречит условию. Просматриваем слева направо буквы в формуле A. Если буква входит в формулу без отрицания, то присваиваем ей значение И, если с отрицанием – значение Л. Тогда значение формулы A имеет вид И∧ И∧ . . . ∧И и, поэтому, равно И, противоречие. Теорема доказана. Напомним определение равносильности формул. О ПРЕДЕЛЕНИЕ 4 Две формулы A и B называются равносильными, если при любом наборе значений переменных, входящих в эти формулы, истинностные значения формул A и B равны. Если формулы A и B равносильны, то записываем A ≡ B. Приведем основные законы, связанные с равносильностью формул, полученные во вводном курсе математики. Т ЕОРЕМА 3 Пусть A, B, C — произвольные формулы алгебры высказываний. Тогда справедливы следующие утверждения:
1. A ∧ A ≡ A, — свойства идемпотентности 2. A ∨ A ≡ A,
3. A ∧ B ≡ B ∧ A, 4. A ∨ B ≡ B ∨ A,

— свойства коммутативности


5. A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C, — свойства ассоциативности 6. A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C,
7. A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C), — свойства дистрибутивности 8. A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C),


9. ¬(A ∧ B) ≡ ¬A ∨ ¬B, 10. ¬(A ∨ B) ≡ ¬A ∧ ¬B, 11. ¬(¬A) ≡ A,

— свойства де Моргана

— свойство двойного отрицания

12. A → B ≡ ¬B → ¬A,

— свойство контрапозиции

13. A → B ≡ ¬A ∨ B, 14. A ↔ B ≡ (A → B) ∧ (B → A), Как в математике, так и в обычной речи можно заменять высказывание на равносильное. Например, можно сказать «неверно, что 3 больше 1 и 11 делится на 2», или сказать «неверно, что 3 больше 1 или неверно, что 11 делится на 2». Мы применили равносильность вида (9). Мы можем заменить произвольную формулу X на равносильную формулу Y , в котором есть только следующие логические знаки: ∨, ∧ и ¬. Для этого выполним следующие преобразования формулы X. 1. Заменим любую часть A ↔ B в формуле X на (A → B) ∧ (B → A) по (14). Получится равносильная с X формула без знака ↔. 2. Заменим любую часть A → B на ¬A ∨ B и избавимся от знака →. Итак, в алгебре высказываний обойтись только следующими логическими знаками: ∨, ∧ и ¬. О ПРЕДЕЛЕНИЕ 5 Конъюнктивной нормальной формой (КНФ) для формулы X называется равносильная ей формула Y , являющаяся конъюнкцией элементарных дизъюнкций. Укажем способ для получения конъюнктивной нормальной формы для формулы X. Избавимся, как было сказано выше, от знаков, отличных от ∨, ∧ и ¬. С помощью дистрибутивных законов и законов ¬(A ∧ B) ≡ ¬A ∨ ¬B , ¬(A ∨ B) ≡ ¬A ∧ ¬B и ¬¬A ≡ A постепенно преобразуем X и промежуточные формулы к виду X1 ∧ X2 . Проделав тоже самое с X1 , X2 и их частями мы получим конъюнкцию элементарных дизъюнкций. О ПРЕДЕЛЕНИЕ 6 Дизъюнктивной нормальной формой (ДНФ) для формулы X называется равносильная ей формула Y , являющаяся дизъюнкцией элементарных конъюнкций.

Рассмотрим способ для получения дизъюнктивной нормальной формой для формулы X. Как и выше избавимся вначале от знаков, отличных от ∨, ∧ и ¬. Затем преобразуем X и промежуточные формулы к виду X1 ∨X2. Проделав это несколько раз, получим дизъюнкцией элементарных конъюнкций. Можно привести и более строгое доказательство индукцией по числу букв в формуле X. Теперь можно получить критерий тождественно истинной и тождественно ложной формулы. Т ЕОРЕМА 4 Формула X является тождественно истинной, тогда и только тогда, когда в ее КНФ каждая элементарная дизъюнкция имеет вхождение некоторой буквы вместе со своим отрицанием. Доказательство. Предположим, что X1 — КНФ для формулы X и X1 = Y ∧ Z ∧ . . ., где Y, Z, . . . – элементарные дизъюнкции. Если каждая элементарная дизъюнкция Y, Z, . . . имеет вхождение некоторой буквы вместе со своим отрицанием, то при любом значении букв, входящих в A, значения Y, Z, . . . равны И. Тогда значения X1 и X равны И. Обратно, пусть формула X тождественно истинна. Тогда элементарные дизъюнкции Y, Z, . . . также тождественно истинны и, поэтому, имеют вхождение некоторой буквы вместе со своим отрицанием. Теорема доказана. Аналогично получаем критерий тождественно тождественно ложной формулы. Т ЕОРЕМА 5 Формула X является тождественно ложной, тогда и только тогда, когда в ее ДНФ каждая элементарная конъюнкция имеет вхождение некоторой буквы вместе со своим отрицанием. Представление произвольной двузначной функции посредством формулы алгебры высказываний. Рассмотрим способ построения формулы с наперед заданной таблицей истинности. Пусть A — произвольная формула алгебры высказываний, содержащая переменные X1 , X1, . . . , Xn. Имеется ровно 2n наборов значений И, Л переменных X1 , X1, . . . , Xn. Каждому набору в таблице истинности соответствует значение формулы A И или Л, которое обозначим через f (X1, X1, . . . , Xn ).

Тем самым произвольной формуле A сопоставляется двузначная функция f = f (X1, X1, . . . , Xn ) от n аргументов. Значения аргументов и значение функции содержатся во множестве из двух элементов { И, Л }. Рассмотрим обратную задачу: пусть задана функция f = f (X1, X1, . . . , Xn) от n аргументов, где значения аргументов и значение функции содержатся во множестве { И, Л }. Требуется найти формулу алгебры высказываний A, которой соответствует данная функция f . Другими словами у нас заполнены значения таблицы истинности, а требуется подобрать формулу с данной таблицей.

Итак, имеем заданные значения f (И,И, . . . , И), f (И,И, . . . , Л), . . . , f (Л,Л, . . . , Л)

(4)

Укажем способ построения формулы A, принимающую данные, наперед указанные, значения. Он состоит из 3 шагов. 1. Рассмотрим любой из 2n наборов аргументов для функции f , например, набор И,И, . . . ,Л. Сопоставим набору элементарную конъюнкцию переменных X1, X2 , . . . , Xn или их отрицаний. Если переменная Xi в наборе (4) имела значение И, то переменную Xi в элементарную конъюнкцию помещаем без отрицанию, иначе — с отрицанием. Затем присоединяем к элементарной конъюнкции с помощью знака ∧ коэффициент – значение функции от данного набора, т.е. одно из значений f(И,И, . . . ,И), . . . , f(Л,Л, . . . ,Л). Получаем 2n членов. В частности, для набора И,И, . . . ,Л получаем член f(И,И, . . . ,Л)∧X1 ∧ X2 ∧ . . . ∧ ¬Xn. 2. Соединяем полученные члены знаком дизъюнкции. 3. Отбрасываем члены, имеющие коэффициент Л, у членов, имеющих коэффициент И отбрасываем только сам коэффициент. Получаем формулу A. Нетрудно проверить, что формула A принимает требуемые значения. Пример. Построить формулу A, содержащую буквы X, Y, Z, и принимающую следующие значения: A(И,И,И)=И, А(И,И,Л)=И, А(Л,Л,Л)=И. Остальные значения формулы A равны Л. Ответ A = (X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ ¬Z). Совершенная конъюнктивная и совершенная дизъюнктивная нормальные формы Пусть F = F1 ∨ F2 ∨ . . . Fk — дизъюнктивная нормальная форма для формулы A, содержащая переменные X1 , X2, . . . , Xn. Однозначна ли нормальная форма F ? Нетрудно привести пример двух различных дизъюнктивных (и конъюнктивных ) нормальных форм для данной формулы A. Желательно иметь некоторую однозначность в выборе нормальных форм. Пусть F = F1 ∨ F2 ∨ . . . Fk

(5)

дизъюнктивная нормальная форма для формулы A, являющаяся дизъюнкцией элементарных конъюнкций F1 , F2, . . . , Fk . Дизъюнктивная нормальная форма F называется совершенной, если выполнены следующие условия. 1. В форме F нет двух одинаковых элементарных конъюнкций F1 , F2 , . . . , Fk . 2. Пусть Xi , ( i = 1, 2, . . . , n) — произвольная переменная и Fj (j = 1, 2, . . . , k) — элементарная конъюнкция из формы F . Тогда имеется ровно одно вхождение переменной Xi или отрицания ¬Xi в элементарную конъюнкцию Fj . Пусть

F = F1 ∧ F2 ∧ . . . Fk

(6)

конъюнктивная нормальная форма для формулы A, являющаяся конъюнкцией элементарных дизъюнкций F1, F2, . . . , Fk . Конъюнктивная нормальная форма F называется совершенной, если выполнены следующие условия. 1. В форме F нет двух одинаковых элементарных дизъюнкций F1 , F2 , . . . , Fk . 2. Пусть Xi (i = 1, 2, . . . , n) — произвольная переменная и Fj (j = 1, 2, . . . , k) — элементарная дизъюнкции из формы F . Тогда имеется ровно одно вхождение переменной Xi или отрицания ¬Xi в элементарную дизъюнкцию Fj . Т ЕОРЕМА 6 Пусть A – произвольная не тождественно истинная формула. Тогда A имеет однозначно определенную совершенную конъюнктивную нормальную форму. Доказательство. Вычислим таблицу истинности для формулы A. По предыдущему пункту построим формулу F = F1 ∧ F2 ∧ . . . Fk с заданной таблицой истинности. При этом члены F1 ∧ F2 ∧ . . . Fk удовлетворяют двум условиям из определения совершенной конъюнктивной нормальной формы. Поэтому F — требуемая нормальная форма. Пусть F  произвольная совершенная конъюнктивная нормальная форма. Нетрудно проверить, что форма F  содержит в точности те члены F1 , F2, . . . , Fk , которые соответствуют наборам, при которых значение

формулы A равно И. Отсюда члены F1, F2, . . . , Fk определены однозначно с точностью до порядка. Теорема доказана. Т ЕОРЕМА 7 Пусть A – произвольная не тождественно ложная формула. Тогда A имеет однозначно определенную совершенную дизъюнктивную нормальную форму. Доказательство самостоятельно.

Лекция 4. Построение исчисления высказываний в виде формальной системы В предыдущей лекции рассматривались тождественно истинные формулы. Если перед нами конкретная формула, то вычисляя таблицу истинности или КНФ формулы, мы можем определить, будет ли она тождественно истинной. Такие методы позволяют провести проверку на тождественную истинность конкретной формулы, но не дают представления об общем устройстве, обозрении всех тождественно истинных формул. Исчисление высказываний — раздел математической логики, изучающий построение всех тождественно истинных формул. В этом разделе мы получим более глубокое понимание природы таких формул. Исчисление высказываний будет построено в виде формальной системы. Понятие формальной системы необходимо не только в исчисление высказываний. В дальнейшем и другой раздел математической логики «Теории первого порядка» будет построен в виде формальной системы. Формальная система отражает синтаксические аспекты математической теории, т.е. ее символы, формулы, аксиомы, правила вывода. Приведем точные определения трех составных частей формальной системы. Первая часть формальной системы — ее язык. Чтобы определить язык формальной системы нужно задать символы этого языка и его формулы. Если сравнить язык формальной системы с русским языком, то получим аналогию символов и формул с буквами и словами в русском языке. Однако символы формальной системы могут быть произвольными знаками, например, знаками &, ∗, +. Единственное требование — неделимость символа (символ не имеет частей, из которых составлен) и возможность его распознания в один прием. Последовательность символов языка называется выражением этого языка. Число символов в выражении – длина выражения. Аналогия в естественном языке: слово насос имеет длину 5. Одно выражение может входить в другое. Например, выражение ма имеет два вхождения в выражение математика. Замена первого вхождения ма на выражение на выражение на дает выражение натематика. Не все выражения в естественном языке являются осмысленными словами. Точно также в формальной системе лишь часть выражений считается формулами. В каждой формальной системе свои правила обра-

зования формул. Как уже отмечалось, язык формальной системы задан если определены символы этого языка и его формулы. Вторая часть формальной системы — аксиомы. Задать аксиомы означает выделить некоторые формулы формальной системы, присвоив им название аксиомы. Третья часть формальной системы — правила вывода. Они имеют вид A1 , A2 , . . . , An , (7) B где A1, A2, . . . , An и B – формулы формальной теории. При этом формулы A1, A2, . . . , An называются посылками правила вывода, а B его заключением. Правила указывают способ для получения теорем. Вначале все аксиомы объявляются теоремами. Из этого начального списка теорем получаются новые теоремы с помощью правил вывода. Если уже установлено, что A1, A2, . . . , An – теоремы и имеется правило вывода (7) с посылками A1, A2, . . . , An, то его заключение добавляется в список теорем. Тем самым получаем следующее определение теоремы формальной системы. 1. Любая аксиома формальной системы F является ее теоремой. 2. Если A1 , A2, . . . , An – теоремы и теорема.

A1 ,A2 ,... B

– правило вывода, то B –

3. То, что формула A является теоремой устанавливается несколькими применениями правил 1 и 2. Тоже самое можно выразить иначе. Считаем аксиомы теоремами шага 1. Обозначим множество теорем шага 1 через F1. Назовем теоремами шага m все теоремы шага m − 1 и все заключения правил вывода (7), где A1, A2, . . . , An теоремы шага m − 1. Рассмотрим F = F1 ∪ F2 ∪ F3 ∪ . . .. Формула A — теорема тогда и только тогда, когда A ∈ F . Любая теорема имеет наименьший номер шага n, на котором она получена. Мы можем доказывать различные утверждения для теорем индукцией по числу n. Построение исчисления высказываний. Рассмотрим исчисление высказываний как формальную систему, построенную в 3 шага. Шаг 1. Определим язык исчисления высказываний. Для этого зададим символы и формулы. Символами исчисления высказываний являются.

1. Латинские буквы a, b, . . . , z, A, B . . . , Z и буквы с индексами, штрихами и т.п. 2. Символы ¬ и ∨. Формулы определяются следующим образом. 1. Буквы является формулами. 2. Если U и V – формулы, то ¬U и ∨U V – формулы. 3. То, что выражение A является формулой, устанавливается несколькими применениями правил 1) и 2). Это определение можно сформулировать иначе. Буквы считаем формулами шага 1. Назовем формулами шага n все формулы шага n − 1 и формулы ¬U и ∨U V , где U и V формулы шага n − 1. Пусть Fi — множество формул шага i и F = F1 ∪ F2 ∪ . . .. Выражение A является формулой тогда и только тогда, когда A ∈ F . Мы можем доказывать различные утверждения для формул индукцией по наименьшему шагу n, на котором получена формула. Шаг 2. Зададим аксиомы исчисления высказываний. Мы рассмотрим всего лишь один вид аксиомы – пропозициональные аксиомы. Они имеют вид ¬A ∨ A, (8) где A – произвольная формула. Шаг 3. Зададим 4 правила вывода исчисления высказываний. Они имеют следующий вид, где A, B, C – произвольные формулы. Правило расширения A (9) B∨A Правило сокращения A∨A (10) A Правило ассоциативности

Правило сечения.

A ∨ (B ∨ C) (A ∨ B) ∨ C

(11)

A ∨ B, ¬A ∨ C B∨C

(12)

В исчислении высказываний обычно вместо слова «теорема» употребляется слова «выводимая формула». То, что формула A является выводимой формулой, записывается в виде A Приведем некоторые пояснения к приведенным определениям. Вместо привычной записи U ∨V использовалась запись ∨U V . Хотя в дальнейшем мы применяем запись U ∨ V , но всегда подразумеваем вместо нее запись ∨U V . При определении формулы не использовались скобки. Оказывается, что мы сможем обойтись без употребления скобок. Для наглядности мы будем использовались скобки, например, записывать (A ∨ B). Однако под этой записью понимаем A ∨ B. Запись F = A1 ∨ A2 ∨ . . . ∨ An подразумевает правостороннюю расстановку скобок, а именно, сборку формулы F в виде F = A1 ∨ (A2 ∨ . . . (An−1 ∨ An )). При определении формулы мы не использовали также знаки ∧, →, ↔. Определяемые символы . В математике и других дисциплинах постоянно встречаются символы, которые служат для обозначения некоторой последовательности символов. Это определяемые символы. Обозревая формулу с определяемыми символами мы должны представить ее как формулу с исходными символами, которая получена заменой определяемых символов на то, что они изображают. Введем следующие определяемые символы →, ∧, ↔ • A → B является обозначением для ¬A ∨ B, • A ∧ B является обозначением для ¬(¬A ∨ ¬B), • A ↔ B является обозначением для (A → B) ∧ (B → A). Отметим еще раз, что обозревая формулу с определяемыми символами мы должны представить на ее месте формулу с исходными символами. Например, длина формулы A → B равна 4, так как в нее входит 4 символа ¬, A, ∨, B, а не 3 символа A, →, B.

Лекция 5. Теоремы о выводимых формулах Рассмотрим основные свойства выводимости, в которых A и B — произвольные формулы исчисления высказываний. Приведем первое из этих свойств: если выводима формула A ∨ B, то выводима формула B ∨ A. По существу это новое правило вывода. Поэтому мы формулируем его в следующем виде. С ВОЙСТВО 1 Справедливо правило вывода (коммутативность) A∨B . B∨A

(13)

Доказательство. Дано, что  A ∨ B. Необходимо доказать  B ∨ A. Применим правило сечения A ∨ B, ¬A ∨ A . B∨A

(14)

Посылка A ∨ B выводима по условию теоремы. Посылка ¬A ∨ A выводима, так как является пропозициональной аксиомой. Следовательно, заключение правила B ∨ A также является выводимой формулой. Свойство доказано. С ВОЙСТВО 2 Справедливо правило (A ∨ B) ∨ C . A ∨ (B ∨ C) Доказательство. Установим, что  A ∨ (B ∨ C) в 6 шагов. 1.  (A ∨ B) ∨ C по условию, 2.  C ∨ (A ∨ B) по правилу коммутативности, 3.  (C ∨ A) ∨ B по правилу ассоциативности, 4.  B ∨ (C ∨ A) по правилу коммутативности, 5.  (B ∨ C) ∨ A по правилу ассоциативности, 6.  A ∨ (B ∨ C) по правилу коммутативности. Свойство доказано. По существу мы установили

(15)

С ВОЙСТВО 3 Если выводима формула (A ∨ B) ∨ C, то выводимы все формулы, полученные из нее с помощью произвольной циклической перестановки членов и произвольной расстановки скобок. С ВОЙСТВО 4 Формула ¬¬A∨B выводима тогда и только тогда, когда выводима формула A ∨ B. Доказательство. Пусть выводима формула ¬¬A ∨ B. Применим правило сечения ¬A ∨ A, ¬¬A ∨ B . (16) A∨B Посылки ¬¬A ∨ B и ¬A ∨ A выводимы (первая — пропозициональная аксиома, вторая по условию ). Следовательно,  A ∨ B. Обратно, пусть выводима формула A ∨ B. Применим правило сечения A ∨ B, ¬A ∨ ¬¬A . (17) B ∨ ¬¬A Посылка A ∨ B выводима по условию. Посылка ¬A ∨ ¬¬A выводима, т.к.  ¬¬A ∨ ¬A (пропозициональная аксиома) и по коммутативности  ¬A ∨ ¬¬A. Получим  B ∨ ¬¬A и по свойству коммутативности  ¬¬A ∨ B. Свойство доказано. С ВОЙСТВО 5 Пусть дана формула A = A1 ∨ A2 · · · ∨ An , у которой выводим один из ее членов Ai, где i = 1, 2, . . . , n. Тогда выводима формула A. Доказательство. Если i = n, то применим несколько раз правило расширения. Получим  An−1 ∨ An ,

 An−2 ∨ An−1 ∨ An , . . . ,

 A1 ∨ A2 ∨ . . . ∨ An ,

т.е.  A. Если i = n, то рассмотрим C = Ai+1 ∨ . . . ∨ An. Как и выше получаем  Ai ∨ C,

 Ai ∨ Ai+1 ∨ C,

. . . ,  A1 ∨ A2 ∨ . . . ∨ An ,

т.е.  A. Свойство доказано. С ВОЙСТВО 6 Пусть дана формула A = A1 ∨ A2 , . . . , ∨An, причем для некоторых ее членов Ai, Aj , где i, j ∈ {1, 2, . . . , n}, выводима формула Ai ∨ Aj . Тогда выводима формула A.

Доказательство проводим индукцией по числу n. Пусть A — контрпример с наименьшим n. Если i = j, то  Ai ∨ Ai . По правилу сокращения  Ai. По предыдущей теореме  A и A — не контрпример. Поэтому считаем i = j. С учетом  Aj ∨ Ai можно считать, что i < j. Если i > 1, то формула B = A2 ∨ A3, . . . , ∨An содержит члены Ai , Aj , причем  Ai ∨ Aj . Тогда по индукции  B и по правилу расширения  A. Пусть i = 1. Тогда  A1 ∨ Aj . Если при этом j = 2, то  A1 ∨ A2. Обозначим C = A3 , . . . , ∨An. По правилу расширения  (A1 ∨ A2 ) ∨ C. По правилу ассоциативности  A = A1 ∨ (A2 ∨ C), что и нужно. Пусть j > 2. По индукции получаем  A1 ∨ C для C = A3 ∨ · · · ∨ An . Тогда 1.  C ∨ A1 (по коммутативности), 2.  (C ∨ A1) ∨ A2 (по правилам расширения и коммутативности), 3.  C ∨ (A1 ∨ A2) (по ассоциативности), 4.  (A1 ∨ A2) ∨ C (по коммутативности), 5.  A1 ∨ (A2 ∨ C) (по свойству 3), т.е.  A. Свойство доказано. С ВОЙСТВО 7 Пусть дана формула A = A1 ∨ A2 ∨ · · · ∨ An , причем для некоторых ее членов Ai1 , Ai2 , . . . , Aim выводима формула Ai 1 ∨ Ai 2 ∨ · · · ∨ Ai m .

(18)

Тогда выводима данная формула A. Доказательство проводим индукцией по числу m. Пусть A — контрпример с наименьшим m. По свойствам 5 и 6 имеем m > 2. Нам дана выводимая формула Ai1 ∨ Ai2 ∨ · · · ∨ Aim , т.е. формула Ai1 ∨ (Ai2 ∨ · · · ∨ (Aim−1 ∨ Aim )), по соглашению о правосторонней расстановке скобок. Рассмотрим другую формулу (Ai1 ∨ Ai2 ) ∨ Ai3 ∨ · · · ∨ Aim .

(19)

Она выводима по правилу ассоциативности и с учетом выводимости формулы (18). Она содержит m − 1 членов следующего вида: один член Ai1 ∨ Ai2 и m − 2 членов Ai3 , . . . , Aim .

(20)

По индукции, если выводима формула, составленная из этих m−1 членов, то выводима формула F , содержащая эти члены. Рассмотрим в качестве F формулу (Ai1 ∨ Ai2 ) ∨ A. (21) Формула (19) составлена из из ее m − 1 членов формулы (21) и выводима. Поэтому по индукции выводима формула (21). Тогда 1.  (Ai2 ∨ A) ∨ Ai1 (по ассоциативности), 2.  (Ai2 ∨ A) ∨ A ( по предыдущему свойству), 3.  Ai2 ∨ (A ∨ A) (по ассоциативности), 4.  (A ∨ A) ∨ Ai2 (по коммутативности), 5.  (A ∨ A) ∨ (A ∨ A) (по предыдущему свойству), 6.  A ∨ A (по правилу сокращения), 7.  A (по правилу сокращения). Свойство доказано. Замечание. Из данного свойства следует, что перестановка членов в формуле A = A1 ∨ A2 ∨ · · · ∨ An , не влияет на выводимость этой формулы. С ВОЙСТВО 8 Справедливо правило ¬A ∨ C, ¬B ∨ C . ¬(A ∨ B) ∨ C

(22)

Доказательство. Имеем: 1.  ¬(A ∨ B) ∨ (A ∨ B) (по пропозициональной аксиоме),   2.  ¬(A ∨ B) ∨ A ∨ B (по свойству 3),   3.  B ∨ ¬(A ∨ B) ∨ A (по свойству 3). Итак, в следующем правиле сечения все посылки выводимы   B ∨ ¬(A ∨ B) ∨ A , ¬B ∨ C . (¬(A ∨ B) ∨ A) ∨ C   Поэтому ¬(A ∨ B) ∨ A ∨ C. По циклической перестановке членов имеем  A ∨ C ∨ ¬(A ∨ B) и по дано  ¬A ∨ C.

По правилу сечения   A ∨ C ∨ ¬(A ∨ B) , ¬A ∨ C   C ∨ ¬(A ∨ B) ∨ C   получаем  C ∨ ¬(A ∨ B) ∨ C. Из членов этой выводимой формулы составлена формула ¬(A ∨ B) ∨ C. По свойству 6 она сама выводима. Свойство доказано.

Лекция 6. Совпадение классов выводимых и тождественно истинных формул В лекции 2 мы сформулировали следующую задачу: «получить достаточно простой способ конструирования тождественно истинных формул — законов логики высказываний». В предыдущей лекции рассмотрен класс выводимых формул. Формулы этого класса по определению имеют простую и обозримую конструкцию. Мы докажем совпадение понятий «выводимая формула» и «тождественно истинная формула». Тем самым мы получим полное описание тождественно истинных формул, то есть законов логики высказываний. Т ЕОРЕМА 8 Всякая выводимая формула является тождественно истинной формулой. Доказательство. Пусть дана произвольная формула X. Напомним определение выводимости. 1. Пропозициональные аксиомы, то есть формулы вида ¬A ∪ A - выводимые формулы. 2. Если посылки правила вывода - выводимые формулы, то заключение - выводимая формула, 3. Выводимость формулы X получается получается несколькими применениями правил 1 и 2. Правила вывода имеют следующий вид. A правило расширения, B∨A A∨A правило сокращения, A A ∨ (B ∨ C) правило ассоциативности, (A ∨ B) ∨ C A ∨ B, ¬A ∨ C правило сечения. B∨C

Каждой формуле X однозначно приписан наименьший номер шага, на котором она получена. Доказательство теоремы проведем индукцией по этому номеру n. Пусть n = 1. Тогда X - пропозициональная аксиома, т.е. X = ¬A ∨ A для некоторой формулы A. Формула A содержит буквы, которым придаются значения истина или ложь. Значения формулы A могут быть как истина так и ложь. Однако формула X всегда истинна, так как одна из ее частей A или ¬A является истинной. Предположим, утверждение верно для всех формул с номером n. Покажем справедливость утверждения для формул с номером n + 1. Пусть формула X имеет номер n + 1. Тогда она совпадает с заключением одного из правил вывода, где где в посылке расположены формулы с номером n. Они тождественно истинны по предположению индукции. Возможны 4 случая для вида правила вывода. 1. Пусть рассматривается правило расширения с посылкой A и заключением X = B ∨ A. Так как посылка A — тождественно-истинная формула, то значения A всегда равны И. Поэтому значения формулы X = B ∨ A всегда равны И, т.е. X — тождественно истинная формула. 2. Пусть имеется правило сокращения с посылкой A ∨ A и заключением A. Так как посылка A ∨ A— тождественно истинная формула, то заключение A тождественно истинно. Действительно, если при некотором наборе букв, входящих в A значение A равно Л, то значение A при этом наборе букв равно Л∨ Л=Л. Это противоречие, так как посылка A ∨ A— тождественно истинная формула, 3. Пусть мы имеем правило правило ассоциативности с посылкой A ∨ (B ∨ C) и заключением (A ∨ B) ∨ C. Так как посылка тождественно истинна, то при любом наборе значений букв, входящих в формулы A, B, C, среди значений есть значение И (иначе значение X равно Л∨(Л∨ Л)= Л). Тогда заключение (A ∨ B) ∨ C также принимает значение И. Получили, что формула (A ∨ B) ∨ C тождественно истинна. 4. Пусть имеется правило сечения с двумя посылками A ∨ B и ¬A ∨ C (которые тождественно истинны) и заключением B ∨ C. Предположим, что при некотором наборе букв, входящих в формулы A, B, C, значение заключения B ∨ C есть Л. Тогда значение формулы B и

значение C есть Л. Если значение формулы A равно Л, то значение формулы A ∨ B равно Л, противоречие с тождественной истинностью A∨B. Если значение формулы A равно И, то значение формулы ¬A∨C равно Л, противоречие с тождественной истинностью ¬A∨C. Значит формула B ∨ C тождественно истинна. Теорема доказана. Докажем обратное утверждение для теоремы 8. Т ЕОРЕМА 9 Всякая тождественно истинная формула является выводимой формулой. Доказательство. Пусть формула A является тождественно истинной. Тогда тождественно истинна формула A ∨ A. Достаточно проверить ее выводимость. Действительно, из выводимости формулы A ∨ A по правилу сокращения следует выводимость формулы A, что и нужно. Вместо доказательства выводимости формулы A ∨ A докажем более общий факт: если формула A1 ∨ A2 ∨ · · · ∨ An , где n истинна, то она выводима.




2 — тождественно

При n = 2 и A1 = A2 = A получим то, что требуется. Итак, дано, что формула X = A1 ∨ A2 ∨ · · · ∨ An (23) является тождественно истинна и n
2. Докажем, что X - выводимая формула, рассматривая несколько случаев. Случай 1. Рассмотрим вначале случай, когда число символов в каждой формуле A1 , A2, . . . , An равно 1 или 2. Из определения формулы следует, что формулы A1, A2, . . . , An являются буквами или отрицанием букв. Поэтому формула X — элементарная дизъюнкция и имеет вид, подобный виду: X = C ∨ ¬D ∨ A ∨ ¬C, где A, D, C — буквы. Элементарная дизъюнкция является тождественно истиной, тогда и только тогда, когда в нее входит некоторая буква вместе со своим отрицанием. Поэтому в формуле X есть вхождение некоторой буквы A вместе с вхождением отрицания ¬A. Выводимость формулы не зависит от порядка членов по свойству 7. Переставляя компоненты считаем, что X = X1 ∨ X2 ∨ . . . ∨ (¬A ∨ A). Имеем  ¬A ∨ A (пропозициональная аксиома). Применяя несколько раз правило расширения, получим  X. Случай 1 рассмотрен.

Предположим, что утверждение теоремы 2 не выполняется. Среди всех формул X, которые не удовлетворяют заключению ( т.е. не являются выводимыми) рассмотрим контрпример X = A1 ∨A2 ∨· · ·∨An с наименьшим количеством символов. Рассмотрим строение каждого члена A1, A2, . . . An формулы X. Поскольку cлучай 1 рассмотрен, то можно считать, что среди членов A1, A2, . . . An есть член Ai , который не является буквой и не является отрицанием буквы. Члены A1, A2, . . . An в записи X можно переставлять; по свойству 7 это не влияет на выводимость формулы. Поэтому считаем, что A1 не буква и не является отрицанием буквы. Любая формула X, отличная от буквы, построена из ранее полученных формул Y и Z с помощью одного из двух действий: 1) X = ¬Y или 2) X = Y ∨Z. Если при этом формула X отличная от отрицания буквы, то в случае 1) имеем 1 а) X = ¬¬Z или 1 б) X = ¬(Y ∨ Z). Поэтому выполнена одна из 3 возможностей: 1. A1 = ¬¬B, 2. A1 = ¬(B ∨ C), 3. A1 = B ∨ C. Обозначим D = A2 ∨ · · · ∨ An . Случай 1 A1 = ¬¬B. Тогда X = (¬¬B) ∨ D. Рассмотрим новую формулу X1 = B ∨ A2 ∨ . . . An = B ∨ D. Формула X1 принимает одинаковые значения с формулой X, и поэтому, X1 тождественно истинна. Она имеет на 2 символа меньше, чем формула X. По индукции заключаем  X1 = B ∨ D. о свойству выводимости 4 получаем  X = ¬¬B ∨ D Случай 2 A1 = ¬(B ∨ C). Тогда X = ¬(B ∨ C) ∨ D. Введем две новые формулы X1 = ¬B ∨ A2 ∨ . . . An = ¬B ∨ D и X2 = ¬C ∨ A2 ∨ . . . An = ¬C ∨ D. Методом от противного установим тождественную истинность формул X1 и X2 . Предположив, что при некотором наборе значений букв формула X1 ложна. Получим, что значение X1 и значение D ложны. Тогда значение формулы X = ¬(B ∨ C) ∨ D ложно, независимо от значения C. Противоречие с тем, что X тождественно истинна. Рассуждения для X2 аналогичны. Итак, формулы X1 = ¬B ∨ D и X2 = ¬C ∨ D тождественно истинны и выводимы по предположению индукции. По свойству 8 выводима формула X = ¬(B ∨ C) ∨ D. Случай 3 A1 = B ∨ C. Подставив в формулу X, получим X = (B ∨ C) ∨ A2 ∨ . . . An = (B ∨ C) ∨ D Выводимость формулы X

равносильна выводимости формулы Y = B ∨(C ∨D) = B ∨C ∨A2 ∨. . . An со стандартной расстанокой скобок и числом членов на 1 больше, чем в X. Число символов тоже, что и в формуле X. Операцию перехода от формулы X к формуле Y назовем «измельчением звеньев». Она не меняет число символов в формуле. Поэтому мы могли среди контрпримеров с минимальным числом символов выбрать контрпример, не допускающий дальнейшего измельчением членов. Тогда последний случай невозможен. Теорема доказана. Мы завершили раздел логики, относящийся к исчислению высказываний.

Лекция 7. Предикаты и кванторы В предыдущих лекциях мы рассмотрели один из первоначальных разделов математической логики – алгебру высказываний. Однако для реальной математической практики выразительные возможности алгебры высказываний явно недостаточны. Мы не можем выразить, например, мысль типа «существует объект x с некоторым свойством A». Для того, чтобы записывать подобные утверждения, нам нужны понятия предиката и квантора. Напомним определение предиката из вводного курса математики. Пусть задано некоторое предложение P (x1, x2, . . . , xn), содержащее n переменных, принимающих значения из некоторого множества M. Это предложение называется n-арным предикатом с областью определения M, если при замене переменных x1 , x2, . . . , xn, на элементы из M получается высказывание. Пример. Предложение x + y = 7 нельзя рассматривать как высказывание. Действительно, не зная конкретного значения переменных x и y, нельзя приписать этому предложению значения «истина» или «ложь». Однако, при подстановке вместо переменных x, y, элементов из множества комплексных чисел получается высказывание. Поэтому предложение x + y = 7 – бинарный предикат с областью определения C. Можно дать более строгое определение предикатов на основе теории множеств. Пусть, например, M - множество всех людей, живущих в настоящее время. Рассмотрим бинарный предикат P (x, y): человек x знает человека y. Составим список P следующим образом: переберем все пары a, b. Если P (a, b) = И, т.е. a знает b, то в этот список поместим пару (a, b). Если P (a, b) = Л, то пара (a, b) не входит в список P . Свойство «знает» полностью характеризуется списком P . Поскольку любой n-арный предикат P может быть подвергнут процессу составления списка и получения подмножества P в M × · · · × M, то приходим к следующему определению. О ПРЕДЕЛЕНИЕ 7 n-арным предикатом, определенным на множестве M называется некоторое подмножество в декартовой произведении M n = M × · · · × M. Особую роль играет в математике бинарный предикат «равно». Для его обозначения используется знак « = ». Имеем a = b тогда и только

тогда, когда a и b — один и тот же объект. Если некоторое математическое утверждение высказано по a, то есть P (a) = И, то и P (b) = И. Однако возможны осложнения, что показывает следующий известный пример из [4]. Пусть n - число планет солнечной системы. Тогда 1. Коперник не знал, что n > 6; 2. на самом деле n = 9, подставим n в 1) и получим, что 3. Коперник не знал, что 9 > 6. Где ошибка? Рассмотрим логические знаки ∃ и ∀, рассматривавшиеся во вводном курсе математики. Они имеют следующие названия: ∃ - квантор существования. ∀ - квантор всеобщности. Пусть P (x) - предикат от одной переменной, определенный на множестве M. Исходя из P (x) и квантора ∃ можно составить высказывание ∃x P (x). Это высказывание истинно тогда и только тогда, когда P (x) превращается в истинное высказывание хотя бы при одном значении x из множества M. Пример. Пусть P (x) определен на M— множестве действительных чисел и P (x) = x2 > 4. Тогда ∃x P (x) - это есть ∃x x2 > 4 - истинное высказывание. Пусть P (x) - предикат от одной переменной, определенный на множестве M. Исходя из P (x) и квантора ∀ можно составить высказывание ∀x

P (x).

Это высказывание истинно тогда и только тогда, когда P (x) превращается в истинное высказывание при каждом значении x из множества M. Если P (x) - предикат на M = R из предыдущего примера, то используя ∀, составим высказывание ∀x x2 > 4. Это ложное высказывание, так как при x = 1, получим: 12 > 4. Рассмотрим следующие высказывания

∃x∃y x + y = 3 ∃x∀y x + y = 3 ∀x∃y x + y = 3 ∀x∀y x + y = 3 ∃x∃y x + y = 3 Какие из данных высказываний истинны? Из вводного курса известны следующее равносильности: ∀x P (x) ≡ ∃x P (x) ∃x P (x) ≡ ∀x P (x) Рассмотрим первую равносильность и составим отрицание для обеих частей. Получим ∀x P (x) ≡ ∃x P (x) Это означает, что квантор всеобщности – излишний знак, который в дальнейшем не будет входить в число основных символов, а будет определяемым символом. Поэтому знак ∀ - определяемый знак. Мы можем применять равносильные формулы из алгебре высказываний: A ∨ B ≡ A ∧ B. Представим вместо A высказывание вание ∃y Q(y) и получим

∀x

P (x), вместо B высказы-

∀x P (x) ∨ ∃y Q(y)) ≡ ∀x P (x) ∧ ∃y Q(y) ≡ ∃x P (x) ∧ ∀y Q(y) В процессе математической деятельности, доказательства теорем, выработке понятий мы всегда должны отобразить мыслительную деятельность посредством записи. Для изображения наших понятий, теорем и т. п. мы должны создать специальные знаки. Особую роль в математике играют переменные. В логике посредством переменной мы будем обозначать произвольный предмет (индивид). Например, x может означать число, вектор, прямую и т. п. Также важнейшим понятием в логике являются понятия функции и предиката.

О ПРЕДЕЛЕНИЕ 8 n - арной функцией, определенной на множестве M, называется правило, сопоставляющее каждому набору (a1, a2 , . . . an ) ∈ M однозначно определенный элемент b ∈ M. Если - f – знак для обозначения функции, то записываем f (a1, a2 , . . . an ) = b, гле b – значение функции. В дальнейшем придерживаемся следующих соглашений. Обычно f, g, h, . . . - знаки для обозначения функций – функциональными символы. Для обозначения предикатов, используем предикатные символы: p, q, r. Рассмотрим применение функциональных и предикатных символы в различных математических выражениях. Рассмотрим выражение (x · y). Здесь y, x - переменные, которые мы можем заменять на конкретные значения. · - это знак для функции. Действительно, заменим x на 2, y на 3, получим 2 · 3, которое есть число. Поэтому · - знак для бинарной функции. Рассмотрим выражение x·y =z Заменим x, y, z на числа 2, 3, 7. Получили 2·3 = 7 - ложное высказывание. Здесь «=» бинарный предикатный символ. Рассмотрим выражение из школьного курса sin x. Здесь нужно sin - это сложный символ, не состоящий из частей. Это унарный функциональный символ. Выражение sin x − − ( это понятие будем обсуждать поэднее). Рассмотрим x + y + z = 1 — это тернарный предикат. Параллельность в геометрии – бинарный предикат и  – знак для этого предиката. В аксиомах Пеано употреблялось x , другое обозначение S(x) - это знак для функции, а не для предиката. На приведенных примерах видно что для выражения наших мыслей о математических объектах достаточно следующих знаков. 1. логических знаков; 2. знаков для предикатов – предикатных символов p, q, r, . . . ; 3. знаков для функций – функциональных символов f, g, h, . . . .

Лекция 8. Формализация математических теорий на языке первого порядка В предыдущих лекциях мы построили исчисление высказываний в виде формальной системы. Сейчас мы начинаем более трудный и значительный шаг – рассмотрение формализаций математических теорий. Напомним, что формальная система отражает синтаксические аспекты математической теории, т.е. отражает процесс переноса нашим мыслей о математических объектах в отображающие их записи с помощью специальных символов. Формальная система имеет следующие составные части. • Первая часть формальной системы – ее язык. Чтобы определить язык формальной системы нужно задать символы этого языка и его формулы. • Вторая часть формальной системы – ее аксиомы. Задать аксиомы означает выделить некоторые формулы формальной системы, присвоив им название аксиомы. • Третья часть формальной системы – ее правила вывода, которые служат для получения теорем. В них отражены логические законы, которые используются в математике. Мы будем рассматривать важный случай формальных систем – теории первого порядка. Определение теории первого порядка Теорией первого порядка или просто теорией называется формальная система Т такая, что: • языком формальной системы является язык первого порядка; • аксиомами формальной системы являются логические аксиомы языка теории T и некоторые другие аксиомы, называемые нелогическими аксиомами; • правилами вывода формальной системы являются правило расширения, правило сокращения, правило ассоциативности, правило сечения и правило ∃ введения.

Теперь разъясним эти понятия подробно. Язык первого порядка. Чтобы задать язык первого порядка нужно определить символы языка и определить формулы языка. Символами языка первого порядка является: 1. переменные x, y, z, x, y , . . . , x1, y1, z1, . . . ; 2. n-арные функциональные символы f, g, h, . . . и n-арные предикатные символы p, q, r, . . ., где n
0; 3. символы ¬, ∨, ∃. Следующие символы называются логическими символами: переменные, знаки ¬, ∨, ∃ и знак =. Функциональные и предикатные символы, отличные от знака =, являются нелогическими символами. Они зависят от теории. Логические символы одни и те же во всех теориях. У каждой теории свой, индивидуальный набор функциональных и предикатных символов, отражающих понятия данной теории. Число n-арных функциональных и предикатных символов для данного n произвольно и в, частности, может равняться 0. Однако среди предикатных символов должен быть символ =. Рассмотрим предназначение каждого типа знаков. Символ = будет использоваться для обозначения равенства. Переменные служат для обозначения произвольных объектов теории T . Например, x может означать в арифметике число, в геометрии вектор, прямую и т.п. Функциональные символы является знаками для обозначения функций, а предикатные символы является знаками для обозначения предикатов. Рассмотрим на примере арифметики необходимость каждого из трех типов знаков. Допустим, что мы описываем свойства натуральных чисел, относящиеся к сложению, умножению, отношению > и отношению «следовать за». Тогда мы запишем следующую систему аксиом. N 1. Sx = 0. N 2. Sx = Sy → x = y. N 3. x + 0 = x. N 4. x + Sy = S(x + y). N 5. x · 0 = 0.

N 6. x · Sy = (x · y) + x. N 7. ¬(x < 0). N 8. x < Sy ↔ x < y ∨ x = y. N 9. x < y ∨ x = y ∨ y < x.

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

ские символы: переменные x, y, знаки ¬, ∨ и знак = . Нелогические символы следующие: унарный функциональный символ S для обозначения функции следования, бинарные функциональные символы + и · для выражения понятий сложения и умножения, бинарный предикатный символ < для выражения понятия меньше, константа 0 для обозначения конкретного элемента. Чтобы определить язык математической теории, заданной в виде формальной системы, нужно определить не только символы, но и формулы. Рассмотрим вначале пример, а затем точное определения формулы. Пример. Рассмотрим формулу N2: Sx = Sy → x = y, изображающую следующее свойство. Если последующее число для x равно последующему числу для y , то число x равно числу y. Построение формулы начинается следующим образом: рассматривается x - это переменная, она предназначена для обозначения конкретных натуральных чисел. Переменная x — это терм. Далее используем знак S - это знак для функции «последующий элемент». Выражение Sx — это терм. Терм изображает значение функции S от элемента x. Заметим, что вместо традиционного S(x) мы записываем это выражение без скобок. Дадим точное определение терма. 1. Переменная является термом; 2. если u1, . . . un — термы и f — n-арный функциональный символ, то f u1u2 . . . un — терм; 3. то, что выражение является термом устанавливается несколькими применениями правил 1 и 2. Скобки и запятые отсутствуют среди символов теории первого порядка и поэтому их нет в определении терма. Однако для наглядности мы будем употреблять запись f (u1, u2, . . . , un), подразумевая вместо нее запись f u1 u2 . . . un . Отдельный нульарный функциональный символ - это терм. Действительно, выражение f u1u2 . . . un при n = 0 имеет вид f . Нульарный функциональный символ f можно отождествить с некоторым предметом, т.к. значение функции от 0 переменных не может изменяться. Символ 0 в N1 – это терм. Вернемся к рассмотрению предыдущего примера – формулы из N2 Sx = Sy → x = y отражающей мысль: если объект Sx совпадает с объ-

ектом Sy, т.е. последующий элемент за x равен последующему элементу за y, то x = y. Эта формула построена в несколько шагов сборки 1–5. 1. Рассмотрим переменную x. Это – терм. 2. Рассмотрим переменную y. Это – терм. 3. Рассмотрим выражение Sx, образованное из унарного предикатного символа y и ранее построенного терма x. Это выражение – терм. 4. Возьмем Sy. Это выражение – терм. 5. Рассмотрим символ бинарный предикатный символ =. Построим выражения Sx = Sy и x = y. Эти выражения является атомными формулами. Построим окончательное выражение Sx = Sy → x = y. с помощью определяемого знака →. Это выражение является формулой, но не атомной формулой. Введем точные определения атомной формулы и формулы в языке 1-го порядка. Атомной формулой называется выражение вида pu1u2 . . . un , где p — n-арный предикатный символ, u1, . . . , un — термы. Определение формулы. 1. Атомная формула является формулой. 2. Если A и B - произвольные формулы, то ¬A,

∨AB - формулы.

3. Если A - формула, то ∃xA - формула. 4. Выражение является формулой тогда и только тогда, когда оно получено несколькими применениями правил 1-3. Задание символов и формул, полностью определяет язык 1-го порядка. Отметим, что в пункте 2 речь идет о способе построении формул таком же, как в исчислении высказываний. В пункте 3 добавляется новая конструкция ∃xA. Она предназначена для отражения высказываний следующего вида : существует x, для которого верно A. Например (∃x x2 > 4) существует число с условием x2 > 4). Соглашения о записях. Мы продолжаем использовать соглашения из исчисления высказываний: вместо ∨AB для удобства восприятия записываем A ∨ B, применяем определяемые знаки →, ↔, ∧ и т.п. Сохраняем соглашение о скобках из исчисления высказываний. Заметим,

что у нас нет квантора ∀. Это обусловлено следующей равносильностью: ∀x P (x) ≡ ¬∃x¬P (x), рассматривавшейся во вводном курсе математики. Поэтому ∀ – определяемый знак и запись ∀xP (x) является сокращением для записи ¬∃x¬P (x). Вместо puv и f uv где p - бинарный предикатный символ, а f - бинарный функциональный символ, записываем upv, и uf v. Кроме того, формулу ¬upv будем записывать перечеркивая знак p, например, Sx = 0 изображает формулу ¬Sx = 0.

Лекция 9. Теорема построения При определении терма и формулы мы не использовали скобок. Поскольку нет скобок, то встает задача об однозначности чтения терма или формулы: нельзя ли терм или формулу собрать двумя различными способами? Для того, чтобы избежать повторений, введем термин «указатель». Указателем будем называть терм или формулу. Каждый указатель имеет вид uv1 . . . vn, где u - первый символ указателя. По правилу построения термов и формул он является или переменной или n -арным функциональным или предикатным символом или одним из знаков ¬, ∨, ∃. Припишем этому первому символу индекс следующим образом. • индекс переменной равен 0, • индекс n -арного функционального или n -арного предикатного символа равен n, • индекс ¬ равен 1, индекс ∨ и индекс ∃ равен 2. Таким образом индекс первого символа указателя показывает «сколько строительных блоков» для построения указателя стоит за ним. В качестве примера запишем терм u = x + y в строгом виде и найдем индекс первого символа. Получим u = +xy с первым символом +. Это бинарный предикатный символ, и, поэтому, имеет индекс 2. Введем отношение сравнимости ∼ на множестве всех выражений языка первого порядка. Пусть даны два выражения u и v. Тогда u сравнимо с v, если одно из них имеет начальное вхождение в другое (т.е. получается из другого приписыванием справа некоторого выражения t, возможно пустого). Очевидно, что отношение ∼ рефлексивно и симметрично. Т ЕОРЕМА 10 Пусть u1, u2, . . . un , u1, u2, . . . un - произвольные указатели, причем u1u2 . . . un ∼ u1u2 . . . un Тогда u1 = u1 , u2 = u2 , . . . , un = un . Доказательство индукцией по числу символов в выражении u1, . . . un. Пусть u1 . . . un — контрпример с наименьшим числом символов. Рассмотрим строение указателя u1 . Имеем u1 = uv1 . . . vl , где u - символ u индекса l (так как за ним стоит l блоков). Тогда u – первый символ в u1. Поэтому u1 имеет вид u1 = uv1 . . . vl (l символов, так первый символ u

индекса l). Из сравнимости u1u2 . . . un ∼ u1u2 . . . un следует сравнимость выражений v1 . . . vl и v1 . . . vl : По индукции v1 = v1 , . . . , vl = vl . Из u1 u2 . . . un ∼ u1 u2 . . . un имеем u1 u2 . . . un = u1u2 . . . un t или u1u2 . . . unt = u1u2 . . . un для некоторого выражения t. Сократим на u1 = u1 и применим индукцию к оставшимся сравнимым выражениям. Получим u2 = u2 , . . . , un = un . Теорема доказана. Т ЕОРЕМА 11 (об однозначности построения терма и формулы). Произвольный указатель v однозначно представим в виде uu1 . . . un , где u – символ индекса n, а u1 , . . . , un – указатели. Доказательство. Существование записи v = uu1 . . . un следует из определения указателя (терма или формулы). Докажем единственность. Пусть наряду с записью v = uu1 . . . un то же самое выражение v построено в другом виде v = uv1 . . . vn . Ясно, что первые символы в обоих выражениях равны и во втором выражении за символом u стоит ровно n указателей v1 . . . vn . При этом u — символ индекса n. Приравняем выражения: uu1 . . . un = uv1 . . . vn и сократим на u. Получим равенство u1 . . . un = v1 . . . vn и, тем более, сравнимость u1 . . . un ∼ v1 . . . vn . По предыдущей лемме v1 = v1 , . . . , vn = vn . Получили однозначность записи. Теорема доказана. Эта теорема необходима для корректности многих последующих определений. Она показывает также, что скобки не обязательны для языка первого порядка. Аксиомы теории первого порядка. Аксиомы теории первого порядка делятся на два вида логические и нелогические. Логические аксиомы — законы логики, которые мы используем в математике. В теории первого порядка правила логического выводы строго зафиксированы. В нелогических аксиомах отражают свойства объектов, рассматриваемых в теории. Например, в аксиомах N1 – N9 отражены свойства сложения, умножения и отношения > для натуральных чисел. Операция подстановки. Для их формулировки аксиом нам необходимо понятие подстановки вместо переменной произвольного терма. Эта подстановка может осуществляться в терме или в формуле. Рассмотрим сначала пример. Пусть дан терм u = x + y. Заменим букву x в терме u на на терм z · t. Получим выражение z · t + y, которое является

термом. Возможна замена буквы x не в в терме, а в формуле. Результат подстановки в формулу A вместо переменной x терма u обозначается Ax[u]. Если формула A что-то утверждала про объект x, то, естественно, мы полагаем, что формула Ax[u] то же самое утверждает про объект u. Однако на этом пути возникает затруднение. Пусть, например, мы рассуждаем о целых числах и записали формулу ∃x 2x = y. Она выражает мысль, что y – четное число. Заменим в этой формуле y на u, где u = x + 1. Мы надеемся получить «x + 1 – четное число», однако результат подстановки ∃x 2x = x + 1 – не выражает эту мысль. Выясним природу этого явления. В формуле ∃x 2x = y квантор ∃x не относится к y, значит и в формуле ∃x 2x = x + 1 квантор ∃x не должен относится к x + 1, что не так при прочтении формулы. Данную ситуацию назовем запрещенной подстановкой . Опишем запрещенные подстановки более точно. Введем понятия связанной и свободной переменной в формуле. Пусть дана произвольная формула A. Тогда A - или атомная формула, т.е. A = pu1 . . . un , или A образована из других формул посредством применения несколько раз следующих действий при сборке формулы: ¬B, ∨BC, ∃xB Формулы, из которых строится формула A, называются ее частями, Сама формула также часть A. Пример. Найти части формулы C = ∃x∃y x + y = 1. Имеем три части: A, B, C, что видно из следующего рисунка  ∃x ∃y 

B

  x+y =1     A  C

Действительно: u1 = x + y — терм, u2 = 1 — терм (конкретный предмет, то есть нульарный функциональный символ). Далее = — бинарный предикатный символ, x + y = 1 - атомная формула, ∃y x + y = 1 и ∃x∃y x + y = 1 — формулы. Рассмотрим произвольную формулу A и некоторое конкретное вхождение переменной x в формулу A (может быть несколько вхождений переменной x в формулу A). О ПРЕДЕЛЕНИЕ 9 Вхождение переменной x в формулу A называ-

ется связанным, если оно содержится в некоторой части формулы A следующего вида ∃xB. В противном случае данное вхождение называется свободным. В предыдущем примере x - связанное вхождение, y - также связанное вхождение. Нет свободного вхождения переменной. О ПРЕДЕЛЕНИЕ 10 Переменная x называется свободной в A, если в A есть свободное вхождение x; переменная x называется связанной в A, если в A есть связанное вхождение x; Рассмотрим формулу A, равную x + 1 = 2 ∨ ∃xx + y = 2. Первое вхождение x в A является свободным, а второе — связанным. Поэтому x одновременно свободная и связанная переменная в формуле A. Очевидно, что в атомной формуле каждая переменная является свободной. Введем два вида подстановки. Пусть a, b —термы. Обозначим через bx[a] результат замены каждого вхождение переменной x в терме b на терм a. Т ЕОРЕМА 12 Результат замены bx [a] является термом. Доказательство самостоятельно индукцией по длине терма b. Рассмотрим произвольную формулу A и некоторое конкретное свободное вхождение переменной x в формулу A. Будем говорить, что допустима подстановка Ax[u], заменяющая данное вхождение переменной x на терм u, если A не содержит части вида ∃y B, для любой переменной y из u. Говоря о подстановке, мы всегда подразумеваем допустимую подстановку. Пусть A - формула, b —терм. Обозначим через Ax [a] результат замены каждого свободного вхождения переменной x в формулу A на терм b. Т ЕОРЕМА 13 Результат замены Ax [a] является формулой. Доказательство самостоятельно индукцией по длине формулы A. Теперь мы можем перечислить логические аксиомы. Напомним, что аксиомы делятся на два вида: • логические аксиомы (в них отражены законы логики, а не специфические свойства предметов, которые мы обсуждаем);

• нелогические аксиомы. В них отражены те свойства предметов, которые мы изучаем в рамках данной теории. Логические аксиомы имеют следующий вид, где A — произвольная формула, a — терм. пропозициональная аксиома ¬A ∨ A ; аксиома равенства (два вида) x1 = y1 → x2 = y2 → · · · → f x1 . . . xn = f y1 . . . yn , x1 = y1 → x2 = y2 → · · · → px1 . . . xn → py1 . . . yn аксиома подстановки Ax[a] → ∃xA; аксиома тождества x = x. Аксиома равенства отражает, например, свойство: если предмет x1 совпадает с y1 , . . . , xn совпадает с yn , то значение функции f x1 . . . xn совпадает со значением функции = f y1 . . . yn . Если предмет x1 = y1 , . . . , xn = yn , то справедливость p для x1 . . . xn влечет справедливость для py1 . . . yn . Правила вывода. Теории первого порядка рассматриваются в виде формальных систем. Третьей частью формальной системы являются ее правила вывода, которые служат для получения теорем. Нам нужно привести правила вывода в теориях первого порядка. В этих правилах отражены законы логики, которые мы применяем в математическом доказательстве. Имеется пять правил вывода. Четыре из них заимствованы из исчисления высказываний и одно новое. Правило расширения A (24) B∨A Правило сокращения A∨A (25) A Правило ассоциативности A ∨ (B ∨ C) (A ∨ B) ∨ C

(26)

Правило сечения. Правило ∃ введения.

A ∨ B, ¬A ∨ C B∨C

A→B − где x не является свободной переменной вB. ∃x A → B

(27)

(28)

Лекция 10. Модель теории первого порядка До сих пор мы рассматривали синтаксис языков первого порядка, то есть точные правила для построения термов, формул, задания аксиом и теорем. Наряду с синтаксическим аспектом будем рассматривать семантический аспект теории. Переход от синтаксиса к семантике совершается тогда, когда вместо функциональных и предикатных символов, рассматриваемых как буквы и только, мы начинаем изучать конкретные функции и предикаты на некотором множестве M. Множество M будем называть универсумом, а его элементы – индивидами. Представим, что мы рассматриваем одну из теорий первого порядка— теорию групп и изучаем семантический аспект. Следовательно, мы должны рассмотреть конкретную группу. Это означает, что нужно задать конкретное множество, элементы которого являются элементами группы, которую мы представляем. Вместо бинарного предикатного символа · , рассматриваемой как знак в языке теории групп, мы должны ввести конкретное умножение на множестве M. В общем случае мы должны вместо функциональных символов f ,g,h, . . . рассматривать конкретные функции на множестве M. Вместо предикатных символов p, q, нужно рассмотреть конкретные предикаты на множестве M. Сформулируем обсуждаемые понятия более точно. Структура для языка первого порядка. Пусть L — язык первого порядка. Структура A для языка L состоит из следующего. 1. Непустого множества M, называемого универсумом структуры A ( элементы из M называются индивидами структуры); 2. n-арной функции fA из M в M для каждого n-арного функционального символа f из L; 3. n-арного предиката pA на M для каждого n-арного предикатного символа p из L, отличного от =. Напомним определение функций и предикатов, которое мы применяем. Пусть M — некоторое множество и M n = M × . . . × M—n-ая степень множества M. Элементами M n являются всевозможные строки (a1, . . . , an ), то есть M n = {(a1, . . . , an ) | ai ∈ M}.

Если f —некоторая n-арная функция на множестве M, то она является сопоставлением (a1, . . . , an ) → a ∈ M. Таким образом, a1 , . . . , an— значения аргумента, a—значение функции, т.е. f (x1, . . . , xn) = a при x1 = a1 , . . . , xn = an . Аргументы и значения функции берутся из одного и того же множества M. n-арным предикатом на множестве M называется произвольное подмножества R из декартова произведения M n = M × M × M . . . × M. Если (a1 , . . . , an ) ∈ R , то говорят, что элементы a1 , . . . ,an находится в отношении R. При n = 2 записываем a1 R a2 . Поскольку мы имеем конкретные функции и предикаты на множестве , то мы сможем приписывать нашим формулам значения истина или ложь. В формуле A заменяем значения переменных на конкретные индивиды из M и приписываем формуле значение И или Л ( истина или ложь ). При этом мы будем говорить, что формула A была истинна в A, если все ее значения истинны. Пример. Рассмотрим формулу x + y = 3. Возьмем в качестве универсума множество натуральных чисел, функциональный символ + истолковываем как обычное сложение. Заменяем значение переменной x на 2, а значение переменной y на 1. Значения формулы равно И. При x = 2, y = 3 значение формулы равно Л. Опишем процедуру приписывания значение формуле A более точно. Пусть L — язык первого порядка и A– структура для языка L с универсумом M, n-арными функциями fA , gA , . . . и n-арными предикатами p A , qA , . . . Заменим произвольным образом значения переменных x,y,. . . языка L на конкретные индивиды a,b, . . . из M x = a, y = b, . . .

(29)

По существу это равенство задает отображение переменных языка первого порядка L в универсум M. Назовем такое отображение интерпретацией. Рассмотрим произвольный терм u. Он имеет запись f u1u2un , где u1, . . . , un — ранее построенные термы и f –n-арный функциональный символ. По теореме об однозначности построения терма части u1, . . . , un определены однозначно. Далее разберем однозначно на части каждый из термов u1, . . . , un и т.д. В результате получим сборку u из его частей. Части, с которых начинается сборка терма u имеют некоторый вид

g(x1, x2, . . .), где x1, x2, . . . — переменные. Они должны заменяться на конкретные индивиды a1 , a2, . . . из M в соответствие с интерпретацией (29). В терме g(x1, x2, . . .) заменим функциональный символ g на функцию gA , а переменные x1, x2, . . . на a1 , a2, . . .. Получим индивид gA (a1, a2 , . . .) из M. Подставим это значение в качестве аргумента в следующий терм, участвующий в сборке терма u. Повторив действие несколько раз, получим значение a ∈ M терма u при интерпретации (29). Рассмотрим атомную формулу p(u1, u2, . . . , un), где p– n-арный предикатный символ. Заменим символ p на предикат pA , т.е. на некоторое подмножества R из декартова произведения M n = M × M × M . . . × M. При интерпретации (29) вместо термов u1, u2, . . . , un получатся элементы a1 , . . . , an из M. Если n-ка элементов (a1, . . . , an ) содержится в R, то приписываем атомной формуле p(u1, . . . , un) значение И, в противном случае – значение Л. Рассмотрим процесс приписывания значений И,Л произвольной формуле X. Напомним, что 1. Атомная формула является формулой 2. Если A и B - произвольные формулы, то ¬A,

∨AB - формулы.

3. Если A - формула, то ∃xA - формула 4. Выражение является формулой тогда и только тогда, когда оно получено несколькими применениями правил 1-3. По теореме построения сборка формулы X из ее частей A,B,. . . однозначна. Исходный элемент для сборки формулы X — атомные формулы. При каждой интерпретации (29) атомная формула принимает значение И или Л. Поэтому нужно лишь указать, как вычислять значение формулы Y из значений ее частей при построениях вида (2), (3),(4). Обозначаем значение произвольной формулы Y через V(Y). • Пусть Y = ¬A. Тогда значение формулы Y противоположно значению формулы A, т.е. V (Y ) = ¬V (A) (если V (A) =И, то V (Y ) =–Л и наоборот); • Пусть Y = A ∨ B. Тогда V (Y ) = V (A) ∨ V (B).

• Пусть Y = ∃xA. Наряду с интерпретацией (29), рассматриваем интерпретации, где значения переменных, отличных от x, те же, что и в интерпретации (29). Эти значения переменных, отличных от x, сочетаем с произвольным выбором x = a, x = b, . . . и вычисляем значение формулы A. Если хотя бы один раз получается значение И, то формуле Y = ∃xA приписываем значение И, в противном случае приписываем значение Л. Пусть T — теория с языком L и A — структура для языка первого порядка . Тем самым задан универсум M, заданы n-арные функции fA и n-арные предикаты pA для каждого n-арного функционального символа f для каждого n-арного предикатного символа p из L. При каждой интерпретации каждая формуле принимает значение И или Л. О ПРЕДЕЛЕНИЕ 11 Формула A теории T , называется истинной в структуре A если при каждой интерпретации формула A принимает значение И. Структура A для языка L теории T называется моделью теории T , если при каждой интерпретации все нелогические аксиомы из T принимают значение И. Другими словами структура A для языка L теории T — модель теории T , если все нелогические аксиомы из T истинны в структуре A. В определении речь идет лишь о нелогических аксиомах, т.к. логические аксиомы истинны в любой структуре. Т ЕОРЕМА 14 Пусть A структура для языка L теории T и X — логическая аксиома теории T . Тогда X истинна в A. Доказательство. По определению логическая аксиома X имеет один из видов: пропозициональная аксиома ¬A ∨ A; аксиома равенства, имеющая один из видов a) или б) a) x1 = y1 → x2 = y2 → · · · → f x1 . . . xn = f y1 . . . yn , б) x1 = y1 → x2 = y2 → · · · → px1 . . . xn = py1 . . . yn ; аксиома подстановки Ax[u] → ∃xA; аксиома тождества x = x.

Рассмотрим произвольную интерпретацию, т.е. заменим значения переменных x,y,. . . на конкретные индивиды a,b, . . . из M; x = a, y = b, . . . . Вычислим истинностное значение V (X) формулы X. 1 случай, X = ¬A ∨ A. Тогда V (X) = ¬V (A) ∨ V (A). Если истинностное значение V (A) формулы A равно И, то V (X) = ¬V (A)∨ И=И. Если V (A)= Л, то V (X) = ¬ Л ∨V (A) =И ∨V (A)= И. В случае 2, предположим противное, т.е. при некоторой замене в формула X значений переменных: x1 = a1 , y1 = b1, . . . истинностное значение V (X) равно Л. Тогда посылка a1 = b1 истинна, а заключение a2 = b2 → · · · → f (a1 . . . an ) = f (b1 . . . bn ) ложно (напомним, что A → B –сокращение для ¬A ∨ B и, поэтому, имеет такое правило для приписывания И, Л). Получили совпадение элементов a1 и b1. Аналогично получаем a2 = b2, . . .. и ложность равенства f (a1 . . . an ) = f (b1 . . . bn ). Тогда совпадение элементов a1 = b1, a2 = b2 , . . . влечет совпадение значений функции f (a1 . . . an ) = f (b1 . . . ), противоречие с допущением f (a1 . . . an ) = f (b1 . . . bn ) В случае 2 б) поступаем аналогично. Случай 3, X имеет вид Ax[a] → ∃xA. Предположим противное, т.е. при некоторой интерпретации формула X имеет значение Л. Тогда V (Ax[u]) равно И, V (∃xA) равно Л. Терм u при заменяется при интерпретации на некоторый элемент a ∈ M. Замена x на этот элемент приводит к значению V (Ax[a]) равному И. Итак, существует значение переменной x, которое которое вместе со значениями переменных, отличных от x, таково, что значение V (A равное И. Тогда значение формулы V (∃xA) равно И, что противоречит допущению. Случай 4, X имеет вид x = x. Подставим индивид a переменной x. Получим a = a. Предикат = по своему определению должен быть таковым, что результат замены a = a имеет значение И. Теорема доказана.

Лекция 11. Теорема о полноте Как уже отмечалось, математика, признающая необходимость доказательства утверждений, возникла в древней Греции. Это достижение о древних греков превратило математику в дедуктивную науку. Каждая теорема должна иметь доказательство из множества предложений, называемых аксиомами. Доказательство должно показать, что заключение теоремы следует из данных аксиом только по законам логики. Возникает естественный вопрос: могут ли понятия «законы логики» и «доказательство» быть математически точными? В этом лекции мы положительно ответим на этот вопрос. Итак, мы находимся в следующей ситуации. 1) Мы располагаем интуитивным понятием «B следует из A1 , A2, . . . только по законам логики». 2) Нам нужно описать эти законы логики в виде набора заведомо верных, строгих правила вывода. Сразу ясно препятствие к осуществлению такого замысла. Как можно строго описать интуитивное понятие «следует по законам логики», если это понятие не имеет точного определения ? Исправим ситуацию точно сформулировав понятие «B следует из A1, A2, . . . только по законам логики». О ПРЕДЕЛЕНИЕ 12 Пусть A1, A2, . . . , B – формулы языка L. Формула B является логическим следствием формул A1, A2, . . ., если формула B истинна в каждой структуре A для языка L, в которой истинны формулы A1 , A2, . . .. Тем самым «следование по законам логики» обеспечивает автоматическую истинность A, если известна истинность A1, A2, . . .. Поэтому пункт 1) четко разъяснен. Приступим к реализации пункта 2). Что означают его слова «заведомо верных»? Мы уже имеем следующие пять правил вывода. Формула A – теорема, если она получена с помощью нескольких применений этих правил. Какое требование мы должны соблюдать при изобретении правил вывода? Это требование очевидно. Действительно, сопоставим следующие соглашения.

1. Если A – модель теории, то все аксиомы теории истинны в в модели A ( по определению модели ). 2. Теоремы теории получены по правилам вывода. 3. Правила вывода отражают понятие «логическим следствие». 4. Формула B является логическим следствием формул A1 , A2, . . ., если истинность формул A1 , A2, . . . в структуре A для языка L влечет истинность в A формулы B. Получаем: правило вывода должны быть таковым, что каждая теорема F теории должна являться истинной в любой модели теории. Проверим, что это действительно так для наших 5 правил. Т ЕОРЕМА 15 Каждая теорема F теории первого порядка T истинна в любой модели A этой теории. Доказательство индукцией по шагу n, на котором получена теорема F . Пусть n = 1. Тогда F — аксиома. По определению модели каждая аксиома теории истинна в модели теории. Поэтому F истинна в модели A. Пусть утверждение доказано для всех теорем с шагом < n и F получена на шаге n. При этом применялось одно из 5 правил вывода к теоремам A, B,. . ., полученным на предыдущих шагах 1, 2, . . . , n − 1. По индукции теоремы A, B,. . . истинны в модели A, т.е. принимают только значение И, при любой интерпретации x = a, y = b, . . .

(30)

1 случай, применялось правило расширения A B∨A Тогда F = B ∨ A. При интерпретации (30) значение формулы V (A) равно И. Тогда V (F ) = V (B ∨ A)= И, что и надо. Случаи 2 , 3, 4 когда применялись правило сокращения, правило ассоциативности и правило сечения, аналогичны. 5 случай, применялось правило ∃ введения A→B , ∃x A → B

где

x не является свободной переменной в B.

(31)

Тогда F = ∃x A → B. Предположим противное, при некоторой интерпретации (30) значение формулы V (F ) равно Л. Тогда V (∃x A → B)= И, V (B) = Л. Имеем некоторое значения a переменной x в интерпретации (30). Поскольку x не является свободной переменной в B, то изменение значения x на a1 в интерпретации (30) не изменяет значения V (B). Поскольку V (∃x A)= И, то существует замена x на a1 в интерпретации (30)такая, что V (∃x A)=И. Для этой новой интерпретации V (A)=И и, поэтому, V (A → B)=Л, противоречие. Теорема доказана. Обратное утверждение для данной теоремы является одним из основных положений логики. Т ЕОРЕМА 16 (теорема К.Геделя о полноте). Если формула F теории первого порядка T истинна в любой модели A этой теории, то F теорема теории T . Доказательство теоремы достаточно сложное и опускается. Обсудим значение этой теоремы. Мы можем рассмотреть два множества формул теории первого порядка T , а именно: • M1 — множество теорем теории T ; • M2 — множество формул теории T , истинных в любой модели A этой теории. По определению логического следования формулы B из формул A1, A2, . . . множество M2 есть множество формул, являющихся логическим следствием аксиом теории T . Две предыдущие теоремы утверждают, что M1 ⊆ M2 и M2 ⊆ M1 , т.е. M1 = M2 . Мы имеем пять правил вывода. Естественно задать вопрос. Какие еще правила вывода мы сможем добавить, чтобы получать более обширный список теорем в теории первого порядка. Ответ следующий: нам не нужны никакие новые правила. Действительно, пусть к старому набору правил с 5 правилами добавляется новое правило и получается новый набор правил с новым набором теорем M1 . Ясно, что M1 ⊆ M1 . Как сказано выше новый набор правил должен быть таким, что: каждая теорема теории первого порядка T c этим набором правил истинна в любой модели A

этой теории. Поэтому необходимо M1 ⊆ M2 . С учетом M2 = M1 получаем M1 ⊆ M1 и M1 = M1 . Изомофизм моделей. Категоричные теории Пусть T — теория первого порядка с языком L. Пусть A и B структуры для языка L с универсумами A и B соответственно. По определению структуры каждого n-арного функционального символа f из L определена n-арныя функция fA из A в A и n-арная функция fB из B в B. Также для каждого n-арного предикатного символа f из L определены n-арные предикаты pA на A и n-арные предикаты pB на B. О ПРЕДЕЛЕНИЕ 13 Биективное отображение ϕ универсума A в универсум B является изоморфизмом структуры A на B, если для любых элементов a1 , a2, . . . , an из A для b1 = ϕ(a1), b2 = ϕ(a2 ), . . . , bn = ϕ(an) имеем fB (b1, b2, . . . , bn) = fA (a1 , a2 , an) и pB (b1, b2, . . . , bn) = pA (a1 , a2 , an ), Cтруктуры A и B называются изоморфными, если существует изоморфизм из A в B. Скажем, что теория T категорична, если любые две модели A и B теории T изоморфны. Пример. Пусть T — теория без нелогических символов и с единственной нелогической аксиомой = . Тогда каждая модель теории T содержит только один индивид, и любые две такие модели изоморфны. Можно дать и более сложные примеры, но все такие примеры имеют только конечные модели. Пусть m некоторая мощность. Определение. Теория T называется m–теорией, если она в ее языке L мощность нелогических символов не выше m. Т ЕОРЕМА 17 (о мощности, А.Тарский). Пусть m –бесконечная мощность и T —m-теория, имеющая бесконечную модель. Тогда T имеет модель мощности m. Если T имеет бесконечную модель, то теорема о мощности показывает, что T имеет модели многих разных мощностей, а две модели с различными мощностями не могут быть изоморфными.

Теория T называется частью теории T  , если T и T  имеют один и тот же язык и каждая нелогическая аксиома теории T является нелогической аксиомой теории T  . Теория Т называется конечно аксиоматизируемой, если она имеет только конечное число нелогических аксиом. Т ЕОРЕМА 18 ( теорема компактности, А.И.Мальцев) Формула A теории T является истинной в T тогда и только тогда, когда A является истинной в некоторой конечно аксиоматизируемой части теории T . Доказательство. Ввиду теоремы полноты нам нужно показать лишь, что формула есть теорема теории T тогда и только тогда, когда эта формула есть теорема в некоторой конечно аксиоматизируемой части теории T . Это очевидно, так как в любом доказательстве может использоваться лишь конечное число нелогических аксиом. Следствие. Теория T имеет модель тогда и только тогда, когда каждая конечно аксиоматизируемая часть теории T имеет модель. Доказательство. Беря в качестве теоремы формулу x = x, замечаем, что x = x в любой структуре не является истинной

Лекция 12. Алгоритмы и машина Тьюринга Понятие алгоритма является одним из основных понятий современной математики, имеющим тесную связь с логикой. С интуитивной точки зрения алгоритм – точное предписание, которое задает вычислительную процедуру. Эта процедура начинается с некоторого набора данных и направлена на получение, обусловленного этими данными результата. При этом должно быть совершено конечное число шагов по заранее заданным правилам. Эти правила — точные инструкции (т.е. программа) конечной длины. Они не должны предполагать никакой догадки и вероятностных соображений со стороны человека или машины, нужно только точно исполнять инструкции. Алгоритмом является, например, сложение натуральных чисел, записанных в десятичной системе счисления. В алгебре известен алгоритм Евклида для нахождения НОД целых чисел или многочленов. Слова «вычислительная процедура» нужно понимать в широком смысле, не как только цифровых вычисления. Исходными данными и результатами вычислительного процесса являются конструктивные объекты. Они характеризуются как последовательности некоторого набора символов — алфавита. Вообще говоря, не предполагается, что в результате процедуры будет обязательно получен результат. Если процедуре дана последовательность символов символами из алфавита , то или 1) процедура вычислений должно закончиться после конечного числа дискретных шагов и выдать результат; или 2) вычисления не заканчиваются после конечного числа шагов; также же возможно, что процедура застревает в некоторой точке, и это нельзя истолковать как выдачу значения результата вычислений. Можно поставить задачу нахождения такого алгоритма, который по произвольному набору данных распознает, будет получен выдан результат вычислений или нет. Говоря об алгоритме, подчеркивают такое его свойство, как массовость — требовании найти единый алгоритм для решения не отдельной задачи (например, сложения двух конкретных чисел), а серии отдельных, единичных задач (сложения двух любых чисел).

Если требуемый алгоритм для решения задачи не не существует, то говорят, что рассматриваемая задача алгоритмически неразрешима. Понятия алгоритма всегда занимало важное место в науке. С древнейших времен многие задачи математики заключались в нахождении того или иного алгоритма. Само слово «алгоритм» происходит от латинской транслитерации арабского имени хорезмийского математика 9 в. альХорезми. Длительное время интуитивного понятия алгоритма было вполне достаточно для задач математики и логики. Пусть имеется некоторая алгоритмическая проблема, т.е. необходимо найти алгоритм для решения определенного класса задач. Если такой алгоритм найден, то предложенный способ для решения задачи «признается всеми как алгоритм, исходя из их собственного интуитивного представления об алгоритме». Поэтому не требует точного понятия алгоритма. Однако ситуация становится противоположной, если у нас после длительных, безуспешных попыток нахождения алгоритма возникает гипотеза, что такого алгоритма не существует. Для доказательства несуществования алгоритма необходимо его точное определение. Разработка точного определения алгоритма — одно из самых замечательных достижений в логике и математике. Оно получено в 30 годах 20 в. в трудах Э.Поста, Э.Тьюринга, А.А.Маркова. Основная задача данной лекции — формулировка точного определения алгоритма. Машина Тьюринга Машина Тьюринга — это воображаемое вычислительное устройство, имеющее следующие составные части. Оно имеет ленту, разбитую на ячейки и каретку, расположенную в каждый конкретный момент работы машины над некоторой ячейкой ленты. Каждая ячейка содержит ровно один из символов 0 или 1. Лента представляется конечной, но дополняемой в любой момент ячейками слева и справа для записи новых символов 0 или 1. Если каретка, расположена над некоторой ячейкой с символом 0 (с символом 1), то будем говорить, что каретка обозревает символ 0 (обозревает символ 1). Машины Тьюринга имеет программу. Это конечная последовательность строк из 5 компонент. Пример программы.

(0, 0, (0, 1, (1, 0, (2, 0,

L, 0, 1) R, 0, 1) L, 0, 1) L, 0, 1)

Строка программы имеет вид (i a x y z). Первая компонента в строке i — номер инструкции. Поэтому предыдущая программа имеет инструкции с номерами 0, 1 и 2. Вторая компонента равна 0 или 1. Выполняя инструкцию с номером i, машина смотрит обозреваемый кареткой символ. Если он равен 0, то исполняется строка с началом i 0; если обозреваемый символ равен 1, то исполняется строка с началом i 1. Если строки с началом i нет, то машина останавливается. Это единственное условие остановки машины Тьюринга. Символы x, y, z в исполняемой строка описывают выполняемые действия. • Записать в обозреваемую ячейку x. При этом x = 0 или x = 1. Поэтому содержимое обозреваемой ячейки останется прежним или сменится на противоположное, например, 0 заменится на 1. • Компонента y равна R или L. При y = R нужно сдвинуть каретку на одну ячейку вправо, при y = L — влево. • Перейти к инструкции с номером z. Возможно, что инструкции с номером z нет, тогда остановка машины. Тем самым выполнение инструкции q0 первый такт работы машины Тьюринга, затем второй такт — выполнение другой инструкции и так далее. В начале работы на ленте имеется исходный набор из символов 0,1 — входные данные, а после остановки на ленте выходные данные. Пример. Пусть дана машина Тьюринга со следующей программой 0 0 1 R 0. Пусть входные данные следующие — на ленте во всех ячейках расположен символ 0. Выполним вначале инструкцию с номером 0. Так как обозреваемый кареткой символ равен 0, нужно выполнить следующее. 1. Заменить этот символ на 1.

2. Сдвинуть каретку вправо. 3. Применить инструкцию с номером 0. Итак, возникла одна единица, каретка снова обозревает 0 и заново выполняются действия 1)–3). Поэтому машина Тьюринга работает бесконечно, заполняя ленту символами 1. Опишем вычисление значений n-арной функции машиной Тьюринга. Рассмотрим произвольное натуральное число x = 0, 1, 2, . . . . Изобразим его на ленте как группу из x + 1 единиц. Данную группу из x + 1 единиц обозначаем знаком x. Например, группа из 3 единиц 111 изображает число 2, а группа 1 изображает число 0. Для изображения последовательности x1, x2, . . . xn используем последовательность символов ленты, равную x1, x2, . . . xn, где группы единиц разделены символом 0. Обычно мы рассматривали всюду определенные n-арные функции. Определим теперь частичную n-арную функцию f (x1, x2, . . . , xn), определенную на множестве натуральных чисел {0, 1, 2, . . . }. Это правило, которое сопоставляет некоторым наборам (a1, a2 , . . . , an ) натуральных чисел однозначно определенное натуральное число f (a1, a2 , . . . , an )— значение функции f при данном наборе аргументов. Множество всех наборов (a1 , a2 , . . . , an ), для которых определено значение функции, называется областью определения функции и обозначается через Dom(f). Множество всех значений функции f называется областью значений функции и обозначается через Ran(f). Мы будем говорить, что машина Тьюринга M с программой q0 , q1 . . . qn , вычисляет частичную n-арную функцию f , если выполняется следующие условия. 1) Если (a1 , a2, . . . , an ) находится в области определения функции f , то M начиная с инструкции q0 и обозревая самый левый символ строки (a1, a2 , . . . , an ) ( остальная часть ленты пуста), на некотором шаге останавливается, обозревая самый левый символ строки f (a1 , a2, . . . , an ) ( часть ленты справа от строки пуста). 2) Если (a1, a2 , . . . , an) не находится в области определения функции f , то M никогда не останавливается. Пример. Указать машину Тьюринга, вычисляющую сумму натуральных чисел x + y. Рассмотрим машину M со следующей программой ( рядом с каждой инструкцией – комментарий).

01 00 11 10 21 31 41 40

1 R 0 прохождение через x 1 R 1 заполнение промежутка 1 R 1 прохождение через y 0 L 2 конец y 0 L 3 стирание 1 0 L 4 стирание другой 1 1 L 4 движение назад 0 R 5 остановка Тезис Черча

Теперь мы располагаем всеми необходимыми определениями для точной формулировки понятия алгоритм. При рассмотрении алгоритма наиболее часто речь идет о вычислении значений функций. n- арная частичная функция f называется вычислимой, если существует алгоритм для вычисления функции f . Тем самым это те функции, для которых мы должны дать точное определение. n- арная частичная функция f называется рекурсивной, если существует машина Тьюринга вычисляющая функцию f . Тем самым это те функции, для которых существует точное определение, которое разъяснено выше. При этом ясно, что каждая рекурсивна функция вычислима. Точным определением понятия алгоритма является следующее положение, выдвинутое Алонзо Черчем в 1936 г. Тезис Черча. Каждая вычислимая функция рекурсивна. Сможем ли мы доказать тезис Черча? Нет, т.к. у нас нет точного определения вычислимости. Это положение является соглашением, возникшим в результате длительного исследования интуитивного понятия алгоритма. Показана рекурсивность огромного количества вычислимых функций. Никто не сумел построить вычислимую функцию, рекурсивность которой нельзя было бы доказать, или хотя бы указать правдоподобный метод построения такой функции. Тезис Черча — естественнонаучный факт, подтвержденный опытом, накопленным математикой за весь период ее развития.

Алгоритмически неразрешимые проблемы Разработка точного определения алгоритма позволила получить строгое доказательство несуществования алгоритма в ряде известных математических задач. Десятая проблема Гильберта Рассмотрим уравнение f (x1, x2, . . . , xn) = 0, где f (x1, x2, . . . , xn) — многочлен от n нескольких переменных с целыми коэффициентами. Такие уравнения называются диофантовыми в честь греческого математика Диофанта. Простейшее из таких уравнений ax + by = c имеет хорошо известный в теории чисел алгоритм для нахождения решений. В августе 1900 г. в Париже состоялся II Международный конгресс математиков, на котором Д.Гильберт прочитал доклад «Математические проблемы». Среди 23 проблем, поставленных Д.Гильбертом, десятая проблема может быть сформулирована в следующем виде. Отыскать алгоритм для распознавания по произвольному диофантовому уравнению разрешимо ли это уравнение в целых числах. Разумеется в то время речь шла лишь о положительном решении десятой проблемы Гильберта - об «указании способа». То, что «способ решения» может отсутствовать - мысль о такой возможности в 1900 г. никому не приходила в голову. Лишь в 30-х гг. оформилось математически точное понятие алгоритма. К концу 40-х гг. вера в адекватность математически точного понятия алгоритма укоренилась уже настолько, что можно было серьезно ставить вопрос об отрицательном решении десятой проблемы Гильберта и других классических проблем, касающихся существования алгоритмов. В начале 50 годов появились работы, направленные на доказательство несуществования такого алгоритма. В 1970 году Ю.Матиясевич завершил доказательство алгоритмической неразрешимости десятой проблемы Гильберта. Понятие алгоритма появляется не только тогда, когда речь идет о вычислении значений функций. Разрешающим методом для формальной системы F называется такой метод, с помощью которого для любой данной формулы A из F мы можем за конечное число шагов решить, будет ли A теоремой системы F или нет. Проблема разрешимости состоит в следующем: найти такой метод (алгоритм) или доказать, что его не существует.

Можно сформулировать еще более общую проблему, чем проблема разрешимости для формальных систем. Предположим, что B — подмножество множества A. Разрешающим методом для B в A называется такой метод, с помощью которого для каждого элемента x из A мы можем за конечное число шагов решить, принадлежит x множеству B или нет. В десятой проблеме Д.Гильберта в качестве A выступают все диофантовы уравнения, а в качестве B диофантовом уравнения, разрешимые в целых числах.

Лекция 13. Теорема Геделя о неполноте Язык первого порядка L называется расширением языка первого порядка L, если каждый нелогический символ из L является нелогическим символом в L. Теория T  называется расширением теории T , если выполнены следующие условия. 1. Язык теории T  является расширением языка теории T . 2. Каждая теорема теории T является теоремой теории T  . Ясно, что для 2 необходимо и достаточно, чтобы каждая нелогическая аксиома теории была теоремой теории T  ( но не обязательно, чтобы каждая нелогическая аксиома теории была нелогической аксиомой теории T  ). Рассмотрим теорию N , которая описываем основные свойства натуральных чисел. Она имеет следующую систему аксиом. N 1. Sx = 0. N 2. Sx = Sy → x = y. N 3. x + 0 = x. N 4. x + Sy = S(x + y). N 5. x · 0 = 0.

N 6. x · Sy = (x · y) + x. N 7. ¬(x < 0). N 8. x < Sy ↔ x < y ∨ x = y. N 9. x < y ∨ x = y ∨ y < x.

В большинстве математических теорий нам потребуются основные свойства натуральных чисел. Поэтому вполне естественно считать, что эти теории являются расширением теории N . Следующее естественное условие, предъявляемое к теориям – возможность проверять доказательство теорем. Одним из действий при проверке доказательства является распознавание аксиом. Обозначим множество формул теории T через F , а множество аксиом через F1 . Мы должны иметь алгоритм, позволяющий для произвольной формулы A теории T определять является ли она аксиомой. Такие теории назовем рекурсивно аксиоматизированными. Такая постановка может странной, т.к. в реальных случаях мы имеем обычно конечный или бесконечный, но достаточно простой список аксиом. Однако, такое ограничение не является естественным. Приведем пример, где вид аксиом не столь прозрачен. Теория структуры A. Пусть T — теории первого порядка с языком L. Рассмотрим произвольную структуру A для языка L теории T . Введем

новую теорию T  с языком L. Нужно задать только аксиомы для теории
T . Рассмотрим произвольную формулу A теории T . Считаем ее аксиомой для теории T  тогда и только тогда, когда формула A истинна в структуре A. Полученная теории T  называется теорией структуры A. Упражнение. Доказать, что понятие теоремы и аксиомы в теории T  совпадают. Теория T называется противоречивой, если каждая формула теории T является теоремой теории T ; в противном случае T называется непротиворечивой. Теория T называется полной, если для каждой замкнутой формулы A теории T ровно одна из формул A или ¬A является теоремой теории T . Замкнутая формула A не имеет свободных переменных и не может иметь разных значений при интерпретациях. В обычной математической практике мы рассматриваем замкнутую формулу A как некоторое высказывание о объектах теории. Поэтому либо высказывание A, либо высказывание ¬A является истинным высказыванием и мы надеемся получить A или ¬A как теорему формальной системы. Однако это не всегда достижимо. Т ЕОРЕМА 19 (о неполноте, К.Гедель) Пусть T — рекурсивно аксиоматизированная теории первого порядка T , являющаяся расширением теории N . Тогда теории T неполна. Доказательство теоремы достаточно сложное и опускается. Теорема неполноте имеет важные следствия, касающиеся аксиоматического метода. Идея аксиоматического метода состоит в следующем. Пусть имеется некоторая неаксиоматическая теорию T0, для которой мы хотим построить соответствующую аксиоматическую теорию T . В теории T0 мы используем некоторые функции и предикаты для выражения понятий теории T0 о ее объектах. При переходе к аксиоматическому построению теории мы вводим язык для выражения утверждений о понятиях теории T0 . Для этого вводим язык первого порядка L теории T . После задания языка мы получаем следующую ситуацию. Если A –замкнутая формула языка L, то представляя те функции и предикаты для для конкретных объектов теории T0 , мы припишем ей значение истина или ложь. Те формулы, которые имеют значение истина — это истинные утверждения об объектах неаксиоматической

теории T0. Теперь мы хотим разделить их на два типа: аксиомы и теоремы, полученные из аксиом с помощью правил вывода теории T . Наше естественное требование истинные утверждения про объекты неаксиоматической теории T0 должны выводиться из аксиом в аксиоматической теории T. Требование, чтобы мы могли опознавать доказательство, означает (как отмечалось ранее), чтобы наша теория T должна быть рекурсивно аксиоматизированной. Естественно мы должны среди аксиом затребовать простейшие свойства натуральных чисел, выраженные в аксиомах теории N ( т.е. теория должна быть расширением теории N ). Однако по теореме К.Геделя о неполноте существует некоторая замкнутая формула A языка L такая, что ни A ни ¬A не являются теоремой теории T . Поэтому мы имеем A или ¬A – истинное утверждение об объектах теории T0, которое нельзя получить средствами вывода в аксиоматической теории T . Это показывает невыполнимость первоначального замысла Гильберта свести все содержательное математическое познание к формализму.

Литература [1] Гильберт Д., Бернайс П. Основания математики. - М.: Наука, 1979. [2] Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука, 1979. [3] Игошин В.И. Задачник-практикум по математической логике. - М.: Просвещение, 1986. [4] Клини С.К. Математическая логика. - М.: Мир, 1973. [5] Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. - М.: Наука, 1995. [6] Мальцев А. И. Алгоритмы и рекурсивные функции. - М.: Наука, 1965. [7] Мендельсон Э. Введение в математическую логику. - М.: Наука, 1976. [8] Новиков П.С. Элементы математической логики. - М.: Наука, 1973. [9] Справочная книга по математической логика: В 4-х частях. - М.: Наука, 1983 [10] Стяжкин Н. И. Формирование математической логики. - М.: Наука, 1967. [11] Черч А. Введение в математическую логику. - М.: Изд. ин. лит., 1960. [12] Шенфилд Д.Р. Математическая логика. - М.: Наука, 1975. Популярная литература. [13] Гжегорчик А. Популярная логика. - М.: Наука, 1979.

[14] Гиндикин С.Г. Алгебра логики в задачах. - М.: Наука, 1972. [15] Градштейн И.С. Прямая и обратная теоремы. Элементы алгебры логики. - М.: Наука, 1972. [16] Депман И.Я. Первое знакомство с математической логикой. - Л.: 1965. [17] Калужин Л.А. Что такое математическая логика. - М.: Наука, 1964. [18] Кац М., Улам С. Математика и логика. Ретроспектива и перспективы. - М.: Мир, 1971. [19] Корельская Т.Д., Падучева Е.В. Обратная теорема. - М.: Знание, 1978. [20] Столяр А. А. Элементарное введение в математическую логику. Пособие для учителей. - М.: Просвещение, 1965.