- •1. Исчисление высказываний
- •1.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2. Метод резолюций в исчислении высказываний
- •1.3. Метод резолюций для хорновских дизъюнктов
- •Задачи и упражнения
- •2. Логика и исчисление предикатов
- •2.1. Логика предикатов
- •2.2. Алгебра предикатов
- •2.2.1. Логические операции
- •2.2.2. Правила записи сложных формул
- •2.2.3. Законы алгебры предикатов
- •2.2.4. Предваренная нормальная форма
- •2.2.4.1. Алгоритм приведения формулы к виду пнф
- •2.2.5. Сколемовская стандартная форма
- •2.2.5.1. Алгоритм Сколема
- •2.3. Исчисление предикатов
- •2.3.1. Интерпретация формул
- •2.3.2. Правила вывода
- •2.3.3. Метод дедуктивного вывода
- •2.3.4. Метод резолюций в исчислении предикатов
- •2.4. Проблемы в исчислении предикатов
- •2.5. Логическое программирование
- •Задачи и упражнения
- •3. Элементы теории алгоритмов
- •3.1. Рекурсивные функции
- •3.1.1. Базовые функции
- •3.1.2. Элементарные операции
- •3.2. Машина Тьюринга
- •3.2.1. Описание машины Тьюринга
- •3.2.2. Примеры машин Тьюринга
- •3.2.3. Условные обозначения и схемные соединения машин Тьюринга
- •3.2.4. Рекурсивные функции и вычисления на машинах Тьюринга
- •3.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
Библиографический список
Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992. 262 с.
Яблонский С.В. Введение в дисретную математику. М.: Наука, 1979. 272 с.
Новиков П.С. Элементы математической логики. М.: Наука, 1973. 400 с.
Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2001. 304 с.
Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов: Учебник. - М.: ИНФРА-М, 2004. – 224 с.
Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982. 432 с.
Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983.
Карпов Ю.Г. Теория автоматов. – СПб.:Питер, 2002.
Моненков А.В. нечеткое моделирование в MATLAB и furry TECH. – СПб.: БХВ-Петербург, 2003.
Оглавление
ВВЕДЕНИЕ |
3 |
|||||||
1. |
ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ |
5 |
||||||
|
1.1. |
Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний |
13 |
|||||
|
1.2. |
Метод резолюций в исчислении высказываний |
16 |
|||||
|
1.3. |
Метод резолюций для хорновских дизъюнктов |
21 |
|||||
|
Задачи и упражнения |
|
22 |
|||||
2. |
ЛОГИКА И ИСЧИСЛЕНИЕ ПРЕДИКАТОВ |
24 |
||||||
|
2.1. |
Логика предикатов |
24 |
|||||
|
2.2. |
Алгебра предикатов |
31 |
|||||
|
|
2.2.1. |
Логические операции |
33 |
||||
|
|
2.2.2. |
Правила записи сложных формул |
|
36 |
|||
|
|
2.2.3. |
Законы алгебры предикатов |
|
39 |
|||
|
|
2.2.4. |
Предваренная нормальная форма |
42 |
||||
|
|
|
2.2.4.1. |
Алгоритм приведения формулы к виду ПНФ |
43 |
|||
|
|
2.2.5. |
Сколемовская стандартная форма |
45 |
||||
|
|
|
2.2.5.1. |
Алгоритм Сколема |
46 |
|||
|
2.3. |
Исчисление предикатов |
47 |
|||||
|
|
2.3.1. |
Интерпретация формул |
48 |
||||
|
|
2.3.2. |
Правила вывода |
49 |
||||
|
|
2.3.3. |
Метод дедуктивного вывода |
52 |
||||
|
|
2.3.4. |
Метод резолюций в исчислении предикатов |
54 |
||||
|
2.4. |
Проблемы в исчислении предикатов |
60 |
|||||
|
2.5. |
Логическое программирование |
61 |
|||||
|
Задачи и упражнения |
64 |
||||||
3. |
ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ |
68 |
||||||
|
3.1. |
Рекурсивные фкункции |
70 |
|||||
|
|
3.1.1. |
Базовые функции |
71 |
||||
|
|
3.1.2. |
Элементарные операции |
72 |
||||
|
3.2. |
Машина Тьюринга |
79 |
|||||
|
|
3.2.1. |
Описание машины Тьюринга |
81 |
||||
|
|
3.2.2. |
Примеры Машин Тьюринга |
85 |
||||
|
|
3.2.3. |
Условные обозначения и схемные соединения машины Тьюринга |
88 |
||||
|
|
3.2.4. |
Рекурсивные функции и вычисления на машинах Тьюринга |
89 |
||||
|
3.3. |
Конечные автоматы |
94 |
|||||
|
|
Задачи и упражнения |
99 |
|||||
4. |
НЕКЛАССИЧЕСКИЕ ЛОГИКИ |
100 |
||||||
|
4.1. |
Пропозициональные логики |
100 |
|||||
|
4.2. |
Алгоритмические логики |
114 |
|||||
|
|
Задачи и упражнения |
120 |
|||||
ЗАКЛЮЧЕНИЕ |
121 |
|||||||
БИБЛИОГРАФИЧЕСКИЙ СПИСОК |
123 |
Учебное издание
Федорков Евгений Дмитриевич
Собенина Ольга Валерьевна
Свиридова Нина Николаевна
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Компьютерный набор О.В. Собениной
Подписано к изданию 26.12.05. Уч.-изд. л.7,5.
Воронежский государственный технический университет