Сборник задач по математической логике и теории алгоритмов: учебное пособие для студентов высших учебных заведений, обучающихся по направлению 44.03.01 "Педагогическое образование" (квалификация Бакалавр)

Титульный лист Выходные данные Предисловие Глава I. СОДЕРЖАТЕЛЬНАЯ ЛОГИКА ВЫСКАЗЫВАНИЙ § 1. Основные понятия алгебры высказываний Формулы алгебры высказываний Тавтологии алгебры высказываний Равносильность формул алгебры высказываний Упрощение систем высказываний Логическое следование формул алгебры высказываний § 2. Нормальные формы для формул алгебры высказываний и их применение Отыскание нормальных форм Применение нормальных форм Нахождение следствий из посылок Нахождение посылок для данных следствий § 3. Приложения алгебры высказываний к логико-математической практике Обратная и противоположная теоремы Принцип полной дизъюнкции Упрощение систем высказываний Правильные и неправильные рассуждения Задачи Льюиса Кэрола Нахождение всех следствий из посылок Нахождение посылок для следствий «Логические» задачи Глава II. БУЛЕВЫ ФУНКЦИИ § 4. Понятие булевой функции и свойства булевых функций Число булевых функций Равенство и сравнение булевых функций Существенные и несущественные аргументы булевых функций Симметрия булевых функций Некоторые соотношения для булевых функций Свойства булевых функций § 5. Специальные классы булевых функций Полиномы Жегалкина и линейные булевы функции Двойственность и самодвойственные булевы функции Монотонные булевы функции Булевы функции, сохраняющие нуль и сохраняющие единицу § 6. Полные системы и функционально замкнутые классы булевых функций Полные и неполные системы булевых функций Применение теоремы Поста Функционально замкнутые классы булевых функций Базисы булевых функций § 7. Применение булевых функций к релейно-контактным схемам Анализ релейно-контактных схем Синтез релейно-контактных схем § 8. Применение булевых функций к логическим схемам из функциональных элементов (функциональным схемам) Анализ функциональных схем Синтез функциональных схем Глава III. СОДЕРЖАТЕЛЬНАЯ ЛОГИКА ПРЕДИКАТОВ § 9. Основные понятия логики предикатов Понятие предиката и операции над предикатами Множество истинности предиката Равносильность и следование предикатов Формулы логики предикатов, их интерпретация и классификация Равносильность формул логики предикатов Тавтологии логики предикатов Равносильные преобразования формул Проблемы разрешимости для общезначимости и выполнимости формул Логическое следование формул логики предикатов § 10. Применение логики предикатов к логико-математической практике Записи на языке логики предикатов Правильные и неправильные рассуждения Логика предикатов и алгебра множеств Равносильные преобразования неравенств и уравнений при их решении Глава IV. ФОРМАЛЬНЫЕ ЛОГИЧЕСКИЕ ТЕОРИИ § 11. Формализованное исчисление высказываний Построение выводов из аксиом Построение выводов из гипотез Теорема о дедукции и ее применение Производные правила вывода Независимость системы аксиом Генцена—Клини Полнота, непротиворечивость и разрешимость исчисления высказываний, построенного на базе системы аксиом Генцена—Клини § 12. Формализованное исчисление предикатов Построение выводов из аксиом Построение выводов из гипотез Теорема о дедукции и ее применение Глава V. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ § 13. Машины Тьюринга и вычислимые по Тьюрингу функции § 14. Рекурсивные функции Примитивно рекурсивные функции Примитивно рекурсивные предикаты Оператор минимизации. Общерекурсивные и частично рекурсивные функции § 15. Нормальные алгоритмы Маркова и нормально вычислимые функции Марковские подстановки Нормальные алгоритмы и их применение к словам Нормально вычислимые функции Ответы Список литературы Оглавление