Математическая логика и теория алгоритмов

Содержание книги "Математическая логика и теория алгоритмов"

Ведение
ГЛАВА 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. Общезначимость и выполнимость формул исчисления предикатов
4.4. Предваренная, скулемовская и клаузальная формы представления формул исчисления предикатов
Вопросы и упражнения для самопроверки
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. Доказательство истинности логических клауз методом резолюций
Вопросы и упражнения для самопроверки
3. ОСНОВНЫЕ ПРИНЦИПЫ ЛОГИЧЕСКОГОПРОГРАММИРОВАНИЯ
3.1. Использование формализмов логики для алгоритмических вычислений. Факты, правила, запросы
3.2. Общие правила выполнения запросов логическими программами
3.3. Методика составления логических программ
Вопросы и упражнения для самопроверки
4. СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА,ОСНОВАНННЫЕ НА ЗНАНИЯХ
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. Основные понятия
3.2. Композиция, итерация и разветвление нормальных алгоритмов. Эквивалентность тезиса Черча и принципа нормализации Маркова
Вопросы и упражнения для самопроверки
4. АНАЛИЗ СЛОЖНОСТИ АЛГОРИТМОВ
4.1. Подходы к оценке сложности алгоритмов. Асимптотика
4.2. Меры и оценки сложности
4.3. Анализ сложности генерирования перестановок
4.4. Класс задач, детерминировано решаемых с полиномиальной сложностью
4.5. NP-полные и NP-трудные задачи
4.6. Понятие алгоритмически неразрешимых проблем
4.7. Примеры алгоритмически неразрешимых проблем
Вопросы и упражнения для самопроверки
ЛИТЕРАТУРА К ГЛАВЕ III
ЗАКЛЮЧЕНИЕ