Конспект лекций затрагивает такие разделы математической логике и теории автоматов как: алгебра высказываний, исчисление высказываний, логика предикатов, исчисление предикатов, элементы теории алгоритмов. <...> 39 Определение выводимой (доказуемой) формулы 39 Производные правила вывода . <...> 85 Аксиомы и правила вывода исчисления предикатов 85 Дополнительные правила вывода для исчисления предикатов 87 Метод резолюций в ИП . <...> Порецкий Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. <...> Первый в России курс по алгебре логики был прочитан Б. <...> Одной из основных причин развития математической логики является широкое распространение аксиоматического метода в построении различных математических теорий. <...> Выбирая по-разному системы аксиом и правила вывода одних формул из других, получают различные синтаксические логические теории. <...> Определение Вычислимые функции - Парадокс о вычислимых функциях множество функций видаf :N N , которые могут быть реализованы на исполнителе машин Тьюринга. <...> Областями использования логики в настоящее время являются: - проектирование цифровых схем; - исследование семантики языков программирования; - спецификация, верификация и синтез программ; - спецификация и верификация параллельных процессов; - создание логических языков программирования; - системы искусственного интеллекта Определение Математическая логика - это современная форма логики, которая полностью опирается на формальные математические методы. <...> Разновидности силлогизмов и модусов: отличие и сходство 15 Лекция 2 Логика высказываний Логика высказываний является простейшей логикой, максимально близкой к человеческой логике неформальных рассуждений и известна ещѐ со времѐн античности. <...> Логика высказываний (или пропозициональная логика, propositional logic or calculus) — это формальная теория, основным объектом которой служит понятие логического высказывания <...>
Математическая_логика_и_теории_алгоритмов_Конспект_лекций.pdf
УДК 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