Гуц А.К. Математическая логика и теория алгоритмов Изд. 4, перераб. и доп.

2023. 160 с.

Онлайн-книга

Аннотация

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

Оглавление

Часть I. Логика				9
Глава 1. Классическая логика				10
1.1. Логика высказываний				10
1.1.1. Высказывания				10
1.1.2. Классическая (материальная) импликация				12
1.1.3. Основные законы логики				14
1.1.4. Логический парадокс Рассела				14
1.1.5. Алгебра (логика) высказываний				15
1.1.6. Релейно-контактные схемы				17
1.1.7. Равносильные формулы				19
1.1.8. Алгебра Буля				20
1.1.9. Истинные и общезначимые формулы				20
1.1.10. Разрешимость логики высказываний				20
1.1.11. Логическое следствие				21
1.1.12. Силлогизмы				22
1.2. Логика предикатов				23
1.2.1. Предикаты и формулы				23
1.2.2. Интерпретации				25
1.2.3. Истинность и выполнимость формул. Модели, общезначимость, логическое следствие				26
1.2.4. Готлоб Фреге				27
1.2.5. Сколемовские функции и сколемизация формул				28
1.3. Метод резолюций				31
1.3.1. Метод резолюций в логике высказываний				31
1.3.2. Метод резолюций в логике предикатов				36
Глава 2. Формальные теории (исчисления)				39
2.1. Определение формальной теории, или исчисления				40
2.1.1. Доказательство. Непротиворечивость теории. Полнота теории				41
2.2. Исчисление высказываний				42
2.2.1. Язык и правила вывода исчисления высказываний				42
2.2.2. Пример доказательства теоремы				44
2.2.3. Полнота и непротиворечивость исчисления высказываний				45
2.3. Исчисление предикатов				46
2.3.1. Язык и правила вывода исчисления предикатов				46
2.3.2. Полнота и непротиворечивость исчисления предикатов				48
2.4. Формальная арифметика				49
2.4.1. Эгалитарные теории				49
2.4.2. Язык и правила вывода формальной арифметики				49
2.4.3. Непротиворечивость формальной арифметики. Теорема Генцена				50
2.4.4. Теорема Геделя о неполноте				50
2.4.5. Курт Гедель				52
2.5. Автоматический вывод теорем				53
2.5.1. С. Ю. Маслов				54
2.6. Логическое программирование				56
2.6.1. Логическая программа				56
2.6.2. Языки логического программирования				60
Глава 3. Неклассические логики				62
3.1. Интуиционистская логика				62
3.2. Нечеткая логика				63
3.2.1. Нечеткие подмножества				63
3.2.2. Операции над нечеткими подмножествами				64
3.2.3. Свойства множества нечетких подмножеств				65
3.2.4. Нечеткая логика высказываний				67
3.2.5. Нечеткие релейно-контактные схемы				69
3.2.6. Нечеткие числа				69
3.3. Модальные логики				71
3.3.1. Типы модальности				72
3.3.2. Модальное исчисление K				73
3.3.3. Исчисления I и Т (Фейса-фон Вригта)				73
3.3.4. Исчисления S4, S5 и исчисление Брауэра				74
3.3.5. Модальные исчисления K4 и S4				75
3.3.6. Пример означивания формул				76
3.3.7. Семантика Крипке				78
3.3.8. Сол Аарон Крипке				80
3.3.9. Другие интерпретации модальных знаков				80
3.3.10. Логика доказуемости				81
3.4. Временные логики				81
3.4.1. Временная логика Прайора				82
3.4.2. Временная логика Леммона				83
3.4.3. Временная логика фон Вригта				84
3.4.4. Георг фон Вригт				84
3.4.5. Приложение временных логик к программированию				85
3.4.6. Временная логика Пнуели				87
3.5. Алгоритмические логики				90
3.5.1. Принципы построения алгоритмической логики				92
3.5.2. Алгоритмическая логика Хоара				94
3.5.3. Чарльз Хоар				98
3.6. Паранепротиворечивые логики				99
3.6.1. Сущность паранепротиворечивых логик				100
3.6.2. Паранепротиворечивая логика LP⇒ Приста				100
3.7. Логика Васильева				102
3.7.1. Интерпретации логики Васильева				103
3.7.2. Н. А. Васильев				104
3.7.3. Трехзначная логика Лукасевича				105
3.7.4. ЭВМ «Сетунь»				106
3.8. Релевантные логики				107
3.8.1. Сущность релевантных логик				108
3.8.2. Л. Л. Максимова				111
3.8.3. Релевантная логика R				112
3.8.4. Релевантная логика RM3				113
3.8.5. И. Е. Орлов				115
3.9. Интуиционистская логика и физика				115
Часть II. Алгоритмы				119
Глава 4. Алгоритмы				120
4.1. Понятие алгоритма и вычислимой функции				120
4.2. Рекурсивные функции				122
4.2.1. Примитивно рекурсивные функции				122
4.2.2. Частично рекурсивные функции				124
4.2.3. Тезис Ч¨ерча				125
4.3. Машина Тьюринга—Поста				126
4.3.1. Вычисление функций на машине Тьюринга—Поста				128
4.3.2. Примеры вычислений				129
4.3.3. Тезис Тьюринга				131
4.3.4. Универсальная машина Тьюринга—Поста				131
4.4. Алан Тьюринг				131
4.5. Эмиль Пост				133
4.6. Нормальные алгорифмы Маркова				134
4.7. Эффективные алгоритмы				136
4.8. Алгоритмически неразрешимые проблемы				137
Глава 5. Сложность алгоритмов				138
5.1. Понятие о сложности алгоритмов				138
5.2. Классы задач P и NP				139
5.2.1. Класс задач P				139
5.2.2. Класс задач NP				140
5.2.3. Недетерминированная машина Тьюринга				140
5.3. О понятии сложности				142
5.3.1. Три типа сложности				142
5.3.2. Четыре категории чисел по Колмогорову				143
5.3.3. Тезис Колмогорова				144
5.4. А.Н.Колмогоров				145
Глава 6. Алгоритмы реальности				147
6.1. Генератор виртуальной реальности				148
6.2. Принцип Тьюринга				148
6.3. Логически возможные среды Кантгоуту				150
Литература				152

Об авторе

Гуц Александр Константинович

Доктор физико-математических наук, профессор. Заслуженный работник высшей школы РФ. Заведующий кафедрой кибернетики Омского государственного университета имени Ф. М. Достоевского, декан факультета компьютерных наук (2003–2022).

Профессор Сочинского государственного университета (г. Сочи). Области исследования: математическая теория пространства-времени, квантовая теория времени, математическое моделирование этнических, социальных и психических процессов, многовариантная и теоретическая история. Автор более 500 научных работ.