В.Л. МАТРОСОВ
М.С. МИРЗОЕВ
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Учебник для бакалавриата
Рекомендовано УМО в качестве учебника для вузов
МОСКВА
2020
Стр.1
УДК 510.6
ББК 22.12
М 63
М 63
В.Л. Матросов , М.С. Мирзоев
Математическая логика: Учебник для бакалавриата /
В.Л. Матросов, М.С. Мирзоев. — М.: Прометей, 2020. — 228 с.
ISBN 978-5-907244-03-0
В учебнике изложены основные понятия математической
логики, язык и средства математической логики, в том числе
системы логических функций и их применение в информатике.
Рассматриваются основные разделы математической логики:
алгебра высказываний; исчисления высказываний и логика предикатов.
Алгоритмическим подходом по шагам представлено доказательство
теорем из аксиоматической теории L. Помимо теоретических
и практических материалов учебник содержит задания
для самостоятельной работы.
Содержание учебника соответствует Федеральному государственному
образовательному стандарту высшего образования
третьего поколения и методическим требованиям, предъявляемым
к учебным изданиям.
Учебник предназначен для студентов высших учебных
заведений, обучающихся по направлению педагогического образования
профилей «Информатика и математика», «Физика
и информатика», «Технология и информатика», «Математика
и информатика», «Прикладная информатика». Может быть
полезен широкому кругу читателей, интересующихся основами
математической логики.
© Матросов В.Л., наследники, 2020
© Мирзоев М.С., 2020
ISBN 978-5-907244-03-0
© Издательство «Прометей», 2020
Стр.2
ОГЛАВЛЕНИЕ
Предисловие. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Введение .......................................... 12
Глава 1. Алгебра высказываний ..................... 21
1.1. Алфавит и формулы алгебры высказываний....... 21
1.2. Основные логические операции алгебры
высказываний............................... 23
1.3. Индуктивное определение формулы
и подформулы алгебры высказывания ........... 24
1.4. Истинностные значения формулы алгебры
высказывания ............................... 26
1.5. Классификация формул алгебры высказываний ... 27
1.6. Понятие равносильности. Основные
равносильные формулы алгебры высказываний ... 28
1.7. Булевы функции (логические функции) .......... 31
1.8. Совершенные нормальные формы ............... 37
1.9. Системы булевых функций . . . . . . . . . . . . . . . . . . . . . 42
1.10. Минимизация булевых функций ............... 54
1.11. Модели функционально-логические схемы
базовых устройств компьютера ................ 76
1.11.1. Логические элементы....................... 76
1.11.2. Моделирование функциональных схем
устройства компьютера ................... 80
1.11.3. Функционально-логическая модель
сумматора................................ 87
1.11.4. Функционально-логическая схема триггера ... 89
1.11.5. Шифраторы и дешифраторы................ 95
— 3 —
Стр.3
Оглавление
1.12. Электронные схемы и компьютер............... 96
1.13. О некоторых других приложениях теории
булевых функций........................... 101
1.14. Некоторые примеры применения языка Java
в алгебре высказываний ..................... 104
Контрольные вопросы и задания................... 124
Практические задания ........................... 126
Глава 2. ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ ......... 132
2.1. Алфавит, формулы, система аксиом и правила
вывода исчисления высказываний ............. 132
2.2. Аксиомы исчисления высказываний ............ 134
2.3. Операция подстановки ....................... 135
2.4. Правила вывода............................. 136
2.5. Понятие формального доказательства . . . . . . . . . . . 136
2.6. Производные правила вывода ................. 138
2.7. Выводимость формулы исчисления
высказываний из совокупности формул
(совокупности гипотез)....................... 141
2.8. Некоторые правила выводимости
из совокупности гипотез H .................... 142
2.9. Примеры доказуемых формул в исчисления
высказываний.............................. 153
2.10. Исследование исчисления высказываний ....... 159
2.11. Полнота исчисления высказываний............ 163
2.12. Независимость системы аксиом исчисления
высказываний ............................. 171
Контрольные вопросы и задания................... 177
Практические задания ........................... 178
Глава 3 ЛОГИКА ПРЕДИКАТОВ ................... 182
3.1. Понятие предиката. Логические операции
над предикатами ............................ 182
3.2. Операции навешивания кванторов.............. 187
3.3. Язык логики предикатов (ЯЛП) ................ 191
3.4. Операция подстановки в ЯЛП.................. 194
3.5. Языки первого порядка....................... 195
— 4 —
Стр.4
Оглавление
3.6. Равносильные формулы языка первого порядка... 203
3.7. Некоторые виды математических теорем......... 209
3.8. Методы доказательств ........................ 211
3.9. Теорема Гёделя о неполноте ................... 222
Контрольные вопросы и задания................... 223
Практические задания ........................... 224
Литература ....................................... 226
— 5 —
Стр.5
ПРЕДИСЛОВИЕ
Математическая логика как основа формирования
интеллекта современного человека, в том числе будущего
специалиста в области информатики и информационных
коммуникационных технологий считается
ядром и главным инструментом изучения и исследования
закономерности информационных процессов
системы различной природы. Искусство рассуждения,
самосознания, строгость математических выводов,
доказательств, вычисления, обобщения, абстракция,
аналогия и интуиция помогают будущему учителю информатики
успешно ориентироваться не только в своей
профессиональной деятельности, но и в организаторских,
социальных, экономических и других жизненно
важных проблемах. Элементы математической логики
присутствуют почти во всех направлениях общеобразовательного
курса информатики (информационные
процессы различных систем, алгоритмизация и программирование,
моделирование и формализация,
информационные технологии, социальная информатика)
и составляют основу архитектуры компьютеров
(новейших процессоров, мультипроцессоров и др.).
Следовательно, знание математической логики играет
ведущую роль в профессиональной деятельности учителя
информатики.
— 6 —
Стр.6