Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов / В. И. Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.
Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов. В каждом параграфе подробно рассмотрены разнообразные типовые примеры и приведены многочисленные задачи разного уровня сложности для самостоятельного решения.
Сборник состоит из четырнадцати параграфов в 5 главах: I. Алгебра высказываний; II. Булевы функции; III. Формализованное исчисление высказываний; IV. Логика предикатов; V. Элементы теории алгоритмов. Каждый параграф предваряется теоретическими сведениями. Особенно ценным является то, что автор в каждой серии однотипных задач (под буквами, скажем, а)- л)) приводит подробное решение одной или нескольких из них в качестве образца. То есть пособие одновременно может рассматриваться как некое руководство по решению задач.
Для студентов университетов, технических и педагогических вузов, обучающихся по специальностям «Математика», «Прикладная математика».
ОГЛАВЛЕНИЕ
Предисловие ......................................................3
Глава I. АЛГЕБРА ВЫСКАЗЫВАНИЙ ..........................................6
§ 1. Основные понятия алгебры высказываний...................................6
Высказывания и операции над ними (6). Формулы алгебры высказываний (15). Тавтологии алгебры высказываний (20). Логическое следование (24). Равносильность формул (33). Упрощение систем высказываний (39).
§ 2. Нормальные формы для формул алгебры высказываний и их применение..............40
Отыскание нормальных форм (41). Применение нормальных форм (47). Нахождение следствий из посылок (57). Нахождение посылок для данных следствий (62).
§ 3. Приложение алгебры высказываний к логико-математической практике...................68
Обратная и противоположная теоремы (68). Принцип полной дизъюнкции (75). Необходимые и достаточные условия (76). Упрощение систем высказываний (81). Правильные и неправильные рассуждения (82). Нахождение всех следствий из посылок (85). Нахождение посылок для следствий (87). ««Логические» задачи (88).
Глава II. БУЛЕВЫ ФУНКЦИИ ....................................................92
§ 4. Понятие булевой функции и свойства булевых функций ...........92
Число булевых функций (93). Равенство булевых функций (96). Свойства булевых функций (98).
§ 5. Специальные классы булевых функций .....................................101
Полиномы Жегалкина и линейные булевы функции (101). Двойственность и самодвойственные булевы функции (107). Монотонные булевы функции (113). Булевы функции, сохраняющие нуль и сохраняющие единицу (120).
§ 6. Полные системы и функционально замкнутые классы булевых функций .....................123
Полные и неполные системы булевых функций (123). Применение теоремы Поста (125). Функционально замкнутые классы булевых функций (127). Базисы булевых функций (128).
§ 7. Применение булевых функций к релейно-контактным схемам .........................130
Анализ релейно-контактных схем (130). Синтез релейно-контактных схем (138).
Глава III. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ ...............................143
§ 8. Построение формализованного исчисления высказываний
и исследование системы аксиом на независимость ...........143
Построение выводов из аксиом (144). Построение выводов из гипотез (146). Теорема о дедукции и ее применение (150). Производные правила вывода и их применение (154). Независимость системы аксиом (157).
Глава IV. ЛОГИКА ПРЕДИКАТОВ.............................................162
§ 9. Основные понятия логики предикатов.......................................162
Понятие предиката и операции над предикатами (162). Множество истинности предиката (167). Равносильность и следование предикатов (179). Формулы логики предикатов, их интерпретация и классификация (182). Равносильность формул логики предикатов (188). Тавтологии логики предикатов (191). Равносильные преобразования формул (195). Проблемы разрешимости для общезначимости и выполнимости формул (197). Логическое следование формул логики предикатов (200).
§ 10. Применение логики предикатов к логико-математической практике .................204
Записи на языке логики предикатов (204). Правильные и неправильные рассуждения (208). Логика предикатов и алгебра множеств (210). Равносильные преобразования неравенств и уравнений при их решении (212).
§ 11. Формализованное исчисление предикатов...............................213
Построение выводов из аксиом (214). Построение выводов из гипотез (217). Теорема о дедукции и ее применение (218).
Глава У. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ ....................221
§ 12. Машины Тьюринга ....................................................................221
Применение машин Тьюринга к словам (222). Конструирование машин Тьюринга (229). Вычислимые по Тьюрингу функции (237).
§ 13. Рекурсивные функции ...............................................................240
Примитивно рекурсивные функции (240). Примитивно рекурсивные предикаты (246). Оператор минимизации. Обще рекурсивные и частично рекурсивные функции (247).
§ 14. Нормальные алгоритмы Маркова ............................................248
Марковские подстановки (249). Нормальные алгоритмы и их применение к словам (250). Нормально вычислимые функции (253).
Ответы .........................257
Список литературы ..................................................301
