Задачи и упражнения
1. Доказать, что
а) все выводимые в ИИВ формулы выводимы в ИВ;
б) формулы (
)
и
не выводимы в ИИВ;
в) если в ИИВ
доказуемо Г,
,
то в ИИВ доказуемо
2. Показать, что
система функций, состоящая из функций
и всех функций
является полной в k-значной логике.
Заключение
Представленное учебное пособие не претендует на полноту рассмотрения всех направлений развивающейся в настоящее время математической логики и теории алгоритмов. Автор лишь хотел ознакомить читателя в рамках выделенного на изучение курса времени, с основными понятиями и подходами дисциплины. Предложенный материал может служить фундаментом для дальнейшего изучения как теоретических и прикладных ворпосов математической логики и теории алгоритмов в целом, так и отдельных ее направлений при изучении специальных дисциплин.
Библиографический список
Нефедов В.Н. Курс дискретной математики / В.Н. Нефедов, В.А. Осипова М.: Изд-во МАИ, 1992. 262 с.
Яблонский С.В. Введение в дисретную математику / С.В. Яблонский. М.: Наука, 1979. 272 с.
Новиков П.С. Элементы математической логики / П.С. Новиков. М.: Наука, 1973. 400 с.
Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. СПб: Питер, 2001. 304 с.
Судоплатов С.В. Математическая логика и теория алгоритмов: учебник / С.В. Судоплатов, Е.В. Овчинникова. М.: ИНФРА-М, 2004. – 224 с.
Кофман А. Введение в теорию нечетких множеств / А. Кофман. М.: Радио и связь, 1982. 432 с.
Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем / Ч. Чень, Р. Ли. – М.: Наука, 1983.
Карпов Ю.Г. Теория автоматов / Ю.Г. Карпов. – СПб.:Питер, 2002.
Моненков А.В. Нечеткое моделирование в MATLAB и furry TECH / А.В. Моненков. – СПб.: БХВ-Петербург, 2003.
Оглавление
ВВЕДЕНИЕ |
3 |
|||||||||
1. |
ЛОГИКА ВЫСКАЗЫВАНИЙ |
5 |
||||||||
|
1.1. |
Алгебра высказываний |
6 |
|||||||
|
|
1.1.1. |
Операции над высказываниями Правила записи сложных формул Таблицы истинности Равносильность формул |
6 |
||||||
|
|
1.1.2. |
10 |
|||||||
|
|
1.1.3. |
12 |
|||||||
|
|
1.1.4. |
15 |
|||||||
|
|
1.1.5. |
Дизъюнктивные и конъюнктивные нормальные формы |
22 |
||||||
|
|
1.1.6. |
Логическое следствие |
26 |
||||||
|
1.2. |
Исчисление высказываний |
29 |
|||||||
|
|
1.2.1. |
Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний |
38 |
||||||
|
|
1.2.2. |
Метод резолюций в исчислении высказываний |
41 |
||||||
|
|
1.2.3. |
Метод резолюций для хорновских дизъюнктов |
46 |
||||||
|
|
Задачи и упражнения |
|
47 |
||||||
2. |
ЛОГИКА И ИСЧИСЛЕНИЕ ПРЕДИКАТОВ |
49 |
||||||||
|
2.1. |
Логика предикатов |
49 |
|||||||
|
2.2. |
Алгебра предикатов |
56 |
|||||||
|
|
2.2.1. |
Логические операции |
58 |
||||||
|
|
2.2.2. |
Правила записи сложных формул |
|
61 |
|||||
|
|
2.2.3. |
Законы алгебры предикатов |
|
64 |
|||||
|
|
2.2.4. |
Предваренная нормальная форма |
67 |
||||||
|
|
|
2.2.4.1. |
Алгоритм приведения формулы к виду ПНФ |
68 |
|||||
|
|
2.2.5. |
Сколемовская стандартная форма |
70 |
||||||
|
|
|
2.2.5.1. |
Алгоритм Сколема |
71 |
|||||
|
2.3. |
Исчисление предикатов |
72 |
|||||||
|
|
2.3.1. |
Интерпретация формул |
73 |
||||||
|
|
2.3.2. |
Правила вывода |
74 |
||||||
|
|
2.3.3. |
Метод дедуктивного вывода |
77 |
||||||
|
|
2.3.4. |
Метод резолюций в исчислении предикатов |
79 |
||||||
|
2.4. |
Проблемы в исчислении предикатов |
85 |
|||||||
|
2.5. |
Логическое программирование |
86 |
|||||||
|
|
Задачи и упражнения |
89 |
|||||||
3. |
ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ |
93 |
||||||||
|
3.1. |
Рекурсивные функции |
96 |
|||||||
|
|
3.1.1. |
Базовые функции |
97 |
||||||
|
|
3.1.2. |
Элементарные операции |
98 |
||||||
|
3.2. |
Машина Тьюринга |
109 |
|||||||
|
|
3.2.1. |
Описание машины Тьюринга |
112 |
||||||
|
|
3.2.2. |
Примеры машин Тьюринга |
115 |
||||||
|
3.3. |
Конечные автоматы |
119 |
|||||||
|
|
Задачи и упражнения |
124 |
|||||||
4. |
НЕКЛАССИЧЕСКИЕ ЛОГИКИ |
125 |
||||||||
|
4.1. |
Пропозиционные логики |
125 |
|||||||
|
4.2. |
Алгоритмические логики |
139 |
|||||||
|
|
Задачи и упражнения |
145 |
|||||||
ЗАКЛЮЧЕНИЕ |
146 |
|||||||||
БИБЛИОГРАФИЧЕСКИЙ СПИСОК |
146 |
|||||||||
Учебное издание
Собенина Ольга Валерьевна
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Компьютерный набор О.В. Собениной
Подписано к изданию 08.12.2011.
Уч-изд. л. 8,2.
ФГБОУВПО «Воронежский государственный технический университет»