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