Оглавление | 3
|
Принятые обозначения | 7
|
Введение | 9
|
Глава 1. Алгебра высказываний (АВ) | 13
|
§ 1. Логические операции АВ | 13
|
1. Понятие высказывания | 13
|
2. Логические операции | 14
|
§ 2. Формулы (слова) АВ | 15
|
1. Алфавит языка АВ | 15
|
2. Формулы (слова) АВ | 15
|
3. Таблица истинности формулы АВ | 16
|
§ 3. Классификация формул АВ | 18
|
1. Тавтологии | 18
|
2. Основные правила получения тавтологий | 19
|
3. Выполнимые, опровержимые и тождественно ложные формулы | 19
|
§ 4. Равносильные формулы АВ | 20
|
1. Равносильные формулы | 20
|
2. Признак равносильности | 20
|
3. Отношение эквивалентности | 21
|
4. Основные равносильности АВ | 21
|
5. Равносильные преобразования формул | 23
|
§ 5. Нормальные формы для формул АВ | 23
|
1. Нормальные формы | 23
|
2. Полная система связок (ПСС) | 24
|
3. Существование ДНФ и КНФ | 25
|
§ 6. Совершенные нормальные формы для формул АВ | 25
|
1. Совершенные нормальные формы | 25
|
2. Замечательное свойство СКО и его приложения | 26
|
3. Существование СДНФ | 27
|
4. Замечательное свойство СДО и его приложения | 28
|
5. Существование СКНФ | 29
|
§ 7. Логическое следствие | 31
|
1. Понятие логического следствия | 31
|
2. Признаки логического следствия | 31
|
3. Логическое следствие и правила логических умозаключений | 33
|
3.1. Правило логического вывода | 33
|
3.2. Правила логических умозаключений | 33
|
3.3. Метод доказательства от противного | 34
|
4. Алгоритм нахождения логического следствия из данной совокупности посылок | 36
|
5. Понятие теоремы в АВ | 38
|
5.1. Взаимно обратные и взаимно противоположные теоремы | 38
|
5.2. Необходимые и достаточные условия | 39
|
Глава 2. Булевы функции | 40
|
§ 1. Булевы функции от одной переменной | 40
|
§ 2. Булевы функции от двух переменных | 40
|
1. Стрелка Пирса и штрих Шеффера | 41
|
2. Множество булевых функций от двух переменных | 42
|
§ 3. Булевы функции от n переменных | 42
|
§ 4. Булевы функции и формулы АВ | 45
|
§ 5. Полные системы булевых функций | 46
|
§ 6. Специальные классы булевых функций | 46
|
1. Теорема Поста | 48
|
§ 7. Приложение булевых функций к релейно-контактным схемам | 52
|
1. Для схемы из двух последовательно соединенных контактов x и y | 53
|
2. Для схемы из двух параллельно соединенных контактов x и y | 53
|
Глава 3. Логика предикатов | 55
|
§ 1. Понятие предиката | 55
|
§ 2. Классификация предикатов | 56
|
§ 3. Множество истинности предиката | 57
|
§ 4. Равносильные предикаты. Следствие предиката | 57
|
§ 5. Логические операции над предикатами | 58
|
1. Отрицание | 58
|
2. Конъюнкция | 59
|
3. Дизъюнкция | 61
|
4. Импликация и эквиваленция | 62
|
§ 6. Кванторные операции над предикатами | 64
|
1. Квантор общности | 64
|
2. Квантор существования | 66
|
§ 7. Формулы логики предикатов | 67
|
1. Алфавит логики предикатов | 67
|
2. Классификация формул логики предикатов | 69
|
3. Тавтологии | 70
|
4. Равносильные преобразования формул логики предикатов | 75
|
5. Приведенная форма | 76
|
6. Предваренная нормальная форма | 77
|
7. Проблема разрешимости | 79
|
8. Проблема разрешимости для формул на конечных множествах | 79
|
9. Проблема разрешимости для формул от одноместных предикатных переменных | 80
|
10. Проблема разрешимости для ∀-формул и ∃-формул | 84
|
§ 8. Приложения логики предикатов | 85
|
1. Символьная запись математических определений | 86
|
2. Строение математических теорем | 86
|
3. Методы доказательства теорем | 88
|
4. Логика предикатов в алгебре множеств | 90
|
Глава 4. Формализованное исчисление высказываний | 92
|
§ 1. Система аксиом и теория формального вывода | 92
|
1. Первоначальные понятия аксиоматической теории | 92
|
2. Понятие вывода и его свойства | 94
|
3. Производные правила | 99
|
§ 2. Полнота и другие свойства формализованного исчисления высказываний | 101
|
1. Синтаксис и семантика | 101
|
2. Лемма о выводимости | 102
|
3. Полнота формализованного исчисления высказываний | 105
|
4. Непротиворечивость формализованного исчисления высказываний | 107
|
5. Разрешимость формализованного исчисления высказываний | 108
|
6. Независимость системы аксиом формализованного исчисления высказываний | 108
|
7. Независимость аксиомы (А1) | 109
|
8. Независимость аксиомы (А2) | 112
|
9. Независимость аксиомы (А3) | 113
|
Примерный перечень вопросов к зачёту и экзамену по учебной дисциплине «Математическая логика» | 115
|
Задачи и упражнения для самостоятельного решения | 117
|
1. Алгебра высказываний | 117
|
2. Булевы функции | 138
|
3. Логика предикатов | 165
|
Список литературы | 174
|