Гуц А.К. Математическая логика и теория алгоритмов

Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. - Омскь, 2003. - 108 с.
Учебное пособие посвящено изложению основ математической логики и теории алгоритмов. Основу пособия составляют конспекты лекций, которые читались студентам второго курса отделения компьютерных наук Омского государственного университета в 2002 году.
Для студентов, обучающихся по специальности 075200 «Компьютерная безопасность» и по специальности 220100 - «Вычислительные машины, комплексы, системы и сети».
Оглавление
I Логика........7
1 Классическая логика.......8
1.1. Логика высказываний..................8
1.1.1. Высказывания......................................8
1.1.2. Основные законы логики..........................9
1.1.3. Логический парадокс Рассела....................10
1.1.4. Алгебра (логика) высказываний..................11
1.1.5. Релейно-контактные схемы........................12
1.1.6. Равносильные формулы..........................14
1.1.7. Алгебра Буля......................................15
1.1.8. Истинные и общезначимые формулы............15
1.1.9. Проблема разрешимости..........................15
1.1.10. Логическое следствие..............................16
1.1.11. Силлогизмы........................................17
1.2. Логика предикатов........................................17
1.2.1. Предикаты и формулы............................18
1.2.2. Интерпретации......................................19
1.2.3. Истинность и выполнимость формул. Модели, общезначимость, логическое следствие..........20
1.2.4. Готлоб Фреге........................................21
1.2.5. Сколемовские функции и сколемизация формул.....................22
1.3. Метод резолюций..........................................25
1.3.1. Метод резолюций в логике высказываний...........................25
1.3.2. Метод резолюций в логике предикатов........................29
2 Формальные теории (исчисления) 31
2.1. Определение формальной теории, или исчисления ......32
2.1.1. Доказательство. Непротиворечивость теории. Полнота теории......32
2.2. Исчисление высказываний................................33
2.2.1. Язык и правила вывода исчисления высказываний ................33
2.2.2. Пример доказательства теоремы................35
2.2.3. Полнота и непротиворечивость исчисления высказываний..........36
2.3. Исчисление предикатов....................................37
2.3.1. Язык и правила вывода исчисления предикатов 37
2.3.2. Полнота и непротиворечивость исчисления предикатов...............39
2.4. Формальная арифметика..................................39
2.4.1. Эгалитарные теории..............................39
2.4.2. Язык и правила вывода формальной арифметики ..................39
2.4.3. Непротиворечивость формальной арифметики. Теорема Генцена........40
2.4.4. Теорема Гёделя о неполноте......................41
2.4.5. Курт Гёдель........................................42
2.5. Автоматический вывод теорем ..........................43
2.5.1. С.Ю. Маслов........................................43
2.6. Логическое программирование..........................45
2.6.1. Логическая программа............................46
2.6.2. Языки логического программирования .... 49
3 Неклассические логики 50
3.1. Интуиционистская логика................................50
3.2. Нечеткая логика............................................51
3.2.1. Нечеткие подмножества..........................51
3.2.2. Операции над нечеткими подмножествами.................52
3.2.3. Свойства множества нечетких подмножеств................53
3.2.4. Нечеткая логика высказываний..................54
3.2.5. Нечеткие релейно-контактные схемы............56
3.3. Модальные логики ........................................56
3.3.1. Типы модальности................................57
3.3.2. Исчисления I и Т (Фейса-фон Вригта)..........57
3.3.3. Исчисления S4, S5 и исчисление Брауэра..................58
3.3.4. Означивание формул..............................59
3.3.5. Семантика Крипке................................60
3.3.6. Другие интерпретации модальных знаков..................62
3.4. Георг фон Вригт............................................62
3.5. Временные логики..........................................62
3.5.1. Временная логика Прайора......................63
3.5.2. Временная логика Деммона......................64
3.5.3. Временная логика фон Вригта..................64
3-5.4. Приложение временных логик к программированию ...............65
3.5.5. Временная логика Пнуели........................67
3.6. Алгоритмические логики..................................70
3.6.1. Принципы построения алгоритмической логики...............71
3.6.2. Чарльз Хоар........................................73
3.6.3. Алгоритмическая логика Хоара..................74
II Алгоритмы 77
4 Алгоритмы 78
4.1. Понятие алгоритма и вычислимой функции............78
4.2. Рекурсивные функции....................................79
4.2.1. Примитивно рекурсивные функции..............80
4.2.2. Частично рекурсивные функции................81
4.2.3. Тезис Чёрча........................................82
4.3. Машина Тьюринга-Поста..................................83
4.3.1. Вычисления функций на машине Тьюринга-Поста............84
4.3.2. Примеры вычислений..............................86
4.3.3. Тезис Тьюринга....................................87
4.3.4. Универсальная машина Тьюринга-Поста..................87
4.4. Алан Тьюринг..............................................87
4.5. Эмиль Пост ................................................89
4.6. Эффективные алгоритмы................................91
4.7. Алгоритмически неразрешимые проблемы..............91
5 Сложность алгоритмов 93
5.1. Понятие о сложности алгоритмов........................93
5.2. Классы задач Р и NP......................................94
5.2.1. Класс задач Р......................................94
5.2.2. Класс задач NP....................................95
5.2.3. Недетерминированная машина Тьюринга......................95
5.3. О понятии сложности......................................97
5.3.1. Три типа сложности..............................97
5.3.2. Четыре категории чисел по Колмогорову.....................97
5.3.3. Тезис Колмогорова................................98
5.4. А.Н. Колмогоров .............................99
6 Алгоритмы реальности 101
6.1. Генератор виртуальной реальности.....................102
6.2. Принцип Тьюринга....................102
6.3. Логически возможные среды Кантгоуту........104
Литература ....... 105