Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов ОНЛАЙН


Сборник состоит из четырнадцати параграфов в 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



Читать онлайн
скачать бесплатно


Теги:
сборник задач по математической логике, задачи по математической логике, задачи по теории алгоритмов, Игошин сборник задач, упражнения по математической логике

Коментарі до Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов ОНЛАЙН