Лекции по математической логике и теории алгоритмов. Лекции - Математическая логика и теория алгоритмов - файл n1.doc
Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся математической логикой. Книга включает около 200 задач различной трудности.
Логика высказываний.
Высказывания и операции
«Если число п рационально, то п - алгебраическое число. Но оно не алгебраическое. Значит, п не рационально.» Мы не обязаны знать, что такое число п, какие числа называют рациональными и какие алгебраическими, чтобы признать, что это рассуждение правильно в том смысле, что из двух сформулированных посылок действительно вытекает заключение. Такого рода ситуации - когда некоторое утверждение верно независимо от смысла входящих в него высказываний составляют предмет логики высказываний.
Такое начало (особенно если учесть, что курс логики входил в программу философского факультета, где также изучалась «диалектическая логика») настораживает, но на самом деле наши рассмотрения будут иметь вполне точный математический характер, хотя мы начнём с неформальных мотивировок.
Оглавление
Предисловие
1. Логика высказываний
1.1. Высказывания и операции
1.2. Полные системы связок
1.3. Схемы из функциональных элементов
2. Исчисление высказываний
2.1. Исчисление высказываний (ИВ)
2.2. Второе доказательство теоремы о полноте
2.3. Поиск контрпримера и исчисление секвенций
2.4. Интуиционистская пропозициональная логика
3. Языки первого порядка
3.1. Формулы и интерпретации
3.2. Определение истинности
3.3. Выразимые предикаты
3.4. Выразимость в арифметике
3.5. Невыразимые предикаты: автоморфизмы
3.6. Элиминация кванторов
3.7. Арифметика Пресбургера
3.8. Теорема Тарского Зайденберга
3.9. Элементарная эквивалентность
3.10. Игра Эренфойхта
3.11. Понижение мощности
4. Исчисление предикатов
4.1. Общезначимые формулы
4.2. Аксиомы и правила вывода
4.3. Корректность исчисления предикатов
4.4. Выводы в исчислении предикатов
4.5. Полнота исчисления предикатов
4.6. Переименование переменных
4.7. Предварённая нормальная форма
4.8. Теорема Эрбрана
4.9. Сколемовские функции
5. Теории и модели
5.1. Аксиомы равенства
5.2. Повышение мощности
5.3. Полные теории
5.4. Неполные и неразрешимые теории
5.5. Диаграммы и расширения
5.6. Ультрафильтры и компактность
5.7. Нестандартный анализ
Литература
Предметный указатель
Указатель имён.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
- fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.
Купить эту книгу
Скачать книгу Лекции по математической логике и теории алгоритмов, Часть 2, Языки и исчисления, Верещагин Н.К., Шень А., 2012 - pdf - depositfiles.
Лектор: А. Л. Семенов
Лекция 1
Введение 1
Задача математической логики и теории алгоритмов 1
Математические результаты математической логики и теории алгоритмов 2
Современная цивилизация и роль МЛиТА 2
Построение математики. Теория множеств 5
Программа математического исследования математической деятельности - Гильберт 9
Общая идея 9
Итоги Программы Гильберта 12
Язык и аксиомы теории множеств. I. Примеры 12
Логические символы и их смысл (семантика) 12
Примеры аксиом существования множеств 13
Введение
Задача математической логики и теории алгоритмов
Задача, решаемая математической логикой и теорией алгоритмов – построить систему математических определений и теорем, позволяющих математически описывать и исследовать следующие виды деятельности человека:
Доказательство теорем и определение математических понятий
Описание отношений между математическими объектами
Получение следствий из экспериментально установленных утверждений, из гипотез и т. п.
Проектирование устройств (механических, электронных и т. д.) с заданными свойствами и функциями.
Создание и выполнение формальных предписаний (описание и применение алгоритмов и программ)
Установление соответствия между описанием требуемого результата и алгоритмом, предназначенным для достижения этого результата (доказательство правильности)
Математические результаты математической логики и теории алгоритмов
Занимаясь указанным исследованием, мы получим и результаты, относящиеся к:
Множествам и отношениям, которые можно описать на том или ином языке
Множествам доказуемых формул
Множествам истинных формул (имеется фундаментальная разница с п. 2)
Множествам математических структур, в которых истинны формулы из заданного множества
Классам функций, которые вычисляются алгоритмами
Существованию алгоритма, выясняющего истинность или доказуемость формул
Сложности вычислений
Сложности объектов
Современная цивилизация и роль МЛиТА
Существенный прогресс в развитии человечества связан с созданием машин для обработки материальных объектов, получения и передачи энергии (используемой этими машинами), средств транспорта, освещения и т. д.В течение столетий у людей возникала идея о создании машин для работы не с материей и энергией, а с информационными объектами. Более того, такие машины создавались и даже успешно работали, например, машина, позволяющая выполнять арифметические действия – арифмометр (Б. Паскаль).
В первой половине XX века было дано общее описание того, какие возможны способы формальной переработки информации человеком. К середине XX века были открыты физические принципы, сделавшие реальным создание устройств, которые могут хранить очень много информации и очень быстро ее обрабатывать. Были созданы универсальные устройства – компьютеры, которые могут делать все то, что формализовано может делать человек, но гораздо быстрее, чем человек.
При совсем общем взгляде можно сказать, что математическая логика дает фундамент для теоретической математики, а теория алгоритмов – для вычислительной практики (использования компьютеров). Более детальное рассмотрение показывает, однако, что многие достижения математической логики нашли приложения в разработке и применении информационных технологий, а алгоритмические рассмотрения существенны и в различных разделах чистой математики.
Вехи истории
Важными моментами в становлении современных представлений о том, что представляют собой математические доказательства и вычисления, стали достижения немецких математиков конца XIX - начала XX вв.Особую важность имело выступление Давида Гильберта (23.01.1862 - 14.01.1943) на II Международном конгрессе математиков (Париж, 1900). Там он сформулировал 23 т. н. Проблемы Гильберта – важнейших для математики того времени и для развития математики в XX в. Некоторые из проблем Гильберта представляли собой вопрос о выяснении истинности конкретного математического утверждения, другие можно назвать скорее предложением осуществить какую-либо программу исследований.
Проблемы I, II, X из списка Гильберта относятся к предмету математической логики и теории алгоритмов.
Из семи математических Проблем тысячелетия первая также относится к нашему предмету (ее не было среди Проблем Гильберта).
В курсе будут обсуждаться упомянутые выше проблемы из области математической логики и теории алгоритмов и современный взгляд на них.
Организационные замечания
Авторы курса считают, что лучший способ изучить математику и стать математиком – это делать математику самому. Под математиками мы здесь понимаем всех, для кого существенной частью их профессиональной деятельности (а для многих – и всей жизни) является работа с математическими объектами с использованием математических способов деятельности. Существенная часть деятельности в сфере информационных технологий, например, устроена именно так. Под «деланием математики» мы имеем в виду решение задач, при этом, в первую очередь , не таких, какие больше всего решают в школе, или в курсе математического анализа на первом курсе университета. Мы имеем в виду задачи, где нужно придумать что-то новое. Конечно, при освоении новой области математики многие из этих задач должны быть простыми и давно решенными, но они не отличаются принципиально от задач, которые приходится решать профессиональному математику и программисту.Задачи того сорта, о котором мы сейчас говорим, будут формулироваться и на лекциях, и на упражнениях по курсу. Не все формулируемые задачи будут совсем простыми. Более того: некоторые из них решены в математике совсем недавно, будут и такие, которые еще не решены, и такие, которые вовсе не имеют решения (но порешать которые – полезно).
Мы предлагаем вам заниматься решением задач во время всего изучения курса и обсуждать их со своим преподавателем (и, конечно, между собой). Это:
Поможет вам лучше понимать содержание лекций и всей математической области, к которой относится курс
Лучше подготовиться к экзамену и частично его «сдать» (решение задач по ходу курса вам «зачтется» на экзамене, подробнее вам расскажут ваши преподаватели)
Попробовать себя в перспективной области математики и, возможно, выбрать ее для своей специализации в Университете, что может оказаться полезным для Вашей работы после университета.
Материалы очередной лекции будут выкладываться в интернете на сайте http://lpcs.math.msu.su/vml2013/
Кроме них, с содержанием курса можно познакомиться по книгам:
Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов, изд. МЦНМО (mccme.ru)
И. А. Лавров, Л. Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов,
Наконец, последнее. Одним из прикладных результатов математической логики и теории алгоритмов является автоматизация различных компонентов математической деятельности. В частности , автоматизации поддается проверка математических доказательств некоторых видов. Область такой автоматизации, естественно, постоянно расширяется за счет развития самих алгоритмов автоматизации, большего понимания математиками, как эти алгоритмы применять, накопления опыта и роста вычислительных возможностей. Сегодня наиболее популярной и эффективной вычислительной средой для автоматизации проверки доказательств является Coq. Наша кафедра ведет практикум по Coq, где можно научиться эту среду применять, представить себе ее возможности и ограничения.
Построение математики. Теория множеств
Современное построение математики, в частности то, как ее изучают в университетах, основано на теории множеств. Сейчас мы напомним некоторые базовые понятия этой теории.Для задания множеств часто используются фигурные скобки. Внутри них можно поместить все элементы задаваемого множества: {2, 14, 5.4} или особым образом его описать: {x|x – действительное число и sin(x)>0}.
Мы используем следующие обозначения для операций над множествами: принадлежность элемента множеству ∊, включение множеств ⊂ , объединение ∪, пересечение ∩, разность \.
Пусть у нас имеются два объекта x ,y . Упорядоченной парой x; y > называется объект, по которому однозначно восстанавливаются x , y , иначе говоря: x;y > = x′;y ′> → ( x = x ′ y = y ′).
Произведением x X y двух множеств x и y называется множество всех упорядоченных пар u; v >, где u ∊ x и v ∊ y .
Аналогично, определяются упорядоченные n –ки объектов и n -ая степень x n множества x . Можно договориться, что x 1 – это x .
Отношением между множествами x , y называется любое подмножество их произведения x X y .
n -местным отношением на множестве x называется любое подмножество n –ой степени этого множества.
Отношение f между x и y называется функцией из x в y , если из совпадения первых компонентов любых двух элементов отношения f вытекает совпадение вторых.
Областью определения функции называется множество первых ее компонентов.
Если область определения функции из x в y совпадает с x , то говорят, что функция отображает x в y и пишут f : x → y . Множество всех функций, отображающих x в y , обозначается y x .
Функция f : x → y называется биекцией между x и y , или биекцией из x в y , или изоморфизмом x и y , если из совпадения вторых компонентов элементов f вытекает совпадение первых, и, кроме того, вторые элементы f образуют все множество y . Изоморфные множества называются также равномощными.
Множество называется счетным, если оно равномощно натуральному ряду.
Задача. Доказать, что всякое подмножество натурального ряда равномощно или его начальному отрезку (что то же самое – некоторому его элементу) или всему натуральному ряду.
Сформулированное в последней задаче элементарное наблюдение – что часть может быть изоморфна целому, вероятно, кажется студентам второго курса тривиальным. Но оно было одним из первых открытий теории множеств.
Конечные множества можно сравнивать по величине. Если одно изоморфно подмножеству другого, то в нем меньше элементов. В случае бесконечных множеств это не так. Эта ситуация была описана Галилео Галилеем в следующем диалоге, который мы приводим с сокращением:
Беседы и математические доказательства, касающиеся двух новых отраслей науки, относящихся к механике и местному движению,
синьора Галилео Галилея Линчео, философа и первого математика светлейшего великого герцога тосканского
Сальвиати. …количество всех чисел вместе - квадратов и не квадратов - больше, нежели одних только квадратов; не так ли?
Симпличио. Ничего не могу возразить против этого.
Сальвиати. Квадратов столько же, сколько существует корней, так как каждый квадрат имеет свой корень и каждый корень свой квадрат; ни один квадрат не может иметь более одного корня и ни один корень более одного квадрата.
Сагредо. Что же нужно сделать, чтобы найти выход из такого положения ?
Сальвиати. Я не вижу возможности никакого другого решения, как признать, что свойства равенства, а также большей и меньшей величины, не имеют места там, где дело идет о бесконечности, и применимы только к конечным количествам. Поэтому, когда синьор Симпличио предлагает мне неравные линии и спрашивает меня, как может быть, чтобы в большей из них не содержалось большего количества точек, чем в меньшей, то я отвечаю ему, что их там не больше, не меньше и не одинаковое количество, но бесконечное множество в каждой.
Однако и среди бесконечных множеств некоторый порядок все-таки есть, как показывает следующая теорема, также объявленная без доказательства Кантором и вскоре доказанная другими немецкими математиками.
Теорема Кантора – Бернштейна. Пусть существует биекция между множеством A и подмножеством множества B , а также биекция между множеством B и подмножеством множества A . Тогда множества A и B – равномощны.
Задача. Доказать Теорему Кантора – Бернштейна.
Задача. Можно ли сравнить любые множества по мощности, то есть, верно ли, что для любых A и B , или A равномощно подмножеству B , или B равномощно подмножеству A ?
Среди функций мы выделяем свойства – функции, принимающие только значения 0 и 1. Всякое свойство задает отношение – множество элементов, на которых ее значение – 1. Любая функция f : x → B называется характеристической (на x ). Заметим, что в наших обозначениях и соглашениях B={0,1}=2. Таким образом, множество всех характеристических функций на x получает обозначение B x или 2 x .
Задача. Построить изоморфизм между множеством характеристических функций на x и множеством подмножеств множества x .
Задача. Доказать, что множество подмножеств любого множества ему не изоморфно.
Идея решения [Диагональ Кантора]. Пусть изоморфизм G : x → 2 x существует. Рассмотрим для каждого элемента y из нашего множества x соответствующее ему подмножество G (y ). Можем ли мы из элементов x собрать подмножество C , которое отличалось бы от множества G (y ) «на элементе y » ? Или, что то же самое, как построить одну характеристическую функцию f C , которая отличалась бы от характеристической функции множества G (y ) «в точке y » при всяком y ?
Если x
- множество натуральных чисел, то доказательство приобретает ясную графическую форму. Будем называть число y
, которое переходит в характеристическую функцию f
, номером функции f
.
Аргумент № функции |
0 |
1 |
2 |
3 |
4 |
… |
0 |
1 |
0 |
0 |
1 |
0 | |
1 |
1 |
1 |
0 |
1 |
0 | |
2 |
1 |
0 |
0 |
1 |
1 | |
3 |
0 |
0 |
0 |
1 |
0 | |
4 |
0 |
1 |
0 |
1 |
0 |
………
В этой таблице в строке с номером n выписана характеристическая функция с номером n . В таблице нет функции, получающейся из ее диагонали сменой 1 на 0 и 0 на 1 (операцией отрицания).
Задача . Доказать, что множество действительных чисел равномощно множеству подмножеств натурального ряда.
Программа математического исследования математической деятельности - Гильберт
Общая идея
Давиду Гильберту принадлежит представление о математике, как области математически описываемой деятельности, осознание важности исследований математической деятельности средствами самой математики, представление программы таких исследований – Программы Гильберта.Программы Гильберта исследования математики можно представить следующим образом:
Математика может быть представлена как система
аксиом – утверждений, которые мы принимаем за истинные и
правила доказательства – получения новых утверждений.
Практика математической деятельности должна убеждать нас в том, что выбранная система позволяет строить все нужные доказательства. В идеале может так случиться , что всякое математическое утверждение можно доказать или опровергнуть с помощью этой системы. (Это свойство называется полнотой .)
Некоторые математические доказательства являются «особенно надежными и убедительными». К ним относятся, например, арифметические вычисления. Используя только их, можно убедиться в том, что выбранная для математики система не позволяет получить противоречий. (Это свойство называется непротиворечивостью .) Более того, могло бы оказаться, что и полноту математики можно также доказать с помощью простых, понятных и убедительных рассуждений.
Заметим, что свойство непротиворечивости куда более существенно. Априори можно было бы представить себе научную теорию, в которой противоречие находится где-то на периферии и относится к каким-то несущественным вопросам. Однако, устройство всех основных систем математического доказательства таково, что доказуемость одного противоречия (например, того, что произведение каких-то двух очень больших чисел равно какому-то третьему и еще другому – четвертому) немедленно приводит к доказуемости любого математического утверждения. Противоречие нельзя «локализовать».
Первые шаги в достижении целей Программы Гильберта были сделаны еще до ее формулирования. Более того, Программа логически вытекала из них. Вот эти шаги.
Доказательства. Логика. В конце XIX века стало ясно, как нужно формализовать систему рассуждений. Эта формализация получила свое завершение в работах Готлоба Фреге (8.11.1848 - 26.07.1925).
Теория множеств. Еще одним достижением математики конца XIX века стало понимание того, что вся математика может быть единообразно представлена в терминах множеств (так, как это делается в современных математических курсах и мы напоминали выше). Это было сделано в работах Георга Кантора (3.03.1845 - 6.01.1918).
Таким образом, оставалось только выбрать подходящую систему аксиом и дальше идти по пути доказательства непротиворечивости и полноты. Надежда на получение таких доказательств простыми и надежными средствами была связана со следующим. Использование аксиом и правил доказательства выглядит довольно простым процессом работы с формулами. Сами формулы – это несложные объекты, цепочки символов. Математика представляется игрой, вроде, например, шахмат. Предположим, что нам нужно доказать, что какая-то позиция в шахматах невозможна. В принципе – это, конечно, можно сделать, перебрав всевозможные шахматные партии. Но можно представить себе и более простые рассуждения, основанные, например, на том, что фигур на поле не добавляется, что слоны бывают белопольные, а бывают чернопольные, и т. д. Такие рассуждения, скорее всего, не будут использовать действительные числа, интегралы и еще более сложные математические объекты.
Система аксиом для теории множеств была, в основном, построена в течение первых десятилетий XX века, первая формулировка, близкая к современной, принадлежала Эрнсту Цермело (27.7.1871 ‒ 21.5.1953) и была им опубликована в 1908 году.
Итоги Программы Гильберта
Что же произошло с Программой Гильберта в дальнейшем? Мы сейчас коротко это сформулируем, а в дальнейшем курсе объясним подробнее.С одной стороны, Программа была успешно реализована:
Аксиоматическая теория множеств является основанием современной математики.
В частности, в тридцатые годы сформировалась группа математиков под коллективным псевдонимом Н. Бурбаки. Максимум ее творческой активности пришелся на 1950 – 60-е гг. Эта группа последовательно и систематически представила существенную часть современной математики, как построенную на базе теории множеств.
Математика – не полна и не может быть полной.
Непротиворечивость математики невозможно установить не только какими-то надежными убедительными средствами.
Язык и аксиомы теории множеств. I . Примеры
Формулирование системы доказательств в математике (теории множеств) мы начинаем с описания логического языка.Логические символы и их смысл (семантика)
Логические значения: символы И (истина), Л (ложь), или символы 1, 0. Множество из двух символов 0 и 1 будем обозначать B.Логические операции:
(не, отрицание), (и, конъюнкция), (или, дизъюнкция), → (следует, импликация), ≡ (эквивалентность), применяются к символам 1 (И) и 0 (Л) и результат их применения описан следующей таблицей:
A |
B |
A |
AB |
AB |
A → B |
A ≡ B |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Кванторы , с которыми вы тоже, конечно, знакомы - x (существует x ), y (для любого y )
Примеры аксиом существования множеств
Ряд аксиом Теории множеств представляет собой утверждения о существовании множеств, в том числе – образованных из других множеств.Чтобы говорить о множествах, в частности, чтобы сформулировать относящиеся к ним аксиомы, надо добавить к логическим символам символы, относящиеся к теории множеств. Как записать, что x – пустое множество, то есть множество, у которого нет элементов? Например, так:
y ( y ∊ x ) (для всякого y неверно, что y принадлежит x )
Нам понадобился символ принадлежности ∊. Внесем его в алфавит нашего языка.
Чтобы нам было о чем разговаривать, хорошо было бы быть уверенным в существовании хотя бы одного множества. Давайте начнем с пустого (Ø):
x y ( y ∊ x ) [Аксиома пустого множества.]
Мы хотим определить какие-то конкретные множества, свойства множеств и т. д. Хотим ввести для них обозначения.
Будем считать нулем пустое множество.
Как получить следующее число из числа n ? Добавим ко всем элементам n еще само n . То есть, будем считать элементами следующего за n числа все элементы из n и еще n . Все полученные элементы образуют множество N :
1 – это {0}
2 – это {0,1}= {0,{0}}
Существование таким образом построенного натурального ряда гарантируется следующей аксиомой. Для удобства понимания мы разбили ее на части и комментируем (в квадратных скобках) эти части:
s (u (u ∊ s v (v ∊ u )) [в качестве s можно взять натуральный ряд N ; в нем найдется u - ноль]
u (u ∊ s → [ для всякого u из s ]
v (v ∊ s [найдется v из s , ]
w
(w
∊
v
≡ (w
∊
u
w
=
u
)))))
[следующее за
u
] [
Аксиома бесконечности]
Однако этой аксиоме может удовлетворять не только натуральный ряд, но и другие множества
Задача . Какие, например?
Задача . Как описать в точности построенный нами натуральный ряд?
В математических построениях используются операции над множествами. Идя по уже начатому пути, мы должны добавлять аксиомы, гарантирующие существование результатов этих операций. Вот еще один пример:
usv (w (w ∊ v →w ∊ u ) ≡ v ∊ s ) [Аксиома степени]
Задача . Проверить, что последняя формула содержательно означает существование множества всех подмножеств любого заданного множества.
Конечно, нам понадобится, например и множество, являющееся пересечением двух данных, и т. д.
Выше мы начали постепенно строить множества. Ясно, как продолжить этот путь, например, построить множество целых чисел, затем - рациональных, как множество пар целых с некоторым отношением эквивалентности на нем, затем – множество действительных чисел и т. д.