- •Введение
- •Занятие 1. Основные понятия математической логики. Исчисление высказываний
- •1.1. Введение
- •1.2. Исчисление высказываний
- •1.2.1. Основные логические функции исчисления высказываний
- •1.2.2. Дизъюнктивно-нормальная и конъюнктивно- нормальная формы
- •Контрольные вопросы и упражнения
- •Занятие 2. Перевод высказываний естественного языка на язык исчисления высказываний
- •Контрольные вопросы и упражнения
- •Занятие 3. Логический вывод в исчислении высказываний
- •3.1. Силлогизмы
- •3.2. Метод прямого преобразования
- •3.3. Метод семантических таблиц
- •3.4. Метод резолюций
- •Метод насыщения уровня
- •3.4.2. Стратегия вычеркивания
- •Контрольные вопросы и упражнения
- •Занятие 4. Исчисление предикатов
- •4.1. Основные понятия
- •4.2. Кванторные операции
- •4.3. Равносильности логики предикатов
- •4.4. Предваренная, сколемовская нормальная и сколемовская стандартная формы
- •Контрольные вопросы и упражнения
- •Занятие 5. Перевод высказываний естественного языка на язык логики предикатов
- •Контрольные вопросы и упражнения
- •Занятие 6. Логическое следствие в исчислении предикатов
- •6.1. Метод семантических таблиц
- •6.2. Процедура вывода Эрбрана
- •6.3. Принцип резолюции
- •6.3.1. Алгоритм унификации
- •6.3.2. Метод резолюций в исчислении предикатов
- •Контрольные вопросы и упражнения
- •Занятие 7. Теория алгоритмов
- •7.1. Вычислимые функции, частично-рекурсивные и общерекурсивные функции. Тезис Черча
- •7.2. Машинная математика. Машина Тьюринга.
- •7.3. Тезис Тьюринга (основная гипотеза теории алгоритмов)
- •7.4. Нормальные алгоритмы Маркова
- •Занятие 8. Обзор неклассических логик
- •8.1. Нечеткая логика
- •8.2. Модальные логики
- •8.3. Временные (темпоральные) логики
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
Заключение
Завершая изложение основ математической логики и теории алгоритмов, следует отметить, что возросший в последнее десятилетие интерес к логическому программированию и его практическому применению для автоматического доказательства теорем требует более глубокого изучения соответствующих глав курса математической логики. Поэтому данное издание, в котором вопросы автоматического доказательства теорем рассмотрены не только теоретически, но и практически, должно оказать существенную помощь студентам в освоении этих вопросов.
Несмотря на то, что в пособии не нашли достаточного полного изложения вопросы, касающиеся неклассических логик, тем не менее успешное освоение основ математической логики и теории алгоритмов должно создать необходимую базу для самостоятельного изучения новых тем и заложить основу для серьезной профессиональной деятельности в этих областях.
158
Библиографический список
1. Клини С. Математическая логика/ С. Клини.- М.: Мир, 1973. – 241 с.
2. Марков А.А. Элементы математической логики/ А.А.Марков. – М.:Изд. Моск. универс.,1984. – 80 с.
3. Столл Р. Множества, логика, аксиоматические теории/ Р. Столл. – М.: Просвещение, 1968. – 134 с.
4. Черч А. Введение в математическую логику/ А. Черч. – М.: ИЛ, 1960. - 243 с.
5. Чень Ч. Математическая логика и автоматическое доказательство теорем/ Ч. Чень, Р. Ли. – М.: Наука, 1983 – 179 с.
6. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций/ Н. Катленд. – М.: Мир, 1983. – 255 с.
7. Метакидес Г. Принципы логики и логического программирования/ Г. Метакидес, А. Нероуд. – М.: Факториал, 1998. – 288 с.
8. Лихтарников Л.М. Математическая логика и теория алгоритмов/ Л.М. Лихтарников, Т.Г. Сукачева - М.: Факториал, 2000. - 420 с.
9. Игошин В.И. Математическая логика и теория алгоритмов/ В.И. Игошин. – М.: Академия, 2008. – 449 с.
10. Игошин В.И. Задачи и упражнения по математической логике/ В.И. Игошин. – М.: Академия, 2007. – 305 с.
11. Достоверный и правдоподобный вывод в интеллектуальных системах/ В.Н. Вагин, Е.Ю. Головина, А.А. Загорянская, М.В. Попова. – М.: Факториал, 2007. – 200 с.
159
12. Галиев Ш.И. Математическая логика и теория алгоритмов/ Ш.И. Галиев. – Казань: Изд-во КГТУ, 2002. – 270 с.
13. Фрейденталь Х. Язык логики/ Х.Фрейденталь. – М.:Наука, 1969. – 136 с.
14. Мадер В.В. Школьнику об алгебре логики/ В.В. Мадер. – М.: Просвещение, 1993. – 240 с.
160
Оглавление
Введение………………………………………………….............3
Занятие 1.Основные понятия математической
логики. Исчисление высказываний…………………………….4
1.1. Введение……………………………………………….4
1.2. Исчисление высказываний…………………………...6
1.2.1. Основные логические функции исчисления
высказываний……………………………………………………9
1.2.2. Дизъюнктивно-нормальная и
конъюнктивно-нормальная формы……………………………12
Контрольные вопросы и упражнения ………………………...14
Занятие 2. Перевод высказываний естественного
языка на язык исчисления высказываний……………………18
Контрольные вопросы и упражнения…………………………21
Занятие 3. Логический вывод в исчислении высказываний…30
3.1. Силлогизмы…………………………………………..30
3.2. Метод прямого преобразования…………………….33
3.3. Метод семантических таблиц……………………….35
3.4. Метод резолюций……………………………………42
3.4.1. Метод насыщения уровня…………………………45
3.4.2. Стратегия вычеркивания…………………………..47
3.4.3. Лок-резолюция……………………………………..49
Контрольные вопросы и упражнения ………………………...51
Занятие 4. Исчисление предикатов……………………………61
4.1. Основные понятия…………………………………...61
4.2. Кванторные операции……………………………….64
4.3. Равносильности логики предикатов………………..69
161
4.4. Предваренная, сколемовская нормальная
и сколемовская стандартная формы…………………………...70
Контрольные вопросы и упражнения…………………………78
Занятие 5. Перевод высказываний естественного
языка на язык исчисления предикатов………………………..84
Контрольные вопросы и упражнения…………………….…...92
Занятие 6. Логическое следствие в исчислении
предикатов………………………………………………………97
6.1. Метод семантических таблиц……………………….99
6.2. Процедура вывода Эрбрана……………………….102
6.3. Принцип резолюции………………………………..108
6.3.1. Алгоритм унификации…………………………...108
6.3.2. Метод резолюций в исчислении предикатов…...116
Контрольные вопросы и упражнения………………………..121
Занятие 7. Теория алгоритмов………………………………..127
7.1. Вычислимые функции, частично-рекурсивные
и общерекурсивные функции. Тезис Черча…………………128
7.2. Машинная математика. Машина Тьюринга……....134
7.3. Тезис Тьюринга (основная гипотеза
теории алгоритмов)…………………………………………..139
7.4. Нормальные алгоритмы Маркова…………………140
Контрольные вопросы и упражнения……………………….146
Занятие 8. Обзор неклассических логик…………………….154
8.1. Нечеткая логика……………………………………154
8.2. Модальные логики………………………………...155
8.3. Временные (темпоральные) логики……………...156
Заключение…………………………………………………...158
Библиографический список…………………………………159
162
Учебное пособие
Холопкина Людмила Владимировна
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ: ПРАКТИКУМ
В авторской редакции
Компьютерный набор Л.В. Холопкиной
Подписано в печать 21.11.2008
Уч.-изд. л.8,2.
ГОУВПО «Воронежский государственный технический университет»