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

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

  Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов. В каждом параграфе подробно рассмотрены разнообразные типовые примеры и приведены многочисленные задачи разного уровня сложности для самостоятельного решения. Теоретический материал изложен в учебном пособии: Игошин В. И. Математическая логика и теория алгоритмов. — М. : Издательский центр «Академия», 2004.
Для студентов университетов, технических и педагогических вузов, обучающихся по специальностям «Математика», «Прикладная математика».




Примеры.
Определите значения истинности следующих высказываний:
а) Если 9 делится на 3, то 4 делится на 2;
б) Если 11 делится на 6, то 11 делится на 3;
в) Если 15 делится на 6, то 15 делится на 3;
г) Если 15 делится на 3, то 15 делится на 6;
д) Если Саратов расположен на Неве, то слоны — насекомые;
е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3;
ж) 4 > 5 тогда и только тогда, когда -4 > -5;
з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3;
и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4;
к) Если 12 делится на 6, то 12 делится на 3;
л) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

Найдите наипростейшую из равносильных формул от трех переменных, которая:
а) всегда принимает то же значение, что и ее второй аргумент;
б) принимает такое же значение, как и большинство ее аргументов;
в) принимает значение 1 тогда и только тогда, когда точно два ее аргумента принимают значение 0;
г) принимает такое же значение, как и меньшинство ее аргументов;
д) принимает значение 0 тогда и только тогда, когда по крайней мере один из первого и третьего аргументов принимает значение 0;
е) принимает значение 1 тогда и только тогда, когда большинство ее аргументов принимают значение 0;
ж) принимает значение 0 тогда и только тогда, когда большинство ее аргументов принимают значение 1;
з) принимает значение 1 тогда и только тогда, когда принимают значение 1 первый аргумент и один и только один из двух оставшихся;
и) принимает значение 1 тогда и только тогда, когда из первых двух ее аргументов принимает значение 1 ровно один;
к) принимает значение 0 тогда и только тогда, когда два ее последних аргумента принимают различные значения;
л) принимает значение 1 тогда и только тогда, когда либо первый ее аргумент равен 1, либо все аргументы равны 0.

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



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

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


Скачать - pdf - Яндекс.Диск.




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