Конспект лекций по учебной дисциплине «Математическая логика и теория алгоритмов» (190,00 руб.)

Стр.3

Стр.4

Стр.5

Стр.6

Стр.7

УДК 519.2 Блатов И.А., Старожилова О.В. Математическая логика и теория алгоритмов. Конспект лекций.- Самара: ГОУВПО ПГУТИ, 2011-216с. Конспект лекций затрагивает такие разделы математической логике и теории автоматов как: алгебра высказываний, исчисление высказываний, логика предикатов, исчисление предикатов, элементы теории алгоритмов. Для студентов и аспирантов университетов и вузов, а также для специалистов, желающих изучать математическую логику самостоятельно. Каждая лекция заканчивается контрольными вопросами, которые помогут проверить теоретическое освоение курса, содержит большое количество задач для самостоятельного решения и ответы для проверки. Рецензент: Асташкин С.В. – д.ф.м.н., проф., зав.кафедрой Самарского государственного университета Государственное образовательное учреждение высшего профессионального образования Поволжский государственный университет телекоммуникаций и информатики ©Блатов И.А., Старожилова О.В., 2011 3

Стр.3

Содержание Введение .................................................................. 8 Лекция 1 ................................................................. 10 Классическая логика .......................................... 10 Логические парадоксы ....................................... 13 Парадокс лжеца .................................................. 13 Парадокс Платона и Сократа ............................ 13 Парадокс Рассела................................................ 13 Парадокс о вычислимых функциях .................. 14 Математическая логика на современном этапе Задачи для самостоятельного решения ............ 15 Контрольные вопросы ....................................... 15 Лекция 2 .................................................................. 16 Логика высказываний ............................................ 16 Алгебра высказываний ...................................... 17 Исчисление высказываний ................................ 22 Формулы логики высказываний ....................... 23 Законы алгебры высказываний ......................... 25 Проблема разрешимости для логики высказываний 27 Контрольные вопросы ....................................... 28 Лекция 3 .................................................................. 29 Формальные теории ............................................... 29 Аксиоматический метод .................................... 30 Теорема Гѐделя о неполноте ............................. 33 Непротиворечивость аксиоматической теории Контрольные вопросы ....................................... 36 14 35 Лекция 4 .................................................................. 37 Система аксиом исчисления высказываний ........ 37 Правила вывода .................................................. 38 Правило подстановки(ПП) ................................ 38 Правило заключения (ПЗ) ................................. 39 Определение выводимой (доказуемой) формулы 39 Производные правила вывода ........................... 39 Правило сложной подстановки (СПП) ............ 40 Правило сложного заключения ........................ 40 Правило силлогизма........................................... 40 Правило контр позиции ..................................... 41 Правило снятия двойного отрицания ............... 41 Понятие выводимости формул из совокупности формул 41 Лекция 5 .................................................................. 43 Понятие вывода ...................................................... 43 Свойства вывода ................................................. 43 Правила выводимости ....................................... 43 4

Стр.4

Основные правила выводимости ...................... 43 Построение вывода в логике высказываний ... 45 Доказательство некоторых законов логики..... 45 Задачи для самостоятельного решения ............ 47 Лекция 6 .................................................................. 49 Связь между алгеброй высказываний .................. 49 и исчислением высказываний ............................... 49 Правила подстановки и замены ........................ 50 Проблемы аксиоматического исчисления высказываний 50 Проблема разрешимости исчисления высказываний 50 Проблема полноты исчисление высказываний 51 Проблема независимости аксиом исчисления высказываний 51 Лекция 7 .................................................................. 52 Автоматическое доказательство теорем .............. 52 Метод резолюций ............................................... 52 Алгоритм построения вывода методом резолюций 55 Лекция 8 .................................................................. 59 Теории первого порядка .................................... 59 Логика предикатов ................................................. 59 Логические операции над предикатами ........... 61 Квантор всеобщности ........................................ 62 Квантор существования ..................................... 63 Численные кванторы .......................................... 63 Отрицание предложений с кванторами ........... 64 Операции навешивания кванторов ................... 66 Свойства кванторов............................................ 66 Лекция 9 .................................................................. 68 Понятие формулы логики предикатов ............. 68 Равносильные формулы логики предикатов ... 69 Законы логических операций ............................ 70 Значение формулы логики предикатов ............ 71 Контрольные вопросы ....................................... 72 Задачи для самостоятельного решения ............ 72 Лекция 10 ................................................................ 74 Нормальные формы формул логики предикатов 74 Алгоритм получения (приведения) ПНФ ........ 74 Задачи для самостоятельного решения ............ 76 Скулемовские функции ..................................... 76 Общезначимость и выполнимость формул логики предикатов 79 Применение языка логики предикатов для записи математических предложений ....................................................... 82 Прямая, обратная и противоположная теоремы Необходимые и достаточные условия ............. 83 82 5

Стр.5

Доказательство теорем методом от противного Контрольные вопросы ....................................... 84 84 Лекция 11 ................................................................ 85 Аксиомы и правила вывода исчисления предикатов 85 Дополнительные правила вывода для исчисления предикатов 87 Метод резолюций в ИП ..................................... 88 Лекция 12 ................................................................ 90 Неклассические логики ......................................... 90 Базовые понятия нечеткой логики ................... 92 Основные операции с нечеткими множествами Понятие лингвистической переменной ........... 94 Нечеткие отношения .......................................... 96 Нечеткие выводы ................................................ 97 Функции принадлежности ................................ 98 Основные характеристики нечетких множеств 92 98 Алгоритм формализации задачи в терминах нечеткой логики 99 Разработка нечетких правил ............................. 99 Метод центра максимума (СоМ) ...................... 100 Метод наибольшего значения (МоМ) .............. 100 Метод центроида (СоА) ..................................... 100 Описание системы .............................................. 101 Лекция 13 ................................................................ 102 Многозначные логики ............................................ 102 Трехзначная система Я. Лукасевича ................ 102 Логика Гейтинга ................................................. 107 Трехзначная система Бочвара Д.А. .................. 107 К - значная логика Поста Е.Л. ........................... 108 Лекция 14 ................................................................ 111 Общие сведения об алгоритмах ............................ 111 Основные свойства алгоритма .......................... 111 Оценка сложности алгоритма ........................... 112 Классификация алгоритмов по сложности ...... 113 Сложность проблем ........................................... 114 Задача комивояжера ........................................... 114 Проблема тройного брака .................................. 114 Тройная выполнимость ...................................... 114 Лекция 15 ................................................................ 117 Рекурсивные функции ....................................... 117 Суперпозиция частичных функций .................. 118 Примитивная рекурсия ...................................... 119 Операция минимизации ..................................... 120 Тезис Черча ......................................................... 122 Лекция 16 ................................................................ 123 6

Стр.6

Сложность алгоритмов ...................................... 123 Класс P ................................................................. 123 Класс E ................................................................ 124 Недетерминированные алгоритмы ................... 125 NP-трудные и NP-полные задачи ..................... 127 Лекция 17 ................................................................ 129 Нормальные алгоритмы Маркова ......................... 129 Алгоритм Евклида .............................................. 131 Задачи для самостоятельного решения ............ 133 Лекция 18 ................................................................ 134 Машины Тьюринга-Поста ................................. 134 Тезис Тьюринга .................................................. 139 Возможности машин Тьюринга ........................ 140 Алгоритмическая машина Поста ...................... 146 Глоссарий ................................................................ 149 К лекции 1 ............................................................... 149 К лекции 2 ............................................................... 149 К лекции 3 ............................................................... 151 К лекции 4 ............................................................... 151 К лекции 5 ............................................................... 153 К лекции 6 ............................................................... 154 К лекции 7 ............................................................... 154 К лекции 8 ........................................................... 155 К лекции 9 ........................................................... 156 К лекции 10 ......................................................... 157 К лекции 11 ......................................................... 157 К лекции 12 ......................................................... 158 К лекции 13 ......................................................... 158 К лекции 14 ......................................................... 158 К лекции 15 ......................................................... 158 К лекции 16 ......................................................... 159 Список литературы ................................................ 160 7

Стр.7