Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007

Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007.

Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов. В каждом параграфе подробно рассмотрены разнообразные типовые примеры и приведены многочисленные задачи разного уровня сложности для самостоятельного решения. 

Для студентов университетов, технических и педагогических ВУЗов, обучающихся по специальностям «Математика», «Прикладная математика».




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


Примеры.
1.15. Из трех данных высказываний А, В, С постройте такое составное высказывание, которое:
а) истинно тогда и только тогда, когда все данные высказывания истинны;
б) ложно тогда и только тогда, когда все данные высказывания ложны;
в) истинно тогда и только тогда, когда все данные высказывания ложны;
г) ложно тогда и только тогда, когда все данные высказывания истинны;
д) истинно тогда и только тогда, когда истинны высказывания А и В;
е) истинно тогда и только тогда, когда ложны высказывания А и В;
ж) ложно тогда и только тогда, когда истинны высказывания An В;
з) ложно тогда и только тогда, когда ложны высказывания А и В;
и) истинно тогда и только тогда, когда все данные высказывания либо истинны, либо ложны;
к) ложно тогда и только тогда, когда все данные высказывания либо истинны, либо ложны;
л) ложно тогда и только тогда, когда ложно лишь высказывание С.

Решение, л) Искомое высказывание должно быть ложно лишь в одном случае: когда высказывание Сложно, а оба высказывания А и В истинны. Таким высказыванием могло бы стать высказывание вида M→С, где высказывание М должно быть истинно и так сконструировано из высказываний А и В, что если хотя бы одно из высказываний А или В будет ложным, то ложным станет и М. Ясно, что в качестве М следует взять конъюнкцию А ∩ В. Итак, искомое высказывание имеет следующий вид: (А ∩ В) → С.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать книгу Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007 - djvu - depositfiles.

Скачать книгу Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007 - djvu - Яндекс.Диск.




Теги: математика :: математическая логика :: теории алгоритмов :: Игошин