| От автора | 6
|
| Предисловие | 8
|
| Глава 1. История возникновения математической логики | 10
|
| 1.1. Общие сведения | 10
|
| 1.2. Некоторые вопросы оснований математики | 12
|
| 1.3. Пример математической теории | 13
|
| 1.4. Проблемы Давида Гильберта | 15
|
| 1.5. Применение математической логики | 16
|
| Глава 2. Алгебра высказываний | 18
|
| 2.1. Высказывания | 18
|
| 2.2. Логические операции | 20
|
| 2.3. Формулы алгебры высказываний | 24
|
| 2.4. Функции алгебры высказываний | 30
|
| 2.5. Основные равносильности | 31
|
| 2.6. Задачи для самостоятельной работы | 36
|
| 2.7. Приведенные формулы | 37
|
| 2.8. Минимизация функций алгебры высказываний | 38
|
| 2.9. Минимизация функций в классе ДНФ | 39
|
| 2.10. Релейно-контактные схемы | 42
|
| 2.11. Контактные схемы | 49
|
| 2.12. Проблема минимизации контактных схем | 51
|
| 2.13. Функция Шеннона для контактных схем | 52
|
| 2.14. Достаточное условие минимальности | 54
|
| 2.15. Задачи для самостоятельной работы | 55
|
| 2.16. Схемы из функциональных элементов | 59
|
| 2.17. Функция Шеннона для схем из функциональных элементов | 63
|
| 2.18. Задачи для самостоятельной работы | 64
|
| Глава 3. Исчисление высказываний | 69
|
| 3.1. Описание исчисления высказываний | 70
|
| 3.2. Аксиомы исчисления высказываний | 72
|
| 3.3. Правила вывода | 72
|
| 3.4. Производные правила вывода | 75
|
| 3.5. Некоторые правила исчисления высказываний | 76
|
| 3.6. Выводимость из гипотез | 78
|
| 3.7. Теорема дедукции | 823.8. Примеры вывода секвенций||85
|
| 3.9. Некоторые правила исчисления высказываний (продолжение) | 87
|
| 3.10. Монотонность в исчислении высказываний | 99
|
| 3.11. Эквивалентные формулы | 104
|
| 3.12. Примеры вывода секвенций (продолжение) | 108
|
| 3.13. Приведенные формулы | 122
|
| 3.14. Непротиворечивость исчисления высказываний | 124
|
| 3.15. Полнота исчисления высказываний | 127
|
| 3.16. Независимость аксиом | 133
|
| 3.17. Задачи для самостоятельной работы | 137
|
| Глава 4. Логика предикатов | 139
|
| 4.1. Предикаты | 139
|
| 4.2. Одноместные предикаты | 142
|
| 4.3. Кванторы | 143
|
| 4.4. Формулы логики предикатов | 145
|
| 4.5. Равносильные формулы | 146
|
| 4.6. Приведенные формулы | 148
|
| 4.7. Нормальные формулы | 149
|
| 4.8. Проблема разрешения | 150
|
| Глава 5. Исчисление предикатов | 154
|
| 5.1. Символы | 154
|
| 5.2. Формулы | 155
|
| 5.3. Правила вывода | 156
|
| 5.4. Правила связывания квантором | 159
|
| 5.5. Непротиворечивость и полнота | 161
|
| 5.6. Некоторые теоремы исчисления предикатов | 164
|
| 5.7. Приведенные формулы | 171
|
| 5.8. Закон двойственности | 172
|
| 5.9. Некоторые теоремы исчисления предикатов (продолжение) | 174
|
| 5.10. Задачи для самостоятельной работы | 180
|
| Глава 6. Машины Тьюринга | 182
|
| 6.1. Историческая справка | 182
|
| 6.2. Определение машины Тьюринга | 184
|
| 6.3. Анализ машин Тьюринга | 186
|
| 6.4. Синтез машин Тьюринга | 187
|
| Заключение | 195
|
| Рекомендуемая литература | 196
|
| Готический алфавит | 197
|
Супрун Валерий Павлович Кандидат технических наук, доцент механико-математического факультета Белорусского государственного университета. Область научных интересов — дискретная математика и вычислительная техника. Автор около 350 изобретений в области автоматики и вычислительной техники. Награжден золотой медалью и дипломом Всемирной организации интеллектуальной собственности (ВОИС) как "Лучший изобретатель Беларуси 2006 года". Заслуженный работник Белорусского государственного университета.
Автор 80 научных статей по дискретной математике, а также учебных пособий "Математика для старшеклассников: Задачи повышенной сложности" (URSS), "Математика для старшеклассников: Нестандартные методы решения задач" (URSS), "Математика для старшеклассников: Методы решения и доказательства неравенств" (URSS), "Математика для старшеклассников: Дополнительные разделы школьной программы" (URSS), "Математика для старшеклассников: Нестандартные методы решения уравнений повышенной сложности" (URSS), "Основы теории булевых функций" (URSS), "Основы математической логики" (URSS). Многие книги автора были переведены и выходили в URSS также на испанском языке.
