ИПОВС - 6 семестр / Пособие / G0

И.Б.Кожухов, А.В.Романов

Математическая логика

Москва

2008

Содержание

	ВВЕДЕНИЕ	2
ГЛАВА 1	ЛОГИКА ВЫСКАЗЫВАНИЙ	5
1.1	Индуктивные определения	5
1.2	Синтаксис формальных языков	6
1.3	Синтаксис ИВ. Формулы, секвенции	8
1.4	Семантика ИВ	11
1.5	Натуральная дедукция	13
1.6	Корректность и полнота исчисления НД	16
1.7	Деревья выполнимости	18
1.8	Интуиционистская логика	23
ГЛАВА 2	ТЕОРИЯ МНОЖЕСТВ	26
2.1	Мощность множества	26
2.2	Аксиома выбора, лемма Цорна, теорема Цермело	33
2.3	Кардинальные и ординальные числа	40
2.4	Аксиоматика теории множеств	46
ГЛАВА 3	ЛОГИКА ПРЕДИКАТОВ	51
3.1	Сигнатуры, термы и формулы	51
3.2	Семантика ИП. Структуры, оценки и истинность	56
3.3	Натуральная дедукция	58
3.4	Корректность и полнота натуральной дедукции	59
3.5	Аксиоматика натуральных и действительных чисел	61
3.6	Выразимость предикатов	64
3.7	Элиминация кванторов	65
3.8	Ультрапроизведение моделей. Теорема Лося	68
3.9	Теоремы Лёвенгейма – Скулема	72
3.10	Аксиоматизируемые классы моделей	75
3.11	Теоремы Гёделя о неполноте	76
ГЛАВА 4	АЛГОРИТМЫ И МАШИНЫ ТЬЮРИНГА	79
4.1	О понятии алгоритма. Тезис Чёрча	79
4.2	Машина Тьюринга	79
4.3	Рекурсивные функции	84
4.4	Вычислимые и перечислимые функции и множества	87
4.5	Алгоритмически неразрешимые задачи	91
4.6	О сложности алгоритмов	92

Введение

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

формул и т.д.

Одной из первых аксиоматических теорий была геометрия Евклида, созданная около 2 тысяч лет назад. Одна из аксиом – так называемый пятый постулат Евклида – состоит в том, что через точку вне прямой можно провести не более одной прямой, не пересекающей данную. Евклид с большой неохотой включил это утверждение в список аксиом – он считал, что его можно доказать. После Евклида многие математики пытались это сделать, но в течение долгого времени все попытки доказать пятый постулат оказывались безуспешными. Лишь в середине XIX века русский математик Н.И.Лобачевский доказал, что пятый постулат Евк-

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

вами, данное утверждение не зависит от других аксиом Евклида, и обе теории – принимающая пятый постулат и отвергающая его – являются непротиворечивыми.

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

Большим толчком, стимулирующим развитие математической логики и аксиоматических теорий, послужило обнаружение в конце XIX – начале XX века противоречий в созданной Г.Кантором “наивной” теории множеств (антиномии теории множеств). В построении аксиоматической теории множеств принимали участие ведущие математики и логики того времени – Д.Гильберт, Б.Рассел, Цорн, Цермело, Френкель, Гёдель, Бернайс. Подобно тому, как алхимики пытались создать “философский камень”, математики начала XX века хотели создать всеобъемлющую аксиоматическую теорию математики, которая сама докажет собственную непротиворечивость и полноту. Однако это оказалось невозможным ввиду теоремы Гёделя о неполноте и ряда других утверждений. Кроме того, первая половина XX века ознаменовалась созданием неклассических логик: интуиционизма Брауэра и Гейтинга, кон-

структивизма А.А.Маркова, многозначных логики т.д.

Во второй половине XX века началось активное проникновение методов математической логики в алгебру. Возникла так называемая теория моделей. Оказалось, что логика может не только исследовать методы доказательства, но и получать конкретные результаты. Локальная теорема Гёделя – Мальцева и изобретённая Лосем конструкция ультрапроизведений приняты на вооружение многими алгебраистами.

Начавшееся в 40-х годах XX века сначала медленное, а затем стремительное развитие вычислительной техники и появление быстродействующих компьютеров стимулировали развитие теории алгоритмов, теории формальных языков и создали возможность машинного доказательства теорем. Как идеализированная модель воображаемого устройства, реализующего вычислительный алгоритм, во все учебники вошла машина Тьюринга, а функций, вычислимыхна механических устройствах, – рекурсивные функции. Согласно тезису Чёрча, с которым согласны практически все математики, все функции, которые можно вычислить с помощью какого-либо алгоритмавообще, можно вычислить на машине Тьюринга.

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

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

3

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

Учебное пособие имеет четыре главы, в которых излагаются, как правило, в классическом стиле основы математической логики и теории алгоритмов. От читателя требуется знание элементарной теории множеств (операции над множествами, бинарные отношения и предикаты), алгебры высказываний (которая излагается в МИЭТе в курсе дискретной математики), а также основ общей алгебры (понятия алгебраической операции, группы, кольца, поля – курс общей алгебры МИЭТ). В учебнике есть ряд упражнений, выполнение которыхпозволитлучше овладеть изучаемым материалом.

4