Анкудинов Г.И., Анкудинов И.Г., Петухов О.A. Математическая логика и теория алгоритмов
Подождите немного. Документ загружается.
предиката 20 предикатов 22
сложность временнáя 86
способ кодирования 86
Я
степень декартова 19
язык
схема ветвей и границ 98
над алфавитом 86
логического
Т
программирования 48
тавтология 6 NP-полный 91
"тезис Черча" 60 Prolog 48
теорема 15
теория
алгоритмов прикладная 60
полная 14
противоречивая 15
формальная 14
терм 39
трассировка 29
Ф
формула
атомарная 39
Блейка – Порецкого 10
исчисления высказываний 6
истинная при любой
интерпретации 27
исчисления предикатов 24
ложная при любой
интерпретации 27
общезначимая 27
правильно построенная 14
противоречивая 27
равносильная 9
тождественно истинная 6
функция
константы ноль 70
общерекурсивная 72
примитивно-рекурсивная 70
программная 29
словарная 63
следования 70
частично-рекурсивная 72, 75
характеристическая 82
Ц
цикл гамильтонов 99
Э
эквивалентность 5, 25
103
ОГЛАВЛЕНИЕ
Глава 1. Логика высказываний ……………………………………. 3
1.1. Логические операции над высказываниями .....………. 3
1.2. Составные высказывания ……………………………… 5
1.3. Основные тавтологии ........................…………… ……..6
1.4. Равносильные формулы .......................…………… ……9
1.5. Логическое следование ......................…………………..12
1.6. Логические функции ……………………………………13
1.7. Формальные теории и исчисление высказываний …… 14
Глава 2. Логика предикатов ……………………………………….. 17
2.1. Основные понятия теории множеств …………………..17
2.2. Определение предиката ………………………………… 19
2.3. Операции над предикатами ……………………………. 21
2.4. Логические операции квантификации ………………… 23
2.5. Исчисление предикатов ……………………………….. 24
2.6. Логика доказательства правильности алгоритмов
и программ ………………………………………………28
Глава 3. Варианты логики и логическое программирование …...37
3.1. Стандартная логика ……………………………………. 37
3.2. Клаузальная логика …………………………………….. 40
3.3. Логическое программирование ………………………..45
3.4. Prolog - язык логического программирования ………..48
3.5. Другие варианты логики ………………………………. 54
Глава 4. Элементы теории алгоритмов ………………………….. 59
4.1. Понятие алгоритма ……………………………………. 59
4.2. Машина Тьюринга ……………………………………… 61
4.3. Элементы теории рекурсивных функций ……………. 69
4.4. Эквивалентность алгоритмических систем ………….. 73
4.5. Универсальные машины Тьюринга
и алгоритмическая разрешимость …………………… 81
Глава 5. Эффективность алгоритмов ……………………………. 85
5.1. Переборные задачи и сложность вычислений ……… 85
5.2. Классы задач P и NP ………………………………….. 87
5.3. Класс NP-полных задач ……………………………….. 90
5.4. Труднорешаемые задачи ……………………………… 97
Литература …………………………………………………………. 100
Предметный указатель ……………………………………………. 101
Анкудинов Георгий Иванович
Анкудинов Иван Георгиевич
Петухов Олег Александрович
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Учебное пособие
Редактор И.Н.Кочугина
Сводный темплан 2003 г.
Лицензия ЛР №020308 от 14.02.97
Подписано в печать Формат 60 x 84 1/16
Б. кн.-журн. П.л. 5,75 Б.л. 2,875 РТП РИО СЗТУ.
Тираж 200 Заказ
Северо-Западный государственный заочный технический
университет
РИО СЗТУ, член Издательско-полиграфической ассоциации вузов
Санкт-Петербурга
191186, Санкт-Петербург, ул.Миллионная, 5
2