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

Стр.2

Стр.3

Стр.4

Стр.414

Стр.415

Стр.416

Стр.417

УДК 94(5) (075.8) ББК 22.12 я73 М 34 Печатается по решению редакционно-издательского совета Северо-Кавказского федерального университета Составители: канд. физ.-мат. наук, доцент А. Н. Макоха, канд. техн. наук, доцент А. В. Шапошников, канд. техн. наук, доцент В. В. Бережной М 34 Математическая логика и теория алгоритмов: учебное пособие / сост.: А.Н. Макоха, А.В. Шапошников, В.В. Бережной. – Ставрополь: Изд-во СКФУ, 2017. – 418 с. Пособие представляет курс лекций, освещающий наиболее важные разделы математической логики и теории алгоритмов; в нем рассматриваются элементы теории множеств, аксиоматическое построение исчисления высказываний, исчисления предикатов, теорий первого порядка и их приложения к некоторым системам искусственного интеллекта; излагаются основные проблемы аксиоматического метода, уточнение интуитивного понятия алгоритма на языке частично рекурсивных функций и машин Тьюринга. Изложение материала сопровождается содержательными примерами, приводятся вопросы и упражнения для самопроверки. Предназначено для студентов математических и IT-специальностей; будет полезно преподавателям, ведущим курс математической логики и теории алгоритмов. УДК 94(5) (075.8) ББК 22.12 я73 Рецензенты: канд. техн. наук, доцент Д. Н. Резеньков (СтГАУ), канд. техн. наук, доцент, доцент С. В. Аникуев (СтГАУ) © ФГАОУ ВО «Северо-Кавказский федеральный университет», 2017 2

Стр.2

ВЕДЕНИЕ Главным содержанием лекционного курса дисциплины «Математическая логика и теория алгоритмов» является формирования у студентов фундаментальных знаний в области основ построения математических теорий, а также построения и анализа алгоритмов. Основными задачами освоения дисциплины являются: - формирование научного мировоззрения, понимания широты и универсальности методов математической логики, умения применять эти методы в решении прикладных задач; - воспитание математической культуры, которая предполагает четкое осознание необходимости и важности математической подготовки для специалиста в области компьютерной безопасности; - ознакомление с основными объектами математической логики, а также их приложениями для решения различных задач, требующих применения вычислительных средств; - ознакомление с основами теории алгоритмов и их приложениями к задачам математической кибернетики; - овладение современным математическим аппаратом для дальнейшего использования при решении теоретических и прикладных задач в области защиты информации. Освоение данной дисциплины позволит будущему специалисту в области компьютерной безопасности полноценно осуществлять свою профессиональную деятельность, в частности, обладать следующими профессиональными и общекультурными компетенциями: Общекультурные компетенции (ОК) 1. Способность анализировать социально значимые явления и процессы, в том числе политического и экономического характера, мировоззренческие и философские проблемы, применять основные положения и методы гуманитарных, социальных и экономических наук при решении социальных и профессиональных задач (ОК-3). Профессиональные компетенции (ПК) 2. Способность понимать сущность и значение информации в развитии современного общества, применять достижения современных информационных технологий для поиска и обработки больших объемов информации по профилю деятельности в глобальных компьютерных системах, сетях, в библиотечных фондах и в иных источниках информации (ПК-3). 3

Стр.3

3. Способность работать с программными средствами прикладного, системного и специального назначения (ПК-8). 4. Способность разрабатывать математические модели безопасности защищаемых компьютерных систем (ПК-18). Материал предлагаемого пособия ориентирован на студентов математических и IT-специальностей. Главная цель, которую преследовали авторы при написании пособия, состоит в ознакомлении студентов с концептуальными положениями теории алгоритмов и математической логики, выросшей из формальной логики, с приложениями формальных исчислений к построению содержательных теорий первого порядка и систем искусственного интеллекта. 4

Стр.4

ОГЛАВЛЕНИЕ Ведение ….………………………………………………………………… 3 ГЛАВА I. ИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ СТРУКТУРЫ 1. ЭЛЕМЕНТАРНОЕ ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ ……….. 1.1. Теоретико-множественная символика и терминология…………. 1.2. Операции над множествами и их основные свойства…….……... 1.3. Декартово произведение множеств и отношения на множествах….. 1.4. Элементы теории отображений ………………………………….. 1.5. Отношение эквивалентности и разбиение множества на классы.. 1.6. Отношения порядка …………….………………………………… 1.7. Базовые алгебраические системы ………………………………... Вопросы и упражнения для самопроверки ………………………………. 2. АЛГЕБРА ВЫСКАЗЫВАНИЙ И ЛОГИКА ПРЕДИКАТОВ ………. 2.1. Алгебраические операции над высказываниями и их свойства .. 2.2. Формулы и функции алгебры логики. Закон двойственности …. 2.3. Совершенные дизъюнктивные и конъюнктивные нормальные формы булевых функций ……………………………………………………. 2.4. Полнота и замкнутость системы булевых функций. Представление о классах Поста ……………………………………………………………… 2.5. Логика предикатов ……………………………………………….. Вопросы и упражнения для самопроверки .……………………………… 3. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ…………………………………. 3.1. Алфавит, формулы и подформулы исчисления высказываний … 3.2. Аксиомы исчисления высказываний ……………………………. 3.3. Основные правила вывода ……………………………………….. 3.4. Определение доказуемой (выводимой) формулы ………………. 3.5. Производные правила вывода. Теорема дедукции ……………… 3.6. Связь алгебры высказываний с исчислением высказываний ….. Вопросы и упражнения для самопроверки ….…………………………… 4. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ .……………………………………. 4.1. Определение формулы исчисления предикатов ………………… 4.2. Аксиомы исчисления предикатов и основные правила вывода… 4.3. Общезначимость и выполнимость формул исчисления представления формул исчисления предикатов ……………………………. Вопросы и упражнения для самопроверки ……………………………… 414 5 7 15 20 25 27 32 36 43 50 50 55 61 65 69 76 87 88 89 90 92 94 100 109 113 113 116 предикатов ……………………………………………………………………. 4.4. Предваренная, скулемовская и клаузальная формы 119 121 126

Стр.414

5. ОСНОВНЫЕ ПОНЯТИЯ АКСИОМАТИЧЕСКИХ ТЕОРИЙ ПЕРВОГО ПОРЯДКА ……………………………………………………….. 5.1. Формальные аксиоматические теории ………………………….. 5.2. Логические и специальные аксиомы ……………………………. 5.3. Правила вывода и понятие доказательства в теории первого порядка ……………………………………………………………………….. 5.4. Понятия интерпретации и модели теории. Изоморфизм интерпретаций ……………………………………………………………….. 5.5. Примеры аксиоматических теорий первого порядка со специальными аксиомами …………………………………………………… Вопросы и упражнения для самопроверки .……………………………… 6. ПРОБЛЕМЫ АКСИОМАТИЧЕСКОГО ПОСТРОЕНИЯ ТЕОРИЙ ПЕРВОГО ПОРЯДКА ……………………………………………………….. 6.1. Проблема непротиворечивости ….………………………………. 6.2. Проблема независимости системы аксиом ……………………… 6.3. Формализуемость и разрешимость теории ……………………… 6.4. Категоричность теории …………………………………………... 6.5. Проблема полноты теории ……………………………………….. ЛИТЕРАТУРА К ГЛАВЕ I ……………………………………………….. ГЛАВА II. НЕТРАДИЦИОННЫЕ ЛОГИКИ 1. ОСНОВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ В ОБЛАСТИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА …………………………………….. 1.1 Естественный и искусственный интеллект …………………………. 1.2. Некоторые философские аспекты проблем искусственного интеллекта ……………………………………………………………………. 1.3. Примеры систем искусственного интеллекта ………………………. Вопросы и упражнения для самопроверки ………………………………. 2. ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ АВТОМАТИЗАЦИИ ДОКАЗАТЕЛЬСТВ………………………………….. 2.1. Постановка задачи автоматического доказательства теорем….. 2.2. Унификация……………………………………………………….. 2.3. Метод резолюций…………………………………………………. 2.4. Алгоритм поиска опровержения методом резолюций…………. 2.5. Доказательство истинности логических клауз методом резолюций……………………………………………………………… Вопросы и упражнения для самопроверки ………………………………. 415 178 179 183 191 203 206 213 164 164 167 169 156 156 157 158 159 159 162 129 131 133 134 137 140 150

Стр.415

3. ОСНОВНЫЕ ПРИНЦИПЫ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ ………………………………………………… 3.1. Использование формализмов логики для алгоритмических вычислений. Факты, правила, запросы……………………………………… 3.2. Общие правила выполнения запросов логическими программами …………………………………………………………………. 3.3. Методика составления логических программ…………………. Вопросы и упражнения для самопроверки ………………………………. 4. СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА, 218 220 223 226 240 ОСНОВАНННЫЕ НА ЗНАНИЯХ ………………………………………….. 4.1. Представление и использование нечетких знаний ……………… 4.2. Нечеткая, вероятностная и монотонная логики…………………. 4.3. Нечеткие множества и нечеткие выводы………………………... 4.4. Многозначная логика…………………………………………….. 4.5. Модальные логики………………………………………………... 4.6. Продукционные системы………………………………………… 4.7. О механизмах вывода в экспертных системах ………………….. Вопросы и упражнения для самопроверки ………………………………. ЛИТЕРАТУРА К ГЛАВЕ II ………………………………………………. ГЛАВА III. ТЕОРИЯ АЛГОРИТМОВ 1. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА НА ОСНОВЕ ЧАСТИЧНО РЕКУРСИВНЫХ ФУНКЦИЙ ………………………………………………. 1.1. Интуитивное понятие алгоритма. Общие свойства алгоритмов ... 1.2. Эффективно вычислимые и примитивно рекурсивные функции. 1.3. Оператор минимизации и частично рекурсивные функции. Тезис Черча …………………………………………………………………... Вопросы и упражнения для самопроверки ………………………………. 2. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА НА ОСНОВЕ МАШИН ТЬЮРИНГА…………………………………………………………………. 2.1.Модель одноленточной машины Тьюринга ….…………………. 2.2.Композиция, итерация и разветвление машин Тьюринга ….…… 2.3.Методологическое значение моделей машин Тьюринга ……..… Вопросы и упражнения для самопроверки ………………………………. 3. НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА…………...……………... 3.1. Основные понятия…………….…….…………………………….. 416 325 326 333 337 339 354 355 298 299 304 311 319 244 245 248 250 253 258 273 289 293 296

Стр.416

3.2. Композиция, итерация и разветвление нормальных алгоритмов. Эквивалентность тезиса Черча и принципа нормализации Маркова……… Вопросы и упражнения для самопроверки ………………………………. 4. АНАЛИЗ СЛОЖНОСТИ АЛГОРИТМОВ …………...………………. 4.1. Подходы к оценке сложности алгоритмов. Асимптотика ............ 4.2. Меры и оценки сложности ………………………………………. 4.3. Анализ сложности генерирования перестановок …….…………. 4.4. Класс задач, детерминировано решаемых с полиномиальной Сложностью …..……………………………………………………………... 4.5. NP-полные и NP-трудные задачи ………………………………... 4.6. Понятие алгоритмически неразрешимых проблем ……………... 4.7. Примеры алгоритмически неразрешимых проблем ……………. 358 365 368 368 377 381 Вопросы и упражнения для самопроверки ………………….…………… ЛИТЕРАТУРА К ГЛАВЕ III ……..……………………………………….. ЗАКЛЮЧЕНИЕ ……..……….……………….…………………………… 385 395 398 401 406 411 412 417

Стр.417