- •ВВЕДЕНИЕ
- •Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
- •§1. Высказывание. Логические операции
- •§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности
- •§ 3. Упрощения в записях пропозициональных форм
- •§ 4. Тавтологии (общезначимые формулы). Противоречия
- •§ 5. Равносильность пропозициональных форм
- •§ 6. Важнейшие пары равносильных пропозициональных форм
- •§ 7. Зависимости между пропозициональными связками
- •§ 8. Нормальные формы
- •§ 9. Совершенные нормальные формы
- •§ 10. Булева (переключательная) функция
- •§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
- •§ 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов
- •§ 13. Вопросы и темы для самопроверки
- •§ 14. Упражнения
- •Глава 2 ЛОГИКА ПРЕДИКАТОВ
- •§ 1. Понятие предиката
- •§ 2. Кванторы
- •§ 3. Формулы логики предикатов
- •§ 4. Интерпретация. Модель
- •§ 5. Свойства формул в данной интерпретации
- •§ 6. Логически общезначимые формулы. Выполнимые и равносильные формулы
- •§ 8. Правила перестановки кванторов
- •§ 9. Правила переименования связанных переменных
- •§ 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма
- •§ 11. Вопросы и темы для самопроверки
- •§ 12. Упражнения
- •Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
- •§ 1. Логическое следствие и проблема дедукции в логике высказываний
- •§ 2. Резольвента дизъюнктов логики высказываний
- •§ 3. Метод резолюций в логике высказываний
- •§ 4. Метод насыщения уровня
- •§ 5. Стратегия вычеркивания
- •§ 6. Лок-резолюция
- •§ 7. Метод резолюций для хорновских дизъюнктов
- •§ 8. Преобразование формул логики предикатов. Сколемовская стандартная форма
- •§ 9. Унификация
- •§ 10. Метод резолюций в логике предикатов
- •§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля.
- •§ 12. Использование метода резолюций в языке ПРОЛОГ
- •§ 13. Введение и использование правил в ПРОЛОГе
- •§ 14. Рекурсивное задание правил в ПРОЛОГе
- •§ 15. Особенности ПРОЛОГа
- •§ 16. Вопросы и темы для самопроверки
- •§ 17. Упражнения
- •Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
- •§ 1. Понятие об эффективных и полуэффективных процессах (методах)
- •§ 2. Дедуктивные теории
- •§ 3. Свойства дедуктивных теорий
- •§ 4. Пример полуформальной аксиоматической теории - геометрия
- •§ 5. Формальные аксиоматические теории
- •§ 6. Свойства выводимости
- •§ 7. Исчисление высказываний (теория L)
- •§ 8. Некоторые теоремы исчисления высказываний
- •§ 9. Эквивалентность двух определений непротиворечивости
- •§ 11. Свойства исчисления высказываний
- •§ 12. Другие аксиоматизации исчисления высказываний
- •§ 13. Теории первого порядка
- •§ 14. Формальная арифметика (теория S)
- •§ 15. Свойства теорий первого порядка
- •§ 16. Значение аксиоматического метода
- •§ 17. Теория естественного вывода
- •§ 18. Вопросы и темы для самопроверки
- •§ 19. Упражнения
- •Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
- •§ 1. Трехзначные логики
- •§ 2. Многозначные логики
- •§ 3. Понятие нечеткого множества
- •§ 4. Нечеткие высказывания и максиминные операции над ними
- •§ 5. Понятие о нечеткой лингвистической логике
- •§ 6. Модальные логики
- •§ 7. Временные (темпоральные) логики
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •Глава 6. ТЕОРИЯ АЛГОРИТМОВ
- •§1. Неформальное понятие алгоритма
- •§ 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы
- •§ 3. Нормальный алгоритм (алгоритм А. А. Маркова)
- •§ 4. Функции частично вычислимые и вычислимые по Маркову
- •§ 5. Замыкание, распространение нормального алгоритма
- •§ 6. Операции над нормальными алгоритмами
- •§ 7. Машина Тьюринга
- •§ 8. Задание машины Тьюринга
- •§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
- •§ 10. Связь между машинами Тьюринга и нормальными алгоритмами
- •§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)
- •§ 12. Проблема алгоритмической неразрешимости
- •§ 13. Примеры алгоритмически неразрешимых массовых проблем
- •§ 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
- •§ 15. Примитивно рекурсивные и общерекурсивные функции
- •§ 16. Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
- •§ 17. Ламбда-исчисление
- •§ 18. Основные результаты
- •§ 19. Вопросы и темы для самопроверки
- •§ 20. Упражнения
- •Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ
- •§ 1. Понятие о сложности
- •§ 2. Временная сложность вычислений (алгоритма)
- •§ 3. Полиномиальные алгоритмы и задачи. Класс Р
- •§ 4. NP класс
- •§ 5. NP-полные и NP-трудные задачи
- •§ 6. Класс Е
- •§ 7. Ёмкостная (ленточная) сложность алгоритма
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •ЛИТЕРАТУРА
- •ПРИЛОЖЕНИЯ
- •Варианты типового задания
- •Тесты для самоконтроля
- •Тест по логике высказываний (тест № 1)
- •Тест по логике предикатов (тест № 2)
- •Тест по логическому следствию и методу резолюций (тест № 3)
- •Тест по дедуктивным теориям (тест № 4)
- •Тест по теории алгоритмов (тест № 5)
- •Тест по неклассическим логикам и сложности вычислений (тест № 6)
- •Ответы к тестам самоконтроля
237
Никто не обнимет необъятного Козьма Прутков
Одна услада в жизни учиться! Петрарка
ЛИТЕРАТУРА
1.Акимов О. Е. Дискретная математика. Логика, группы, графы. -М.: А39 Лаборатория Базовых Знаний, 2001 –352 с.
2.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. –536 с.
3.Батыршин И. З. Основные операции нечёткой логики и их обобщения. - Казань: Отечество, 2001. –102 с.
4.Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта. Пер. с англ. -М.: Мир, 1990. –560 с.
5.Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. -М.: Наука, 1977. –368 с.
6.Гетманова А. Д. Учебник по логике. 2-ое издание. -М.: ВЛАДОС, 1995. –186 с.
7.Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. Пер. с нем. -М.: Наука, 1979. –560 с.
8.Гиндикин С. Г. Алгебра логики в задачах. М.: Наука, 1975. –288 с.
9.Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учебник для втузов. -М.: Наука.
Физматлит, 2000. -544с.
10.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Пер. с англ. -М.: Мир, 1982. –416 с.
11.Ефимов Н. В. Высшая геометрия. -М.: Физматлит, 1961. –580 с.
12.Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. Пер. с англ. -М.: Мир, 1976. –168с.
13.Ивлев Ю. В. Модальная логика. -М.: Издательство МГУ, 1991. –224с.
14.Клини С. Математическая логика. Пер. с англ. -М.: Мир, 1973. –480с.
15.Klir G. J. and Folger T. A. Fuzzy Sets, Uncertainty and Information. Prentice Hall PTR, Englewood Cliffs, New Jersey, 1988 –356 p.
16.Кофман А. Введение в теорию нечётких множеств. Пер. с франц. -М.: Радио и связь, 1982. -432с.
17.Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. -М.: Энергоатомиздат, 1988. -480с.
18.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. -М.: Наука, 1975. -240с.
19.Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер. с франц. Тейз А., Грибомон П., Луи Д. И др. -М.: Мир, 1990. -432с.
238
20.Лорьер Ж. –Л. Системы искусственного интеллекта. Пер. с франц. -
М.: Мир, 1991. –568 с.
21.Мендельсон Э. Введение в математическую логику. Пер. с англ. -М.:
Наука, 1984. –320 с.
22.Нефедов В. Н., Осипова В. А. Курс дискретной математики. -М.: Издательство МАИ, 1992. -264 с.
23.Нечеткие множества в моделях управления и искусственного интеллекта. А. Н. Аверкин, Н. З. Батыршин, А. Ф. Блишун и др. Под ред. Д. А. Поспелова. -М.: Наука, 1986. –312с.
24.Новиков П.С. Элементы математической логики. -М.: Наука, 1973. - 400с.
25.Новиков Ф. А. Дискретная математика для программистов. –СПб.:
Питер., 2001. –304 с.
26.Попадимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. -М.: Мир, 1985. –512 с.
27.Проблемы Гильберта. Сборник под общей редакцией П. С. Александрова. -М.: Наука, 1969. –240 с.
28.Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. Пер. с англ. -М.: Мир, 1980. – 478 с.
29.Самсонов Б. Б., Плохов Е. М. и Филоненков А. И. Компъютерная математика (основание информатики). -Ростов-на-Дону: «Феникс», 2002. –512с .
30.Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. Пер. с англ. -М.: Наука, 1983. -360 с.
31.Яблонский С. В. Введение в дискретную математику. -М.: Высшая школа, 2001. -384с.