Математическая логика и теория алгоритмов (290,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

УДК 519.6 Рекомендовано к изданию методическим советом ПГУТИ, протокол №45, от 10.03.2017 г. Блатов, И.А., Старожилова О.В. Б Математическая логика и теория алгоритмов: учебное пособие / И.А.Блатов, О.В.Старожилова – Самара: ПГУТИ, 2017. –214 с. Учебное пособие затрагивает такие разделы математической логики и теории алгоритмов как: алгебра высказываний, исчисление высказываний, логика предикатов, исчисление предикатов, элементы теории алгоритмов. Предназначено в качестве учебного пособия для студентов направления подготовки 09.03.02. «Информационные системы и технологии», а также для студентов и магистрантов других направлений подготовки и специалистов, желающих изучать математическую логику самостоятельно. Каждый раздел заканчивается контрольными вопросами, которые помогут проверить теоретическое освоение курса, содержит большое количество задач для самостоятельного решения и ответы для проверки. ©Блатов И.А., Старожилова О.В., 2017 2

Стр.2

Содержание Введение ........................................................................................ 7 Глава 1 Классическая логика ..................................................... 9 1.1 Логические парадоксы ...................................................... 13 1.2 Парадокс лжеца ................................................................. 13 1.3 Парадокс Платона и Сократа ........................................... 14 1.4 Парадокс Рассела ............................................................... 14 1.5 Парадокс о вычислимых функциях ................................. 14 1.6 Математическая логика на современном этапе .............. 15 Задачи для самостоятельного решения ................................. 16 Контрольные вопросы............................................................. 16 Глава 2 Логика высказываний ..................................................... 17 2.1 Алгебра высказываний ..................................................... 19 2.2 Приоритет или ранг связок ............................................... 24 2.3 Исчисление высказываний ............................................... 25 2.4 Формулы логики высказываний ...................................... 26 2.5 Законы алгебры высказываний ........................................ 29 2.6 Проблема разрешимости для логики высказываний ..... 32 Контрольные вопросы............................................................. 33 Глава 3 Формальные теории ........................................................ 35 3.1 Аксиоматический метод ................................................... 37 3.2 Теорема Гёделя о неполноте ............................................ 41 3.3 Непротиворечивость аксиоматической теории .............. 43 Контрольные вопросы............................................................. 45 Глава 4 Система аксиом исчисления высказываний ................. 47 4.1 Правила вывода ................................................................. 48 4.2 Правило подстановки(ПП) ............................................... 48 4.3 Правило заключения (ПЗ) ................................................. 50 4.4 Определение выводимой (доказуемой) формулы .......... 50 4.5 Производные правила вывода .......................................... 51 4.6 Правило сложной подстановки (СПП) ............................ 51 4.7 Правило сложного заключения ........................................ 52 4.8 Правило силлогизма .......................................................... 52 4.9 Правило контр позиции .................................................... 53 4.10 Правило снятия двойного отрицания ............................ 53 3

Стр.3

4.11 Понятие выводимости формул из совокупности формул ...................................................................................... 53 Глава 5 Понятие вывода ............................................................. 56 5.1 Свойства вывода ................................................................ 56 5.2 Правила выводимости ....................................................... 57 5.3 Основные правила выводимости ..................................... 57 5.4 Построение вывода в логике высказываний ................... 58 5.5 Доказательство некоторых законов логики .................... 59 Задачи для самостоятельного решения ................................. 62 Глава 6 Связь между АВ и ИВ ................................................... 64 6.1 Правила подстановки и замены ....................................... 65 6.2Проблемы аксиоматического исчисления высказываний ........................................................................... 66 6.3 Проблема разрешимости исчисления высказываний .... 66 6.4 Проблема полноты исчисление высказываний .............. 67 6.5 Проблема независимости аксиом исчисления высказываний ........................................................................... 67 Глава 7 Автоматическое доказательство теорем ...................... 69 7.1 Метод резолюций .............................................................. 70 7.2 Алгоритм построения вывода методом резолюций ....... 73 Глава 8 Теории первого порядка ................................................. 78 8.1 Логические операции над предикатами .......................... 81 8.2 Квантор всеобщности ....................................................... 83 8.3Квантор существования ..................................................... 83 8.4 Численные кванторы ......................................................... 85 8.5 Отрицание предложений с кванторами ........................... 85 8.6 Операции навешивания кванторов .................................. 88 8.7 Свойства кванторов ........................................................... 89 Глава 9 Понятие формулы логики предикатов .......................... 91 9.1 Равносильные формулы логики предикатов .................. 92 Законы логических операций ................................................. 94 9.2 Значение формулы логики предикатов ........................... 96 Контрольные вопросы............................................................. 96 Задачи для самостоятельного решения ................................. 97 Глава 10 Нормальные формы ЛП ............................................... 99 10.1 Алгоритм получения (приведения) ПНФ ...................... 100 Задачи для самостоятельного решения ................................. 102 4

Стр.4

10.2 Скулемовские функции................................................... 102 10.3 Общезначимость и выполнимость формул логики предикатов ................................................................................ 105 10.4 Применение языка логики предикатов для записи математических предложений ................................................ 109 10.5 Прямая, обратная и противоположная теоремы ........... 110 10.6 Необходимые и достаточные условия ........................... 111 10.7 Доказательство теорем методом от противного ........... 113 Контрольные вопросы............................................................. 113 Глава 11 Аксиомы и правила вывода исчисления предикатов 115 11.1 Дополнительные правила вывода ИП ........................... 117 11.2 Метод резолюций в ИП................................................... 120 Глава12 Неклассические логики ................................................. 122 12.1 Базовые понятия нечеткой логики ................................. 124 12.2 Основные операции с нечеткими множествами ........... 125 12.3 Понятие лингвистической переменной ......................... 128 12.4 Нечеткие отношения ....................................................... 131 12.5 Нечеткие выводы ............................................................. 131 12.6 Функции принадлежности .............................................. 133 12.7 Основные характеристики нечетких множеств ............ 134 12.8 Алгоритм формализации задачи в терминах нечеткой логики ....................................................................................... 135 12.9 Разработка нечетких правил ........................................... 135 12.10 Метод центра максимума (СоМ).................................. 136 12.11 Метод наибольшего значения (МоМ) ......................... 136 12.12 Метод центроида (СоА) ................................................ 137 Глава 13 Многозначные логики .................................................. 139 13.1 Трехзначная система Я. Лукасевича .............................. 139 13.2 Логика Гейтинга .............................................................. 145 13.3 Трехзначная система Бочвара Д.А. ................................ 146 13.4 К - значная логика Поста Е.Л. ........................................ 147 Глава 14 Общие сведения об алгоритмах .................................. 150 14.1 Основные свойства алгоритма ....................................... 150 14.2 Оценка сложности алгоритма ........................................ 151 14.3 Классификация алгоритмов по сложности ................... 153 14.4 Сложность проблем ......................................................... 154 Глава 15 Рекурсивные функции .................................................. 158 5

Стр.5

15.1 Суперпозиция частичных функций ............................... 160 15.2 Примитивная рекурсия ................................................... 160 15.3 Операция минимизации .................................................. 162 15.4 Тезис Черча ...................................................................... 164 Глава 16 Сложность алгоритмов ................................................. 166 16.1 Класс P .............................................................................. 166 16.2 Класс E.............................................................................. 167 16.3 Недетерминированные алгоритмы ................................ 168 16.4 NP-трудные и NP-полные задачи ................................... 172 16.5 Нормальные алгоритмы Маркова - ................................ 174 16.6 Алгоритм Евклида ........................................................... 177 Задачи для самостоятельного решения ................................. 180 Глава 17 Машины Тьюринга-Поста .......................................... 181 17.1 Тезис Тьюринга ............................................................... 189 17.2 Возможности машин Тьюринга ..................................... 189 17.3 Алгоритмическая машина Поста ................................... 197 Глоссарий ...................................................................................... 201 Список литературы ...................................................................... 214 6

Стр.6