Сборник задач по математической логике и теории алгоритмов, Игошин В.И., 2019

Сборник задач по математической логике и теории алгоритмов, Игошин В.И., 2019.

   Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов: 1. Содержательная логика высказываний; II. Булевы функции; III. Содержательная логика предикатов; IV. Формальные логические теории; V. Элементы теории алгоритмов. В каждом параграфе подробно рассматриваются разнообразные типовые примеры и даются многочисленные задачи разного уровня сложности для самостоятельного решения. Теоретический материал изложен в учебниках: Игошин В.И. Математическая логика: Учеб, пособие. М.: ИНФРА-М, 2012. 399 с. + CD-R. (Высшее образование); Игошин В.И. Теория алгоритмов: Учеб, пособие. М.: ИНФРА-М, 2012. 318 с. (Высшее образование).
Для студентов университетов, технических и педагогических вузов, обучающихся как на уровне бакалавриата, так и на уровне магистратуры по направлениям «Математика», «Информатика», «Прикладная математика и информатика», «Математика и компьютерные науки», «Бизнес-информатика», «Математик-педагог», «Учитель математики».




Приложения алгебры высказываний к логико-математической практике.
В этом параграфе собраны разноплановые задачи, объединяемые тем, что при решении каждой из них могут быть применены методы алгебры высказываний. Первая группа задач посвящена нахождению обратных и противоположных теорем для исходных прямых теорем, имеющих разнообразные логические структуры. Далее следуют задачи на применение принципа полной дизъюнкции (теоремы об обратимости системы импликаций) для доказательства справедливости обратных теорем, на установление необходимых и достаточных условий, на упрощение совокупностей высказываний, на построение умозаключений из данных посылок.

Заключительная группа задач этого параграфа — это, как их иногда называют в школьной практике, логические задачи, или задачи на рассуждение. Некоторые из них могут быть решены и без применения алгебры высказываний, «методом рассуждений», но методы алгебры высказываний обеспечивают гарантированный успех при их решении.

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

Купить .





Теги: задачник по математике :: математика :: Игошин